Using a proof by contradiction with unprovable statement

Question

In a standard proof by contradiction of the statement p => q “p implies q”, we can suppose the statement is false. If we then derive an absurdity then the statement is shown to not be false, hence it must be true.

But it seems when we begin our proof by contradiction we begin with the claim:

the statement is either true or false. Suppose it is false...

Hence when we show the statement cannot be false, the only other possible option/case is true. But it seems there is another option in that the statement could be unprovable, so the original claim in yellow above should read:

the statement is either true or false or unprovable.

I am hoping someone could show me why a proof by contradiction still works and where I have gone wrong.

Also: I believe I remember my professor saying that if a statement is unprovable then it can be shown to both be true AND false. Is this correct?

Note: I am not acquainted with formal logic notation

Answer 1

In standard logic we accept all tautologies, which include the law of the excluded middle. For any statement $\phi$ we have $\phi \vee \lnot \phi$. If you start with $\phi$ and derive a contradiction, you can conclude $\lnot \phi$

Depending on your axioms, there may be many statements $\phi$ where we cannot derive either $\phi$ or $\lnot \phi$. This means the axioms are incomplete. In the metatheory this tells us that our axioms are consistent, as from inconsistent axioms you can derive anything. In this case you can assume $\phi$ and still cannot prove a contradiction. You can also assume $\lnot \phi$ and cannot prove a contradiction. You can then add either $\phi$ or $\lnot \phi$ to your axioms and still have a consistent set.

No, if you cannot prove $\phi$ or $\lnot \phi$ that does not mean that $\phi$ is both true and false. It means there are models of the axioms where $\phi$ is true and also models where $\phi$ is false.

Answer 2

the statement is either true or false or unprovable.

'unprovable' is not mutually exclusive from 'true' or 'false'. I can tell you that the shirt I am wearing right now is either red or blue, but I am not telling you which it is. Then you could say:

your shirt is either red or blue or of unknown color ... and I pick 'unknown'!

but obviously, just because you don't know what color my shirt is does not mean that it can no longer be either red or blue

Same for the truth of statements. Just because the truth-value of some statement is unprovable and unknown does not mean that it is suddenly no longer true or false.

Also: I believe I remember my professor saying that if a statement is unprovable then it can be shown to both be true AND false. Is this correct?

Absolutely not. See my shirt

Answer 3

Proofs don't exist in vacuum of course. Proofs start from somewhere. A theory.

Truth also does not exist in vacuum. Truth is relative to a structure, usually one that satisfies a certain theory.

If you underlying logic, in this case I suppose first-order logic, is sound, then every provable statement is true in all the models of the theory. And if the logic is complete, then a statement true in all the models of a theory is also provable.

In some cases we say that something is true to mean that there is a concrete structure in which we measure that truth value. For example, in the case of arithmetic this would be $\Bbb N$, but this is far from the unique model of Peano's axioms. In other cases when we say true we really just mean provable (e.g. $\forall x,y:\ x\cdot y=y\cdot x$ is not true in the case of groups because there are groups where it is false; whereas $\forall x\exists y:x\cdot y=y\cdot x$ is true since we can take $y$ to be the identity, but it's not "true", instead it is provable from the axioms of a group).

And therein lies the rub. You are conflating truth and provability since you haven't set the context in sufficient details to distinguish them.

In the case of a proof by contradiction relying on an unprovable statement, you will either fail to complete the contradiction, or you end up proving that if the unprovable statement is true in your model, then the consequent is also true in that model.

Mind you, you still prove (by contradiction) the implication is true, but nobody promised you that the antecedent is true.