Chương 20: Quan hệ và hàm theo nghĩa tập hợp

Câu hỏi mở đầu

Tập hợp là những chiếc túi đồ vật tĩnh. Làm sao nói về mối liên kết giữa các phần tử: "nhỏ hơn", "cùng lớp với", "ứng với"?

Liên kết là một tập các cặp

"3 nhỏ hơn 5". "13 giờ cùng lớp với 1 giờ" (trên mặt đồng hồ của Chương 3). "Mỗi người ứng với một ngày sinh". Mỗi câu nói về hai đối tượng cùng lúc. Một tập hợp chỉ trả lời câu hỏi về từng đối tượng riêng lẻ; vậy mối liên kết giữa hai đối tượng nằm ở đâu? Nó không phải một đồ vật thứ ba nằm lơ lửng giữa 3 và 5.

Chương 19 đã có sẵn lời giải, chỉ cần dùng lại. Một tập được biết hoàn toàn qua câu hỏi "thuộc hay không" đặt cho từng đối tượng. Một mối liên kết cũng vậy: nó được biết hoàn toàn qua câu hỏi "có liên kết hay không" đặt cho từng cặp. Với các số 1, 2, 3, 4, câu "\(a\) nhỏ hơn \(b\)" đúng với đúng sáu cặp:

\[ \{(1; 2); (1; 3); (1; 4); (2; 3); (2; 4); (3; 4)\}. \]

Biết tập này là biết mọi điều về "nhỏ hơn" trên bốn số ấy. Cặp phải có thứ tự, vì "1 nhỏ hơn 2" khác "2 nhỏ hơn 1"; và mọi cặp có thể có tạo thành tích Descartes \(\{1; 2; 3; 4\} \times \{1; 2; 3; 4\}\). Vậy mỗi mối liên kết là một tập con của một tích Descartes. Đó là toàn bộ định nghĩa.

Vì sao cấu trúc này phải xuất hiện, dù chưa ai đặt tên cho nó? Vì mỗi khi có một câu hỏi có hoặc không về hai đối tượng, đặt câu hỏi ấy cho mọi cặp là tự động tách ra một tập con của tích Descartes; không cần gì thêm. Cái giá là ta bỏ đi "lý do" của liên kết. "\(a\) nhỏ hơn \(b\)", "\(b - a\) là số dương" và "\(a\) nằm bên trái \(b\) trên trục số" là ba cách nói với ba lý do khác nhau, nhưng cho cùng một tập cặp, nên toán học coi chúng là một. Chương 22 sẽ quay lại mặt "quy luật" mà cách nhìn này gác sang một bên.

Có ba cách trình bày một tập cặp, và mỗi cách làm lộ ra những điều khác nhau: liệt kê như trên; vẽ một lưới, trong đó ô ở hàng \(a\), cột \(b\) được tô khi cặp \((a; b)\) thuộc tập; hoặc vẽ mũi tên từ \(a\) tới \(b\).

Quan hệ "nhỏ hơn" trên \(\{1; 2; 3; 4\}\) vẽ theo hai cách. Sáu ô tô của lưới và sáu mũi tên ứng với đúng sáu cặp trong tập ở trên.

Ba kiểu liên kết

Ba chữ trong câu hỏi mở đầu ứng với ba kiểu liên kết mà toán học dùng nhiều nhất. Mỗi kiểu được nhận ra bằng vài tính chất đơn giản của tập cặp.

"Cùng lớp với" là kiểu của Chương 3: phản xạ, đối xứng, bắc cầu. Trên lưới, cả đường chéo được tô, và hình tô đối xứng qua đường chéo. Nếu xếp các phần tử cùng lớp cạnh nhau, các ô tô gom thành những khối vuông rời nhau, mỗi khối là một lớp.

"Nhỏ hơn hoặc bằng" là kiểu xếp hàng. Nó phản xạ và bắc cầu, nhưng thay cho tính đối xứng là một tính chất gần như ngược lại: hai đối tượng khác nhau không bao giờ đứng trước nhau theo cả hai chiều; nếu \(a \leq b\) và \(b \leq a\) thì \(a = b\). Trên lưới, không ô tô nào ngoài đường chéo có ô đối xứng với nó cũng được tô. Quan hệ "nhỏ hơn hẳn" \(<\) là quan hệ ấy bỏ đi các ô trên đường chéo; người ta lấy \(\leq\) làm mẫu vì nó phản xạ.

"Ứng với" là kiểu của phép gán: mỗi đối tượng bên trái ứng với đúng một đối tượng bên phải, như mỗi người ứng với một ngày sinh. Trên lưới, mỗi hàng có đúng một ô tô; trên hình mũi tên, mỗi điểm bên trái có đúng một mũi tên đi ra. Đây là khái niệm quan trọng nhất của chương. Chương 6 gọi nó là biến đổi, Chương 15 gọi nó là quy tắc \(f\) gán cho mỗi \(x\) một số \(f(x)\). Giờ nó có một định nghĩa không cần đến chữ "quy tắc": một tập cặp mà mỗi phần tử bên trái đứng đầu đúng một cặp.

Mỗi điểm của \(A\) phải có đúng một mũi tên đi ra. Hai điểm được phép chung một đích (hình trái); một điểm có hai mũi tên, hay không có mũi tên nào, thì không được.

Với phép gán, còn hai câu hỏi về phía bên phải. Có hai điểm bên trái nào bị dồn về cùng một đích không? Chương 6 gọi việc ấy là mất thông tin. Có điểm bên phải nào mà không mũi tên nào chạm tới không? Đó là bỏ sót. Hai câu hỏi ấy sinh ra ba khái niệm ở mục sau.

Hình trái không dồn hai điểm về một đích nhưng bỏ sót \(d\); hình giữa không bỏ sót đích nào nhưng dồn 1 và 2 về \(a\); hình phải không mất, không sót, nên các mũi tên ghép hai bên thành từng cặp.

Ký hiệu

