Logic toán

Logic toán là một ngành con của toán học có liên hệ gần gũi với cơ sở toán học, khoa học máy tính lý thuyết, logic triết học. Ngành này bao gồm hai phần: nghiên cứu toán học về logic và những ứng dụng của logic hình thức trong các ngành khác của toán học. Các chủ đề thống nhất trong logic toán học bao gồm các nghiên cứu về khả năng thể hiện ý nghĩa và khả năng suy diễn của các hệ thống logic hình thức.

Ngành này thường được chia thành các lĩnh vực con như lý thuyết mô hình, lý thuyết chứng minh, lý thuyết tập hợp và lý thuyết tính toán. Nghiên cứu về logic toán thường đóng vai trò quan trọng trong ngành cơ sở toán học.

Kể từ khi ra đời, logic toán đã và đang vừa đóng góp cho ngành cơ sở toán học, vừa được ngành này thúc đẩy. Quá trình nghiên cứu bắt đầu từ cuối thế kỷ 19 với các khung tiên đề cho hình học, số học, và giải tích. Đầu thế kỷ 20, logic toán được định hình bởi chương trình của David Hilbert, vốn có mục đích chứng minh sự phi mâu thuẫn của các lý thuyết cơ sở. Các kết quả của Kurt Gödel, Gerhard Gentzen, v.v, đã phần nào giải quyết chương trình này và làm rõ các vấn đề về chứng minh sự phi mâu thuẫn. Các công trình về lý thuyết tập hợp chỉ ra rằng hầu hết toán học thông thường có thể được hình thức hóa thông qua các tập hợp, dù có các định lý không chứng minh được trong các hệ tiên đề lý thuyết tập hợp thông thường.

Các công trình hiện nay ở lĩnh vực cơ sở toán học thường tập trung xác định xem phần nào của toán học có thể được hình thức hóa trong các hệ thống hình thức nhất định (chẳng hạn như toán học đảo ngược) thay vì tìm những lý thuyết có thể dùng để phát triển toàn bộ toán học.

== Phân ngành và phạm vi ==
Năm 1977, cuốn "Handbook of Mathematical Logic"  tạm chia logic toán đương thời thành bốn lĩnh vực:

1. lý thuyết tập hợp
2. lý thuyết mô hình
3. lý thuyết tính toán
4. lý thuyết chứng minh và toán học kiến thiết (được coi là hai phần của cùng một lĩnh vực)

Ngoài ra, đôi khi ngành lý thuyết độ phức tạp tính toán cũng được xếp vào thành một phần của logic toán.

== Lịch sử ==
Phân ngành logic toán xuất hiện vào khoảng giữa thế kỷ 19 từ sự hội tụ của hai truyền thống toán học và logic hình thức trong triết học. Đây là tập hợp các lý thuyết logic được diễn giải bằng các ký hiệu nhân tạo và phương pháp suy luận chặt chẽ. Trước thời kỳ này, người ta nghiên cứu logic bằng phép tu từ học và hùng biện, calculationes, phép tam đoạn luận, và triết học.

Đầu thế kỷ 20, xuất hiện hàng loạt các kết quả nền tảng và các tranh luận nảy lửa về nền tảng toán học.

=== Thời kỳ đầu ===
Nhiều nền văn hóa trong lịch sử đã phát triển các lý thuyết về logic, như Trung Quốc, Ấn Độ, Hi Lạp và các nền văn minh Hồi giáo. Các phương pháp của Hi Lạp, cụ thể là logic học Aristotle trong bộ tác phẩm Organon, được khoa học và toán học phương Tây ứng dụng và chấp nhận rộng rãi trong hàng thiên niên kỷ. Các nhà Khắc kỷ, đặc biệt là Chrysippus, đã bắt đầu phát triển logic bậc nhất. Vào thế kỷ 18 ở châu Âu, các nhà toán học kiêm triết gia như Leibniz và Lambert đã thử đại số hóa và ký hiệu hóa các thao tác lập luận của logic hình thức, tuy nhiên các công trình này còn lẻ tẻ và ít được chú ý.

=== Thế kỷ 19 ===
Giữa thế kỷ 19, George Boole và sau đó là Augustus De Morgan đã hệ thống hóa logic trong Toán học bằng cách mở rộng quan điểm truyền thống về logic học Aristotles thành khuôn khổ đủ để nghiên cứu nền tảng toán học.

