Nguyên lý sắp thứ tự tốt

Trong toán học, nguyên lý sắp thứ tự tốt, còn gọi là tính chất sắp thứ tự tốt hay đơn giản là nguyên lý sắp tốt, phát biểu rằng mỗi tập con khác rỗng của tập hợp số nguyên không âm có phần tử nhỏ nhất. Nói cách khác, nếu  là một tập con khác rỗng của tập số nguyên không âm, thì có một phần tử của   hoặc bằng mọi phần tử khác của . Về mặt hình thức, . Hầu hết các nguồn nói rằng đây là một tiên đề hoặc định lý về số tự nhiên, nhưng cụm từ "số tự nhiên" đã được tránh ở trên do tranh cãi về việc bao gồm số không. Phát biểu này đúng cho tập hợp số tự nhiên  bất kể nó được định nghĩa là  (số nguyên không âm) hay  (số nguyên dương), vì một trong các tiên đề Peano cho , tiên đề quy nạp (hoặc nguyên lý quy nạp toán học), là tương đương về mặt logic với nguyên lý sắp thứ tự tốt. Do  và quan hệ tập hợp con  bắc cầu, mệnh đề về  được suy ra từ mệnh đề về .

Thứ tự tiêu chuẩn trên  được sắp tốt theo nguyên lý sắp thứ tự tốt, vì nó bắt đầu bằng phần tử nhỏ nhất, bất kể là 1 hay 0. Ngược lại, thứ tự tiêu chuẩn trên  (hoặc trên ) không được sắp tốt theo nguyên lý này, vì không có số âm nhỏ nhất. Theo Deaconu và Pfaff, cụm từ "nguyên lý sắp thứ tự tốt" được một số tác giả (không nêu tên) sử dụng làm tên cho "định lý sắp thứ tự tốt" của Zermelo trong lý thuyết tập hợp, theo đó mọi tập hợp đều có thể được sắp tốt. Định lý, không phải là chủ đề của bài viết này, kéo theo rằng "về nguyên tắc, có thứ tự khác nào đó trên  được sắp tốt, mặc dù dường như không có mô tả cụ thể nào về thứ tự như vậy."

Tương đương với quy nạp 
Nguyên lý sắp tốt tương đương về mặt logic với nguyên lý quy nạp toán học, theo đó . Nói cách khác, nếu ta lấy nguyên lý quy nạp toán học làm tiên đề, ta có thể chứng minh nguyên lý sắp tốt như định lý (như đã thực hiện trong ), và ngược lại, nếu ta lấy nguyên lý sắp tốt làm tiên đề, ta có thể chứng minh nguyên lý quy nạp toán học như định lý (như đã thực hiện trong ). Cách đầu tiên phổ biến hơn theo truyền thống, vì nguyên lý quy nạp toán học là một trong những tiên đề về các số tự nhiên của Peano, một nhà toán học có ảnh hưởng.

Nguyên lý quy nạp toán học và nguyên lý sắp tốt đều tương đương với nguyên lý quy nạp mạnh, theo đó .  Vì vậy, người ta cũng có thể dùng nguyên lý quy nạp mạnh làm tiên đề để chứng minh nguyên lý sắp tốt như định lý (như đã thực hiện trong ), hoặc xem nguyên lý sắp tốt là tiên đề để chứng minh nguyên lý quy nạp mạnh như định lý (như trong ).

Điều này cũng có nghĩa, trong lý thuyết tập hợp tiên đề, định nghĩa tập số tự nhiên là tập quy nạp nhỏ nhất, , tương đương việc phát biểu nguyên lý sắp tốt đúng với nó.

Suy ra từ tính đầy đủ của số thực 
Nếu biết rằng các số thực là đầy đủ, thì người ta có thể sử dụng điều này để chứng minh nguyên lý sắp tốt cho các số nguyên không âm. Điều này là do tính đầy đủ kéo theo mọi tập hợp bị chặn dưới của  có một cận dưới đúng, nghĩa là, vì  là một tập con bị chặn dưới của  (và quan hệ tập hợp con  bắc cầu), nên mọi tập  có một cận dưới đúng , dẫn đến tồn tại số nguyên  sao cho  nằm trong nửa khoảng , suy ra rằng  và .

