# Least Element $\implies n\geq 2$ Has Prime Factorization: An Analysis of Strong Induction

$$\color{blue}{\text{PROBLEM}}$$

Show every natural number $n\geq 2$ has a prime factorization.

$$\text{TYPICAL SOLUTION}$$

Base case: $2$ is prime, so it is its own prime factorization.

Inductive step: Suppose for all $k\geq 2$ and $k<n$, then $k$ has a prime factorization. Either $n$ is prime or not prime.

$\hspace{3cm}$ If prime:

$\hspace{4cm}$$n is its own prime factorization. \hspace{3cm} If not: \hspace{4cm}$$n=ab$ where $a,b>1$ and $a,b<n$,

so by the hypothesis of $\color{red}{\text{strong induction}}$$^{\dagger} a,b both have a prime factorization, so their product is a prime factorization of n.$$\text{MY QUESTION}$$How can I prove this using the fact that every non-empty subset of \mathbb{N}_0 has a least element? Here, \mathbb{N}_0 is the set \mathbb{N}\cup 0. More specifically though, how can we use my definition for this (see below) to prove the \color{blue}{\text{PROBLEM}}?$$(\forall {\scr{S}}\subseteq \mathbb{N}_0)[({\scr{S}}\neq \emptyset)\implies (\exists s\in{\scr{S}})[(\forall n\in{\scr{S}})(s \leq n)]]\text{NOTES}$$^{\dagger}$$\color{red}{Strong\text{ }induction}$:

$$\forall {\scr{P}}(n)[(\forall n\in \mathbb{N}_0)[(\forall k \in \mathbb{N}_{<n})(k\in {\scr{P}}(n))]\implies (n\in {\scr{P}}(n)) \implies (\forall n\in\mathbb{N}_0)(n\in {\scr{P}}(n))]$$

$\tiny{{\scr{P}}(n):=\text{"$n$is in the set${\scr{P}}$}}$

• I may have made a mistake in my language/symbology. If so, let me know. – user121977 Jan 17 '14 at 6:29

Suppose the claim is false and let $\;\emptyset\neq H\subset\Bbb N\setminus\{0,1\}\;$ be the set of all elements which have no prime factorization.
Let $\;h\in H\;$ be the first element in $\;H\;$ ; this element cannot be prime as then it'd be its own prime factorization, contradicting the fact that $\;h\in H\;$ . Thus, there exist $\;2\le a,b<h\;$ s.t. $\;ab=h\;$.
But $\;a,b<h\implies a,b\notin H\implies a,b\;$ have a prime factorization, and thus does $\;h\;$ ...
• As written, this is almost correct. $H$ needs to be defined as the set of numbers without prime factorization except $0$ and $1$. – Asaf Karagila Jan 17 '14 at 7:38