Difference between revisions of "Well Ordering Principle"
Aops turtle (talk | contribs) m |
|||
(One intermediate revision by the same user not shown) | |||
Line 1: | Line 1: | ||
− | The '''Well Ordering Principle''' states that every nonempty | + | 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 |
− | + | <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 <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 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 of the real numbers is said to be inductive if it contains the number
, and if for every
, the number
as well. Let
be the collection of all the inductive subsets of
. Then the positive integers denoted
are defined by the equation
![$\mathbb{Z}^{+}=\bigcap_{A\in \mathcal{A}}A$](http://latex.artofproblemsolving.com/c/3/9/c396409747b989fe26675f73841263ff1a24d534.png)
Using this definition, we can rephrase the principle of mathematical induction as follows: if is an inductive set of the positive integers, then
. We can now proceed with the proof.
Proof: We first show that for any , every nonempty subset of
has a smallest element. Let
be the set of all positive integers
where this statement holds. We see
contains
, since if
then the only subset of
is
itself. Then, supposing
contains
we show that it must contain
. Let
be a nonempty subset of
. If
then
is its smallest element. Otherwise, consider
, which is nonempty. Because
, this set has a smallest element, which will be the smallest element of
also. This means that
is inductive and
, so the statement is true for all
.
Now suppose
is nonempty. By choosing some
, the set
is also nonempty which means that
has a smallest element
. This means that
is the smallest element of
too, which completes the proof