复旦大学：《离散数学》PPT教学课件（赵一鸣）06/28

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 nN,      + − = 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 ❖ AA, AA。 ❖ Russell’s paradox: Let S={A|AA}. The question is, does SS? ❖ i.e. SS or SS? ❖ If SS, ❖ If SS, ❖ The statements " SS " and " SS " 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

II Introductory Combinatorics Chapter 4 Introductory Combinatorics k Countin P100(Sixth) P88(Fifth)

II Introductory Combinatorics Chapter 4 Introductory Combinatorics Counting P100(Sixth) P88(Fifth)

Combinatorics, is an important part of discrete mathematics Techniques for counting are important in computer science, especially in the analysis of algorithm. ☆ sorting, searching g combinatorial algorithms . Combinatorics

❖ Combinatorics, is an important part of discrete mathematics. ❖ Techniques for counting are important in computer science, especially in the analysis of algorithm. ❖ sorting,searching ❖ combinatorial algorithms ❖ Combinatorics

☆ existence counting 今 construction ☆ optimization 4 existence Pigeonhole principle .& o Counting techniques for permutation and combinations, and Generating function, and Recurrence relations

❖ existence ❖ counting ❖ construction ❖ optimization ❖ existence :Pigeonhole principle ❖ Counting techniques for permutation and combinations,and Generating function, and Recurrence relations

4.1 Pigeonhole principle .o Dirichlet 1805-1859 ☆ shoebox principle

4.1 Pigeonhole principle ❖ Dirichlet,1805-1859 ❖ shoebox principle

4.1.1 Pigeonhole principle Simple form o If n pigeons are assigned to m pigeonholes, and m<n, then at least one pigeonhole contains two or more pigeons. &o Theorem 4.1: If n+1 objects are put into n boxes. then at least one box contain tow or more of the objects

4.1.1 Pigeonhole principle :Simple Form ❖ If n pigeons are assigned to m pigeonholes, and m<n, then at least one pigeonhole contains two or more pigeons. ❖ Theorem 4.1: If n+1 objects are put into n boxes, then at least one box contain tow or more of the objects