Chung qui chỉ tại Cantor (3)

NQH | 10/02/2005 |

Tôi thấy, nhưng tôi không tin.

[Trích một bức thư Cantor gửi Dedekind năm 1878]

Trở lại với hành trình lịch sử của ta: trong các thập niên cuối cùng cùng của thế kỷ 19, nhà toán học vĩ đại Georg Cantor (Georg Ferdinand Ludwig Philipp Cantor, 1845-1918) đề ra một trong những tư tưởng táo bạo nhất trong lịch sử toán học, khuấy đảo toàn bộ thế giới toán học lúc bấy giờ, làm cho các nhà toán học xuất sắc nhất thế giới thời kỳ đó như Henri Poincaré (1854-1912) và David Hilbert (1862-1943) phải nhảy vào “tham chiến”. Cá nhân tôi có cảm tình đặc biệt với Cantor, và cho rằng ông là nhà toán học có tư tưởng độc đáo nhất mọi thời đại. Chữ độc đáo không đủ để diễn tả điều tôi muốn nói về Cantor. Tiếng Anh họ dùng chữ original, mang nghĩa là nguyên gốc, độc đáo, đầu tiên, …

Lý thuyết tập hợp của Cantor không chỉ làm lung lay nền tảng toán học, đặt ra các vấn đề mấu chốt của triết học và logic, là tiền thân của lý thuyết tập hợp hiện đại, mà còn mang một trong những tư tưởng tiên phong của lý thuyết tính toán hiện đại. Sinh viên học máy tính nên biết và đọc về lý thuyết Cantor.

Lý thuyết tập hợp Cantor có hai đối tượng chính: các tập hợp, và lực lượng (cardinality) của các tập hợp. Tập {a,b,c} có lực lượng là 3. Ta dùng |S| để chỉ lực lượng của tập S. Có tất cả 2³=8 tập con của tập {a,b,c}. Nói chung, nếu S là tập hữu hạn thì có tất cả 2^|S| tập con của tập S. Ta dùng 2^S để chỉ tập tất cả các tập con của S. Nếu S hữu hạn, thì rõ ràng |2^S| = 2^|S| > |S|.

Dĩ nhiên những điều này người ta đã biết từ lâu. Cantor bắt đầu lý thuyết của ông bằng một câu hỏi cực kỳ khó chịu: thế nếu S là tập vô hạn thì thế nào? Quan hệ |S| < |2^S| có còn đúng nữa không? Thế nào là lực lượng của tập vô hạn?

Hai tập {a,b,c} và {x,y,z} có lực lượng bằng nhau. Điều này có thể hiểu theo hai cách: (1) đếm các phần tử trong từng tập, và cho kết quả là 3. Thế là chúng bằng nhau. Nhưng đối với Cantor, lý do chúng bằng nhau sâu sắc hơn nhiều. Chúng có lực lượng bằng nhau là vì ta có thể ghép cặp một-một giữa chúng: (a,y), (b,x), (c,z). Dĩ nhiên có nhiều song ánh (bijection – hoặc ánh xạ một-một) giữa hai tập này (3! = 6), nhưng miễn có một song ánh là chúng bằng nhau. Theo dòng lý luận này, nếu có một đơn ánh (injection) từ tập A vào tập B thì |A|≤|B|. Ví dụ: từ {a,b} vào {x,y,z} thì có đơn ánh {(a,z),(b,x)}, cho nên |{a,b|}≤|{x,y,z}|. Nếu có đơn ánh từ A vào B, nhưng không có song ánh từ A vào B, thì |A|< |B|.

Để làm ví dụ, ta thử xét các tập hợp sau: N là tập các số tự nhiên, E là tập các số tự nhiên chẵn, và R là tập các số thực. Dễ thấy |E|≤|N|≤|R|. Về mặt trực quan, ta có thể nghĩ rằng tập E bằng khoảng một nửa tập N, nhưng thực ra |N|=|E| vì ta có song ánh f: N –> E định nghĩa bởi f(x) = 2x. Ví dụ này minh họa sự tinh tế khi ta xét các tập vô hạn.

