Biểu tượng chim cắt của Kestrel Exams KESTREL EXAMSLUYỆN TẬP ĐỂ ĐẠT
Bản dịch này do AI thực hiện và chưa được người bản ngữ kiểm duyệt. Nếu có khác biệt, bản tiếng Anh là bản chính. Mã nguồn được giữ nguyên bằng tiếng Anh. Ứng dụng luyện tập và tài liệu cho các kỳ thi chứng chỉ của Hoa Kỳ chỉ có bằng tiếng Anh. Read in English
Discrete MathĐọc trong 8 phút

Hàm đơn ánh, toàn ánh và song ánh

Ba từ nghe giống nhau nhưng khi kiểm tra thì rất khác nhau. Bài hướng dẫn này gắn mỗi từ với một hình ảnh, cho bạn dòng đầu tiên chính xác của mỗi chứng minh, giải năm ví dụ, rồi cho thấy một song ánh chính là điều mà việc đếm thực sự có nghĩa.

Luyện tập chủ đề này trong ứng dụng miễn phí →Tất cả bài hướng dẫn Discrete Math

Một chỗ gửi áo khoác#

Ở chỗ gửi áo khoác, mỗi chiếc áo được một cái móc có số. Hãy coi áo khoác là đầu vào và các móc là đầu ra. Quy tắc của nhân viên, từ áo đến móc, là một hàm.

  • Nếu không có hai chiếc áo nào chung một móc, quy tắc là đơn ánh (injective), còn gọi là một-một (one-to-one).
  • Nếu mọi móc đều có một chiếc áo, quy tắc là toàn ánh (surjective), còn gọi là lên (onto).
  • Nếu cả hai cùng xảy ra, mỗi móc một áo và không móc nào trống, quy tắc là song ánh (bijective). Một song ánh là một sự ghép cặp hoàn hảo.

Hãy giữ hình ảnh đó. Mỗi định nghĩa bên dưới là một trong ba câu đó được viết bằng ký hiệu.

Một hàm có ba phần#

Một hàm f: A → B được đọc là “f từ A đến B”. Nó có ba phần:

  • miền xác định (domain) A, các đầu vào được phép (những chiếc áo);
  • tập đích (codomain) B, nơi các đầu ra được phép rơi vào (những cái móc);
  • quy tắc, gán cho mỗi đầu vào đúng một đầu ra.

Miền giá trị (range) (còn gọi là ảnh, Im f) là tập các đầu ra thực sự được dùng. Nó nằm trong tập đích và có thể nhỏ hơn.

Đổi miền xác định hoặc tập đích và bạn có một hàm khác, dù quy tắc giống nhau. Điều này rất quan trọng với x², như bạn sẽ thấy.

Đơn ánh: không có hai đầu vào nào chung một đầu ra#

Định nghĩa. f là đơn ánh khi các đầu vào khác nhau luôn cho các đầu ra khác nhau. Với mọi x₁, x₂ trong A: nếu x₁ ≠ x₂, thì f(x₁) ≠ f(x₂).

Cách chứng minh. Các mệnh đề về ≠ khó làm việc, nên hãy chứng minh mệnh đề phản đảo, có cùng nghĩa:

Giả sử f(x₁) = f(x₂). Chỉ ra x₁ = x₂.

Ví dụ: f(x) = 3x − 7 trên các số thực ℝ. Giả sử 3x₁ − 7 = 3x₂ − 7. Cộng 7 và chia cho 3: x₁ = x₂. Xong.

Cách bác bỏ. Tìm hai đầu vào khác nhau có cùng đầu ra. Với x² trên ℝ, f(1) = f(−1) = 1.

Một cái bẫy: “nếu x₁ = x₂ thì f(x₁) = f(x₂)” đúng với mọi hàm. Chứng minh điều đó không cho thấy gì. Hãy đảm bảo dấu bằng bạn bắt đầu nằm giữa các đầu ra.

Toàn ánh: mọi đầu ra đều được dùng#

