Bourbaki

2. Các tập được sắp thứ tự tốt

1. Các đoạn của một tập được sắp thứ tự tốt

Một quan hệ R{x,y}\mathrm{R}\{x, y\} được gọi là một quan hệ sắp thứ tự tốt giữa xx và yy nếu R là một quan hệ thứ tự giữa xx và yy và nếu, với mỗi tập hợp E khác rỗng trên đó R{x,y}\mathrm{R}\{x, y\} cảm sinh một quan hệ thứ tự (nghĩa là sao cho x∈Ex \in \mathrm{E} kéo theo R{x,x}\mathrm{R}\{x, x\}; cf. § 1, no. 1), E, được sắp thứ tự bởi quan hệ này, có một phần tử nhỏ nhất.

¶ Một tập hợp E có thứ tự bởi một phép sắp thứ tự Γ\Gamma được gọi là được sắp tốt nếu quan hệ y∈Γ⟨x⟩y \in \Gamma\langle x\rangle là một quan hệ sắp thứ tự tốt giữa xx và yy; khi đó Γ\Gamma được gọi là một phép sắp thứ tự tốt trên E. Định nghĩa sau tương đương với định nghĩa này:

Định nghĩa 1 03JY

Một tập hợp* E được gọi là được sắp tốt nếu nó có thứ tự và mỗi tập con khác rỗng của E *đều có một phần tử nhỏ nhất.

Một tập hợp được sắp tốt E được sắp thứ tự toàn phần vì mọi tập con {x,y}\{x, y\} của E đều có một phần tử nhỏ nhất. Mọi tập con A của E bị chặn trên trong E đều có một cận trên nhỏ nhất trong E.

Ví dụ

Ví dụ 1 03SX

Cho E={α,β}\mathrm{E} = \{\alpha, \beta\} là một tập hợp có các phần tử phân biệt. Dễ dàng kiểm tra rằng tập con {(α,α),(β,β),(α,β)}\{(\alpha, \alpha), (\beta, \beta), (\alpha, \beta)\} của E×E\mathrm{E} \times \mathrm{E} là đồ thị của một thứ tự tốt trên E.

Ví dụ 2 03SY

Mọi tập con (đặc biệt là tập con rỗng) của một tập được sắp thứ tự tốt đều được sắp tốt theo thứ tự cảm sinh.

Ví dụ 3 03SZ

\* Sự tồn tại của các tập hợp được sắp thứ tự toàn phần nhưng không được sắp thứ tự tốt tương đương với tiên đề vô hạn (§ 4, no. 4, Hệ quả 1 của Mệnh đề 3, và Bài tập 3).

Ví dụ 4 03T0

Nếu Γ\Gamma là một thứ tự tốt trên E, thì thứ tự đối với Γ\Gamma là một thứ tự tốt trên E chỉ khi E hữu hạn (§ 4, Bài tập 3). \

Ví dụ 5 03T1

Cho E là một tập được sắp thứ tự tốt. Tập hợp E1\mathrm{E}_1 nhận được bằng cách thêm vào E một phần tử lớn nhất bb (§ 1, no. 7) được sắp tốt, vì nếu H là một tập con khác rỗng bất kỳ của E1\mathrm{E}_1 khác với {b}\{b\}, thì phần tử nhỏ nhất của H∩E\mathrm{H} \cap \mathrm{E} cũng là phần tử nhỏ nhất của H.

Nhận xét 03JZ

\* Hệ quả của tiên đề vô hạn (§ 6, no. 1) là tồn tại các tập được sắp tốt không có phần tử lớn nhất, chẳng hạn tập hợp N\mathbf{N} các số nguyên tự nhiên. \

Định nghĩa 2 03QN

Trong một tập hợp có thứ tự* E, một tập con của E sao cho các quan hệ x∈Sx \in \mathrm{S}, y∈Ey \in \mathrm{E}, và y⩽xy \leqslant x suy ra y∈Sy \in \mathrm{S} được gọi là một đoạn của E.

Rõ ràng, mọi giao và hợp của các đoạn của E đều là một đoạn của E. Nếu S là một đoạn của E, thì mọi đoạn của S cũng là một đoạn của E. Tập hợp E và tập rỗng đều là các đoạn của E.

Mệnh đề 1 03QO

