Danh sách lý thuyết bậc I

Sơ bộ

Đối với mỗi cấu trúc toán học tự nhiên có chữ ký σ liệt kê các hằng số, hàm và quan hệ của lý thuyết cùng với các giá trị của chúng, sao cho đối tượng đó là một cấu trúc tự nhiên. Đưa ra một chữ ký σ có một ngôn ngữ thứ tự đầu tiên duy nhất Lσ có thể được sử dụng để nắm bắt các sự kiện thể hiện thứ tự đầu tiên về cấu trúc σ.

Có hai cách phổ biến để xác định các lý thuyết:

• Liệt kê hoặc mô tả một tập các câu trong ngôn ngữ Lσ, được gọi là tiên đề của lý thuyết.

• Đưa ra một tập hợp các cấu trúc, và xác định một lý thuyết là tập hợp các câu trong Lσ đang nắm giữ trong tất cả các mô hình này. Ví dụ, "lý thuyết của các trường hữu hạn" bao gồm tất cả các câu trong ngôn ngữ của các trường đúng trong tất cả các trường hữu hạn.

Một lý thuyết Lσ có thể:

• nhất quán: không có bằng chứng mâu thuẫn nào tồn tại;

• được thỏa mãn: có tồn tại một cấu trúc for mà các câu của lý thuyết đều đúng (theo định lý đầy đủ, sự thỏa mãn tương đương với tính thống nhất);

• được hoàn thành: đối với bất kỳ tuyên bố nào, hoặc nó hoặc từ chối của nó là có thể chứng minh được;

• loại bỏ định lượng;

• loại bỏ trí tưởng tượng;

• có khả năng siêu âm;

• có thể giải mã được: Có một thuật toán để quyết định câu nào có thể được chứng minh;

• được đệ quy axiomatizable;

• hoàn thành mô hình hoàn chỉnh hoặc mô hình phụ;

• κ-categorical: Tất cả các mô hình của cardinality κ là đẳng cấu;

• ổn định hoặc không ổn định;

• là ω-ổn định (giống như hoàn toàn siêu việt đối với các lý thuyết có thể đếm được);

• siêu ổn định

• có một mô hình nguyên tử;

• có một mô hình chính;

• có một mô hình bão hòa.

Lý thuyết nhận dạng thuần túy

Chữ ký của lý thuyết nhận dạng thuần túy trống rỗng, không có hàm, hằng số hoặc quan hệ.

Lý thuyết nhận dạng thuần túy không có tiên đề (phi logic). Nó là decidable.

Một trong số ít thuộc tính thú vị có thể được nói trong ngôn ngữ của lý thuyết nhận dạng thuần túy là của vô hạn. Điều này được đưa ra bởi một tập các tiên đề vô hạn cho biết có ít nhất 2 phần tử, có ít nhất 3 phần tử, v.v.

• ∃x1 ∃x2 ¬x1 = x2, ∃x1 ∃x2 ∃x3 ¬x1 = x2 ∧ ¬x1 = x3 ∧ ¬x2 = x3,...

Những tiên đề này định nghĩa lý thuyết của một tập vô hạn.

Tài sản trái ngược của hữu hạn không thể được nêu trong logic bậc 1 cho bất kỳ lý thuyết nào có các mô hình hữu hạn lớn tùy ý: trên thực tế, bất kỳ lý thuyết nào cũng có các mô hình vô hạn theo định lý compactness. Nói chung, nếu một thuộc tính có thể được biểu diễn bằng một số hữu hạn các câu của lôgic bậc 1 thì thuộc tính ngược lại cũng có thể được nêu trong logic bậc 1, nhưng nếu một thuộc tính cần một số câu vô hạn thì thuộc tính đối nghịch của nó không thể được nói trong logic bậc 1.

