3
$\begingroup$

Note: This is not a duplicate of general "Proofs that there are infinitely many primes" because this one imposes what seems to be a novel condition: the fundamental theorem of arithmetic is not at the disposal of the proof.

I've only seen proofs of the infiniteness of primes which revolved around the fact that every positive integer is the product of a unique prime factorization.

For example, Euclid's proof using $p = p_1p_2\cdots p_n+1$ depends on the fact that $p$ is guaranteed by the fundamental theorem of arithmetic to have at least one prime factor because it, being a positive integer, has as a unique prime factorization. In this case, the uniqueness doesn't come into play. Euclid's proof depends on something weaker:

Positive integers are divisible by at least one prime number or they are $1$. (Weaker FTA)

There are a few weaker versions of the FTA, but in fact this statement is of equal power to the FTA without uniqueness of prime factorizations.

$n$ is divisible by $p_1$, therefore $n/p_1$ is an integer. You can repeat this until you are left with $\frac n{p_1p_2\cdots p_n} = 1$. This gives you a prime factorization of $n$.

Incorrect uniqueness argument removed. Unnecessary, anyways.

Forgive the lax proof, but note that the above statement has been shown to imply the FTA without uniqueness. However, the uniqueness is never really relevant so this should make it easier to identify when the FTA is being used by a proof.

Is it possible to proof that there are infinitely many primes without using the Weaker FTA?

$\endgroup$
  • 1
    $\begingroup$ That's not a valid proof of the uniqueness of prime factorizations. Euclid's proof does not use the full power of FTA, only the much weaker statement that you highlighted. $\endgroup$ – Bill Dubuque Jan 10 '17 at 4:00
  • $\begingroup$ What is missing from the proof of uniqueness? What doesn't it cover? $\endgroup$ – Axoren Jan 10 '17 at 4:07
  • 1
    $\begingroup$ The statement "since these factorizations..." makes no sense. What do you mean by that? Normally to prove uniqueness one uses the prime divisor property $\,p\mid ab\,\Rightarrow\,p\mid a\,$ or $\,p\mid b,\,$ or some closely related property such as Euclid's Lemma, or Euler's Four Number Theorem, or gcd properties, etc. This uniqueness proof is the meat of FTA. Existence is trivial (by strong induction). $\endgroup$ – Bill Dubuque Jan 10 '17 at 4:10
  • 1
    $\begingroup$ But the statement used in the proof is so easily proven that to talk about a proof without using that almost doesn't make sense. $\endgroup$ – Jacob Wakem Jan 10 '17 at 4:39
  • 1
    $\begingroup$ Uniqueness is equivalent to PDP. Existence is equivalent to WFTA (inductive extension). $\endgroup$ – Bill Dubuque Jan 10 '17 at 6:08
2
$\begingroup$

This should really be a comment as opposed to an answer - see the end for why - but it's far too long for that. Hopefully it is not too disappointing!

This is a great question - but, of course, it's difficult to make things precise here. (In particular: what would be a convincing argument that there is no such proof?) I want to say a bit about a weaker, but related and perfectly precise, question; besides being interesting in its own right (in my opinion), I think it gives a good example of how we can go about making questions like this rigorous, and some of the difficulties we run into in trying to do so.

Specifically, here's the version of the question I want to consider; I'll then try to justify why I'm asking the question in this way, below.

Is there a model of open induction satisfying "There are infinitely many primes" but not satisfying "Every number $>1$ has a prime divisor"?

Here, a "model of open induction" is equivalently (i) the positive elements of an integer part of a real closed field, or (ii) an ordered semiring satisfying induction for quantifier-free ("open") formulas. Basically, the natural numbers $(\mathbb{N}; +, \times, <)$ satisfy the extremely strong axiom system of (first-order) Peano arithmetic (PA); but when we're interested in what is necessary to prove what, we can "stratify" PA into smaller subtheories, and look at what these subtheories prove or don't prove - the latter being studied by looking for weird models. (Like, for instance, a positive answer to the highlighted question above.) This general process is part of Reverse Mathematics.

