[PDF] [PDF] Math 127: Infinite Cardinality - CMU Math

[PDF] Bijective Proof Examples

8 fév 2017 · We have defined a function f : {0, 1}n → P(S) Because f is injective and surjective , it is bijective Problem 2 Prove there exists a bijection between 

[PDF] Countability

Since we have found a bijection between these two sets, this tells us that in fact We will prove that this function f : N → Z is a bijection, by first showing that it is 

[PDF] Mathematics 220 Homework 12 Not to be handed in 1 - UBC Math

bijective (Proof: one can prove that a function is bijective by showing that the inverse function exists m ≥ 1, we have that n ≤ n+m−1 Thus we really have  

[PDF] MATH 220 (all sections)—Homework  not to be turned in posted

24 nov 2017 · Prove or disprove: There exists a bijective function f : Q → R Disproof: if there were such a bijective function, then Q and R would have the same

[PDF] Math 127: Finite Cardinality - CMU Math

number of things in an infinite set, we will use the idea of bijection to The number of different rationals between 0 and 1 that have denominator m is certainly m+1 1 [Proof of Theorem 1] Suppose that X and Y are finite sets with X = Y = n

[PDF] Math 127: Infinite Cardinality - CMU Math

You proved in that homework exercise that f is a bijection That means that we have a bijection 1 Page 2 from N to Z, and therefore 

[PDF] BIJECTIVE COUNTING 1 Binomial and Multinomial Coefficients

monotonic provided that x ≤ y in M implies f(x) ≤ f(y) in N We have the class of {1, 2, ,n} Proposition 3 1 The map ̂ cyc : Sn → Sn is a bijection Proof

[PDF] Contents 1 Introduction - Harvard Mathematics Department

The subset of elements of A that have a multiplicative inverse in A are usually denoted n + 1 is as well Proof by induction that people can live arbitrarily long: let P(n) be the A function is bijective if it is both injective and surjective Graphs

[PDF] Lecture 19 1 Overview 2 Comparing Sizes via Functions

27 mar 2019 · In this lecture, we will learn how to compare the “sizes” of two sets that both have an infinite Recall that A bij B means there exists a bijective function from A to B, and A inj include these proofs for infinite sets below

[PDF] 3 Countable and Uncountable Sets

bijection f : {1, ,n} → A Otherwise the set A is called infinite Two Theorem 3 3 There is no surjection from a set A to P(A) Proof Consider any function f : A → P( A) and let B = {a ∈ Aa ∈ f(a)} As a corollary we have the following result

[PDF] 1 part to 5 parts gallon

[PDF] 1 part to 50 parts water

[PDF] 1 to 1 dilution calculator

[PDF] 1 to 1 dilution ratio

[PDF] 1 to 1 serial dilution

[PDF] 1 to 10 dilution example

[PDF] 1 ton ac equals how many btu

[PDF] 1 ton ac equals how many watts

[PDF] 1 ton ac max room size

[PDF] 1 ton ac means

[PDF] 1 ton ac means how many kw

[PDF] 1 ton ac means how much btu

[PDF] 1 ton ac means what

[PDF] 1 ton ac room size india

[PDF] 1 ton ac room size pakistan

Math 127: Innite Cardinality

Mary Radclie

1 Denitions

Recall that when we dened niteness, we used the notion of bijection to dene the size of a nite set. In

particular, we dened a nite set to be of sizenif and only if it is in bijection with [n]. For innite sets, this strategy doesn't quite work. What set do we take to biject to in order to dene

innity? It's not immediately clear that there is a \canonical" set we can use for the denition. So instead,

we use a denition for innite sets based on what was a theorem in the world of nite sets. Denition 1.LetXandYbe innite sets. We say thatjXj=jYjif there exists a bijectionf:X!Y. We say a setXiscountably inniteifjXj=jNj. IfXis innite, but it is not countably innite, we say thatXisuncountably innite, or justuncountable. A setXis calledcountableif it is either nite or countably innite. It can be a bit confusing that the wordcountabledoes not imply countably innite. In general, you can think ofcountableas really meaning that a set isenumerable. We saw in lecture that when talking about nite sets, we have the following: Proposition 1.A setXis nite if and only if the elements ofXcan be enumerated in a terminating list asX=fx1;x2;:::;xng. For countably innite sets, we have a similar structure: Proposition 2.A setXis countably innite if and only if the elements ofXcan be enumerated in an interminable list asX=fx1;x2;x3;:::g. The proof of this proposition is immediate from the denition: ifXis countably innite, then there exists a bijectionf:N!X, which immediately provides a way to enumerate the elements ofX, taking x i=f(i). Hence, we can think of the word \countable" as really being about enumeration. A set is countable if it can be enumerated, regardless of if the enumeration terminates.Example 1.Zis countable. Actually, you've already proven this, even though you may not have realized it. In Homework 6, problem 15, you saw the following functionf:N!Z f(x) = x2 xis even x12 xis odd: You proved in that homework exercise thatfis a bijection. That means that we have a bijection1 fromNtoZ, and therefore by denitionZis countably innite. Another way to approach this, of course, is to attempt to enumerate (aka, list) the elements ofZ. Certainly we can list the elements ofZ; there are many ways to do so. Here is one:

Z=f0;1;1;2;2;3;3;4;4;:::g:The fact thatZis the same size asNmay be a bit surprising. Indeed,Nis a proper subset ofZ, and

in fact there are innitely many elements ofZthat are not a part ofN. Nevertheless, they are the same size! We will nd this happens a lot in the world of innity.

2 Countable Innity

Here, let's consider how our favorite set operations and functions interact with countable sets. We begin

with a characterization of countability: Theorem 1.LetXbe a nonempty set. The following are equivalent:

1.Xis countable.

2.

Ther eexists a surje ctionf:N!X.

3.

Ther eexists an inje ctiong:X!N.

Before we write the proof, a quick word on the phrasing \the following are equivalent," which is sometimes abbreviated as TFAE. This construction is a short hand for saying \there is an if and only

if between each of the following statements." Here, if we think of the three statements as propositions

p

1;p2;p3, the theorem is statingp1,p2,p3.

In proving TFAE type theorems, it's common to prove a cycle of implications. That is, instead of provingp1,p2, and alsop2,p3, and alsop1,p3, we would prove the shorter set of statements p

1)p2, andp2)p3, andp3)p1. These three implications are sucient to get all parts of the if