Với căn bản như trên, ta có thể chứng minh |S|< |2^S| bằng một lý luận đơn giản nhưng có uy lực cực kỳ gọi là lý luận đường chéo (diagonal argument). Lý luận này cũng là nền tảng của các kết quả nổi tiếng của Gödel và Turing mà ta sẽ đề cập sau. Đại khái, để chứng minh |S|< |2^S| (dù S là vô hạn) ta có thể làm như sau:

Dễ thấy |S|≤|2^S| (bạn nên tự tìm vài đơn ánh chứng minh điều này).
Giả sử |S|=|2^S|, nghĩa là có một song ánh f: S –> 2^S. Gọi T là tập tất cả các phần tử x thuộc S sao cho x không thuộc f(x). Gọi b là phần tử của S mà f(b) = T. Bây giờ ta thử hỏi: b có nằm trong T hay không? Nếu b thuộc T thì, theo định nghĩa của T, b không thuộc f(b=T), vô lý. Nếu b không thuộc T, thì cũng theo định nghĩa của T, b thuộc f(b)=T.
Tóm lại, |S|< |2^S|.

Nhà toán học nổi tiếng Paul Erdos thường ví von rằng một chứng minh tuyệt đẹp như vậy phải là một chứng minh trong quyển sách của thượng đế (xem “Proofs from the book”). Không biết các bạn thế nào chứ lần đầu tiên tôi thấy chứng minh này, tôi cảm thấy ná thở vì cái đẹp! Sau này tôi mới khám phá ra rằng lúc đó, dù hiểu về mặt kỹ thuật và cảm nhận được một ít cái đẹp của ý tưởng này, tôi thật sự chưa hiểu vấn đề!

Bài tập 1: chứng minh rằng |N|< |R|.

Ta sẽ còn gặp lại lý luận đường chéo vài lần trên hành trình xuôi dòng lịch sử này.

Chủ đề : Lý thuyết tính toán. Bookmark the permalink. Trackbacks are closed, but you can post a comment.

20 Comments

Anonymous

Posted 17/05/2005 at 7:16 am | Permalink

