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 A 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 A nhỏ hơn hoặc bằng mọi phần tử khác của A. Về mặt hình thức, \forall A \left[ \left( A \subseteq \mathbb{Z}_{\geq 0} \land A \neq \varnothing \right) \rightarrow \left( \exists m \in A \, \forall a \in A \, (m \leq a) \right) \right]. 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 \mathbb{N} bất kể nó được định nghĩa là \mathbb{Z}_{\geq 0} (số nguyên không âm) hay \mathbb{Z}^+ (số nguyên dương), vì một trong các tiên đề Peano cho \mathbb{N}, 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 \mathbb{Z}^+ \subseteq \mathbb{Z}_{\geq 0} và quan hệ tập hợp con \subseteq bắc cầu, mệnh đề về \mathbb{Z}^+ được suy ra từ mệnh đề về \mathbb{Z}_{\geq 0}.

{{Quote box
| quote = Thực hành cho thấy nguyên lý này đúng. Ví dụ, tập T = {5, 8, 3, 11} có phần tử nhỏ nhất là 3, và 2 là phần tử nhỏ nhất trong tập hợp các số dương chẵn. Đây là một nguyên lý hiển nhiên đến mức đánh lừa vì trong nhiều trường hợp, không rõ số nhỏ nhất thực sự là bao nhiêu.
| author = Lars Tuset
| source = Abstract Algebra via Numbers (Đại số trừu tượng qua các con số)
| width = 30%
| align = right
}}

Thứ tự tiêu chuẩn trên \mathbb{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 \mathbb{R} (hoặc trên \mathbb{Z}) 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 \mathbb{R} đượ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." 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 ). 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 trong đó quy nạp mạnh được chứng minh là tương đương nguyên lý sắp tốt; hoặc, trong đó tính tương đương của ba nguyên lý được chứng minh bằng cách chỉ ra nguyên lý quy nạp kéo theo nguyên lý quy nạp mạnh, nguyên lý quy nạp mạnh kéo theo nguyên lý sắp tốt và nguyên lý sắp tốt kéo theo nguyên lý quy nạp.|group=lower-alpha}}).

Đ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, \mathbb{N} = \{ x \in S \mid 0 \in S \land \forall n \in S,\; n+1 \in S \}, tương đương việc phát biểu nguyên lý sắp tốt đúng với nó. Đ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 \mathbb{R} có một cận dưới đúng, nghĩa là, vì \mathbb{Z}_{\geq 0} là một tập con bị chặn dưới của \mathbb{R} (và quan hệ tập hợp con \subseteq bắc cầu), nên mọi tập A \subseteq \mathbb{Z}_{\geq 0} có một cận dưới đúng a, dẫn đến tồn tại số nguyên n sao cho a nằm trong nửa khoảng (n-1,n], suy ra rằng a = n và n \in A.

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ể S, 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 n thỏa mãn 0 . 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à n. Từ 0 , nhân mọi vế của bất đẳng thức với n thu được 0 . Nhưng nếu n là số nguyên, thì n^2 cũng là số nguyên, điều này mâu thuẫn với giả định ban đầu rằng n 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 S tạo thành bởi các số nguyên không âm a_1 > a_2 > a_3 > \cdots; khi đó theo nguyên lý sắp tốt, S có phần tử nhỏ nhất a_k với k nào đó. Nhưng a_k phải là phần tử cuối cùng trong dãy, nếu không a_{k+1} , điều này mâu thuẫn với giả định rằng a_k 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 C 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 C rỗng: giả sử phản chứng, C khác rỗng. Sau đó, theo nguyên lý sắp tốt, có một yếu tố ít nhất n \in C; n 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ố, n có các ước a, b, trong đó a, b là số nguyên lớn hơn một và nhỏ hơn n. Do a, b , chúng không thuộc C vì n là phần tử nhỏ nhất của C. Vì vậy, a, b có thể phân tích thành thừa số nguyên tố, với a = p_1p_2...p_k và b = q_1q_2...q_l, nghĩa là n = p_1p_2...p_k \cdot q_1q_2...q_l, một tích các số nguyên tố. Điều này mâu thuẫn với giả định n \in C, nên giả định C 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