In a proof by contradiction, what if both the proposition and its negation lead to contradictions?

Question

I'm learning math.

I've recently thought more about the proof by contradiction technique, and I have a question that I would like cleared up. Let me set the stage.

Suppose I am trying to prove a theorem.

Theorem: If A and $\neg$B, then $\neg$C.

Proof (contradiction): Let us suppose that A is true and $\neg$B is true. Let us assume that C is true ($\neg$C is false).

[blah blah blah]

From this, we arrive at a contradiction because we see that B is true ($\neg$B is false), but we know that $\neg$B is true (because we assumed it to be true). Thus, since assuming that C is true lead us to a contradiction, it must be the case that C is false ($\neg$C is true). QED.

My issue with this: why is it that C leading to a contradiction must mean that $\neg$C is true? What if $\neg$C also leads to a contradiction? In that case, doesn't a proof by contradiction not prove anything? Why can we be sure that C leading to a contradiction must mean that $\neg$C doesn't lead to a contradiction?

I'm sorry if this question has already been asked. I searched for a bit before asking to see if anyone had this same specific question, but most results just asked why a proof by contradiction works in general without any clear question.

Answer 1

If both $C$ and $\neg C$ lead to a contradiction, then you must be working with an inconsistent set of assumptions ... from which anything can be inferred ... including $\neg C$. As such, $\neg C$ can still be concluded given that assumption $C$ leads to a contradiction.

So, regardless of whether $\neg C$ also leads to a contradiction or whether it does not, we can conclude $\neg C$ once assumption $C$ leads to a contradiction.

The thing to remember is that when in logic we say that we can 'conclude' something, we mean that that something follows from the assumptions ... not that that something is in fact true. I think that's the source of your confusion. You seem to be saying: "OK, if $C$ leads to a contradiction, then we want to say that $\neg C$ is true ... But wait! What if $\neg C$ leads to a contradiction as well .. wouldn't that mean that $\neg C$ cannot be true either? So, how can we say $\neg C$ is true?!". But it's not that $\neg C$ is true .. it's just that it logically follows from the assumptions. That is: if the assumptions are all true, then $\neg C$ will be true as well. Well, are they? .. and is it? Funny thing is, as logicians, we don't really care :)

Answer 2

Similar to what Wofsey commented, a statement must be either true or false. You might wonder what happens if we have conflicting axioms. That is, what if we assume A and not A? It turns out that you can then prove any statement with these assumptions.

Answer 3

why is it that $C$ leading to a contradiction must mean that $\neg C$ is true?

Rather: why does $\def\false{\mathsf{contradiction}} A,\neg B, C\vdash \false$ let us infer that $A,\neg B\vdash \neg C$

Well, $A,\neg B,C\vdash \false$ means that $\false$ is true assuming that $\{A,\neg B, C\}$ all are true.   However, a $\false$ is, by definition, false, so that informs us that at least one from $\{A,\neg B, C\}$ must be false.   Thus when we assume that $\{A,\neg B\}$ are both true, we are implicating that $C$ is false.   That is $A,\neg B\vdash \neg C$

Notice: We are not unconditionally declaring that $\neg C$ is true; we are asserting that it is so under assumption that $A$ and $\neg B$ are true.

What if $\neg C$ also leads to a contradiction?

Why, if we can prove $A,\neg B,C\vdash \false$ and also that $A,\neg B,\neg C\vdash \false$ then we have shown that: at least one from $\{A,\neg B, C\}$ and at least one from $\{A,\neg B,\neg C\}$ are false; simultaneously even.   Since we usually accept that $C$ cannot have two different truth assignments at once (the law of noncontradiction: $\neg(\neg C\wedge C)$) we must conclude that at least one from $\{A,\neg B\}$ are false.   Therefore we infer from those two proofs that that: $A,\neg B\vdash\false$.$$\begin{split}A,\neg B,C &\vdash \false\\ A,\neg B,\neg C&\vdash\false\\\hline A,\neg B&\vdash \false\end{split}\text{ because } \begin{split}A,\neg B &\vdash \neg C\\ A,\neg B&\vdash\neg\neg C\\\hline A,\neg B&\vdash \false\end{split}$$

Answer 4

Good question! There are some mathematicians who do not agree that the Law of the Excluded Middle is valid, and therefore accept only direct proofs as sound, not proofs by contradiction. They would say your intuition is on to something important. If you’re using rules of logic that don’t explode when they encounter $p∧¬p$, that is, a logic that does not state that an inconsistency proves that all statements are vacuously true, you’re using a paraconsistent logic. If you can prove a contradiction, and still think the theory is of interest, you’re doing inconsistent mathematics.

