Một cây cầu mới nối toán học kỳ lạ của vô hạn với khoa học máy tính

• Lý thuyết tập hợp mô tả, lĩnh vực kỹ thuật nghiên cứu cấu trúc của các tập vô hạn, đã được phát hiện là có thể diễn giải lại bằng ngôn ngữ thuật toán
• Nhà toán học Anton Bernshteyn đã chứng minh rằng các bài toán về đồ thị vô hạn có thể được viết lại thành các bài toán truyền thông trong mạng máy tính
• Mối liên kết này cho thấy sự tương ứng giữa tính đo được (measurability) và hiệu quả của thuật toán phân tán
• Các nhà nghiên cứu đang dùng cây cầu này để chuyển đổi qua lại các định lý và bài toán giữa hai lĩnh vực, từ đó rút ra những kết quả mới
• Đây là một phát hiện định nghĩa lại ranh giới giữa vô hạn và tính toán, đồng thời mở rộng khả năng hợp tác giữa toán học và khoa học máy tính

---

Giới thiệu: Lý thuyết tập hợp và thế giới của vô hạn

• Nền tảng của toán học hiện đại dựa trên lý thuyết tập hợp, và đa số nhà toán học đều tiếp cận bài toán trên giả định đó
• Tuy nhiên, các nhà lý thuyết tập hợp mô tả (descriptive set theorists) là một nhóm nghiên cứu nhỏ vẫn tiếp tục khám phá bản chất của các tập vô hạn
• Năm 2023, Anton Bernshteyn đã phát hiện ra một mối liên hệ sâu sắc giữa lý thuyết tập hợp mô tả và khoa học máy tính
  • Ông cho thấy có thể chuyển các bài toán về một số tập vô hạn nhất định thành các bài toán truyền thông trong mạng máy tính
• Kết quả này được xem như một cây cầu nối giữa những ngôn ngữ tưởng như đối lập: logic và thuật toán, vô hạn và hữu hạn

Bối cảnh của lý thuyết tập hợp mô tả

• Nguồn gốc của lý thuyết tập hợp bắt đầu từ công trình của Georg Cantor, người đã chứng minh sự tồn tại của các kích thước vô hạn khác nhau
• Các khái niệm biểu thị độ lớn của một tập bao gồm lực lượng (cardinality) và độ đo (measure)
  • Ví dụ: tập số thực trên đoạn 0~1 và tập số thực trên đoạn 0~10 có cùng lực lượng, nhưng độ đo lần lượt là 1 và 10
• Lý thuyết tập hợp mô tả phân biệt giữa tập đo được và tập không đo được, rồi phân loại chúng theo hệ phân cấp độ phức tạp (hierarchy)
• Hệ phân cấp này trở thành tiêu chí lựa chọn công cụ phù hợp trong các lĩnh vực toán học khác như xác suất, hệ động lực và lý thuyết nhóm

Đồ thị vô hạn và bài toán tô màu

• Bernshteyn nghiên cứu đồ thị vô hạn, mô hình hóa các nút và cạnh của mỗi đồ thị như một cấu trúc liên kết vô hạn
• Ví dụ: nếu nối các điểm trên một đường tròn theo những khoảng cách cố định, thì với khoảng cách hữu tỉ sẽ tạo thành các vòng kín, còn với khoảng cách vô tỉ sẽ hình thành cấu trúc liên kết vô hạn
• Khi tô các nút của đồ thị bằng hai màu, điều đó có thể làm được nếu dùng tiên đề chọn (axiom of choice), nhưng sẽ tạo ra tập không đo được
• Ngược lại, nếu dùng cách tô màu liên tục, cần ba màu nhưng sẽ thu được tập đo được
• Sự khác biệt này đóng vai trò là yếu tố cốt lõi quyết định vị trí trong hệ phân cấp độ phức tạp của lý thuyết tập hợp

Cuộc gặp gỡ với thuật toán phân tán

• Năm 2019, Bernshteyn nghe một bài giảng khoa học máy tính về thuật toán phân tán (distributed algorithms) và nhận ra sự tương đồng
  • Ví dụ: bài toán để các bộ định tuyến Wi-Fi chọn tần số (màu sắc) khác nhau nhằm tránh gây nhiễu lẫn nhau
• Mỗi nút chỉ giao tiếp với các nút lân cận và dùng thuật toán cục bộ (local algorithm) để quyết định màu
• Với hai màu thì không hiệu quả, nhưng nếu cho phép ba màu thì có thể giải quyết hiệu quả
• Bernshteyn nhận ra rằng ngưỡng (threshold) về số lượng màu này trùng khớp với ngưỡng của bài toán tô màu đo được trong lý thuyết tập hợp mô tả