Theo nghĩa tập hợp, một quan hệ (relation) từ \(A\) tới \(B\) là một tập con \(R \subseteq A \times B\); khi \(B = A\), ta nói \(R\) là một quan hệ trên \(A\). Viết \(a \mathrel{R} b\) thay cho \((a; b) \in R\). Các dấu quen thuộc \(<\), \(\leq\), \(\sim\), \(\mid\) đều là tên của những tập cặp như thế.

Với một quan hệ \(R\) trên \(A\), ngoài ba tính chất phản xạ, đối xứng, bắc cầu của Chương 3, có thêm tính phản đối xứng (antisymmetric): nếu \(a \mathrel{R} b\) và \(b \mathrel{R} a\) thì \(a = b\). Quan hệ phản xạ, phản đối xứng và bắc cầu là một quan hệ thứ tự (order relation). Nếu thêm nữa mọi hai phần tử \(a\), \(b\) đều so sánh được, tức \(a \mathrel{R} b\) hoặc \(b \mathrel{R} a\), đó là một thứ tự toàn phần (total order), như \(\leq\) trên \(\mathbb{R}\).

Với một quan hệ tương đương \(\sim\) trên \(A\), lớp \([a] = \{x \in A \mid x \sim a\}\) như ở Chương 3, và tập mọi lớp gọi là tập thương (quotient set):

\[ A/{\sim} = \{[a] \mid a \in A\}. \]

Mỗi phần tử của tập thương là một lớp, tức một tập; tập thương là một tập của các tập.

Một hàm (function) từ \(A\) tới \(B\), còn gọi là ánh xạ (map), là một quan hệ \(f \subseteq A \times B\) mà mỗi \(a \in A\) đứng đầu đúng một cặp \((a; b) \in f\). Phần tử \(b\) ấy viết là \(f(a)\), gọi là giá trị của \(f\) tại \(a\). Ta viết \(f: A \to B\), và \(a \mapsto f(a)\) như ở Chương 6. Tập \(A\) là miền xác định (domain), tập \(B\) là đối miền (codomain), và tập các giá trị thật sự đạt được,

\[ f(A) = \{f(a) \mid a \in A\}, \]

là tập ảnh (image), một tập con của \(B\). Khi \(A\) và \(B\) là những tập số, người ta thường nói hàm số, như ở Chương 15. Một hàm \(f: A \to B\) là:

• đơn ánh (injection) nếu hai phần tử khác nhau của \(A\) luôn cho hai giá trị khác nhau: không mất thông tin;
• toàn ánh (surjection) nếu mọi phần tử của \(B\) đều là giá trị tại ít nhất một phần tử của \(A\), tức \(f(A) = B\): không bỏ sót;
• song ánh (bijection) nếu vừa là đơn ánh vừa là toàn ánh.

Nếu một hàm \(g: B \to A\) tháo ngược \(f\) theo cả hai chiều, tức \(g(f(a)) = a\) với mọi \(a \in A\) và \(f(g(b)) = b\) với mọi \(b \in B\), thì \(g\) gọi là hàm ngược (inverse function) của \(f\), viết \(f^{-1}\). Số mũ \(-1\) ở đây không phải nghịch đảo: \(f^{-1}(b)\) khác \(\frac{1}{f(b)}\).

Trên lưới của một quan hệ \(f \subseteq A \times B\), với hàng là các phần tử của \(A\) và cột là các phần tử của \(B\):

Tính chất	Trên lưới
\(f\) là một hàm	mỗi hàng có đúng một ô tô
đơn ánh	thêm nữa, mỗi cột có nhiều nhất một ô tô
toàn ánh	thêm nữa, mỗi cột có ít nhất một ô tô
song ánh	mỗi hàng và mỗi cột có đúng một ô tô

Làm bằng tay

Ví dụ 1 (bốn quan hệ trên \(\{1; 2; 3; 4\}\)). Xét bốn quan hệ: "\(a\) là ước của \(b\)" (chia hết), "\(a < b\)" (nhỏ hơn), "\(a\) và \(b\) cùng tính chẵn lẻ", và "\(|a - b| \leq 1\)" (gần nhau).

Bốn quan hệ trên \(\{1; 2; 3; 4\}\). Ô ở hàng \(a\), cột \(b\) được tô khi \(a\) có quan hệ với \(b\).

Đọc các tính chất ngay trên lưới:

Quan hệ	Phản xạ	Đối xứng	Phản đối xứng	Bắc cầu	Kiểu
chia hết	Đ	S	Đ	Đ	thứ tự
nhỏ hơn	S	S	Đ	Đ	thiếu phản xạ
cùng chẵn lẻ	Đ	Đ	S	Đ	tương đương
gần nhau	Đ	Đ	S	S	không kiểu nào

Chia hết không đối xứng vì \(1 \mid 2\) mà \(2 \nmid 1\). Nó phản đối xứng: với \(a\), \(b\) dương, \(a \mid b\) cho \(a \leq b\), nên \(a \mid b\) và \(b \mid a\) cho \(a = b\). "Nhỏ hơn" phản đối xứng một cách trống rỗng: không bao giờ có cả \(a < b\) lẫn \(b < a\). "Cùng chẵn lẻ" không phản đối xứng, vì 1 và 3 liên quan theo cả hai chiều mà \(1 \neq 3\); xếp lại thứ tự thành 1, 3, 2, 4 thì lưới của nó thành hai khối vuông, đúng hai lớp \(\{1; 3\}\) và \(\{2; 4\}\). "Gần nhau" không bắc cầu: 1 gần 2, 2 gần 3, mà 1 không gần 3.

Ví dụ 2 (đồng dư theo 4). Trên \(\mathbb{Z}\), đặt \(a \sim b\) khi \(a - b\) chia hết cho 4, tức \(a \equiv b \pmod 4\) theo cách viết của Chương 8. Đây là một quan hệ tương đương: phản xạ vì \(a - a = 0\); đối xứng vì \(b - a = -(a - b)\); bắc cầu vì \(a - c = (a - b) + (b - c)\). Có đúng bốn lớp, ứng với bốn số dư:

