9
$\begingroup$

Why does a logic system not use the law of the excluded middle?

I studied non-classical logic (intuitionistic and modal) where double negation can't be removed and the law of excluded middle can't be used. But what is a simple example that non-mathematicians can directly understand where we can't use the law of the excluded middle?

A non-mathematician can agree that the statement "The door is not unlocked" does not necessarily imply that the door is locked (the door might not have a lock or the door doesn't even exist and therefore it is false that the door can be locked or some other interpretation). But I don't think that's a good example.

Excluded middle suits well for numbers but rarely for other entities e.g. category placement "Is the cat white?" - The alternatives might be not disjunct, there might be no cat at all, it might be undecidable or other alternative.

I've seen that scientific questions should preferably be "yes-or-no questions" but what's a good example when that will fail and we can't remove a double negation?

For instance, a real example of "A is B and A is not B", which would be impossible in classical logic but could be true about something like Schrödinger's cat that is alive and dead at the same time?

$\endgroup$
  • 2
    $\begingroup$ "will there be a seabattle tomorrow?" (very ancient example, think it goes back to Aristotle, he overlooked the option that he could start one himself) $\endgroup$ – Willemien Apr 4 '14 at 20:17
  • 1
    $\begingroup$ I really can't understand your question. First and foremost you need to specify your logical axioms. Only then can the question make sense. $\endgroup$ – Git Gud Apr 4 '14 at 20:20
  • 1
    $\begingroup$ "The door is not unlocked" does not necessarily imply that the door is locked (the door might not have a lock or the door doesn't even exist and therefore it is false that the door can be locked or some other interpretation). This is wrong. If the door doesn't exist or it doesn't have a lock, then the finite sequence of characters "The door is not unlocked"is meaningless, it doesn't have a truth value. $\endgroup$ – Git Gud Apr 4 '14 at 20:22
  • 3
    $\begingroup$ Jan Łukasiewicz argued that the law of excluded middle belongs to two-valued logics and such systems are not expressive enough to model more complex dependencies. One of his examples was that expressions that involve time might be indeterminate, because some events didn't happen yet, and so we can't determine if these are true or false. It was one of the reasons behind the three-valued logic. $\endgroup$ – dtldarek Apr 4 '14 at 20:56
  • 1
    $\begingroup$ @909Niklas If you are interested in modeling some systems, then notice that there might be some transition state between locked and unlocked. In fact, the system might be observationally consistent, but not consistent inside. This frequently happens in databases with complex dependencies, where some modification implies many others that cannot be done simultaneously, however, the user does not see the middle transitions, only the final, proper state. $\endgroup$ – dtldarek Apr 4 '14 at 21:12
9
$\begingroup$

The law of excluded middle says that for all φ, either φ is true or ¬φ is true. Recast in intuitionistic terms, this means that for all φ either we have a proof of φ or a proof of (φ → ⊥). While the law of excluded middle makes sense for the semantics of classical logic which uses the notion of truth, it doesn't seem to be justified from the perspective of the proof semantics of intuitionistic logic.

As an example, you can take any unsolved problem P in your domain of choice, say Goldbach's Conjecture. No doubt, P ∨ ¬P is true; either every integer greater than 2 has the property or doesn't. But the intuitionist cannot claim P ∨ ¬P, because she has neither an algorithm that can map such an integer to a pair of twin primes, nor a proof that no such algorithm can be found.

$\endgroup$
4
$\begingroup$

An alternative to considering the law of the excluded middle as an axiom is to consider it as a definition. You can consider the definition of a Boolean value to be that it is either true or false, then the mechanic of the logic becomes to simply to determine whether we can prove that a value is a Boolean, at which point you can deduce the excluded middle.

But you asked for an example. Here is one I came across once.

There is a duality between sets and functions. For example, one person may write $S \cup T$ and another may write $s(x) \lor t(x)$. It is a worthwhile exercise to convert expressions between their set form and their function form. So let's do that with Russell's self contradictory set:

Set form:

$$P \equiv \{x \mid x \not \in x\}$$

Converted to boolean logic and functions becomes:

$$p \equiv (\lambda q)\, \lnot q(q)$$

Russell's paradox comes from considering $P \in P$. The function form equivalent is to consider $p(p)$:

$$p(p) = \bigg((\lambda q)\, \lnot q(q)\bigg)(p) = \lnot p(p)$$

Is $p(p) = \lnot p(p)$ paradoxical? No, because we haven't defined that $(\forall x )p(x)$ must be a boolean. We haven't assumed the excluded middle. On the other hand, some logics do assume $(\forall x,y)\,x\in y$ is a boolean, which does assume the excluded middle (and make a heroic attempt to limit set comprehension), which does result in the definition of $P$ being paradoxical.

There are trade offs in the design of a logic. If you only use first order logic, you can assume the excluded middle all day long. If you want to use higher order logic and partial logics (logics where the domain of functions isn't the universe), then you give up the excluded middle.


Another way of looking at this question (there seem to be many) is in terms of decidability.

Godel established that in every sufficiently description axiom/inference set, either there is a grammatically valid statement that is undecidable or that your logic is self-contradictory.

Now what happens if we assume every undecidable statement $D$ is either true or false? Let $A$ be the set of all possible assignments of true or false to $D$:

$$\forall d \in D ~~\bigg(d \lor \lnot d\bigg)$$ $$\exists c \in A ~~\forall d \in D ~~ \bigg(d = c_d\bigg)$$

Still being fairly informal, the law of the excluded middle implies that there is at least one assignment to the undecidable statements. But Godel established that at least one undecidable statement must exist which is neither true nor false for the axiom set to be consistent. I'm fairly certain that this inevitably leads to a paradox, although given all the encoding associate with the Godel Sentence it might be very complicated and roundabout.

Either way, it is just easier (from a consistency POV) to not assume that all grammatically correct propositions are true or false, even if it does make some proofs harder or nonexistent.

$\endgroup$
3
$\begingroup$

In the "real" world, i.e.in the world of everyday experience, contrasted to the world of mathematics, with its abstracts objects and structures, it is not so easy to find meaningful examples.

You can try with "vague" or "fuzzy" properties, like shade of colours. The question if my half-blue and half-green shirt "is green or is not green" can have no clear answer.

A person wieghting 100 kg is obese or is not obese ?

A young person of 12 years is a child or he is not ?

Since Aristotle, the excluded middle is so deeply ingrained into our rational thinking that when we "think logically" we tacitely assume it.

But there are significative example in philosophy of "overcoming" the principle; see in Wiki Hegel's dialectic :

Another important principle for Hegel is the negation of the negation, which he also terms Aufhebung (sublation): Something is only what it is in its relation to another, but by the negation of the negation this something incorporates the other into itself. The dialectical movement involves two moments that negate each other, something and its other. As a result of the negation of the negation, "something becomes its other; this other is itself something; therefore it likewise becomes an other, and so on ad infinitum". Something in its passage into other only joins with itself, it is self-related. In becoming there are two moments: coming-to-be and ceasing-to-be: by sublation, i.e., negation of the negation, being passes over into nothing, it ceases to be, but something new shows up, is coming to be. What is sublated (aufgehoben) on the one hand ceases to be and is put to an end, but on the other hand it is preserved and maintained.

$\endgroup$
2
$\begingroup$

Schrodinger's cat is not a good example because even in intuitionistic logic one can't have $P$ and $\neg P$ at the same time. What one can have, on the other hand, is a number $a$ which is neither nonpositive nor nonnegative. Then the function $f(x)=ax$ provides a (Brouwerian) counterexample to the extreme value theorem. This is discussed on page 294 of the book

Troelstra, A. S.; van Dalen, D. Constructivism in mathematics. Vol. I. An introduction. Studies in Logic and the Foundations of Mathematics, 121. North-Holland Publishing Co., Amsterdam, 1988.

$\endgroup$
1
$\begingroup$

There are many real-world examples that might be used. There are problems arising from incomplete information, going back to Aristotle's example of whether there will be a sea battle tomorrow, and as recent as having a data base system pick out all people with an address in a certain city when some people don't have a complete address. This example of whether a door is closed is another. Certain states of the weather make it difficult to decide whether "It is raining" is true or false. There are mathematical conjectures which have not yet been either proved or disproved. There are also inherently paradoxical statements such as the Liar paradox.

Classical, formal logic simply excludes such statements from consideration and goes to great lengths to define terms so that statements can be classed as either true or false. There is no truth value corresponding to "Don't know", "can't tell", or "maybe". However, real life is full of statements which could be classified this way and resist classification as "true" and "false".

The difficulty is in finding consistent, intuitively reasonable rules for rational reasoning and valid and sound deduction with equivocal or doubtful statements. Modal logic, intuitionism, and multi-valued logic are the three most successful approaches. None of them as they are presently understood has all the advantages of classical two valued logic.

Modal logic, following Aristotle and C.I. Lewis, has held to the law of the excluded middle. Lukasiewicz pioneered the use of 3-valued logic to examine modal logic, but his approach fell at least one important step short of success and has not been followed up by modern logicians. However, with his logic, any statement that can be considered both "possibly true" and "possibly false" is a candidate for application of the middle truth value.

$\endgroup$
0
$\begingroup$

If you want to communicate some of the issues with the law of the excluded middle to a non-mathematician, ask them to consider whether the statement "This statement is false" is true, false, neither or both.

The example with "The door is not unlocked" is unsatisfactory because it can be "explained away" by requiring that all presuppositions are agreed upon. Similarly, with the examples with vague/fuzzy properties we can require more precise wording or definitions, and with the examples of time-dependent statements we can say they are simply unknowable until time $t$.

However, Liar paradoxes such as "This statement is false" are much harder to fix by requiring more precise wording or blaming on bad communication, and do not even depend on knowledge of the outside world.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.