Phi đại số 
Nguyên lý sắp tốt, giống như nguyên lý cận trên đúng đối với số thực, phi đại số, tức là, nó không thể được suy ra từ các tính chất đại số của số nguyên (các tính chất này tạo thành một miền nguyên có thứ tự).

Ứng dụng 
Nguyên lý sắp tốt được sử dụng trong chứng minh bằng phản ví dụ cực tiểu, trong đó để chứng minh rằng mọi số tự nhiên đều thuộc về một tập hợp cụ thể , ta giả định điều ngược lại, từ đó suy ra rằng tập hợp phản ví dụ khác rỗng và do đó (áp dụng nguyên lý sắp giếng) chứa một phản ví dụ nhỏ nhất. Sau đó, ta chỉ ra rằng, với bất kỳ phản ví dụ nào, luôn tồn tại một phản ví dụ nhỏ hơn nữa, dẫn đến mâu thuẫn. Phương thức lập luận này là phản đảo của chứng minh bằng quy nạp mạnh, và về bản chất tương tự như phương pháp lùi vô hạn của Fermat. Sau đây là một vài ví dụ.

Ví dụ: không có số nguyên nào giữa 0 và 1 
Định lý: Không có số nguyên nào nằm giữa 0 và 1, do đó 1 là số nguyên dương nhỏ nhất.

Chứng minh. Giả sử phản chứng, tồn tại một số nguyên  thỏa mãn . Theo nguyên lý sắp tốt, tập hợp các số nguyên dương nhỏ hơn 1 có phần tử nhỏ nhất, đặt là . Từ , nhân mọi vế của bất đẳng thức với  thu được . Nhưng nếu  là số nguyên, thì  cũng là số nguyên, điều này mâu thuẫn với giả định ban đầu rằng  là số nguyên dương nhỏ nhất giữa 0 và 1. Do đó, giả định này là sai, hay không có số nguyên nào giữa 0 và 1.

Ví dụ: mọi dãy số nguyên không âm giảm hữu hạn 
Định lý: Mọi dãy số nguyên không âm giảm đều hữu hạn.

Chứng minh. Giả sử tồn tại dãy giảm nghiêm ngặt  tạo thành bởi các số nguyên không âm ; khi đó theo nguyên lý sắp tốt,  có phần tử nhỏ nhất  với  nào đó. Nhưng  phải là phần tử cuối cùng trong dãy, nếu không , điều này mâu thuẫn với giả định rằng  là phần tử nhỏ nhất.

Ví dụ: phân tích thừa số nguyên tố 
Định lý: Mọi số nguyên lớn hơn 1 đều là tích của hữu hạn số nguyên tố. Đây là một phần trong định lý cơ bản của Số học.

Chứng minh. Gọi  là tập hợp tất cả số nguyên hơn một không thể phân tích thành thừa số nguyên tố. Ta chỉ ra  rỗng: giả sử phản chứng,  khác rỗng. Sau đó, theo nguyên lý sắp tốt, có một yếu tố ít nhất ;  không thể là số nguyên tố vì mỗi số nguyên tố được coi là tích các số nguyên tố. Theo định nghĩa của các số không nguyên tố,  có các ước , trong đó  là số nguyên lớn hơn một và nhỏ hơn . Do , chúng không thuộc  vì  là phần tử nhỏ nhất của . Vì vậy,  có thể phân tích thành thừa số nguyên tố, với  và , nghĩa là , một tích các số nguyên tố. Điều này mâu thuẫn với giả định , nên giả định  khác rỗng phải sai.

Ghi chú

Tham khảo

Liên kết ngoài 
 Chứng minh sự tương đương giữa nguyên lý sắp thứ tự tốt và nguyên lý quy nạp toán học

Nguyên lý toán học
Lý thuyết thứ tự