Trong một tập hợp được sắp tốt* E, mọi đoạn của E khác E chính nó đều là một khoảng ]←,a[]\leftarrow, a[, trong đó a∈Ea \in \mathrm{E}.

Cho S là một đoạn của E sao cho S≠E\mathrm{S} \neq \mathrm{E}. Vì E−S\mathrm{E} - \mathrm{S} không rỗng, nên nó có phần tử nhỏ nhất aa. Theo Định nghĩa 2, quan hệ x⩾ax \geqslant a suy ra x∉Sx \notin \mathrm{S}; nếu không, ta sẽ có a∈Sa \in \mathrm{S}, điều này là vô lý. Do đó E−S\mathrm{E} - \mathrm{S} là khoảng [a,→[[a, \rightarrow[, và S là khoảng ]←,a[]\leftarrow, a[.

¶ Với mọi phần tử xx trong một tập hợp được sắp thứ tự toàn phần E, đoạn ]←,x[]\leftarrow, x[ được gọi là đoạn có đầu mút x, và được ký hiệu bởi Sx\mathrm{S}_x.

Lưu ý rằng nếu E được sắp thứ tự tốt và không rỗng, Sx\mathrm{S}_x có một phần tử nhỏ nhất α\alpha và do đó cũng là khoảng [α,x[[\alpha, x[.

Cho E là một tập sắp thứ tự toàn phần. Hợp A của các Sx\mathrm{S}_x, khi xx chạy qua E, là E nếu E không có phần tử lớn nhất; và nếu E có một phần tử lớn nhất bb, ta có A=E−{b}\mathrm{A} = \mathrm{E} - \{b\}.

Mệnh đề 2 03QP

Tập hợp* E\* các đoạn của một tập hợp được sắp thứ tự tốt E được sắp tốt theo quan hệ bao hàm. Ánh xạ x→Sxx \rightarrow \mathrm{S}_x là một đẳng cấu từ tập hợp được sắp thứ tự tốt E lên tập hợp các đoạn của E khác với chính E *.

Hiển nhiên rằng nếu x∈Ex \in \mathrm{E} và y∈Ey \in \mathrm{E}, quan hệ x⩽yx \leqslant y kéo theo Sx⊂Sy\mathrm{S}_x \subset \mathrm{S}_y, và x<yx < y kéo theo Sx≠Sy\mathrm{S}_x \neq \mathrm{S}_y; do đó ánh xạ x→Sxx \rightarrow \mathrm{S}_x là một đẳng cấu từ E lên tập hợp S(E) các đoạn của E phân biệt với chính E (§ 1, no. 12, Mệnh đề 11), và do đó S(E) được sắp tốt. Hơn nữa, E\* đẳng cấu với tập hợp được sắp thứ tự tốt thu được từ S(E) bằng cách thêm vào một phần tử lớn nhất.

Mệnh đề 3 03QQ

Cho* (Xι)ι∈I(\mathrm{X}_\iota)_{\iota \in \mathbf{I}} là một họ các tập hợp được sắp thứ tự tốt sao cho với mỗi cặp chỉ số (ι,ϰ)(\iota, \varkappa) một trong hai tập hợp Xι\mathrm{X}_\iota, Xϰ\mathrm{X}_\varkappa là một đoạn của tập hợp kia. Khi đó tồn tại duy nhất một thứ tự trên tập hợp E=⋃ι∈IXι\mathrm{E} = \bigcup_{\iota \in \mathbf{I}} \mathrm{X}_\iota cảm sinh thứ tự đã cho trên mỗi tập hợp Xι\mathrm{X}_\iota. Được trang bị thứ tự này, E là một tập được sắp thứ tự tốt. Mọi đoạn của Xι\mathrm{X}_\iota là một đoạn của E; với mỗi x∈Xιx \in \mathrm{X}_\iota, đoạn có điểm cuối là xx trong Xι\mathrm{X}_\iota bằng đoạn có điểm cuối là xx trong E; và mỗi đoạn của E hoặc là chính E hoặc là một đoạn của một trong các Xι\mathrm{X}_\iota.

Mệnh đề đầu tiên là một hệ quả của bổ đề tổng quát sau:

Bổ đề 1 03QR

Cho* (Xα)α∈A(\mathrm{X}_\alpha)_{\alpha \in \mathrm{A}} là một họ các tập hợp có thứ tự, có hướng đối với quan hệ ⊂\subset (nói cách khác, sao cho với mỗi cặp chỉ số α\alpha, β\beta tồn tại một chỉ số γ\gamma sao cho Xα⊂Xγ\mathrm{X}_\alpha \subset \mathrm{X}_\gamma và Xβ⊂Xγ\mathrm{X}_\beta \subset \mathrm{X}_\gamma). Giả sử rằng, với mỗi cặp chỉ số (α,β)(\alpha, \beta) sao cho Xα⊂Xβ\mathrm{X}_\alpha \subset \mathrm{X}_\beta, thứ tự cảm sinh trên Xα\mathrm{X}_\alpha bởi thứ tự của Xβ\mathrm{X}_\beta trùng với thứ tự đã cho trên Xα\mathrm{X}_\alpha. Khi đó tồn tại duy nhất một thứ tự trên tập hợp E=⋃α∈AXα\mathrm{E} = \bigcup_{\alpha \in \mathrm{A}} \mathrm{X}_\alpha cảm sinh thứ tự đã cho trên mỗi Xα\mathrm{X}_\alpha.

Cho Gα\mathrm{G}_\alpha là đồ thị của thứ tự đã cho trên Xα\mathrm{X}_\alpha. Nếu G là đồ thị của một thứ tự trên E cảm sinh trên mỗi Xα\mathrm{X}_\alpha thứ tự có đồ thị là Gα\mathrm{G}_\alpha, thì ta phải có Gα⊂G\mathrm{G}_\alpha \subset \mathrm{G} với mỗi α∈A\alpha \in \mathrm{A}; do đó G chứa ⋃α∈AGα\bigcup_{\alpha \in \mathrm{A}} \mathrm{G}_\alpha. Mặt khác, với mỗi cặp (x,y)(x, y) các phần tử của E, theo giả thiết tồn tại một chỉ số α∈A\alpha \in \mathrm{A} sao cho x∈Xαx \in \mathrm{X}_\alpha và y∈Xαy \in \mathrm{X}_\alpha; nếu (x,y)∈G(x, y) \in \mathrm{G}, ta có (x,y)∈Gα(x, y) \in \mathrm{G}_\alpha, do đó G⊂⋃α∈AGα\mathrm{G} \subset \bigcup_{\alpha \in \mathrm{A}} \mathrm{G}_\alpha. Vậy nếu thứ tự cần tìm trên E tồn tại, đồ thị của nó tất yếu là G=⋃α∈AGα\mathrm{G} = \bigcup_{\alpha \in \mathrm{A}} \mathrm{G}_\alpha. Còn phải chứng minh rằng tập hợp này thỏa mãn các điều kiện của bổ đề. Vì Gβ∩(Xα×Xα)=Gα\mathrm{G}_\beta \cap (\mathrm{X}_\alpha \times \mathrm{X}_\alpha) = \mathrm{G}_\alpha nếu Xα⊂Xβ\mathrm{X}_\alpha \subset \mathrm{X}_\beta, nên ta có G∩(Xα×Xα)=Gα\mathrm{G} \cap (\mathrm{X}_\alpha \times \mathrm{X}_\alpha) = \mathrm{G}_\alpha với mọi α∈A\alpha \in \mathrm{A}; mặt khác, từ giả thiết suy ra ba phần tử bất kỳ xx, yy, zz của E thuộc cùng một Xα\mathrm{X}_\alpha. Do đó (x,y)∈G(x, y) \in \mathrm{G} là một quan hệ thứ tự trên E, và bổ đề được chứng minh.

¶ Bây giờ ta xét chứng minh của Mệnh đề 3. Trước hết, hãy chứng minh rằng mỗi Xι\mathrm{X}_\iota là một đoạn của E. Thật vậy, nếu x∈Xιx \in \mathrm{X}_\iota, y∈Ey \in \mathrm{E} và y⩽xy \leqslant x, thì tồn tại một chỉ số ϰ\varkappa sao cho Xι⊂Xϰ\mathrm{X}_\iota \subset \mathrm{X}_\varkappa và y∈Xϰy \in \mathrm{X}_\varkappa; theo giả thiết Xι\mathrm{X}_\iota là một đoạn của Xϰ\mathrm{X}_\varkappa, nên ta có y∈Xιy \in \mathrm{X}_\iota, điều này chứng minh mệnh đề. Lập luận tương tự chứng minh rằng với mỗi x∈Xιx \in \mathrm{X}_\iota, đoạn có điểm mút xx trong Xι\mathrm{X}_\iota trùng với khoảng ]←,x[]\leftarrow, x[ trong E. Tiếp theo, hãy chứng minh rằng E được sắp tốt. Nếu H là một tập con không rỗng của E, thì tồn tại một chỉ số ι∈I\iota \in \mathrm{I} sao cho H∩Xι≠∅\mathrm{H} \cap \mathrm{X}_\iota \neq \emptyset; nếu aa là phần tử nhỏ nhất của H∩Xι\mathrm{H} \cap \mathrm{X}_\iota trong Xι\mathrm{X}_\iota, thì aa cũng là phần tử nhỏ nhất của H trong E. Nghĩa là, nếu x∈Hx \in \mathrm{H}, thì tồn tại một chỉ số ϰ∈I\varkappa \in \mathrm{I} sao cho Xι⊂Xϰ\mathrm{X}_\iota \subset \mathrm{X}_\varkappa và x∈Xϰx \in \mathrm{X}_\varkappa; ta không thể có x<ax < a, vì khoảng ]←,a[]\leftarrow, a[ được chứa trong Xι\mathrm{X}_\iota, và do đó ta có x⩾ax \geqslant a vì Xϰ\mathrm{X}_\varkappa được sắp thứ tự toàn phần.

¶ Cuối cùng, ta phải chứng minh rằng một đoạn của E, khác với chính E, là một đoạn của một trong các Xι\mathrm{X}_\iota; điều này là một hệ quả ngay lập tức của các lập luận trên, vì một đoạn như vậy có dạng ]←,x[]\leftarrow, x[ (Mệnh đề 1) và vì xx thuộc một Xι\mathrm{X}_\iota nào đó.

2. Nguyên lý quy nạp siêu hạn

Bổ đề 2 03K0

Cho EE là một tập hợp được sắp thứ tự tốt và S\mathfrak{S} là một tập hợp các đoạn của EE có các tính chất sau: (1) hợp của mọi các đoạn thuộc S\mathfrak{S} đều thuộc S\mathfrak{S}; (2) nếu Sx∈SS_x\in\mathfrak{S}, thì Sx∪{x}∈SS_x\cup\{x\}\in\mathfrak{S}. Khi đó mọi đoạn của EE đều thuộc S\mathfrak{S}.

Giả sử rằng có những đoạn của EE không thuộc S\mathfrak{S}, và gọi SS là đoạn nhỏ nhất trong số đó (no. 1, Mệnh đề 2). Nếu SS không có phần tử lớn nhất, thì SS là hợp của các đoạn của SS phân biệt với chính SS, và các đoạn này thuộc S\mathfrak{S} theo định nghĩa của SS; do đó S∈SS\in\mathfrak{S}, điều này vô lý. Ngược lại, nếu SS có phần tử lớn nhất aa, thì S=Sa∪{a}S=S_a\cup\{a\}, và vì SaS_a là một đoạn của SS phân biệt với SS, ta có Sa∈SS_a\in\mathfrak{S}; nhưng khi đó cũng có S∈SS\in\mathfrak{S}, lại là điều vô lý.

¶ Để tiện lợi hơn, ta sẽ đặt mình trong một lý thuyết T\mathscr{T} trong đó EE là một tập hợp được sắp tốt bởi một quan hệ viết dưới dạng x≤yx\leq y. Khi đó ta có các tiêu chuẩn sau:

C59. (Nguyên lý quy nạp siêu hạn). *Cho R{x}R\{x\} là một quan hệ trong T\mathscr{T} (xx không phải là một hằng của T\mathscr{T}) sao cho quan hệ

(x∈E vaˋ (∀y)((y∈E vaˋ y<x)⇒R{y}))⇒R{x} (x\in E\text{ và }(\forall y)((y\in E\text{ và }y<x)\Rightarrow R\{y\}))\Rightarrow R\{x\}

là một định lý trong T\mathscr{T}. Trong những điều kiện này, quan hệ (x∈E)⇒R{x}(x\in E)\Rightarrow R\{x\} là một định lý trong T\mathscr{T}.*

Cho S\mathfrak{S} là tập hợp các đoạn SS của EE sao cho (y∈S)⇒R{y}(y\in S)\Rightarrow R\{y\}. Rõ ràng là mọi hợp của các đoạn thuộc S\mathfrak{S} cũng thuộc S\mathfrak{S}. Mặt khác, nếu Sx∈SS_x\in\mathfrak{S}, theo giả thiết ta có R{x}R\{x\}; do đó (y∈Sx∪{y})⇒R{y}(y\in S_x\cup\{y\})\Rightarrow R\{y\} theo phương pháp phân chia các trường hợp. Vậy (Bổ đề 2) E∈SE\in\mathfrak{S}, điều này chứng minh tiêu chuẩn.

¶ Trong các áp dụng của C59, quan hệ

x∈E vaˋ (∀y)((y∈E vaˋ y<x)⇒R{y}) x\in E\text{ và }(\forall y)((y\in E\text{ và }y<x)\Rightarrow R\{y\})

thường được gọi là “giả thiết quy nạp”.

¶ Trong những điều sau đây, với mọi ánh xạ gg của một đoạn SS của EE vào một tập hợp FF, và với mỗi x∈Sx\in S, ta sẽ ký hiệu g(x)g^{(x)} là ánh xạ của đoạn Sx=]←,x[S_x=]\leftarrow,x[ của EE lên g(Sx)g(S_x) trùng với gg trên SxS_x. Với ký hiệu này, ta có

C60. (Định nghĩa một ánh xạ bằng quy nạp siêu hạn.) Cho uu là một chữ cái, T{u}\mathrm{T}\{u\} là một số hạng trong lý thuyết T\mathscr{T}. Tồn tại một tập hợp UU và một ánh xạ ff của EE lên UU sao cho với mọi x∈Ex\in E ta có f(x)=T{f(x)}f(x)=\mathrm{T}\{f^{(x)}\}. Hơn nữa, tập hợp UU và ánh xạ ff được xác định duy nhất bởi các điều kiện này.

Trước hết hãy chứng minh tính duy nhất. Giả sử rằng f′f' và U′\mathrm{U}' cũng thỏa mãn các điều kiện của tiêu chuẩn. Gọi S\mathfrak{S} là tập hợp các đoạn S của E sao cho ff và f′f' trùng nhau trên S. Hiển nhiên mọi hợp của các đoạn thuộc S\mathfrak{S} cũng thuộc S\mathfrak{S}. Mặt khác, nếu Sx∈S\mathrm{S}_x \in \mathfrak{S}, thì ff và f′f' trùng nhau trên Sx\mathrm{S}_x và do đó f(x)=f′(x)f^{(x)} = {f'}^{(x)}; do đó

f(x)=T{f(x)}=T{f′(x)}=f′(x),f(x) = \mathrm{T}\{f^{(x)}\} = \mathrm{T}\{{f'}^{(x)}\} = f'(x),

điều đó cho thấy rằng Sx∪{x}∈S\mathrm{S}_x \cup \{x\} \in \mathfrak{S}. Suy ra E∈S\mathrm{E} \in \mathfrak{S} (Bổ đề 2), do đó f′=ff' = f và U′=f′(E)=f(E)=U\mathrm{U}' = f'(\mathrm{E}) = f(\mathrm{E}) = \mathrm{U}.

¶ Bây giờ gọi S1\mathfrak{S}_1 là tập hợp các đoạn S của E sao cho tồn tại một tập US\mathrm{U_S} và một ánh xạ fSf_\mathrm{S} của S lên US\mathrm{U_S} sao cho với mọi x∈Sx \in \mathrm{S} ta có fS(x)=T{f(x)}f_\mathrm{S}(x) = \mathrm{T}\{f^{(x)}\}. Với mỗi S∈S1\mathrm{S} \in \mathrm{S}_1, fSf_\mathrm{S} và US\mathrm{U_S} được xác định duy nhất, theo phần đầu của chứng minh; đặc biệt, nếu S′\mathrm{S}' và S′′\mathrm{S}'' là hai đoạn thuộc S1\mathfrak{S}_1 sao cho S′⊂S′′\mathrm{S}' \subset \mathrm{S}'', thì fS′f_{\mathrm{S}'} là ánh xạ của S′\mathrm{S}' lên fS′′(S′)f_{\mathrm{S}''}(\mathrm{S}') trùng với fS′′f_{\mathrm{S}''} trên S′\mathrm{S}'. Từ nhận xét này suy ra rằng mọi hợp của các đoạn thuộc S1\mathfrak{S}_1 cũng thuộc S1\mathfrak{S}_1 (Chương II, § 4, no. 6, Mệnh đề 7). Mặt khác, nếu Sx∈S1\mathrm{S}_x \in \mathfrak{S}_1, ta định nghĩa trên S=Sx∪{x}\mathrm{S} = \mathrm{S}_x \cup \{x\} một hàm fSf_\mathrm{S} kéo dài fSxf_{\mathrm{S}_x} bằng cách đặt

fS(x)=T{fSx}f_\mathrm{S}(x) = \mathrm{T}\{f_{\mathrm{S}_x}\}

(Chương II, § 4, no. 7, Mệnh đề 8); vì fS(x)=fSxf_\mathrm{S}^{(x)} = f_{\mathrm{S}_x}, nên hiển nhiên là Sx∪{x}∈S1\mathrm{S}_x \cup \{x\} \in \mathfrak{S}_1. Do đó (Bổ đề 2) E∈S1\mathrm{E} \in \mathfrak{S}_1, và chứng minh là đầy đủ.

¶ Thông thường tiêu chuẩn này được áp dụng trong những tình huống ở đó tồn tại một tập hợp F sao cho đối với mọi ánh xạ h của một đoạn của E lên một tập con của F ta có T{h}∈F\mathrm{T}\{h\} \in \mathrm{F}. Khi đó tập hợp U thu được bằng cách áp dụng C60 là một tập con của F. Thật vậy, với ký hiệu đã dùng ở trên, gọi S2\mathfrak{S}_2 là tập con của S1\mathfrak{S}_1 gồm các đoạn S của E sao cho US⊂F\mathrm{U_S} \subset \mathrm{F}. Hiển nhiên mọi hợp của các đoạn thuộc S2\mathfrak{S}_2 cũng đều thuộc S2\mathfrak{S}_2; mặt khác, giả thiết về F suy ra rằng nếu Sx∈S2\mathrm{S}_x \in \mathfrak{S}_2, thì ta có Sx∪{x}∈S2\mathrm{S}_x \cup \{x\} \in \mathfrak{S}_2. Mệnh đề bây giờ suy ra từ Bổ đề 2.

3. Định lý zermelo

Bổ đề 3 03K1

Cho* E là một tập hợp, cho S\mathfrak{S} là một tập con của P(E)\mathfrak{P}(\mathrm{E}), và cho pp là một ánh xạ của S\mathfrak{S} vào E sao cho p(X)∉Xp(\mathrm{X}) \notin \mathrm{X} với mọi X∈S\mathrm{X} \in \mathfrak{S}. Khi đó tồn tại một tập con M của E và một thứ tự tốt Γ\Gamma trên M sao cho, nếu x⩽yx \leqslant y ký hiệu quan hệ y∈Γ⟨x⟩y \in \Gamma\langle x \rangle và Sx\mathrm{S}_x ký hiệu đoạn ]←,x]]\leftarrow, x],

(1) với mọi x∈Mx \in \mathrm{M} ta có Sx∈S\mathrm{S}_x \in \mathfrak{S} và p(Sx)=xp(\mathrm{S}_x) = x;

(2) M∉S\mathrm{M} \notin \mathfrak{S}.

Cho M\mathfrak{M} là tập hợp các tập con G của E×E\mathrm{E} \times \mathrm{E} thỏa mãn các điều kiện sau đây :

(a) G là đồ thị của một thứ tự tốt trên pr1G=U\mathrm{pr}_1 \mathrm{G} = \mathrm{U};

(b) nếu x⩽yx \leqslant y ký hiệu quan hệ (x,y)∈G(x, y) \in \mathrm{G} trên U, thì với mỗi x∈Ux \in \mathrm{U} đoạn Sx\mathrm{S}_x sao cho Sx∈S\mathrm{S}_x \in \mathfrak{S} và p(Sx)=xp(\mathrm{S}_x) = x.

¶ Ta sẽ chứng minh rằng nếu G và G' là hai phần tử của M và nếu U, U' ký hiệu các hình chiếu thứ nhất của chúng, thì một trong hai tập hợp U, U' được chứa trong tập kia và nếu, chẳng hạn, U⊂U′\mathrm{U} \subset \mathrm{U}', thì G=G′∩(U×U)\mathrm{G} = \mathrm{G}' \cap (\mathrm{U} \times \mathrm{U}) (nói cách khác, quan hệ thứ tự trên U được cảm sinh bởi quan hệ thứ tự trên U') và U là một đoạn của U'.

¶ Xét tập hợp V gồm các phần tử x∈U∩U′x \in \mathrm{U} \cap \mathrm{U}' sao cho các đoạn có đầu mút xx là như nhau trong U và U', và sao cho các thứ tự cảm sinh trên đoạn này bởi các thứ tự trên U và U' là đồng nhất. Rõ ràng V là một đoạn trong cả U lẫn U' và các thứ tự cảm sinh trên V là như nhau; vì vậy mệnh đề của chúng ta sẽ được chứng minh nếu ta chỉ ra rằng hoặc V=U\mathrm{V} = \mathrm{U} hoặc V=U′\mathrm{V} = \mathrm{U}'. Ta sẽ lập luận bằng phản chứng và giả sử rằng V≠U\mathrm{V} \neq \mathrm{U} và V≠U′\mathrm{V} \neq \mathrm{U}'. Gọi xx là phần tử bé nhất của U−V\mathrm{U} - \mathrm{V} trong U và gọi x′x' là phần tử bé nhất của U′−V\mathrm{U}' - \mathrm{V} trong U'; ta có V=Sx\mathrm{V} = \mathrm{S}_x trong U, và V=Sx′\mathrm{V} = \mathrm{S}_{x'} trong U'. Nhưng theo giả thiết, V∈S\mathrm{V} \in \mathfrak{S} và

x=p(Sx),x′=p(Sx′),x = p(\mathrm{S}_x), \qquad x' = p(\mathrm{S}_{x'}),

sao cho x=x′x = x'. Do đó theo định nghĩa x∈Vx \in \mathrm{V}, điều này vô lý.

¶ Vì vậy ta có thể áp dụng Mệnh đề 3 của no. 1 cho tập hợp các hình chiếu thứ nhất U=pr1G\mathrm{U} = \mathrm{pr}_1 \mathrm{G} (trong đó G∈M\mathrm{G} \in \mathfrak{M}) và do đó thu được một tập hợp được sắp thứ tự tốt

M=⋃G∈Mpr1G.\mathrm{M} = \bigcup_{\mathrm{G} \in \mathfrak{M}} \mathrm{pr}_1 \mathrm{G}.

Dễ thấy rằng đồ thị của thứ tự trên M thuộc M\mathfrak{M}. Nếu ta có M∈S\mathrm{M} \in \mathrm{S}, thì, đặt a=p(M)a = p(\mathrm{M}), ta sẽ có a∉Ma \notin \mathrm{M}. Do đó ta có thể thêm vào M phần tử aa như phần tử lớn nhất, và tập hợp M′=M∪{a}\mathrm{M}' = \mathrm{M} \cup \{a\} sẽ được sắp tốt. Vì M=Sa\mathrm{M} = \mathrm{S}_a trong M', nên ta sẽ có Sa∈S\mathrm{S}_a \in \mathfrak{S} và p(Sa)=ap(\mathrm{S}_a) = a; do đó đồ thị của thứ tự trên M' sẽ thuộc M\mathfrak{M}, điều này vô lý.

Chú ý rằng nếu ∅∉S\emptyset \notin \mathfrak{S} (và đặc biệt nếu S\mathfrak{S} rỗng), thì tập hợp M mà Bổ đề 3 khẳng định sự tồn tại là tập rỗng; điều này suy ra từ điều kiện 1 của Bổ đề 3.

Định lý 1 (Zermelo) 03QS

Mọi tập hợp* E *đều có thể được sắp tốt.

Cho S=P(E)−{E}\mathfrak{S} = \mathfrak{P}(\mathrm{E}) - \{\mathrm{E}\} là tập hợp tất cả các tập con của E trừ chính E. Với mỗi X∈S\mathrm{X} \in \mathfrak{S}, đặt p(X)=τx (x∈E−X)p(\mathrm{X}) = \tau_x \ (x \in \mathrm{E} - \mathrm{X}); vì quan hệ X∈S\mathrm{X} \in \mathfrak{S} kéo theo (∃x)(x∈E−X)(\exists x)(x \in \mathrm{E} - \mathrm{X}), nên ta có p(X)∈E−Xp(\mathrm{X}) \in \mathrm{E} - \mathrm{X} (Chương I, § 4, no. 1) và do đó p(X)∉Xp(\mathrm{X}) \notin \mathrm{X}. Vậy ta có thể áp dụng Bổ đề 3, và do đó tồn tại một sắp thứ tự tốt trên một tập con M của E sao cho M∉S\mathrm{M} \notin \mathfrak{S}; nhưng tập con duy nhất của E không thuộc S\mathfrak{S} chính là E, và định lý được chứng minh.

4. Tập hợp quy nạp

Định nghĩa 3 03K2

Một tập hợp có thứ tự* E được gọi là quy nạp nếu mọi tập con được sắp thứ tự toàn phần của E đều có một cận trên trong E.

Ví dụ

Ví dụ 1 03T2

Cho F\mathfrak{F} là một tập hợp các tập con của một tập hợp A, được sắp thứ tự bởi quan hệ bao hàm, và sao cho đối với mọi tập con được sắp thứ tự toàn phần G\mathfrak{G} của F\mathfrak{F} thì hợp của các tập hợp thuộc G\mathfrak{G} thuộc về F\mathfrak{F}. Khi đó F\mathfrak{F} là quy nạp đối với quan hệ ⊂\subset vì hợp của các tập hợp thuộc G\mathfrak{G} là cận trên bé nhất của G\mathfrak{G} trong P(A)\mathfrak{P}(\mathrm{A}).

Ví dụ 2 03T3

Một ví dụ quan trọng về một tập hợp các tập con là quy nạp đối với quan hệ ⊂\subset là tập hợp F\mathfrak{F} các đồ thị của các ánh xạ từ các tập con của một tập hợp A vào một tập hợp B. Thật vậy, F\mathfrak{F} là một tập con của P(A×B)\mathfrak{P}(\mathrm{A} \times \mathrm{B}), và nói rằng một tập con G\mathfrak{G} của F\mathfrak{F} được sắp thứ tự toàn phần bởi quan hệ bao hàm có nghĩa là các phần tử của G\mathfrak{G} là các đồ thị của những ánh xạ sao cho, với hai ánh xạ bất kỳ trong số đó, một ánh xạ là một mở rộng của ánh xạ kia. Từ đó suy ra ngay lập tức rằng hợp của các tập hợp thuộc G\mathfrak{G} là một phần tử của F\mathfrak{F} (Chương II, § 4, no. 6, Mệnh đề 7). Do đó tập hợp Φ(A,B)\Phi(\mathrm{A}, \mathrm{B}) các ánh xạ từ các tập con của A vào B là quy nạp đối với quan hệ thứ tự "vv là một mở rộng của uu" giữa uu và vv.

Ví dụ 3 03T4

\* Từ tiên đề vô hạn (§ 6, no. 1) suy ra rằng tập được sắp tốt các số nguyên tự nhiên không là quy nạp đối với quan hệ ⩽\leqslant. \

Định lý 2 ("Bổ đề Zorn") 03QT

— *Mọi tập hợp có thứ tự quy nạp đều có một phần tử cực đại.

Định lý này là một trường hợp riêng của kết quả sau đây:

Mệnh đề 4 03K3

Cho* E là một tập hợp có thứ tự trong đó mọi tập con được sắp tốt đều bị chặn trên; khi đó E *có một phần tử cực đại.

Ta sẽ nói rằng một phần tử v∈Ev \in \mathrm{E} là một cận trên ngặt của một tập con X của E nếu vv là một cận trên của X và v∉Xv \notin \mathrm{X}. Gọi S\mathfrak{S} là tập hợp các tập con của E có một cận trên ngặt trong E, và với mỗi S∈S\mathrm{S} \in \mathfrak{S} đặt p(S)=τv(vp(\mathrm{S}) = \tau_v(v là một cận trên ngặt của S)); khi đó p(S)p(\mathrm{S}) là một cận trên ngặt của S. Áp dụng Bổ đề 3 của no. 3 cho S\mathfrak{S} và pp, ta thấy rằng tồn tại một tập con M của E và một thứ tự tốt Γ\Gamma trên M thỏa mãn các điều kiện của Bổ đề 3; đặc biệt, M không có cận trên ngặt nào trong E. Hơn nữa, thứ tự Γ\Gamma đồng nhất với thứ tự cảm sinh trên M bởi thứ tự trên E. Thật vậy, trong M quan hệ “y∈Γ⟨x⟩y\in\Gamma\langle x\rangle and x≠yx\ne y” tương đương với x∈Syx\in S_y; và vì p(Sy)=yp(S_y)=y là một cận trên của SyS_y (đối với thứ tự trên E), nên điều đó suy ra x<yx<y trong E. Nhưng điều này có nghĩa là đơn ánh từ M vào E là một ánh xạ tăng ngặt (M được trang bị thứ tự Γ\Gamma); và vì M được sắp thứ tự toàn phần, nên suy ra rằng các quan hệ y∈Γ⟨x⟩y\in\Gamma\langle x\rangle và x≤yx\leq y là tương đương trong M (§ 1, no. 12, Mệnh đề 11). Do đó, theo giả thiết, tồn tại một cận trên mm của M trong E; nhưng vì M không có cận trên ngặt, nên suy ra rằng mm là một phần tử cực đại của E.

Hệ quả 1 03K4

Cho E là một tập hợp có thứ tự quy nạp và cho a là một phần tử của E. Khi đó tồn tại một phần tử cực đại m của E sao cho m≥am\geq a.

Thật vậy, theo Định nghĩa 3 thì tập hợp F gồm các phần tử x≥ax\geq a của E là quy nạp, và một phần tử cực đại của F cũng cực đại trong E.

Hệ quả 2 03K5

Cho F\mathfrak{F} là một tập hợp các tập con của một tập hợp E sao cho, với mọi tập con G\mathfrak{G} của F\mathfrak{F} được sắp thứ tự toàn phần bởi quan hệ bao hàm, hợp (resp. giao) của các tập hợp thuộc G\mathfrak{G} thuộc về F\mathfrak{F}; khi đó F\mathfrak{F} có một phần tử cực đại (resp. cực tiểu).

5. Đẳng cấu của các tập hợp được sắp tốt

Định lý 3 03K6

Cho E và F là hai tập hợp được sắp tốt. Khi đó ít nhất một trong hai mệnh đề sau là đúng :

(1) tồn tại một đẳng cấu duy nhất của E lên một đoạn đầu của F;

(2) tồn tại một đẳng cấu duy nhất của F lên một đoạn đầu của E.

Cho F\mathfrak{F} là tập hợp các ánh xạ từ các tập con của E vào F sao cho mỗi ánh xạ được xác định trên một đoạn của E và là một đẳng cấu từ đoạn này lên một đoạn của F. Khi đó tập hợp F\mathfrak{F}, được sắp thứ tự bởi quan hệ “vv mở rộng uu” giữa uu và vv, là quy nạp. Thật vậy, nếu G\mathfrak{G} là một tập con được sắp thứ tự toàn phần của F\mathfrak{F}, thì hợp S của các miền xác định của các ánh xạ u∈Gu\in\mathfrak{G} là một hợp các đoạn của E và do đó bản thân nó cũng là một đoạn của E. Nếu vv là cận trên bé nhất của G\mathfrak{G} trong Φ(E,F)\Phi(E,F) (no. 4, Ví dụ 2), thì v(S)v(S) là hợp các ảnh của các ánh xạ u∈Gu\in\mathfrak{G} và do đó là một đoạn của F. Cuối cùng, với mỗi cặp phần tử xx, yy của S sao cho x<yx<y thì tồn tại u∈Gu\in\mathfrak{G} mà miền xác định chứa cả xx và yy (vì G\mathfrak{G} được sắp thứ tự toàn phần); và vì v(x)=u(x)<u(y)=v(y)v(x)=u(x)<u(y)=v(y), nên vv là một đẳng cấu từ S lên v(S)v(S), và mệnh đề của chúng ta được chứng minh.

¶ Bây giờ, cho u0u_0 là một phần tử cực đại của F\mathfrak{F} (no. 4, Định lý 2) và gọi S0S_0 là đoạn của E là miền xác định của u0u_0. Nếu ta chỉ ra rằng hoặc S0=ES_0=E hoặc u0(S0)=Fu_0(S_0)=F, thì định lý sẽ được chứng minh. Ta lập luận bằng phản chứng và giả sử rằng S0≠ES_0\ne E và u0(S0)≠Fu_0(S_0)\ne F. Khi đó sẽ tồn tại một phần tử a∈Ea\in E và một phần tử b∈Fb\in F sao cho S0=]−←,a[S_0=]-\leftarrow,a[ và u0(S0)]=]−←,b[u_0(S_0)]=]-\leftarrow,b[ (no. 1, Mệnh đề 1). Mở rộng u0u_0 thành một ánh xạ u1u_1 từ đoạn ]−←,a]]-\leftarrow,a] vào F bằng cách đặt u1(a)=bu_1(a)=b; vì u1u_1 là một đẳng cấu từ ]−←,a]]-\leftarrow,a] lên đoạn ]−←,b]]-\leftarrow,b], điều này mâu thuẫn với tính cực đại của u0u_0 trong F\mathfrak{F}.

¶ Tính duy nhất được khẳng định trong Định lý 3 là một hệ quả của Bổ đề sau:

Bổ đề 4 03K7

Cho E, F là hai tập hợp được sắp tốt và f, g là hai ánh xạ tăng từ E vào F sao cho f(E)f(E) là một đoạn của F và g tăng ngặt; khi đó f(x)≤g(x)f(x)\leq g(x) với mọi x∈Ex\in E.

Giả sử ngược lại rằng tập hợp các phần tử y∈Ey\in E sao cho f(y)>g(y)f(y)>g(y) không rỗng; khi đó tập hợp này có một phần tử nhỏ nhất aa. Nếu x<ax<a, khi đó ta có f(x)≤g(x)<g(a)<f(a)f(x)\leq g(x)<g(a)<f(a) vì gg tăng ngặt. Vì f(E)f(E) là một đoạn của F, tồn tại z∈Ez\in E sao cho g(a)=f(z)g(a)=f(z); ff tăng, do đó f(z)<f(a)f(z)<f(a) kéo theo z<az<a. Vậy

f(z)≤g(z)<g(a)=f(z),f(z)\leq g(z)<g(a)=f(z),

điều này là vô lý.

Hệ quả 1 03K8

Đẳng cấu duy nhất của một tập hợp được sắp thứ tự tốt E lên một đoạn của E là ánh xạ đồng nhất của E lên chính nó.

