Quy nạp hoàn toàn là kết luận về cả một lớp đối tượng sau khi đã xét từng phần tử của lớp đó; nếu từng quan sát đúng thì kết luận chắc chắn đúng. Quy nạp không hoàn toàn là kết luận về cả lớp khi mới xét một phần; kết luận khi ấy chỉ có tính xác suất, dù số trường hợp đã xét lớn đến đâu. Phân biệt hai loại này là bài nhập môn của mọi giáo trình Logic học đại cương ở phần suy luận quy nạp.
Hai loại qua một lớp học
Cô chủ nhiệm lớp 8A có 36 học sinh. Cô muốn biết "cả lớp đã nộp phiếu khảo sát chưa".
- Cách 1: cô dò từng tên trong danh sách 36 em, em nào cũng đã nộp. Kết luận "cả lớp đã nộp" là quy nạp hoàn toàn. Nó chắc chắn — trừ khi cô dò nhầm.
- Cách 2: cô hỏi 10 em ngồi bàn đầu, cả 10 đã nộp, cô kết luận "chắc cả lớp nộp rồi". Đó là quy nạp không hoàn toàn. Có thể đúng, nhưng chỉ cần một em ngồi cuối lớp quên là sai.
Hình thức chung, viết theo kiểu giáo trình:
| Quy nạp hoàn toàn | Quy nạp không hoàn toàn | |
|---|---|---|
| Tiền đề | S₁, S₂, …, Sₙ có tính chất P; S₁…Sₙ là toàn bộ lớp S | S₁, S₂, …, Sₖ có tính chất P; đây chỉ là một phần lớp S |
| Kết luận | Mọi S có tính chất P | Mọi S (có lẽ) có tính chất P |
| Độ tin | Chắc chắn, nếu tiền đề đúng | Xác suất, có thể sai dù tiền đề đúng |
| Điều kiện dùng | Lớp hữu hạn, đếm hết được | Lớp lớn, vô hạn, hoặc không xét hết được |
| Cho thêm thông tin mới? | Hầu như không — chỉ tóm gọn điều đã biết | Có — đoán về những trường hợp chưa thấy |
Dòng cuối là chỗ hay bị bỏ qua. Quy nạp hoàn toàn chắc chắn chính vì nó không vượt ra ngoài những gì đã kiểm. Quy nạp không hoàn toàn rủi ro chính vì nó nói về cái chưa kiểm — và đó cũng là lý do nó có ích.
Quy nạp hoàn toàn trong toán: xét hết các trường hợp
Quy nạp hoàn toàn không chỉ dùng cho lớp vài chục học sinh. Toán học dùng nó để chứng minh điều đúng cho vô số số, bằng cách chia vô số ấy thành hữu hạn nhóm rồi xét đủ từng nhóm.
Ví dụ: chứng minh bình phương của một số nguyên chia cho 3 chỉ dư 0 hoặc 1, không bao giờ dư 2.
Mọi số nguyên n đều thuộc đúng một trong ba dạng:
- n = 3k: n² = 9k² = 3·(3k²), chia hết cho 3, dư 0.
- n = 3k + 1: n² = 9k² + 6k + 1 = 3·(3k² + 2k) + 1, dư 1.
- n = 3k + 2: n² = 9k² + 12k + 4 = 3·(3k² + 4k + 1) + 1, dư 1.
Ba dạng đã phủ kín mọi số nguyên, không sót, nên kết luận chắc chắn. Thử lại: 7 = 3·2 + 1, 7² = 49 = 3·16 + 1, dư 1; 8 = 3·2 + 2, 8² = 64 = 3·21 + 1, dư 1; 9² = 81 chia hết cho 3. Khớp.
Điều kiện sống còn là danh sách trường hợp phải đủ. Nếu quên dạng 3k + 2 thì "chứng minh" trông vẫn gọn gàng mà thực chất là quy nạp không hoàn toàn trá hình.
Khi quy nạp không hoàn toàn dẫn lạc: hai ví dụ có thật
Số Fermat
Pierre de Fermat (thế kỷ 17) xét các số dạng 2^(2ⁿ) + 1. Với n = 0, 1, 2, 3, 4 ta được 3, 5, 17, 257, 65537 — cả năm đều là số nguyên tố. Fermat cho rằng mọi số dạng này đều nguyên tố. Năm 1732, Leonhard Euler chỉ ra n = 5 cho số 4 294 967 297 = 641 × 6 700 417, không nguyên tố.
Kiểm phép nhân: 6 700 417 × 600 = 4 020 250 200; 6 700 417 × 41 = 274 717 097; cộng lại 4 294 967 297. Đúng.
Đa thức n² + n + 41
Thay n = 0, 1, 2, … vào n² + n + 41 ta được 41, 43, 47, 53, 61, 71… đều nguyên tố, và cứ thế liền một mạch 40 giá trị từ n = 0 tới n = 39. Ai dừng lại ở đó sẽ tin chắc công thức luôn cho số nguyên tố. Nhưng n = 40 cho 1600 + 40 + 41 = 1681 = 41 × 41. Chuỗi 40 lần đúng liên tiếp không cứu được lần thứ 41.
Hai ví dụ cho thấy: trong toán, số trường hợp đã kiểm không bao giờ thay được chứng minh. Toán chỉ dùng quy nạp không hoàn toàn để đoán, rồi chứng minh bằng cách khác.
Hai kiểu quy nạp không hoàn toàn
Giáo trình Logic học đại cương ở Việt Nam thường chia quy nạp không hoàn toàn làm hai:
| Kiểu | Cơ sở | Ví dụ | Độ tin |
|---|---|---|---|
| Quy nạp phổ thông (liệt kê đơn giản) | Thấy lặp lại nhiều lần, chưa gặp trường hợp trái | "Thiên nga nào ta gặp cũng trắng, vậy thiên nga đều trắng" | Thấp; một phản ví dụ là đổ |
| Quy nạp khoa học | Ngoài lặp lại còn tìm ra mối liên hệ tất yếu, nguyên nhân giải thích được | "Kim loại nào đã thử cũng dẫn điện, và ta biết vì kim loại có electron tự do" | Cao hơn nhiều, vì có cơ chế đứng sau |
Thiên nga là ví dụ kinh điển. Người châu Âu nhiều thế kỷ chỉ thấy thiên nga trắng. Cuối thế kỷ 17, các đoàn thám hiểm ghi nhận thiên nga đen ở vùng nay là Tây Úc. Một quan sát duy nhất làm sụp một kết luận dựa trên hàng triệu lần nhìn thấy. Karl Popper về sau lấy chính ví dụ này để nói về sự bất cân xứng giữa xác nhận và bác bỏ (xem bài về Popper trong danh mục này).
Làm sao cho quy nạp không hoàn toàn đáng tin hơn
Không làm cho nó chắc chắn được, nhưng làm cho nó bớt liều được. Bốn nguyên tắc thường được nêu:
- Nhiều trường hợp: 10 em bàn đầu kém xa 30 em trên 36.
- Đa dạng trường hợp: hỏi cả bàn đầu, bàn giữa, bàn cuối, em hay quên lẫn em chăm. Mẫu đa dạng quan trọng hơn mẫu to mà lệch.
- Chủ động tìm phản ví dụ: hỏi đúng những em hay quên nộp. Nếu cả nhóm ấy cũng đã nộp, kết luận mạnh lên hẳn.
- Tìm lý do: nếu biết cô đã thu phiếu ngay trong giờ sinh hoạt, ai có mặt đều phải nộp, thì kết luận chuyển từ "phổ thông" sang "khoa học".
Ngược lại, lỗi hay gặp nhất có tên là khái quát vội vàng: rút kết luận chung từ vài trường hợp, thường là những trường hợp gây ấn tượng mạnh. "Hai lần mua hàng online đều hỏng, vậy hàng online toàn đồ dỏm" — hai mẫu, chọn theo trí nhớ, không có cơ chế.
Bài tập
- "Kiểm 12 tháng trong năm, tháng nào cũng có ít nhất 28 ngày. Vậy mọi tháng đều có ít nhất 28 ngày." Đây là loại quy nạp nào? — Đáp án: quy nạp hoàn toàn, vì 12 tháng là toàn bộ lớp.
- "Ba quả xoài đầu sọt đều ngọt, vậy cả sọt ngọt." — Đáp án: quy nạp không hoàn toàn kiểu phổ thông; mẫu ít và lệch (quả đầu sọt thường được chọn đẹp).
- Chứng minh tích hai số nguyên liên tiếp luôn chẵn bằng quy nạp hoàn toàn. — Đáp án: xét n chẵn: n(n+1) có thừa số chẵn n; xét n lẻ: n + 1 chẵn. Hai trường hợp phủ kín mọi số nguyên, nên tích luôn chẵn. Thử: 7 × 8 = 56, 10 × 11 = 110.
- Vì sao kiểm 40 giá trị liên tiếp của n² + n + 41 vẫn không chứng minh được công thức luôn cho số nguyên tố? — Đáp án: vì tập số tự nhiên vô hạn, 40 giá trị chỉ là một phần; thực tế n = 40 cho 1681 = 41².
Dùng vào đâu
- Thi Logic học đại cương: câu "phân biệt quy nạp hoàn toàn và không hoàn toàn, cho ví dụ" gần như chắc gặp. Bảng so sánh ở trên là khung trả lời.
- Toán: chứng minh bằng chia trường hợp (theo số dư, theo dấu, theo chẵn lẻ) chính là quy nạp hoàn toàn. Lỗi thường gặp là sót một trường hợp.
- Kiểm hàng, kiểm sổ: biết lúc nào mình đã kiểm hết, lúc nào mới lấy mẫu — và nói rõ điều đó khi báo cáo.
- Học tiếp: chương suy luận quy nạp trong giáo trình Logic học đại cương; phần quy nạp trong Introduction to Logic của Irving Copi. Bài về quy nạp toán học trong danh mục này giải thích vì sao "quy nạp toán học" lại là suy diễn.
Câu hỏi thường gặp
Quy nạp hoàn toàn là gì?
Là suy luận đi tới kết luận về mọi phần tử của một lớp sau khi đã xét đủ từng phần tử của lớp đó. Vì không bỏ sót trường hợp nào, kết luận chắc chắn đúng nếu từng quan sát đúng. Nó chỉ dùng được khi lớp hữu hạn hoặc chia được thành hữu hạn trường hợp.
Quy nạp không hoàn toàn khác quy nạp hoàn toàn thế nào?
Quy nạp không hoàn toàn chỉ xét một phần của lớp rồi kết luận cho cả lớp, nên kết luận chỉ có tính xác suất. Quy nạp hoàn toàn xét hết nên chắc chắn, nhưng gần như không cho thông tin mới. Đổi lại, quy nạp không hoàn toàn cho phép dự đoán những trường hợp chưa thấy.
Quy nạp phổ thông và quy nạp khoa học khác nhau ra sao?
Quy nạp phổ thông chỉ dựa vào việc thấy một điều lặp lại nhiều lần và chưa gặp trường hợp trái. Quy nạp khoa học còn tìm ra mối liên hệ nguyên nhân hoặc cơ chế giải thích vì sao điều đó lặp lại. Vì có cơ chế, quy nạp khoa học đáng tin hơn hẳn.
Chứng minh bằng cách chia trường hợp có phải quy nạp hoàn toàn không?
Có. Khi chia mọi số nguyên theo số dư khi chia cho 3 rồi xét đủ ba trường hợp, ta đang làm quy nạp hoàn toàn trên ba nhóm. Điều kiện là các trường hợp phải phủ kín, không sót.
Vì sao số Fermat là ví dụ hay về quy nạp không hoàn toàn?
Vì năm số Fermat đầu tiên 3, 5, 17, 257, 65537 đều nguyên tố, khiến Fermat tin mọi số dạng 2^(2ⁿ) + 1 đều nguyên tố. Năm 1732 Euler chỉ ra số thứ sáu, 4 294 967 297, bằng 641 × 6 700 417. Một phản ví dụ đủ đánh đổ một kết luận dựa trên năm trường hợp đúng.
