Mdtryhht

Although the proof by contradiction is correct, your feeling of unease is fine, because the direct proof by induction is so much clearer:

Take an integer $N$. If $N$ is prime, there is nothing to prove. Otherwise, we must have $N = mn$, where $1 < m, n < N$. By induction, since $m, n$ are smaller than $N$, they must each be a product of primes. Then so is $N = mn$. Done.

The proof is not circular, the key is in the second sentence: Let N be the smallest positive integer with this property.

We are allowed to say a least $N$ exists because of the well-ordering principle.

I feel like this proof kind of presupposes the lemma.

Because it does.

It says so right in the first two sentences, which can be rephrased as:

Let $N$ be the smallest positive integer that cannot be written as a product of primes.

So yes, the proof assumes that all positive integers smaller than $N$ can be written as a product of primes.

This is OK, though, because it is trivially true for the smallest integers: 1, 2. The proof builds on that to infer that no such an $N$ exists where the lemma is not true.

I can definitely understand how this can feel a little off.

1) The lemma (as stated in the question) says all nonzero integers. Primes are integers and, by definition, cannot be products of primes. So, I think the lemma probably is actually more along the lines of: "all positive non-prime integers can be written as a product of primes".

2) Also, the statement "since 𝑚,𝑛 are positive and smaller than 𝑁 they must each be a product of primes" doesn't really explain why they must be a product of primes. Since, 𝑁 is the smallest positive non-prime integer that cannot be written as a product of primes (by supposition of the lemma), then 𝑚,𝑛 are either prime themselves or a product of primes (as they are less than 𝑁 and 𝑁 is the smallest number that isn't a product of primes). Either way, they will provide the primes necessary to create 𝑁, making 𝑁 able to be constructed as a product of primes.

Hopefully this helps to see why the proof by contradiction works.

A proof by induction has base case(s), Let m and n be said base cases. if it's true for m and true for n (not necessarily distinct), then because it's a product, it follows for mn. All the proof supposes, is N=mn for some base case ( primes or prime powers to start, in these cases) with m and n proved. Then it follows for N, which by saying N which
originally was consider the least element of a set of counterexamples, has one, it eliminates all possible least elements for the set we originally supposed existed.

An integer $n$ is said to be a composite if it can be expressed as the product of two integers $a$ and $b$ with $a notin -1,0,1$ and $b notin -1,0,1$.

An integers $p notin -1,0,1$ that is not a composite is called a prime number.

Recall the method of infinite descent used in mathematical proofs.

Suppose $m notin -1,0,1$ and it can't be expressed as a product of primes. If $m lt 0$ then it is certainly true that the positive number $-m$ can't be factored into primes. So the existence of $m$ allows us to assert that there are positive integers greater than $1$ that can't be factored into a product of prime numbers.

So using infinite descent, we have a minimal $n > 1$ that can't be written as a product of primes. In particular, $n$ can't be a prime. But then it must be a composite, and we can write

$quad n = st text with s,t gt 1$

Note: The composite factors $s$ and $t$ must both be positive or negative.

If they are both negative, replace $s$ with $-s$ and $t$ with $-t$.

But then $s lt n$ and so it can be written as a product of primes. Similarly, $t$ can be written as a product of primes. But then $n$ itself is a product of primes. But this is not possible by our choice of $n$. So the initial assumption of the existence of $m notin -1,0,1$ with no prime factorization leads to a contradiction.

So every $n notin -1,0,1$ has a prime factorization.

There is a property of the natural numbers called well-order. A set is well-ordered if every non-empty subset has a least element. So given any property $P$:

1. The set of numbers for which $P(n)$ is false is either empty or has a least element.




2. Suppose there is some number $n_0$ such that $P(n_0)$ is false. If $n_0$ is the least such number, then obviously $P(n_0-1)$ is true ^[1] (otherwise $n_0-1$ would be a number for which $P$ is false that is smaller than $n_0$, and so $n_0$ wouldn't be the smallest such number).




3. Thus, if we can prove that there is no number $n_0$ such that $P(n_0-1)$ is true and $P(n_0)$ is false (i.e. "$neg exists n_0: (P(n_0-1) land neg P(n_0))$", then we have shown that the set of numbers for which $P$ is false has no least element.




4. "$neg exists n_0: (P(n_0-1) land neg P(n_0))$" is equivalent to "$forall n_0: (neg P(n_0-1) lor P(n_0))$", which is in turn equivalent to "$forall n_0: (P(n_0-1) rightarrow P(n_0))$".




5. Thus, if we can prove $forall n_0: (P(n_0-1) rightarrow P(n_0))$, then it follows that the set of numbers for which $P(n)$ is false does not have a least element. Since all non-empty sets of natural numbers have a least element, this set must be empty. That is, there are no numbers for which $P(n)$ is false, i.e. $P(n)$ is true for all $n$.

[1] There is also the possibility that $n_0-1$ isn't a natural number, which happens when $n_0=0$. Dealing with this possibility requires proving that $P(0)$ is true separately, which is why induction proofs require a base case.

So that's the concept behind induction proofs: if the proposition isn't true for all numbers, then there is a non-empty set of numbers for which it is false, which has to have a least element, which means that we have to go from "true" to "false" at some point. Inductive proofs thus look a bit like circular reasoning: you start assuming that the proposition is true, and use that to prove that the proposition is true. But what makes it non-fallacious is that you prove that the proposition is true for a later number by assuming that it's true for an earlier number.

The proof that you cite is using the same basic principle as induction, namely the well-order of the natural numbers, but it is skipping the one-by-one sort of process that induction proofs usually use. Instead of saying "If $P(n_0)$ is false, then $P(n_0-1)$ being true leads to a contradiction", it's saying "If $P(n_0)$ is false, then $P(n)$ being true for $n<n_0$ leads to a contradiction". Like a standard induction proof, it superficially looks like circular reasoning, but isn't, because it's proving that the proposition is true for $N$ using the fact that it's true for smaller numbers.