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


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)]]$$


$^{\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}}$}}$

  • $\begingroup$ I may have made a mistake in my language/symbology. If so, let me know. $\endgroup$ – 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\;$ ...

  • $\begingroup$ As written, this is almost correct. $H$ needs to be defined as the set of numbers without prime factorization except $0$ and $1$. $\endgroup$ – Asaf Karagila Jan 17 '14 at 7:38
  • $\begingroup$ Much better now! $\endgroup$ – Asaf Karagila Jan 17 '14 at 14:15
  • $\begingroup$ Done, @AsafKaragila. Thanks. One needs a logic/set theory guy once in a while to point the accurate stuff. $\endgroup$ – DonAntonio Jan 17 '14 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.