2019 Tháng Tư 01
Xem tất cả bài viết
Đây là bản sao của bài đăng tại https://medium.com/@VitalikButerin/cantor-was-sai-debunking-the-infinite-set-hierarchy-e9ba5015102.
Bởi Vitalik Buterin, Tiến sĩ tại Đại học Basel
Một chuỗi toán học phổ biến lập luận rằng, thay vì là một loại vô hạn duy nhất, thực sự có một hệ thống phân cấp vô hạn gồm các cấp độ vô hạn khác nhau. Trong khi kích thước của tập hợp các số nguyên đơn giản là vô hạn và tập hợp các số hữu tỷ cũng lớn như các số nguyên (vì bạn có thể ánh xạ mọi số hữu tỷ thành một số nguyên bằng cách xen kẽ các chữ số của tử số và mẫu số của nó, ví dụ: \(0.456456456…. = \frac{456}{999} = \frac{152}{333} \rightarrow 135323\)), kích thước của tập hợp có thật những con số là một loại vô cực thậm chí còn lớn hơn, bởi vì ở đó không có cách nào để tạo một ánh xạ tương tự từ số thực sang số nguyên.
Trước hết, tôi nên lưu ý rằng tương đối dễ dàng để thấy rằng tuyên bố rằng không có ánh xạ là sai. Đây là một ánh xạ đơn giản. Đối với một số thực nhất định, hãy cung cấp cho tôi một chương trình python (xác định) sẽ in ra các chữ số của nó (ví dụ: đối với π, đó có thể là một chương trình tính toán các xấp xỉ tốt hơn và tốt hơn bằng cách sử dụng chuỗi vô hạn \(\pi = 4 – \frac{4}{3} + \frac{4}{5} – \frac{4}{7} + …\)). Tôi có thể chuyển đổi chương trình thành một số (sử dụng n = int.from_bytes(open('program.py').read(), 'big')) và sau đó xuất số. Xong. Có ánh xạ từ số thực sang số nguyên.
Bây giờ chúng ta hãy xem lập luận phổ biến nhất được sử dụng để khẳng định rằng không thể tồn tại ánh xạ như vậy, đó là lập luận đường chéo của Cantor. Đây là một cuộc triển lãm từ UC Denver; nó ngắn nên tôi sẽ chỉ chụp màn hình toàn bộ:
Bây giờ, đây là lỗ hổng cơ bản trong lập luận này: khai triển thập phân của số thực không phải là duy nhất. Để cung cấp một phản ví dụ ở định dạng chính xác mà “bằng chứng” yêu cầu, hãy xem xét tập hợp (các số được viết ở dạng nhị phân), với các chữ số chéo được in đậm:
-
x[1] = 0.000000…
-
x[2] = 0,011111…
-
x[3] = 0,001111…
-
x[4] = 0,000111…
-
…..
Đường chéo cho ta: 01111….. Lật từng chữ số ta được số: \(y =\) 0,10000……
Và đây là vấn đề: giống như trong số thập phân, 0,9999…. bằng 1, trong hệ nhị phân 0,01111….. bằng 0,10000….. Và do đó, mặc dù mới mở rộng thập phân không có trong danh sách ban đầu, số \(y\) hoàn toàn giống với số \(x[2]\).
Lưu ý rằng điều này ngụ ý trực tiếp rằng vấn đề tạm dừng trên thực tế có thể giải quyết được. Để hiểu tại sao, hãy tưởng tượng một chương trình máy tính mà ai đó tuyên bố sẽ không dừng lại. Hãy để c[1] là trạng thái của chương trình sau một bước, c[2] sau hai bước, v.v. Cho x[1]x[2]x[3]…. là một liệt kê đầy đủ của tất cả các số thực (tồn tại, như chúng tôi đã chứng minh ở trên), được biểu thị bằng cơ số \(2^D\) ở đâu \(D\) là kích thước của bộ nhớ chương trình, vì vậy trạng thái chương trình luôn có thể được biểu diễn dưới dạng một “chữ số” duy nhất. Cho y = 0.c[1]c[2]c[3]…….. Số này là một phần giả định của danh sách, vì vậy nó là một trong số x[i] giá trị, và do đó nó có thể được tính toán trong một khoảng thời gian hữu hạn. Điều này có ý nghĩa trong một số ngành, đặc biệt là trong việc chứng minh rằng các chuỗi khối “Turing-complete” trên thực tế là an toàn.
Bằng sáng chế về nghiên cứu này đang chờ xử lý.