Định nghĩa. f là toàn ánh khi miền giá trị bằng tập đích. Với mọi y trong B có ít nhất một x trong A thỏa f(x) = y.

Cách chứng minh. Bắt đầu từ tập đích, không phải miền xác định:

Lấy một y bất kỳ trong B. Giải f(x) = y để tìm x. Kiểm tra rằng x nằm trong A.

Ví dụ: f(x) = 3x − 7 trên ℝ. Cho y, giải 3x − 7 = y để được x = (y + 7)/3. Đó là một số thực, nên nó nằm trong miền xác định, và f(x) = y. Xong.

Cách bác bỏ. Tìm một y trong tập đích mà không gì với tới. Với f(n) = 2n trên các số nguyên ℤ, đầu ra 3 không bao giờ đạt được, vì 2n = 3 không có nghiệm nguyên.

Song ánh: đúng một nghiệm#

Gộp hai điều lại. f là một song ánh khi, với mọi y trong tập đích, phương trình f(x) = y có đúng một nghiệm.

Với mọi y, f(x) = y có…Tên
nhiều nhất một nghiệmđơn ánh
ít nhất một nghiệmtoàn ánh
đúng một nghiệmsong ánh

Nghiệm duy nhất đó là hàm ngược, f−1(y). Chỉ các song ánh mới có hàm ngược.

Khi miền xác định và tập đích là cùng một tập hợp, một song ánh còn được gọi là một hoán vị. Ánh xạ x ↦ 3x mod 7 trên {1, …, 6} là một hoán vị.

Một lối tắt cho tập hữu hạn

Nếu A và B hữu hạn và có cùng số phần tử, thì đơn ánh và toàn ánh là cùng một thứ. n đầu ra khác nhau trong một tập n phần tử phải lấp đầy nó. Điều này sai với tập vô hạn: n ↦ 2n trên ℕ là đơn ánh và không phải toàn ánh.

Năm ví dụ, cạnh nhau#

HàmĐơn ánh?Toàn ánh?Vì sao
x², ℝ → ℝKhôngKhôngf(1) = f(−1); −1 không bao giờ là một đầu ra
x², [0, ∞) → [0, ∞)CóCókhông có số âm để va chạm; y được √y chạm tới
2n, ℤ → ℤCóKhôngcác số lẻ không bao giờ được chạm tới
3x − 7, ℝ → ℝCóCóx = (y + 7)/3 là nghiệm duy nhất
⌊n/2⌋, ℤ → ℤKhôngCóf(0) = f(1) = 0; f(2m) = m

Hai dòng đầu dùng cùng một quy tắc, x². Chỉ miền xác định và tập đích thay đổi, và đáp án đã đổi từ “không cái nào” sang “song ánh”. (⌊n/2⌋ đọc là “phần nguyên của n chia 2”: chia, rồi làm tròn xuống.)

Đếm là một song ánh#

Khi bạn đếm một đống đồng xu, bạn chạm vào từng đồng và nói “một, hai, ba…”. Bạn không bao giờ bỏ sót đồng nào và không bao giờ nói một số hai lần. Đó là một song ánh giữa các đồng xu và tập {1, 2, …, n}, mà môn học viết là [n].

Vì vậy môn học định nghĩa: một tập hữu hạn A có n phần tử, viết là |A| = n (đọc là “lực lượng của A là n”), khi có một song ánh từ A đến [n]. Tổng quát hơn, hai tập có cùng lực lượng khi có một song ánh giữa chúng.

Định nghĩa này cũng dùng được cho tập vô hạn, nơi nó cho những đáp án đáng ngạc nhiên. Ánh xạ n ↦ 2n là một song ánh từ ℕ = {1, 2, 3, …} đến các số chẵn {2, 4, 6, …}. Vậy có đúng bằng nhau số các số chẵn và số các số tự nhiên, dù các số chẵn là một phần thực sự của ℕ.

Vì sao một tập n phần tử có 2n tập con#

