Cầu nối bất ngờ kết nối toán học kỳ lạ về cái vô hạn với khoa học máy tính

Khởi đầu của một sự giao thoa kỳ lạ

Trong thế giới toán học, lý thuyết tập hợp được coi là nền móng vững chãi nhất, nơi các nhà nghiên cứu tìm cách tổ chức những bộ sưu tập trừu tượng của các đối tượng. Tuy nhiên, đối với hầu hết các nhà toán học thông thường, họ hiếm khi phải bận tâm đến những chi tiết tỉ mỉ của nền móng này khi giải quyết các bài toán của mình. Họ mặc định rằng các tập hợp sẽ hoạt động theo đúng kỳ vọng và tiếp tục công việc chuyên môn. Nhưng có một cộng đồng nhỏ những nhà nghiên cứu, được gọi là các nhà lý thuyết tập hợp mô tả (descriptive set theorists), thì lại khác. Họ dành cả đời để nghiên cứu bản chất cơ bản của các tập hợp — đặc biệt là những tập hợp vô hạn kỳ quái mà đa số mọi người thường phớt lờ.

Giờ đây, lĩnh vực vốn dĩ xa xôi và cô độc này bỗng chốc trở nên sôi động hơn bao giờ hết. Vào năm 2025, nhà toán học Anton Bernshteyn đã công bố một mối liên hệ sâu sắc và đầy bất ngờ giữa biên giới xa xăm của lý thuyết tập hợp mô tả và khoa học máy tính hiện đại. Ông đã chứng minh rằng mọi bài toán về một số loại tập hợp vô hạn nhất định đều có thể được viết lại dưới dạng các bài toán về cách các mạng lưới máy tính giao tiếp với nhau. Cây cầu này đã khiến giới nghiên cứu ở cả hai phía ngạc nhiên tột độ: một bên dùng ngôn ngữ của logic và cái vô hạn, bên kia dùng ngôn ngữ của thuật toán và cái hữu hạn. Không có lý do hiển nhiên nào cho thấy chúng lại tương đương với nhau, nhưng thực tế đã chứng minh điều ngược lại.

Sự phân cấp của những tập hợp vô hạn

Lý thuyết tập hợp mô tả bắt nguồn từ Georg Cantor, người đã chứng minh vào năm 1874 rằng vô hạn có nhiều kích cỡ khác nhau. Chẳng hạn, tập hợp các số nguyên ($0, 1, 2, 3, \dots$) có cùng kích thước với tập hợp các phân số, nhưng lại nhỏ hơn tập hợp các số thực. Vào thời điểm đó, giới toán học cảm thấy không thoải mái với sự tồn tại của nhiều loại vô hạn khác nhau này. Để giải quyết sự khó chịu đó, họ đã phát triển một khái niệm khác về kích thước — gọi là “độ đo” (measure), thay vì chỉ dựa vào số lượng phần tử (lực lượng – cardinality).

Hãy tưởng tượng bạn đang so sánh độ dài. Tập hợp các số thực nằm giữa $0$ và $1$ và tập hợp giữa $0$ và $10$ đều vô hạn và có cùng lực lượng, nhưng tập hợp đầu tiên có độ đo Lebesgue là $1$ và tập hợp thứ hai là $10$. Các nhà lý thuyết tập hợp mô tả đóng vai trò như những người quản thủ thư viện, sắp xếp các tập hợp vào một hệ thống phân cấp. Ở trên cùng là những tập hợp “ngoan ngoãn”, dễ đo lường và nghiên cứu. Ở dưới cùng là những tập hợp “không thể đo lường” (unmeasurable), hay còn gọi là các tập hợp “bệnh lý” (pathological) — chúng quá phức tạp và cư xử kỳ quặc đến mức không một công cụ đo lường nào có thể xác định được kích thước của chúng.

Bài toán tô màu đồ thị vô hạn

Bernshteyn nghiên cứu các bài toán về đồ thị vô hạn — những mạng lưới gồm các nút (node) được kết nối bởi các cạnh (edge). Hãy xem xét một ví dụ điển hình: bắt đầu với một vòng tròn có vô số điểm. Chọn một điểm làm nút đầu tiên, sau đó di chuyển một khoảng cách cố định dọc theo chu vi để chọn nút thứ hai. Nếu khoảng cách đó là một số vô tỉ (không thể viết dưới dạng phân số), quá trình này sẽ kéo dài mãi mãi mà không bao giờ quay lại điểm xuất phát, tạo ra một chuỗi vô hạn các nút được kết nối.

Điều thú vị là chuỗi này chỉ là một phần nhỏ của đồ thị. Để hoàn thiện, bạn phải lặp lại quá trình này cho mọi điểm khởi đầu có thể trên vòng tròn. Kết quả là một đồ thị khổng lồ gồm vô số mảnh tách biệt, mỗi mảnh lại chứa vô số nút. Câu hỏi đặt ra là: Liệu ta có thể tô màu các nút này bằng chỉ hai màu sao cho không có hai nút nào được nối với nhau có cùng màu không?

Tiên đề chọn và cái giá của sự tùy tiện

