※ 引述《jacksoncsie (Nov)》之铭言： : 想问一下这题， : 虽然明天可能会公布解答 : 但想知道我的想法是正确的吗? : https://i.imgur.com/65LRlwN.jpg : 我认为的确证明有理数是要透过其digital一对一至x : 但题目对映的方式应该是检查所有对映点1~j : 应该是这部分有问题 我的想法不知道有没有错? 这题目挺有趣的，想把我学到的观念分享给大家，有错还请帮忙指出XD ----------Prerequisite--------------------------------- 看这题目前要先知道甚麽是 countable 以及 Cantor's diagonal argument #Countable(可数): 我们说一个集合A是countable是指说A里面的elements 要麽是finite有限个 要麽是infinite，并且存在一种对应M: A -> N, M是1-1和onto，N是所有自然数 (更简单的说，A里面每个数字都可以一个一个枚举出来) #Cantor's diagonal argument: Cantor利用一种叫diagonalization的技巧(不是线代里的diagonalization) 来证明实数R是uncountably infinite 这边我们只要了解他证明里的精神即可，我举个简单的例子， EX: Prove that the set of real numbers in (0, 1) is uncountable <pf> 方便起见，令 A = the set of real numbers in (0, 1) 用反证法，假设A是countable，我们就可以把A里每个数 都一一列出来(这边顺序随意)，譬如说 x1 = 0.123456789... x2 = 0.234567890... x3 = 0.345678901... x4 = 0.456789012... x5 = 0.567890123... ... Claim: 我们可以在这个set里找到一个x，不是任何xi (这边打个比方，我们把A的数字全部倒出来，然後一个一个写在清单上， 当我们再把全部数字倒回A後，再取一个数字x出来， 发现他居然不在这个清单上，进而得到矛盾。) 这个数字x是谁呢？ 我们令x小数点後的第一个digit不同於x1, 第二个digit不同於x2，以此类推。 以我们上面的例子来讲： x1 = 0.123456789... x2 = 0.234567890... x3 = 0.345678901... x4 = 0.456789012... x5 = 0.5678901234 ... 取 x = 0.21456... 或是 x = 0.38697... 都可以 (x不是唯一的，只要x与任何一个xi都不同於至少1个digit都ok) 因为 x != xi, for any i, and x is in A -> 矛盾产生 -> 所以A是uncountable (可以看到上面黄色数字形成对角线，所以叫diagonal argument) --------------Prerequisite Done----------------------- 回到题目，题意是 X = (0, 1)之间的所有有理数的子集合 Peter想用 Cantor's diagonal argument 来证明 X 是uncountable， 但其实 X 是countable (因为所有有理数的集合 Q 都是countable)， 我们找出这个case里哪里不适用这个方法 问题出在，Peter造出来的x其实不在X里，因此无法证得矛盾 要了解这个我们先知道有理数的一个性质: 任何有理数写成小数後，小数点後经过一些finite period後的数字 都会是repeating sequence。 譬如说: 1/2 = 0.5000000000... 重复0 1/3 = 0.33333333... 重复3 1/100 = 0.010000.... 重复0 比较有趣的例子是1/7 1/7 = 0.142857 142857 142857... 重复 142857 因此如果造出来的x是有理数，那麽 x在小数点後，经过一些finite period後，他也应该要是repeating sequence 可是根据Peter的造法，因为xi有无限多个(每个xi都对应到一个不同的自然数i，而自然数 有无限多个)， 所以x在小数点後会有无限多个digits要differ，我们无法造出一个在finite period後， 会是repeating sequence的x。 应该要的x: 0.<-> | <------------------------------------> finite repeating sequence (infinite) period 事实上得到的x: 0.<------------------------------------------> infinite period 所以造出来的x不会是有理数 因此x不会在X里，即使他跟每个xi都不同 以上分享给大家 如果有错误还请帮我指出来感恩~ XD ref: 上课讲义 https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument https://www.mathpages.com/home/kmath371/kmath371.htm --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.166.212.2 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1638271698.A.863.html