Confused about proofs by contradiction, the Law of the Excluded Middle and existence of consistent axiomatic systems.

Question

I apologize if my question is too dumb. I'm not particularly educated in this area of Mathematics.

Proof by contradiction consists of assuming a statement $P$ is false, and then reach a contradiction thus allowing us to conclude that $P$ must be true. Such line of reasoning seems to be using the Law of the Excluded Middle, that is, $P \lor \neg P$ is a tautology.

Wouldn't assuming said law lead to some problems. As an example, it has been proven that if ZFC is consistent, then both ZFC$+$CH and ZFC$+\neg$CH are also consistent. Thus, by LEM, there are only two possible options:

1) CH is true, but unprovable within ZFC.

2) $\neg$CH is true, but unprovable within ZFC.

Suppose for a second that the first option was correct. Since $\neg$ CH is consistent with ZFC, the axiomatic system ZFC$+ \neg$CH contains no contradictions. However CH being true does imply that ZFC$+ \neg$CH has a contradiction. The second option being true leads to the same result.

What am I missing?

---

I would truly appreciate any help/thoughts.

Answer 1

Usually when it is said that a "sentence $s$ is true of some theory $T$" it is meant that $s$ is satisfied in some particular model of $T$ that is considered as a standard model of $T$, that is a model that most captures the informal concept the formal system is about.

To say that $s$ is true in $T$ does imply that $T + s$ is consistent! But it doesn't necessarily imply that $T + \neg s $ is inconsistent at all. To say that $T + \neg s$ is inconsistent is to say that $s$ is not satisfied in any model of $T$ and not just the standard one. The picture should be clear by now, since $s$ being satisfied in a particular model of $T$ doesn't at all imply that $\neg s$ cannot be satisfied in another model of $T$.

Answer 2

Your confusion is in conflating the truth of a set of axioms with their consistency. I'll assume ZFC is consistent throughout this explanation (that's not known, but it's assumed in the undecidability result you stated).

Let $\diamond p$ denote "$p$ is consistent" and $\square p$ denote "$p$ is provable" viz. modal logic (I'm tweaking its concepts slightly for the present context). Also, let $c,\,z$ respectively denote the CH and ZFC. From the law of the excluded middle $c\lor\neg c$ we deduce $z\to((z\land c)\lor(z\land\neg c))$, and the undecidability of $c$ in $z$ means that $(\diamond(z\land c))\land(\diamond(z\land\neg c))$. But these results are not inconsistent. In particular, $z\land c$ does not imply $\square(z\land c)$, and hence does not contradict $\diamond(z\land\neg c)$.

In particular, a general instance of the law of the excluded middle, $p\lor\neg p$, doesn't imply $(\square p)\lor(\square(\neg p))$. Similarly, the law of non-contradiction $\neg(p\land\neg p)$ doesn't imply $\neg((\diamond p)\land(\diamond(\neg p)))$.

Just to relate all this to something you said earlier:

Proof by contradiction consists of assuming a statement $P$ is false, and then reach a contradiction thus allowing us to conclude that $P$ must be true.

An intuitionistic logician, who rejects the law of the excluded middle, would instead say you assume some statement is true, reach a contradiction, and thus conclude the statement was false. In other words, $(q\to\bot)\to\neg q$. The case $q:=\neg p$ gives $(\neg p\to\bot)\to\neg\neg p$, which if $p=\neg\neg p$ simplifies to $(\neg p\to\bot)\to p$ as you intended. This simplification follows from the law of the excluded middle, but fails in intuitionistic logic. One way to understand this is that intuitionistic logic tracks provability rather than truth (this isn't necessarily how to read it, but it gives the right logical structure). In other words, $p\lor\neg p$ fails in intuitionistic logic because $(\square p)\lor(\square(\neg p))$ fails in classical logic.

Answer 3

Let me make it very clear: Truth is always relative to a structure/model. Remember, every first-order sentence over a language $L$ can be true in some $L$-structure but false in another. For a trivial example "$∀x,y\ ( x·y = y·x )$" is true in every abelian group but false in every non-abelian group. Likewise "CH is true" is meaningless unless we specify explicitly or implicitly the structure we are talking about. Once you precisely specify this, all the problems will go away. Historically, some philosophers have made this same mistake of confusing syntax with semantics.

In fact, the independence of CH directly implies via Godel's completeness theorem that there is a model of ZFC in which CH is true, as well as a model of ZFC in which CH is false. There is simply no contradiction because those are two different models!

Some people may use "true in ZFC" to mean "provable by ZFC", but that would then mean "true in all models of ZFC", which certainly does not hold for CH. Also, if you come across statements that Godel's incompleteness theorems are about "true but unprovable sentences", note that there is still a model we are talking about, namely the standard model $\mathbb{N}$ of PA. For more on that see this post.