1、計算機問題求解-論題1-11-有限與無限2017年12月14日“聰明的經理”、“非常聰明的經理” 和“非常非常聰明的經理”你能給我們講講這個故事嗎?“希爾伯特旅館”/article/cantors-infinite/集合的等勢Tb make precise what it means for two sets (even two infinite sets) to have the same number of elements, we need a definition. We say that a set A is equivalent t

2、o a set B if there exists a bijection f : A f B. We write A B for A is equivalent to B. (Other authors use the words equipotent or cquinumerous：.會墨什么樣的呢?問題3:如何精確定義什么是有限集?We say that a setS is finite if either S=0 or if $ is equivalent to the set 1, 2,閨 n* * *#tor some positive integer 兒 o更力口數學化的表述：（

3、每一個自然數也是一個集合）空集記為0;如果k是自然數，則其“后繼”為：k k。于是：有限集就是與某個自然數等勢的集合。問題&提示：有限集就是與某個自然數等勢的集合A set is infinite if it is not finiteA set is infinite if and only if for every natural number the set has a subset whose cardinality is that natural number.自然數集與整數集等勢> N explicitly as follows：* f lx/(%) =10*-(1

4、+ 2a) otherwise“排隊”130,-1, 1,-2, 2,-3, 3,-4, 4,-5, 5,阿題猊關于雙射的證明(1)_ t -2-3 explicitly 筋 follows：注意：小)=尸 心不能遺漏了 case 3!八| (1 + 2x) otherwise/Proof that f is one-to-one*/Let mf n e Z and suppose that / pn) Lf (網)Case L Suppose that m 三9 and n 三 0. Then f (m) = 2m and /(r?) = 2n* Tlius 2m = 2nf and the

5、refore m = n.Case 2. Suppose that 之 0 and h < Q. Then f(m) = 2m 1 and /(h) = 2n Thus, 2m 1 = 2n 1F and therefore m = n. /Case 3. Suppose/that one of the two, say is nonnegative, and the other is negative. Then f(m) = 2m and /(n) = 2n 1. Thus 2,i = 1. But this means that a門 numb(1 i;2m, is equal t

6、o an odd nu mbt?n 2n 1, which is impossible.Therefore, if f(m) = only case 1 and case 2 can occur In either of these eases, we have shown that m = n. Thus / is one-to- one.關于雙射的證明(2)f: Z N explicitly as follows：2x if a > 0 1八 r *1.八' -(1+Zv) otherwisePn)of that f maps Z onto N.Let k g N. If k

7、 is even, then k = 2m for some m g Z with m > 0. Thus, m Z and f (m) = 2m = k. If k is odd, then k + 1 is even, Hence m = (k + 1)/(2) Z. Since k > lr we have m < 0. Thus, f(rn) = -2m 1 = 2(Jc + 1)/(2) 1 = k. We conclude that for all k £ N there exists m g Z such that f(m) = k. Since f

8、: Z N is a well-defined function, / maps Z onto N.無窮不僅僅是“很多很多Galileo Galilei伽利略悖論:Not necessary !It is possible to define comparisons amongst infinite sets in a meaningful way!整體與局部“一樣大”！1The ideas of less, equal, and greater apply to (what we would now call) finite sets , but not to infinite sets !

9、https:/wiki/Galileo%27s_paradoxTheorem 206Let A, B C and D be nonempty sets. Suppose that AHB = 0f CDD = 0t A x Cf andBD. Then A UBCU D.Comllarv 20JkLet A andB be disjoint sets. If A and B are finite, then AUB is finite.1-mTMMM_ _JMExercise 21.12. Use induction to prove the following

10、. Let m G 勿. If A2)A/ are finite sets, then the union IJ/= 1 A/ is finite.Let S be a finite set. Then every subset of S is finite.Theorem 20.12*The廿山日用of tu心fimte sas is .用用"問題7:為什么“鴿巢原理”在證 明一個集合是無限集合時 有關鍵的應用？對于Definition 154. Let f i A B be a function and CCA. The restriction of f to C is the

11、function f |c : C B defined by fc (x) = /(x) for all a G CThe restriction ? is not one-to-one, then f cannot be one-to-one鴿巢：“證明策略”和“數學定理”In its popu lar form, the principle says that if there are more pigeons than holes f then at least one hole is the home of more than one pigeon. 1Theorem 2E2 | Pi

12、geonhole principle).Let m and n be positive integers with m > nf and letf be a map satisfying f : lj r m > 11 j Then f is not one-to-one.f The proof of the pigeonhole principle summarizes much of what"' you learned： mathematical induct ion ? proof in cases, and one-to-one jfiinctions.

13、JProof. We will prove this theorem by induction on n. The assertion that we will prove is: For every integer m such that m > % if f : 1)一 m 一 L .then f is not one-to-one.For the induction step, let n e Z+ and suppose that if m is an integer greater than n and f is a function f : L . .m 1.then f i