Bất kỳ tuyên bố nào về lý thuyết nhận dạng thuần túy đều tương đương với σ (N) hoặc ¬σ (N) đối với một số tập con hữu hạn N của các số nguyên không âm, trong đó σ (N) là câu cho biết số phần tử là N. Thậm chí có thể mô tả tất cả các lý thuyết có thể có trong ngôn ngữ này như sau. Bất kỳ lý thuyết nào là lý thuyết của tất cả các tập hợp của số hạng trong N đối với một số tập con hữu hạn N của các số nguyên không âm, hoặc lý thuyết của tất cả các bộ có số hạng không phải là N, đối với một số tập con hữu hạn hoặc vô hạn N số nguyên. (Không có giả thuyết nào có mô hình chính xác là tập hợp N số N nếu N là một tập con vô hạn của các số nguyên.) Các lý thuyết hoàn chỉnh là các lý thuyết về tập hợp của n số n cho một số hữu hạn n, và lý thuyết của các tập vô hạn.

Một trường hợp đặc biệt của điều này là lý thuyết không nhất quán được xác định bởi tiên đề ∃x ¬x = x. Nó là một lý thuyết hoàn hảo tốt với nhiều tính chất tốt: nó là hoàn chỉnh, decidable, finiely axiomatizable, và như vậy. Vấn đề duy nhất là nó không có mô hình nào cả. Theo định lý đầy đủ của Gödel, đó là lý thuyết duy nhất (cho bất kỳ ngôn ngữ nào) không có mô hình. [1] Nó không giống như lý thuyết của tập rỗng (trong các phiên bản của logic bậc nhất cho phép một mô hình trống): lý thuyết của tập rỗng có chính xác một mô hình, mà không có yếu tố nào.

Quan hệ đơn nhất

Một tập hợp các quan hệ đơn nhất Pi cho i trong một số bộ tôi được gọi là độc lập nếu cho mỗi hai tập con hữu hạn rời rạc A và B của tôi có một số phần tử x sao cho Pi (x) là đúng cho i trong A và sai cho i trong B Độc lập có thể được thể hiện bằng một tập hợp các lệnh đầu tiên.

Lý thuyết về số lượng quan hệ đơn nhất có thể đếm được hoàn tất, nhưng không có mô hình nguyên tử. Nó cũng là một ví dụ về một lý thuyết siêu ổn định nhưng không hoàn toàn siêu việt.

Quan hệ tương đương [chỉnh sửa nguồn]

Chữ ký của các mối quan hệ tương đương có một biểu tượng quan hệ nhị phân nhị phân ~, không có hằng số và không có hàm nào. Quan hệ tương đương thỏa mãn các tiên đề:

• Độ phản xạ ∀x x ~ x;

• Đối xứng ∀x ∀y x ~ y → y ~ x;

• Độ nhạy: ∀x ∀y ∀z (x ~ y ∧ y ~ z) → x ~ z.

Một số thuộc tính thứ tự đầu tiên của quan hệ tương đương là:

• ~ có vô số các lớp tương đương;

• ~ có chính xác n lớp tương đương (đối với bất kỳ số nguyên dương cố định nào n);

• Tất cả các lớp tương đương là vô hạn;

• Tất cả các lớp tương đương có kích thước chính xác n (cho bất kỳ số nguyên dương cố định n).

Lý thuyết của một mối quan hệ tương đương với chính xác 2 lớp tương đương vô hạn là một ví dụ dễ dàng của một lý thuyết mà là ω-phân loại nhưng không phân loại cho bất kỳ hồng y lớn hơn.

Mối quan hệ tương đương ~ không nên nhầm lẫn với biểu tượng nhận dạng '=': nếu x = y thì x ~ y, nhưng ngược lại không nhất thiết phải đúng. Các lý thuyết về mối quan hệ tương đương không phải là tất cả những khó khăn hoặc thú vị, nhưng thường cho các ví dụ dễ dàng hoặc đối sánh với các câu lệnh khác nhau.

