February 21, 2018 - Page 2 of 2 - Shawn Zhong

$Cardinality • The cardinality of a set A is equal to the cardinality of a set B, denoted |A|=|B|, • if and only if there is a one-to-one correspondence (i.e., a bijection) from A to B • If there is a one-to-one function (i.e., an injection) from A to B, then • the cardinality of A is less than or equal to the cardinality of B and we write |A|≤|B| • When |A|≤|B| and A and B have different cardinality, • we say that the cardinality of A is less than the cardinality of B and write |A||B| Countable and Uncountable • A set that is either finite or has the same cardinality as Z+ is called countable. • A set that is not countable is uncountable. • The set of real numbers R is an uncountable set. • When an infinite set is countable (countably infinite) its cardinality is ℵ_0 • (where ℵ is aleph, the 1st letter of the Hebrew alphabet). • We write |S|=ℵ_0 and say that S has cardinality “aleph null.” Showing that a Set is Countable • An infinite set is countable iff it is possible to list the elements of the set in a sequence. • A 1-1 correspondence f from the set of positive integers to a set S can be expressed • in terms of a sequence a_1,a_2,…,a_n where a_1=f(1), a_2=f(2),…,a_n=f(n) • Example 1: The set of positive even integers E is countable set. ○ Let f(x)=2x ○ ■8(1&2&3&4&…@↕&↕&↕&↕&↕@2&4&6&8&…) ○ Then f is a bijection from N to E since f is both one-to-one and onto. ○ To show that it is one-to-one, suppose that f(n)=f(m). ○ Then 2n=2m, and so n=m. ○ To see that it is onto, suppose that t is an even positive integer. ○ Then t=2k for some positive integer k and f(k)=t. • Example 2: The set of integers Z is countable. ○ Can list in a sequence: 0, 1, − 1, 2, − 2, 3, − 3,… ○ Or can define a bijection from N to Z: § f(2n)=−n § f(2n+1)=n+1 • Example 3: The positive rational numbers are countable. § A rational number can be expressed as p/1 where p,q∈Z and q≠0. ○ Note: § p and q such that q≠0. ○ The positive rational numbers are countable since they can be arranged in a sequence • Example 4: Union of countable sets is countable ○ A={a_1,a_2,…,a_n,…} ○ B={b_1,b_2,…,b_n,…} ○ A∪B={a_1,b_1,a_2,b_2,…,a_n,b_n,…} • Example 5: The set of all rationals is countable ○ Q={0}∪Q+∪Q− ○ f(−p/q)=p/q is a bijiection from Q− to Q+ • Example 6: The set of finite string S over a finite alphabet A is counitable infinite ○ A={a,b} ○ List all strings with length § 0: λ § 1: a, b § 2: aa,ab,ba,bb § 3: aaa,aab,aba,abb,baa,bab,bba,bbb § ⋯ • Example 7: Show that the set of all Java program is countable ○ Just list all the strings Hilbert’s Grand Hotel • The Grand Hotel has countably infinite number of rooms, each occupied by a guest. • We can always accommodate a new guest at this hotel. • How is this possible? • Because the rooms of Grand Hotel are countable • We can list them as Room 1, Room 2, Room 3, and so on. • When a new guest arrives, we move the guest in Room n to Room n+1 • This frees up Room 1, which we assign to the new guest, and all the current guests still have rooms. • The hotel can also accommodate a countable number of new guests, all the guests on a countable number of buses where each bus contains a countable number of guests The Real Numbers are Uncountable • The method is called the Cantor diagnalization argument • Suppose R is countable. Then the real numbers between 0 and 1 are also countable • The real numbers between 0 and 1 can be listed in order r1 , r2 , r3 ,… . • Let the decimal representation of this listing be ○ r_1=0.d_11 d_12 d_13… ○ r_2=0.d_21 d_22 d_23… ○ r_3=0.d_31 d_32 d_33… • Form a new real number with the decimal expansion r=0.s_1 s_2 s_3… where ○ s_n={■8(4&d_nn=4@3&d_nn≠3)┤ • r is not equal to any of the r_1,r_2,r_3,… • Because it differs from r_i in its i-th position after the decimal point. • Therefore there is a real number between 0 and 1 that is not on the list • since every real number has a unique decimal expansion. • Hence, all the real numbers between 0 and 1 cannot be listed • so the set of real numbers between 0 and 1 is uncountable. • Since a set with an uncountable subset is uncountable • the set of real numbers is uncountable. Computability • We say that a function is computable if there is a computer program in some programming language that finds the values of this function. • If a function is not computable we say it is uncomputable. • There are uncomputable functions. • We have shown that the set of Java programs is countable. • We can show that the set of functions f:N→N is uncountable • Therefore there must be uncomputable functions$

Shawn Zhong

Shawn Zhong

2.5 Cardinality of Sets

Search

WeChat Account