and only ifs on the three propositions, since if we start from any one proposition we can follow a series of

implications to any other.

That being said, let's prove Theorem 1.

Proof.LetXbe a nonempty set.

(1)2)Supp osethat Xis countable. We wish to show that there exists a surjectionf:N!X. We consider two cases, according as whetherXis nite. Case 1:Xis nite. Then for somen2N, there exists a bijectionh: [n]!X. Letx02Xbe some element ofX. Denef:N!Xby f(k) =h(k) 1kn x

0kn+ 1:

Sincehis bijective,f([n]) =h([n]) =X, and hencefis a surjective function. Case 2:Xis innite. SinceXis countable, we must therefore have thatXis countably innite. Then by denition, there exists a bijectionf:N!X, which is by denition surjective.

(2)3)Supp osethere exists a surjectiv efunction f:N!X. We wish to show that there exists an injection

g:X!N. This is proven in HW7 Problem 1. 2 (3)1)Supp osethere exists an injectiv efunction g:X!N. We wish to show thatXis countable. IfXis nite, we are done. Suppose, then, thatXis an innite set and there exists an injective functiong:X!N. LetS= g(X)N. Sincegis injective, andXis innite, we have thatSis also innite. Moreover, asSN, we can writeS=fs1;s2;s3;:::gby takings1= min(S),s2= min(Snfs1g),s3= min(Snfs1;s2g), etc. Hence we have thatSis a countably innite set. Moreover, the functiong0:X!Sdened by g

