Chứng minh tồn tại là chỉ ra rằng có ít nhất một đối tượng thoả điều kiện, hoặc bằng cách đưa ra hẳn đối tượng đó (chứng minh xây dựng), hoặc bằng cách lập luận rằng nó không thể không có (chứng minh không xây dựng); chứng minh duy nhất là chỉ ra mọi đối tượng thoả điều kiện đều trùng nhau. Hai phần này đi cùng nhau trong cụm quen thuộc "tồn tại duy nhất", và phải làm đủ cả hai.
Bài này đi qua ba công cụ tồn tại hay dùng ở năm đầu đại học: xây dựng trực tiếp, nguyên lý Dirichlet (còn gọi là nguyên lý chuồng bồ câu) và định lý giá trị trung gian; khuôn chứng minh duy nhất bằng cách giả sử có hai; những lỗi hay gặp; và vì sao phân biệt "có tồn tại" với "tìm được" quan trọng với người học toán để làm tối ưu hay AI.
Tồn tại xây dựng: đưa vật ra là xong
Cách chứng minh tồn tại dễ hiểu nhất là chỉ thẳng ra một đối tượng rồi kiểm nó thoả điều kiện. Mệnh đề "tồn tại hai số vô tỉ có tổng là số hữu tỉ" được chứng minh bằng một dòng: căn bậc hai của 2 và trừ căn bậc hai của 2 đều vô tỉ, tổng bằng 0 là số hữu tỉ. Mệnh đề "giữa hai số hữu tỉ khác nhau a nhỏ hơn b luôn có một số hữu tỉ khác" được chứng minh bằng cách đưa ra (a + b)/2: nó là số hữu tỉ vì tổng và thương của số hữu tỉ là số hữu tỉ, và nó nằm giữa a và b vì là trung bình cộng.
Ưu điểm của chứng minh xây dựng là nó cho bạn nhiều hơn điều mệnh đề hứa: không chỉ biết có, mà còn biết nó là gì và cách tạo ra nó. Trong ví dụ thứ hai, công thức (a + b)/2 dùng lặp lại được, nên từ đó suy ra luôn giữa hai số hữu tỉ có vô số số hữu tỉ.
Chỗ cần cẩn thận là khâu kiểm. Đưa ra một ứng viên mà không chứng minh nó thoả mọi điều kiện thì chưa xong. Ở ví dụ thứ nhất, bạn phải dẫn được vì sao trừ căn bậc hai của 2 vô tỉ: nếu nó hữu tỉ thì căn bậc hai của 2, bằng âm của nó, cũng hữu tỉ, trái với điều đã chứng minh. Một dòng thôi, nhưng không được bỏ.
Tồn tại không xây dựng: biết có mà không cần chỉ ra
Nguyên lý Dirichlet. Nếu xếp nhiều hơn n vật vào n ngăn thì có ít nhất một ngăn chứa từ hai vật trở lên. Áp dụng: trong 13 người bất kỳ, có ít nhất hai người sinh cùng tháng, vì chỉ có 12 tháng. Chứng minh không nói được đó là hai người nào, chỉ nói chắc chắn họ có mặt.
Một ví dụ hình học. Đặt 5 điểm bất kỳ trong một hình vuông cạnh 2. Chia hình vuông thành 4 ô vuông cạnh 1. Có 5 điểm và 4 ô nên một ô chứa ít nhất 2 điểm, và hai điểm trong cùng một ô cạnh 1 cách nhau không quá độ dài đường chéo, tức căn bậc hai của 2. Vậy luôn có hai điểm cách nhau không quá căn bậc hai của 2.
Ví dụ kinh điển dùng phân chia trường hợp. Mệnh đề: tồn tại hai số vô tỉ a, b sao cho a mũ b là số hữu tỉ. Xét x bằng căn 2 mũ căn 2. Nếu x hữu tỉ thì lấy a = b = căn 2 là xong. Nếu x vô tỉ thì lấy a = x, b = căn 2, khi đó a mũ b bằng căn 2 mũ (căn 2 nhân căn 2), tức căn 2 bình phương, bằng 2, là số hữu tỉ. Trường hợp nào cũng có cặp cần tìm, dù chứng minh không cho biết là trường hợp nào.
Một ghi chú về ví dụ trên. Nhờ một định lý sâu hơn nhiều trong lý thuyết số, người ta biết rằng căn 2 mũ căn 2 thực ra là số vô tỉ, nên trường hợp thứ hai mới là trường hợp xảy ra. Nhưng chứng minh ở trên không cần biết điều đó, và đó chính là điểm đẹp của nó.
Định lý giá trị trung gian: tồn tại nghiệm mà không giải phương trình
Trong giải tích, công cụ tồn tại quen thuộc nhất là định lý giá trị trung gian: nếu hàm f liên tục trên đoạn từ a tới b, và f(a), f(b) trái dấu, thì có ít nhất một c nằm giữa a và b với f(c) = 0. Ví dụ với phương trình x³ + x − 1 = 0:
- Đặt f(x) = x³ + x − 1. Đây là đa thức nên liên tục trên toàn trục số.
- Tính f(0) = −1, âm, và f(1) = 1 + 1 − 1 = 1, dương.
- Theo định lý giá trị trung gian, có ít nhất một nghiệm nằm giữa 0 và 1.
- Muốn khoanh vùng hẹp hơn, chia đôi: f(0,5) = 0,125 + 0,5 − 1 = −0,375, âm, nên nghiệm nằm giữa 0,5 và 1. Tiếp: f(0,75) = 0,421875 + 0,75 − 1 = 0,171875, dương, nên nghiệm nằm giữa 0,5 và 0,75. Lặp tiếp sẽ tới gần giá trị khoảng 0,682.
- Để chứng minh nghiệm là duy nhất, chỉ ra f tăng ngặt: nếu x nhỏ hơn y thì x³ nhỏ hơn y³, nên f(x) nhỏ hơn f(y). Một hàm tăng ngặt không thể nhận giá trị 0 tại hai điểm khác nhau.
Ví dụ này cho thấy cách hai phần "tồn tại" và "duy nhất" dùng hai công cụ khác nhau. Định lý giá trị trung gian cho tồn tại nhưng không nói gì về số nghiệm; tính tăng ngặt cho duy nhất nhưng tự nó không nói nghiệm có hay không. Thiếu một trong hai là chứng minh chưa đủ.
Khuôn chứng minh duy nhất: giả sử có hai
Khuôn chuẩn để chứng minh duy nhất rất gọn: giả sử có hai đối tượng x và y cùng thoả điều kiện, rồi chứng minh x = y. Không cần giả sử x khác y; chỉ cần đi từ hai điều kiện tới đẳng thức. Ví dụ trong đại số tuyến tính: nếu ma trận vuông A có nghịch đảo thì nghịch đảo đó là duy nhất. Giả sử B và C đều là nghịch đảo của A, tức BA = AB = I và CA = AC = I, với I là ma trận đơn vị. Khi đó B = BI = B(AC) = (BA)C = IC = C. Mỗi dấu bằng dùng đúng một tính chất: định nghĩa ma trận đơn vị, giả thiết AC = I, tính kết hợp của phép nhân ma trận, giả thiết BA = I.
Một ví dụ khác, đơn giản hơn: với a khác 0, phương trình ax = b có nghiệm duy nhất. Tồn tại: x = b/a thoả phương trình. Duy nhất: nếu ax = b và ay = b thì a(x − y) = 0, mà a khác 0 nên x − y = 0. Để ý bước cuối dùng tính chất tích bằng 0 thì một thừa số bằng 0, đúng với số thực nhưng không đúng với ma trận, và đó là lý do bài toán tương tự với ma trận cần thêm điều kiện khả nghịch.
Có thể viết duy nhất bằng phản chứng: giả sử có hai đối tượng khác nhau rồi dẫn tới mâu thuẫn. Cách này hợp lệ, nhưng thường mâu thuẫn cuối cùng chính là "hai đối tượng bằng nhau", nên viết thẳng theo khuôn ở trên gọn hơn.
Lỗi hay gặp với tồn tại và duy nhất
Chỉ làm một nửa. Đề yêu cầu tồn tại duy nhất mà chỉ chứng minh duy nhất, hoặc chỉ đưa ra nghiệm rồi dừng. Một phương trình có thể có nghiệm duy nhất theo nghĩa "nếu có thì chỉ có một" mà lại không có nghiệm nào.
Tìm được một nghiệm rồi kết luận là duy nhất. Giải ra x = 2 bằng một chuỗi biến đổi không có nghĩa là không còn nghiệm nào khác, nếu chuỗi biến đổi có bước một chiều như bình phương hai vế hay chia cho biểu thức có thể bằng 0.
Dùng định lý tồn tại mà không kiểm giả thiết. Định lý giá trị trung gian cần hàm liên tục trên cả đoạn. Hàm 1/x có giá trị âm tại −1 và dương tại 1 nhưng không có nghiệm, vì nó không xác định, càng không liên tục, tại 0.
Nhầm số ngăn và số vật trong nguyên lý Dirichlet. Cần số vật lớn hơn số ngăn. 12 người thì chưa chắc có hai người cùng tháng sinh. Trước khi dùng, hãy viết ra rõ đâu là vật, đâu là ngăn, và đếm cả hai. Phần sáng tạo của bài thường nằm ở chỗ chọn ngăn, như chia hình vuông thành bốn ô ở ví dụ trên.
Có tồn tại khác với tìm được: vì sao người làm tối ưu và AI cần biết
Trong giải tích có một định lý tồn tại rất quan trọng: hàm liên tục trên một đoạn đóng và bị chặn thì đạt giá trị lớn nhất và nhỏ nhất trên đoạn đó. Định lý bảo đảm cực trị có tồn tại, nhưng không chỉ cách tìm. Người làm tối ưu và người học các thuật toán huấn luyện mô hình AI gặp đúng khoảng cách này hằng ngày: lý thuyết nói có một điểm tốt nhất, còn thuật toán thì đi từng bước để tới gần nó, và có thể dừng ở một điểm chỉ tốt cục bộ.
Hiểu sự khác biệt này giúp bạn đọc tài liệu kỹ thuật tỉnh táo hơn. Câu "bài toán có nghiệm tối ưu" là một khẳng định tồn tại. Câu "thuật toán hội tụ về nghiệm tối ưu" là một khẳng định khác hẳn, cần giả thiết riêng như hàm lồi, bước nhảy đủ nhỏ. Lẫn hai câu với nhau là lỗi phổ biến khi đọc lướt.
Khi nhờ chatbot giải thích một định lý tồn tại, một câu hỏi hay là: "Định lý này có cho cách tìm đối tượng không, hay chỉ bảo đảm nó tồn tại? Nếu muốn tìm thật, thường dùng phương pháp gì?" Sau đó tự kiểm câu trả lời bằng giáo trình, vì đây là chỗ AI hay nói gộp hai ý làm một.
Câu hỏi thường gặp
Chứng minh xây dựng và không xây dựng khác nhau thế nào?
Chứng minh xây dựng đưa ra hẳn đối tượng rồi kiểm nó thoả điều kiện. Chứng minh không xây dựng chỉ ra đối tượng phải tồn tại, ví dụ bằng nguyên lý Dirichlet hay phản chứng, mà không cho biết cụ thể nó là gì.
Nguyên lý Dirichlet dùng thế nào cho đúng?
Xác định rõ đâu là vật, đâu là ngăn, và chắc chắn số vật lớn hơn số ngăn. Khi đó có ít nhất một ngăn chứa từ hai vật trở lên. Phần khó thường là chọn cách chia ngăn phù hợp với bài.
Chứng minh duy nhất có cần chứng minh tồn tại không?
Nếu đề yêu cầu tồn tại duy nhất thì cần cả hai. Chỉ chứng minh duy nhất mới nói rằng nếu có thì chỉ có một, chưa nói là có. Hai phần thường dùng hai công cụ khác nhau.
Định lý giá trị trung gian có cho biết số nghiệm không?
Không. Nó chỉ bảo đảm có ít nhất một nghiệm trong khoảng khi hàm liên tục và hai đầu trái dấu. Muốn biết có đúng một nghiệm, cần thêm lập luận như hàm tăng ngặt hoặc giảm ngặt trên khoảng đó.
Vì sao khuôn giả sử có hai được dùng nhiều để chứng minh duy nhất?
Vì nó gọn và trực tiếp: lấy hai đối tượng cùng thoả điều kiện rồi chứng minh chúng bằng nhau. Không cần giả sử chúng khác nhau, nên tránh được lớp vỏ phản chứng thừa.
Có tồn tại nghiệm tối ưu thì thuật toán có tìm ra không?
Chưa chắc. Định lý tồn tại chỉ bảo đảm có điểm tốt nhất. Thuật toán có tìm tới được hay không là một câu hỏi khác, phụ thuộc vào giả thiết như tính lồi của hàm và cách chọn bước.