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^[1], Gerhard Gentzen^[2], 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^[3] tạm chia logic toán đương thời thành bốn lĩnh vực:

lý thuyết tập hợp
lý thuyết mô hình
lý thuyết tính toán
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^[4].

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^[5]. Đâ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ẽ^[6]. 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^[7], 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ỷ^[8]. 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^[9]. 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^[10]. 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^[11] đã 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^[12]. 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^[13], 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^[14].

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^[15] đư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^[16], 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^[17] 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^[18], được Fraenkel chứng minh^[19] 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^[20]. 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^[21].

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.^[22]

Ứ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.

Tham khảo

^ Chẳng hạn: Gödel, Kurt, 1931, “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I,” Monatshefte für Mathematik und Physik, 38: 173–198.
^ G. Gentzen, 1936/1969. Die Widerspruchfreiheit der reinen Zahlentheorie. Mathematische Annalen 112:493–565. Translated as 'The consistency of arithmetic', in The collected papers of Gerhard Gentzen, M. E. Szabo (ed.), 1969.
^ Barwise, Jon; Keisler, H. Jerome (1977). Handbook of mathematical logic. Studies in logic and the foundations of mathematics. Amsterdam New York: North-Holland Pub. Co. ISBN 978-0-444-86388-1.
^ Computability Theory and Foundations of Mathematics/ February, 17th-20th, 2014/ Tokyo Institute of Technology, Tokyo, Japan
^ Ferreirós, José (2001). "The Road to Modern Logic-An Interpretation" (PDF), tr. 443, Bulletin of Symbolic Logic. 7 (4): 441–484. doi:10.2307/2687794. hdl:11441/38373. JSTOR 2687794. S2CID 43258676.
^ Bochenski, Jozef Maria, ed. (1959). A Precis of Mathematical Logic. Synthese Library, Vol. 1. Translated by Otto Bird. Dordrecht: Springer. doi:10.1007/978-94-017-0592-9. ISBN 9789048183296.
^ Swineshead, Richard (1498). Calculationes Suiseth Anglici (in Lithuanian). Papie: Per Franciscum Gyrardengum.
^ Boehner, Philotheus (1950). Medieval Logic. Manchester.
^ Dedekind, Richard (1888). Was sind und was sollen die Zahlen?.
^ Katz, Victor J. (1998). A History of Mathematics. Addison–Wesley. ISBN 9780321016188.
^ Hilbert, David (1899). Grundlagen der Geometrie (in German). Leipzig: Teubner.
^ Pasch, Moritz (1882). Vorlesungen über neuere Geometrie.
^ Felscher, Walter (2000). "Bolzano, Cauchy, Epsilon, Delta". The American Mathematical Monthly. 107 (9): 844–862. doi:10.2307/2695743. JSTOR 2695743.
^ Dedekind, Richard (1872). Stetigkeit und irrationale Zahlen (in German).
^ Kleene, Stephen Cole (1943). "Recursive Predicates and Quantifiers". Transactions of the American Mathematical Society. 53 (1): 41–73. doi:10.2307/1990131. JSTOR 1990131.
^ Turing, Alan M. (1939). "Systems of Logic Based on Ordinals". Proceedings of the London Mathematical Society. 45 (2): 161–228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3.
^ Zermelo, E. (tháng 6 năm 1908). “Untersuchungen über die Grundlagen der Mengenlehre. I”. Mathematische Annalen (bằng tiếng Đức). 65 (2): 261–281. doi:10.1007/BF01449999. ISSN 0025-5831.
^ Zermelo, E. (tháng 12 năm 1904). “Beweis, daß jede Menge wohlgeordnet werden kann: Aus einem an Herrn Hilbert gerichteten Briefe”. Mathematische Annalen (bằng tiếng Đức). 59 (4): 514–516. doi:10.1007/BF01445300. ISSN 0025-5831.
^ Schur, Issai; Brauer, Alfred; Rohrbach, Hans (1973), “Neue Begründung der Theorie der Gruppencharaktere”, Gesammelte Abhandlungen, Berlin, Heidelberg: Springer Berlin Heidelberg, tr. 143–169, ISBN 978-3-642-61948-9, truy cập ngày 3 tháng 5 năm 2024
^ Cohen, Paul J. (1966). Set Theory and the Continuum Hypothesis. Menlo Park CA: W. A. Benjamin.
^ Soare, Robert I. (2016), “Defining Computability”, Turing Computability, Berlin, Heidelberg: Springer Berlin Heidelberg, tr. 3–22, ISBN 978-3-642-31932-7, truy cập ngày 3 tháng 5 năm 2024
^ Weyl, Hermann (1918). Das Kontinuum. Kritische Untersuchungen über die Grund lagen der Analysis (in German). Leipzig.

Liên kết ngoài

[1] Chẳng hạn: Gödel, Kurt, 1931, “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I,” Monatshefte für Mathematik und Physik, 38: 173–198.

[2] G. Gentzen, 1936/1969. Die Widerspruchfreiheit der reinen Zahlentheorie. Mathematische Annalen 112:493–565. Translated as 'The consistency of arithmetic', in The collected papers of Gerhard Gentzen, M. E. Szabo (ed.), 1969.

[3] Barwise, Jon; Keisler, H. Jerome (1977). Handbook of mathematical logic. Studies in logic and the foundations of mathematics. Amsterdam New York: North-Holland Pub. Co. ISBN 978-0-444-86388-1.

[4] Computability Theory and Foundations of Mathematics/ February, 17th-20th, 2014/ Tokyo Institute of Technology, Tokyo, Japan

[5] Ferreirós, José (2001). "The Road to Modern Logic-An Interpretation" (PDF), tr. 443, Bulletin of Symbolic Logic. 7 (4): 441–484. doi:10.2307/2687794. hdl:11441/38373. JSTOR 2687794. S2CID 43258676.

[6] Bochenski, Jozef Maria, ed. (1959). A Precis of Mathematical Logic. Synthese Library, Vol. 1. Translated by Otto Bird. Dordrecht: Springer. doi:10.1007/978-94-017-0592-9. ISBN 9789048183296.

[7] Swineshead, Richard (1498). Calculationes Suiseth Anglici (in Lithuanian). Papie: Per Franciscum Gyrardengum.

[8] Boehner, Philotheus (1950). Medieval Logic. Manchester.

[9] Dedekind, Richard (1888). Was sind und was sollen die Zahlen?.

[10] Katz, Victor J. (1998). A History of Mathematics. Addison–Wesley. ISBN 9780321016188.

[11] Hilbert, David (1899). Grundlagen der Geometrie (in German). Leipzig: Teubner.

[12] Pasch, Moritz (1882). Vorlesungen über neuere Geometrie.

[13] Felscher, Walter (2000). "Bolzano, Cauchy, Epsilon, Delta". The American Mathematical Monthly. 107 (9): 844–862. doi:10.2307/2695743. JSTOR 2695743.

[14] Dedekind, Richard (1872). Stetigkeit und irrationale Zahlen (in German).

[15] Kleene, Stephen Cole (1943). "Recursive Predicates and Quantifiers". Transactions of the American Mathematical Society. 53 (1): 41–73. doi:10.2307/1990131. JSTOR 1990131.

[16] Turing, Alan M. (1939). "Systems of Logic Based on Ordinals". Proceedings of the London Mathematical Society. 45 (2): 161–228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3.

[17] Zermelo, E. (tháng 6 năm 1908). “Untersuchungen über die Grundlagen der Mengenlehre. I”. Mathematische Annalen (bằng tiếng Đức). 65 (2): 261–281. doi:10.1007/BF01449999. ISSN 0025-5831.

[18] Zermelo, E. (tháng 12 năm 1904). “Beweis, daß jede Menge wohlgeordnet werden kann: Aus einem an Herrn Hilbert gerichteten Briefe”. Mathematische Annalen (bằng tiếng Đức). 59 (4): 514–516. doi:10.1007/BF01445300. ISSN 0025-5831.

[19] Schur, Issai; Brauer, Alfred; Rohrbach, Hans (1973), “Neue Begründung der Theorie der Gruppencharaktere”, Gesammelte Abhandlungen, Berlin, Heidelberg: Springer Berlin Heidelberg, tr. 143–169, ISBN 978-3-642-61948-9, truy cập ngày 3 tháng 5 năm 2024

