1. Quan hệ thứ tự. Tập hợp có thứ tự

1. Định nghĩa của một quan hệ thứ tự

Cho $R\{x, y\}$ là một quan hệ, trong đó $x$ và $y$ là các chữ phân biệt. Ta nói R là một quan hệ thứ tự đối với các chữ x và y (hoặc giữa x và y) nếu

Quan hệ thứ nhất trong các quan hệ trên nói rằng R là bắc cầu đối với các chữ $x$ và $y$ (Chương II, § 6, no. 1).

Ví dụ

(1) Quan hệ đẳng thức, $x = y$, là một quan hệ thứ tự.

(2) Quan hệ $X \subset Y$ là một quan hệ thứ tự giữa X và Y (Chương II, § 1, no. 2, Mệnh đề 1 và 2 và tiên đề A1), và thường được gọi là quan hệ bao hàm.

(3) Cho $R\{x, y\}$ là một quan hệ thứ tự giữa $x$ và $y$. Khi đó quan hệ $R\{\, y,\, x\}$ cũng là một quan hệ thứ tự giữa x và y, được gọi là đối của quan hệ thứ tự $R\{x,\, y\}$.

Một quan hệ thứ tự trên một tập hợp E là một quan hệ thứ tự $R\{x,\, y\}$ đối với hai chữ phân biệt $x$, $y$ sao cho quan hệ $R\{x,\, x\}$ là tương đương với $x \in E$ (nói cách khác, sao cho $R\{x,\, y\}$ là phản xạ trên E (Chương II, § 6, no. 1)). Khi đó quan hệ $R\{x,\, y\}$ kéo theo "$x \in E$ và $y \in E$" và quan hệ $(R\{x,\, y\}$ and $R\{\, y,\, x\})$ là tương đương với "$x \in E$ và $y \in E$ và $x = y$".

Ví dụ

2. Quan hệ tiền thứ tự

Cho $R\{x, y\}$ là một quan hệ, $x$ và $y$ là hai chữ cái phân biệt. Nếu $R$ là bắc cầu và nếu ta có $R\{x, y\} \Rightarrow (R\{x, x\}$ và $R\{y, y\})$, thì không nhất thiết suy ra rằng $R$ là một quan hệ thứ tự vì quan hệ

không nhất thiết suy ra $x = y$. $R\{x, y\}$ được gọi là một quan hệ tiền thứ tự giữa $x$ và $y$; khi đó $R\{y, x\}$ cũng là một quan hệ tiền thứ tự giữa $x$ và $y$, gọi là đối của quan hệ $R\{x, y\}$.

Chẳng hạn, cho $\mathfrak{R}$ là tập hợp các tập con của $\mathfrak{P}(E)$ mà là những phủ của E (Chương II, § 4, no. 6). Quan hệ "$\mathfrak{R}$ thô hơn $\mathfrak{R}'$" giữa các phần tử $\mathfrak{R}$, $\mathfrak{R}'$ của $\mathfrak{R}$ (Chương II, § 4, no. 6) là bắc cầu và phản xạ. Nhưng hai phủ phân biệt có thể sao cho mỗi phủ đều thô hơn phủ kia; chẳng hạn, đó là trường hợp khi $\mathfrak{R}'$ là hợp (trong $\mathfrak{P}(E)$) của $\mathfrak{R}$ và một tập con của E được chứa trong một tập hợp của $\mathfrak{R}$ nhưng không thuộc $\mathfrak{R}$.

Nhưng trong mọi trường hợp, quan hệ $(R\{x, y\}$ and $R\{y, x\})$ là một quan hệ tương đương $S\{x, y\}$ đối với $x$ và $y$. Gọi $x'$, $y'$ là các chữ cái phân biệt với $x$, $y$ mà không xuất hiện trong R. Khi đó $R\{x, y\}$ là tương thích (đối với $x$ và $y$) với các quan hệ tương đương $S\{x, x'\}$ và $S\{y, y'\}$; nói cách khác (Chương II, § 6, no. 8), quan hệ

suy ra $R\{x', y'\}$.

¶ Một quan hệ tiền thứ tự trên một tập hợp E là một quan hệ tiền thứ tự $R\{x, y\}$ sao cho quan hệ $R\{x, x\}$ tương đương với $x \in E$. Khi đó quan hệ $R\{x, y\}$ suy ra "$x \in E$ và $y \in E$".

¶ Nếu $R\{x, y\}$ là một quan hệ tiền thứ tự trên một tập hợp E, thì quan hệ $S\{x, y\}$ được định nghĩa ở trên là một quan hệ tương đương trên E. Gọi $R'\{X, Y\}$ là quan hệ

nghĩa là, quan hệ cảm sinh bởi R khi chuyển qua thương (đối với $x$ và $y$); ta đã thấy ở Chương II, § 6, no. 3, rằng nó tương đương với quan hệ

¶ Ta hãy chứng minh rằng $R'\{X, Y\}$ là một quan hệ thứ tự giữa các phần tử của E/S. Quan hệ $(R'\{X, Y\}$ và $R'\{Y, Z\})$ tương đương với

(Chương I, § 4, các tiêu chuẩn C40, C41). Vì $R\{x, y\}$ là bắc cầu và $Y \in E/S \Rightarrow Y \neq \emptyset$ (Chương II, § 6, no. 2), suy ra ngay lập tức rằng $R'\{X, Y\}$ là bắc cầu. Tiếp theo, $(R'\{X, Y\}$ và $R'\{Y, X\})$ tương đương với

và do đó tương đương với

và vì thế kéo theo

Hơn nữa, $R\{x, y\}$ suy ra $R\{x, x\}$ và $R\{y, y\}$, và do đó $R'\{X, Y\}$ suy ra mỗi quan hệ sau

do đó $R'\{X, Y\}$ suy ra $(R'\{X, X\}$ và $R'\{Y, Y\})$. Sau cùng, vì $x \in E$ suy ra $R\{x, x\}$, $X \in E/S$ suy ra $R'\{X, X\}$, và chứng minh của mệnh đề của chúng ta là đầy đủ. $R'\{X, Y\}$ được gọi là quan hệ thứ tự liên kết với $R\{x, y\}$.

¶ Một tiền thứ tự trên một tập hợp E là một sự tương ứng $\Gamma = (G, E, E)$ với E là nguồn và là đích, và sao cho $(x, y) \in G$ là một quan hệ tiền thứ tự trên E. Do lạm dụng ngôn ngữ, đôi khi ta cũng gọi đồ thị G của $\Gamma$ là một tiền thứ tự trên E. Để điều này đúng, điều kiện cần và đủ là $\Delta \subset G$ và $G \circ G \subset G$ (điều này kéo theo $G \circ G = G$). Khi đó quan hệ tương đương S tương ứng với quan hệ tiền thứ tự $(x, y) \in G$ có $G \cap \overset{-1}{G}$ làm đồ thị của nó; quan hệ thứ tự liên kết với $(x, y) \in G$ có làm đồ thị tập con G' của $(E/S) \times (E/S)$ tương ứng (Chương II, § 6, no. 8) với ảnh của G dưới ánh xạ chính tắc từ $E \times E$ lên

3. Ký hiệu và thuật ngữ

Các định nghĩa sẽ được đưa ra trong phần còn lại của tiết diện này áp dụng cho một quan hệ thứ tự (hoặc quan hệ tiền thứ tự) tùy ý $\mathrm{R}\{x, y\}$ giữa $x$ và $y$, nhưng sẽ chủ yếu được dùng trong trường hợp $\mathrm{R}\{x, y\}$ được viết là $x \leqslant y$ \*(theo phép tương tự với quan hệ thứ tự thông thường giữa các số nguyên hoặc số thực)\* (hoặc $x \subset y$, hoặc bằng một dấu tương tự nào đó); vì vậy chúng tôi sẽ chỉ phát biểu chúng cho ký hiệu $x \leqslant y$, và để lại cho người đọc việc chuyển chép chúng sang các ký hiệu khác. Khi $\mathrm{R}\{x, y\}$ được viết là $x \leqslant y$, thì $y \geqslant x$ đồng nghĩa với $x \leqslant y$, và các quan hệ này được đọc là "$x$ nhỏ hơn $y$", hoặc "$x$ bé hơn $y$", hoặc "$y$ lớn hơn $x$" hoặc "$y$ vĩ đại hơn $x$". Khi đó quan hệ $x \geqslant y$ là quan hệ tiền thứ tự (giữa $x$ và $y$) đối với $x \leqslant y$.

Do sự lạm dụng ngôn ngữ, ta sẽ thường nói "quan hệ $\leqslant$" thay vì "quan hệ $x \leqslant y$"; trong trường hợp này "quan hệ $\geqslant$" là quan hệ đối của "quan hệ $\leqslant$". Ta cũng nhận xét rằng, trong cùng một chứng minh, ta thường có thể dùng cùng dấu $\leqslant$ để chỉ nhiều quan hệ thứ tự khác nhau khi không có nguy cơ nhầm lẫn.

Các điều kiện để một quan hệ viết dưới dạng $x \leqslant y$ là một quan hệ thứ tự trên một tập hợp E như sau :

(RO$_{\mathrm{I}}$) Quan hệ "$x \leqslant y$ và $y \leqslant z$" kéo theo $x \leqslant z$. (RO$_{\mathrm{II}}$) Quan hệ "$x \leqslant y$ và $y \leqslant x$" kéo theo $x = y$. (RO$_{\mathrm{III}}$) Quan hệ $x \leqslant y$ kéo theo "$x \leqslant x$ và $y \leqslant y$". (RO$_{\mathrm{IV}}$) Quan hệ $x \leqslant x$ là tương đương với $x \in \mathrm{E}$.

Nếu bỏ điều kiện (RO$_{\mathrm{II}}$), ta được các điều kiện để $x \leqslant y$ là một quan hệ tiền thứ tự trên E. ¶ Khi một quan hệ thứ tự được viết $x \leqslant y$ thì ta sẽ viết $x < y$ (hoặc $y > x$) cho quan hệ "$x \leqslant y$ và $x \neq y$"; các quan hệ này được đọc là "$x$ nhỏ hơn nghiêm ngặt $y$", hoặc "$x$ nhỏ hơn hẳn $y$", hoặc "$y$ lớn hơn nghiêm ngặt $x$", hoặc "$y$ lớn hơn hẳn $x$".

Ví dụ về quan hệ bao hàm cho thấy rằng phủ định của $x \leqslant y$ (đôi khi được ký hiệu bởi $x \nleqslant y$) không nhất thiết tương đương với $y < x$ (xem no. 12).

C58. Cho $\leqslant$ là một quan hệ thứ tự, và cho $x$, $y$ là hai chữ cái phân biệt. Quan hệ $x \leqslant y$ tương đương với "$x < y$ hoặc $x = y$". Mỗi quan hệ trong các quan hệ "$x \leqslant y$ và $y < z$", "$x < y$ và $y \leqslant z$" đều suy ra $x < z$.

Mệnh đề thứ nhất suy ra từ tiêu chuẩn $A \Rightarrow ((A$ và (không $B$)) hoặc $B$) (Chương I, § 3, tiêu chuẩn C24). Để chứng minh mệnh đề thứ hai, ta nhận thấy rằng mỗi giả thiết đều kéo theo $x \leqslant z$, theo tính bắc cầu; và quan hệ ($x = z$ và $x \leqslant y$ và $y \leqslant z$) sẽ kéo theo $x = y = z$, trái với giả thiết.

¶ Để làm cho mọi việc dễ dàng hơn và thay thế các tiêu chuẩn siêu toán học bằng các định lý toán học, ta thường sẽ xét một lý thuyết $\mathscr{T}$ chứa các tiên đề và các lược đồ tiên đề của lý thuyết tập hợp, và thêm vào đó, hai hằng số E và $\Gamma$ thỏa mãn tiên đề

"$\Gamma$ là một thứ tự trên tập hợp E" (no. 1).

Ta sẽ ký hiệu bởi $x \leqslant y$ quan hệ $y \in \Gamma\langle x \rangle$, và ta sẽ nói rằng tập hợp E được sắp thứ tự bởi thứ tự $\Gamma$ (hoặc bởi quan hệ thứ tự $y \in \Gamma\langle x \rangle$) (xem Chương IV, § 1).

¶ Mỗi khi, trong $\mathscr{T}$, $\Gamma$ là một tiền thứ tự trên E, ta cũng nói rằng E được tiền thứ tự bởi tiền thứ tự $\Gamma$.

