Quy nạp toán học và quy nạp khoa học trùng tên nhưng khác hẳn bản chất: quy nạp toán học là một phép suy diễn chặt chẽ, kết luận chắc chắn cho mọi số tự nhiên nhờ hai bước cơ sở và bước chuyển; còn quy nạp khoa học đi từ một số quan sát tới kết luận chung, nên luôn có thể sai. Gọi chung một chữ "quy nạp" chỉ vì cả hai cùng đi tới một mệnh đề cho "mọi trường hợp" — cách đi thì ngược nhau.
Đặt hai thứ cạnh nhau
Hai câu nghe có vẻ cùng loại:
- (1) "Tổng n số lẻ đầu tiên luôn bằng n²."
- (2) "Mọi mẫu nước tinh khiết ở áp suất 1 atm đều sôi ở 100 °C."
Thử vài trường hợp của câu (1): 1 = 1²; 1 + 3 = 4 = 2²; 1 + 3 + 5 = 9 = 3²; 1 + 3 + 5 + 7 = 16 = 4². Thử vài mẫu nước cho câu (2): mẫu nào cũng sôi ở 100 °C. Tới đây hai câu ở cùng một vị thế: thấy đúng ở mọi trường hợp đã thử.
Khác biệt bắt đầu ở bước tiếp theo. Câu (1) có thể được chứng minh cho mọi n, vĩnh viễn, không cần thử thêm số nào. Câu (2) không bao giờ đạt tới vị thế đó: mẫu nước tiếp theo vẫn là một lần thử mới, và nếu một ngày đo được kết quả khác (mà mọi điều kiện đã kiểm kỹ), câu (2) phải sửa.
Quy nạp toán học: vì sao nó là suy diễn
Nguyên lý quy nạp toán học, nói gọn: nếu mệnh đề P(1) đúng, và với mọi k, từ P(k) đúng suy ra được P(k + 1) đúng, thì P(n) đúng với mọi số tự nhiên n ≥ 1.
Áp vào câu (1). Gọi P(n): 1 + 3 + … + (2n − 1) = n².
- Cơ sở: n = 1, vế trái là 1, vế phải 1² = 1. Đúng.
- Bước chuyển: giả sử P(k) đúng, tức 1 + 3 + … + (2k − 1) = k². Số lẻ tiếp theo là 2(k + 1) − 1 = 2k + 1. Cộng vào hai vế: 1 + 3 + … + (2k − 1) + (2k + 1) = k² + 2k + 1 = (k + 1)². Đó chính là P(k + 1).
Thử lại với n = 6: 1 + 3 + 5 + 7 + 9 + 11 = 36 = 6². Khớp — nhưng phép thử này chỉ để yên tâm là không tính nhầm; chứng minh không cần nó.
Điểm mấu chốt: bước chuyển không quan sát gì cả. Nó là một phép biến đổi đại số đúng cho một k bất kỳ. Nguyên lý quy nạp thì là một tính chất của tập số tự nhiên — trong cách xây dựng hiện đại, nó được đặt làm một tiên đề (hệ tiên đề Peano, 1889) hoặc suy ra từ tính chất "mọi tập con khác rỗng của ℕ có phần tử nhỏ nhất". Từ tiên đề và hai bước đã chứng minh, kết luận đi ra theo đúng quy tắc suy diễn. Không có chỗ nào cho "có lẽ".
Phần kỹ thuật chứng minh bằng quy nạp (quy nạp mạnh, quy nạp hai bước, cách chọn mệnh đề cho khéo) được bàn ở site toán khác trong hệ; bài này chỉ dùng một ví dụ để so sánh.
Quy nạp khoa học: vì sao nó không thể chắc chắn
Với câu (2), không có "bước chuyển" nào. Ta không thể chứng minh "nếu mẫu thứ k sôi ở 100 °C thì mẫu thứ k + 1 cũng thế" bằng đại số. Thứ nối các mẫu với nhau là niềm tin rằng tự nhiên đồng dạng — đúng chỗ David Hume chỉ ra là không chứng minh được mà không vòng quanh (xem bài về Hume trong danh mục này).
Khoa học bù chỗ thiếu này bằng lý thuyết giải thích (vì sao nước sôi ở nhiệt độ đó, phụ thuộc áp suất ra sao), bằng thí nghiệm có kiểm soát, và bằng việc nói rõ phạm vi (nước tinh khiết, áp suất 1 atm). Kết quả là kết luận rất đáng tin — nhưng loại đáng tin đó vẫn khác về chủng loại với chứng minh toán học.
Bảng so sánh
| Quy nạp toán học | Quy nạp khoa học | |
|---|---|---|
| Bản chất | Suy diễn | Suy luận có tính xác suất |
| Đối tượng | Mệnh đề về số tự nhiên (hoặc cấu trúc xây dựng từng bước) | Quy luật về thế giới tự nhiên, xã hội |
| Bước then chốt | Chứng minh P(k) → P(k + 1) cho k bất kỳ | Quan sát, thí nghiệm, tìm cơ chế |
| Thử thêm trường hợp | Không cần, không làm kết luận mạnh thêm | Cần, làm kết luận mạnh thêm |
| Một phản ví dụ | Không thể có nếu chứng minh đúng | Có thể xuất hiện bất cứ lúc nào |
| Kết luận | Chắc chắn, vĩnh viễn | Tạm thời, sửa được |
Khi nhà toán học dùng quy nạp kiểu khoa học
Toán học cũng dùng quy nạp không hoàn toàn — nhưng chỉ ở khâu đoán. Ví dụ nổi tiếng về chỗ đoán dễ sai:
Chia hình tròn: đặt n điểm trên đường tròn, nối mọi cặp điểm bằng dây cung (chọn vị trí sao cho không có ba dây nào cắt nhau tại một điểm). Đếm số miền trong hình tròn:
| Số điểm n | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Số miền | 1 | 2 | 4 | 8 | 16 | 31 |
Năm giá trị đầu gợi ý ngay "số miền là 2ⁿ⁻¹", và n = 6 phải ra 32. Thực tế là 31. Công thức đúng là C(n, 4) + C(n, 2) + 1, trong đó C(n, k) là số cách chọn k phần tử từ n phần tử. Kiểm: n = 5 cho 5 + 10 + 1 = 16; n = 6 cho 15 + 15 + 1 = 31; n = 4 cho 1 + 6 + 1 = 8. Năm lần "đúng" của công thức 2ⁿ⁻¹ chỉ là trùng hợp của những số nhỏ.
Ở chiều ngược lại, giả thuyết Goldbach (mọi số chẵn lớn hơn 2 là tổng hai số nguyên tố) đã được máy tính kiểm cho các số chẵn tới hơn 10¹⁸ mà chưa thấy ngoại lệ. Theo chuẩn khoa học, đó là bằng chứng cực mạnh. Theo chuẩn toán học, nó vẫn chỉ là giả thuyết, vì chưa ai chứng minh được.
Đây là chỗ thể hiện rõ nhất sự khác biệt: cùng một khối lượng bằng chứng, nhà vật lý gọi là định luật, nhà toán học gọi là giả thuyết.
Lỗi hay gặp khi dùng quy nạp toán học
- Bỏ bước cơ sở: bước chuyển đúng mà cơ sở sai thì cả chuỗi sụp. Ví dụ "n² + n là số lẻ": nếu n² + n lẻ thì (n + 1)² + (n + 1) = (n² + n) + 2n + 2 cũng lẻ (cộng thêm số chẵn) — bước chuyển đúng! Nhưng n = 1 cho 2, chẵn. Mệnh đề sai với mọi n.
- Bước chuyển không đúng với mọi k: lập luận "mọi con ngựa cùng màu" nổi tiếng (thường gắn với George Pólya) gãy đúng ở bước từ 1 sang 2 con, vì phần "chồng lên nhau" của hai nhóm khi đó rỗng. Ai từng làm bài này sẽ nhớ: bước chuyển phải kiểm với cả k nhỏ nhất.
- Thử vài số rồi viết "theo quy nạp ta có…": đó là quy nạp không hoàn toàn khoác tên quy nạp toán học — lỗi thường bị trừ điểm khi chấm thi.
Đôi nét lịch sử và chuyện tên gọi
- Khoảng 1654: Blaise Pascal dùng lập luận kiểu quy nạp trong chuyên luận về tam giác số học, một trong những trình bày rõ ràng sớm của kỹ thuật này.
- 1838: Augustus De Morgan đặt tên "mathematical induction" (quy nạp toán học).
- 1889: Giuseppe Peano công bố hệ tiên đề cho số tự nhiên, trong đó nguyên lý quy nạp là một tiên đề.
Một bẫy thuật ngữ: trong tiếng Anh, "complete induction" đôi khi chỉ quy nạp toán học dạng mạnh, trong khi "quy nạp hoàn toàn" trong giáo trình Logic học đại cương tiếng Việt lại là xét hết mọi phần tử của một lớp hữu hạn. Đọc tài liệu dịch, hãy xem ngữ cảnh trước khi hiểu.
Bài tập
- "Định luật bảo toàn khối lượng đã được kiểm trong hàng triệu phản ứng" — đây là quy nạp loại nào? — Đáp án: quy nạp khoa học (quy nạp không hoàn toàn có cơ sở lý thuyết); kết luận rất đáng tin nhưng không có tính chắc chắn kiểu toán học (thực tế nó còn được hiệu chỉnh trong vật lý hạt nhân).
- Chỉ ra bước sai: "P(n): n = n + 1. Nếu k = k + 1 thì cộng 1 vào hai vế được k + 1 = k + 2, tức P(k + 1). Vậy P(n) đúng với mọi n." — Đáp án: thiếu bước cơ sở; P(1) là 1 = 2, sai.
- Kiểm công thức số miền cho n = 3 và n = 2. — Đáp án: n = 3: C(3, 4) = 0, C(3, 2) = 3, tổng 0 + 3 + 1 = 4; n = 2: 0 + 1 + 1 = 2. Khớp bảng.
- Vì sao giả thuyết Goldbach chưa được coi là định lý dù đã kiểm tới hơn 10¹⁸? — Đáp án: vì tập số chẵn vô hạn và chưa có chứng minh cho mọi số; kiểm hữu hạn trường hợp chỉ là quy nạp không hoàn toàn.
Dùng vào đâu
- Thi THPT, học sinh giỏi: nhớ rằng bài chứng minh "với mọi n" bằng quy nạp phải có đủ hai bước; thử vài số chỉ là nháp.
- Thi Logic học đại cương: câu hỏi "quy nạp toán học có phải quy nạp không" — trả lời: về bản chất là suy diễn.
- Lập trình: chứng minh vòng lặp đúng bằng "bất biến vòng lặp" chính là quy nạp toán học; chạy thử vài bộ dữ liệu chỉ là quy nạp khoa học.
- Học tiếp: bài về quy nạp hoàn toàn và không hoàn toàn, bài về Hume trong danh mục này; mục "Problem of Induction" trên Stanford Encyclopedia of Philosophy.
Câu hỏi thường gặp
Quy nạp toán học có phải là quy nạp không?
Về tên gọi thì có, về bản chất thì không. Quy nạp toán học là một phép suy diễn: từ bước cơ sở, bước chuyển và nguyên lý quy nạp, kết luận được rút ra chắc chắn. Nó không dựa vào việc quan sát nhiều trường hợp.
Quy nạp toán học khác quy nạp khoa học thế nào?
Quy nạp toán học chứng minh một mệnh đề cho mọi số tự nhiên bằng lập luận chặt chẽ, nên không thể có phản ví dụ nếu chứng minh đúng. Quy nạp khoa học khái quát từ các quan sát, luôn có thể bị một quan sát mới bác bỏ. Thêm trường hợp thử chỉ có ý nghĩa với quy nạp khoa học.
Vì sao thử nhiều trường hợp vẫn không chứng minh được một mệnh đề toán học?
Vì tập số tự nhiên vô hạn, và mẫu hình đúng ở các số nhỏ có thể gãy ở số lớn hơn. Bài chia hình tròn cho 1, 2, 4, 8, 16 miền rồi đến 31 chứ không phải 32 là ví dụ quen thuộc. Chỉ chứng minh mới bảo đảm mệnh đề đúng với mọi n.
Ai đặt tên quy nạp toán học?
Augustus De Morgan đặt tên "mathematical induction" năm 1838. Kỹ thuật này đã được dùng trước đó, chẳng hạn trong chuyên luận về tam giác số học của Pascal. Năm 1889, Peano đưa nguyên lý quy nạp vào hệ tiên đề số tự nhiên.
Bỏ bước cơ sở trong quy nạp toán học thì sao?
Chứng minh sẽ hỏng, dù bước chuyển đúng. Ví dụ mệnh đề "n² + n là số lẻ" có bước chuyển đúng nhưng sai ngay từ n = 1. Cơ sở là điểm xuất phát của cả chuỗi suy diễn.
