Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Well Ordering Principle"

(This article had a horrendous proof that was really informal. I added significant rigor and formalism to this topic.)
 
Line 1: Line 1:
−
The '''Well Ordering Principle''' states that every nonempty subset of the positive integers <math>\mathbb{Z}^{+}</math> contains a smallest element.  While this theorem is mostly brushed off as common sense, there is a bit of formalism required to actually prove the theorem sufficiently.  We will do this here.   
+
The '''Well Ordering Principle''' states that every nonempty subset of the positive integers <math>\mathbb{Z}^{+}</math> contains a smallest element.  While this theorem is mostly brushed off as common sense, there is a bit of formalism required to actually prove it sufficiently.  We will do this here.   
  
 
'''Definition''': A subset <math>A</math> of the real numbers is said to be inductive if it contains the number <math>1</math>, and if for every <math>x\in A</math>, the number <math>x+1\in A</math> as well.  Let <math>\mathcal{A}</math> be the collection of all the inductive subsets of <math>\mathbb{R}</math>.  Then the positive integers denoted <math>\mathbb{Z}^{+}</math> are defined by the equation
 
'''Definition''': A subset <math>A</math> of the real numbers is said to be inductive if it contains the number <math>1</math>, and if for every <math>x\in A</math>, the number <math>x+1\in A</math> as well.  Let <math>\mathcal{A}</math> be the collection of all the inductive subsets of <math>\mathbb{R}</math>.  Then the positive integers denoted <math>\mathbb{Z}^{+}</math> are defined by the equation
−
<center><math>\mathbb{Z}^{+}=\bigcap_{A\in \mathcal{A}}A</math></center>
+
<center><math>\mathbb{Z}^{+}=\bigcap_{A\in \mathcal{A}}A</math>.</center>
  
 
Using this definition, we can rephrase the principle of mathematical induction as follows: if <math>A</math> is an inductive set of the positive integers, then <math>A=\mathbb{Z}^{+}</math>.  We can now proceed with the proof.
 
Using this definition, we can rephrase the principle of mathematical induction as follows: if <math>A</math> is an inductive set of the positive integers, then <math>A=\mathbb{Z}^{+}</math>.  We can now proceed with the proof.
Line 8: Line 8:
  
 
''Proof'': We first show that for any <math>n\in\mathbb{Z}^{+}</math>, every nonempty subset of <math>\{1,2,\ldots, n\}</math> has a smallest element.  Let <math>A</math> be the set of all positive integers <math>n</math> where this statement holds.  We see <math>A</math> contains <math>1</math>, since if <math>n=1</math> then the only subset of <math>\{1,2,\ldots, n\}</math> is <math>\{1\}</math> itself.  Then, supposing <math>A</math> contains <math>n</math> we show that it must contain <math>n+1</math>.  Let <math>C</math> be a nonempty subset of <math>\{1,2,\ldots, n+1\}</math>.  If <math>C=\{n+1\}</math> then <math>n+1</math> is its smallest element.  Otherwise, consider <math>C\cap \{1,2,\ldots,n\}</math>, which is nonempty.  Because <math>n\in A</math>, this set has a smallest element, which will be the smallest element of <math>C</math> also.  This means that <math>A</math> is inductive and <math>A=\mathbb{Z}^{+}</math>, so the statement is true for all <math>n\in\mathbb{Z}^{+}</math>.   
 
''Proof'': We first show that for any <math>n\in\mathbb{Z}^{+}</math>, every nonempty subset of <math>\{1,2,\ldots, n\}</math> has a smallest element.  Let <math>A</math> be the set of all positive integers <math>n</math> where this statement holds.  We see <math>A</math> contains <math>1</math>, since if <math>n=1</math> then the only subset of <math>\{1,2,\ldots, n\}</math> is <math>\{1\}</math> itself.  Then, supposing <math>A</math> contains <math>n</math> we show that it must contain <math>n+1</math>.  Let <math>C</math> be a nonempty subset of <math>\{1,2,\ldots, n+1\}</math>.  If <math>C=\{n+1\}</math> then <math>n+1</math> is its smallest element.  Otherwise, consider <math>C\cap \{1,2,\ldots,n\}</math>, which is nonempty.  Because <math>n\in A</math>, this set has a smallest element, which will be the smallest element of <math>C</math> also.  This means that <math>A</math> is inductive and <math>A=\mathbb{Z}^{+}</math>, so the statement is true for all <math>n\in\mathbb{Z}^{+}</math>.   
−
Now suppose <math>D\in \mathbb{Z}^{+}</math> is nonempty.  By choosing some <math>n\in D</math>, the set <math>A\cap\{1,2\ldots, n\}</math> is also nonempty which means that <math>A</math> has a smallest element <math>k</math>.  This means that <math>k</math> is the smallest element of <math>D</math> too, which completes the proof.
+
Now suppose <math>D\in \mathbb{Z}^{+}</math> is nonempty.  By choosing some <math>n\in D</math>, the set <math>A\cap\{1,2\ldots, n\}</math> is also nonempty which means that <math>A</math> has a smallest element <math>k</math>.  This means that <math>k</math> is the smallest element of <math>D</math> too, which completes the proof <math>\square</math>

Latest revision as of 22:20, 12 May 2022

The Well Ordering Principle states that every nonempty subset of the positive integers $\mathbb{Z}^{+}$ contains a smallest element. While this theorem is mostly brushed off as common sense, there is a bit of formalism required to actually prove it sufficiently. We will do this here.

Definition: A subset $A$ of the real numbers is said to be inductive if it contains the number $1$, and if for every $x\in A$, the number $x+1\in A$ as well. Let $\mathcal{A}$ be the collection of all the inductive subsets of $\mathbb{R}$. Then the positive integers denoted $\mathbb{Z}^{+}$ are defined by the equation

$\mathbb{Z}^{+}=\bigcap_{A\in \mathcal{A}}A$.

Using this definition, we can rephrase the principle of mathematical induction as follows: if $A$ is an inductive set of the positive integers, then $A=\mathbb{Z}^{+}$. We can now proceed with the proof.


Proof: We first show that for any $n\in\mathbb{Z}^{+}$, every nonempty subset of $\{1,2,\ldots, n\}$ has a smallest element. Let $A$ be the set of all positive integers $n$ where this statement holds. We see $A$ contains $1$, since if $n=1$ then the only subset of $\{1,2,\ldots, n\}$ is $\{1\}$ itself. Then, supposing $A$ contains $n$ we show that it must contain $n+1$. Let $C$ be a nonempty subset of $\{1,2,\ldots, n+1\}$. If $C=\{n+1\}$ then $n+1$ is its smallest element. Otherwise, consider $C\cap \{1,2,\ldots,n\}$, which is nonempty. Because $n\in A$, this set has a smallest element, which will be the smallest element of $C$ also. This means that $A$ is inductive and $A=\mathbb{Z}^{+}$, so the statement is true for all $n\in\mathbb{Z}^{+}$. Now suppose $D\in \mathbb{Z}^{+}$ is nonempty. By choosing some $n\in D$, the set $A\cap\{1,2\ldots, n\}$ is also nonempty which means that $A$ has a smallest element $k$. This means that $k$ is the smallest element of $D$ too, which completes the proof $\square$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Well_Ordering_Principle&oldid=173922"