Trong tác phẩm Begriffsschrift xuất bản năm 1879, Gottlob Frege trình bày một phát triển độc lập của logic có lượng từ. Công trình được coi như một bước chuyển mình của lịch sử logic này, tuy nhiên không nhận được nhiều sự chú ý cho đến khi Bertrand Russell quảng bá về nó vào cuối thế kỷ. Ký hiệu hai chiều của Frege chưa từng được sử dụng rộng rãi và không xuất hiện trong các văn bản đương thời.

Từ năm 1890 đến 1905, Enrst Schroder xuất bản ba phần bài giảng über die Algebra der Logik, trong đó ông tóm tắt và mở rộng các công trình của Boole, De Morgan, và Peirce. Đây là một nguồn tham khảo kỹ càng về logic học biểu tượng cuối thế kỷ 19.

==== Các lý thuyết cơ sở ====
Từ các quan ngại về tính đúng đắn của cơ sở của toán học, người ta đã phát triển các hệ thống tiên đề cho các lĩnh vực toán cơ bản.

Giuseppe Peano đã công bố một hệ tên đề số học mang tên ông, dùng một biến thể có lượng từ của hệ thống logic Boole và Schroder. Cũng trong khoảng thời gian này, Richard Dedekind chứng minh được các số tự nhiên xác định duy nhất từ tính chất quy nạp của chúng. Ông sau đó đề xuất một cách xác lập khác thiếu các ký tự hình thức của hệ tiên đề Peano. Tuy nhiên hệ tiên đề này chứng minh được các định lý không thể chỉ ra trong hệ của Peano, bao gồm tính duy nhất của tập hợp các số tự nhiên (theo các đẳng cấu) và định nghĩa phép cộng và phép nhân một cách truy hồi nhờ vào hàm số liền sau và quy nạp.

Giữa thế kỷ 19, người ta dần phát hiện ra các lỗ hổng trong tiên đề hình học của Euclid. Ngoài sự độc lập của tiên đề song song, các nhà toán học nhận ra một số định lý Euclid coi nhẹ thật ra không chứng minh được chỉ từ các tiên đề của ông, chẳng hạn như một đường thẳng chứa ít nhất hai điểm, hay các đường tròn cùng bán kính và hai tâm cách nhau đoạn dài bằng bán kính đó sẽ cắt nhau (xem Mệnh đề 1 cuốn Cơ sở). Hilbert đã hoàn thiện một hệ tiên đề cho hình học dựa vào các công trình trước đó của Pasch. Thành công này là động lực để Hilbert tìm cách lập tiên đề hoàn thiện các hệ tiên đề cho các lĩnh vực toán học khác, như là tập số tự nhiên và đường thẳng thực. Đây sẽ trở thành một lĩnh vực nghiên cứu lớn vào nửa đầu thế kỷ 20.