Trong một số tình huống (chẳng hạn trong định nghĩa sau đây), các lý thuyết mà chúng ta sẽ xét hơi phức tạp hơn một chút. Chúng tôi để bạn đọc tự làm minh nhiên các hằng số và các tiên đề của các lý thuyết như vậy.

Cho E, E$'$ là hai tập hợp có thứ tự bởi các thứ tự $\Gamma$, $\Gamma'$. Một đẳng cấu của E lên E$'$ (đối với các thứ tự $\Gamma$ và $\Gamma'$) là một song ánh $f$ từ E lên E$'$ sao cho các quan hệ $x \leqslant y$ và $f(x) \leqslant f(y)$ là tương đương (xem Chương IV, § 1).

4. Tập con có thứ tự. Tích của các tập hợp có thứ tự

Cho E là một tập hợp có thứ tự bởi một thứ tự $\Gamma$, với đồ thị G. Với mỗi tập con A của E, $G \cap (A \times A)$ là một thứ tự trên A; quan hệ thứ tự tương ứng là tương đương với "$x \leqslant y$ and $x \in A$ and $y \in A$", và ta sẽ ký hiệu nó đơn giản là $x \leqslant y$ (do lạm dụng ngôn ngữ). Thứ tự và quan hệ thứ tự như vậy xác định trên A được gọi là cảm sinh bởi thứ tự và quan hệ thứ tự đã cho trên E; và thứ tự cùng quan hệ thứ tự trên E được gọi là những mở rộng của thứ tự và quan hệ thứ tự mà chúng cảm sinh trên A. Mỗi khi ta xét A như một tập hợp có thứ tự thì ta ngầm hiểu thứ tự cảm sinh trên A bởi thứ tự của E, trừ khi có nói rõ điều ngược lại.

Ví dụ. Các quan hệ cảm sinh bởi quan hệ bao hàm $X \subset Y$ trên các tập hợp khác nhau của những tập con có tầm quan trọng đáng kể. Dưới đây là một vài ví dụ:

5. Các ánh xạ tăng

Một ánh xạ tăng từ E vào F trở thành giảm (và ngược lại) khi ta thay thế một trong các quan hệ tiền thứ tự trên E hoặc trên F bằng quan hệ tiền thứ tự đối. Mọi hàm hằng đều vừa tăng vừa giảm; đảo lại của mệnh đề này thường không đúng.

Ví dụ, nếu một tập hợp E được sắp thứ tự bởi quan hệ đẳng thức, thì ánh xạ đồng nhất của E lên chính nó vừa tăng vừa giảm, nhưng không hằng nếu E có nhiều hơn một phần tử (xem Bài tập 7).

Ví dụ

6. Phần tử cực đại và cực tiểu

7. Phần tử lớn nhất và phần tử nhỏ nhất

Nếu tồn tại một phần tử $a$ trong một tập hợp có thứ tự E sao cho $a \leqslant x$ với mọi $x \in E$, thì $a$ là phần tử duy nhất của E có tính chất này; thật vậy, nếu cũng có $b \leqslant x$ với mọi $x \in E$, thì ta phải có $a \leqslant b$ và $b \leqslant a$, và do đó $a = b$.

8. Cận trên và cận dưới

Mọi cận trên của $X$ đều là một cận dưới của $X$ đối với thứ tự đối, và ngược lại.

¶ Nếu $x$ là một cận dưới của $X$, thì mọi phần tử $z\leq x$ cũng là một cận dưới của $X$. Một cận dưới của $X$ cũng là một cận dưới của mọi tập con của $X$. Một tập hợp có thứ tự $X$ có một phần tử bé nhất nếu và chỉ nếu tồn tại một cận dưới của $X$ thuộc về $X$.

¶ Tập hợp các cận dưới của một tập con $X$ của một tập tiền thứ tự $E$ có thể rỗng : đó là trường hợp khi $X=E$ và $E$ là một tập hợp có thứ tự không có phần tử bé nhất.

¶ Một tập con $X$ của $E$ mà tập hợp các cận dưới (tương ứng, cận trên) của nó không rỗng được gọi là bị chặn dưới (tương ứng, bị chặn trên). Một tập con vừa bị chặn dưới vừa bị chặn trên được gọi là bị chặn. Nếu $X$ bị chặn dưới (tương ứng bị chặn trên, bị chặn), thì mọi tập con của $X$ cũng có tính chất đó.