Các công trình sau đây đôi khi được sử dụng để tạo ra các ví dụ về lý thuyết với quang phổ nhất định; trong thực tế, bằng cách áp dụng chúng vào một số ít các lý thuyết rõ ràng, T có được các ví dụ về các lý thuyết có thể đếm được hoàn toàn với tất cả các phổ không đếm được. Nếu T là một lý thuyết trong một số ngôn ngữ, chúng ta định nghĩa một lý thuyết 2T mới bằng cách thêm một mối quan hệ nhị phân mới vào ngôn ngữ, và thêm tiên đề nói rằng nó là một mối quan hệ tương đương, sao cho có vô số các lớp tương đương Các mô hình của T. Có thể lặp đi lặp lại cấu trúc này: với định nghĩa thứ tự, xác định một lý thuyết mới bằng cách thêm một tương quan Eβ cho mỗi β <α, cùng với tiên đề nói rằng bất cứ khi nào β <γ thì mỗi lớp tương đương E is là sự kết hợp của vô số các lớp tương đương E,, và mỗi lớp E0equivalence là một mô hình T. Không chính thức, ta có thể hình dung các mô hình của lý thuyết này là cây phân nhánh vô hạn có chiều cao α với các mô hình T gắn liền với tất cả các lá.

Lattices

Lattices có thể được coi là dạng đặc biệt của các bộ có trật tự một phần, với một chữ ký bao gồm một biểu tượng quan hệ nhị phân ≤ hoặc cấu trúc đại số có chữ ký gồm hai phép toán nhị phân ∧ và ∨. Hai phương pháp tiếp cận có thể liên quan bằng cách xác định a≤ b có nghĩa là a∧b = a.

Đối với hai hoạt động nhị phân, các tiên đề cho một mạng là:

• Luật giao hoán
• Luật liên kết
• Luật hấp thụ

Đối với một mối quan hệ, các tiên đề là:

• Axioms nêu ≤ là một phần đơn đặt hàng, như trên.

• (tồn tại của c = a∧b)

• (tồn tại của c = a∨b)

Các thuộc tính thứ tự đầu tiên bao gồm:

• (lưới phân phối)

• (lưới mô-đun)

Đại số Heyting có thể được định nghĩa là lưới với một số thuộc tính thứ tự đầu tiên.

Tính toàn vẹn không phải là thuộc tính thứ tự đầu tiên của mạng.

Đồ thị [chỉnh sửa nguồn]

Bài chi tiết: Logic của đồ thị

Chữ ký của đồ thị không có hằng số hoặc hàm, và một ký hiệu quan hệ nhị phân R, trong đó R (x, y) được đọc là "có một cạnh từ x đến y".

Các tiên đề cho lý thuyết đồ thị là

• Đối xứng: ∀x ∀y R (x, y) → R (y, x)

• Chống phản xạ: ∀x ¬R (x, x) ("không có vòng lặp")

Lý thuyết đồ thị ngẫu nhiên có các tiên đề phụ sau cho mỗi số nguyên dương n:

• Đối với bất kỳ hai tập hợp hữu hạn nào có kích thước n, có một điểm được nối với tất cả các điểm của tập đầu tiên và không có điểm nào của tập thứ hai. (Đối với mỗi n cố định, thật dễ dàng để viết câu lệnh này bằng ngôn ngữ đồ thị.)

Lý thuyết của các đồ thị ngẫu nhiên là phân loại, đầy đủ, và có thể giải mã được, và mô hình đếm được của nó được gọi là đồ thị Rado. Một tuyên bố trong ngôn ngữ của đồ thị là đúng trong lý thuyết này nếu và chỉ khi xác suất mà một đồ thị ngẫu nhiên n-đỉnh mô hình các tuyên bố có xu hướng 1 trong giới hạn khi n đi đến vô cùng.

Đại số Boolean

Có một số chữ ký và quy ước khác nhau được sử dụng cho đại số Boolean:

