# Does one proof imply the existence of other proofs?

I asked my math professor if the existence of one proof for something implies the existence of other proofs we may or may not have found yet (she didn't know).

Another way to phrase it: are there things that can only be proved in certain ways such that if we hadn't discovered those types of proof (by this I mean e.g. no one had yet discovered the concept of proof by contradiction, not that we just hadn't figured out how to prove x by contradiction for some specific problem) we would be forced to conclude that they're false?

(Please feel free to add tags, I wasn't sure what to put).

• Fermat's Last Theorem had to wait quite a few years until all the powerful, intricate mathematics used in its proof arrived...yet nobody dared to say before that that "we have to conclude it is false"". That would be utterly absurd and anti-matematical, of course. What we used to say is "we suspect this is true/false, yet we don't know how to prove either way...so far". – DonAntonio Oct 27 '16 at 20:09
• Some things can even be both true or false (not at the say time though) independently of (ZFC) axioms (for instance the continuum hypothesis) – Astyx Oct 27 '16 at 20:14
• The Riemann hypothesis is assumed to be true in many publications, yet I doubt its authors are adamant about it. – Josué Oct 27 '16 at 20:17
• Unfortunately, when you formalise the notion of proof, you find that there are infinitely many trivially distinct proofs of any result. (For example, you can turn any given proof into a spurious proof by induction: just repeat the given proof in the base case and in the inductive step, ignoring the inductive hypothesis.) It is a long-standing (and probably insoluble) problem in mathematical logic to come up with a good definition of when two proofs are "the same". – Rob Arthan Oct 27 '16 at 21:37
• I second @RobArthan's comment. It's trivial to come up with infinitely many proofs, just by adding unnecessary steps along the way (say, while proving infinitude of primes we prove that $2+2=4$ and $2+2\neq 5$ along the way). Of course, the underlying idea of the proof stays there. There is no known way, though, to formalize the idea of "the underlying idea" being the same or different. – Wojowu Oct 28 '16 at 10:31

I think this is an example of the sort of the thing you're looking for:

Any sentence of number theory that can be proven using the axiom of choice and/or the continuum hypothesis can be proven from ZF alone, without using the axiom of choice or the continuum hypothesis.

In other words, if there is a proof of a sentence of number theory that uses AC and/or CH, then you can find some other proof of the sentence that doesn't use AC or CH.

A sentence of number theory here is a first-order statement about the structure $\langle \mathbb{N}; +, \cdot; \le\rangle.$ This is a statement about the natural numbers under the usual arithmetic operations and the usual ordering, where all quantifiers are over the natural numbers.

This is called a sentence of number theory because it's the kind of statement that is normally considered part of number theory (rather than, say, analysis). Here are some examples of sentences of number theory:

1. Fermat's last theorem: There do not exist positive integers $x, y, z,$ and $n$ such that $n\ge 3$ and $x^n+y^n=z^n.$

2. Goldbach's conjecture: Every even positive integer greater than $2$ can be written as the sum of two primes.

3. The Collatz conjecture: If you start with any positive integer and generate a sequence by repeatedly taking the current number $n$ and either dividing it by $2$ (if $n$ is even) or computing $3n+1$ (if $n$ is odd), you'll eventually reach $1.$ (To see that this is a first-order statement as described above, you need to set up the machinery of coding finite sequences as individual numbers, but that can be done in a straightforward fashion.)

4. P=NP.

5. Even the Riemann hypothesis: As customarily written, this is not a sentence of number theory (it's about infinite series of complex numbers), but it is equivalent to a sentence of number theory. You can see this either by either talking about rational approximations of all the numbers involved or by using one of the number-theoretic equivalents that are known (which are arguably the reason that the Riemann hypothesis is of interest anyway).

If any of the sentences above can be proven using the axiom of choice and the continuum hypothesis, then they can actually be proven without those special assumptions.

None of the above sentences except 1 are known to be true. However, their negations are also sentences of number of theory, so it's also true that if any of 2-5 can be disproven using AC and/or CH, then they can be disproven without those special assumptions.



By the way, here are some examples of statements that are not sentences of number theory:

1. There are uncountably many real numbers.

2. The countable union of a countable set of real numbers is countable.

There's no way to express these without quantifying over real numbers, or, equivalently, over sets of natural numbers. (At least for example 7, even that's not sufficient; to express that, you need to quantify over sets of real numbers.)



The removability of AC and CH from the proof of any number-theoretic statement follows from the fact that Gödel's constructible universe $L,$ in which AC and CH are true, has the same natural numbers as the entire mathematical universe $V$ (along with the same addition, multiplication, and ordering).

This type of result can be extended considerably, by the way. First, it applies to the generalized continuum hypothesis, since that's true in $L.$ More interestingly, the Shoenfield absoluteness theorem shows that it also applies to some (but not all!) sentences of analysis; the sentences it applies to are allowed to include quantification over real numbers and/or sets of natural numbers, but the number of quantifier alternations is restricted.

• It may be helpfu to clarify what is meant by "any sentence of number theory". I think I can formulate the property of countable additivity of the Lebesgue measure, with some effort, as a sentence about the integers. This property cannot be proved in ZF and in fact its negation is consistent with ZF. – Mikhail Katz Oct 28 '16 at 10:20
• @MikhailKatz Indeed, "number theory" here should be understood as the first-order arithmetic, which is a language in which we can quantify over integers/natural numbers, but not sets of these. The stated theorem is then true. – Wojowu Oct 28 '16 at 10:47
• @Wojowu, this should be clarified in the answer. There is little indication in the question asked that the OP is aware of the notion of first-order arithmetic. – Mikhail Katz Oct 28 '16 at 10:50
• @MikhailKatz Thanks for the comments. I've added some information on sentences of number theory to the answer. – Mitchell Spector Oct 28 '16 at 17:12
• @Wojowu Yes, exactly -- the phrase "sentences of number theory" refers to first-order sentences, with quantification only over natural numbers. I've added to the answer to clarify this. – Mitchell Spector Oct 28 '16 at 17:12

A beautiful illustration of this idea is the notion of duality in projective geometry. This is a duality between points and lines. This is a kind of metatheorem that you can use to deduce other results. For example, if you have a theorem proved from the projective axioms, then an automatic translation of the statement of the theorem replacing "points" by "lines" and "lines" by "points", as well as "collinear" by "concurrent", etc., produces a new theorem that is automatically true. An example is Desargues' theorem: since is converse is the same as its dual, one needs to prove only one direction from the axioms in order to have the full equivalence, based of course on a proof of the meta-result on duality.

It is also possible to interpret that OP's question as concerning the existence of alternative proofs of the same result, rather than other results. A beautiful illustration of such a phenomenon is Abraham Robinson's metatheorem that a result proved using infinitesimals in the hyperreal framework, also admits a traditional proof using only the traditional Weierstrassian framework based on the complete ordered field of real numbers. It is worth noting that this result is purely theoretical; the length of the expansion of the proof may be out of control so that the translation into a Weierstrassian proof may be unreadable to a human reader, or even to computer verification if the original proof were difficult.

• The question asks about "other proofs" of the same result, not proofs of new results. – Wojowu Oct 28 '16 at 10:44
• @Wojowu, what you propose is one interpretation of the question. It is formulated in a somewhat vague way that lends itself to multiple interpretations. – Mikhail Katz Oct 28 '16 at 10:52
• In my opinion, the second paragraph in the body doesn't leave much room for interpretations other than mine. – Wojowu Oct 28 '16 at 10:55
• OK, I added something consistent with your interest in fast-growing functions; hope you like it better. @Wojowu – Mikhail Katz Oct 28 '16 at 10:57

are there things that can only be proved in certain ways such that if we hadn't discovered those types of proof (by this I mean e.g. no one had yet discovered the concept of proof by contradiction, not that we just hadn't figured out how to prove x by contradiction for some specific problem) we would be forced to conclude that they're false?

Proof by contradiction uses the law of the excluded middle. If you drop the law of the excluded middle you get something called "intuitionistic logic," and the set of things you can prove is smaller. This doesn't mean that we're "forced to conclude that they're false," though; it means that we can't determine either way whether they're true or false.

More generally you can consider the field of reverse mathematics in logic, which takes a particular theorem and tries to determine precisely which axioms are necessary to prove it.