Chứng minh tính tương đương giữa hai thế giới

• Bernshteyn đã chứng minh về mặt toán học tính tương đương giữa thuật toán cục bộ hiệu quả ↔ cách tô màu đo được
• Trong đồ thị hữu hạn, có thể gán số hiệu riêng cho từng nút, nhưng điều đó không thể thực hiện với đồ thị vô hạn không đếm được
• Ông đã nghĩ ra một phương pháp gán nhãn không trùng lặp giữa các nút kề nhau, nhờ đó có thể mở rộng thuật toán sang cả đồ thị vô hạn
• Kết quả là đã chứng minh được rằng “mọi thuật toán cục bộ đều tương ứng với một cách tô màu đo được trong lý thuyết tập hợp mô tả”
• Điều này cho thấy mối liên hệ toán học sâu sắc giữa khả năng tính toán và tính xác định được (definability)

Mở rộng nghiên cứu và ứng dụng

• Václav Rozhoň cùng các cộng sự đã dùng mối liên kết này để giải bài toán tô màu đồ thị cây (tree), đồng thời rút ra các công cụ nghiên cứu hệ động lực
• Theo chiều ngược lại, cũng có các nghiên cứu dùng phương pháp của lý thuyết tập hợp để cải thiện ước lượng độ khó của bài toán
• Cây cầu này không chỉ là công cụ giải quyết bài toán đơn thuần, mà còn góp phần tái thiết hệ thống phân loại của lý thuyết tập hợp
• Các nhà lý thuyết tập hợp mô tả giờ đây có thể tham khảo phương pháp phân loại có hệ thống của khoa học máy tính để sắp xếp các bài toán chưa được phân loại
• Bernshteyn kỳ vọng nghiên cứu này sẽ trở thành một bước ngoặt giúp khái niệm vô hạn được nhìn nhận như một phần thực chất của toán học

[GN⁺]

Ý kiến Hacker News

• Tôi tự hỏi liệu kết quả kiểu này có thể được ứng dụng vào các lĩnh vực thực tế như điện toán phân tán hay không. Hay nó chỉ tồn tại như một điều thú vị thuần túy về mặt toán học

  • Đây hoàn toàn không phải là một câu hỏi ngớ ngẩn. Insight kỹ thuật có thể dẫn tới các định lý bất khả mới trong thuật toán phân tán hoặc lý thuyết độ phức tạp tính toán. Những ứng dụng như mesh networking cũng rất đáng quan tâm

• Câu “mọi toán học hiện đại đều được xây trên lý thuyết tập hợp” là quá tuyệt đối. Các công cụ toán học hiện đại như Lean hay Rocq đang phát triển dựa trên toán học được hình thức hóa (formalized mathematics), và thứ đó được xây trên lý thuyết kiểu (type theory)

  • Tôi không phải nhà toán học, nhưng tôi nghĩ ZFC vẫn là một hệ nền tảng hợp lệ. Kiểu phụ thuộc (dependent types) hữu ích cho việc quản lý chứng minh định lý, nhưng không giúp bạn chứng minh được nhiều định lý hơn. Isabelle/HOL của Lawrence Paulson không dựa trên kiểu nhưng vẫn có thể chứng minh phần lớn toán học
  • Nhưng các nhà toán học thực tế hầu như không dùng toán học hình thức hóa. Dù có biết, họ cũng không dùng nó như ngôn ngữ nền tảng vì bất tiện
  • Không nên nhầm lẫn giữa ngôn ngữ của toán học và ngôn ngữ hình thức dùng để chứng minh về ngôn ngữ đó. Cái trước gần như hoàn toàn dùng tập hợp, còn cái sau tất yếu dùng kiểu
  • Nói chính xác hơn thì cuộc khủng hoảng nền tảng của toán học được xem là đã tạm khép lại bằng sự hình thức hóa của lý thuyết tập hợp

• Cụm đùa “cons’es all the way down” là cách châm biếm cấu trúc đệ quy

• Tôi xúc động trước câu “cuối cùng chúng ta cũng có thể tính được vô hạn”

  • Tháng sau ở Bay Area sẽ có tour Calculating Infinity của The Dillinger Escape Plan. Link sự kiện. Tôi chia sẻ vì thấy cộng đồng toán, hacking và mathcore có vẻ sẽ giao nhau
  • Đùa nối theo câu “tính được vô hạn” bằng câu “và cả xa hơn nữa!”
  • Trong Haskell, người ta nói có thể biểu diễn vô hạn đếm được (countable infinity) chỉ bằng một dòng let x = x in x
  • Thêm chút hài hước bằng meme “Chuck Norris đã đếm từ 1 đến vô hạn hai lần”
  • Và thêm câu mỉa mai “Cái này thật sự mất quá lâu /s”

• Tôi không đồng ý với nhận định “khoa học máy tính chỉ xử lý những thứ hữu hạn”. Thực tế khoa học máy tính gắn sâu với vô hạn

  • Quanta hay xử lý theo kiểu này. Họ có xu hướng tập trung vào câu chuyện xoay quanh con người theo lối khoa học đại chúng, và lược bỏ chi tiết
  • Tuy vậy, khoa học máy tính ít quan tâm tới vô hạn không đếm được (uncountable infinity) hơn. Lý thuyết độ đo (measure theory) chủ yếu xử lý mảng đó
  • Ban đầu tôi cũng nghĩ “CS xấp xỉ vô hạn”, nhưng thật ra từ khóa là xấp xỉ (approximation). Chúng ta luôn chỉ làm việc trong ranh giới hữu hạn. Dù vũ trụ là vô hạn, phạm vi ta có thể quan sát vẫn bị giới hạn bởi tốc độ ánh sáng
  • Những câu kiểu “khoa học máy tính không dùng logic” là cách nói quá cẩu thả. Logic Boolean là bằng chứng rõ ràng nhất

• Tôi đã học toán trong thời gian dài, và rồi tin rằng vô hạn (infinity) không tồn tại. Tôi nghĩ toán học có thể còn tốt hơn nếu không có vô hạn

  • Tôi cũng chỉ học toán ở mức kỹ sư, nhưng tôi nghĩ vô hạn không phải là một con số mà là một quá trình (process). Dấu “...” trong {1, 2, 3, ...} biểu thị một quá trình mở rộng không có điểm kết thúc. Không có cái gọi là số nguyên tố thứ vô hạn, chỉ có quy tắc sinh rằng luôn tồn tại số nguyên tố lớn hơn
  • Nhưng nếu loại bỏ vô hạn thì toán học sẽ trở nên kinh khủng phức tạp. Nếu không cho phép mở rộng số tự nhiên vô tận thì việc tính toán sẽ rất bất tiện
  • Toán học quan tâm tới tính hữu ích về mặt khái niệm hơn là chuyện nó có tồn tại hay không. Đường tròn cũng không tồn tại trong thực tại nhưng vẫn hữu ích. Nếu không có vô hạn thì cuối cùng ta cũng sẽ phải phát minh lại nó dưới dạng kiểu như “giới hạn khi x tiến tới một số rất rất lớn”
  • Một câu đùa kiểu “cứ dừng ở 8 là được” để châm biếm sự không cần thiết của vô hạn
  • Vô hạn chỉ là cái tên để chỉ một quá trình không bao giờ kết thúc. Có những quá trình tăng nhanh hơn nên tồn tại những vô hạn lớn hơn. Cá nhân tôi thích khái niệm vô hạn trong mô hình cầu Riemann

• Câu đùa rằng “node_modules” đã nối toán học của vô hạn vào hệ thống tệp của tôi, nhằm châm biếm sự bùng nổ phụ thuộc

• Phản bác câu “mọi toán học hiện đại đều được xây trên lý thuyết tập hợp”, và chỉ ra rằng còn có lý thuyết kiểu (Type Theory)

  • Type Theory là một hệ tiên đề mạnh hơn ZFC. Xem thêm giải thích trong câu trả lời trên MathOverflow
  • Nhưng vẫn chưa có một tập tiên đề của lý thuyết kiểu nào có tầm ảnh hưởng như ZF hay ZFC
  • Về mặt kỹ thuật, lý thuyết tập hợp mô tả (descriptive set theory) là một thứ tách biệt với lý thuyết tập hợp nền tảng. Nó có thể được tái cấu trúc dễ dàng bằng các khái niệm về kiểu và không gian, và cách đó thường có lợi hơn. Việc diễn giải lại vô hạn toán học từ góc nhìn tính toán không phải là một nỗ lực mới
  • Mô tả kiểu “ngành học tổ chức các tập hợp của các đối tượng trừu tượng” là cách giải thích quá đơn giản về lý thuyết tập hợp. Dù vậy, đúng là phần lớn toán học vẫn được định nghĩa từ các tiên đề tập hợp