Now, why did I focus specifically on open induction? Well, PA breaks into two pieces: the ordered semiring axioms, $P^-$, and the induction axioms: for each formula $\varphi(x,\overline{y})$, we have the axiom $I_\varphi$ stating that induction holds for $\varphi$: $$\forall\overline{a}[(\varphi(0,\overline{a})\mbox{ and }\forall n(\varphi(n, \overline{a})\implies\varphi(n+1,\overline{a})))\implies\forall x\varphi(x,\overline{a})].$$ Taking the basic algebraic structure provided by $P^-$ for granted, the natural place to start pruning is the induction axioms. That is, we look at systems of the form $$I\Gamma=P^-\cup\{I_\varphi: \varphi\in\Gamma\},$$ for $\Gamma$ a natural class of formulas - usually a layer in the arithmetical hierarchy, in fact most often $\Sigma_1$.

. . . Except that $I\Sigma_1$ already proves both statements we're interested in! So it's too strong to tell the difference. So we need to go weaker.

A natural candidate is $I\Delta_0$ - induction is restricted to formulas with only bounded quantifiers. It is currently open whether $I\Delta_0$ proves the infinitude of primes; however, it does very easily prove that every number $>1$ has a prime factor! So it's still too strong to address the question.

Open induction is, to my knowledge, the next "natural" theory weaker than $I\Delta_0$. There are certainly things in between, but - to the best of my knowledge - they are fairly technical, whereas open induction both has a nice characterization in terms of what formulas it proves induction for, and a nice algebraic characterization of its models. In particular, even if we later decide that it's the wrong base theory for your specific question, the highlighted question above is still of general interest.

See this paper by Macintyre and Marker for some examples of weird things you can do with models of open induction.


Having just plugged Reverse Mathematics, let me cover my bases: how is this approach inadequate? Let me point out something that the reverse math-style approach will not detect. Let's say I have a proof of the infinitude of primes which uses all the pieces necessary to get a proof of "Every number $>1$ has a prime factor," but "rearranged" so that we never actually use that statement itself. From a reverse math point of view - paying attention only to the axiomatic overhead - this still counts as a proof using "Every number $>1$ has a prime factor"! Even though you might very reasonably accept it as a proof which does not.

My point is that - as in any case - there are limitations to how this formal approach can faithfully capture your intuitive question. That said, I hope you find this interesting.


So what's the answer?

This is the really awkward bit.

I recall having seen a construction of a model of open induction with infinitely many primes, but not satisfying weak FTA. However, looking through my notes, I can't find the argument, or a source, so I'm no longer sure. However, my memory is that such a structure can be constructed using the same kinds of techniques as in the Macintyre/Marker paper.

So that's why this shouldn't be an answer - it's addressing an ultraweak version of your question, and it's not even answering that version! But hopefully you found some of the preceding stuff interesting, and I hope that someone more knowledgeable in fragments of arithmetic can set me straight re: these models of open induction.

$\endgroup$
  • $\begingroup$ This definitely adds to the discussion and in effect makes more precise my question. What I see is that the only difference between your ultraweak version and mine is that you restrict yourself to models by open induction. What you've shown is that you believe models of open induction are the best place to look for this kind of answer, correct? $\endgroup$ – Axoren Jan 10 '17 at 4:57
  • $\begingroup$ @Axoren Yes, but there's another important weakness of what I've described - see the "how is this approach inadequate" bit. Personally I find the reverse math viewpoint very convincing, but that doesn't mean that other people do, or should! You may very reasonably care about not just what axioms are used, but the way they are put together; and this is not something that reverse math can "see". While in my opinion a positive answer to my highlighted question (i.e. "Yes, there is a...") would suggest that the answer to your question should also be "yes," I am less sure about the converse. $\endgroup$ – Noah Schweber Jan 10 '17 at 5:04
  • $\begingroup$ The problem involved with only caring about which axioms are used opens up the way for a proof which first proves the statement I don't want used as an axiom so that it can then be used. I don't want such a proof. From what I understand, the reverse math viewpoint can identify whether or not the weak FTA statement necessary for the requested proof, right? If that's the case, that's exactly what I'm looking for. $\endgroup$ – Axoren Jan 10 '17 at 5:16

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.