Các nhà lý thuyết tập hợp mô tả là một ngoại lệ. Cộng đồng nhỏ các nhà toán học này chưa bao giờ ngừng nghiên cứu bản chất cơ bản của các tập hợp—đặc biệt là các tập hợp vô hạn kỳ lạ mà các nhà toán học khác bỏ qua.

Lĩnh vực nghiên cứu của họ giờ đây đã bớt cô đơn hơn rất nhiều. Năm 2023, một nhà toán học tên là Anton Bernshteyn đã công bố một mối liên hệ sâu sắc và đáng ngạc nhiên giữa lĩnh vực toán học xa xôi 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 tất cả các vấn đề về một số loại tập hợp vô hạn nhất định có thể được viết lại thành các vấn đề về cách thức mạng lưới máy tính giao tiếp. Cầu nối giữa hai lĩnh vực này đã làm các nhà nghiên cứu ở cả hai phía ngạc nhiên. Các nhà lý thuyết tập hợp sử dụng ngôn ngữ logic, các nhà khoa học máy tính sử dụng ngôn ngữ thuật toán. Lý thuyết tập hợp nghiên cứu về vô hạn, khoa học máy tính nghiên cứu về hữu hạn. Không có lý do gì để các vấn đề của họ phải liên quan đến nhau, chứ đừng nói đến việc tương đương nhau.

“Đây là một điều thực sự kỳ lạ,” Václav Rozhoň , một nhà khoa học máy tính tại Đại học Charles ở Prague, nói. “Kiểu như, lẽ ra bạn không nên có thứ này.”

Kể từ kết quả của Bernshteyn, các đồng nghiệp của ông đã tìm tòi cách di chuyển qua lại giữa hai phía của cây cầu để chứng minh các định lý mới ở cả hai bên, và cách mở rộng cây cầu đó sang các lớp vấn đề mới. Một số nhà lý thuyết tập hợp mô tả thậm chí còn bắt đầu áp dụng những hiểu biết từ lĩnh vực khoa học máy tính để tổ chức lại toàn bộ lĩnh vực của họ, và để suy nghĩ lại cách họ hiểu về vô cực.

Anton Bernshteyn đã và đang khám phá những mối liên hệ quan trọng giữa lý thuyết tập hợp và các lĩnh vực ứng dụng hơn, chẳng hạn như khoa học máy tính và hệ thống động lực học.

“Suốt thời gian qua, chúng ta đã nghiên cứu những vấn đề rất giống nhau mà không trực tiếp trao đổi với nhau,” Clinton Conley , một nhà lý thuyết tập hợp mô tả tại Đại học Carnegie Mellon, cho biết. “Điều này mở ra cánh cửa cho tất cả những sự hợp tác mới.”

Bộ bị hỏng

Bernshteyn còn là sinh viên đại học khi lần đầu tiên nghe nói về lý thuyết tập hợp mô tả — như một ví dụ về một lĩnh vực từng rất quan trọng, rồi sau đó suy tàn. Hơn một năm sau, ông mới biết rằng giáo sư đã sai.

Năm 2014, khi còn là sinh viên cao học năm nhất tại Đại học Illinois, Bernshteyn đã tham gia một khóa học logic với Anush Tserunyan , người sau này trở thành một trong những người hướng dẫn của anh. Bà đã sửa chữa quan niệm sai lầm. “Bà ấy xứng đáng nhận tất cả công lao vì đã đưa tôi đến với lĩnh vực này,” anh nói. “Bà ấy thực sự đã giúp tôi hiểu rằng logic và lý thuyết tập hợp là chất keo kết nối tất cả các phần khác nhau của toán học.”

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 có nhiều kích thước khác nhau của vô cực . Ví dụ, tập hợp các số nguyên dương (0, 1, 2, 3, …) có cùng kích thước với tập hợp tất cả các phân số, nhưng nhỏ hơn tập hợp tất cả các số thực

Anush Tserunyan coi lý thuyết tập hợp mô tả như là sợi dây liên kết các phần khác nhau của toán học lại với nhau.

Ảnh: Do Anush Tserunyan cung cấp