0(x) =g(x)8x2Xis a bijection, and hencejXj=jSj. Therefore,Xis countably innite.

This theorem will allow us to prove that sets are countable, even if we don't know that the functions

we construct are exactly bijective, and also without actually knowing if the sets we consider are nite or

countably innite. Let's see an example of this in action.Example 2.IfXandYare countable sets, thenX[Yis also a countable set.

Proof.Suppose thatXandYare countable. By Theorem 1, there exists surjective functions f:N!Xandg:N!Y.

Dene a functionh:N!(X[Y) by

h(k) =f(k2 )kis even g(k+12 )kis odd: Sincefandgare surjective, we have thath(N) =f(N)[g(N) =X[Y, and thushis a surjective

function. Hence, by Theorem 1, we have thatX[Yis countable.In the above example, we are able to determine that the set we wish to consider is countable, even

without knowing whether or notXorYis countably innite or nite, and without knowing what their intersection looks like. Using the result of Theorem 1, we can also prove the following, which is assigned as a homework

exercise. This allows us to take advantage of the structure of Theorem 1 when it is more convenient to

use a dierent set fromN. Theorem 2.LetXbe a nonempty set, and letYbe a countably innite set. Then TFAE:

1.Xis countable.

2.

Ther eexists a surje ctivefunction f:Y!X.

3.

Ther eexists an inje ctivefunction g:X!Y.

The following theorem will be quite useful in determining the countability of many sets we care about.

Theorem 3.Letn2N, and letX1;X2;:::;Xnbe nonempty countable sets. ThennY i=1X i=X1X2 Xnis countable. Proof.We work by induction onn. The base case, thatn= 1, is trivial, asnY i=1X i=X1, which is countable by hypothesis.

For the sake of illustration, we consider also the case thatn= 2. The technique for this case will also

be used in the inductive step, so it is worth our time to consider it. 3 LetX1;X2be countable sets. WriteX1=fx1;x2;x3;:::g, and writeX2=fy1;y2;y3;:::g; we note that these enumerations can be terminating, or not. Recall thatX1X2=f(x;y)jx2X1;y2X2g:We can visualize the elements ofX1X2in a table, as follows:x 1x 2x 3x 4::: y

1(x1;y1)(x2;y1)(x3;y1)(x4;y1):::

y

2(x1;y2)(x2;y2)(x3;y2)(x4;y2):::

y

3(x1;y3)(x2;y3)(x3;y3)(x4;y3):::

y

4(x1;y4)(x2;y4)(x3;y4)(x4;y4):::

..Now, in order to show thatX1X2is countable, it suces to show thatX1X2is enumerable. Using the table, we cannot enumerate the set by tracing rst the rows or the columns; ifX2is innite, then

enumerating along the rst row will never terminate, and we will never arrive at the second row! So, we

will have to be more clever. Our clever idea will be as follows. While it's true that the rows and columns of the matrix are

potentially innite in length, the diagonals of the matrix are not. So we can try to enumerate by following

the diagonals:x 1x 2x 3x 4::: y

1(x1;y1)(x2;y1)(x3;y1)(x4;y1):::

y

2(x1;y2)(x2;y2)(x3;y2)(x4;y2):::

y

3(x1;y3)(x2;y3)(x3;y3)(x4;y3):::

y

4(x1;y4)(x2;y4)(x3;y4)(x4;y4):::

..Following these paths, we achieve the following enumeration forX1X2: X Another way to think of this enumeration is as follows: we enumerate (xi;yj) by rst listing all the elements withi+j= 2, then listing all the elements withi+j= 3, then listing all the elements with

i+j= 4, and so on. Each of these is a nite set, and hence this will yield a full enumeration of all of

X 1X2. Now, for the inductive step, suppose that we know that the Cartesian product of anyncountable sets is itself countable. Consider the productX1X2 XnXn+1, all of which are countable. PutY=X1X2Xn. Note that there is a bijectionf:YXn+1!X1X2XnXn+1, by ((a1;a2;:::;an);an+1)7!(a1;a2;:::;an;an+1). Moreover, by the induction hypothesis,Yis countable. Applying the technique above to the productYXn+1, since bothYandXn+1are countable, we have thatYXn+1is countable. Moreover,YXn+1is in bijection withX1X2 XnXn+1, and henceX1X2 XnXn+1is also countable. Thus, as the result is true for anynby induction, the theorem holds.

It is important to note that this theorem applies only to a nite length Cartesian product; if we wish

to take an innite length Cartesian product, things can go very dierently for us, which we shall see in

Section 3 below. However, this theorem has an immediate, delightful corollary: 4 Corollary 1.The set of rational numbersQis countably innite. Proof.Recall from Example 1 thatZis countable. Since there is an injectionf:Znf0g !Zdened byf(x) =xfor allx, by Theorem 2, we also have thatZnf0gis countable. Therefore, by Theorem 3, we have thatZ(Znf0g) is countable. Consider the functiong:Z(Znf0g)!Qdened byg((a;b)) =ab . Note that this is well dened, as

b6= 0. Moreover, since every element ofQcan be expressed in at least one way as a ratio of integers with

a nonzero denominator, we have thatgis surjective. But then by Theorem 2, we have thatQis countable. Finally,Qis not nite, asNQ, and any subset of a nite set must also be nite.

Therefore,Qis countably innite.

Amazing! So we have then that three of our favorite number sets are all countably innite. Indeed, thoughNZQ, all three sets have the exact same cardinality, and are in bijection with each other! Finally, we note the following theorem, whose proof is left as a homework exercise. Theorem 4.LetX1;X2;X3;:::be a countable list of countable sets. Then1[ i=1X iis countable.

The proof will look similar to that of Theorem 3: if we can write the elements of the union in a table,

we can then trace the diagonals of the table to enumerate the elements. A word on the proof: be careful

with notation! It gets, well, messy.

3 Uncountable Innity

So, ifN;Z;andQare all the same size, what aboutR? Is that also countable? Sadly, no. The real numbers are a whole new ballgame. What we will actually prove here is that the

real numbers between 0 and 1 are not countable; this will certainly imply that the set of all real numbers

is not countable.

To prove that, we're gonna have to do a little work. This is a classic argument called Cantor's Diago-

nalization, and in order to employ it, we need a Lemma rst. Lemma 1.Every real number between 0 and 1 can be represented uniquely in base 10 representation as

0:d1d2d3:::, where thedirepresent digits between 0 and 9, and the digits have the property that8n2N,

9mn,dm6= 9.

Let's think carefully about what this is saying. First, we want to represent our numbers in base 10; no

problem there, we already did that long ago in our notes on Understanding Number Sets. The last part of

the statement is saying that we do not want a representation that ends in just a bunch of 9s forever. As

we have seen before, 0:9999= 1, so a decimal that terminates in all 9s can be simplied. For example:

0:12362574999999= 0:12362574 + 0:0000000099999= 0:12362574 + 0:00000001 = 0:12362575:

Hence, we'd like to forbid a decimal from going to all 9s. Moreover, the Lemma claims that if we are able

to do so, then the decimal representation of the number is unique. Proof.[Proof of Lemma 1] That each number can be represented as a decimal in base 10 expansion is

already known; we need only prove uniqueness of the representation under the condition that no represen-

tation terminates in all 9s. 5 Suppose thatxis a real number between 0 and 1, and that we have two decimal representations of xthat satisfy the given condition; that is, we can writex= 0:d1d2d3= 0:c1c2c3:::, neither of which terminate with innitely many 9s. We work by induction to show thatdn=cnfor alln. For the base case, considerd1;c1. Suppose thatd16=c1; wolog say thatd1< c1. Note then that x= 0:c1c2c3 0:c1. On the other hand, since at least onedn, forn2 is not a 9, we have that x0:d1= 0:0d2d3<0:1, and thusx <0:(d1+ 1)0:c1. Hence, 0:c1x <0:c1, which is impossible.

Therefore,d1=c1.

For induction, suppose that for somen2Nwe know thatdk=ckfor allkn. Considery= 10nxd1d2:::dn= 0:dn+1dn+2dn+3= 0:cn+1cn+2cn+3:::. By repeating the above argument, we obtain thatdn+1=cn+1. Therefore, by induction, we have thatdn=cnfor alln, and hence the desired decimal representation ofxis unique. Theorem 5.The set of real numbers between0and1is uncountable. Proof.We work by contradiction. WriteX=fx2Rj0< x <1g. Suppose thatXis countable. ClearlyXis innite, and hence by denition, there exists a bijectionf:N!X.

For eachn2N, writef(n) = 0:d(n)

1d(n) 2d(n)

3:::to be the unique decimal representation off(n)

guaranteed by Lemma 1. Deney2Xwith decimal representationy= 0:y1y2y3:::, where for eachn2N, we dene y n=8 :d (n)n1 ifd(n)n6= 0;1

1 ifd(n)n= 0

2 ifd(n)n= 1

Note thatysatises the condition in Lemma 1, since in fact none of the digits ofyare 9s. Moreover, by denition 0< y <1, since none of the digits ofyare 0s. Therefore,y2X, and hence sincefis a bijection,y=f(n) for somen2N.

Therefore,y= 0:y1y2y3= 0:d(n)

1d(n) 2d(n)

3=f(n). By Lemma 1, we must therefore have that

y i=d(n) ifor alli2N. But by denition,yn6=d(n)n, and hence we have a contradiction. Therefore, it must be the case thatXis not countable. SinceXis innite, then,Xis uncountable. This theorem shows that a particular subset ofRis uncountable, which of course implies thatRitself

is uncountable. Moreover, we can form a bijection fromXdescribed in the Theorem toR, as follows.Example 3.The setX=fx2Rj0< x <1gis in bijection withR.

Proof.Dene a functionf:X!Rbyf(x) =2x1xx2. Note that as 0;1=2X, this is a well-dened function. We claim it is a bijection. To demonstrate this, we show an inverse. Letg:R!Xbe dened byg(y) =y2+p4+y22yfory6= 0, andg(0) =12 . We rst claim

that this is well-dened; we need to show thatg(y)2Xfor ally. Note that for ally6= 0,p4 +y2p44y+y2=jy2j, and henceg(y)>y2+jy2j2y0.

Therefore,gis well dened. Moreover, we have forx=12 , by denitiongf(x) =x. Forx6=12 ,6 gf(x) =g2x1xx2

2x1xx22 +r4 +

2x1xx2

22

2x1xx2

2x21xx2+q4x24x+1+4(xx2)2(xx2)24x2xx2

2x21 +p4x24x+ 1 + 4x28x3+ 4x44x2

2x21 +p4x48x3+ 8x24x+ 14x2

2x21 +p(2x22x+ 1)24x2

4x22x4x2=x

ThusgfX. Similarly, one can show thatfgR. Therefore,gis an inverse tof, and in

particular, then,fis a bijection.Hence, we have that sinceXis uncountable, andjXj=jRj, also we know thatRis uncountable.

A similar type of argument as in the proof of Theorem 5 can be used (and will be, in homework!) to prove the following.

Theorem 6.LetXbe any set. ThenjXj We have already proven this theorem for nite sets in previous homework. For innite sets, it is

equally true. Note what this implies: if we have one set of innite size, then we can generate innitely

many dierent sizes of innity by repeatedly taking power sets. Indeed, the following sets

N;P(N);P(P(N));P(P(P(N)));:::

are all of dierent cardinality, increasing in size from left to right. Moreover, it is not too dicult to

show the following.

Theorem 7.The setRis in bijection withP(N).

To prove this theorem one can work with binary representations of elements inX, rather than decimal representations as was done in Lemma 1 and Theorem 5. We have seen, in the nite counting notes, that

P(X) is in bijection with the strings of 0s and 1s; we can use this to construct a bijection with decimal

representations of numbers.

3.1 The Continuum Hypothesis and Incompleteness

Ok, so we have a bunch of innities. But every set we've actually looked at takes only one of two sizes.

In some cases, we like to give a name to the sizes of innity; these are cardinal numbers, and in fact they

have a whole algebra of their own, which we here omit. But a fundamental question then arises:

Are these all the possible sizes of innity?

7 To be really specic, let's consider a question. We know thatNandRhave dierent cardinalities; we proved that in the work above. So here is a question.

Is there any setSsuch thatjNj That is to say, can we construct a set whose size is in between that ofNandR? Or is there nothing in between? Even more, what about the other sizes of innity? We saw above thatjP(X)j 6=jXjfor any X, so an even more general version of our question above could be phrased as follows: LetXbe an innite set. Is there any setSsuch thatjXjI would love to answer this question for you, and I think a lot of mathematicians would. We have just

one problem here:

The answer to this question cannot be known.

Now that sounds a little bit crazy, and it feels pretty bad. But this is the question that lead to a famous, important theorem in mathematics known as Godel's Incompleteness Theorem. We're not going

to get into the nitty gritty details here, but the broad strokes of the idea are like this. First we rephrase

our question as a proposition. This proposition is often referred to as the Continuum Hypothesis. p: There does not exist any setSwithjNjThen the \answer" to the question just becomes the truth value of the proposition: if the proposition is

True, then no suchSexists, and if the proposition is False, then such a set does exist, and we have not

found all the innities. In the 1940s, a mathematician named Godel proved something resembling the following statement: Using the standard mathematical axioms,pcannot be proven to be False. In the 1960s, a mathematican named Cohen followed up with something resembling the following statement: Using the standard mathematical axioms,pcannot be proven to be True. Let's be very clear about what is being said here. What Godel and Cohen are doing is not a proof

that the statement is true or false, but a proof about proofs themselves. Specically, what Godel proved

is that there is no proof that the statement is false. This does not, of course, mean that there IS a proof

that the statement is true, as we see in Cohen's follow up theorem. Indeed, the set of proofs that one can

write using the standard set of axioms about mathematics simply DO NOT INCLUDE a proof about this statement. Its truth cannot be known, at all. Well, ne. We could get around this, if we wanted, by simply adding a new axiom that asserts thatp

is either true or false, depending upon your preference. Godel and Cohen's work actually shows that this

is a logically consistent thing to do; the Continuum Hypothesis can be taken as either true or false and

nothing about the existing axiomatic structure will break. But even before this work, in the 1930s, Godel proved a theorem that might make this solution less than satisfying. This result is known as the Godel Incompleteness Theorem. Suppose you have an axiomatic system of mathematics. Then you can make statements that are neither provable nor unprovable in that system. 8 That is to say, assuming the truth value of the Continuum Hypothesis does not end this conundrum.

At some point, mathematics will bump up into another proposition that cannot be proven true and cannot

be proven false. Godel's Incompleteness Theorem says that this is unavoidable: you will never be able to

create an axiom system for which every proposition has a knowable truth value.

This, of course, is very sad-making for mathematicians. Our whole schtick is caring about problems for

which proofs or disproofs are not known. We may never know, working on a problem, whether the truth of that question is even knowable, let alone how to solve it ourselves.

Incidentally, both Godel and Cantor, after successful careers studying the nature of innity, ended their

lives completely crazy. Cantor died in a mental institution, after having moved in and out of sanatoria for

the last 34 years of his life. Godel was paranoid that people were out to get him; he died of starvation

after refusing to eat for months, claiming all his food was being poisoned. (Cohen seemed to do just ne

for himself, giving lectures on mathematics and the continuum problem up until his death in 2007.) 9quotesdbs_dbs30.pdfusesText_36