4

In $ZF$ (or $ZFC$) let's take a sentence $S:= CH\vee \neg CH$, where $CH$ is the continuum hypothesis. Then $S$ has trivial proof, namely application of the law of the excluded middle ($LEM$). On the other hand the $CH$ sentence is independent of $ZF$.

For me that stands in conflict with what the $LEM$ has to say: either $CH$ is true, or $\neg CH$ is. Not only neither of these sentences can be proved to be true, but neither of them is true in our axiomatic system.

Generally I'm not here for discussion about intuitionistic vs non-intuitionistic logics and I don't think that is the meritum. I'm here to ask where is the fallacy in my reasoning and why no one thinks that $ZF$ with $LEM$ is inconsistent. Is the acceptance of the validity of the proof using $LEM$ to independent sentence only a purely philosophical issue? How come we are sure that any inconsistency cannot be produced this way?

Does my problem come from a fact that I think this way:

"$ ZF \vdash CH\vee \neg CH$ implies $ZF \vdash CH $ or $ ZF \vdash \neg CH $"

and this is a no no way of thinking? Do I mix theory with a metatheory? I'm not sure of that, but even if I do, then anyways $LEM$ has a clear semantic meaning to me: "Don't worry my son, I guarantee to you that either $CH$ or it's negation is true. Which is true you don't need to know now or care. Just work your proof for both cases and everything will be fine.". The same goes for independence - it has concrete semantic meaning to me - but then I cannot seem to reconcile it with my understanding of $LEM$. Please, restore my faith in mathematics

Are there known proponents of using, let's call it "weak intuitionism", i.e. classical $LEM$ is allowed only with sentences known to be not independent?

user121882
  • 389
  • 2
    Yes, the idea that $T\vdash \alpha\vee\beta$ implies $T\vdash\alpha$ or $T\vdash\beta$ is incorrect (it only works if $T$ is complete or if our underlying logic is nonclassical). From a semantic perspective it's useful to (via the completeness theorem) read "$T\vdash\alpha$" as "Every model of $T$ satisfies $\alpha$." Semantic LEM says "For every structure $\mathcal{M}$ and sentence $\alpha$, either $\mathcal{M}\models\alpha$ or $\mathcal{M}\models\neg\alpha$;" consequently we get the syntactic LEM "For every theory $T$ and sentence $\alpha$ we have $T\vdash\alpha\vee\neg\alpha$." (cont'd) – Noah Schweber Aug 21 '21 at 21:07
  • 12
    It may help to think about something simpler than $\mathsf{ZFC}$ - say, the theory $\mathsf{Grp}$ of groups. Letting $\theta$ be the sentence $\forall x,y(xy=yx)$ we have $\mathsf{Grp}\vdash\theta\vee\neg\theta$ by LEM but of course $\mathsf{Grp}\not\vdash\theta$ and $\mathsf{Grp}\not\vdash\neg\theta$ since some groups are abelian and others aren't. I think $\mathsf{ZFC}$ makes things seem more mysterious since intuitively we expect it to be "pretty much complete," at least early on. (BTW I'm leaving comments as opposed to an answer since I'm pretty sure this is a duplicate question.) – Noah Schweber Aug 21 '21 at 21:10
  • 2
    I think some of the mystery or doubt arises because one often thinks that $ZFC$ has one right model but unlike $PA$ or $Q$ which have the natural numbers as "intended" model. It is harder to grasp what a $ZFC$ model ought to be or which is the true one or if one exists. If there is a model of $ZFC$ by definition of it being a model every sentece $\varphi$ or it's negation must be true. – MIO Aug 21 '21 at 21:17
  • 2
    Correct, that is a “no-no way of thinking”. Every theory $T$ proves $p \lor \neg p$ for every sentence $p$ In their language, but only complete theories either prove $p$ or prove $\neg p$ for every such $p$. – BrianO Aug 21 '21 at 21:18
  • 2
    I am afraid your post is riddled with multiple negations (in the English) that make it almost impossible to understand. Your repugnance to a discussion of intuitionism makes it almost impossible to answer. I suggest you look into the disjunction property in intuitionistic logic. A sentence that is not independent of a set of axioms is either provable or disprovable from that set of axioms and so LEM doesn't need to be assumed for such a sentence - it is provable. – Rob Arthan Aug 21 '21 at 22:32
  • 1
    I think @Noah hits the nail on the head here. In general, when facing a confusing result about set theory or logic, it is often useful to substitute it by a simpler theory. This tends to highlight why the problem is not set theory or logic, but rather something deeper. You already hit that nail yourself. But the suggestion to think that every group is abelian or not is great. Even simpler, to the point of annoying triviality, take the empty theory and consider the statement $\forall x\forall y(x=y)$, that is "there is exactly/at most one element" (depending if you allow empty structures). – Asaf Karagila Aug 22 '21 at 00:03

1 Answers1

7

Expanding on my comment above:

It's often helpful to think of model theory as operating on two levels separately: the individual (= one structure at a time) and the collective (= a whole class of structures at once). Here I'm using the completeness theorem to disregard talk of proofs in favor of entirely semantic reasoning; this isn't always the right call, pedagogically speaking, but in this case I think it helps clarify what's going on.

At the individual level, LEM holds unproblematically: for every structure $\mathcal{M}$ and every sentence $\varphi$ in the appropriate language, either $\mathcal{M}\models\varphi$ or $\mathcal{M}\models\neg\varphi$. In particular, if $\mathcal{M}$ is a model of $\mathsf{ZFC}$ then either $\mathcal{M}\models\mathsf{CH}$ or $\mathcal{M}\models\neg\mathsf{CH}$.

However, this doesn't translate to the collective level as directly as we might want: if $\mathbb{K}$ is a class of structures and $\varphi$ is a sentence, some elements of $\mathbb{K}$ might satisfy $\varphi$ while others satisfy $\neg\varphi$, so it need not be the case that $\mathbb{K}\models\varphi$ or $\mathbb{K}\models\neg\varphi$. Here I write "$\mathbb{A}\models\eta$" to mean "$\mathcal{A}\models\eta$ for every $\mathcal{A}\in\mathbb{A}$," which does indeed match the usual notation re: theories once we conflate a theory $T$ with its class of models $Mod(T)=\{\mathcal{X}:\mathcal{X}\models T\}$. Of course LEM does show up at the collective level in a way, namely as $\mathbb{K}\models\varphi\vee\neg\varphi$ (for every $\mathbb{K},\varphi$), but this is not what we might naively expect.

Note that this really has nothing to do with logic at all; it's just an example of the fuzziness that can arise when we lose specificity. For example, every specific group is either abelian or non-abelian, but we can have a class of groups which is not entirely abelian nor entirely non-abelian (say, the class of all groups itself). Or, with even less model-theoretic flavor, every integer is either even or odd (= not even), but a set of integers might contain some elements which are even and some elements which are odd.

Noah Schweber
  • 245,398