\[ [0] = \{\dots; -8; -4; 0; 4; 8; \dots\}, \qquad [1] = \{\dots; -7; -3; 1; 5; 9; \dots\}, \]

và tương tự \([2]\), \([3]\). Tập thương \(\mathbb{Z}/{\sim} = \{[0]; [1]; [2]; [3]\}\) có bốn phần tử, dù mỗi phần tử là một tập vô hạn. Một lớp có nhiều tên: \([7] = [3] = [-1]\).

Bốn lớp đồng dư theo 4 như bốn ngăn kéo: mỗi số nguyên nằm trong đúng một ngăn. Số màu xanh là số dư, đại diện quen dùng nhất của mỗi ngăn.

Ví dụ 3 (đếm hàm). Có bao nhiêu hàm từ \(A = \{1; 2; 3\}\) tới \(B = \{a; b\}\)? Một hàm là ba lựa chọn \(f(1)\), \(f(2)\), \(f(3)\), mỗi lựa chọn có hai khả năng, nên có \(2 \cdot 2 \cdot 2 = 8\) hàm. Trong đó:

• toàn ánh: mọi hàm trừ hai hàm gửi cả ba phần tử về cùng một đích, tức 6 toàn ánh;
• đơn ánh: không có. Ba phần tử, hai đích, nên hai phần tử phải chung một đích: đó chính là nguyên lý chuồng bồ câu của Chương 17.

Tổng quát, từ một tập \(m\) phần tử tới một tập \(n\) phần tử có \(n^m\) hàm, vì mỗi phần tử trong \(m\) phần tử chọn một trong \(n\) đích. Khi đích là \(\{\text{có}; \text{không}\}\), mỗi hàm chọn ra một tập con của \(A\) (những phần tử được gán "có"), và ta gặp lại \(2^m\) tập con của Chương 19.

Ví dụ 4 (hàm ngược của \(f(x) = 3x + 2\)). Xét \(f: \mathbb{R} \to \mathbb{R}\), \(f(x) = 3x + 2\).

