Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. Mời bạn giúp hoàn thiện bài viết này bằng cách bổ sung chú thích tới các nguồn đáng tin cậy. Các nội dung không có nguồn có thể bị nghi ngờ và xóa bỏ.

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[sửa | sửa mã nguồn]

Năm 1977, cuốn Handbook of Mathematical Logic^[1]  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.

Cơ sở toán học[sửa | sửa mã nguồn]

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.

Các hệ thống logic hình thức[sửa | sửa mã nguồn]

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[sửa | sửa mã nguồn]

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^[2] 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^[3], được Fraenkel chứng minh^[4] 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[sửa | sửa mã nguồn]

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[sửa | sửa mã nguồ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^[5].

Các bài toán không giải được bằng thuật toán[sửa | sửa mã nguồ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[sửa | sửa mã nguồn]

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[sửa | sửa mã nguồn]

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[sửa | sửa mã nguồn]

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.

Tham khảo[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]

Bài viết liên quan đến toán học này vẫn còn sơ khai. Bạn có thể giúp Wikipedia mở rộng nội dung để bài được hoàn chỉnh hơn. x t s