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 là một quan hệ, và là hai chữ phân biệt. Quan hệ được gọi là đối xứng (đối với các chữ và ) nếu
Nếu vậy, bằng cách thay và lần lượt bằng hai chữ và , phân biệt với nhau và với tất cả các chữ xuất hiện trong , rồi thay và lần lượt cho và , ta thấy rằng
Do đó và là tương đương.
¶ Cho là một chữ cái không xuất hiện trong . Quan hệ được gọi là bắc cầu (đối với các chữ cái ) nếu ta có
Ví dụ
Quan hệ là đối xứng và bắc cầu. Quan hệ là bắc cầu nhưng không đối xứng. Quan hệ là đối xứng nhưng không bắc cầu.
Nếu 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ữ và ). Trong trường hợp này, ký hiệu đôi khi được dùng như một từ đồng nghĩa của ; nó được đọc là "*x tương đương với y modulo* ". Nếu là một quan hệ tương đương, ta có và , vì kéo theo , và và kéo theo và theo các định nghĩa.
¶ Cho là một quan hệ; quan hệ này được gọi là phản xạ trên (đối với các chữ ) nếu quan hệ tương đương với . Nếu không có khả năng nhầm lẫn nào về , người ta nói đơn giản, do lạm dụng ngôn ngữ, rằng là phản xạ.
¶ Một quan hệ tương đương trên được định nghĩa là một quan hệ tương đương phản xạ trên . Nếu là một quan hệ tương đương trên , ta có , do đó có một đồ thị (đối với các chữ ). Ngược lại, giả sử rằng quan hệ tương đương có một đồ thị . Hãy nhận thấy rằng quan hệ tương đương với quan hệ ; 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ì suy ra , nên suy ra và do đó cũng suy ra . Vậy tương đương với , và do đó là một quan hệ tương đương trên .
¶ 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ệ 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ệ 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ệ " và " là một quan hệ tương đương trên E mà đồ thị là đường chéo của .
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ệ " và " là một quan hệ tương đương trên E, mà đồ thị là .
Ví dụ 6 03TP
\* Quan hệ " và và chia được cho 4" là một quan hệ tương đương trên .\
Mệnh đề 1 03QH
Một sự tương ứng* 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 ; (b) ; (c) . Cho là một sự tương ứng giữa X và X, và gọi G là đồ thị của nó. Nếu là một quan hệ tương đương trên X, thì với mọi ; do đó X là miền xác định của . Quan hệ tương đương với , do đó tương đương với , suy ra và vì thế . Các quan hệ và kéo theo , do đó ; ngược lại, kéo theo và vì thế , do đó ; suy ra và do đó . ¶ 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ệ 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 là một hàm, E là tập xác định của nó, F là đồ thị của nó. Quan hệ " và và " 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ệ and , tức là với and , và do đó đồ thị của nó là .
¶ Bây giờ ta sẽ chỉ ra rằng mọi quan hệ tương đương trên một tập hợp đều thuộc kiểu này. Gọi là đồ thị của . Với mỗi , tập hợp (không rỗng) được gọi là lớp tương đương của đối với ; do đó nó là tập hợp của mọi sao cho . Mọi tập hợp có thể viết dưới dạng với một nào đó được gọi là một lớp tương đương (đối với ). 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 (nghĩa là, tập hợp của mọi đối tượng có dạng với một nào đó) được gọi là tập thương của theo và được ký hiệu là . Ánh xạ có miền là và có đích là được gọi là ánh xạ chính tắc của lên .
C55. Cho là một quan hệ tương đương trên một tập hợp , và gọi là ánh xạ chính tắc từ lên . Khi đó
Với ký hiệu ở trên, cho và là các phần tử của sao cho
Khi đó và ; hãy chỉ ra rằng . Vì , ta có (Mệnh đề 1) . Mặt khác, ta cũng có , do đó và vì vậy
tức là, . Ngược lại, nếu , ta có , nên . Đ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 từ lên (§ 3, no. 8, Định nghĩa 11) được gọi gọn hơn là một tiết diện của (đối với quan hệ ).
Ví dụ
Ví dụ 1 03SD
Cho là quan hệ tương đương " và và " trên một tập hợp . Khi đó lớp tương đương của là tập hợp , và ánh xạ chính tắc từ lên là song ánh.
Ví dụ 2 03SE
Cho , là hai tập hợp và gọi là quan hệ tương đương trên liên kết với ánh xạ của lên . Các lớp tương đương đối với là các tập hợp có dạng , trong đó ; ánh xạ là một song ánh từ lên .
Cho là một quan hệ tương đương trên một tập hợp . Tập thương là một tập con của , và ánh xạ đồng nhất của là một phân hoạch của (§ 4, no. 7); thật vậy, nếu là đồ thị của , thì ta có với mọi , và nếu hai lớp tương đương và có một phần tử chung , thì và , do đó . Hơn nữa, quan hệ
tương đương với .
¶ Ngược lại, cho 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ệ và và 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 của phân hoạch, và ánh xạ 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 , tập hợp 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 là một quan hệ tương đương và cho là một quan hệ. Quan hệ được gọi là tương thích với quan hệ tương đương (đối với ) nếu ta có
trong đó 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ệ đều tương thích với quan hệ tương đương .
C56. Cho là một quan hệ tương đương trên một tập hợp E, và cho là một quan hệ không chứa chữ cái và tương thích (đối với *) với quan hệ tương đương* . Khi đó, nếu không xuất hiện trong , thì quan hệ " và và *" tương đương với quan hệ "* và *".*
Cho . Nếu tồn tại sao cho , thì với mỗi ta có và do đó . Vì thế và kéo theo . Mệnh đề đảo lại là hiển nhiên vì kéo theo .
¶ Quan hệ
được gọi là cảm sinh bởi khi chuyển qua thương (đối với ) theo R. Nếu quan hệ này được ký hiệu bởi , và nếu là ánh xạ chính tắc từ E lên E/R, thì quan hệ
(trong đó không xuất hiện trong ) tương đương với ( và ), như kiểm tra ngay lập tức được.
4. Các tập con bão hòa
Cho 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ệ là tương thích (đối với ) với ; hoặc, tương đương, nếu với mỗi , lớp tương đương của đượ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 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 , lớp này bằng , được chứa trong A, và do đó ; vì trong mọi trường hợp ta đều có , suy ra . Ngược lại, nếu , thì với mọi lớp tương đương của đối với R là một phần tử của ; và vì , ta có . 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 . Tương đương, đó là các tập con của E có dạng , trong đó ; vì quan hệ suy ra , do đó .
¶ Nếu là một họ các tập con bão hòa của E, thì các tập hợp và 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ì 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 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ó , nên
Vì thế ta có thể nói rằng 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 là một họ các tập con của E và nếu là bão hòa của đối với R, thì bão hòa của là (§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 là một hàm có miền xác định là E. Khi đó người ta nói rằng là tương thích với quan hệ R nếu quan hệ là tương thích (đối với ) với quan hệ .
¶ Điều này tương đương với việc nói rằng hạn chế của 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 là hằng trên mỗi lớp tương đương đối với R. Nếu là ánh xạ chính tắc từ E lên E/R, thì một mệnh đề tương đương là quan hệ kéo theo ; 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 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 .
Ánh xạ được gọi là cảm sinh bởi f khi chuyển qua thương đối với R.
¶ Cho là một ánh xạ từ một tập hợp E vào một tập hợp F, và đặt . Cho R là quan hệ tương đương liên kết với (no. 2); hiển nhiên tương thích với R. Hơn nữa, ánh xạ cảm sinh bởi khi chuyển qua thương là một đơn ánh từ E/R vào F : vì nếu , là các lớp tương đương đối với R sao cho , thì ta có với mọi và , điều này suy ra theo định nghĩa của R. Cho là ánh xạ từ E/R lên A có cùng đồ thị với ; khi đó là song ánh. Nếu là đơn ánh chính tắc từ A vào F và nếu là ánh xạ chính tắc từ E lên E/R, thì ta có thể viết
Quan hệ này được gọi là phân tích chính tắc của f.
¶ Cho 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 là ánh xạ chính tắc từ E lên E/R, và cho là ánh xạ chính tắc từ lên . Ánh xạ được gọi là tương thích với các quan hệ tương đương và nếu tương thích với ; điều đó có nghĩa là quan hệ (mod ) kéo theo (mod ). Khi đó, ánh xạ từ vào được cảm sinh bởi khi chuyển qua thương theo được gọi là ánh xạ cảm sinh bởi khi chuyển qua các thương theo và ; nó được đặc trưng bởi hệ thức .
6. Ảnh ngược của một quan hệ tương đương; quan hệ tương đương cảm sinh
Cho là một ánh xạ của một tập hợp vào một tập hợp , và cho là một quan hệ tương đương trên . Nếu là ánh xạ chính tắc của lên , thì quan hệ tương đương liên kết với ánh xạ của vào được gọi là ảnh ngược của theo ; nếu là quan hệ này, thì tương đương với , và các lớp tương đương đối với là các ảnh ngược theo của các lớp tương đương đối với có giao với .
¶ Đặc biệt, xét một quan hệ tương đương trên một tập hợp , và cho là một tập con của ; khi đó ảnh ngược của dưới đơn ánh từ vào được gọi là quan hệ tương đương cảm sinh bởi trên , và được ký hiệu bởi .
¶ Các lớp tương đương đối với là các vết trên của các lớp tương đương đối với mà cắt . Phép đơn ánh hiển nhiên tương thích với các quan hệ và ; ánh xạ từ vào được cảm sinh bởi khi chuyển qua thương đối với và là một ánh xạ đơn ánh từ vào : vì nếu (tương ứng ) là ánh xạ chính tắc từ lên (tương ứng từ lên ), thì quan hệ , trong đó và , là tương đương với và do đó với . Ảnh bằng . Nếu là ánh xạ song ánh từ lên có cùng đồ thị như , thì 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 , là hai quan hệ tương đương đối với hai chữ , . Ta sẽ nói rằng mịn hơn (hoặc rằng thô hơn ) nếu quan hệ là đúng. Nếu và là các quan hệ tương đương trên cùng một tập hợp , mệnh đề nói rằng mịn hơn có nghĩa là đồ thị của được chứa trong đồ thị của , hay cũng là mọi lớp tương đương đối với đều được chứa trong một lớp tương đương đối với ; hoặc, tương đương, mọi lớp tương đương đối với đều bão hòa đối với .
Ví dụ
Ví dụ 1 03SF
Quan hệ " và và " mịn hơn mọi quan hệ tương đương trên E. Quan hệ " và " thô hơn mọi quan hệ tương đương trên E.
Ví dụ 2 03SG
\* Quan hệ tương đương " và và chia được cho 4" mịn hơn quan hệ tương đương " và và 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 và 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 tương thích với S. Gọi là hàm cảm sinh bởi khi chuyển qua thương đối với S; khi đó là một ánh xạ từ E/S lên E/R. Quan hệ tương đương liên kết với 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ệ tương đương với , và các lớp tương đương đối với R/S là các ảnh qua của các lớp tương đương đối với R. Gọi là phân tích chính tắc (no. 5) của ánh xạ . Khi đó là ánh xạ chính tắc từ E/S lên (E/S)/(R/S), là ánh xạ đồng nhất của E/R, và là một ánh xạ một-một từ (E/S)/(R/S) lên E/R. Ánh xạ 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 (no. 6). Vì quan hệ tương đương với , suy ra T tương đương với R/S.
8. Tích của hai quan hệ tương đương
Cho và là hai quan hệ tương đương. Gọi là quan hệ
ngay lập tức kiểm tra được rằng 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 . 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ệ tương đương với
tức là với và và , do đó với . Suy ra rằng là một quan hệ tương đương trên . Nếu
là một phần tử của , thì quan hệ tương đương với
nếu và lần lượt là các đồ thị của và , thì quan hệ này đến lượt nó lại tương đương với . Do đó mọi lớp tương đương đối với đều là tích của một lớp tương đương đối với và một lớp tương đương đối với , và ngược lại.
¶ Cho và là các ánh xạ chính tắc từ lên và từ lên , tương ứng, và gọi là phép mở rộng chính tắc của và lên các tập hợp tích (§ 3, no. 9). Khi đó với mọi . Ảnh ngược theo của một phần tử của chính là tích của lớp tương đương đối với và lớp tương đương đối với . Suy ra rằng quan hệ tương đương liên kết với là tương đương với . Do đó ánh xạ có thể được viết thành , trong đó là ánh xạ chính tắc từ lên
và là một ánh xạ một-một từ lên
ánh xạ 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 là một quan hệ trong đó các chữ , không xuất hiện. Ta nói P là tương thích với các quan hệ tương đương và (đối với và ) nếu quan hệ và và kéo theo . Cho là quan hệ và ; khi đó nói rằng tương thích (đối với ) với quan hệ tương đương , là tích của và , là một điều tương đương.
9. Các lớp đối tượng tương đương
Cho 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 , , là ba chữ phân biệt, thì quan hệ kéo theo "" và do đó cũng kéo theo quan hệ . Theo lược đồ S7 (Chương I, § 5, no. 1), nếu ta đặt , thì quan hệ kéo theo
Mặt khác, chú ý rằng theo định nghĩa là quan hệ và do đó (no. 1) tương đương với . Suy ra rằng quan hệ và và là tương đương với , vì theo S6 (Chương I, §5, no. 1) nó kéo theo quan hệ
do đó cũng kéo theo và , và sau cùng kéo theo theo tính bắc cầu và tính đối xứng. Và vì ngược lại kéo theo và , mệnh đề được chứng minh. Số hạng đượ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)
là đúng. Khi đó quan hệ and là xác định tập theo z. Thật vậy, ta có thể giả sử rằng kéo theo ; chỉ cần thay thế T bằng tập hợp mọi sao cho (nhận thấy rằng kéo theo ). Gọi là tập hợp mọi đối tượng có dạng với (§1, no. 6). Giả sử rằng là đúng; khi đó tồn tại sao cho và do đó . Tập hợp đượ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 sao cho , là phần tử duy nhất sao cho .
Dưới cùng giả thiết, cho là một số hạng sao cho suy ra . Khi đó quan hệ and xác định tập theo , vì , tương đương với , suy ra , và do đó nếu E là tập hợp các đối tượng có dạng với , thì suy ra . Nếu là hàm , thì quan hệ suy ra .
Đặ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 là lớp tương đương của x đối với R (no. 2), và khi đó hàm là một song ánh từ 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 là quan hệ tương đương " và là hai không gian vectơ có cùng số chiều hữu hạn trên "; 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 , hoặc khi tập con T' của T gồm các không gian với các quy ước rằng gồm điểm 0 của và rằng là tổng của thành phần đầu tiên của tổng trực tiếp . Với lựa chọn thứ hai này, ta có .\*
Bài tập
Xem bài tập cho § 6.