Lý thuyết hình thái

Trong toán học, logic và khoa học máy tính, một lý thuyết hình thái hoặc một hệ hình thái là một hệ thống hình thức trong đó mọi đối tượng đều có một hình thái (hay mọi "biến" đều có một "kiểu", mọi "từ" đều có một "loại"...). Hình thái của một đối tượng hạn chế các "tác động" (hay "phép toán", "cách dùng") có thể được thực hiện trên đối tượng (hay "biến", "từ") ấy. Ngành nghiên cứu các hệ hình thái cũng được gọi là Lý thuyết Hình Thái.
Một số lý thuyết hình thái có thể đóng vai trò thay thế lý thuyết tập hợp để làm nền tảng cho toán học. Hai lý thuyết như vậy khá nổi tiếng là lý thuyết phép tính lambda hình thái của Alonzo và lý thuyết hình thái trực giác của Per Martin-Löf.
Giống như các lý thuyết tập hợp tiên đề, lý thuyết hình thái được tạo ra để tránh những nghịch lý trong các nền tảng trước đây của toán học như lý thuyết tập hợp ngây thơ, logic hình thức.
Lý thuyết hình thái có quan hệ chặt chẽ với, và đôi khi trùng lặp với, hệ thống kiểu trong khoa học máy tính.
Lịch sử.
Trong khoảng thời gian từ năm 1902 đến năm 1908, Bertrand Russell đã đề xuất nhiều "lý thuyết hình thái" khác nhau để giải quyết vấn đề mà chính ông trước đó khám phá ra: rằng phiên bản lý thuyết tập ngây thơ của Gottlob Frege bị ảnh hưởng bởi nghịch lý Russell.
Các khái niệm cơ bản.
Trong phần tiếp theo, "từ" và "đối tượng" mang cùng một nghĩa; "loại" và "hình thái" mang cùng một nghĩa.
Trong một hệ hình thái, mỗi từ có một loại. Ví dụ, formula_1, formula_2 và formula_3 là các từ phân biệt đều có loại formula_4 của các số tự nhiên. Theo truyền thống, loại của từ được viết sau dấu hai chấm, chẳng hạn như formula_5 nghĩa là số formula_6 có loại formula_4.
Các hệ hình thái có các phép tính tường minh được thể hiện qua các luật viết lại. Các luật viết lại này được gọi là quy tắc chuyển đổi hoặc, nếu luật chỉ hoạt động theo một chiều, quy tắc rút gọn. Ví dụ, formula_8 và formula_1 là những từ khác nhau về mặt cú pháp, nhưng từ đầu tiên có thể được rút gọn thành từ thứ hai. Phép rút gọn này được viết là formula_10.
Các hàm trong hệ hình thái có một quy tắc rút gọn đặc biệt: một biến xuất hiện trong định nghĩa hàm sẽ được thay thế bởi đối số tương ứng. Giả sử hàm formula_11 được định nghĩa là formula_12. Phép gọi hàm formula_13 sẽ được rút gọn bằng cách thay thế formula_6 cho mọi formula_15 trong định nghĩa hàm. Như vậy ta có phép rút gọn formula_16.
Loại hàm được ký hiệu bằng một mũi tên formula_17 từ loại tham số đến loại trả về của hàm. Như vậy, ta viết formula_18 (tức là, formula_11 là một "từ", "loại" của nó là formula_20, tức là nó là một hàm lấy vào một từ của loại các số tự nhiên, và cho ra một từ của loại các số tự nhiên).
Khác biệt với lý thuyết tập hợp.
Có nhiều lý thuyết tập hợp khác nhau và nhiều hệ thống khác nhau của lý thuyết hình thái. Tuy nhiên, ta có thể nêu ra một số nhận xét chung.
Tính chất khác.
Chuẩn hóa.
Từ formula_21 được rút gọn về formula_22. Từ formula_22 không thể được rút gọn hơn nữa, nó được gọi là một dạng chuẩn. Một hệ hình thái được gọi là "chuẩn hóa mạnh" nếu tất cả các từ đều có dạng chuẩn và bất kỳ một dãy các phép rút gọn nào đều sẽ dẫn đến dạng chuẩn. Các hệ "chuẩn hóa yếu" là các hệ có dạng chuẩn, tuy nhiên các phép rút gọn có thể tạo thành vòng lặp và không dẫn đến dạng chuẩn.
Đối với một hệ chuẩn hóa, một phần tử là một lớp các từ có cùng một dạng chuẩn hóa. Một từ đóng là một từ không có tham số. (Một từ như formula_24 với tham số formula_15 được gọi là một từ mở.) Như vậy, formula_21 và formula_27 là hai từ khác nhau của phần tử formula_22.
Các loại phụ thuộc.
Một loại phụ thuộc là một loại mà phụ thuộc vào một từ hoặc loại khác. Ví dụ, loại trả về của một hàm có thể phụ thuộc vào đối số đưa vào hàm.
Ví dụ, một danh sách formula_4 s có độ dài 4 có thể có loại khác với một danh sách formula_4 s có độ dài 5.
Các loại đẳng thức.
Nhiều hệ hình thái có một loại đại diện cho "sự bằng nhau" của các loại và các từ. Loại này khác với quy tắc chuyển đổi, và được gọi là "đẳng thức mệnh đề".
Trong lý thuyết hình thái trực giác, loại đẳng thức được gọi là formula_31. Có một loại formula_32 với formula_33 là một loại và formula_34, formula_35 là các từ có loại formula_33. Một từ của loại formula_32 là một đẳng thức "formula_34 bằng formula_35".
Trong thực tế, có thể xây dựng một loại formula_40 nhưng loại đó sẽ không có từ nào cả (vì formula_22 khác formula_1). Trong lý thuyết loại trực giác, ta xây dựng các từ đẳng thức bắt đầu từ các đẳng thức đồng nhất. Nếu formula_22 là một từ loại formula_4, tồn tại một từ với loại formula_45. Các đẳng thức phức tạp hơn có thể được tạo ra bằng cách tạo ra một từ đồng nhất rồi thực hiện rút gọn một bên. Ví dụ, nếu formula_46 là một từ loại formula_4, ta có một đẳng thức đồng nhất formula_48, và bằng cách rút gọn, ta có một từ mới loại formula_49. Do đó, trong hệ này, loại đẳng thức thể hiện rằng hai giá trị cùng loại có thể được chuyển đổi bằng phép rút gọn.