Đặt F=EF=E trong Định lý 3.

Hệ quả 2 03K9

Cho E, F là hai tập được sắp thứ tự tốt. Nếu tồn tại một đẳng cấu ff của E lên một đoạn T của F và một đẳng cấu gg của F lên một đoạn S của E, thì tất yếu có S=ES=E, T=FT=F, và g,fg,f là nghịch đảo của nhau.

Thật vậy, g∘fg\circ f là một đẳng cấu của E lên đoạn g(T)⊂Sg(T)\subset S của E; theo Hệ quả 1 ta có g(T)=S=Eg(T)=S=E, và g∘fg\circ f là ánh xạ đồng nhất của E. Tương tự, f∘gf\circ g là ánh xạ đồng nhất của F, do đó suy ra kết quả.

Hệ quả 3 03KA

Mọi tập con A của một tập hợp được sắp thứ tự tốt E đều đẳng cấu với một đoạn của E.

Do Định lý 3, chỉ cần chứng minh rằng không tồn tại đẳng cấu gg từ E lên một đoạn của A có dạng SaS_a. Nếu có một đẳng cấu như vậy, thì gg khi đó sẽ là một ánh xạ tăng ngặt từ E vào E sao cho g(a)∈Sag(a)\in S_a, nói cách khác sao cho g(a)<ag(a)<a; nhưng bất đẳng thức này mâu thuẫn với Bổ đề 4 (ff là ánh xạ đồng nhất).

6. Các tích từ điển

Cho (Eι)ι∈I(E_\iota)_{\iota\in I} là một họ các tập hợp có thứ tự, được đánh chỉ số bởi một tập hợp I được sắp tốt. Xét tập hợp tích E=∏ι∈IEιE=\displaystyle\prod_{\iota\in I}E_\iota, và quan hệ

“x∈E vaˋ y∈E, vaˋ đoˆˊi với chỉ soˆˊ nhỏ nhaˆˊt ι∈I sao cho pr⁡ιx≠pr⁡ιy, ta coˊ pr⁡ιx<pr⁡ιy”, \text{``}x\in E\text{ và }y\in E,\text{ và đối với chỉ số nhỏ nhất }\iota\in I\text{ sao cho }\operatorname{pr}_{\iota}x\ne\operatorname{pr}_{\iota}y,\text{ ta có }\operatorname{pr}_{\iota}x<\operatorname{pr}_{\iota}y\text{''},

mà ta sẽ ký hiệu bởi R{x,y}R\{x,y\}. Hiển nhiên là R{x,x}R\{x,x\} tương đương với x∈Ex\in E, rằng R{x,y}R\{x,y\} suy ra R{x,x}R\{x,x\} và R{y,y}R\{y,y\}, và rằng (R{x,y} vaˋ R{y,x})(R\{x,y\}\text{ và }R\{y,x\}) suy ra x=yx=y. Cũng dễ kiểm tra rằng (R{x,y} vaˋ R{y,z})(R\{x,y\}\text{ và }R\{y,z\}) suy ra R{x,z}R\{x,z\} (xét chỉ số nhỏ nhất ι∈I\iota\in I sao cho ít nhất hai trong ba phần tử pr⁡ιx\operatorname{pr}_{\iota}x, pr⁡ιy\operatorname{pr}_{\iota}y, pr⁡ιz\operatorname{pr}_{\iota}z là khác nhau); do đó R{x,y}R\{x,y\} là một quan hệ thứ tự trên tập hợp tích E. Quan hệ này và thứ tự mà nó xác định được gọi lần lượt là quan hệ thứ tự từ điển và thứ tự từ điển trên EE (được cảm sinh bởi các thứ tự đã cho trên II và trên các EιE_\iota); tập hợp E được trang bị thứ tự này được gọi là tích từ điển của họ các tập hợp có thứ tự (Eι)ι∈I(E_\iota)_{\iota\in I}. Nếu mỗi EιE_\iota đều được sắp thứ tự toàn phần thì tích từ điển cũng được sắp thứ tự toàn phần.

Bài tập

Xem bài tập cho § 2.

Machine translation of the English, by gpt-5-6-mini, gpt-5.4, against glossary version 34. Not checked by a person. That model is a cut down version of the one the rest of this language was written by.