Bạn sẽ học được gì
- Xây dựng ngôn ngữ bậc nhất, viết công thức, câu và diễn giải chúng trong một cấu trúc
- Thực hiện suy diễn hình thức và phân biệt rõ tính suy diễn được với tính đúng trong mô hình
- Phát biểu, nắm khung chứng minh và áp dụng định lý đầy đủ, định lý compact và định lý Löwenheim–Skolem
- Giải thích mã hóa Gödel, tính biểu diễn được và bổ đề tự tham chiếu
- Phát biểu và nắm khung chứng minh hai định lý bất toàn của Gödel, cùng liên hệ với bài toán dừng
- Trình bày hệ tiên đề ZFC và xây dựng số tự nhiên, quan hệ, hàm từ tập hợp
- Làm việc với bản số, tiên đề chọn, bổ đề Zorn, thứ tự tốt và tự số
Nên học trước
Giới thiệu
Logic toán và lý thuyết tập hợp lấy chính toán học làm đối tượng nghiên cứu. Thay vì chứng minh một định lý cụ thể, ta hỏi: một chứng minh là gì, một mô hình của một hệ tiên đề là gì, và có những giới hạn nào mà không hệ tiên đề nào vượt qua được? Những câu trả lời — định lý đầy đủ và hai định lý bất toàn của Gödel, hệ tiên đề Zermelo–Fraenkel cho tập hợp — là một trong những thành tựu trí tuệ lớn nhất của thế kỷ XX, và có hệ quả trực tiếp cho tin học: giới hạn của thuật toán, kiểm chứng hình thức, trợ lý chứng minh như Lean và Coq.
Cú pháp và ngữ nghĩa
Điểm xuất phát là phân biệt rạch ròi hai thế giới. Cú pháp: một ngôn ngữ bậc nhất gồm ký hiệu hằng, hàm, quan hệ, biến và lượng từ; công thức và câu được xây dựng theo quy tắc hình thức, và suy diễn là chuỗi công thức sinh ra từ tiên đề logic theo các quy tắc suy luận. Ngữ nghĩa: một cấu trúc (mô hình) diễn giải các ký hiệu thành tập hợp, hàm và quan hệ cụ thể, và một câu có thể đúng hoặc sai trong cấu trúc đó. Ví dụ, câu "mọi phần tử đều có nghịch đảo" đúng trong cấu trúc (ℚ ∖ {0}, ·) nhưng sai trong (ℤ, ·).
Định lý đầy đủ và định lý compact
Định lý đầy đủ của Gödel nối hai thế giới: một câu suy diễn được từ một tập tiên đề khi và chỉ khi nó đúng trong mọi mô hình của tập tiên đề đó — "chứng minh được" trùng với "đúng ở mọi nơi". Hệ quả là định lý compact (compactness theorem): một tập câu có mô hình nếu mọi tập con hữu hạn của nó có mô hình. Từ đây xuất hiện những kết quả bất ngờ: tồn tại mô hình "không chuẩn" của số học có phần tử lớn hơn mọi số tự nhiên, và định lý Löwenheim–Skolem nói rằng một lý thuyết có mô hình vô hạn thì có mô hình ở nhiều bản số khác nhau.
Hai định lý bất toàn
Phần trung tâm của môn học là định lý bất toàn thứ nhất: mọi hệ tiên đề nhất quán, liệt kê được bằng thuật toán và đủ mạnh để diễn tả số học đều có một câu đúng mà không chứng minh được trong hệ. Định lý bất toàn thứ hai: một hệ như vậy không thể tự chứng minh tính nhất quán của chính nó. Con đường tới đó đi qua mã hóa Gödel (gán cho mỗi công thức và mỗi chứng minh một số tự nhiên), hàm đệ quy nguyên thủy, tính biểu diễn được trong số học và bổ đề tự tham chiếu — chính là ý tưởng của câu "câu này không chứng minh được". Giáo trình chính còn trình bày con đường thứ hai, qua tính toán được: nếu mọi câu đúng của số học đều chứng minh được thì bài toán dừng sẽ giải được, mâu thuẫn.
Lý thuyết tập hợp tiên đề
Phần cuối xây dựng toán học từ tập hợp: hệ tiên đề ZFC (Zermelo–Fraenkel với tiên đề chọn), cách định nghĩa quan hệ, hàm, số tự nhiên, số thực chỉ bằng tập hợp; bản số và định lý Cantor (không có song ánh giữa một tập và tập lũy thừa của nó), tiên đề chọn và các dạng tương đương như bổ đề Zorn; thứ tự tốt và tự số (số thứ tự), cho phép "đếm" vượt qua vô hạn và chứng minh bằng quy nạp siêu hạn.
Cách học hiệu quả
Đây là môn trừu tượng và giàu chứng minh — cần đã thành thạo viết chứng minh và quen với tập hợp, quy nạp, đồ thị từ Toán rời rạc. Hãy làm hết bài tập phần cú pháp và ngữ nghĩa trước khi sang định lý bất toàn: phần mã hóa rất dài nhưng từng bước đều đơn giản. Với mỗi định lý lớn, tự tóm tắt khung chứng minh trong nửa trang. Bài giảng về định lý đệ quy và logic trong khóa Lý thuyết tính toán (MIT 18.404J) trên OpenER cho một góc nhìn tin học rất ngắn gọn về định lý bất toàn.
Sau môn này
Bạn có thể học tiếp lý thuyết mô hình, lý thuyết chứng minh, lý thuyết tính toán được, lý thuyết tập hợp nâng cao (forcing, tính độc lập của giả thuyết continuum), hoặc chuyển sang hướng ứng dụng như kiểm chứng hình thức và trợ lý chứng minh.
Về thời lượng: số giờ ghi ở các bước là thời lượng tối thiểu cho lượt học đầu; một học phần tương đương ở đại học thường cần 120–150 giờ.
Giáo trình & sách tham khảo
Xem tất cả trong tab SáchGiáo trình chính
A Friendly Introduction to Mathematical Logic
Christopher C. Leary, Lars Kristiansen · 2015 · Bản thứ 2
Vì sao chọn: Giáo trình mở (CC BY-NC-SA 4.0) của Milne Library, SUNY Geneseo, tải miễn phí hợp pháp; được Viện Toán học Hoa Kỳ (AIM) chấp thuận trong chương trình giáo trình mở. Đúng như tên gọi, sách dẫn dắt người mới từ ngôn ngữ, cấu trúc và suy diễn tới chứng minh chặt chẽ cả hai định lý bất toàn, kèm lời giải cho một số bài tập. Bốn bước đầu của lộ trình bám theo Chương 1–6.
Nên đọc: Chương 1–6
A Mathematical Introduction to Logic
Herbert B. Enderton · 2001 · Bản thứ 2
Giáo trình logic toán kinh điển (Academic Press, trả phí), chặt chẽ và cô đọng hơn sách chính, với phần logic mệnh đề, logic bậc nhất và tính không quyết định được rất chuẩn mực. Tên chương theo mục lục của nhà xuất bản.
Nên đọc: Sentential Logic; First-Order Logic; Undecidability
Elements of Set Theory
Herbert B. Enderton · 1977
Nhập môn lý thuyết tập hợp tiên đề rõ ràng và gọn (Academic Press, trả phí): các tiên đề, số tự nhiên, bản số, tiên đề chọn, thứ tự và tự số. Là tài liệu chính cho bước cuối của lộ trình; Chương 5 về xây dựng số thực là phần đọc thêm.
Nên đọc: Chương 1–4, Chương 6–8
Các bước học
Đăng nhập để đánh dấu các bước đã hoàn thành.
Bước 1: Ngôn ngữ bậc nhất và cấu trúc
khoảng 7 giờNgôn ngữ, số hạng, công thức và câu; cấu trúc và phép gán giá trị cho biến; định nghĩa chân lý của Tarski, quan hệ thỏa mãn và hệ quả logic; tính thay thế được. Luyện tập: viết các tiên đề của lý thuyết nhóm và của thứ tự tuyến tính dày đặc trong một ngôn ngữ bậc nhất, rồi tìm cấu trúc thỏa mãn và cấu trúc không thỏa mãn từng tiên đề.
- Đọc: Chương 1 Structures and Languages — A Friendly Introduction to Mathematical Logic
Bước 2: Suy diễn hình thức
khoảng 6 giờHệ suy diễn: tiên đề logic, quy tắc suy luận, định nghĩa suy diễn; các chiến lược chứng minh hình thức và định lý về tính đúng đắn (soundness). Luyện tập: viết đầy đủ vài suy diễn hình thức ngắn và chứng minh bổ đề suy diễn; giải thích vì sao mọi điều suy diễn được đều đúng trong mọi mô hình.
- Đọc: Chương 2 Deductions — A Friendly Introduction to Mathematical Logic
Bước 3: Định lý đầy đủ và định lý compact
khoảng 8 giờChứng minh định lý đầy đủ (dựng mô hình từ một tập câu nhất quán cực đại có tính chất Henkin), định lý compact và các hệ quả: mô hình không chuẩn của số học, định lý Löwenheim–Skolem. Luyện tập: dùng định lý compact chứng minh không có tập câu bậc nhất nào mô tả đúng lớp các đồ thị liên thông, hoặc lớp các nhóm hữu hạn; tóm tắt khung chứng minh định lý đầy đủ trong nửa trang.
- Đọc: Chương 3 Completeness and Compactness — A Friendly Introduction to Mathematical Logic
- Đọc: First-Order Logic — A Mathematical Introduction to Logic
Bước 4: Mã hóa Gödel và hai định lý bất toàn
khoảng 10 giờBất toàn qua hai con đường: tính toán được (liên hệ với bài toán dừng) và cú pháp; ngôn ngữ số học và hệ tiên đề N, tính biểu diễn được của các hàm đệ quy nguyên thủy, mã hóa Gödel, bổ đề tự tham chiếu, định lý bất toàn thứ nhất và thứ hai. Luyện tập: tự mã hóa một công thức ngắn thành số Gödel; viết lại bằng lời chứng minh định lý bất toàn thứ nhất; xem bài giảng về định lý đệ quy và logic của MIT 18.404J trên trang để thấy cùng kết quả dưới góc nhìn máy Turing.
- Đọc: Chương 4 Incompleteness From Two Points of View; Chương 5 Syntactic Incompleteness - Groundwork; Chương 6 The Incompleteness Theorems — A Friendly Introduction to Mathematical Logic
- Đọc: Undecidability — A Mathematical Introduction to Logic
Bước 5: Lý thuyết tập hợp tiên đề: ZFC, bản số và tự số
khoảng 11 giờCác tiên đề của ZF và các phép toán tập hợp; xây dựng quan hệ, hàm và số tự nhiên từ tập hợp; bản số, định lý Cantor và định lý Schröder–Bernstein, tiên đề chọn và các dạng tương đương (bổ đề Zorn, định lý sắp thứ tự tốt); thứ tự tốt, tự số, quy nạp siêu hạn và kiểu thứ tự. Luyện tập: chứng minh ℝ và P(ℕ) cùng bản số; dùng bổ đề Zorn chứng minh mọi không gian vectơ có cơ sở.
- Đọc: Chương 2 Axioms and Operations; 3 Relations and Functions; 4 Natural Numbers; 6 Cardinal Numbers and the Axiom of Choice; 7 Orderings and Ordinals; 8 Ordinals and Order Types — Elements of Set Theory
Khái niệm chính
- Ngôn ngữ bậc nhất
- Tập ký hiệu hằng, hàm và quan hệ cùng biến, phép nối logic và lượng từ ∀, ∃ chạy trên các phần tử; các công thức được sinh theo quy tắc hình thức.
- Cấu trúc (mô hình)
- Một tập nền cùng cách diễn giải các ký hiệu của ngôn ngữ; một câu đúng hay sai tùy theo cấu trúc, và M ⊨ φ nghĩa là câu φ đúng trong M.
- Suy diễn hình thức
- Dãy hữu hạn công thức, mỗi công thức là tiên đề hoặc suy ra từ các công thức trước theo quy tắc suy luận; Σ ⊢ φ nghĩa là φ suy diễn được từ Σ.
- Tính đúng đắn (soundness)
- Mọi điều suy diễn được đều đúng: nếu Σ ⊢ φ thì φ đúng trong mọi mô hình của Σ.
- Định lý đầy đủ của Gödel
- Chiều ngược lại của tính đúng đắn: nếu φ đúng trong mọi mô hình của Σ thì Σ ⊢ φ. Suy diễn được và đúng ở mọi mô hình là một.
- Định lý compact (compactness theorem)
- Một tập câu có mô hình khi và chỉ khi mọi tập con hữu hạn của nó có mô hình; dẫn tới sự tồn tại của mô hình không chuẩn của số học.
- Định lý Löwenheim–Skolem
- Lý thuyết đếm được có mô hình vô hạn thì có mô hình ở mọi bản số vô hạn; logic bậc nhất không phân biệt được các bản số vô hạn.
- Mã hóa Gödel
- Gán cho mỗi ký hiệu, công thức và chứng minh một số tự nhiên duy nhất, để các khẳng định về chứng minh trở thành khẳng định về số.
- Định lý bất toàn thứ nhất
- Mọi lý thuyết nhất quán, liệt kê được bằng thuật toán và chứa đủ số học đều có một câu mà cả nó lẫn phủ định của nó đều không chứng minh được trong lý thuyết.
- Định lý bất toàn thứ hai
- Một lý thuyết như trên không chứng minh được câu khẳng định tính nhất quán của chính nó.
- Hệ tiên đề ZFC
- Hệ tiên đề Zermelo–Fraenkel cùng tiên đề chọn; là nền móng chuẩn mà gần như toàn bộ toán học hiện đại được xây dựng trên đó.
- Định lý Cantor
- Không có toàn ánh từ một tập A lên tập lũy thừa P(A); vì vậy có vô hạn cấp độ vô hạn ngày càng lớn.
- Tiên đề chọn và bổ đề Zorn
- Mọi họ gồm các tập khác rỗng đều có một hàm chọn; tương đương với bổ đề Zorn và định lý sắp thứ tự tốt, được dùng để chứng minh mọi không gian vectơ có cơ sở.
- Tự số
- Các “số thứ tự” mở rộng số tự nhiên vượt qua vô hạn (ω, ω + 1, …), đại diện cho mọi tập được sắp thứ tự tốt; cho phép quy nạp và đệ quy siêu hạn.
Học xong để làm gì
- Tin học lý thuyết: giới hạn của thuật toán, tính không quyết định được và mối liên hệ giữa chứng minh với chương trình
- Kiểm chứng hình thức phần mềm và phần cứng: logic bậc nhất, bộ giải SAT/SMT và các công cụ kiểm tra mô hình
- Trợ lý chứng minh như Lean, Coq, Isabelle, nơi các định lý toán học được kiểm tra hoàn toàn bằng máy
- Cơ sở dữ liệu: ngôn ngữ truy vấn quan hệ có nền tảng là logic bậc nhất
- Nền móng của toán học: xác định chính xác thế nào là một chứng minh và những gì có thể hoặc không thể chứng minh
- Triết học toán học và trí tuệ nhân tạo: suy luận tự động, biểu diễn tri thức bằng logic
Câu hỏi thường gặp
Môn này khác gì phần logic trong Nhập môn chứng minh và Toán rời rạc?
Hai môn đó dùng logic như một công cụ để viết chứng minh. Môn này biến logic thành đối tượng nghiên cứu: định nghĩa hình thức ngôn ngữ, suy diễn và mô hình, rồi chứng minh các định lý về chính chúng như định lý đầy đủ và định lý bất toàn.
Định lý bất toàn có nghĩa là toán học “không đáng tin” không?
Không. Nó nói rằng không có hệ tiên đề (đủ mạnh, liệt kê được) nào chứng minh được mọi mệnh đề đúng của số học, và không hệ nào tự chứng minh được tính nhất quán của mình. Các định lý đã chứng minh vẫn đúng; chỉ là luôn có những câu hỏi nằm ngoài tầm với của một hệ tiên đề cố định.
Vì sao môn này được xếp mức nâng cao?
Vì nó đòi hỏi làm việc cùng lúc ở hai tầng (toán học và siêu toán học), với những chứng minh dài như chứng minh định lý đầy đủ và phần mã hóa Gödel. Nên học sau khi đã vững kỹ năng chứng minh và Toán rời rạc; học Lý thuyết tính toán trước hoặc song song cũng rất có ích.
Có cần học lý thuyết tập hợp trước phần logic không?
Không. Phần logic chỉ cần tập hợp ở mức ngây thơ (hợp, giao, ánh xạ, tập đếm được). Lý thuyết tập hợp tiên đề được học ở bước cuối của lộ trình, khi bạn đã hiểu thế nào là một hệ tiên đề bậc nhất.
Giáo trình chính có miễn phí không?
Có. A Friendly Introduction to Mathematical Logic (lần xuất bản thứ hai) là giáo trình mở của Milne Library (SUNY Geneseo), tải miễn phí hợp pháp. Hai cuốn của Enderton là sách trả phí, dùng để đọc sâu phần logic và phần tập hợp.