Vào thời điểm đó, các nhà toán học cảm thấy vô cùng khó chịu với mớ hỗn độn các loại vô cực khác nhau này. "Thật khó để hiểu nổi", Bernshteyn, hiện đang làm việc tại Đại học California, Los Angeles, cho biết.

Một phần để đáp lại sự khó chịu đó, các nhà toán học đã phát triển một khái niệm khác về kích thước—một khái niệm mô tả, chẳng hạn, chiều dài, diện tích hoặc thể tích mà một tập hợp có thể chiếm, thay vì số lượng phần tử mà nó chứa. Khái niệm về kích thước này được gọi là “độ đo” của một tập hợp (trái ngược với khái niệm về kích thước của Cantor, là “lực lượng” của một tập hợp). Một trong những loại độ đo đơn giản nhất—độ đo Lebesgue—định lượng chiều dài của một tập hợp. Mặc dù tập hợp các số thực từ 0 đến 1 và tập hợp các số thực từ 0 đến 10 đều vô hạn và có cùng lực lượng, nhưng tập hợp thứ nhất có độ đo Lebesgue là 1 và tập hợp thứ hai có độ đo Lebesgue là 10.

Georg Cantor đã phát hiện ra rằng vô cực trong toán học có thể xuất hiện dưới nhiều hình dạng và kích thước khác nhau.

Nguồn ảnh: Emilio Segre Visual Archives

Để nghiên cứu các tập hợp phức tạp hơn, các nhà toán học sử dụng các loại phép đo khác. Tập hợp càng "xấu xí" thì càng có ít cách để đo lường nó. Các nhà lý thuyết tập hợp mô tả đặt ra các câu hỏi về việc tập hợp nào có thể được đo lường theo các định nghĩa khác nhau về "phép đo". Sau đó, họ sắp xếp chúng theo một hệ thống phân cấp dựa trên câu trả lời cho những câu hỏi đó. Ở trên cùng là các tập hợp có thể được xây dựng dễ dàng và nghiên cứu bằng bất kỳ khái niệm phép đo nào bạn muốn. Ở dưới cùng là các tập hợp "không thể đo lường", chúng phức tạp đến mức không thể đo lường được. "Từ mà mọi người thường dùng là 'bệnh lý'", Bernshteyn nói. "Các tập hợp không thể đo lường thực sự rất tệ. Chúng phản trực giác và chúng không hoạt động tốt."

Hệ thống phân cấp này không chỉ giúp các nhà lý thuyết tập hợp vạch ra bức tranh tổng thể của lĩnh vực nghiên cứu của họ; nó còn cung cấp cho họ những hiểu biết sâu sắc về các công cụ mà họ có thể sử dụng để giải quyết các vấn đề điển hình hơn trong các lĩnh vực toán học khác. Các nhà toán học trong một số lĩnh vực, chẳng hạn như hệ động lực, lý thuyết nhóm và lý thuyết xác suất, cần thông tin về kích thước của các tập hợp mà họ đang sử dụng. Vị trí của một tập hợp trong hệ thống phân cấp quyết định các công cụ mà họ có thể sử dụng để giải quyết vấn đề của mình.

Các nhà lý thuyết tập hợp mô tả do đó giống như những người thủ thư, chăm sóc một giá sách khổng lồ chứa đầy các loại tập hợp vô hạn khác nhau (và các cách đo lường khác nhau của chúng). Công việc của họ là tiếp nhận một vấn đề, xác định độ phức tạp của một tập hợp mà lời giải của nó đòi hỏi, và đặt nó vào đúng vị trí trên giá sách, để các nhà toán học khác có thể ghi nhận.

Đưa ra lựa chọn

Bernshteyn thuộc một nhóm các nhà thư viện chuyên giải quyết các vấn đề về tập hợp vô hạn các nút được kết nối bằng các cạnh, được gọi là đồ thị. Cụ thể, ông nghiên cứu các đồ thị có vô số phần riêng biệt, mỗi phần chứa vô số nút. Hầu hết các nhà lý thuyết đồ thị không nghiên cứu loại đồ thị này; thay vào đó, họ tập trung vào các đồ thị hữu hạn. Nhưng các đồ thị vô hạn như vậy có thể biểu diễn và cung cấp thông tin về các hệ động lực và các loại tập hợp quan trọng khác, khiến chúng trở thành một lĩnh vực nghiên cứu trọng điểm đối với các nhà lý thuyết tập hợp mô tả.

