Quan hệ lập tốt

Quan hệ hai ngôi
Đối xứng Phản đối xứng Toàn phần Lập tốt Có nối Có gặp Quan hệ tương đương ✓ ✗ ✗ ✗ ✗ ✗ Tiền thứ tự (giả thứ tự) ✗ ✗ ✗ ✗ ✗ ✗ Thứ tự riêng phần ✗ ✓ ✗ ✗ ✗ ✗ Tiền thứ tự toàn phần ✗ ✗ ✓ ✗ ✗ ✗ Thứ tự toàn phần ✗ ✓ ✓ ✗ ✗ ✗ Tiền thứ tự tốt ✗ ✗ ✓ ✓ ✗ ✗ Giả thứ tự tốt ✗ ✗ ✗ ✓ ✗ ✗ Thứ tự tốt ✗ ✓ ✓ ✓ ✗ ✗ Dàn ✗ ✓ ✗ ✗ ✓ ✓ Nửa dàn có nối ✗ ✓ ✗ ✗ ✓ ✗ Nửa dàn có gặp ✗ ✓ ✗ ✗ ✗ ✓
Dấu "✓" chỉ tính chất trong cột đó cần phải có trong định nghĩa của hàng đó. Ví dụ, định nghĩa của quan hệ tương đương buộc nó phải có tính đối xứng. Tất cả định nghĩa đều yêu cầu tính bắc cầu và tính phản xạ.

Trong toán học, một quan hệ hai ngôi R trên một lớp X được gọi là quan hệ lập tốt (tiếng Anh: well-founded relation; tiếng Trung: 良基关系 (âm Hán Việt: lương cơ quan hệ)) nếu mọi tập con không rỗng S ⊆ X có một phần tử tối tiểu đối với R, tức là, một phần tử m sao cho với mọi s ∈ S, không thể có sRm ("s không nhỏ hơn m"). Nói cách khác, một quan hệ là lập tốt nếu

$(\forall S\subseteq X)\;[S\neq \emptyset \implies (\exists m\in S)(\forall s\in S)\lnot (sRm)].$

Trong lý thuyết thứ tự, một thứ tự riêng phần là lập tốt nếu thứ tự ngặt tương ứng là một quan hệ lập tốt. Nếu thứ tự là toàn phần và lập tốt, thì nó là một thứ tự tốt.

Quy nạp Noether

Đối với các quan hệ lập tốt, một phiên bản của quy nạp siêu hạn có thể được sử dụng: giả sử (X, R) là một quan hệ lập tốt, P(x) là một thuộc tính cho các phần tử của X, và ta muốn chứng minh rằng:

P(x) đúng với mọi x thuộc X,

Thế thì ta chỉ cần chứng minh rằng:

Nếu x thuộc X và P(y) đúng với mọi y sao cho y R x, thì P(x) đúng.

Nói cách khác,

$(\forall x\in X)\;[(\forall y\in X)\;[yRx\implies P(y)]\implies P(x)]\quad {\text{suy ra}}\quad (\forall x\in X)\,P(x).$

Quy nạp đối với một quan hệ lập tốt đôi khi được gọi là quy nạp Noether, theo tên nhà toán học Emmy Noether.

Ví dụ

Các quan hệ thứ tự riêng phần sau là lập tốt:

• các số dương {1, 2, 3,...}, cùng với quan hệ chia hết.
• tập hợp N × N các cặp số dương với quan hệ (n₁, n₂) < (m₁, m₂) khi và chỉ khi n₁ < m₁ and n₂ < m₂.
• một lớp các tập hợp cùng với quan hệ $\in$ ("thuộc"). Đây là hệ quả của tiên đề chính tắc.

Các quan hệ sau là không lập tốt:

• các số nguyên âm {−1, −2, −3, …}, cùng với quan hệ thứ tự thông thường.

Thư mục

• Just, Winfried and Weese, Martin (1998) Discovering Modern Set Theory. I, American Mathematical Society ISBN 0-8218-0266-6.
• Karel Hrbáček & Thomas Jech (1999) Introduction to Set Theory, 3rd edition, "Well-founded relations", trang 251–5, Marcel Dekker ISBN 0-8247-7915-0