[20] Cohen, Paul J. (1966). Set Theory and the Continuum Hypothesis. Menlo Park CA: W. A. Benjamin.

[21] Soare, Robert I. (2016), “Defining Computability”, Turing Computability, Berlin, Heidelberg: Springer Berlin Heidelberg, tr. 3–22, ISBN 978-3-642-31932-7, truy cập ngày 3 tháng 5 năm 2024

[22] Weyl, Hermann (1918). Das Kontinuum. Kritische Untersuchungen über die Grund lagen der Analysis (in German). Leipzig.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

x t s Logic toán
Chung	Ngôn ngữ hình thức Formation rule Hệ hình thức Hệ suy luận Chứng minh hình thức Ngữ nghĩa hình thức (logic) Well-formed formula Tập hợp Phần tử (toán học) Lớp (lý thuyết tập hợp) Classical logic Tiên đề Natural deduction Rule of inference Quan hệ (toán học) Định lý toán học Logical consequence Hệ tiên đề Lý thuyết hình thái Symbol (formal) Syntax (logic) Lý thuyết (logic toán)
Thuật ngữ logic	Mệnh đề toán học Suy luận Luận cứ logic Validity Cogency Tam đoạn luận Square of opposition Sơ đồ Venn
Propositional calculus Đại số Boole	Boolean functions Phép tính mệnh đề Công thức mệnh đề Logical connectives Truth tables
Logic vị từ	Logic bậc nhất Lượng từ (logic) Predicate (mathematical logic) Logic bậc hai Monadic predicate calculus
Naive set theory	Tập hợp Tập hợp rỗng Enumeration Extensionality Tập hợp hữu hạn Tập hợp vô hạn Tập hợp con Tập lũy thừa Tập hợp đếm được Tập hợp không đếm được Recursive set Tập xác định Range (mathematics) Ánh xạ Song ánh Đơn ánh Toàn ánh Hàm số Phép toán hai ngôi Cặp được sắp
Lý thuyết tập hợp	Nền tảng toán học Lý thuyết tập hợp Zermelo–Fraenkel Tiên đề chọn General set theory Lý thuyết tập hợp Kripke–Platek Lý thuyết tập hợp Von Neumann–Bernays–Gödel Lý thuyết tập hợp Morse–Kelley Lý thuyết tập hợp Tarski–Grothendieck Phép đẳng cấu
Lý thuyết mô hình	Cấu trúc (logic toán) Interpretation (logic) Non-standard model Lý thuyết mô hình hữu hạn Giá trị chân lý Validity
Lý thuyết chứng minh	Formal proof Deductive system Hệ hình thức Định lý toán học Hệ quả logic Rule of inference Syntax (logic)
Lý thuyết tính toán	Đệ quy Tập đệ quy Tập tuần tự đệ quy Bài toán quyết định Church–Turing thesis Hàm tính được Primitive recursive function

x t s Toán học
Lịch sử Dòng thời gian Tương lai Đại cương Danh sách Ký hiệu
Nền tảng	Logic toán Lý thuyết hình thái Lý thuyết phạm trù Lý thuyết tập hợp Lý thuyết thông tin Triết học toán học
Đại số	Đa tuyến tính Đồng điều Giao hoán Lý thuyết nhóm Phổ dụng Sơ cấp Trừu tượng Tuyến tính
Giải tích	Giải tích điều hòa Giải tích hàm Giải tích phức Giải tích thực Lý thuyết độ đo Phương trình vi phân Vi tích phân
Rời rạc	Lý thuyết đồ thị Lý thuyết thứ tự Tổ hợp
Hình học	Đại số Euclid Giải tích Hữu hạn Rời rạc Số học Vi phân
Lý thuyết số	Số học Đại số Giải tích Hình học Diophantos
Tô pô	Đại số Hình học Đại cương Vi phân Lý thuyết đồng luân
Ứng dụng	Hóa học Kinh tế Lý thuyết điều khiển tự động Lý thuyết trò chơi Sinh học Tài chính Tâm lý Thống kê toán học Xác suất Thống kê Vật lý
Tính toán	Khoa học máy tính Lý thuyết tính toán Lý thuyết độ phức tạp tính toán Đại số máy tính Giải tích số Tối ưu hóa
Liên quan	Toán học giải trí Toán học và nghệ thuật Giáo dục toán học
Thể loại · Chủ đề · Commons · Dự án