Đây là một ví dụ về loại đồ thị vô hạn mà Bernshteyn và các đồng nghiệp của ông có thể nghiên cứu. Bắt đầu với một hình tròn, chứa vô số điểm. Chọn một điểm: Đây sẽ là nút đầu tiên của bạn. Sau đó, di chuyển một khoảng cách cố định xung quanh chu vi của hình tròn. Điều này sẽ cho bạn một nút thứ hai. Ví dụ, bạn có thể di chuyển một phần năm quãng đường quanh hình tròn. Nối hai nút bằng một cạnh. Di chuyển cùng khoảng cách đó đến nút thứ ba và nối nó với nút trước đó. Và cứ thế tiếp tục.

Nếu mỗi lần bạn di chuyển một phần năm quãng đường quanh vòng tròn, sẽ mất năm bước để quay lại điểm xuất phát. Nói chung, nếu bạn di chuyển bất kỳ khoảng cách nào có thể viết dưới dạng phân số, các nút sẽ tạo thành một vòng khép kín. Nhưng nếu khoảng cách không thể viết dưới dạng phân số, quá trình này sẽ tiếp diễn mãi mãi. Bạn sẽ có vô số nút được kết nối.

Hình minh họa: Mark Belan/Tạp chí Quanta

Nhưng đó chưa phải là tất cả: Chuỗi dài vô tận này chỉ tạo thành phần đầu tiên của đồ thị. Mặc dù nó chứa vô số nút, nhưng nó không chứa tất cả các điểm trên đường tròn. Để tạo ra các phần còn lại của đồ thị, hãy bắt đầu từ một trong những điểm đó. Bây giờ, hãy di chuyển cùng một khoảng cách ở mỗi bước như bạn đã làm ở phần đầu tiên. Cuối cùng, bạn sẽ xây dựng được một chuỗi vô tận thứ hai gồm các nút được kết nối, hoàn toàn không liên kết với chuỗi đầu tiên.

Nhưng để thực hiện việc tô màu này, bạn phải dựa vào một giả định ngầm mà các nhà lý thuyết tập hợp gọi là tiên đề chọn. Đó là một trong chín khối xây dựng cơ bản tạo nên tất cả các mệnh đề toán học. Theo tiên đề này, nếu bạn bắt đầu với một tập hợp các tập hợp, bạn có thể chọn một phần tử từ mỗi tập hợp đó để tạo ra một tập hợp mới—ngay cả khi bạn có vô số tập hợp để lựa chọn. Tiên đề này rất hữu ích, vì nó cho phép các nhà toán học chứng minh tất cả các loại mệnh đề thú vị. Nhưng nó cũng dẫn đến những nghịch lý kỳ lạ. Các nhà lý thuyết tập hợp mô tả tránh nó.

Đồ thị của bạn có vô số mảnh ghép. Điều này tương ứng với việc có vô số tập hợp. Bạn đã chọn một phần tử từ mỗi tập hợp—điểm đầu tiên mà bạn quyết định tô màu xanh lam trong mỗi mảnh ghép. Tất cả các điểm màu xanh lam đó tạo thành một tập hợp mới. Bạn đã sử dụng tiên đề chọn.

Điều này dẫn đến một vấn đề khi bạn tô màu các nút còn lại theo các mẫu xen kẽ màu xanh lam và vàng. Bạn đã tô màu từng nút (có độ dài bằng không) một cách riêng biệt, mà không hiểu mối quan hệ giữa các nút với nhau khi chúng đến từ các phần khác nhau của đồ thị. Điều này có nghĩa là bạn không thể mô tả tập hợp tất cả các nút màu xanh lam của đồ thị, hoặc tập hợp tất cả các nút màu vàng của nó, theo độ dài. Nói cách khác, các tập hợp này là không thể đo lường được. Các nhà toán học không thể nói bất cứ điều gì hữu ích về chúng.

