4
$\begingroup$

The law of the excluded middle (LEM) states that for any proposition, either it is true or its inverse is true. In other words, there is no "middle ground" between truth and falsehood in mathematical logic. This makes possible proofs by contradiction.

But it seems to me that there do exist propositions whose truth value is neither true nor false. A famous example is "This proposition is false." Such statements are usually said to be undefined because no value can be consistently assigned to them. In my experience it's often considered incorrect to treat "undefined" as a value in this context (i.e. "x does not exist" is preferred over "x = undef"), but regardless it is obvious that the above proposition is neither true nor false.

How can this be reconciled with the law of the excluded middle?

$\endgroup$
6
  • 4
    $\begingroup$ One way to get around it is that the liar expression is neither true nor false, but malformed and so "not a proposition". This is the "exception-barring" approach in the terminology of Imre Lakatos. $\endgroup$
    – Patrick Stevens
    Commented Apr 9, 2016 at 8:49
  • $\begingroup$ Not all sequences of words are propositions. You'd have no trouble accepting that "a the supercalifragilisticexpialidocious morning" isn't a proposition. Well, "This proposition is false" isn't a proposition either. That you think of it as being a proposition is a fault of your brain (and most people's - including me at first). It really carries no meaning. $\endgroup$
    – Git Gud
    Commented Apr 9, 2016 at 9:24
  • $\begingroup$ "Asdafb4562ijsadf;ja...(2134!)" is not a valid statement in English. However all the symbols are part of the English alphabet. How can you even accept the fact that English is a language useful for communication between two beings if you can use the English alphabet to write something which is meaningless? $\endgroup$
    – Asaf Karagila ♦
    Commented Apr 9, 2016 at 10:05
  • 1
    $\begingroup$ There was a time when I was convinced that since $1/0$ is neither positive nor negative, then it must be zero. Another example of improperly using the LEM $\endgroup$
    – Yuriy S
    Commented Apr 9, 2016 at 10:31
  • 1
    $\begingroup$ Re: 1/0 example. We define division on $R$ as follows: $\forall a,b,c\in R:[b\neq 0 \implies [a/b=c \iff a=cb]]$. Is $1/0=0$? We cannot use this definition to determine if it is true or not. We cannot apply the definition in this case because we have $0$ denominator ($b=0$). In general, we say that any expression with a $0$ denominator is undefined. Nothing mysterious about that. LEM still applies. Being "undefined" is not some kind of third value for logical expressions. It just means that our definition does not handle that case. $\endgroup$
    – Dan Christensen
    Commented Apr 13, 2016 at 15:20

1 Answer 1

Reset to default
5
$\begingroup$

The law of excluded middle is a law used for the types of propositions that we usually hold to be either true or false, e.g. arithmetic propositions such as "All even numbers are squares." We're well familiar with other types of propositions where it doesn't apply. For instance, it's not either true or false that I am in the living room, since I might be partly inside and partly not; it's not either true or false that there is a god because we'd first have to come to agree what it would mean for there to be a god, which will likely prove difficult; and it's not either true or false that Darth Vader is dead because it depends on future movies.

So there's nothing mysterious about the applicability of the law of excluded middle being restricted. What's confusing in the case that you mention is that at first sight the sentence "This proposition is false" seems like a proposition in the realm of logic, in which we assume the law of excluded middle to hold. But this is an illusion – it's actually a natural-language proposition that uses the fact that natural language has deictics like "this" to establish reference and self-reference. Numbers and logical propositions don't refer to themselves. So the problem isn't in believing in the law of excluded middle for numbers and logic but in misidentifying this natural-language proposition as a purely logical proposition.

Now the fundamental idea that Gödel used to prove his first incompleteness theorem is to make numbers and logical propositions refer to themselves after all, in a sense. By doing this, he showed that a sufficiently powerful formal system is either inconsistent or incomplete, i.e. it's either useless or there are propositions that it can neither prove nor disprove. Thus, there's no law of excluded middle for provability in formal systems – every sufficiently powerful formal system violates this "law". But that doesn't mean that these formally undecidable propositions are neither true nor false – you just need a meta-system that can reason about the first system in order to prove them, because trying to let the system reason about itself would lead to the same sort of self-referential inconsistencies as regarding "This proposition is false." as a logical proposition.

P.S.: As Asaf pointed out, Gödel's first incompleteness theorem applies only to formal systems that are recursively enumberable (i.e. whose axioms and inference rules an algorithm can enumerate).

$\endgroup$
5
  • 1
    $\begingroup$ I'd be keen to learn the reasons for the downvote. $\endgroup$
    – joriki
    Commented Apr 9, 2016 at 10:22
  • $\begingroup$ Maybe the inaccuracy regarding the incompleteness theorem? You're missing the requirement that the system is RE (I didn't downvote). $\endgroup$
    – Asaf Karagila ♦
    Commented Apr 9, 2016 at 10:36
  • $\begingroup$ @AsafKaragila: Thanks for that -- I added a note at the end. $\endgroup$
    – joriki
    Commented Apr 9, 2016 at 11:11
  • $\begingroup$ What do you mean by "the law of excluded middle doesn't hold for provability in formal systems"? Anyway, one interesting phenomenon is that, regardless of incompleteness, for any $\phi$, if $T$ is a theory and the background logic is classical, $T \vdash \phi \vee \neg \phi$. So one is in a situation in which the system thinks that one of them must be true, but can't prove which. Perhaps this is closer to what the OP was thinking? $\endgroup$
    – Nagase
    Commented Apr 9, 2016 at 16:47
  • 1
    $\begingroup$ @Nagase: I just meant what the incompleteness theorem says, that a proposition isn't either provable or refutable in a formal system -- I've rephrased it as "there's no law of excluded middle for provability in formal systems" so it doesn't sound like I'm saying that the actual law of excluded middle doesn't hold. $\endgroup$
    – joriki
    Commented Apr 9, 2016 at 19:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .