Bourbaki

6. Quan hệ tương đương

Về nguyên tắc, từ nay về sau chúng ta sẽ thôi dùng các chữ in nghiêng đậm để ký hiệu các dãy ký hiệu chưa xác định; người đọc sẽ dễ dàng nhận ra từ ngữ cảnh những mệnh đề áp dụng cho các chữ hoặc các quan hệ chưa xác định.

1. Định nghĩa một quan hệ tương đương

Cho R{x,y}R\{x, y\} là một quan hệ, xx và yy là hai chữ phân biệt. Quan hệ RR được gọi là đối xứng (đối với các chữ xx và yy) nếu

R{x,y}⇒R{y,x}.R\{x, y\} \Rightarrow R\{y, x\}.

Nếu vậy, bằng cách thay xx và yy lần lượt bằng hai chữ x′x' và y′y', phân biệt với nhau và với tất cả các chữ xuất hiện trong RR, rồi thay yy và xx lần lượt cho x′x' và y′y', ta thấy rằng

R{y,x}⇒R{x,y}.R\{y, x\} \Rightarrow R\{x, y\}.

Do đó R{x,y}R\{x, y\} và R{y,x}R\{y, x\} là tương đương.

¶ Cho zz là một chữ cái không xuất hiện trong RR. Quan hệ RR được gọi là bắc cầu (đối với các chữ cái x,yx, y) nếu ta có

(R{x,y} vaˋ R{y,z})⇒R{x,z}.(R\{x, y\} \text{ và } R\{y, z\}) \Rightarrow R\{x, z\}.

Ví dụ

Quan hệ x=yx = y là đối xứng và bắc cầu. Quan hệ X⊂YX \subset Y là bắc cầu nhưng không đối xứng. Quan hệ X∩Y=∅X \cap Y = \emptyset là đối xứng nhưng không bắc cầu.

Nếu R{x,y}R\{x, y\} vừa đối xứng vừa bắc cầu thì nó được gọi là một quan hệ tương đương (đối với các chữ xx và yy). Trong trường hợp này, ký hiệu x≡y(modR)x \equiv y \pmod{R} đôi khi được dùng như một từ đồng nghĩa của R{x,y}R\{x, y\}; nó được đọc là "*x tương đương với y modulo* RR". Nếu RR là một quan hệ tương đương, ta có R{x,y}⇒(R{x,x}R\{x, y\} \Rightarrow (R\{x, x\} và R{y,y})R\{y, y\}), vì R{x,y}R\{x, y\} kéo theo R{y,x}R\{y, x\}, và (R{x,y}(R\{x, y\} và R{y,x})R\{y, x\}) kéo theo (R{x,x}(R\{x, x\} và R{y,y})R\{y, y\}) theo các định nghĩa.

¶ Cho R{x,y}R\{x, y\} là một quan hệ; quan hệ này được gọi là phản xạ trên EE (đối với các chữ x,yx, y) nếu quan hệ R{x,x}R\{x, x\} tương đương với x∈Ex \in E. Nếu không có khả năng nhầm lẫn nào về EE, người ta nói đơn giản, do lạm dụng ngôn ngữ, rằng RR là phản xạ.

¶ Một quan hệ tương đương trên EE được định nghĩa là một quan hệ tương đương phản xạ trên EE. Nếu R{x,y}R\{x, y\} là một quan hệ tương đương trên EE, ta có R{x,y}⇒((x,y)∈E×E)R\{x, y\} \Rightarrow ((x, y) \in E \times E), do đó RR có một đồ thị (đối với các chữ x,yx, y). Ngược lại, giả sử rằng quan hệ tương đương R{x,y}R\{x, y\} có một đồ thị GG. Hãy nhận thấy rằng quan hệ R{x,x}R\{x, x\} tương đương với quan hệ (∃y)R{x,y}(\exists y)R\{x, y\}; thật vậy, quan hệ thứ nhất suy ra quan hệ thứ hai (Chương I, § 4, no. 2, lược đồ S5), và ngược lại, vì R{x,y}R\{x, y\} suy ra R{x,x}R\{x, x\}, nên (∃y)R{x,y}(\exists y) R\{x, y\} suy ra (∃y)R{x,x}(\exists y) R\{x, x\} và do đó cũng suy ra R{x,x}R\{x, x\}. Vậy R{x,x}R\{x, x\} tương đương với x∈pr1Gx \in \mathrm{pr}_1 G, và do đó RR là một quan hệ tương đương trên pr1G\mathrm{pr}_1 G.

¶ Một tương đương trên một tập hợp E là một sự tương ứng mà nguồn và đích đều bằng E, và có đồ thị F sao cho quan hệ (x,y)∈F(x, y) \in F là một quan hệ tương đương trên E.

Ví dụ

Trích dẫn đến 1

Trích dẫn đến I § 4. Các lý thuyết có lượng từ

Ví dụ 1 03IX

Quan hệ x=yx = y là một quan hệ tương đương không có đồ thị nào, vì nếu có thì phép chiếu thứ nhất của đồ thị này sẽ là tập hợp của mọi đối tượng.

Ví dụ 2 03SC

Quan hệ "x=yx = y và x∈Ex \in E" là một quan hệ tương đương trên E mà đồ thị là đường chéo của E×EE \times E.

Ví dụ 3 03TQ

Quan hệ "tồn tại một song ánh từ X lên Y" là một quan hệ tương đương không có đồ thị nào (xem Chương III, § 3).

Trích dẫn đến 1

Trích dẫn đến III § 3. Các tập hợp đẳng lực. Lực lượng

Ví dụ 4 03TR

Quan hệ "x∈Ex \in E và y∈Ey \in E" là một quan hệ tương đương trên E, mà đồ thị là E×EE \times E.

Ví dụ 5 03TS

Giả sử A⊂EA \subset E; khi đó quan hệ

(x∈E−A vaˋ y=x) hoặc (x∈A vaˋ y∈A)(x \in E - A \text{ và } y = x) \text{ hoặc } (x \in A \text{ và } y \in A)

là một quan hệ tương đương trên E.

Ví dụ 6 03TP

\* Quan hệ "x∈Zx \in \mathbf{Z} và y∈Zy \in \mathbf{Z} và x−yx - y chia được cho 4" là một quan hệ tương đương trên Z\mathbf{Z}.\

Mệnh đề 1 03QH

Một sự tương ứng* Γ\Gamma giữa X và X là một quan hệ tương đương trên X khi và chỉ khi nó thỏa mãn các điều kiện sau : (a) X là miền xác định của Γ\Gamma; (b) Γ=Γ−1\Gamma = \overset{-1}{\Gamma}; (c) Γ∘Γ=Γ\Gamma \circ \Gamma = \Gamma. Cho Γ\Gamma là một sự tương ứng giữa X và X, và gọi G là đồ thị của nó. Nếu Γ\Gamma là một quan hệ tương đương trên X, thì (x,x)∈G(x, x) \in G với mọi x∈Xx \in X; do đó X là miền xác định của Γ\Gamma. Quan hệ (x,y)∈G(x, y) \in G tương đương với (y,x)∈G(y, x) \in G, do đó tương đương với (x,y)∈G−1(x, y) \in \overset{-1}{G}, suy ra G=G−1G = \overset{-1}{G} và vì thế Γ=Γ−1\Gamma = \overset{-1}{\Gamma}. Các quan hệ (x,y)∈G(x, y) \in G và (y,z)∈G(y, z) \in G kéo theo (x,z)∈G(x, z) \in G, do đó G∘G⊂GG \circ G \subset G; ngược lại, (x,y)∈G(x, y) \in G kéo theo (x,x)∈G(x, x) \in G và vì thế (x,y)∈G∘G(x, y) \in G \circ G, do đó G⊂G∘GG \subset G \circ G; suy ra G=G∘GG = G \circ G và do đó Γ=Γ∘Γ\Gamma = \Gamma \circ \Gamma. ¶ Ngược lại, giả sử rằng các điều kiện (a), (b) và (c) được thỏa mãn. Quan hệ (x,y)∈G(x, y) \in G là đối xứng (theo (b)) và bắc cầu (theo (c)); do đó nó là một quan hệ tương đương, và theo (a) nó là một quan hệ tương đương trên X.

Được trích dẫn bởi 1

Được trích dẫn bởi § 6. Quan hệ tương đương

2. Các lớp tương đương ; tập thương

Cho ff là một hàm, E là tập xác định của nó, F là đồ thị của nó. Quan hệ "x∈Ex \in E và y∈Ey \in E và f(x)=f(y)f(x) = f(y)" là một quan hệ tương đương trên E, được gọi là quan hệ tương đương liên kết với f. Nó tương đương với quan hệ (∃z)((x,z)∈F(\exists z)((x, z) \in F and (y,z)∈F)(y, z) \in F), tức là với (∃z)((x,z)∈F(\exists z)((x, z) \in F and (z,y)∈F−1)(z, y) \in \overset{-1}{F}), và do đó đồ thị của nó là F−1∘F\overset{-1}{F} \circ F.

¶ Bây giờ ta sẽ chỉ ra rằng mọi quan hệ tương đương R\mathrm{R} trên một tập hợp E\mathrm{E} đều thuộc kiểu này. Gọi G\mathrm{G} là đồ thị của R\mathrm{R}. Với mỗi x∈Ex \in \mathrm{E}, tập hợp (không rỗng) G(x)⊂E\mathrm{G}(x) \subset \mathrm{E} được gọi là lớp tương đương của xx đối với R\mathrm{R}; do đó nó là tập hợp của mọi y∈Ey \in \mathrm{E} sao cho R{x,y}\mathrm{R}\{x, y\}. Mọi tập hợp có thể viết dưới dạng G(x)\mathrm{G}(x) với một x∈Ex \in \mathrm{E} nào đó được gọi là một lớp tương đương (đối với R\mathrm{R}). Một phần tử của một lớp tương đương được gọi là một đại diện của lớp này. Tập hợp các lớp tương đương đối với R\mathrm{R} (nghĩa là, tập hợp của mọi đối tượng có dạng G(x)\mathrm{G}(x) với một x∈Ex \in \mathrm{E} nào đó) được gọi là tập thương của E\mathrm{E} theo R\mathrm{R} và được ký hiệu là E/R\mathrm{E}/\mathrm{R}. Ánh xạ x→G(x)x \to \mathrm{G}(x) (x∈E)(x \in \mathrm{E}) có miền là E\mathrm{E} và có đích là E/R\mathrm{E}/\mathrm{R} được gọi là ánh xạ chính tắc của E\mathrm{E} lên E/R\mathrm{E}/\mathrm{R}.

C55. Cho R\mathrm{R} là một quan hệ tương đương trên một tập hợp E\mathrm{E}, và gọi pp là ánh xạ chính tắc từ E\mathrm{E} lên E/R\mathrm{E}/\mathrm{R}. Khi đó

R{x,y}⇔(p(x)=p(y)).\mathrm{R}\{x, y\} \Leftrightarrow (p(x) = p(y)).

Với ký hiệu ở trên, cho xx và yy là các phần tử của E\mathrm{E} sao cho

(x,y)∈G.(x, y) \in \mathrm{G}.

Khi đó x∈Ex \in \mathrm{E} và y∈Ey \in \mathrm{E}; hãy chỉ ra rằng G(x)=G(y)\mathrm{G}(x) = \mathrm{G}(y). Vì y∈G(x)y \in \mathrm{G}(x), ta có (Mệnh đề 1) G(y)⊂(G∘G)(x)=G(x)\mathrm{G}(y) \subset (\mathrm{G} \circ \mathrm{G})(x) = \mathrm{G}(x). Mặt khác, ta cũng có (y,x)∈G(y, x) \in \mathrm{G}, do đó G(x)⊂G(y)\mathrm{G}(x) \subset \mathrm{G}(y) và vì vậy

G(x)=G(y),\mathrm{G}(x) = \mathrm{G}(y),

tức là, p(x)=p(y)p(x) = p(y). Ngược lại, nếu G(x)=G(y)\mathrm{G}(x) = \mathrm{G}(y), ta có y∈G(y)=G(x)y \in \mathrm{G}(y) = \mathrm{G}(x), nên (x,y)∈G(x, y) \in \mathrm{G}. Điều này hoàn tất chứng minh.

¶ Một tiết diện của ánh xạ chính tắc pp từ E\mathrm{E} lên E/R\mathrm{E}/\mathrm{R} (§ 3, no. 8, Định nghĩa 11) được gọi gọn hơn là một tiết diện của E\mathrm{E} (đối với quan hệ R\mathrm{R}).

Ví dụ

Ví dụ 1 03SD

Cho R\mathrm{R} là quan hệ tương đương "x∈Ex \in \mathrm{E} và y∈Ey \in \mathrm{E} và x=yx = y" trên một tập hợp E\mathrm{E}. Khi đó lớp tương đương của x∈Ex \in \mathrm{E} là tập hợp {x}\{x\}, và ánh xạ chính tắc x→{x}x \to \{x\} từ E\mathrm{E} lên E/R\mathrm{E}/\mathrm{R} là song ánh.

Ví dụ 2 03SE

Cho E\mathrm{E}, F\mathrm{F} là hai tập hợp và gọi R\mathrm{R} là quan hệ tương đương trên E×F\mathrm{E} \times \mathrm{F} liên kết với ánh xạ pr1\mathrm{pr}_1 của E×F\mathrm{E} \times \mathrm{F} lên E\mathrm{E}. Các lớp tương đương đối với R\mathrm{R} là các tập hợp có dạng {x}×F\{x\} \times \mathrm{F}, trong đó x∈Ex \in \mathrm{E}; ánh xạ x→{x}×Fx \to \{x\} \times \mathrm{F} là một song ánh từ E\mathrm{E} lên (E×F)/R(\mathrm{E} \times \mathrm{F})/\mathrm{R}.

Cho R\mathrm{R} là một quan hệ tương đương trên một tập hợp E\mathrm{E}. Tập thương E/R\mathrm{E}/\mathrm{R} là một tập con của P(E)\mathfrak{P}(\mathrm{E}), và ánh xạ đồng nhất của E/R\mathrm{E}/\mathrm{R} là một phân hoạch của E\mathrm{E} (§ 4, no. 7); thật vậy, nếu G\mathrm{G} là đồ thị của R\mathrm{R}, thì ta có x∈G(x)x \in \mathrm{G}(x) với mọi x∈Ex \in \mathrm{E}, và nếu hai lớp tương đương G(x)\mathrm{G}(x) và G(y)\mathrm{G}(y) có một phần tử chung zz, thì R{x, z}\mathrm{R}\{x,\ z\} và R{y, z}\mathrm{R}\{y,\ z\}, do đó G(x)=G(y)\mathrm{G}(x) = \mathrm{G}(y). Hơn nữa, quan hệ

(∃X)(X∈E/R vaˋ x∈X vaˋ y∈X)(\exists \mathrm{X})(\mathrm{X} \in \mathrm{E}/\mathrm{R} \text{ và } x \in \mathrm{X} \text{ và } y \in \mathrm{X})

tương đương với R{x, y}\mathrm{R}\{x,\ y\}.

¶ Ngược lại, cho (Xι)ι∈I(\mathrm{X}_\iota)_{\iota \in \mathrm{I}} là một phân hoạch của một tập hợp E. Người ta kiểm tra ngay lập tức rằng quan hệ (∃ι)(ι∈I(\exists \iota)(\iota \in \mathrm{I} và x∈Xιx \in \mathrm{X}_\iota và y∈Yι)y \in \mathrm{Y}_\iota) là một quan hệ tương đương R trên E; các lớp tương đương đối với R chính là các tập hợp Xι\mathrm{X}_\iota của phân hoạch, và ánh xạ ι→Xι\iota \to \mathrm{X}_\iota là một song ánh từ I lên E/R. Mọi tập con S của E sao cho, với mỗi ι∈I\iota \in \mathrm{I}, tập hợp S∩Xι\mathrm{S} \cap \mathrm{X}_\iota chỉ gồm một phần tử được gọi là một hệ đại diện (hay một hệ cắt) của các lớp tương đương đối với R. Tên gọi này cũng được dùng để chỉ mọi đơn ánh từ một tập hợp K vào E sao cho ảnh của K qua đơn ánh ấy là một hệ đại diện của các lớp tương đương đối với R; chẳng hạn, mọi tiết diện của E đối với R.

Trích dẫn đến 1

Trích dẫn đến II § 4. Hợp và giao của một họ tập hợp

3. Các quan hệ tương thích với một quan hệ tương đương

Cho R{x, x′}\mathrm{R}\{x,\ x'\} là một quan hệ tương đương và cho P{x}\mathrm{P}\{x\} là một quan hệ. Quan hệ P{x}\mathrm{P}\{x\} được gọi là tương thích với quan hệ tương đương R{x, x′}\mathrm{R}\{x,\ x'\} (đối với xx) nếu ta có

(P{x} vaˋ R{x, y})⇒P{y},(\mathrm{P}\{x\} \text{ và } \mathrm{R}\{x,\ y\}) \Rightarrow \mathrm{P}\{y\},

trong đó yy ký hiệu một chữ cái không xuất hiện trong cả P lẫn R.

Ví dụ, suy ra từ C43 (chương I, §5), no. 1) rằng mọi quan hệ P{x}\mathrm{P}\{x\} đều tương thích với quan hệ tương đương x=x′x = x'.

C56. Cho R{x, x′}\mathrm{R}\{x,\ x'\} là một quan hệ tương đương trên một tập hợp E, và cho P{x}\mathrm{P}\{x\} là một quan hệ không chứa chữ cái x′x' và tương thích (đối với xx*) với quan hệ tương đương* R{x, x′}\mathrm{R}\{x,\ x'\}. Khi đó, nếu tt không xuất hiện trong P{x}\mathrm{P}\{x\}, thì quan hệ "t∈E/Rt \in \mathrm{E}/\mathrm{R} và (∃x)(x∈t(\exists x)(x \in t và P{x})\mathrm{P}\{x\})*" tương đương với quan hệ "*t∈E/Rt \in \mathrm{E}/\mathrm{R} và (∀x)((x∈t)⇒P{x})(\forall x)((x \in t) \Rightarrow \mathrm{P}\{x\})*".*

Cho t∈E/Rt \in \mathrm{E}/\mathrm{R}. Nếu tồn tại a∈ta \in t sao cho P{a}\mathrm{P}\{a\}, thì với mỗi x∈tx \in t ta có R{a, x}\mathrm{R}\{a,\ x\} và do đó P{x}\mathrm{P}\{x\}. Vì thế (∃x)(x∈t(\exists x)(x \in t và P{x})\mathrm{P}\{x\}) kéo theo (∀x)((x∈t)⇒P{x})(\forall x)((x \in t) \Rightarrow \mathrm{P}\{x\}). Mệnh đề đảo lại là hiển nhiên vì t∈E/Rt \in \mathrm{E}/\mathrm{R} kéo theo t≠∅t \neq \emptyset.

¶ Quan hệ

t∈E/R vaˋ (∃x)(x∈t vaˋ P{x})t \in \mathrm{E}/\mathrm{R} \text{ và } (\exists x)(x \in t \text{ và } \mathrm{P}\{x\})

được gọi là cảm sinh bởi P{x}P\{x\} khi chuyển qua thương (đối với xx) theo R. Nếu quan hệ này được ký hiệu bởi P′{t}P'\{t\}, và nếu ff là ánh xạ chính tắc từ E lên E/R, thì quan hệ

y∈E vaˋ P′{f(y)}y \in E \text{ và } P'\{f(y)\}

(trong đó yy không xuất hiện trong P{x}P\{x\}) tương đương với ( y∈Ey \in E và P{y}P\{y\}), như kiểm tra ngay lập tức được.

4. Các tập con bão hòa

Cho R{x,y}R\{x, y\} là một quan hệ tương đương trên một tập hợp E, và A là một tập con của E. A được gọi là bão hòa đối với R nếu quan hệ x∈Ax \in A là tương thích (đối với xx) với R{x,y}R\{x, y\}; hoặc, tương đương, nếu với mỗi x∈Ax \in A, lớp tương đương của xx được chứa trong A. Nói cách khác, một tập hợp là bão hòa đối với R khi và chỉ khi nó là hợp của một tập hợp các lớp tương đương đối với R.

¶ Cho ff là ánh xạ chính tắc của E lên E/R. Nếu A bão hòa đối với R, thì lớp tương đương của mỗi x∈Ax \in A, lớp này bằng f−1⟨{f(x)}⟩\overset{-1}{f}\langle\{f(x)\}\rangle, được chứa trong A, và do đó f−1⟨f⟨A⟩⟩⊂A\overset{-1}{f}\langle f\langle A\rangle\rangle \subset A; vì trong mọi trường hợp ta đều có A⊂f−1⟨f⟨A⟩⟩A \subset \overset{-1}{f}\langle f\langle A\rangle\rangle, suy ra f−1⟨f⟨A⟩⟩=A\overset{-1}{f}\langle f\langle A\rangle\rangle = A. Ngược lại, nếu A=f−1⟨f⟨A⟩⟩A = \overset{-1}{f}\langle f\langle A\rangle\rangle, thì với mọi x∈Ax \in A lớp tương đương K=f(x)K = f(x) của xx đối với R là một phần tử của f⟨A⟩f\langle A\rangle; và vì K=f−1⟨{K}⟩K = \overset{-1}{f}\langle\{K\}\rangle, ta có K⊂f−1⟨f⟨A⟩⟩=AK \subset \overset{-1}{f}\langle f\langle A\rangle\rangle = A. Vậy các tập con của E bão hòa đối với R chính xác là các tập con A của E sao cho A=f−1⟨f⟨A⟩⟩A = \overset{-1}{f}\langle f\langle A\rangle\rangle. Tương đương, đó là các tập con của E có dạng f−1⟨B⟩\overset{-1}{f}\langle B\rangle, trong đó B⊂E/RB \subset E/R; vì quan hệ A=f−1⟨B⟩A = \overset{-1}{f}\langle B\rangle suy ra B=f⟨A⟩B = f\langle A\rangle, do đó A=f−1⟨f⟨A⟩⟩A = \overset{-1}{f}\langle f\langle A\rangle\rangle.

¶ Nếu (Xι)ι∈I(X_\iota)_{\iota \in I} là một họ các tập con bão hòa của E, thì các tập hợp ⋃ι∈IXι\bigcup_{\iota \in I} X_\iota và ⋂ι∈IXι\bigcap_{\iota \in I} X_\iota là bão hòa (§4, Mệnh đề 3 và 4). Nếu A là một tập con bão hòa của E, thì ∁EA\complement_E A cũng vậy (§4, Mệnh đề 6).

¶ Bây giờ cho A là một tập con tùy ý của E. Khi đó tập hợp f−1⟨f⟨A⟩⟩\overset{-1}{f}\langle f\langle A\rangle\rangle chứa A và là bão hòa. Ngược lại, nếu A′ là một tập con bão hòa của E chứa A, thì ta có f⟨A′⟩⊃f⟨A⟩f\langle A'\rangle \supset f\langle A\rangle, nên

A′=f−1⟨f⟨A′⟩⟩⊃f−1⟨f⟨A⟩⟩.A' = \overset{-1}{f}\langle f\langle A'\rangle\rangle \supset \overset{-1}{f}\langle f\langle A\rangle\rangle.

Vì thế ta có thể nói rằng f−1⟨f⟨A⟩⟩\overset{-1}{f}\langle f\langle A\rangle\rangle là tập con bão hòa "nhỏ nhất" của E chứa A (x. Chương III); tập hợp này được gọi là bão hòa của A đối với quan hệ R. Ngay lập tức thấy rằng bão hòa của A là hợp của các lớp tương đương của các phần tử của A. Nếu (Xι)ι∈I(\mathrm{X}_\iota)_{\iota \in \mathrm{I}} là một họ các tập con của E và nếu Aι\mathrm{A}_\iota là bão hòa của Xι\mathrm{X}_\iota đối với R, thì bão hòa của ⋃ι∈IXι\bigcup_{\iota \in \mathrm{I}} \mathrm{X}_\iota là ⋃ι∈IAι\bigcup_{\iota \in \mathrm{I}} \mathrm{A}_\iota (§4, Mệnh đề 3).

5. Các ánh xạ tương thích với các quan hệ tương đương

Cho R là một quan hệ tương đương trên một tập hợp E, và cho ff là một hàm có miền xác định là E. Khi đó người ta nói rằng ff là tương thích với quan hệ R nếu quan hệ y=f(x)y = f(x) là tương thích (đối với xx) với quan hệ R{x, x′}\mathrm{R}\{x,\ x'\}.

¶ Điều này tương đương với việc nói rằng hạn chế của ff trên mỗi lớp tương đương là một ánh xạ hằng, trong trường hợp đó ta nói rằng ff là hằng trên mỗi lớp tương đương đối với R. Nếu gg là ánh xạ chính tắc từ E lên E/R, thì một mệnh đề tương đương là quan hệ g(x)=g(x′)g(x) = g(x') kéo theo f(x)=f(x′)f(x) = f(x'); do đó (§3, Mệnh đề 9) ta có tiêu chuẩn sau:

C57. Cho R là một quan hệ tương đương trên một tập hợp E, và cho g là ánh xạ chính tắc từ E lên E/R. Khi đó một ánh xạ f từ E vào F là tương thích với R khi và chỉ khi f có thể được viết dưới dạng h ∘\circ g, trong đó h là một ánh xạ từ E/R vào F. Ánh xạ h được xác định duy nhất bởi f; nếu s là một tiết diện bất kỳ của g, ta có h =f∘s= f \circ s.

Ánh xạ hh được gọi là cảm sinh bởi f khi chuyển qua thương đối với R.

¶ Cho ff là một ánh xạ từ một tập hợp E vào một tập hợp F, và đặt A=f⟨E⟩⊂F\mathrm{A} = f\langle \mathrm{E}\rangle \subset \mathrm{F}. Cho R là quan hệ tương đương liên kết với ff (no. 2); hiển nhiên ff tương thích với R. Hơn nữa, ánh xạ hh cảm sinh bởi ff khi chuyển qua thương là một đơn ánh từ E/R vào F : vì nếu tt, t′t' là các lớp tương đương đối với R sao cho h(t)=h(t′)h(t) = h(t'), thì ta có f(x)=f(x′)f(x) = f(x') với mọi x∈tx \in t và x′∈t′x' \in t', điều này suy ra t=t′t = t' theo định nghĩa của R. Cho kk là ánh xạ từ E/R lên A có cùng đồ thị với hh; khi đó kk là song ánh. Nếu jj là đơn ánh chính tắc từ A vào F và nếu gg là ánh xạ chính tắc từ E lên E/R, thì ta có thể viết

f=j∘k∘g.f = j \circ k \circ g.

Quan hệ này được gọi là phân tích chính tắc của f.

¶ Cho ff là một ánh xạ từ một tập hợp E vào một tập hợp F, cho R là một quan hệ tương đương trên E, và cho S là một quan hệ tương đương trên F. Cho uu là ánh xạ chính tắc từ E lên E/R, và cho vv là ánh xạ chính tắc từ FF lên F/SF/S. Ánh xạ ff được gọi là tương thích với các quan hệ tương đương RR và SS nếu v∘fv\mathbin{\circ}f tương thích với RR; điều đó có nghĩa là quan hệ x≡x′x\equiv x' (mod RR) kéo theo f(x)≡f(x′)f(x)\equiv f(x') (mod SS). Khi đó, ánh xạ hh từ E/RE/R vào F/SF/S được cảm sinh bởi v∘fv\mathbin{\circ}f khi chuyển qua thương theo RR được gọi là ánh xạ cảm sinh bởi ff khi chuyển qua các thương theo RR và SS; nó được đặc trưng bởi hệ thức v∘f=h∘uv\mathbin{\circ}f=h\mathbin{\circ}u.

6. Ảnh ngược của một quan hệ tương đương; quan hệ tương đương cảm sinh

Cho φ\varphi là một ánh xạ của một tập hợp EE vào một tập hợp FF, và cho SS là một quan hệ tương đương trên FF. Nếu uu là ánh xạ chính tắc của FF lên F/SF/S, thì quan hệ tương đương liên kết với ánh xạ u∘φu\mathbin{\circ}\varphi của EE vào F/SF/S được gọi là ảnh ngược của SS theo φ\varphi; nếu RR là quan hệ này, thì R{x,y}R\{x,y\} tương đương với S{φ(x),φ(y)}S\{\varphi(x),\varphi(y)\}, và các lớp tương đương đối với RR là các ảnh ngược theo φ\varphi của các lớp tương đương đối với SS có giao với φ⟨E⟩\varphi\langle E\rangle.

¶ Đặc biệt, xét một quan hệ tương đương RR trên một tập hợp EE, và cho AA là một tập con của EE; khi đó ảnh ngược của RR dưới đơn ánh jj từ AA vào EE được gọi là quan hệ tương đương cảm sinh bởi RR trên AA, và được ký hiệu bởi RAR_A.

¶ Các lớp tương đương đối với RAR_A là các vết trên AA của các lớp tương đương đối với RR mà cắt AA. Phép đơn ánh jj hiển nhiên tương thích với các quan hệ RAR_A và RR; ánh xạ hh từ A/RAA/R_A vào E/RE/R được cảm sinh bởi jj khi chuyển qua thương đối với RAR_A và RR là một ánh xạ đơn ánh từ A/RAA/R_A vào E/RE/R: vì nếu ff (tương ứng gg) là ánh xạ chính tắc từ EE lên E/RE/R (tương ứng từ AA lên A/RAA/R_A), thì quan hệ h(g(x))=h(g(x′))h(g(x))=h(g(x')), trong đó x∈Ax\in A và x′∈Ax'\in A, là tương đương với f(x)=f(x′)f(x)=f(x') và do đó với g(x)=g(x′)g(x)=g(x'). Ảnh h⟨A/RA⟩h\langle A/R_A\rangle bằng f⟨A⟩f\langle A\rangle. Nếu kk là ánh xạ song ánh từ A/RAA/R_A lên f⟨A⟩f\langle A\rangle có cùng đồ thị như hh, thì kk và ánh xạ nghịch đảo của nó được gọi là chính tắc.

7. Thương của các quan hệ tương đương

Cho RR, SS là hai quan hệ tương đương đối với hai chữ xx, yy. Ta sẽ nói rằng SS mịn hơn RR (hoặc rằng RR thô hơn SS) nếu quan hệ S⇒RS\Rightarrow R là đúng. Nếu RR và SS là các quan hệ tương đương trên cùng một tập hợp EE, mệnh đề nói rằng SS mịn hơn RR có nghĩa là đồ thị của SS được chứa trong đồ thị của RR, hay cũng là mọi lớp tương đương đối với SS đều được chứa trong một lớp tương đương đối với RR; hoặc, tương đương, mọi lớp tương đương đối với RR đều bão hòa đối với SS.

Ví dụ

Ví dụ 1 03SF

Quan hệ "x∈Ex \in E và y∈Ey \in E và x=yx = y" mịn hơn mọi quan hệ tương đương trên E. Quan hệ "x∈Ex \in E và y∈Ey \in E" thô hơn mọi quan hệ tương đương trên E.

Ví dụ 2 03SG

\* Quan hệ tương đương "x∈Zx \in \mathbf{Z} và y∈Zy \in \mathbf{Z} và x−yx - y chia được cho 4" mịn hơn quan hệ tương đương "x∈Zx \in \mathbf{Z} và y∈Zy \in \mathbf{Z} và x−yx - y chia được cho 2". \

Cho R và S là hai quan hệ tương đương trên cùng một tập hợp E, sao cho S mịn hơn R. Gọi ff và gg là các ánh xạ chính tắc từ E lên E/R và từ E lên E/S tương ứng; khi đó hàm ff tương thích với S. Gọi hh là hàm cảm sinh bởi ff khi chuyển qua thương đối với S; khi đó hh là một ánh xạ từ E/S lên E/R. Quan hệ tương đương liên kết với hh trên E/S được gọi là thương của R theo S và được ký hiệu là R/S. Quan hệ x≡y(modR)x \equiv y \pmod{R} tương đương với g(x)≡g(y)(modR/S)g(x) \equiv g(y) \pmod{R/S}, và các lớp tương đương đối với R/S là các ảnh qua gg của các lớp tương đương đối với R. Gọi h=j∘h2∘h1h = j \circ h_2 \circ h_1 là phân tích chính tắc (no. 5) của ánh xạ hh. Khi đó h1h_1 là ánh xạ chính tắc từ E/S lên (E/S)/(R/S), jj là ánh xạ đồng nhất của E/R, và h2h_2 là một ánh xạ một-một từ (E/S)/(R/S) lên E/R. Ánh xạ h2h_2 và ánh xạ nghịch đảo của nó được gọi là chính tắc.

¶ Ngược lại, xét một quan hệ tương đương tùy ý T trên tập hợp E/S, và gọi R là quan hệ tương đương trên E là ảnh ngược của quan hệ T theo gg (no. 6). Vì quan hệ x≡y(modR)x \equiv y \pmod{R} tương đương với g(x)≡g(y)(modT)g(x) \equiv g(y) \pmod{T}, suy ra T tương đương với R/S.

8. Tích của hai quan hệ tương đương

Cho R{x,y}R\{x, y\} và R′{x′,y′}R'\{x', y'\} là hai quan hệ tương đương. Gọi S{u,v}S\{u, v\} là quan hệ

(∃x)(∃y)(∃x′)(∃y′)(u=(x,x′) vaˋ v=(y,y′) vaˋ R{x,y} vaˋ R′{x′,y′});(\exists x)(\exists y)(\exists x')(\exists y')(u = (x, x') \text{ và } v = (y, y') \text{ và } R\{x, y\} \text{ và } R'\{x', y'\});

ngay lập tức kiểm tra được rằng S{u,v}S\{u, v\} là một quan hệ tương đương, gọi là tích của R và R', và được ký hiệu bởi R×R′R \times R'. Giả sử rằng R là một quan hệ tương đương trên một tập hợp E và rằng R' là một quan hệ tương đương trên một tập hợp E'. Khi đó quan hệ S{u,u}S\{u, u\} tương đương với

(∃x)(∃x′)(u=(x,x′) vaˋ R{x,x} vaˋ R′{x′,x′})(\exists x)(\exists x')(u = (x, x') \text{ và } R\{x, x\} \text{ và } R'\{x', x'\})

tức là với (∃x)(∃x′)(u=(x,x′)(\exists x)(\exists x')(u = (x, x') và x∈Ex \in E và x′∈E′)x' \in E'), do đó với u∈E×E′u \in E \times E'. Suy ra rằng R×R′R \times R' là một quan hệ tương đương trên E×E′E \times E'. Nếu

u=(x,x′)u = (x, x')

là một phần tử của E×E′E \times E', thì quan hệ S{u,v}S\{u, v\} tương đương với

(∃y)(∃y′)(v=(y,y′) vaˋ R{x,y} vaˋ R′{x′,y′});(\exists y)(\exists y')(v = (y, y') \text{ và } R\{x, y\} \text{ và } R'\{x', y'\});

nếu GG và G′G' lần lượt là các đồ thị của RR và R′R', thì quan hệ này đến lượt nó lại tương đương với v∈G(x)×G(x′)v \in G(x) \times G(x'). Do đó mọi lớp tương đương đối với R×R′R \times R' đều là tích của một lớp tương đương đối với RR và một lớp tương đương đối với R′R', và ngược lại.

¶ Cho ff và f′f' là các ánh xạ chính tắc từ EE lên E/RE/R và từ E′E' lên E′/R′E'/R', tương ứng, và gọi f×f′f \times f' là phép mở rộng chính tắc của ff và f′f' lên các tập hợp tích (§ 3, no. 9). Khi đó (f×f′)(x,x′)=(f(x),f′(x′))(f \times f')(x, x') = (f(x), f'(x')) với mọi (x,x′)∈E×E′(x, x') \in E \times E'. Ảnh ngược theo f×f′f \times f' của một phần tử (u,u′)(u, u') của (E/R)×(E′/R′)(E/R) \times (E'/R') chính là tích u×u′u \times u' của lớp tương đương uu đối với RR và lớp tương đương u′u' đối với R′R'. Suy ra rằng quan hệ tương đương liên kết với f×f′f \times f' là tương đương với R×R′R \times R'. Do đó ánh xạ f×f′f \times f' có thể được viết thành h∘gh \circ g, trong đó gg là ánh xạ chính tắc từ E×E′E \times E' lên

(E×E′)/(R×R′)(E \times E')/(R \times R')

và hh là một ánh xạ một-một từ (E×E′)/(R×R′)(E \times E')/(R \times R') lên

(E/R)×(E′/R′);(E/R) \times (E'/R');

ánh xạ hh này và ánh xạ nghịch đảo của nó được gọi là chính tắc.

Nhận xét 03IY

Cho P{x,x′}P\{x, x'\} là một quan hệ trong đó các chữ yy, y′y' không xuất hiện. Ta nói P là tương thích với các quan hệ tương đương R{x,y}R\{x, y\} và R′{x′,y′}R'\{x', y'\} (đối với xx và x′x') nếu quan hệ (P{x,x′}(P\{x, x'\} và R{x,y}R\{x, y\} và R′{x′,y′})R'\{x', y'\}) kéo theo P{y,y′}P\{y, y'\}. Cho Q{u}Q\{u\} là quan hệ (∃x)(∃x′)(u=(x,x′)(\exists x)(\exists x')(u = (x, x') và P{x,x′})P\{x, x'\}); khi đó nói rằng Q{u}Q\{u\} tương thích (đối với uu) với quan hệ tương đương S{u,v}S\{u, v\}, là tích của RR và R′R', là một điều tương đương.

9. Các lớp đối tượng tương đương

Cho R{x,y}R\{x, y\} là một quan hệ tương đương, mà không nhất thiết có đồ thị. Hiển nhiên rằng nếu xx, x′x', yy là ba chữ phân biệt, thì quan hệ R{x,x′}R\{x, x'\} kéo theo "R{x,y}⟺R{x′,y}R\{x, y\} \Longleftrightarrow R\{x', y\}" và do đó cũng kéo theo quan hệ (∀y)(R{x,y}⟺R{x′,y})(\forall y)(R\{x, y\} \Longleftrightarrow R\{x', y\}). Theo lược đồ S7 (Chương I, § 5, no. 1), nếu ta đặt θ{x}=τy(R{x,y})\theta\{x\} = \tau_y(R\{x, y\}), thì quan hệ R{x,x′}R\{x, x'\} kéo theo

θ{x}=θ{x′}.\theta\{x\} = \theta\{x'\}.

Mặt khác, chú ý rằng theo định nghĩa R{x,θ{x}}R\{x, \theta\{x\}\} là quan hệ (∃y)(R{x,y})(\exists y)(R\{x, y\}) và do đó (no. 1) tương đương với R{x,x}R\{x, x\}. Suy ra rằng quan hệ (R{x,x}(R\{x, x\} và R{x′,x′}R\{x', x'\} và θ{x}=θ{x′})\theta\{x\} = \theta\{x'\}) là tương đương với R{x,x′}R\{x, x'\}, vì theo S6 (Chương I, §5, no. 1) nó kéo theo quan hệ

(R{x,x} vaˋ R{x′,x′} vaˋ (R{x′,θ{x}}⇔R{x′,θ{x′}})),(R\{x, x\} \text{ và } R\{x', x'\} \text{ và } (R\{x', \theta\{x\}\} \Leftrightarrow R\{x', \theta\{x'\}\})),

do đó cũng kéo theo (R{x,θ{x}}(R\{x, \theta\{x\}\} và R{x′,θ{x}})R\{x', \theta\{x\}\}), và sau cùng kéo theo R{x,x′}R\{x, x'\} theo tính bắc cầu và tính đối xứng. Và vì ngược lại R{x,x′}R\{x, x'\} kéo theo R{x,x}R\{x, x\} và R{x′,x′}R\{x', x'\}, mệnh đề được chứng minh. Số hạng θ{x}\theta\{x\} được gọi là lớp các đối tượng tương đương với x (đối với quan hệ R).

¶ Bây giờ giả sử rằng T là một số hạng sao cho quan hệ

(1)

(∀y)(R{y,y}⇒(∃x)(x∈T vaˋ R{x,y}))(\forall y)(R\{y, y\} \Rightarrow (\exists x)(x \in T \text{ và } R\{x, y\}))

là đúng. Khi đó quan hệ (∃x)(R{x,x}(\exists x)(R\{x, x\} and z=θ{x})z = \theta\{x\}) là xác định tập theo z. Thật vậy, ta có thể giả sử rằng x∈Tx \in T kéo theo R{x,x}R\{x, x\}; chỉ cần thay thế T bằng tập hợp mọi x∈Tx \in T sao cho R{x,x}R\{x, x\} (nhận thấy rằng R{x,y}R\{x, y\} kéo theo R{x,x}R\{x, x\}). Gọi Θ\Theta là tập hợp mọi đối tượng có dạng θ{x}\theta\{x\} với x∈Tx \in T (§1, no. 6). Giả sử rằng R{y,y}R\{y, y\} là đúng; khi đó tồn tại x∈Tx \in T sao cho R{x,y}R\{x, y\} và do đó θ{y}=θ{x}∈Θ\theta\{y\} = \theta\{x\} \in \Theta. Tập hợp Θ\Theta được gọi là tập hợp các lớp đối tượng tương đương đối với R; và với mỗi xx sao cho R{x,x}R\{x, x\}, θ{x}\theta\{x\} là phần tử duy nhất z∈Θz \in \Theta sao cho R{x,z}R\{x, z\}.

Dưới cùng giả thiết, cho A{x}A\{x\} là một số hạng sao cho R{x,y}R\{x, y\} suy ra A{x}=A{y}A\{x\} = A\{y\}. Khi đó quan hệ (∃x)(R{x,x}(\exists x)(R\{x, x\} and z={x})z = \{x\}) xác định tập theo zz, vì R{x,x}R\{x, x\}, tương đương với R{x,θ{x}}R\{x, \theta\{x\}\}, suy ra A{x}=A{θ{x}}A\{x\} = A\{\theta\{x\}\}, và do đó nếu E là tập hợp các đối tượng có dạng A{t}A\{t\} với t∈Θt \in \Theta, thì R{x,x}R\{x, x\} suy ra A{x}∈EA\{x\} \in E. Nếu ff là hàm t→A{t}t \to A\{t\} (t∈Θ,A{t}∈E)(t \in \Theta, A\{t\} \in E), thì quan hệ R{x,x}R\{x, x\} suy ra A{x}=f(θ{x})A\{x\} = f(\theta\{x\}).

Đặc biệt, nếu R là một quan hệ tương đương trên một tập hợp F, ta có thể lấy A{x}A\{x\} là lớp tương đương của x đối với R (no. 2), và khi đó hàm ff là một song ánh từ Θ\Theta lên tập thương F/R; điều này biện minh cho thuật ngữ đã đưa vào.

\* Ví dụ. Cho R{x,y}R\{x, y\} là quan hệ tương đương "xx và yy là hai không gian vectơ có cùng số chiều hữu hạn trên C\mathbf{C}"; quan hệ này không có đồ thị. Nó thỏa mãn điều kiện (1) khi T là tập hợp tất cả các không gian con vectơ của C(N)\mathbf{C}^{(\mathbf{N})}, hoặc khi tập con T' của T gồm các không gian Cn\mathbf{C}^n (n∈N)(n \in \mathbf{N}) với các quy ước rằng C0\mathbf{C}^0 gồm điểm 0 của C(N)\mathbf{C}^{(\mathbf{N})} và rằng Cn\mathbf{C}^n (n>0)(n > 0) là tổng của nn thành phần đầu tiên của tổng trực tiếp C(N)\mathbf{C}^{(\mathbf{N})}. Với lựa chọn thứ hai này, ta có Θ=T′\Theta = T'.\*

Bài tập

Xem bài tập cho § 6.

Bản dịch máy từ tiếng Anh, bởi gpt-5-6, gpt-5.4, theo bảng thuật ngữ phiên bản 34. Chưa được người kiểm tra.