Để giải bài toán tô màu trên bằng $2$ màu, cách tiếp cận thông thường là chọn một nút trong mỗi mảnh, tô màu xanh, rồi tô các nút tiếp theo theo kiểu xen kẽ: vàng, xanh, vàng, xanh. Tuy nhiên, cách làm này dựa trên một khái niệm gây tranh cãi gọi là “Tiên đề chọn” (Axiom of Choice). Tiên đề này cho phép bạn chọn một phần tử từ vô số các tập hợp để tạo ra một tập hợp mới.

Vấn đề là khi sử dụng Tiên đề chọn, tập hợp các nút màu xanh bạn tạo ra sẽ trở nên “không thể đo lường”. Bạn đã tô màu từng nút một cách riêng lẻ mà không quan tâm đến mối liên hệ giữa chúng trên vòng tròn. Đối với một nhà lý thuyết tập hợp mô tả, đây là một lời giải không thỏa đáng. Họ muốn tìm một cách tô màu “liên tục” hơn, không cần dùng đến Tiên đề chọn và tạo ra các tập hợp có thể đo lường được độ dài.

Nếu chúng ta cố gắng tô màu theo các cung tròn — tức là tô màu cho cả một đoạn thay vì từng điểm rời rạc — chúng ta sẽ gặp rắc rối khi quay lại điểm gần xuất phát. Sẽ luôn có một đoạn nhỏ còn sót lại không thể tô bằng $2$ màu mà không vi phạm quy tắc. Để giải quyết, bạn buộc phải dùng đến màu thứ ba. Do đó, bài toán tô màu bằng $2$ màu nằm ở kệ thấp nhất (không thể đo lường), trong khi bài toán $3$ màu nằm ở kệ cao hơn nhiều vì nó có lời giải đo lường được.

Khi Wi-Fi gặp gỡ cái vô hạn

Bước ngoặt xảy ra khi Bernshteyn tham dự một bài giảng về khoa học máy tính vào năm 2019, thảo luận về “thuật toán phân tán” (distributed algorithms). Hãy tưởng tượng một tòa nhà với hàng loạt bộ phát Wi-Fi. Các bộ phát gần nhau sẽ bị nhiễu nếu dùng chung kênh tần số. Mỗi bộ phát cần chọn một kênh khác với hàng xóm của nó mà không có một máy chủ trung tâm nào điều phối.

Các nhà khoa học máy tính mô hình hóa điều này thành một bài toán tô màu đồ thị hữu hạn. Mỗi nút (bộ phát) chạy một thuật toán cục bộ: nó kiểm tra màu của những nút lân cận trong một phạm vi nhất định, sau đó quyết định màu của chính mình. Họ nhận thấy rằng việc tô màu bằng $2$ màu cực kỳ kém hiệu quả, nhưng nếu được dùng $3$ màu, họ có thể tìm ra một thuật toán chạy rất nhanh. Bernshteyn nhận ra rằng các ngưỡng hiệu suất trong khoa học máy tính nghe rất giống với các ngưỡng về độ đo trong lý thuyết tập hợp.

Xây dựng cây cầu của Bernshteyn

Bernshteyn đã chứng minh một điều kinh ngạc: Mọi thuật toán cục bộ hiệu quả trong mạng lưới hữu hạn đều có thể được chuyển đổi thành một cách tô màu có độ đo Lebesgue cho một đồ thị vô hạn. Khó khăn lớn nhất là trong mạng lưới hữu hạn, ta có thể đánh số thứ tự cho các nút, nhưng trong đồ thị vô hạn “không đếm được”, việc đánh số là bất khả thi.

Bernshteyn đã tìm ra một cách thông minh để gắn nhãn (label) cho các đồ thị vô hạn sao cho các nút lân cận luôn có nhãn khác nhau, cho phép áp dụng các thuật toán từ thế giới hữu hạn vào thế giới vô hạn. Ông chứng minh rằng luôn có cách để mở rộng thuật toán từ khoa học máy tính sang lý thuyết tập hợp mà không gặp xung đột. “Bất kỳ thuật toán nào trong thiết lập của chúng tôi cũng tương ứng với một cách tô màu đo lường được trong thiết lập lý thuyết tập hợp mô tả,” nhà khoa học máy tính Václav Rozhoň nhận xét.

Tầm nhìn mới về toán học

Khám phá này không chỉ là một công cụ mới để giải các bài toán riêng lẻ. Nó cho phép các nhà lý thuyết tập hợp nhìn nhận lĩnh vực của họ một cách rõ ràng hơn. Nhiều bài toán trước đây không biết phân loại vào đâu nay đã tìm thấy vị trí của mình trên những chiếc kệ ngăn nắp của khoa học máy tính. Ngược lại, các nhà khoa học máy tính cũng bắt đầu sử dụng những hiểu biết từ lý thuyết tập hợp để chứng minh các ước lượng mới về độ khó của thuật toán.

Bernshteyn hy vọng rằng sự giao thoa này sẽ thay đổi cái nhìn của mọi người về lý thuyết tập hợp — từ một lĩnh vực trừu tượng, xa vời trở thành một phần không thể thiếu của thế giới toán học thực dụng. Cái vô hạn, thông qua ngôn ngữ của thuật toán, giờ đây không còn là một khái niệm đáng sợ mà trở thành một công cụ mạnh mẽ để thấu hiểu cấu trúc của thực tại.