# Proof: $X$ exists, or there exists a proof that $X$ does not exist

"I went on the internet today", as it were, and happened upon a devious proof for the claim that either a thing $$X$$ exists, or there exists a proof that $$X$$ does not exist.

The proof, if I understood its author correctly, is as follows:

Define proof to mean a valid argument with all true premises. Let $$P_1$$ be the proposition that $$X$$ exists. Then

1. Either $$X$$ exists, or $$X$$ does not exist: $$P_1 \vee \neg P_1$$ is true by assumption. If $$X$$ exists, then our claim is satisfied and we may stop here; otherwise:

2. Let us assume that there does not exist a proof that $$X$$ does not exist.

3. Disjunctive syllogism, $$((P \vee Q) \wedge \neg P) \rightarrow Q$$, is a valid argument, with premises $$P \vee Q$$ and $$\neg P$$.

4. $$((P_1 \vee \neg P_1) \wedge \neg P_1) \rightarrow \neg P_1$$ is a disjunctive syllogism, thus a valid argument, with premises $$P_1 \vee \neg P_1$$ and $$\neg P_1$$.

5. If $$((P_1 \vee \neg P_1) \wedge \neg P_1) \rightarrow \neg P_1$$ has all true premises, it is a proof (since it is a valid argument). But this violates our assumption in step 2, so at least one of the premises $$P_1 \vee \neg P_1$$ and $$\neg P_1$$ must be false.

6. $$P_1 \vee \neg P_1$$ is true by assumption, so of the two premises only $$\neg P_1$$ can be false.

7. Therefore, $$\neg P_1$$ is false, thus $$P_1$$ is true: if there is no proof that $$X$$ does not exist, then $$X$$ has been shown to exist!

...now this feels extremely wrong, but I simply cannot tell why. I'm almost certain that there is an error at least in step 5, but I cannot see it. I can't even tell if the proof contains a logical error or if it has employed some form of verbal trickery. The proof seems correct, yet feels wrong.

What error(s), if any, have been made in the above proof? Is the original claim correct even if the proof itself fails?

• I am confused: Ignoring the formalisms, if we assume that $x$ does not exist, then "$x$ does not exist by assumption" is a proof that $x$ doesn't exist, no ? – Maximilian Janisch Jun 30 '20 at 18:32
• The claim in the title is clearly wrong. There are diophantine equations with no integer solutions such that , given any therory, no matter how strong , this theory cannot prove this fact. – Peter Jun 30 '20 at 18:39
• The "trick", as I understand it, is that we never do actually assume that $x$ does not exist. Since the claim is that "$x$" exists" -OR- "some proof that $x$ does exist exists", the claim is clearly satisfied if we do assume that $x$ exists. From point 2 onwards, the assumption we make is that "a proof that $x$ does not exist does not exist", while not making any explicit assumptions about $x$. – jaymmer - Reinstate Monica Jul 1 '20 at 1:36
• For some context, while I've phrased this in a way that $X$ could be anything, the proof was shared in several communities set up for discussion of theism, or lack thereof, in a well known content aggregator website, and a very specific $X$ (that you could probably guess) was assumed. Lots of discussion, and a few minor flamewars, some still ongoing, have erupted, yet nobody seems to have convincingly shown where the mistake in the purported proof is. Would it be appropriate to share links to those discussions here? – jaymmer - Reinstate Monica Jul 1 '20 at 1:43
• Can you link to where you found the original "proof"? – lemontree Jul 1 '20 at 16:49

This "proof" is conflating modalities.

The $$((P_1 \lor \lnot P_1) \land \lnot P_1) \to \lnot P_1$$ part can be simplified to just saying $$\lnot P_1 \to \lnot P_1$$ while retaining the same fallacy. You can also get rid of all the negations while retaining the same fallacy, e.g., let $$Q = \lnot P_1$$. And the subscript 1 is just pointlessly annoying.

Here is a cleaned up version of what the author is trying to put up:

1. To establish contradiction, assume some arbitrary $$Q$$ and that there is no proof of $$Q$$.
2. Well $$Q \implies Q$$, and since we assumed $$Q$$, this is a valid proof of $$Q$$.
3. But that is a contradiction with the assumption no proof exists.

Obviously the flaw is that $$X \implies Y$$ is only a valid proof of $$Y$$ if there is already a valid proof of $$X$$ established.

• Thanks, this is exactly the kind of explanation I was after! The subscript was my invention - I thought I might need to state several propositions, as I substantially shortened the author's original writeup (if you can believe that). I didn't end up needing those extra propositions, but didn't think to clean it up. It seems that the author was in fact informed that this kind of circularity is a problem, yet the argument continues anyway. – jaymmer - Reinstate Monica Jul 1 '20 at 16:48
• @jaymmer-ReinstateMonica I'm not entirely sure what proposition the person in the original post is trying to make, but you can tell at the outset it is a fallacy. In logic, you cannot prove something about a thing unless you first assume something at least as strong as what you are trying to prove. For example, the only reason we can prove the uniqueness of prime factorizations is because the axioms we use are even stronger than that. So people who try to prove a posteriori statements using a priori arguments are always wrong. – DanielV Jul 2 '20 at 18:43