Ba`i viet ra^’t hay, to^i cu~ng co’ ta^m tra.ng tha?ng tho^’t khi ho.c chu+’ng minh na`y.
Co’ mo^.t lo^~i chi’nh ta? nho? : trong chu+’ng minh, xin chu+~a la.i tha`nh : “Gia? su+? $|S| = 2^|S|$”.

Chu’c vui

Reply
Anonymous

Posted 18/05/2005 at 4:30 pm | Permalink

Do.c chu*’ng minh |S|< |2^S|, to^i co' mo^.t tha('c ma('c nho?: La\m sao ba?o da?m to^\n ta.i pha^\n tu*? b tho?a:
“Gọi b là phần tử của S mà f(b) = T”? Ne^’u kho^ng to^\n ta.i b thi\ ly’ lua^.n co\n la.i co\n du’ng kho^ng?

Chu’c vui!

Reply
Anonymous

Posted 18/05/2005 at 10:33 pm | Permalink

Ta.i vi` khi gia? su+? S = 2^S thi` f la` a’nh xa. mo^.t mo^.t, ne^n mo^~i T dde^`u co’ b duy nha^’t thoa? ma~n f(b) = T.

Reply
donnghi

Posted 07/08/2009 at 9:14 am | Permalink

Giả sử |S|=|2^S|, nghĩa là có một song ánh f: S –> 2^S. Gọi T là tập tất cả các phần tử x thuộc S sao cho x không thuộc f(x).

Em thắc mắc là trong câu trên f(x) là một tập hợp hay một giá trị ? (nếu là giá trị thì dùng từ “thuộc” không chính xác lắm, nếu là tập hợp thì nó không đảm bảo đơn ánh).

Mong anh giải thích lại cho em câu trên ^^

Reply
Ngô Quang Hưng

Posted 08/08/2009 at 12:33 pm | Permalink

@Donnghi, 2^S là tâp các tập, vì thế f(x) là một tập hợp.

Reply
Nguyen Viet Dung

Posted 13/09/2010 at 6:20 am | Permalink

Em chứng minh thử bài tập này , mong mọi người nhận xét hộ , em rất cảm ơn :

Bài tập 1: chứng minh rằng |N|< |R|.

1, Chứng minh |N|<=|R|
Ta xét đơn ánh f (x ) = x ;

2, Giả sử |N|= |R|
Tồn tại song ánh f từ N vào R .
Như vậy mỗi phần tử của N tương ứng với 1 phần tử của R và ngược lại . Ta xây dựng được song ánh g từ f bằng cách cho tương ứng lại tất cả các phần tử của N và R sao cho :
g(x)=x1 ;
g(y)=y1 ;
Với x<y thì |x1| < |y1| . Tồn tại z thuộc R để |x1| < |z| < |y1| không có phần tử tương ứng t thuộc tập N để g(t)=z;
Như vậy giả sử sai .

Vậy : |N|< |R|

Reply
Ngô Quang Hưng

Posted 13/09/2010 at 7:27 am | Permalink

Chào Dũng,

Tôi không hiểu lắm chứng minh của Dũng. Làm sao để có x1 và y1? Có vẻ như bạn dùng tính đậm đặc của R.

Để biết CM đúng hay không, Dũng thử thay R bằng Q. CM của bạn có “làm việc” (nghĩa là có suy ra rằng |N| < |Q|) hay không? (Q là tập các số hữu tỉ.) Nếu dùng CM này mà suy ra |N| < |Q| thì CM sai, tại vì N và Q có lực lượng bằng nhau trong lý thuyết tập hợp Cantor.

Reply
Nguyen Viet Dung

Posted 13/09/2010 at 9:42 am | Permalink

Em chào thầy .

Em xin giải thích thêm về ý tưởng của mình :

Giả sử ta có song ánh f : N->R
Như vậy ta luôn xác định tương ứng được cặp (x;y) với x thuộc N và y thuộc R . ( Các cặp số khác nhau các thành phần “x” và “y” khác nhau vì f là song ánh ) .
Với f , ta có các cặp sau (x1;y1) ; ( x2;y2) ; (x3;y3) … Ta sắp xếp được các cặp này đã cho theo chiều tăng x ( số tự nhiên N ). Việc tiếp theo là “đổi chỗ ” các y sao cho nếu xi < xj thì yi < yj .
Chẳng hạn từ ( 1 ; 4 ) ; ( 2 ; 3 ) ; ( 3 ; 2 ) … ta đổi lại thành : ( 1 ; 2 ) ; ( 2 ; 3) ; ( 3 ; 4 ) …
Ta lại thấy 2 số tự nhiên bất kỳ tương ứng với 2 số thực , giữa 2 số tự nhiên chỉ có hữu hạn chữ số , vì vậy khoảng giữa 2 số tự nhiên này tương ứng với hữu hạn số thực , điều này là vô lý vì giữa 2 số thực có vô hạn số .

Theo như thầy nói ở trên thì cách chứng minh của em có sai xót ở đâu đó vì theo cách này |N| < |Q| .

Reply
- Ngô Quang Hưng
  
  Posted 13/09/2010 at 9:50 am | Permalink
  
  À, CM của bạn sai ở đoạn “đổi chỗ” đó, tại vì thuật toán đổi chỗ không bao giờ dừng lại để cho ta một ánh xạ g cụ thể. Hãy nhìn phần tử nhỏ nhất của N là 0. Giả sử f(0) là một số nào đó, bạn phải đổi chỗ vô hạn lần để đảm bảo là f(0) < f(n) với mọi n.
  
  Reply
Nguyen Viet Dung

Posted 13/09/2010 at 9:58 am | Permalink

Em cảm ơn thầy , khi nào có thời gian rỗi thầy có thể post CM lên cho em tham khảo ?

Reply
- Ngô Quang Hưng
  
  Posted 13/09/2010 at 10:45 am | Permalink
  
  OK.
  
  Reply
Lê Xuân Định

Posted 14/12/2010 at 12:49 pm | Permalink

Thấy Cantor là mình nhào vô, không ngờ tới bài thứ 3 (bài này) mới gặp mặt Cantor. Thì ra là Cantor ông tổ lý thuyết Tập hợp chứ không phải Cantor trong lý thuyết Hỗn loạn (Chaos).

Tôi cũng đã “gặp” Cantor từ bé, thuở còn học PT, nhưng không phải thông qua lý thuyết tập hợp mà thông qua “bụi Cantor” (Cantor dust) trong lý thuyết Fractal và Chaos. Sau này, khi phát triển lý thuyết Thông tin Thống nhất thì tôi cũng phải gặp lại Cantor trong rất nhiều “ý tưởng” vừa tự nhiên vừa táo bạo của ông.

- Fractal và bụi Cantor: Fractal là một hiện tượng thường gặp trong thế giới tự nhiên, còn bụi Cantor thì được thành lập dựa trên một quy luật tự nhiên của tư duy con người, đó là tư duy “và tương tự…” nói chung cũng như phép định nghĩa truy hồi trong toán học nói riêng. Nhưng bụi Cantor lại cho thấy một khoảng cách khổng lồ giữa những khái niệm đơn giản của con người (như tập hợp, chiều không gian, đếm, .v.v.) và thế giới hiện tượng mà nó mang đến: Bụi Cantor nếu trải lên một cây thước thì sẽ “lủng lổ trổ” đến độ nó có thứ nguyên tương đương với một điểm (= không), nhưng nó lại “mịn và nhiều” đến độ có cardinal tương đương với cả tập R (tương đương với đoạn thẳng vạch ra bởi cây thước đó).

- Ordinal – xây dựng cả thế giới từ tập hợp rỗng: Không biết Cantor có tự coi mình là theo “trường phái xây dựng” (constructivism) không, nhưng các luận điểm và phương pháp luận của ông đều rất mang tính xây dựng. Chỉ bằng 1 nguyên tố “tập hợp rỗng”, 1 phép toán “bao hàm”, 1 cách xây dựng rất tự nhiên của con người “và tương tự…”, Cantor đã dựng nên khuôn mẫu cho thế giới “tập hợp” một cách rõ ràng, có lớp có lang, và có cả thứ tự nữa, đó là số ordinal. Nó đơn giản, hiệu quả, mà vô cùng đột phá. Ngày trước, trong thế giới “lý thuyết tập hợp ngây thơ”, các khái niệm và quy luật của chúng chỉ được “phán” theo một cách rất cảm tính, không xây dựng, và sau này mới biết là chúng đưa đến những “nghịch lý” rõ ràng. Ordinal không những chỉ ra một hình dáng cụ thể rõ ràng cho thế giới tập hợp, mà nó còn cho thấy sức mạnh vô biên của sự đơn giản: Mọi thứ đều có thể trải ra thành một “đường thẳng”, và thậm chí “đường thẳng” đó còn “rời rạc” như tập số tự nhiên nhất mà chúng ta tập đếm từ thuở nhỏ “1, 2, 3, …” Các nhà toán học đương thời (và thậm chí sau này) không thể hình dung được làm sao chúng ta có thể “đếm số thực” được. Nhưng Cantor đã làm được điều đó với một lập luận cơ bản rằng “Tư duy đếm và quy nạp là tư duy tự nhiên của con người“.

Ngoài ra, lập luận đường chéo của Cantor cũng hết sức “xây dựng”!

Dù trong toán học hay tin học, khoa học máy tính hay lý thuyết thông tin, xây dựng hay không xây dựng, thì Cantor vẫn là một cây đại thụ với cái “gốc” ở một con người từ hơn trăm năm trước, nhưng cái tán nó lan rộng mãi cho đến mấy trăm năm sau nữa chắc vẫn còn che.

Cantor = Căn-to = Cội lớn = Cái gốc lớn… vậy!
(Chú thích: “Căn” tiếng Hán-Việt nghĩa là “gốc rễ”, như trong “căn bản”. Chính các nhà toán học cũng dịch chữ “root” bên Tây sang thành phép “lấy căn” đó thôi.)

Reply
Lê Xuân Định

Posted 14/12/2010 at 1:10 pm | Permalink

À, nhân tiện cũng muốn hỏi các anh chị một tí về các vấn đề kỹ thuật:

1) Chứng minh bài toán dừng bằng lập luận đường chéo, có cái nào là “chính thống” không? Tôi là một người theo trường phái xây dựng, nhưng từ khi tôi học “Khoa học máy tính” cho đến những lần tìm kiếm trên mạng, tôi đều không hài lòng với cái mác “lập luận đường chéo” che đậy cho cái ruột “phản chứng” bên trong. Thậm chí có thầy dạy môn “khoa học máy tính” còn nói với SV (bạn tôi) rằng “lập luận đường chéo chẳng qua cũng chỉ là phản chứng”. Có vẻ như những nhà khoa học máy tính không quan tâm đến tính xây dựng, một tính chất rất đặc trưng của tin học, khác hẳn toán học cổ điển, nên mới có những nhận xét như vậy. Tôi có nhận xét về vấn đề này ở blog của mình, không biết có anh chị nào quan tâm không?!

2) Không hiểu sao các bác nhà ta dịch “cardinality” thành “lực lượng”? Có vẻ đây là cách dịch thoáng nghĩa. Nếu vậy thì “cardinal” và “ordinal” thì dịch là cái gì?

Reply
- Ngô Quang Hưng
  
  Posted 26/02/2011 at 11:02 pm | Permalink
  
  Chào Định,
  
  Theo bạn hiểu, “phương pháp xây dựng” chứng minh sư không tồn tại của cái gì đó (ví dụ như không tồn tại số hữu tỉ với bình phương bằng 2) như thế nào?
  
  Reply
Lê Xuân Định

Posted 26/02/2011 at 9:09 pm | Permalink

À, nhân tiện đây, cho mình hỏi luôn về “bài toán dừng linh động”:
- Bài toán dừng cổ điển (cố định): “Tồn tại một máy Turing để kiểm tra xem một máy Turing bất kỳ có dừng hay không.” <– Đã được chứng minh là sai!
- Bài toán dừng linh động: "Với bất kỳ máy Turing X nào cũng tồn tại một máy Turing để kiểm tra xem máy X có dừng hay không.” –> Theo kinh nghiệm thì bài toán này có triển vọng (kết quả positive) hơn chứ không phải bị phủ định hoàn toàn như bài toán dừng cố định. Nhưng việc chứng minh nó thì có lẽ còn khó hơn bài toán dừng cổ điển nữa!

Vậy cho hỏi là trên thế giới đã có ai thảo luận về “bài toán dừng linh động” trên chưa?

Reply
- Ngô Quang Hưng
  
  Posted 26/02/2011 at 10:59 pm | Permalink
  Chào Định,
  
  1. Với một số máy Turing X nhất định thì dĩ nhiên là có tồn tại máy Turing để kiểm tra xem X có dừng hay không. Ví dụ, nếu X là máy không làm gì cả.
  
  2. Lưu ý rằng bài toán dừng nói rằng không tồn tại máy Turing — với input [M, x] — quyết định xem máy Turing M có dừng trên input x hay không. Chứ không phải thuần túy là máy M có dừng hay không. Do đó, câu hỏi của bạn là không đủ cụ thể.
  
  2a. Giả sử câu hỏi của bạn là, “Với một cặp [M,x] bất kỳ nào thì có luôn tồn tại một máy Turing (phụ thuộc vào [M,x]) quyết định xem M có dừng trên input x hay không?”.
  
  Thì câu trả lời là luôn luôn có. Xét 2 máy Turing YES và NO. Máy YES luôn trả lời là “có dừng”. Máy NO luôn trả lời là “không dừng”. Dĩ nhiên một trong hai máy phải trả lời đúng cho cặp [M,x]
  
  2b. Giả sử câu hỏi của bạn là, “Với một máy Turing M bất kỳ nào thì có luôn tồn tại một máy Turing D (phụ thuộc vào M) sao cho D(x) = YES/NO nếu và chỉ nếu M dừng/không dừng trên input x không?”.
  
  Thì câu trả lời là không luôn luôn tồn tại D như thế. Ví dụ, xét máy M như sau:
```
M(x):
    If (x([M]) == YES) then loop forever
    If(x([M]) == NO) then return