• Đơn ánh: nếu \(3x + 2 = 3x' + 2\) thì \(3x = 3x'\), nên \(x = x'\).
• Toàn ánh: cho \(y \in \mathbb{R}\), số \(x = \frac{y - 2}{3}\) cho \(f(x) = y\).

Vậy \(f\) là song ánh, và \(f^{-1}(y) = \frac{y - 2}{3}\): "trừ 2 rồi chia cho 3", tháo từng bước theo thứ tự ngược như ở Chương 6. Kiểm lại: \(f^{-1}(f(x)) = \frac{3x + 2 - 2}{3} = x\) và \(f(f^{-1}(y)) = 3 \cdot \frac{y - 2}{3} + 2 = y\). Chẳng hạn \(f(3) = 11\) và \(f^{-1}(11) = 3\).

Cùng công thức ấy, nhưng như một hàm \(\mathbb{Z} \to \mathbb{Z}\), vẫn là đơn ánh mà không còn là toàn ánh: \(3x + 2 = 1\) cho \(x = -\frac13 \notin \mathbb{Z}\). Tập ảnh gồm các số nguyên chia cho 3 dư 2, như \(-1\), 2, 5, 8. Không có hàm ngược từ \(\mathbb{Z}\) về \(\mathbb{Z}\); chỉ tháo ngược được trên tập ảnh.

Ví dụ 5 (song ánh và đếm). Chương 4 định nghĩa "cùng số lượng" bằng một tương ứng một-một: ghép mỗi phần tử của \(A\) với đúng một phần tử của \(B\), sao cho mỗi phần tử của \(B\) được ghép với đúng một phần tử của \(A\). Ghi cách ghép ấy thành tập các cặp đã ghép, ta được một quan hệ mà mỗi hàng và mỗi cột của lưới có đúng một ô: một song ánh. Định nghĩa của Chương 4 giờ chỉ dùng tập hợp: có \(n\) phần tử nghĩa là có một song ánh tới \(\{1; 2; \dots; n\}\).

Có bao nhiêu song ánh từ \(\{1; 2; 3\}\) tới \(\{a; b; c\}\)? Chọn \(f(1)\): 3 cách; \(f(2)\) phải khác \(f(1)\): 2 cách; \(f(3)\) là đích còn lại: 1 cách. Tổng cộng \(3 \cdot 2 \cdot 1 = 3! = 6\) song ánh, với giai thừa của Chương 18. Mỗi song ánh là một cách xếp ba đồ vật vào ba chỗ.

Ví dụ 6 (một thứ tự không toàn phần). Quan hệ chia hết trên tập các ước của 12, \(\{1; 2; 3; 4; 6; 12\}\), là một quan hệ thứ tự. Vẽ mũi tên từ \(a\) tới \(b\) khi \(b\) là bội của \(a\) và không có số \(c\) nào khác trong tập nằm "giữa" hai số theo nghĩa \(a \mid c\) và \(c \mid b\):

flowchart BT
  n1["1"] --> n2["2"]
  n1 --> n3["3"]
  n2 --> n4["4"]
  n2 --> n6["6"]
  n3 --> n6
  n4 --> n12["12"]
  n6 --> n12

Đi theo mũi tên là đi tới một bội. Hai số 4 và 6 không so sánh được: không số nào là ước của số kia. Vậy chia hết không phải thứ tự toàn phần, khác với \(\leq\), nơi mọi hai số đều xếp được trước sau. Một thứ tự có thể rẽ nhánh rồi nhập lại, chứ không nhất thiết là một hàng thẳng.

Ranh giới

Căn bậc hai: hai giá trị, rồi một lựa chọn. Quan hệ "\(y^2 = x\)" từ \(\mathbb{R}\) tới \(\mathbb{R}\) không phải một hàm, vì hai lẽ: với \(x = 4\) có hai giá trị \(y = 2\) và \(y = -2\) (một hàng có hai ô tô), còn với \(x = -1\) không có \(y\) nào (một hàng trống). Muốn có một hàm, phải làm hai việc: thu miền xác định về các số không âm, và chọn một trong hai giá trị, lấy giá trị không âm. Hàm \(\sqrt{x}\) quen thuộc là kết quả của hai quyết định ấy, đúng như định nghĩa ở Chương 11: \(\sqrt{a}\) là số không âm có bình phương bằng \(a\). Cách viết \(\pm\sqrt{x}\) nhắc rằng quan hệ ban đầu có hai nhánh.

Cùng công thức, khác hàm. Hàm \(n \mapsto n^2\) từ \(\mathbb{N}\) tới \(\mathbb{N}\) là đơn ánh: với \(m, n \geq 0\), từ \(m^2 = n^2\) suy ra \(m = n\). Cùng công thức ấy từ \(\mathbb{Z}\) tới \(\mathbb{Z}\) thì không, vì \((-2)^2 = 2^2\). Tính toàn ánh còn phụ thuộc vào đối miền: \(x \mapsto x^2\) từ \(\mathbb{R}\) tới \(\mathbb{R}\) không là toàn ánh (\(-1\) không đạt được), nhưng từ \(\mathbb{R}\) tới tập các số thực không âm thì là toàn ánh. Một hàm gồm ba thứ, miền xác định, đối miền và các cặp; công thức chỉ là một cách mô tả các cặp. Ngược lại, hai công thức khác nhau có thể cho cùng một hàm: trên \(\mathbb{R}\), \(\sqrt{x^2}\) và \(|x|\) cho cùng mọi cặp.

Phản đối xứng không có nghĩa là "không đối xứng". Quan hệ "\(=\)" vừa đối xứng vừa phản đối xứng. Quan hệ \(\{(1; 2); (2; 1); (1; 3)\}\) trên \(\{1; 2; 3\}\) thì không có tính nào trong hai: nó không đối xứng vì có \((1; 3)\) mà thiếu \((3; 1)\), và không phản đối xứng vì có cả \((1; 2)\) lẫn \((2; 1)\). Mỗi tính chất là một câu "với mọi cặp"; phủ định của nó chỉ cần một cặp hỏng (Chương 15), và hai phủ định có thể cùng đúng.

Đơn ánh chưa đủ để có hàm ngược. Hàm \(f(n) = n + 1\) từ \(\mathbb{N}\) tới \(\mathbb{N}\) là đơn ánh, và "trừ 1" tháo ngược nó: \((n + 1) - 1 = n\). Nhưng 0 không phải giá trị của \(f\) tại số nào, nên dù chọn \(g(0)\) là gì, \(f(g(0)) = g(0) + 1 \geq 1\), không bằng 0. Đây chính là điều Chương 6 gặp khi dựng phép ngược của "cộng \(b\)" chỉ trên các số \(y \geq b\). Chương ấy gọi một biến đổi là khả nghịch khi nó không dồn hai đầu vào về một đầu ra, tức là đơn ánh, và dựng phép ngược trên những đầu ra đạt được, tức trên tập ảnh. Thu đối miền về tập ảnh thì mọi đơn ánh thành song ánh, và phép ngược của Chương 6 chính là hàm ngược của song ánh ấy.

Không bắc cầu thì không chia lớp được. Quan hệ "gần nhau" của Ví dụ 1 phản xạ và đối xứng nhưng không bắc cầu, như "trông như nhau" với dãy cốc nước ở Chương 3. Các ô tô của nó xếp thành một dải dọc đường chéo, và không cách xếp lại nào gom được chúng thành những khối vuông rời nhau.

Phát biểu chặt chẽ

Định nghĩa 1 (quan hệ). Một quan hệ từ \(A\) tới \(B\) là một tập con \(R \subseteq A \times B\); một quan hệ trên \(A\) là một tập con \(R \subseteq A \times A\). Quan hệ \(R\) trên \(A\) là:

• phản xạ nếu \(\forall a \in A\ (a \mathrel{R} a)\);
• đối xứng nếu \(\forall a, b \in A\ (a \mathrel{R} b \Rightarrow b \mathrel{R} a)\);
• phản đối xứng nếu \(\forall a, b \in A\ \big((a \mathrel{R} b \land b \mathrel{R} a) \Rightarrow a = b\big)\);
• bắc cầu nếu \(\forall a, b, c \in A\ \big((a \mathrel{R} b \land b \mathrel{R} c) \Rightarrow a \mathrel{R} c\big)\).

\(R\) là quan hệ tương đương nếu nó phản xạ, đối xứng và bắc cầu; là quan hệ thứ tự nếu nó phản xạ, phản đối xứng và bắc cầu.

Định lý 2 (quan hệ tương đương và phân hoạch). Cho \(\sim\) là một quan hệ tương đương trên \(A\). Với mọi \(a, b \in A\):

(a) \(a \in [a]\);

(b) \(a \sim b\) khi và chỉ khi \([a] = [b]\);

(c) nếu \([a] \neq [b]\) thì \([a] \cap [b] = \varnothing\).

Do đó tập thương \(A/{\sim}\) là một phân hoạch của \(A\). Hơn nữa, hai phần tử nằm trong cùng một lớp khi và chỉ khi chúng tương đương.

Chứng minh. (a) Tính phản xạ cho \(a \sim a\). (b) Chiều thuận là Mệnh đề 1(b) của Chương 3. Chiều ngược: nếu \([a] = [b]\) thì theo (a), \(a \in [a] = [b]\), tức \(a \sim b\). (c) Ta chứng minh phản đảo: giả sử có \(x \in [a] \cap [b]\), tức \(x \sim a\) và \(x \sim b\). Tính đối xứng cho \(a \sim x\), rồi tính bắc cầu cho \(a \sim b\), nên theo (b), \([a] = [b]\).

Các lớp khác rỗng theo (a), phủ kín \(A\) vì mỗi \(a\) nằm trong \([a]\), và hai lớp khác nhau thì rời nhau theo (c): đó đúng là một phân hoạch. Cuối cùng, nếu \(a\) và \(b\) cùng nằm trong một lớp \([c]\) thì \(a \sim c\) và \(b \sim c\), nên theo (b), \([a] = [c] = [b]\), tức \(a \sim b\); ngược lại, nếu \(a \sim b\) thì cả hai nằm trong \([b]\). \(\square\)

Mệnh đề 2 của Chương 3 đi theo chiều ngược: mỗi phân hoạch cho một quan hệ tương đương mà các lớp đúng là các mảnh của phân hoạch. Định lý 2 nói thêm rằng quan hệ dựng lại từ các lớp chính là quan hệ ban đầu. Vậy hai cách đi, từ quan hệ tương đương tới phân hoạch và ngược lại, tháo ngược nhau: "cùng lớp với" và "chia thành ngăn" là một cấu trúc, như Chương 3 đã hứa.

Định nghĩa 3 (hàm). Một hàm \(f: A \to B\) là một quan hệ \(f \subseteq A \times B\) sao cho

\[ \forall a \in A\ \exists b \in B\ \ (a; b) \in f \qquad \text{và} \qquad \forall a \in A\ \forall b, b' \in B\ \big((a; b) \in f \land (a; b') \in f \Rightarrow b = b'\big). \]

Hai hàm cùng miền xác định \(A\) và cùng đối miền \(B\) bằng nhau khi chúng có cùng giá trị tại mọi \(a \in A\), tức khi chúng là cùng một tập cặp.

Định nghĩa 4 (đơn ánh, toàn ánh, song ánh). Hàm \(f: A \to B\) là đơn ánh nếu \(\forall a, a' \in A\ \big(f(a) = f(a') \Rightarrow a = a'\big)\); là toàn ánh nếu \(\forall b \in B\ \exists a \in A\ \ f(a) = b\); là song ánh nếu nó vừa là đơn ánh vừa là toàn ánh.

Định lý 5 (hàm ngược). Hàm \(f: A \to B\) có hàm ngược khi và chỉ khi \(f\) là song ánh. Khi đó hàm ngược là duy nhất, và nó là tập các cặp của \(f\) đảo thứ tự:

\[ f^{-1} = \{(b; a) \mid (a; b) \in f\}. \]

Chứng minh. Giả sử \(g: B \to A\) là một hàm ngược của \(f\). Nếu \(f(a) = f(a')\) thì \(a = g(f(a)) = g(f(a')) = a'\), nên \(f\) là đơn ánh. Với mọi \(b \in B\), phần tử \(a = g(b)\) cho \(f(a) = f(g(b)) = b\), nên \(f\) là toàn ánh.

Ngược lại, giả sử \(f\) là song ánh. Với mỗi \(b \in B\), có ít nhất một \(a\) mà \(f(a) = b\) (toàn ánh) và nhiều nhất một \(a\) như thế (đơn ánh). Đặt \(g(b)\) là phần tử \(a\) duy nhất ấy. Theo cách đặt, \(f(g(b)) = b\). Với \(a \in A\), \(g(f(a))\) là phần tử duy nhất có giá trị \(f(a)\), mà \(a\) là một phần tử như thế, nên \(g(f(a)) = a\). Vậy \(g\) là một hàm ngược, và các cặp của nó đúng là các cặp \((f(a); a)\).

Duy nhất: nếu \(g\) và \(h\) đều là hàm ngược của \(f\) thì với mọi \(b \in B\), \(g(b) = g(f(h(b))) = h(b)\). \(\square\)

Đảo thứ tự các cặp của bất kỳ quan hệ nào cũng cho một quan hệ; trên lưới, đó là đổi vai hàng và cột. Định lý 5 nói rằng với một hàm, quan hệ đảo ấy là một hàm đúng khi hàm ban đầu là song ánh.

Mệnh đề 6 (cùng số lượng). Hai tập \(A\) và \(B\) có cùng số lượng theo Định nghĩa 2 của Chương 4 khi và chỉ khi có một song ánh \(f: A \to B\).

Chứng minh. Ghi một tương ứng một-một thành tập các cặp đã ghép, ta được một tập \(R \subseteq A \times B\) mà mỗi \(a\) đứng đầu đúng một cặp, tức \(R\) là một hàm \(A \to B\), và mỗi \(b\) đứng sau đúng một cặp, tức hàm ấy nhận giá trị \(b\) tại nhiều nhất một phần tử (đơn ánh) và ít nhất một phần tử (toàn ánh). Ngược lại, các cặp \((a; f(a))\) của một song ánh \(f\) là một cách ghép đúng như Chương 4 đòi hỏi. \(\square\)

Nói theo ngôn ngữ này, nguyên lý chuồng bồ câu khẳng định: nếu \(A\), \(B\) hữu hạn và \(|A| > |B|\) thì không có đơn ánh nào từ \(A\) tới \(B\).

Sợi chỉ

• S2. Thông tin và khả nghịch. Đơn ánh là "không mất thông tin" của Chương 6, toàn ánh là "không bỏ sót", và song ánh, có cả hai, là đúng những hàm có hàm ngược (Định lý 5). Hàm ngược chỉ là đảo các cặp. Từ một tập 3 phần tử vào một tập 2 phần tử, mọi hàm đều mất thông tin.
• S1. Bất biến qua biến đổi. Đi từ \(a\) tới lớp \([a]\) là giữ lại cái bất biến và quên phần còn lại: lớp đồng dư theo 4 chỉ nhớ số dư. Một phép toán trên các lớp chỉ có nghĩa khi kết quả không phụ thuộc vào đại diện được chọn (bài C3).
• S6. Biểu diễn khác nhau của cùng một cấu trúc. Một quan hệ là tập cặp, là lưới, là hình mũi tên. Hàm là "mỗi hàng một ô", song ánh là "mỗi hàng, mỗi cột một ô", hàm ngược là đổi vai hàng và cột. Một hàm từ \(A\) tới \(\{\text{có}; \text{không}\}\) là một tập con của \(A\). Quan hệ tương đương và phân hoạch là một.

Tóm tắt

• Một quan hệ từ \(A\) tới \(B\) là một tập con của \(A \times B\): nó được biết hoàn toàn qua các cặp có liên kết, như một tập được biết qua các phần tử.
• Quan hệ tương đương (phản xạ, đối xứng, bắc cầu) là "cùng lớp với"; quan hệ thứ tự (phản xạ, phản đối xứng, bắc cầu) là "xếp trước sau", và có thể không toàn phần, như chia hết.
• Các lớp tương đương tạo thành tập thương, một phân hoạch; quan hệ tương đương và phân hoạch xác định lẫn nhau.
• Một hàm \(f: A \to B\) là quan hệ mà mỗi \(a\) ứng với đúng một \(f(a)\); nó gồm miền xác định, đối miền và các cặp, không chỉ là một công thức.
• Đơn ánh không mất thông tin, toàn ánh không bỏ sót, song ánh làm được cả hai; một hàm có hàm ngược khi và chỉ khi nó là song ánh, và hàm ngược là các cặp đảo chiều.
• Từ tập \(m\) phần tử tới tập \(n\) phần tử có \(n^m\) hàm; giữa hai tập \(n\) phần tử có \(n!\) song ánh.
• "Cùng số lượng" của Chương 4 là "có song ánh"; nguyên lý chuồng bồ câu nói không có đơn ánh từ một tập hữu hạn vào một tập ít phần tử hơn.

Bài tập

A. Tư duy

A1. Mục đầu chương đưa ra ba mô tả bằng lời cho cùng tập sáu cặp của "nhỏ hơn" trên \(\{1; 2; 3; 4\}\). Hãy tìm thêm một mô tả nữa. Đồng nhất một quan hệ với tập cặp của nó thì được gì và mất gì?

Lời giải

Chẳng hạn "khi đếm từ 1, \(a\) được đọc tới trước \(b\)", hay "có một số tự nhiên \(k \geq 1\) với \(a + k = b\)". Cái được: một định nghĩa chính xác, không phụ thuộc vào lời nói, và hai quan hệ được so sánh đúng như hai tập (Chương 19): cùng các cặp thì là một. Cái mất: lý do. Tập cặp không cho biết vì sao \((1; 3)\) thuộc nó. Với tập vô hạn như \(\mathbb{R}\), ta cũng không liệt kê được các cặp, nên vẫn cần một mô tả để nắm được quan hệ; nhưng mô tả chỉ là cách chỉ ra tập cặp, không phải bản thân quan hệ.

A2. Một người nói: "Hàm là một công thức." Chỉ ra ba chỗ câu này không đúng.

Lời giải

Thứ nhất, cùng một công thức với miền xác định khác nhau là hai hàm khác nhau: \(n \mapsto n^2\) là đơn ánh trên \(\mathbb{N}\) nhưng không là đơn ánh trên \(\mathbb{Z}\). Thứ hai, có những hàm không cần công thức nào: "mỗi người ứng với ngày sinh của mình", hay một hàm cho bằng bảng như ở Ví dụ 3. Thứ ba, hai công thức khác nhau có thể cho cùng một hàm: trên \(\mathbb{R}\), \(\sqrt{x^2} = |x|\) với mọi \(x\). Một hàm là miền xác định, đối miền và tập cặp; công thức chỉ là một cách nén tập cặp lại.

A3. Chương 6 gọi phép "cộng 3" trên các số tự nhiên là khả nghịch, và phép ngược "trừ 3" chỉ dùng cho các số từ 3 trở lên. Hàm \(n \mapsto n + 3\) từ \(\mathbb{N}\) tới \(\mathbb{N}\) là đơn ánh, toàn ánh hay song ánh? Vì sao phép ngược chỉ xác định trên các số \(\geq 3\)? Trên \(\mathbb{Z}\) thì sao?

Lời giải

Nó là đơn ánh (\(n + 3 = m + 3\) kéo theo \(n = m\)) nhưng không là toàn ánh: tập ảnh là \(\{3; 4; 5; \dots\}\), và 0, 1, 2 không đạt được. Phép ngược "trừ 3" chỉ có nghĩa trên tập ảnh; coi \(n \mapsto n + 3\) là hàm từ \(\mathbb{N}\) lên \(\{3; 4; 5; \dots\}\) thì nó là song ánh, với hàm ngược \(m \mapsto m - 3\). Trên \(\mathbb{Z}\), mọi số nguyên \(m\) đều bằng \((m - 3) + 3\), nên \(n \mapsto n + 3\) là song ánh từ \(\mathbb{Z}\) tới \(\mathbb{Z}\).

B. Tính toán

B1. Trên \(A = \{1; 2; 3\}\), liệt kê các cặp của quan hệ "\(a \leq b\)" và của quan hệ "\(a + b\) là số chẵn". Mỗi quan hệ có những tính chất nào trong bốn tính chất?

Lời giải

"\(a \leq b\)": \(\{(1; 1); (1; 2); (1; 3); (2; 2); (2; 3); (3; 3)\}\), sáu cặp. Nó phản xạ, phản đối xứng, bắc cầu, không đối xứng: một thứ tự, và là thứ tự toàn phần.

"\(a + b\) chẵn": \(\{(1; 1); (1; 3); (2; 2); (3; 1); (3; 3)\}\), năm cặp. Nó phản xạ, đối xứng, bắc cầu, không phản đối xứng (\((1; 3)\) và \((3; 1)\) cùng có mặt): một quan hệ tương đương với hai lớp \(\{1; 3\}\) và \(\{2\}\).

B2. Trên \(\{1; 2; 3\}\), xét \(R_1 = \{(1; 1); (2; 2); (3; 3); (1; 2); (2; 1)\}\), \(R_2 = \{(1; 2); (2; 3); (1; 3)\}\) và \(R_3 = \{(1; 1); (2; 2); (3; 3); (1; 2); (2; 3)\}\). Mỗi quan hệ có những tính chất nào? Quan hệ nào là tương đương, quan hệ nào là thứ tự?

Lời giải

\(R_1\): phản xạ, đối xứng, bắc cầu, không phản đối xứng. Là quan hệ tương đương, với hai lớp \(\{1; 2\}\) và \(\{3\}\).

\(R_2\): không phản xạ, không đối xứng, phản đối xứng, bắc cầu (cặp nối tiếp duy nhất là \((1; 2)\), \((2; 3)\), và \((1; 3)\) có mặt). Không là tương đương, cũng không là thứ tự vì thiếu phản xạ: đó là quan hệ "\(<\)".

\(R_3\): phản xạ, phản đối xứng, không đối xứng, không bắc cầu (có \((1; 2)\) và \((2; 3)\) mà thiếu \((1; 3)\)). Không là kiểu nào; thêm \((1; 3)\) thì thành "\(\leq\)".

B3. Liệt kê mọi phân hoạch của \(\{1; 2; 3\}\). Với mỗi phân hoạch, quan hệ tương đương tương ứng gồm bao nhiêu cặp? Trên \(\{1; 2; 3\}\) có bao nhiêu quan hệ tương đương?

Lời giải

Có năm phân hoạch: \(\{\{1\}; \{2\}; \{3\}\}\) cho 3 cặp (chỉ các cặp \((a; a)\)); \(\{\{1; 2\}; \{3\}\}\), \(\{\{1; 3\}; \{2\}\}\), \(\{\{2; 3\}; \{1\}\}\), mỗi cái cho 5 cặp; \(\{\{1; 2; 3\}\}\) cho cả 9 cặp. Một mảnh có \(k\) phần tử góp \(k^2\) cặp, như một khối vuông \(k \times k\) trên lưới. Theo Định lý 2 và Mệnh đề 2 của Chương 3, quan hệ tương đương và phân hoạch ứng với nhau một-một, nên có đúng 5 quan hệ tương đương.

B4. Với đồng dư theo 4 trên \(\mathbb{Z}\): (a) 2026 và \(-3\) nằm trong lớp nào, và có cùng lớp không? (b) Liệt kê các phần tử của \([3]\) từ \(-10\) đến \(10\).

Lời giải

(a) \(2026 = 4 \cdot 506 + 2\), nên \(2026 \in [2]\); \(-3 = 4 \cdot (-1) + 1\), nên \(-3 \in [1]\). Hai lớp khác nhau; kiểm lại: \(2026 - (-3) = 2029\) không chia hết cho 4. (b) \(-9\), \(-5\), \(-1\), \(3\), \(7\).

B5. Tập nào sau đây là một hàm từ \(\{1; 2; 3\}\) tới \(\{a; b; c\}\)? Với mỗi hàm, cho biết nó có là đơn ánh, toàn ánh không, và tìm hàm ngược nếu có. (a) \(\{(1; a); (2; a); (3; b)\}\); (b) \(\{(1; a); (2; b)\}\); (c) \(\{(1; a); (1; b); (2; c); (3; c)\}\); (d) \(\{(1; c); (2; a); (3; b)\}\).

Lời giải

(a) Là hàm; không đơn ánh (1 và 2 cùng về \(a\)), không toàn ánh (\(c\) không đạt được). (b) Không là hàm: 3 không có giá trị. (c) Không là hàm: 1 có hai giá trị. (d) Là hàm và là song ánh; hàm ngược là \(\{(c; 1); (a; 2); (b; 3)\}\), tức \(a \mapsto 2\), \(b \mapsto 3\), \(c \mapsto 1\).

B6. (a) Có bao nhiêu hàm từ \(\{1; 2; 3\}\) tới \(\{a; b; c\}\), và bao nhiêu trong số đó là đơn ánh? (b) Có bao nhiêu hàm từ một tập 4 phần tử tới một tập 2 phần tử, và bao nhiêu toàn ánh?

Lời giải

(a) \(3^3 = 27\) hàm; đơn ánh có \(3 \cdot 2 \cdot 1 = 6\), và ở đây chúng cũng là các song ánh. (b) \(2^4 = 16\) hàm; bỏ hai hàm gửi mọi phần tử về cùng một đích, còn \(16 - 2 = 14\) toàn ánh.

B7. Cho \(f: \mathbb{R} \to \mathbb{R}\), \(f(x) = 5 - 2x\). Chứng minh \(f\) là song ánh, tìm \(f^{-1}\), tính \(f^{-1}(1)\) và kiểm lại \(f^{-1}(f(x)) = x\).

Lời giải

Đơn ánh: \(5 - 2x = 5 - 2x'\) kéo theo \(x = x'\). Toàn ánh: với mọi \(y\), số \(x = \frac{5 - y}{2}\) cho \(5 - 2x = y\). Vậy \(f^{-1}(y) = \frac{5 - y}{2}\) và \(f^{-1}(1) = 2\); thật vậy, \(f(2) = 1\). Kiểm lại: \(f^{-1}(f(x)) = \frac{5 - (5 - 2x)}{2} = x\).

B8. Mỗi hàm sau là đơn ánh, toàn ánh, song ánh, hay không là gì? (a) \(f: \mathbb{N} \to \mathbb{N}\), \(f(n) = 2n\); (b) \(g: \mathbb{Z} \to \mathbb{N}\), \(g(n) = |n|\); (c) \(h: \mathbb{Z} \to \mathbb{Z}\), \(h(n) = n + 5\); (d) \(k: \mathbb{R} \to \mathbb{R}\), \(k(x) = x^2\).

Lời giải

(a) Đơn ánh, không toàn ánh: 1 không có dạng \(2n\). (b) Toàn ánh, vì mỗi \(m \in \mathbb{N}\) bằng \(|m|\); không đơn ánh, vì \(g(-1) = g(1)\). (c) Song ánh, với \(h^{-1}(n) = n - 5\). (d) Không đơn ánh (\(k(-1) = k(1)\)), không toàn ánh (\(-1\) không đạt được).

B9. Mô tả thứ tự chia hết trên tập các ước của 18, và tìm mọi cặp hai số không so sánh được với nhau.

Lời giải

Các ước của 18 là 1, 2, 3, 6, 9, 18. Số 1 là ước của mọi số; 2 là ước của 6 và 18; 3 là ước của 6, 9, 18; 6 và 9 là ước của 18. Các cặp không so sánh được: \(\{2; 3\}\), \(\{2; 9\}\), \(\{6; 9\}\). Có ba cặp, nên đây không phải thứ tự toàn phần.

C. Phản ví dụ và chứng minh

C1. Cho \(f: A \to B\) và \(g: B \to C\), và đặt \(h(a) = g(f(a))\) với \(a \in A\). Chứng minh: nếu \(f\) và \(g\) là đơn ánh thì \(h\) là đơn ánh; nếu \(f\) và \(g\) là toàn ánh thì \(h\) là toàn ánh. Suy ra tính bắc cầu của "cùng số lượng" (bài C1 của Chương 4).

Lời giải

Đơn ánh: nếu \(h(a) = h(a')\) thì \(g(f(a)) = g(f(a'))\); vì \(g\) đơn ánh, \(f(a) = f(a')\); vì \(f\) đơn ánh, \(a = a'\). Toàn ánh: cho \(c \in C\); vì \(g\) toàn ánh, có \(b \in B\) với \(g(b) = c\); vì \(f\) toàn ánh, có \(a \in A\) với \(f(a) = b\); khi đó \(h(a) = c\). \(\square\)

Vậy nếu có song ánh từ \(A\) tới \(B\) và song ánh từ \(B\) tới \(C\), thì \(h\) là một song ánh từ \(A\) tới \(C\). Theo Mệnh đề 6, \(A\) cùng số lượng với \(B\) và \(B\) cùng số lượng với \(C\) thì \(A\) cùng số lượng với \(C\).

C2. Tìm chỗ sai trong "chứng minh" sau và cho một phản ví dụ: "Một quan hệ đối xứng và bắc cầu thì phản xạ. Thật vậy, nếu \(a \mathrel{R} b\) thì \(b \mathrel{R} a\) (đối xứng), rồi từ \(a \mathrel{R} b\) và \(b \mathrel{R} a\) suy ra \(a \mathrel{R} a\) (bắc cầu)."

Lời giải

Lập luận chỉ cho \(a \mathrel{R} a\) với những \(a\) có ít nhất một \(b\) mà \(a \mathrel{R} b\). Tính phản xạ đòi mọi \(a\). Phản ví dụ: trên \(\{1; 2\}\), quan hệ \(R = \{(1; 1)\}\) đối xứng và bắc cầu (cặp duy nhất chỉ nối với chính nó), nhưng không phản xạ vì \((2; 2) \notin R\). Ba tính chất của quan hệ tương đương thật sự cần được đòi riêng.

C3. Với đồng dư theo 4, chứng minh: nếu \(a \sim a'\) và \(b \sim b'\) thì \(a + b \sim a' + b'\) và \(a \cdot b \sim a' \cdot b'\). Vì thế có thể định nghĩa \([a] + [b] = [a + b]\) và \([a] \cdot [b] = [a \cdot b]\). Vì sao không thể định nghĩa "\([a]\) nhỏ hơn \([b]\) khi \(a < b\)"?

Lời giải

Viết \(a' = a + 4s\) và \(b' = b + 4t\) với \(s\), \(t\) nguyên. Khi đó \(a' + b' = (a + b) + 4(s + t)\) và \(a'b' = ab + 4(at + bs + 4st)\), nên \(a' + b' \sim a + b\) và \(a'b' \sim ab\). Vậy lớp của tổng và của tích không phụ thuộc vào đại diện được chọn, và hai định nghĩa có nghĩa. \(\square\)

Với "nhỏ hơn" thì không: \(1 < 2\) sẽ cho "\([1]\) nhỏ hơn \([2]\)", nhưng \([1] = [5]\) và \(5 > 2\), nên cũng lập luận ấy cho "\([2]\) nhỏ hơn \([1]\)". Kết quả phụ thuộc vào đại diện, tức phép so sánh này không đi qua được tập thương: chỉ những tính chất bất biến trong mỗi lớp mới đi qua được.

C4. Cho \(A\) là một tập hữu hạn và \(f: A \to A\). Chứng minh \(f\) là đơn ánh khi và chỉ khi \(f\) là toàn ánh. Chỉ ra rằng điều này sai với \(\mathbb{N}\).

Lời giải

Gọi \(n = |A|\). Trước hết, với mọi tập con \(X \subseteq A\), tập giá trị \(f(X)\) có không quá \(|X|\) phần tử: chọn cho mỗi giá trị một phần tử của \(X\) có giá trị ấy; các phần tử được chọn khác nhau, nên có không quá \(|X|\) giá trị.

Nếu \(f\) đơn ánh thì \(n\) phần tử của \(A\) cho \(n\) giá trị khác nhau, nên \(f(A)\) là một tập con \(n\) phần tử của \(A\). Một tập hữu hạn không ghép một-một được với một phần thực sự của nó (bài C2 Chương 4), nên \(f(A) = A\): \(f\) toàn ánh.

Nếu \(f\) toàn ánh mà không đơn ánh, có \(a \neq a'\) với \(f(a) = f(a')\). Bỏ \(a'\) đi, giá trị \(f(a')\) vẫn đạt được tại \(a\), nên \(f(A \setminus \{a'\}) = A\). Nhưng \(A \setminus \{a'\}\) chỉ có \(n - 1\) phần tử, nên theo nhận xét đầu, tập giá trị của nó có không quá \(n - 1\) phần tử, mâu thuẫn. \(\square\)

Với \(\mathbb{N}\): \(n \mapsto n + 1\) là đơn ánh mà không toàn ánh; hàm gán cho \(n\) thương của phép chia \(n\) cho 2 là toàn ánh mà không đơn ánh (0 và 1 cùng cho 0). Tập vô hạn cư xử khác hẳn, và Chương 21 bắt đầu từ chính chỗ này.

Câu hỏi để ngỏ

Song ánh cho ta cách so sánh cỡ của hai tập mà không cần đếm. Áp dụng cho tập vô hạn thì sao? Mọi tập vô hạn có "to bằng nhau" không?