In mainstream mathematics and philosophy, however, such a result would prove that the formal system you were using is inconsistent. In a traditional logic, such as the axioms of logic defined by David Hilbert, it means that all (well-formed) statements become vacuously true as theorems within that system. The proof system generated by the single premise “False” and containing all other statements as theorems with the same one-line proof is too trivial to be interesting, and you’d have shown the inconsistent system to be equivalent to the trivial one under traditional logic, so an inconsistent theory would be abandoned. But, since there had been some reason people were using the theory before, they would then ask, “Can we rescue the parts of this theory we care about? Change the axioms to make them consistent, and still have a interesting theory, maybe even a useful one?”

The best-known example is probably when Frege attempted to prove that all of mathematics could be founded in set theory. In his theory, it was permissible to define the set of all sets with some property. Bertrand Russell proved that this led to Russell’s Paradox: does the set of all sets that do not contain themselves, contain itself? Thus, the theory was proven inconsistent.

Frege withdrew his book, but people kept working on the problem. The long-term result was the development of Zermelo-Frankel set theory, which most mathematicians use as the underlying basis for their work today. It has different axioms that allow you to prove the existence of sets corresponding to the natural numbers, the real numbers, matrices, sequences, and all the other structures we need to do mathematics as we presently understand it. However, (and this is not a rigorous explanation) they are intentionally limited so that you cannot prove the existence of a set that contains itself, or anything like one.

Also keep in mind that, by Gödel’s Second Incompleteness Theorem, it is impossible for a formal system both complex enough to contain arithmetic, and also consistent, to prove its own consistency. At least not in a finite number of steps.

Answer 5

While you already have excellent answers, let me remind you that "$x$ implies $y$" just means "$\neg x$ or $y$". So the theorem states $\neg(A\text{ and }\neg B)\text{ or }\neg C$, which is equivalent to $\neg(\text{$A$ and $\neg B$ and $C$})$. And what you have done is exactly deriving a contradiction from $A$ and $\neg B$ and $C$, so this proves the theorem.

Of course, it is still possible that $\neg(\text{$A$ and $\neg B$ and $\neg C$})$ is also true, which would show $\neg(\text{$A$ and $\neg B$})$.

Answer 6

To make sense of the question, I interpret it as inquiring concerning a situation where both an assumption and its negation lead to a proof of the proposition (which may be a proof by contradiction).

A few years ago there were reports that precisely such a situation occurred: a certain number-theoretic result was proved and the assumption of the Riemann hypothesis (RH), and a separate proof was provided in the assumption of the negation of RH. This is evidence in favor of the claim that in practical situations, classical logic is advantageous to intuitionistic logic.

Answer 7

If assuming that C is true leads to a contradiction, and assuming that C is false also leads to a contradiction, then the universe collapses in on itself and time comes to an end.

Seriously, either you have made an error in your proofs, or your axioms are mutually contradictory.

Do you actually have an example of this? It should be impossible. And asking, "What would happen if this impossible hypothetical situation actually happened?" is generally non-productive. It's like asking, "What if someone could prove that 2+2=5?" Well, in that case I guess a lot of mathematics would turn out to be a giant mistake.

Answer 8

In logic, by and large we don't make absolute statements, only deductionary ones (if that's a word). Meaning, when we say 'Q is true', we aren't saying Q actually is true in the real world (although it might be)

Instead our statements actually have meanings like this:

• Assuming P is true (for some P) and the laws of logical argument we use are valid, then Q would be true.
• Assuming P is false (for some P) and the laws of logical argument we use are valid, then Q must be false.
• Assuming P is false (for some P) and the laws of logical argument we use are valid, then Q cannot be proven true or false within those laws of logical argument.

We routinely shortcut these to "If P is true then Q is true" etc, but you can see we miss out at least a few major assumptions when we describe the statements that way.

So coming back to the OP, when we use argument by contradiction, we are saying:

• If P were true, and the laws of logical/mathematical argument we use are valid, then Q must be true.
• But Q isn't true, and we believe the laws we use are valid.
• If so, P must have been untrue as well, otherwise our first statement would be contradicted and either the laws we use aren't valid (or aren't validly applied, we've missed some subtle issue that means our definitions or argument are invalid) or Q isn't in fact true.

So really, the validity of a proof by contradiction follows from:

• our definition of logical argument,
• our beliefs (which can't actually be proved!) that our understanding of logic is sound and that logic and maths are consistent even if not provably so.
• our belief (which we will recheck if necessary!) that we haven't made blatant or subtle errors in our logic or our definitions.
• lack of any concrete instance despite centuries of searching, that disproves these - at least, as it is relevant to anything we are aware of (so far as I know!)