```
  Ở đây ta giả sử máy Turing M tự lấy được đoạn mã [M]của chính nó, điều rất dễ làm dùng phương pháp như trong bài chương trình tự tái sinh. (Hoặc áp dụng định lý recursion.)
  
  Đến đây sẽ thấy D([D]) sẽ cho câu trả lời sai vì ta đã thiết kế máy M trả lời ngược lại.
  Reply
Lê Xuân Định

Posted 28/05/2011 at 8:50 pm | Permalink

> 2. …— với input [M, x] —…
Hè, việc bắt M phải có input x chỉ là một “chiêu” để tránh dùng đến code của chính nó, tức [M] trong khi viết M thôi, anh Hưng à! Nếu dùng cái “chương trình tự tái sinh” của anh thì chẳng cần phải nhọc công dùng tới cái trick đó làm gì , ta có thể giải quyết (phản bác) bài toán dừng với M không input như sau: Để đơn giản, em không phân biệt chương trình M và code của nó [M], thay vào đó, em ký hiệu việc thực thi chương trình M(·,·,·) với input (x,y,z) bằng [M(x,y,z)].

$\exists D(\cdot) \{\;\; \forall M() \{\; D(M) = true \leftrightarrow \text{Halt}( [M()] ) \;\} \;\;\}$
$M() ::= \{\;\; \text{if }D(M)=true \text{ then loop; else return; } \;\;\}$
$D(M) = ?$

Bản thân em thích cách này hơn vì nó đơn giản dễ nhớ dễ hiểu mà vẫn thể hiện được đầy đủ ý tưởng “nói/làm điều phủ định ý nghĩa (meta giá trị) của phán quyết về chính mình”: M nói rằng nó phủ định phán quyết của D về tính dừng của chính M, hay đơn giản $M() : \neg D(M)$ . Đây là cách “gián tiếp phủ định chính mình“, một dạng tinh vi hơn của “nghịch lý Kẻ nói dối” $D ::= \text{``}D=false\text{''}$ . Kiểu tự phủ định gián tiếp này đã được sử dụng một cách tương tự trong bài toán tiểu học “Treo cổ – Chặt đầu“:

- Bài toán dừng rút gọn:
$\exists D(\cdot) \{\;\; \forall M() \{\; D(M) = \text{Halt}( [M()] ) \;\} \;\;\}$
$M() ::= \text{``Do against} D(M) \text{''} = \{\;\; \text{Halt}( [M()] ) = \neg D(M) \;\;\}$
$\Rightarrow D(M) = \text{Halt}( [M()] ) = \neg D(M)$

- Bài toán “Treo cổ – Chặt đầu”:
$\exists Ex(\cdot) \{\;\; \forall S\{\; Ex(S) = \text{Capital}( [S] ) ::= \{ \text{``behead''} if [S]=true; else \text{``hang''} \} \;\} \;\;\}$
$S ::= \text{``I'll be hung''} = \{\;\; \text{Capital}( [S] ) \neq Ex(S) \;\;\}$
$\Rightarrow Ex(S) = \text{Capital}( [S] ) \neq Ex(S)$

Tự phủ định chính mình như “kẻ nói dối” thì lố bịch quá; Trong bài toán dừng rút gọn bên trên, D phủ định chính nó một cách gián tiếp thông qua đối số M, nhưng M vẫn phải tự tham chiếu đến chính nó (sử dụng code [M]). Thế nên để “nói dối tinh vi” hơn, bài toán dừng chính thống đã giả lập việc tham chiếu bản thân bằng cách thêm một biến x nữa và dùng kỹ thuật nhân đôi code x –> (x,x):
$\exists D(\cdot,\cdot) \{\;\; \forall (M(\cdot),x) \{\; D(M,x) = true \leftrightarrow \text{Halt}( [M(x)] ) \;\} \;\;\}$
$M(x) ::= \{\;\; \text{if }D(x,x)=true \text{ then loop; else return; } \;\;\}$
$D(M,M) = ?$

Reply
- Lê Xuân Định
  
  Posted 28/05/2011 at 10:16 pm | Permalink
  
  À, cái chiêu gián tiếp tham chiếu và phủ định bản thân của bài toán dừng chính thống còn được áp dụng trong nghịch lý Thợ cạo (Barber paradox):
  
  $\exists Shave(\cdot,\cdot) \{\;\; \forall (B(\cdot),m) \{\; Shave(B,m) = true \leftrightarrow \text{DoShave}( [B(m)] ) \;\} \;\;\}$
  $B(m) ::= \{\;\; \text{if }Shave(m,m)=true \text{ then return; else shave; } \;\;\}$
  $Shave(B,B) = ?$
  
  Reply
- Lê Xuân Định
  
  Posted 29/05/2011 at 11:14 am | Permalink
  
  À, nói đến sự lắt léo trong việc phủ định bản thân thì có lẽ “kẻ nói dối tinh vi nhất” chính là nghịch lý Berry:
  
  $\exists N(\cdot) \{\;\; \forall S \{\; N(S) = \text{NumDefBy}( [S] ) \;\} \;\;\}$
  $S ::= \text{``} min( \{ n = \text{NumDefBy}([s]) \,:\, \text{Under1000Chars}(s) \} ) - 1 \text{''}$
  $UKCN ::= \{ n = \text{NumDefBy}([s]) \,:\, \text{Under1000Chars}(s) \}$
  $\Rightarrow \text{Under1000Chars}(S) \wedge (\, N(S) = \text{NumDefBy}([S]) = min(UKCN) - 1 \,)$
  $\Rightarrow (\, N(S) = \text{NumDefBy}([S]) \in UKCN \,) \wedge (\, \forall n \in UKCN \{ N(S) < n \} \,)$
  $\Rightarrow (\, N(S) \in UKCN \,) \wedge (\, N(S) \not\in UKCN \,)$
  
  Reply
- Lê Xuân Định
  
  Posted 29/05/2011 at 1:11 pm | Permalink
  
  Nhưng “lắt léo xảo quyệt” quá không hẳn đã là tốt. Tuy ít lắt léo hơn, nhưng kỹ thuật “nhân đôi code” lại có khả năng ứng dụng cao hơn, cụ thể là trong lập luận đường chéo của Cantor về tương quan lực lượng giữa tập hợp $S$ và tập luỹ thừa của nó $2^S = \{ Y: Y \subset S \}$ :
  
  $\exists (f: S \rightarrow 2^S) \{\;\; \forall (Y \in 2^S) \{\; \exists x \in S \{ Y = f(x) \} \;\} \;\;\}$
  $Y_0 ::= \{\; x \in S : x \not\in f(x) \;\}$
  $I(x) ::= in(x,f(x)) = \text{``} x \in f(x) \text{''}$
  $Set(P(\cdot)) ::= \{\; x \in S : P(x) \;\}$
  $\Rightarrow Y_0 = Set( \neg I(\cdot) )$
  $x_0 :: Y_0 = f(x_0)$
  $\Rightarrow I(x_0) = in(x_0, f(x_0)) = in(x_0, Y_0) = in(x_0, Set(\neg I(\cdot)) ) = \neg I(x_0)$
  
  Reply