14、s not one-to-one. We will show that if m > w + 1 and f : 1 .，m 1+ 1, then f is not one-to-one.So let us suppose that m > n + 1 and we have a mapf : 1., m 7 1 + 1.There are three cases to consider: Either f maps nothing to n + 1, more than one element to + 1, or exactly one element to n + 1.For

15、 the first case, " + 1 is not in the range of 八 so f actually defines a map f : 1,* j? > 1 Since m十 1 > n, our induction hypothesis tells us that / is not one-to-one, and we are done in this case.In case two, there exist j、k e 1,with j ' k, and /(y)= + 1 = Then f is not one-to-one, an

16、d we are done in this case, loo.For the last ctise, we may assume that / G 1 一 .is the only integer for which f(j)=" + 1. We now define the function g : L > 1,/? that interchanges m with j and leaves all other elements of 1 m fixed:(?° ?)(?)= ?%?(?)= ?+ 1.I kifWm g(0=(J if * = mI in if

17、k = j(?° ?1,?.1 maps 1, ,?- 1 tol,？； By H, (?。?i,?-1 is not one-to-one.Then(？?° ? cannot be one-to-one; As ?is one-to-one, So ?cannot be one-to-one;問題7:為什么“鴿巢原理”在證 明一個集合是無限集合時 有關鍵的應用？自然數集是無限集,反證法無限變有限，構造鴿子與籠子/Suppose to the contrary that N is finite. Since N # 0 there exists an integer m a

18、nd a one-toone mapping. gy of N onto |lr2.Now 1,2, _., +1| 三 N so we may consider the restriction g|t2 .w+i： (121) 一 12 . The pigeonhole principle (Theorem2L2 ) implies that g|( 12 也+“ is not one-to-one. Thisr in turn, implies (as you surely showed in Exercise 20.9) that g is not one-to-one, contrad

19、icting our choice of g. Therefore, it must be the case that N is infinite,有限集合的“勢” (cardinality)rhcorcm 21.6.Let A be a nonempty finite set. There is a unique positive integer n such that A v lf.(n|.正因為這樣的n的唯一性，可以定義集合的“勢”。問題死如果不唯一2怎樣能構造出與鴿巢原理”的矛盾來?An infinite set A is said to be countably infinite i

20、f A % NA set is countable if it is either finite or countably infinite.a nonempty set A is countable if and only if there exists a one-to-one function f ： A - N.J注意：這個性質使得我們可以不區分有限或無限可數； 通常找一個一對一的函數比找一個雙射容易。可數集的子集是可數集可以比擬為“輔助線”的定理：Every subset of ? is countable“N與其任一無限子集T之間存在雙射”證明的基本思路：1 .建立一個函數f :f

21、(k戶T中第k個“最小”元素；2 .證明f是一對一的：函數值構成嚴格遞增序列；3 .證明f是滿射：對T中任何元素s，假設比s小的元素有n個, 則f (n+1)=s。有理數集是可數集我們似乎沒法“數”有理數，但是有理數集是“可數”集。I see it but I do not believe it -Geore CantorfWe will begin by showing that Q+ is countable. We define f ： Q+ > N x N as follows. Write each member of Q+ as p/q where p, q > 0 a

22、nd p/q is in reduced form； that is, p and q have no positive common factor other than 1. Now define f(p/q) = Because p/qis in reduced form, f is well-defined and one-to-one. Since N * /is countable (Theorem 22.81 and /(Q+) is a subset of it, we knowfrom CoroHary 22.4 that f(Q+) is countable. Hence Q

23、+ is countable.Now the set of negative nationals, Q-f is equivalent to Q+. Since Q = Q+ U Q_ U 0，and we have a finite union of countable sets, we use Corollary 22.7 to conclude that Q is countable. Since Q is infinite we know that it is countably infinite,但是實數集不是可數集!Cantor ' s diagonalization ar

24、gument反證：假設實數集可數a bijective function f : Z (0/)、,/( 1 i = O.aii«i2«i3 /(2) = 0. 21a22a23 /(3)= 0.”31432a33 ,9flf m = o.斯斯2 斯3 ann.矛盾一Since every subset of a countable set is countable, the open interval (0,1) must be (infinitely) countablefb - U.bib2 b3 .|Let me circle the digits in the di

25、agonalLet me construct a number with these digits:Give me any list of reg Is, and I'll find reals you forgot 8 3 18 5 3 0 7.I'll now change every digit of this number: 0,769762.,.I know for sure that this real number is not in/article/cantors-infinite/直線上的點集與平面上的點集等勢康托爾定理-沒有“最大”的集合任何集合與其募集不等勢即：A? (A)證明要點：設g是從A到(A)的函數，構造集合B如下:問題10:你從這 個證明中看到康 托爾對角線證明 法了嗎？B=x| x A,但x g(x)因為，如果有這樣的x,則x B iff. x B因此，g不可能是滿射則B (A),但不可能存在x A,能滿足g(x)=B