Thế kỷ 19 cũng là thời điểm có nhiều tiến bộ trong giải tích thực, bao gồm sự hội tụ của hàm và chuỗi Fourier. Các nhà toán học như Karl Weierstrass bắt đầu xây dựng các hàm thách thức trực giác, như các hàm liên tục nhưng không khả vi ở bất kỳ điểm nào. Các quan niệm trước đây về hàm như là một quy tắc tính toán hoặc một đồ thị trơn không còn là đầy đủ nữa. Weierstrass tán thành chủ trương số học hóa giải tích, trong đó các tiên đề của giải tích sẽ được thiết lập dựa vào các số tự nhiên.Từ tận năm 1817, Bolzano đã đưa ra định nghĩa (ε, δ) của giới hạn và hàm liên tục, nhưng hầu như không được chú ý. Cauchy định nghĩa tính liên tục bằng infinitesimal năm 1821 (xem trang 34 cuốn Cours d'Analyse). Năm 1858, Richard Dedekind đề xuất một định nghĩa cho số thực bằng lát cắt Dedekind. Định nghĩa này hiện vẫn được sử dụng.

=== Thế kỷ 20 ===
Các lĩnh vực nghiên cứu chính đầu thế kỷ 20 là lý thuyết tập hợp và logic hình thức. Sau khi phát hiện các nghịch lý trong lý thuyết tập hợp không hình thức (informal set theory), một số người nghi vấn liệu bản thân toán học có tự mâu thuẫn hay không, và tìm cách chứng minh khả năng này không xảy ra.

Năm 1900, Hilbert liệt kê 23 vấn đề cho thế kỷ tới. Hai bài toán đầu tiên là giải quyết Giả thuyết continuum và chứng minh sự phi mâu thuẫn của số học sơ cấp. Các công trình nhằm giải quyết các bài toán này và Entscheindungsproblem của Hilbert đã định hình hướng phát triển logic toán học.

==== Khởi đầu của các nhánh khác ====
Alfred Tarski đã phát triển các điểm cơ bản của lý thuyết mô hình.

Từ năm 1935, một nhóm các nhà toán học nổi tiếng đã cộng tác dưới bí danh Nicolas Bourbaki và xuất bản một chuỗi bách khoa toàn thư cho toán học tên là "Éléments de mathématique". Các công trình này nhấn mạnh vào nền tảng lý thuyết tập hợp và sự chặt chẽ trong trình bày, diễn giải bằng văn phong khắc khổ và theo tiên đề. Nhiều thuật ngữ được sáng tạo từ đó, chẳng hạn như song ánh, đơn ánh, toàn ánh, được sử dụng rộng rãi.

Ngành nghiên cứu khả năng tính toán sau này được gọi là lý thuyết đệ quy hay lý thuyết tính toán, bởi vì sự hình thức hóa ban đầu của Gödel và Kleene dựa vào định nghĩa quy nạp của các hàm số. Người ta đã chứng minh những định nghĩa này tương đương với cách hình thức hóa của Turing sử dụng máy Turing, và từ đây họ khám phá ra một khái niệm mới - hàm tính toán được. Định nghĩa này đủ mạnh để được mô tả theo nhiều cách khác nhau. Trong công trình về các định lý bất toàn vào năm 1931, Gödel đã thiếu một khái niệm chính xác về một hệ thống hình thức đủ hiệu quả. Ông ngay lập tức nhận ra những định nghĩa mới của sự tính toán được có thể được sử dụng cho mục đích này, cho phép ông phát biểu các định lý bất toàn phổ quát hơn những gì có trong bài báo ban đầu.

Vào những năm 1940, nhiều kết quả trong lý thuyết tính toán được Stephen Cole Kleene và Emil Leon Post chứng minh. Kleene đưa ra những khái niệm về sự tính toán được tương đối, như được tiên đoán bởi Turing, và thứ bậc số học. Kleene và Georg Kreisel đã nghiên cứu những phiên bản hình thức thức của toán học trực giác, đặc biệt là trong ngữ cảnh lý thuyết chứng minh.

== Các hệ thống logic hình thức ==
Về cơ bản, logic toán làm việc với các khái niệm toán học được biểu diễn qua các hệ thống logic hình thức. Tuy các hệ thống này có nhiều chi tiết khác biệt, chúng đều chỉ xem xét các biểu thức bằng một ngôn ngữ hình thức cố định. Ngày nay các hệ thống logic được nghiên cứu nhiều nhất gồm logic mệnh đề và logic bậc nhất do chúng có thể được ứng dụng vào cơ sở toán học và các tính chất đáng muốn thuộc về lý thuyết chứng minh.

Các loại logic cổ điển mạnh hơn, chẳng hạn như logic bậc hai hay logic vô hạn (infinitary) hiện vẫn được nghiên cứu, cùng với Logic không cổ điển, chẳng hạn như logic trực giác.

== Lý thuyết tập hợp ==
Lý thuyết tập hợp là ngành nghiên cứu các tập hợp - các bộ trừu tượng gồm các đối tượng (vật thể, đối tượng toán học...). Nhiều khái niệm cơ bản như số thứ tự và số đếm được phát triển bởi Cantor trước khi các hệ thống tiên đề hình thức của ngành này thành hình. Cách lập tiên đề đầu tiên của Zermelo về sau được mở rộng thành Lý thuyết tập hợp Zermelo-Fraenkel (ZF) - lý thuyết thường được sử dụng nhất làm cơ sở toán học.

Hai mệnh đề nổi tiếng trong lý thuyết tập hợp là Tiên đề chọn và Giả thuyết continuum. Tiên đề chọn, được phát biểu lần đầu bởi Zermelo, được Fraenkel chứng minh là độc lập với ZF, nhưng hiện được đông đảo các nhà toán học chấp nhận. Phát biểu của tiên đề chọn là với một họ các tập hợp không rỗng bất kỳ, có đúng một tập hợp C chứa đúng một phần tử từ mỗi tập hợp trong họ. Ta gọi tập C là "chọn" một phần tử từ mỗi tập trong họ. Dù một số người cho rằng hành động chọn này là hợp lý, vì các tập hợp đều không rỗng, tiên đề này không kiến thiết (non constructive) do thiếu các quy luật tường minh cho quy trình chọn. Tiên đề này có nhiều hệ quả phản trực giác, chẳng hạn như nghịch lý Banach-Tarski.

Giả thuyết continuum, lần đầu tiên được Cantor đề ra, là một trong 23 vấn đề David Hilbert đưa ra năm 1900. Gödel chứng minh rằng giả thuyết này không thể bị chứng minh là sai trong hệ tiên đề Zermelo-Fraenkel của lý thuyết tập hợp (dù có hay không có tiên đề chọn). Năm 1963, Paul Cohen chỉ ra rằng giả thuyết này không thể được chứng minh bằng các tiên đề của hệ tiên đề Zermelo-Fraenkel. Kết quả về sự độc lập này chưa hoàn toàn giải quyết vấn đề Hilbert đặt ra, do có thể có một hệ tiên đề khác có thể giải quyết giả thuyết này.

== Lý thuyết mô hình ==
Lý thuyết mô hình nghiên cứu các mô hình của một số lý thuyết hình thức. Ở đây lý thuyết được hiểu là một tập hợp các công thức dưới một logic hình thức và các ký hiệu không mang nghĩa logic (signature) nhất định, còn một mô hình là một cấu trúc có thể diễn giải tường minh lý thuyết đó. Lý thuyết mô hình liên quan chặt chẽ với đại số phổ dụng và hình học đại số, dù các phương pháp của ngành này nặng về các cân nhắc logic hơn hai ngành kia.

== Lý thuyết tính toán ==
Lý thuyết tính toán nghiên cứu những tính chất của những hàm tính toán được và độ Turing (một khái niệm để phân loại các mức độ không tính toán được của các hàm). Lý thuyết này bao gồm cả việc nghiên cứu sự tính toán được và sự định nghĩa được tổng quát. Nó phát triển từ công trình của Rózsa Péter, Alonzo Church và Alan Turing vào những năm 1930. Những công trình này sau đó đã được mở rộng đáng kể bởi Kleene và Post vào những năm 1940.

=== Các bài toán không giải được bằng thuật toán ===
Một nhánh quan trọng của lý thuyết tính toán nghiên cứu về tính không thể giải được bằng thuật toán; một bài toán quyết định hay bài toán hàm số được gọi là không thể giải được bằng thuật toán nếu như không tồn tại thuật toán tính toán được nào đưa ra được câu trả lời chính xác với mọi đầu vào hợp lệ của bài toán đó. Kết quả đầu tiên về tính không giải được, được Church và Turing độc lập chỉ ra vào năm 1936, nói rằng Entscheidungsproblem là một bài toán không thể giải được bằng thuật toán. Turing chứng minh điều này bằng cách chỉ ra tính không giải được của bài toán dừng, một kết quả với nhiều hệ quả trong cả lý thuyết tính toán và khoa học máy tính.

== Lý thuyết chứng minh và toán học kiến thiết ==
Lý thuyết chứng minh là ngành nghiên cứu những chứng minh hình thức trong nhiều hệ thống logic diễn dịch khác nhau. Những chứng minh này được coi như là các đối tượng toán học, từ đây chúng được phân tích bởi các kĩ thuật toán học. Các hệ thống diễn dịch được xét đến có thể bao gồm các hệ thống diễn dịch kiểu Hilbert, các hệ thống diễn dịch tự nhiên, và phép tính tuần tự phát triển bởi Gentzen.

Việc nghiên cứu toán học kiến thiết, trong ngữ cảnh logic toán, bao gồm việc nghiên cứu các hệ thống logic không cổ điển như logic trực giác và các hệ thống không tự quy chiếu. Herman Weyl là một người đã đưa ra chủ nghĩa không tự quy chiếu. Ông đã cho thấy ta có thể phát triển một phần lớn của giải tích thực chỉ bằng các phương pháp không tự quy chiếu.

== Ứng dụng ==
Logic toán đã không chỉ được ứng dụng thành công vào toán học và cơ sở của nó, mà còn vào cả vật lý, sinh học, tâm lý học, pháp luật và đạo đức học, cho tới kinh tế học, các câu hỏi thực tế, và kể cả siêu hình học. Đã có cả những ứng dụng ngành này vào thần học.

== Quan hệ với khoa học máy tính ==
Việc nghiên cứu lý thuyết tính toán trong khoa học máy tính có sự liên hệ gần gũi với việc nghiên cứu khả năng tính toán trong logic toán. Tuy nhiên, điểm quan trọng của hai việc này khác nhau. Các nhà khoa học máy tính thường tập trung vào các ngôn ngữ lập trình và khả năng tính toán trong thực tiễn, trong khi các nhà nghiên cứu logic toán thường tập trung vào mặt lý thuyết thuần túy của khả năng tính toán và sự không thể tính toán hơn.

== Cơ sở toán học ==
Từ thế kỉ 19 các nhà toán học sớm đã nhận ra các khoảng trống logic và sự mẫu thuẫn trong các lĩnh vực toán học như hình học hay giải tích. Công việc nghiên cứu các tập hợp vô hạn của Cantor cũng vướng phải nhiều sự chỉ trích. trong khi Leopold Kronecker cùng những người theo chủ nghĩa kiến thiết vào thế kỉ 20 phản đối công trình của Cantor, David Hilbert lại đồng thuận với việc nghiên cứu sự vô hạn.Các nhà toán học bắt đầu tìm kiếm các hệ thống tiên đề để hình thức hóa những phần rộng lớn của toán học, với hi vọng rằng việc tiên đề hóa toán học sẽ cho phép khả năng chứng minh sự phi mâu thuẫn. Vào thế kỉ 19, phương pháp chính để chứng minh sự phi mâu thuẫn của một hệ tiên đề là cung cấp một mô hình cho hệ tiên đề đó.

Khi logic hình thức phát triển, Hilbert đặt câu hỏi liệu có thể hay không việc chứng minh một hệ tiên đề là phi mâu thuẫn bằng cách phân tích cấu trúc của các chứng minh khả dĩ trong hệ đó, và qua phân tích đó chỉ ra không thể rút ra mâu thuẫn. Ý tưởng này dẫn đến việc nghiên cứu lý thuyết chứng minh, Hơn nữa, Hilbert đề xuất rằng phân tích ấy nên rời rạc. Ông sử dụng thuật ngữ "hữu hạn" (finitary) để nói đến phương pháp ông cho phép dù không định nghĩa nó một cách chính xác.

Trong lịch sử phát triển cơ sở toán học còn có sự xuất hiện của các loại logic không cổ điển và toán học kiến thiết. Ngành thứ hai có nhiều chương trình với những định nghĩa "kiến thiết" khác nhau. Ở mức độ dễ tính nhất, nhiều nhà toán học coi các chứng minh trong lý thuyết tập hợp ZF không sử dụng tiên đề chọn là có tính kiến thiết. Các định nghĩa giới hạn hơn chỉ cho phép làm việc với các số tự nhiên, các hàm số học, và tập hợp các số tự nhiên (thứ cho phép biểu diễn số thực và tạo điều kiện để thiết lập bộ môn giải tích). Thông thường, trước khi một hàm số được coi là tồn tại, phải có một cách tính tường minh các giá trị của hàm số đó.

Đầu thế kỷ 20, Luitzen Egbertus Jan Brouwer đã thành lập trường phái trực giác như là một phần của triết học toán học. Trường phái này phát biểu rằng để một mệnh đề toán học là đúng với một nhà toán học, người này phải hình dung được mệnh đề đó, để không chỉ tin vào sự đúng đắn của nó mà còn hiểu lý do cho điều đó. Một hệ quả của định nghĩa này là sự loại bỏ luật bài trung, bởi vì theo Brouwer, có những mệnh đề không thể được coi là đúng khi phủ định của chúng cũng vậy. Triết lý ảnh hưởng sâu rộng này là nguyên nhân của những tranh cãi nảy lửa giữa những nhà toán học nổi tiếng. Về sau, Kleene và Kresei nghiên cứu các phiên bản hình thức của logic trực giác (Brouwer từ chối sự hình thức hóa, và viết công trình của mình bằng ngôn ngữ tự nhiên không hình thức hóa). Nhờ sự phát triển của diễn giải BHK và các mô hình Kripke, trường phái trực giác có thể được hòa hợp dễ dàng hơn với toán học cổ điển.