[PDF] 1+1+100 dilution
[PDF] 1.00 of minutes conversion chart
[PDF] 1.5 line spacing in points
[PDF] 1/0 welding cable
[PDF] 1/0 wire
[PDF] 1/10 dilution factor
[PDF] 1/10 dilution series
[PDF] 1/10 serial dilution
[PDF] 1/12 octave band frequencies
[PDF] 1/2 log serial dilution
[PDF] 1/2 normal saline for hypernatremia
[PDF] 1/2 normal saline hypotonic
[PDF] 1/2 normal saline iv
[PDF] 1/2 normal saline iv solution
[PDF] 1/2 normal saline meq
![[PDF] Chapter 7 Cardinality of sets](https://pdfprof.com/Listes/27/60202-27cardinality.pdf.pdf.jpg "[PDF] Chapter 7 Cardinality of sets")
Christopher HeilA Short Review of CardinalityJune 24, 2017 c ?2017 Christopher Heil
Chapter 1CardinalityWe will give a short review of the definition of cardinality and prove somefacts about the cardinality of sets. Throughout, the set of natural numbersis denoted by
N={1,2,3,...},
the set of integers is
Z={...,-1,0,1,...},
the set of rational numbers is
Q={m/n:m,n?Z, n?= 0},
the set of real numbers is
R={x:xis a real number},
and the set of complex numbers is
C={a+ib:a,b?R}.
1.1 The Definition of Cardinality
We say that two setsAandBhave the same cardinalityif there exists a bijectionfthat mapsAontoB,i.e., if there is a functionf:A→Bthat is both injective and surjective. Such a functionfpairs each element ofAwith a unique element ofBand vice versa, and therefore is sometimes called a1-1 correspondence. Example 1.1.1.(a) The functionf: [0,2]→[0,1] defined byf(x) =x/2 for 1
21 Cardinality
cardinality. This shows that a proper subset of a set can have the same cardinality as the set itself. (b) The functionf:N→ {2,3,4,...}defined byf(n) =n+ 1 forn?N is a bijection, so the set of natural numbersN={1,2,3,...}has the same cardinality as its proper subset{2,3,4,...}. (c) The functionf:N→Zdefined by f(n) =? n
2,ifnis even,
n-1
2,ifnis odd,
is a bijection, so the set of integersZhas the same cardinality as the set of natural numbersN. (d) Ifnis a finite positive integer, then there is no way to define a function f:{1,...,n} →Nthat is a bijection. Hence{1,...,n}andNdo not have the same cardinality. Likewise, ifm?=nare distinct positive integers, then {1,...,m}and{1,...,n}do not have the same cardinality.♦
1.2 Finite, Countable, and Uncountable Sets
We use cardinality to define finite sets and infinite sets, as follows. Definition 1.2.1 (Finite and Infinite Sets).LetXbe a set. We say thatXisfiniteifXis either empty or there exists an integern >0 such thatXhas the same cardinality as the set{1,...,n}.That is, a nonempty
Xis finite if there is a bijection of the form
f:{1,...,n} →X.
In this case we say thatXhasnelements.
We say thatXisinfiniteif it is not finite.♦
We use the following terminology to further distinguish among sets based on cardinality. Definition 1.2.2 (Countable and Uncountable Sets).We say that a set Xis: denumerableorcountably infiniteif it has the same cardinality as the natural numbers, i.e., if there exists a bijectionf:N→X, countableifXis either finiteorcountably infinite,
uncountableifXis not countable.♦
1.2 Finite, Countable, and Uncountable Sets3
Every finite set is countable by definition, and parts (b) and (c) of Ex- ample 1.1.1 show thatN,Z,and{2,3,4,...}are countable. Here is another countable set. Example 1.2.3.ConsiderN2=N×N=?(j,k) :j,k?N?,the set of all or- dered pairs of positive integers. We display the elements ofN2as the following table of pairs (with additional arrows that we will shortly explain): (1,1)→(1,2) (1,3)→(1,4) (1,5)→(1,6) (2,1) (2,2) (2,3) (2,4) (2,5) (3,1) (3,2) (3,3) (3,4) (4,1) (4,2) (4,3) (5,1) (5,2) (6,1) (6,2) (7,1) The first line of pairs in this table includes all ordered pairs whose first component is 1,the second line of pairs lists those whose first component is 2,and so forth. We define a bijectionf:N→N2by following the arrows in the table:f(1) = (1,1), f(2) = (1,2), f(3) = (2,1), f(4) = (3,1), f(5) = (2,2), f(6) = (1,3), f(7) = (1,4), f(8) = (2,3), In other words, oncef(n) has been defined to be a particular ordered pair (j,k),then we letf(n+ 1) be the ordered pair that (j,k) points to next. In this way the outputsf(1),f(2),f(3),...give us a list of every ordered pair inN2.ThusNandN2have the same cardinality, soN2is denumerable and hence countable.♦ In Example 1.2.3 we showed how to create alistof the all of the elements ofN2.In the same way, ifXis any countable set then we can create a list of
41 Cardinality
the elements ofX.There are two possibilities. First, a countableXset might be finite, in which case there exists a bijectionf:{1,2,...,n} →Xfor some positive integern.Sincefis surjective, we therefore have
X= range(f) =?f(1), f(2), ..., f(n)?.
Thus the functionfgives us a way to list thenelements ofX.On the other hand, ifXis countably infinite then there is a bijectionf:N→X,and hence
X= range(f) =?f(1), f(2), f(3), ...?.
Thus the elements ofXhave been again been listed in some order. For example, Example 1.2.3 shows that we can list the elements ofN2in the following order: N
2=?(1,1),(1,2),(2,1),(3,1),(2,2),(1,3),(1,4),(2,3), ...?.
It may seem more natural to depictN2as a "two-dimensional" table, but becauseN2is countable we can also make a "one-dimensional"listof all of the elements ofN2.
1.3 Uncountability of the Real Line
Now we will show that there exist infinite sets that are not countable. LetS be the open interval (0,1),which is the set of all real numbers that lie strictly between zero and one:
S= (0,1) =?x?R: 0< x <1?.
We will use an argument by contradiction to prove thatSis not countable. First we recall that every real number can be written in decimal form. In particular, if 0< x <1 then we can write x= 0.d1d2d3...=∞? k=1d k 10k, where each digitdkis an integer between 0 and 9.Some numbers have two decimal representations, for example 1
2= 0.5000...=510+∞?
k=2010k, but also
1.4 Facts about Cardinality5
1
2= 0.4999...=410+∞?
k=2910k.(1.1) Any number whose decimal representation ends in infinitely many zeros also has a decimal representation that ends in infinitely many nines, but all other real numbers have a unique decimal representation. Suppose thatSwas countable. In this case there would exist a bijection f:N→S,and therefore we could make a list of all the elements ofS.If we letxn=f(n),then we can writeSas follows: S= range(f) ={f(1), f(2), f(3), ...}={x1, x2, x3, ...}. This is a list of every real number between 0 and 1.Further, we can write eachxnin decimal form, say, x n= 0.dn1dn2dn3..., where each digitdnkis an integer between 0 and 9. Now we will create another sequence of digits between 0 and 9.In fact, in order to avoid difficulties arising from the fact that some numbers have two decimal representations, we will always choose digits that are between 1 and 8. To start, lete1be any integer between 1 and 8 that does not equald11(the first digit of the first numberx1). For example, if the decimal representation ofx1happened to bex1= 0.72839172...,then we lete1be any digit other than 0,7,or 9 (so we might takee1= 5 in this case). Then we lete2be any integer between 1 and 8 that does not equald22(the second digit of the second numberx2), and so forth. This gives us digitse1,e2,...,and we letx be the real number whose decimal expansion has exactly those digits: x= 0.e1e2e3...=∞? k=1e k 10k. Thenxis a real number between 0 and 1,soxis one of the real numbers in the setS.Yetx?=x1,because the first digit ofx(which ise1) is not equal to the first digit ofx1(why not-what ifx1has two decimal representations?). Similarlyx?=x2,because their second digits are different, and so forth. Hencexdoes not equal any element ofS,which is a contradiction. Therefore
Scannot be a countable set.
1.4 Facts about Cardinality
Here are some properties of countable and uncountable sets (the proof is assigned as Problem 1.5.4).
61 Cardinality
Lemma 1.4.1.IfXandYare sets, then the following statements hold. (a)IfXis countable andY?X,thenYis countable. (b)IfXis uncountable andY?X,thenYis uncountable. (c)IfXis countable and there exists an injectionf:Y→X,thenYis countable. (d)IfXis uncountable and there exists an injectionf:X→Y,thenYis uncountable.♦ Example 1.4.2.(a) LetQ+={r?Q:r >0}be the set of all positive rational numbers. Ifr?Q+,then there is a unique way to writeras a fraction in lowest terms. That is,r=m/nfor a unique choice of positive integersm andnthat have no common factors. Therefore, by settingf(r) = (m,n) we can define an injective map ofQ+intoN2.SinceN2is countable andfis injective, we apply Lemma 1.4.1 and conclude thatQ+is countable. A similar argument shows thatQ-,the set of negative rational numbers, is countable. Problem 1.5.5 tells us that a union of finitely many (or countably many) countable sets is countable, so it follows thatQ=Q+?Q-? {0}is countable. (b) We saw above thatS= (0,1) is uncountable. SinceRcontainsS, Lemma 1.4.1 implies thatRis uncountable. Also, every real number is a complex number, so the real lineRis a subset of the complex planeC.
ThereforeCis uncountable as well.
(c) LetI=R\Qbe the set of irrational real numbers. SinceR=I?Q,if Iwas countable thenRwould be the union of two countable sets, which is countable by Problem 1.5.5. This is a contradiction, so the set of irrationals must be uncountable. ThusQis countable whileIis uncountable. This may seem counterin- tuitive since between any two rational numbers there is an irrational, and between any two irrational numbers there is a rational number!♦
1.5 Problems
1.5.1.Prove equation (1.1).
1.5.2.Prove that ifA, B,andCare sets, then the following statements hold.
(a)Ahas the same cardinality asA. (b) IfAhas the same cardinality asB,thenBhas the same cardinality asA. (c) IfAhas the same cardinality asBandBhas the same cardinality as
C,thenAhas the same cardinality asC.
1.5 Problems7
1.5.3.Prove that the closed interval [0,1] and the open interval (0,1) have
the same cardinality by exhibiting a bijectionf: [0,1]→(0,1).
Hint: Do not try to create acontinuousfunctionf.
1.5.4.Prove Lemma 1.4.1.
1.5.5.(a) Show that ifXandYare countable sets, then their unionX?Y
is countable. (b) Prove that the union of finitely many countable setsX1,...,Xnis countable. (c) Suppose thatX1,X2,...are countably many sets, each of which is countable. Prove that?∞k=1Xk=X1?X2?···is countable. Thus the union of countably many countable sets is countable. Hint: Consider the table that appeared in Section 1.2 depicting the ele- ments ofN2.
1.5.6.LetFbe the set of all functions that map real numbers to real num-
bers, i.e.,Fis the set of all functions of the formf:R→R. Suppose thatRandFhad the same cardinality. Then there would exist a bijectionG:R→ F.This functionGmaps a real numberxto a function inF.Let us call this functionfx.That is, to simplify the notation we will writefxinstead ofG(x).Each real numberxcorresponds to a functionfx, and sinceGis onto we know that every function isGequals some function f xfor somex.
Now define a functiong:R→Rby setting
g(x) =fx(x) + 1,forx?R. For example, iffxhappened to take the value 100 atx,then we would declare thatg(x) isg(x) =fx(x) + 1 = 101.For each numberx,we look at the functionfx,take the output offxat the pointx,and add 1 to that to get the value that we assign tog(x).Prove thatgis a function that maps real numbers to real numbers, and thereforegbelongs toF.Also prove that there is nox?Rsuch thatg=fx.That is, show that no matter whatx that we choose,g(t) andfx(t) cannot be equal for everyt?R,sogandfx cannot be the same function. Explain why this is a contradiction, and use this to show thatRandFdonothave the same cardinality.quotesdbs_dbs31.pdfusesText_37
[PDF] Cardinality