Đối với các nhà lý thuyết tập hợp mô tả, điều này là không thỏa đáng. Vì vậy, họ muốn tìm ra cách tô màu đồ thị một cách liên tục—một cách không sử dụng tiên đề chọn, và mang lại cho họ các tập hợp đo được.

Để làm điều này, hãy nhớ lại cách bạn đã xây dựng phần đầu tiên của đồ thị: Bạn chọn một nút trên một đường tròn và nối nó với một nút thứ hai cách đó một khoảng. Bây giờ hãy tô màu nút đầu tiên màu xanh lam, nút thứ hai màu vàng và toàn bộ cung tròn giữa chúng màu xanh lam. Tương tự, hãy tô màu cung tròn giữa nút thứ hai và nút thứ ba màu vàng. Tô màu cung tròn thứ ba màu xanh lam. Và cứ thế tiếp tục.

Chẳng mấy chốc, bạn sẽ tô màu gần như hoàn toàn một vòng tròn—có nghĩa là bạn đã tô màu cho tất cả các nút trong đồ thị của mình ngoại trừ những nút nằm trong một đoạn nhỏ còn sót lại. Giả sử cung cuối cùng bạn tô màu là màu vàng. Làm thế nào để bạn tô màu cho đoạn nhỏ cuối cùng này? Bạn không thể dùng màu xanh lam, vì các nút này sẽ kết nối với các nút trong cung ban đầu bạn đã tô màu xanh lam. Nhưng bạn cũng không thể dùng màu vàng, vì các nút này kết nối trở lại với các nút màu vàng từ cung trước đó.

Bạn cần sử dụng màu thứ ba—ví dụ như màu xanh lá cây—để hoàn thành việc tô màu.

Tuy nhiên, các tập hợp các nút màu xanh lam, vàng và xanh lục mà bạn thu được đều chỉ là các phần của chu vi hình tròn, chứ không phải là các điểm phân tán mà bạn thu được khi sử dụng tiên đề chọn. Bạn có thể tính toán độ dài của các tập hợp này. Chúng có thể đo được.

Do đó, các nhà lý thuyết tập hợp mô tả đặt phiên bản hai màu của bài toán ở vị trí thấp nhất trong hệ thống phân cấp của họ (đối với các tập hợp không đo được), trong khi bài toán ba màu được đặt ở vị trí cao hơn nhiều – những bài toán mà nhiều khái niệm về đo lường có thể được áp dụng.

Bernshteyn đã dành nhiều năm học cao học để nghiên cứu các bài toán tô màu như vậy, giải quyết chúng từng cái một. Sau đó, không lâu sau khi tốt nghiệp, ông tình cờ tìm ra một cách tiềm năng để giải quyết tất cả chúng cùng một lúc—và chứng minh rằng những bài toán này có cấu trúc sâu sắc hơn và có ý nghĩa toán học hơn nhiều so với những gì mọi người từng nhận ra.

Từng vòng một

Thỉnh thoảng, Bernshteyn thích tham dự các buổi thuyết trình về khoa học máy tính, nơi đồ thị là hữu hạn và biểu diễn mạng lưới máy tính.

Năm 2019, một trong những bài thuyết trình đó đã thay đổi hướng đi sự nghiệp của ông. Bài thuyết trình nói về “thuật toán phân tán”—tập hợp các lệnh được chạy đồng thời trên nhiều máy tính trong mạng để hoàn thành một nhiệm vụ mà không cần bộ điều phối trung tâm.

Giả sử bạn có nhiều bộ định tuyến Wi-Fi trong một tòa nhà. Các bộ định tuyến gần nhau có thể gây nhiễu lẫn nhau nếu chúng sử dụng cùng một kênh tần số truyền thông. Vì vậy, mỗi bộ định tuyến cần chọn một kênh khác với các kênh được sử dụng bởi các bộ định tuyến lân cận.

Các nhà khoa học máy tính có thể diễn giải lại bài toán này như một bài toán tô màu trên đồ thị: Biểu diễn mỗi bộ định tuyến như một nút, và kết nối các nút lân cận bằng các cạnh. Chỉ sử dụng hai màu (biểu thị hai kênh tần số khác nhau), hãy tìm cách tô màu cho mỗi nút sao cho không có hai nút nào được kết nối có cùng màu.

