> [!NOTE] **Proposition** (Well-Ordering Principle) > Any non-empty subset of the [[Natural Numbers|set of natural numbers]] $\mathbb{N}$ has a unique [[Ordering the natural numbers|least]] element. > **Proof (Induction principle -> WO)**: Suppose $S$ is a non-empty subset of $\mathbb{N}.$ Suppose $S$ has no least element then STS that $S$ is empty which is the contrapositive. We proceed by [[Induction Principle|induction]]. Let $P(n)$ be the sentence $S \cap \{ k\in \mathbb{N} \mid k < n \}= \emptyset.$ In the base case $n=0.$ So $P(0)$ is $S\cap \emptyset =\emptyset$ is true. Suppose that $S\cap \{ 0,\dots,n-1 \}$ is empty and $S\cap \{ 1,\dots ,n \}$ is non-empty. Thus $n$ lies in $S,$ and is a least element. This contradicts our assumption that $S$ has no least element. We deduce that $P(n)$ holds for all $n.$ Thus $S$ is empty as desired. We now prove that the least elements are unique. Suppose that $s$ and $s'$ are both least elements of $S.$ Then $s\leq s'$ and $s'\leq s.$ We deduce by anti-symmetry that $s=s'$ **Proof (Completeness of $\mathbb{R}$ -> WO)**: Let $A \subset \mathbb{N}$. Then $A$ is bounded below by $0$ so has $\exists r: = \inf A$ by [[Real numbers|LUBA]]. BWOC suppose $r \not \in A$. Then for every $n \in A$, $r<n$. Since $r$ is the greatest lower bound, $\exists m \in A$ such that $m<r+1$. Following assumption that $m \neq r$ we have $r<m<r+1.$Since $m>r$, $m$ cannot be a lower bound for $A$, so there exists $k \in A$ such that $r<k<m<r+1$This is impossible, because $k,m \in \mathbb{N}$ and $0<m-k<1$. So in fact we must have $r \in A$. # Properties WO -> IP? then WO <-> IP? # Applications **Weak FTA**: We can use the WO to show that [[Every natural number greater than one is divisible by a prime number|every natural number greater than one is divisible by a prime number]] using the fact that least element in the set of its divisors greater than one will be a prime. **Bézout's lemma:** We can use WO to prove [[Bézout's lemma|Bézout's lemma]] which asserts than the gcd of two natural numbers can be written as a linear combination of them. **Euclidean division**: [[Division with remainder for integers|Division with remainder]] is the process  is the process of dividing one integer (the dividend) by another (the divisor), in a way that produces an integer quotient and a natural number remainder strictly smaller than the absolute value of the divisor. We can use WO to show that the quotient & remainder exist.