2
$\begingroup$

Not a particularly difficult question! However, just for the sake of completeness, I wanted to check if the following two proofs work.

To begin with, I prove every integer greater than $2$ has a prime divisor. Take any integer $x$ $\geq 2$. Since $x$ divides itself, the set $S$ of integers $\geq 2$ that divide $x$ is nonempty. By the well-ordering property, $S$ has a smallest element. Take the smallest element of $S$, which I'll call $y$. $y$ must be a prime. To establish this, suppose $y$ isn't a prime. Then there are integers $a,b$ such that $y\gt a,b \geq 2$ and $a,b$ both divide $y$. But if $a,b$ divide $y$, then $a,b$ must divide $x$ and therefore $a,b \in S$. This contradicts minimality of $y$. So $y$ must be a prime. This proves the property that every integer $\geq 2$ must have a prime divisor.

To prove that every integer can be written as a product of possibly non-unique primes and $1$, I think it should be sufficient to do strong induction on the composite numbers. Base case is $4$ and it follows obviously. Assuming the claim is true for each of the first $k^{th}$ composites, I note that the $k+1$$^{th}$ composite can be written as the product of two integers $a,b \geq2$. If $a,b$ are prime, then the proposition is true. If either or both of $a,b$ are composites, then they be must one of the first $k$ composites and the proposition must be true of $a,b$ by the inductive hypothesis. So the proposition is true of the $k+1$$^{th}$ composite and is therefore true for all integers greater than $2$.

$\endgroup$
8
  • 2
    $\begingroup$ You can use well-ordering principle again for the second part. If $n$ is the least natural number without a prime factorization, then … $\endgroup$ Commented Aug 29, 2021 at 21:50
  • 2
    $\begingroup$ I don’t see any reason to distinguish the cases of primes from compositors in the second part. A prime is a product of a single prime. If you define things correctly, $1$ is a product of an empty set of primes. $\endgroup$ Commented Aug 29, 2021 at 21:53
  • $\begingroup$ @ThomasAndrews For the second part, I had a proof based on well-ordering, too. But for whatever reason, the strong induction proof struck me immediately and quickly, and I just decided to stick with it. Agree re the second part, no need to distinguish between primes and compositions. But I do wonder if the proof works nonetheless. I am curious if I can do strong induction this way, i.e. on just the composite numbers, and in particular whether there are technical reasons to avoid going down this route. $\endgroup$ Commented Aug 29, 2021 at 21:58
  • 2
    $\begingroup$ Well-ordering and strong induction are essentially equivalent, and a well-ordering proof is a proof by contradiction, so probably strong induction is better. $\endgroup$ Commented Aug 29, 2021 at 22:01
  • 3
    $\begingroup$ Mostly aesthetic. But intuitionists hate proof by contradiction, because they don’t believe “not(not $P$)” implies $P.$ This is because proof by contradiction can be “non-constructive,” which is to say, it can be used to assert something exists without knowing any way to find it. $\endgroup$ Commented Aug 29, 2021 at 22:11

1 Answer 1

1
$\begingroup$

Either of these proofs are fine. I would propose rewriting the second proof more simply - it's true that you could use induction to prove a statement such as:

The $k^{th}$ composite number can be written as a product of primes.

However, this is a bit silly - since now you have to handle primes and composites separately, even though the same logic applies. It also has the issue that you're writing a proof without knowing which number in particular you're applying it to - you could get in trouble if you had to use more specifics about the number in question but could only say "it's the $1000^{th}$ composite number."

It's easier just to write the proof by strong induction on $n$ itself:

We will prove by strong induction that every $n\geq 2$ can be written as a product of primes. If $n$ is prime, the claim is trivial. Otherwise, we can write $n=ab$ for $2\leq a,b < n$ and use strong induction to rewrite $a$ and $b$ as products of primes - and multiplying these products together gives $n$ as a product of primes.


The comments raised some questions of using strong induction vs. using well-ordering; I think your proofs make appropriate use of both - essentially, your proofs provide algorithms of finding a prime factor or a prime factorization respectively. Your first proof says:

Test every number from $2$ up to $x$ to see which are divisors of $x$. Note that $x$ is assured to be a divisor of $x$, but there may be others. Let $y$ be the least such divisor.

This gives us an iterative algorithm for extracting prime divisors of numbers - and, in general, uses of the well-ordering theorem correspond to an algorithm like this*.

The second proof corresponds to a recursive algorithm:

Check whether $n$ is prime. If so, note that $n=n$ is a prime factorization. If not, write $n=ab$ and recursively apply this algorithm to both $a$ and $b$ and combine the resulting prime factorizations.

The fact that this algorithm finishes is provided by strong induction - since, to factor $n$, we are only going to try to apply the algorithm to smaller inputs, and we can only do that for so long.

These algorithms correspond to the intuition behind the two proofs - indicating that you made a good choice in which to use (and also indicating, as was brought up in comments, that your proofs are constructive - they provide an algorithm for producing the objects they claim exist). It's possible, though not advisable, to rewrite the second proof to start with:

Suppose that it's not true that all $n\geq 2$ have a prime factorization. Let $n$ be the least number without a prime factorization. ...

This would be considered inelegant because it uses proof by contradiction, but could be rephrased as a direct proof without changing the structure of the argument. Note that writing a proof this way also makes it nonconstructive - if I want to actually factor $289$, it doesn't help me to know why there can't be a number that doesn't have a prime factorization! Which is to say: it's a good thing you didn't write a proof that started this way. :)


(*This assumes you have an algorithm to test whether something is in the given set - but, for the set of divisors of $x$, that's clearly possible)

$\endgroup$
1
  • 1
    $\begingroup$ This is a great answer! The best thing about it is that it helps me with thinking about what makes for a good proof -- and, by extension, will help me structure future proofs as I continue to work through the text I'm currently going through. As somebody who's trying to learn math on my own and who hasn't taken a math course since grade 12 (10+ years ago and in circumstances which were not conducive to learning math), this kind of feedback re proof-writing is hard to come by. Thanks very much! $\endgroup$ Commented Aug 31, 2021 at 3:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .