Hàm f từ tập A tới tập B là đơn ánh khi hai phần tử khác nhau của A luôn cho hai ảnh khác nhau, là toàn ánh khi mọi phần tử của B đều là ảnh của ít nhất một phần tử của A, và là song ánh khi vừa đơn ánh vừa toàn ánh. Nói bằng hình ảnh mũi tên: đơn ánh là không có hai mũi tên cắm vào cùng một điểm, toàn ánh là không điểm nào ở B bị bỏ trống, song ánh là ghép cặp một đổi một trọn vẹn.
Ba khái niệm này nằm ở chương tập hợp và ánh xạ của giáo trình toán rời rạc và đại số đại cương. Chúng nghe khô nhưng là nền của phép đếm, của hàm ngược, của mã hoá dữ liệu, và của câu hỏi nổi tiếng “số tự nhiên có nhiều hơn số chẵn không”. Bài ôn nhanh các phép toán tập hợp cần dùng, rồi đi vào từng khái niệm với ví dụ kiểm từng bước.
Ôn nhanh tập hợp: những phép toán cần dùng
Tập hợp là một bộ sưu tập các đối tượng phân biệt, không quan tâm thứ tự và không đếm lặp: {1, 2, 3} và {3, 1, 2, 2} là cùng một tập. Ký hiệu x ∈ A nghĩa là x thuộc A; A ⊆ B nghĩa là mọi phần tử của A đều thuộc B. Tập rỗng, ký hiệu ∅, là tập con của mọi tập. Số phần tử của tập hữu hạn A viết là |A|, gọi là lực lượng của A.
Bốn phép toán quen thuộc: hợp A ∪ B gồm phần tử thuộc ít nhất một tập; giao A ∩ B gồm phần tử thuộc cả hai; hiệu A \ B gồm phần tử thuộc A mà không thuộc B; phần bù của A trong một tập vũ trụ U gồm mọi phần tử của U không thuộc A. Các phép này ứng với phép tuyển, hội và phủ định của logic mệnh đề, nên luật De Morgan cũng có bản tập hợp: phần bù của A ∪ B bằng giao của hai phần bù.
Phép quan trọng nhất cho bài này là tích Descartes A × B, tập mọi cặp có thứ tự (a, b) với a thuộc A, b thuộc B. Nếu A có 3 phần tử và B có 4 phần tử thì A × B có 12 cặp. Một hàm từ A tới B, theo định nghĩa chặt chẽ của lý thuyết tập hợp, chính là một tập con của A × B sao cho mỗi a thuộc A xuất hiện trong đúng một cặp. Định nghĩa này nghe trừu tượng nhưng giúp trả lời gọn những câu như “có bao nhiêu hàm từ A tới B”: mỗi phần tử trong 3 phần tử của A chọn ảnh trong 4 khả năng, nên có 4 × 4 × 4 = 64 hàm.
Đơn ánh: không có hai đầu vào chung một đầu ra
Hàm f: A → B là đơn ánh nếu với mọi x1, x2 thuộc A, f(x1) = f(x2) kéo theo x1 = x2. Phát biểu tương đương theo phản đảo: x1 khác x2 thì f(x1) khác f(x2). Khi chứng minh, dạng thứ nhất thường tiện hơn vì bạn được làm việc với một phương trình.
Ví dụ kiểm từng bước: f từ tập số nguyên vào tập số nguyên, f(x) = 2x + 3. Giả sử f(x1) = f(x2), tức 2x1 + 3 = 2x2 + 3. Trừ 3 hai vế được 2x1 = 2x2, chia 2 được x1 = x2. Vậy f là đơn ánh. Ngược lại, g(x) = x bình phương trên tập số thực không phải đơn ánh, vì g(2) = g(−2) = 4 trong khi 2 khác −2. Để bác bỏ tính đơn ánh, chỉ cần một cặp phản ví dụ như vậy.
Với tập hữu hạn, đơn ánh từ A vào B chỉ tồn tại khi |A| ≤ |B|. Đây chính là nguyên lý chuồng bồ câu nhìn từ phía hàm: nếu A nhiều phần tử hơn B, mọi hàm từ A tới B đều buộc phải có hai phần tử chung một ảnh. Ví dụ đời thường: gán mã số sinh viên là một đơn ánh từ tập sinh viên vào tập mã số; hệ thống cấp trùng mã cho hai người tức là hỏng tính đơn ánh. Với đồ thị hàm số thực, phép thử đường ngang cho câu trả lời trực quan: mọi đường thẳng nằm ngang cắt đồ thị nhiều nhất một lần thì hàm là đơn ánh.
Toàn ánh: mọi phần tử đích đều được chạm tới
Hàm f: A → B là toàn ánh nếu với mọi y thuộc B, tồn tại x thuộc A sao cho f(x) = y. Nói cách khác, tập ảnh f(A) bằng toàn bộ B. Chú ý rằng tính toàn ánh phụ thuộc vào việc bạn khai báo tập đích là gì, không chỉ vào công thức.
Ví dụ: f(x) = 2x + 3 từ số nguyên vào số nguyên không toàn ánh. Lấy y = 4, phương trình 2x + 3 = 4 cho x = 1/2, không phải số nguyên, nên 4 không có tạo ảnh. Nhưng cùng công thức đó, xét từ số thực vào số thực, thì với mọi y bạn luôn tìm được x = (y − 3)/2, nên f là toàn ánh. Tương tự, g(x) = x bình phương từ số thực vào số thực không toàn ánh vì số âm không có tạo ảnh, nhưng nếu đổi tập đích thành tập các số thực không âm thì g trở thành toàn ánh.
Mẫu chứng minh toàn ánh luôn có hai bước: lấy một y bất kỳ trong tập đích, giải tìm x theo y, rồi kiểm rằng x vừa tìm thật sự nằm trong tập nguồn. Bước kiểm thứ hai hay bị bỏ qua, và đó đúng là chỗ ví dụ số nguyên ở trên bị trượt. Hàm phần nguyên, lấy số nguyên lớn nhất không vượt quá x, từ số thực vào số nguyên là một toàn ánh nhưng không đơn ánh: mọi số nguyên n đều là ảnh của chính n, nhưng 2,1 và 2,7 cùng cho ảnh là 2. Với tập hữu hạn, toàn ánh từ A lên B chỉ tồn tại khi |A| ≥ |B|.
Song ánh, hàm ngược và bảng so sánh ba loại
Song ánh là hàm vừa đơn ánh vừa toàn ánh: mỗi phần tử của B có đúng một tạo ảnh. Chỉ song ánh mới có hàm ngược đi từ B về A sao cho đi rồi quay lại luôn trở về điểm cũ. Với f(x) = 2x + 3 trên số thực, hàm ngược đưa y về (y − 3)/2. Bảng dưới xếp các ví dụ đã gặp cạnh nhau.
| Hàm | Nguồn → đích | Đơn ánh | Toàn ánh | Song ánh |
|---|---|---|---|---|
| f(x) = 2x + 3 | Số nguyên → số nguyên | Có | Không (4 không có tạo ảnh) | Không |
| f(x) = 2x + 3 | Số thực → số thực | Có | Có | Có, ngược là (y − 3)/2 |
| g(x) = x bình phương | Số thực → số thực | Không (2 và −2) | Không (số âm) | Không |
| g(x) = x bình phương | Số thực không âm → số thực không âm | Có | Có | Có, ngược là căn bậc hai |
| Phần nguyên của x | Số thực → số nguyên | Không | Có | Không |
| n đi tới 2n | Số tự nhiên → số chẵn | Có | Có | Có |
Hai dòng của g cho thấy cùng một công thức, chỉ cần thu hẹp tập nguồn và tập đích là biến một hàm “xấu” thành song ánh. Đó chính là cách người ta định nghĩa hàm căn bậc hai, hay các hàm lượng giác ngược như arcsin: thu hẹp miền để hàm gốc thành song ánh rồi mới lấy ngược.
Với hai tập hữu hạn có cùng số phần tử, ba khái niệm gộp làm một: hàm từ A tới B với |A| = |B| là đơn ánh khi và chỉ khi nó là toàn ánh, và khi đó nó là song ánh. Tính chất này hay được dùng để rút ngắn chứng minh: chỉ cần kiểm một chiều.
Đếm bằng song ánh: mẹo mạnh nhất của toán tổ hợp
Nếu có một song ánh giữa hai tập hữu hạn thì chúng có cùng số phần tử. Mệnh đề nghe hiển nhiên này là một trong những công cụ đếm mạnh nhất: khi một tập khó đếm, bạn tìm cách ghép cặp một đổi một nó với một tập dễ đếm hơn.
Ví dụ kinh điển: tập A có n phần tử thì có bao nhiêu tập con? Ghép mỗi tập con với một chuỗi n ký tự 0 và 1, ký tự thứ i là 1 nếu phần tử thứ i có mặt trong tập con, 0 nếu không. Với A = {a, b, c}, tập con {a, c} ứng với chuỗi 101, tập rỗng ứng với 000, chính A ứng với 111. Phép ghép này là song ánh: mỗi tập con cho đúng một chuỗi và mỗi chuỗi cho đúng một tập con. Số chuỗi nhị phân độ dài n là 2 mũ n, nên số tập con cũng là 2 mũ n; với ba phần tử là 8.
Song ánh còn dẫn tới một kết quả từng làm giới toán bối rối vào cuối thế kỷ 19, khi Georg Cantor dùng nó để so sánh các tập vô hạn. Hàm n đi tới 2n là song ánh từ tập số tự nhiên lên tập số chẵn, nên hai tập này có cùng lực lượng, dù tập số chẵn chỉ là một phần của tập số tự nhiên. Cantor cũng chứng minh không có song ánh nào giữa số tự nhiên và số thực, tức là có nhiều mức vô hạn khác nhau. Với người học khoa học máy tính, mã hoá một đối tượng thành chuỗi bit mà không mất thông tin chính là một đơn ánh; giải mã ngược lại được là nhờ tính đơn ánh đó.
Dùng AI luyện bài đơn ánh, toàn ánh mà vẫn tự hiểu
Bài tập loại này có khuôn chứng minh rất rõ, nên AI thường viết lời giải trông gọn gàng. Lỗi hay gặp lại nằm ở chỗ tinh: quên kiểm tập nguồn, nhầm tập đích, dùng một ví dụ thay cho chứng minh. Cách dùng hợp lý như sau.
- Viết rõ tập nguồn và tập đích trong câu hỏi. “f(x) = 2x + 3 có phải toàn ánh không” là câu hỏi thiếu; AI sẽ tự chọn số thực và trả lời “có”, trong khi đề của bạn có thể là số nguyên.
- Tự làm trước, gửi lời giải của mình kèm câu lệnh mẫu: “Đây là chứng minh mình viết rằng hàm sau là đơn ánh. Đừng viết lại lời giải. Chỉ ra bước nào thiếu lập luận hoặc dùng điều chưa được chứng minh.”
- Hỏi AI tìm phản ví dụ khi bạn nghi một hàm không đơn ánh hoặc không toàn ánh, rồi tự thay số kiểm phản ví dụ đó. Phản ví dụ sai thì cả kết luận sai theo.
- Nhờ AI ra bài với độ khó tăng dần: hàm trên tập hữu hạn cho dưới dạng bảng, rồi hàm tuyến tính, hàm bậc hai, hàm hợp. Yêu cầu nó giữ đáp án lại cho tới khi bạn gửi bài làm.
- Với hàm số thực, vẽ đồ thị bằng phần mềm vẽ đồ thị để dùng phép thử đường ngang, đối chiếu với kết luận đại số. Hình vẽ không thay được chứng minh nhưng bắt lỗi rất nhanh.
Nếu đây là bài tập lấy điểm, đọc quy định dùng AI của môn học; phần chứng minh nộp phải là của bạn. Mục tiêu của dạng bài này là luyện cách viết lập luận chặt, thứ mà đọc lời giải của người khác không luyện được.
Câu hỏi thường gặp
Hàm hằng có phải là đơn ánh không?
Hàm hằng gán mọi phần tử của A cho cùng một giá trị, nên chỉ là đơn ánh khi A có đúng một phần tử. Nó là toàn ánh khi tập đích B chỉ có một phần tử. Trong bài tập, hàm hằng thường được dùng làm phản ví dụ nhanh cho những phát biểu tổng quát quá mức.
Hợp của hai đơn ánh có còn là đơn ánh không?
Có. Nếu f và g đều là đơn ánh và hàm hợp g sau f xác định được, thì g(f(x1)) = g(f(x2)) suy ra f(x1) = f(x2) nhờ g đơn ánh, rồi suy ra x1 = x2 nhờ f đơn ánh. Lập luận tương tự cho thấy hợp của hai toàn ánh là toàn ánh, và hợp của hai song ánh là song ánh.
Có bao nhiêu song ánh từ một tập n phần tử lên chính nó?
Có n giai thừa song ánh, vì phần tử thứ nhất có n lựa chọn ảnh, phần tử thứ hai còn n − 1 lựa chọn, cứ thế đến phần tử cuối còn một lựa chọn. Mỗi song ánh như vậy chính là một hoán vị của tập đó; tập ba phần tử có 6 hoán vị.
Vì sao cần phân biệt tập đích với tập ảnh?
Tập đích là tập bạn khai báo khi định nghĩa hàm, tập ảnh là những giá trị hàm thực sự đạt được. Hàm là toàn ánh đúng khi hai tập này bằng nhau. Nhiều bài tập cố ý giữ nguyên công thức và chỉ đổi tập đích để kiểm xem người học có để ý điều này hay không.
Đơn ánh, toàn ánh có liên quan gì tới cơ sở dữ liệu?
Khá gần. Khoá chính của một bảng đòi hỏi ánh xạ từ bản ghi sang giá trị khoá là đơn ánh, không hai bản ghi trùng khoá. Quan hệ một – một giữa hai bảng tương ứng với song ánh, còn quan hệ nhiều – một giống một hàm không đơn ánh. Hiểu khái niệm toán giúp thiết kế bảng ít lỗi hơn.
Lực lượng của tập vô hạn có ý nghĩa thực tế không?
Với lập trình hằng ngày thì ít. Nhưng nó giải thích những giới hạn cơ bản của máy tính: tập các chương trình máy tính là đếm được, còn tập các hàm từ số tự nhiên vào tập gồm 0 và 1 thì không đếm được, nên tồn tại những hàm không chương trình nào tính được. Đây là một cửa vào lý thuyết tính toán.