Difference between revisions of "Well Ordering Principle"

Revision as of 21:19, 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 the theorem 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.

@@ Line 1: / Line 1: @@
-The '''Well Ordering Principle''' states that every nonempty set of positive integers contains a smallest member. The proof of this is simply common sense, but we can construct a formal proof by contradiction. Assume there is no smallest element. Then for each element in the set, there exists a smaller element, so if we take this smaller element, there must a different smaller element, and so on. Since the set is finite, we cannot continue like this infinitely many times, contradiction.
+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.
-{{stub}}
+'''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
-[[Category:Axioms]]
+<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.
+''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.

Page

Toolbox

Search

Difference between revisions of "Well Ordering Principle"

Revision as of 21:19, 12 May 2022