Nhưng có một điều cần lưu ý: Các nút chỉ có thể giao tiếp với các nút lân cận trực tiếp của chúng, bằng cách sử dụng các thuật toán cục bộ. Đầu tiên, mỗi nút chạy cùng một thuật toán và tự gán cho mình một màu. Sau đó, nó giao tiếp với các nút lân cận để tìm hiểu cách các nút khác được tô màu trong một vùng nhỏ xung quanh nó. Tiếp theo, nó chạy lại thuật toán để quyết định xem có giữ nguyên màu hiện tại hay đổi màu. Nó lặp lại bước này cho đến khi toàn bộ mạng lưới được tô màu đúng cách.

Các nhà khoa học máy tính muốn biết một thuật toán cụ thể cần bao nhiêu bước. Ví dụ, bất kỳ thuật toán cục bộ nào có thể giải quyết bài toán định tuyến chỉ với hai màu đều cực kỳ kém hiệu quả, nhưng có thể tìm thấy một thuật toán cục bộ rất hiệu quả nếu được phép sử dụng ba màu.

Tại buổi nói chuyện mà Bernshteyn tham dự, diễn giả đã thảo luận về các ngưỡng này đối với các loại vấn đề khác nhau. Ông nhận ra rằng một trong những ngưỡng đó nghe rất giống với một ngưỡng tồn tại trong lý thuyết tập hợp mô tả—về số lượng màu sắc cần thiết để tô màu một số đồ thị vô hạn nhất định theo cách có thể đo lường được.

Đối với Bernshteyn, điều đó dường như không chỉ là sự trùng hợp ngẫu nhiên. Không chỉ đơn thuần là các nhà khoa học máy tính cũng giống như những người thủ thư, sắp xếp các vấn đề dựa trên hiệu quả hoạt động của thuật toán. Cũng không chỉ đơn thuần là những vấn đề này cũng có thể được diễn đạt bằng đồ thị và phép tô màu.

Có lẽ, anh nghĩ, hai giá sách đó có nhiều điểm chung hơn thế. Có lẽ mối liên hệ giữa hai lĩnh vực này còn sâu sắc hơn nhiều.

Có lẽ tất cả các cuốn sách, và cả giá sách, đều giống hệt nhau, chỉ khác nhau ở ngôn ngữ - và cần người phiên dịch.

Mở cánh cửa

Bernshteyn đã đặt mục tiêu làm rõ mối liên hệ này. Ông muốn chứng minh rằng mọi thuật toán cục bộ hiệu quả đều có thể được chuyển đổi thành một cách tô màu đồ thị vô hạn có thể đo được theo Lebesgue (thỏa mãn một số tính chất quan trọng khác). Nghĩa là, một trong những "kệ" quan trọng nhất của khoa học máy tính tương đương với một trong những "kệ" quan trọng nhất của lý thuyết tập hợp (ở vị trí cao trong hệ thống phân cấp).

Ông bắt đầu với các bài toán mạng từ bài giảng khoa học máy tính, tập trung vào quy tắc bao quát của chúng—rằng thuật toán của bất kỳ nút nào cũng chỉ sử dụng thông tin về vùng lân cận cục bộ của nó, bất kể đồ thị có một nghìn nút hay một tỷ nút.

Để hoạt động đúng cách, thuật toán chỉ cần gán cho mỗi nút trong một vùng lân cận nhất định một số duy nhất, để nó có thể ghi lại thông tin về các nút lân cận và đưa ra hướng dẫn về chúng. Điều đó khá dễ thực hiện trong một đồ thị hữu hạn: Chỉ cần gán cho mỗi nút trong đồ thị một số khác nhau.

Nhà khoa học máy tính Václav Rozhoň đã tận dụng mối liên hệ mới được phát hiện giữa lý thuyết tập hợp và khoa học mạng để giải quyết các vấn đề mà ông quan tâm. Ảnh: Tomáš Princ, Đại học Charles

