3.4 Cardinality Definition 3.7: The empty set is a finite set of cardinality 0. If there is a one-to-one correspondence between A and the set {0,1,2,3 19, then A is a finite set of cardinality n Definition 3.8: A set A is countably infinite if there is a one-to-one correspondence between a and the set n of natural number We write A=NNo. A set is countable if it is finite or countably infinite
3.4 Cardinality ❖ Definition 3.7: The empty set is a finite set of cardinality 0. If there is a one-to-one correspondence between A and the set {0,1,2,3,…, n-1}, then A is a finite set of cardinality n. ❖ Definition 3.8: A set A is countably infinite if there is a one-to-one correspondence between A and the set N of natural number. We write |A|=|N|=0 . A set is countable if it is finite or countably infinite
4 Example: The set z is countably infinite o Proof: f :N-Z, for any nEN, n is even number f(n)= (n+1) n is odd number 2
❖ Example: The set Z is countably infinite ❖ Proof: f:N→Z,for any nN, + − = n n is odd number n n is even number f n ( 1) 2 1 2 1 ( )
%o The set Q of rational number is countably infinite, i.e. QFIN=Noo 0,11≠80 .8 Theorem 3.13 The r of real numbers is not countably infinite And rlo, 1 &o Theorem 3.14: The power set P(N of the set n of natural number is not countably infinite AndP(NR=s. 4 Theorem 3.15(Cantor's Theorem): For any set, the power set of X is cardinally larger than X &N, P(N, P(P(N)
❖ The set Q of rational number is countably infinite, i.e. |Q|=|N|=0 . ❖ |[0，1]| 0 . ❖ Theorem 3.13: The R of real numbers is not countably infinite. And |R|=|[0，1]|. ❖ Theorem 3.14: The power set P(N) of the set N of natural number is not countably infinite. And |P(N)|=|R|=1 . ❖ Theorem 3.15(Cantor’s Theorem): For any set, the power set of X is cardinally larger than X. ❖ N, P (N),P (P (N)),…
3.5 Paradox ☆1. Russells paradox 令A∈A,AgA。 o Russells paradox: Let SAAsA. The question is, does s∈S sie.S∈ Sor SEs? IsEs, 冷IfS∈S, ☆ The statements"S∈s"and"SgS" cannot both be true. thus the contradiction
3.5 Paradox ❖ 1.Russell’s paradox ❖ AA, AA。 ❖ Russell’s paradox: Let S={A|AA}. The question is, does SS? ❖ i.e. SS or SS? ❖ If SS, ❖ If SS, ❖ The statements " SS " and " SS " cannot both be true, thus the contradiction
☆2. Cantor, s paradox 81899, Cantor's paradox, sometimes called the paradox of the greatest cardinal expresses what its second name would imply--that there is no cardinal larger than every other cardinal 冷 Let s be the set of all sets..S?≤|P(S)or P(S)?≤(S .g The third crisis in mathematics
❖ 2.Cantor’s paradox ❖ 1899,Cantor's paradox, sometimes called the paradox of the greatest cardinal, expresses what its second name would imply--that there is no cardinal larger than every other cardinal. ❖ Let S be the set of all sets. |S|?|P (S)| or |P (S)|?|(S)| ❖ The Third Crisis in Mathematics