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ệm | toàn ánh |
| đúng một nghiệm | song á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ị.
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ông | Không | f(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ông | cá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ông | Có | 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.
Đơ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.
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.