Nếu Bernshteyn có thể chạy cùng một thuật toán trên một đồ thị vô hạn, điều đó có nghĩa là ông ấy có thể tô màu đồ thị theo một cách có thể đo lường được—giải quyết một bài toán tô màu đồ thị thuộc lĩnh vực lý thuyết tập hợp. Nhưng có một vấn đề: Những đồ thị vô hạn này là vô hạn "không đếm được". Không có cách nào để gán nhãn duy nhất cho tất cả các nút của chúng.

Thử thách của Bernshteyn là tìm ra một cách khéo léo hơn để chú thích các đồ thị.

Anh ấy biết rằng mình sẽ phải tái sử dụng nhãn. Nhưng điều đó không sao miễn là các nút lân cận được dán nhãn khác nhau. Liệu có cách nào để gán nhãn mà không vô tình tái sử dụng một nhãn trong cùng một khu vực lân cận không?

Bernshteyn đã chứng minh rằng luôn có cách giải quyết – bất kể bạn quyết định sử dụng bao nhiêu nhãn và bất kể vùng lân cận cục bộ của bạn có bao nhiêu nút. Điều này có nghĩa là bạn luôn có thể mở rộng thuật toán một cách an toàn từ phía khoa học máy tính sang phía lý thuyết tập hợp. Rozhoň nói: “Bất kỳ thuật toán nào trong thiết lập của chúng tôi đều tương ứng với một cách tô màu có thể đo lường được cho bất kỳ đồ thị nào trong thiết lập lý thuyết tập hợp mô tả”.

Bằng chứng này đã gây bất ngờ cho các nhà toán học. Nó chứng minh mối liên hệ sâu sắc giữa tính toán và khả năng định nghĩa, cũng như giữa thuật toán và các tập hợp đo được. Các nhà toán học hiện đang tìm hiểu cách tận dụng phát hiện của Bernshteyn. Ví dụ, trong một bài báo được xuất bản năm nay, Rozhoň và các đồng nghiệp đã tìm ra rằng có thể tô màu các đồ thị đặc biệt gọi là cây bằng cách xem xét cùng một vấn đề trong bối cảnh khoa học máy tính. Kết quả này cũng làm sáng tỏ những công cụ mà các nhà toán học có thể sử dụng để nghiên cứu các hệ động lực tương ứng của cây. “Đây là một trải nghiệm rất thú vị, khi cố gắng chứng minh các kết quả trong một lĩnh vực mà tôi thậm chí không hiểu các định nghĩa cơ bản,” Rozhoň nói.

Các nhà toán học cũng đã nỗ lực chuyển dịch các vấn đề theo chiều ngược lại. Trong một trường hợp, họ đã sử dụng lý thuyết tập hợp để chứng minh một ước lượng mới về độ khó giải quyết của một lớp vấn đề nhất định.

Cầu nối của Bernshteyn không chỉ đơn thuần là một bộ công cụ mới để giải quyết các vấn đề riêng lẻ. Nó còn cho phép các nhà lý thuyết tập hợp có được cái nhìn rõ ràng hơn về lĩnh vực của họ. Trước đây, có rất nhiều vấn đề mà họ không biết cách phân loại. Trong nhiều trường hợp, điều đó giờ đã thay đổi, bởi vì các nhà lý thuyết tập hợp đã có những "giá sách" được sắp xếp khoa học hơn của các nhà khoa học máy tính để hướng dẫn họ.

Bernshteyn hy vọng lĩnh vực nghiên cứu đang phát triển này sẽ thay đổi cách các nhà toán học thực hành nhìn nhận công trình của các nhà lý thuyết tập hợp – rằng họ sẽ không còn coi đó là xa vời và tách rời khỏi thế giới toán học thực tế nữa. “Tôi đang cố gắng thay đổi điều này,” ông nói. “Tôi muốn mọi người làm quen với việc suy nghĩ về vô cực.”

Bài viết gốc được đăng lại với sự cho phép của Quanta Magazine , một ấn phẩm độc lập về mặt biên tập của Quỹ Simons, với sứ mệnh nâng cao hiểu biết của công chúng về khoa học bằng cách đưa tin về các phát triển và xu hướng nghiên cứu trong toán học, khoa học vật lý và khoa học sinh học.