x t s Những lĩnh vực chính của khoa học máy tính
Các nền tảng toán học	Logic toán · Lý thuyết tập hợp · Lý thuyết số · Lý thuyết đồ thị · Lý thuyết kiểu · Lý thuyết thể loại · Giải tích số · Lý thuyết thông tin · Đại số · Nhận dạng mẫu · Nhận dạng tiếng nói · Toán học tổ hợp · Đại số Boole · Toán rời rạc
Lý thuyết phép tính	Độ phức tạp Kolmogorov · Lý thuyết Automat · Lý thuyết tính được · Lý thuyết độ phức tạp tính toán · Lý thuyết điện toán lượng tử
Các cấu trúc dữ liệu và các giải thuật	Phân tích giải thuật · Thiết kế giải thuật · Hình học tính toán · Tối ưu hóa tổ hợp
Các ngôn ngữ lập trình và Các trình biên dịch	Các bộ phân tích cú pháp · Các trình thông dịch · Lập trình cấu trúc · Lập trình thủ tục · Lập trình hướng đối tượng · Lập trình hướng khía cạnh · Lập trình hàm · Lập trình logic · Lập trình máy tính · Lập trình mệnh lệnh · Lập trình song song · Lập trình tương tranh · Các mô hình lập trình · Prolog · Tối ưu hóa trình biên dịch
Tính song hành, Song song, và các hệ thống phân tán	Đa xử lý · Điện toán lưới · Kiểm soát song hành · Hiệu năng hệ thống · Tính toán phân tán
Công nghệ phần mềm	Phân tích yêu cầu · Thiết kế phần mềm · Các phương pháp hình thức · Kiểm thử phần mềm · Quy trình phát triển phần mềm · Các phép đo phần mềm · Đặc tả chương trình · LISP · Mẫu thiết kế · Tối ưu hóa phần mềm
Kiến trúc hệ thống	Kiến trúc máy tính · Tổ chức máy tính · Các hệ điều hành · Các cấu trúc điều khiển · Cấu trúc bộ nhớ lưu trữ · Vi mạch · Thiết kế ASIC · Vi lập trình · Vào/ra dữ liệu · VLSI design · Xử lý tín hiệu số
Viễn thông và Mạng máy tính	Audio máy tính · Chọn tuyến · Cấu trúc liên kết mạng · Mật mã học
Các cơ sở dữ liệu và Các hệ thống thông tin	Hệ quản trị cơ sở dữ liệu · Cơ sở dữ liệu quan hệ · SQL · Các giao dịch · Các chỉ số cơ sở dữ liệu · Khai phá dữ liệu · Biểu diễn và giao diện thông tin · Các hệ thống thông tin · Khôi phục dữ liệu · Lưu trữ thông tin · Lý thuyết thông tin · Mã hóa dữ liệu · Nén dữ liệu · Thu thập thông tin
Trí tuệ nhân tạo	Lập luận tự động · Ngôn ngữ học tính toán · Thị giác máy tính · Tính toán tiến hóa · Các hệ chuyên gia · Học máy · Xử lý ngôn ngữ tự nhiên · Robot học · Biểu diễn tri thức và suy luận
Đồ họa máy tính	Trực quan hóa · Hoạt họa máy tính · Xử lý ảnh
Giao diện người-máy tính	Khả năng truy cập máy tính · Giao diện người dùng · Điện toán mang được · Điện toán khắp mọi nơi · Thực tế ảo
Khoa học tính toán	Cuộc sống nhân tạo · Tin sinh học · Khoa học nhận thức · Hóa học tính toán · Khoa học thần kinh tính toán · Vật Lý học tính toán · Các giải thuật số · Toán học kí hiệu
Chú ý: khoa học máy tính còn có thể được chia thành nhiều chủ đề hay nhiều lĩnh vực khác dựa theo Hệ thống xếp loại điện toán ACM.