1. Chữ ký có 2 hằng số, 0 và 1, và hai hàm nhị phân ∧ và ∨ ("và" và "hoặc") và một hàm unary ¬ ("not"). Điều này có thể gây nhầm lẫn khi các hàm sử dụng các biểu tượng giống như các hàm mệnh đề của logic bậc nhất.

2. Trong lý thuyết tập hợp, một quy ước chung là ngôn ngữ có 2 hằng số, 0 và 1, và hai hàm nhị phân · và +, và một hàm unary -. Ba hàm này có cùng cách giải thích như các hàm trong quy ước đầu tiên. Thật không may, quy ước này gặp sự cố với quy ước tiếp theo:

3. Trong đại số, quy ước thông thường là ngôn ngữ có 2 hằng số, 0 và 1, và hai hàm nhị phân · và +. Hàm · có cùng ý nghĩa như ∧, nhưng a + b có nghĩa là a∨b∧¬ (a∧b). Lý do cho điều này là các tiên đề cho đại số Boolean sau đó chỉ là tiên đề cho một vòng với 1 cộng ∀x x2 = x. Thật không may, điều này đụng độ với quy ước chuẩn trong lý thuyết tập đã nêu ở trên.

Các tiên đề là:

• Các tiên đề cho một mạng lưới phân phối (xem ở trên)

• ∧¬a a∧¬a = 0, ∀a a∨¬a = 1 (thuộc tính phủ định)

• Một số tác giả bổ sung thêm tiên đề ¬0 = 1, để loại trừ đại số tầm thường bằng một phần tử.

Tarski đã chứng minh rằng lý thuyết về đại số Boolean là đáng tin cậy.

Chúng tôi viết x ≤ y là viết tắt của x ∧ y = x và nguyên tử (x) làm chữ viết tắt cho ¬x = 0 ∧ ∀yy≤x → y = 0 ∨ y = x, được đọc là "x là nguyên tử" nói cách khác, một phần tử khác 0 không có gì giữa nó và 0. Đây là một số thuộc tính thứ tự đầu tiên của đại số Boolean:

• Nguyên tử: ∀x x = 0 ∨ ∃y y≤x ∧ nguyên tử (y)

• Không có nguyên tử: ∀x ¬atom (x)

Lý thuyết về đại số Boolean không phân tử là ω-phân loại và đầy đủ.

Đối với bất kỳ đại số Boolean B, có một số bất biến được định nghĩa như sau.

• lý tưởng I (B) bao gồm các nguyên tố là tổng của một nguyên tố nguyên tử và không nguyên tử (một nguyên tố không có nguyên tử bên dưới nó).

• Đại số thương số Bi của B được xác định một cách tự cảm bởi B0 = B, Bk + 1 = Bk / I (Bk).

• M bất biến (B) là số nguyên nhỏ nhất sao cho Bm + 1 là tầm thường, hoặc ∞ nếu không tồn tại số nguyên như vậy.

• Nếu m (B) là hữu hạn, n bất biến (B) là số nguyên tử của Bm (B) nếu số này là hữu hạn, hoặc ∞ nếu số này là vô hạn.

• Bất biến l (B) là 0 nếu Bm (B) là nguyên tử hoặc nếu m (B) là ∞, và 1 nếu không.

Sau đó, hai đại số Boolean tương đương nguyên tố nếu và chỉ khi các bất biến của chúng l, m, và n là như nhau. Nói cách khác, các giá trị của những bất biến này phân loại các sự hoàn thành có thể có của lý thuyết đại số Boolean. Vì vậy, các lý thuyết hoàn chỉnh có thể là:

• Đại số tầm thường (nếu điều này được cho phép, đôi khi 0 ≠ 1 được bao gồm như một tiên đề.)

• Lý thuyết với m = ∞

• Các lý thuyết với m một số tự nhiên, n một số tự nhiên hoặc ∞, và l = 0 hoặc 1 (với l = 0 nếu n = 0).