We know that in proof by contradiction, to prove the truth of a proposition $p$, first, we assume that $\neg p$ is true and then show that this leads to a contradiction, that is, we conclude that a proposition is both true and false and therefore, our assumption (truth of $\neg p$) is false and thus $\neg(\neg p)$ is true. Now since $\neg(\neg p)\equiv p$, so we have proven the truth of $p$.
Now I have a question. By assuming $\neg p$, we prove that $p$ must be true, because the assumption of truth of $\neg p$, leads to a contradiction. Now my question is, how can we prove that the assumption of $p$ doesn't lead to any contradiction? Now you maybe say that since every proposition is either true or false, so the assumption of $p$ must not have any contradiction. But now consider the liar paradox:
This sentence is false.
If we use proof by contradiction and assume that it is false, then we conclude that it is true and this is a contradiction. So our first assumption is false and therefore, the above sentence must be true? Nope. The assumption of its truth leads to a contradiction again! In fact, my question is, how can we prove that other statements, is not similar to the liar paradox and have exactly one truth value?
Also consider this sentence:
This sentence is unprovable.
If we assume that it is false, then this implies that it is provable and this implies that it must be true which contradicts our first assumption, so our first assumption must be false and thus any sentence that says that itself is unprovable, must be true. Now my question appears here again. How can we prove that the above sentence is not like the liar paradox and has exactly one truth value and there is no contradiction in the assumption that it is true?
Best Answer
From the point of view of formalism, after we set up a (first order) formal language, a (mathematical) statement is neither true nor false, but simply a (meaningless) string of symbols. Even if we agree that some of the statements are axioms, we are not really saying they are true, but simply playing the game of printing new strings of symbols from them under certain rules, and there are statements that could be printed (provable), and others that could not (unprovable). There is neither truth nor falsehood within the formal system. Proof by contradiction is just one of the rules used to generate new statements from old ones.
For example, neither Euclidean geometry nor non-Euclidean ones are "true" or "false". It's just that if you accept the axioms of one kind, there are inevitable consequences you must accept as well. Whether the axioms (hence theorems) match physical reality is beyond the scope of mathematical investigation.
To speak about truth, we need a "model" of the theory, that is a set (with some functions and relations) that fits the axiomatic setup, i.e., each statement makes sense, and each axiom is true. It's more or less clear that for any given model, a statement is either true or false. For example, $\exists x,y,z\in\mathbb N$ such that $x^n+y^n=z^n, xyz\not=0$ is either true or false for the (standard) model $\mathbb N$. The difference between a formal system and a model, is like the difference between the English word "rose" and rose -- the flower.
There is a fundamental theorem (or meta-theorem) in mathematical logic that says proof (including proof by contradiction) is "sound". This means that if you start with true statements about a model, everything that can be proved is also true. To be more specific, the tautology theorem claims all tautologies hold, and "Reductio ad absurdum" is amongst them. So, the closest thing to a proof of "reductio ad absurdum" is the one of the tautology theorem.
Most of us would accept this, probably because we (including Godel) do believe the existence of a Platonic universe that reflects our axiomatic reasoning. (Still, questions like whether CH or its negation hold are very much for debate.). There are other values of more constructive proofs, but philosophically to completely reject reductio ad absurdum, I guess it tries not to assume our reasoning is about some kind of (unspecified or unreachable) Platonic "model" or reality, but about the status of our knowledge itself. I personally believe even if a murder case was never solved, the existence of a criminal is not in doubt.
Neither "this is false" nor "this is unprovable" is a well-formed formula in some formal language, and statements of natural languages are too ambiguous to have definite truth values, even more innocent ones might still suffer: such as whether a 50 years old is “old”. However, given a well-formed statement within a formal system, whether it can be proved or not from the given axioms has objective truth value. But this is like you're talking about whether a printer can print certain symbols, and the printer itself is incapable of "talking" about this. However, Godel's genius idea is roughly that, if such a proof exists, it can be encoded using natural numbers, and "this is unprovable" itself can be made a first-order statement about natural numbers, that is a sentence within the vocabulary of the printer if it can “speak” about natural numbers.