Mọi tập con gồm một phần tử đều bị chặn. Nhưng một tập con gồm hai phần tử thì không nhất thiết bị chặn trên cũng không nhất thiết bị chặn dưới (no. 10).

Cho $E$ là một tập tiền thứ tự và $f$ là một ánh xạ từ một tập hợp tùy ý $A$ vào $E$. Ánh xạ $f$ được gọi (do lạm dụng ngôn ngữ) là bị chặn dưới (tương ứng bị chặn trên, bị chặn) nếu tập $f(A)$ bị chặn dưới (tương ứng bị chặn trên, bị chặn) trong $E$.

9. Cận trên bé nhất và cận dưới lớn nhất

Với một tập con $X$ của một tập hợp có thứ tự $E$, cận trên bé nhất (resp. cận dưới lớn nhất) của $X$ trong $E$, khi nó tồn tại, được ký hiệu là

hoặc bởi sup X (tương ứng inf X) nếu không có nguy cơ nhập nhằng. Cận trên nhỏ nhất (tương ứng cận dưới lớn nhất) của một tập hợp $\{x, y\}$ gồm hai phần tử, khi tồn tại, được ký hiệu là sup $(x, y)$ (tương ứng inf $(x, y)$). Tương tự đối với cận trên nhỏ nhất và cận dưới lớn nhất của một tập hợp gồm ba phần tử, v.v.

¶ Nếu một tập con X của E có một phần tử lớn nhất $a$, thì $a$ là cận trên nhỏ nhất của X trong E.

¶ Nếu X có một cận dưới lớn nhất $a$ trong E, thì $a$ là cận trên nhỏ nhất của X đối với thứ tự đối trên E. Vì lý do này, trong phần lớn những gì tiếp theo, ta có thể chủ yếu chỉ xét các tính chất của cận trên nhỏ nhất.

Ví dụ

(1) Tập hợp các cận trên của tập rỗng $\emptyset$ trong một tập hợp có thứ tự E hiển nhiên là chính E; do đó $\emptyset$ có một supremum trong E khi và chỉ khi E có một phần tử nhỏ nhất, và khi đó phần tử này là cận trên nhỏ nhất của $\emptyset$.

(2) Trong tập hợp $\mathfrak{P}(E)$ các tập con của một tập hợp E, được sắp thứ tự bởi quan hệ bao hàm, mọi tập con $\mathfrak{S}$ của $\mathfrak{P}(E)$ đều có một cận trên nhỏ nhất, đó là hợp của các tập hợp thuộc $\mathfrak{S}$, và một cận dưới lớn nhất, đó là giao của các tập hợp thuộc $\mathfrak{S}$.

(3) Cho E, F là hai tập hợp và cho $\Theta$ là một tập con của $\Phi(E, F)$, tập các ánh xạ từ các tập con của E vào F, được sắp thứ tự bởi quan hệ mở rộng của các ánh xạ (no. 1, Ví dụ 3). Với mỗi $u \in \Phi(E, F)$, gọi $D(u)$ là miền xác định của $u$. Điều kiện tồn tại một mở rộng chung của một họ các ánh xạ thuộc $\Phi(E, F)$ (Chương II, § 4, no. 6, Mệnh đề 7) cho thấy rằng $\Theta$ có một cận trên nhỏ nhất trong $\Phi(E, F)$ khi và chỉ khi với mỗi cặp $(u, v)$ gồm các phần tử của $\Theta$ ta có $u(x) = v(x)$ mỗi khi $x \in D(u) \cap D(v)$.

Một ánh xạ $f$ từ một tập hợp A vào một tập hợp có thứ tự E được gọi là có một cận trên nhỏ nhất nếu ảnh $f(A)$ có một cận trên nhỏ nhất trong E; khi đó cận này được gọi là cận trên nhỏ nhất của f và được viết là $\sup_{x \in A} f(x)$. Tương tự đối với cận dưới lớn nhất.

Đặc biệt, nếu một tập con A của E có một cận trên nhỏ nhất trong E, thì cận này là cận trên nhỏ nhất của đơn ánh chính tắc của A vào E, và do đó có thể được viết là $\sup_{x \in A} x$.