Tập lũy thừa (power set) P(A) là tập hợp tất cả các tập con của A. Với A = {a, b, c}:

∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}. Đó là 8 = 23.

Cả ∅ (tập rỗng) và chính A đều được tính. Tập rỗng là tập con của mọi tập hợp, và mọi tập hợp là tập con của chính nó.

Vì sao 2n: để xây dựng một tập con, đi qua các phần tử từng cái một và trả lời có hoặc không. Đó là hai lựa chọn độc lập cho mỗi phần tử, nên 2 · 2 · … · 2 = 2n. Theo ngôn ngữ của trang này, các tập con song ánh với các chuỗi n bit, 1 cho có và 0 cho không.

Một câu để mang vào phòng thi

Đơn ánh: giả sử f(x₁) = f(x₂) và chỉ ra x₁ = x₂. Toàn ánh: lấy một y bất kỳ và giải f(x) = y bên trong miền xác định.

Sai ở chỗ nào#

  • Chứng minh sai chiều cho đơn ánh. Bắt đầu từ x₁ = x₂ không chứng minh được gì.
  • Bắt đầu chứng minh toàn ánh từ x. Tính vài đầu ra không cho thấy mọi y đều được chạm tới. Hãy bắt đầu từ y.
  • Bỏ qua tập đích. “x² có phải là lên không?” không có đáp án cho đến khi bạn biết tập đích.
  • Giải tìm x mà không kiểm tra nó nằm trong miền xác định. Với f(n) = 2n trên ℤ, giải 2n = 3 cho n = 1,5, không phải số nguyên. Đó chính xác là lý do f không phải là toàn ánh.
  • Quên ∅ hoặc A khi liệt kê các tập con. Số đếm là 2n, không phải 2n − 2.

Tự kiểm tra trong ứng dụng Kestrel Exams miễn phí

Luyện tập Discrete Math theo chủ đề: dùng được khi không có mạng, không quảng cáo, không cần tài khoản.

Luyện tập hàm và lực lượng →

Câu hỏi thường gặp#

Đơn ánh và toàn ánh khác nhau ở đâu?

Đơn ánh (một-một) nghĩa là không có hai đầu vào nào chung một đầu ra. Toàn ánh (lên) nghĩa là mọi phần tử của tập đích đều là đầu ra của một thứ nào đó. Một hàm có thể là một trong hai, cả hai, hoặc không cái nào; cả hai cùng lúc là một song ánh.

Làm sao chứng minh một hàm là đơn ánh?

Giả sử f(x₁) = f(x₂) và dùng đại số để chỉ ra x₁ = x₂. Đây là mệnh đề phản đảo của định nghĩa, và nó dễ hơn vì bạn được bắt đầu từ một phương trình.

Làm sao chứng minh một hàm là toàn ánh?

Lấy một y bất kỳ trong tập đích, giải f(x) = y để tìm x, và kiểm tra rằng x bạn tìm được nằm trong miền xác định. Nếu có một y nào đó không có nghiệm trong miền xác định, hàm không phải là toàn ánh.

f(x) = x² có phải là một-một không?

Không trên các số thực, vì f(1) = f(−1). Trên miền [0, ∞) nó là một-một, và với tập đích [0, ∞) nó cũng là toàn ánh, nên nó trở thành một song ánh. Miền xác định và tập đích là một phần của hàm.

Vì sao một tập hợp có n phần tử thì có 2^n tập con?

Mỗi phần tử độc lập hoặc nằm trong tập con hoặc không, tức là 2 lựa chọn cho mỗi phần tử. Nhân lại cho 2^n. Phép đếm này tính cả tập rỗng và cả toàn bộ tập hợp.

Đề xuất chỉnh sửa

Có chỗ nào chưa rõ? Có chủ đề nào bạn muốn chúng tôi viết? Hãy cho chúng tôi biết. Chúng tôi đọc mọi tin nhắn, và một lời đề nghị là cách nhanh nhất để có bài hướng dẫn mới: một số bài ở đây ra đời vì có người hỏi.