Understanding relationship between law of excluded middle and law of noncontradiction

Question

I was trying to understand the relationship between the two concepts.

On Wikipedia definition of excluded middle, it says:

In logic, the law of excluded middle (or the principle of excluded middle) states that for any proposition, either that proposition is true OR its negation is true

Is the bold OR above, "or" in mathematical sense, i.e. meaning according to above definition any proposition can be both true and false? (In math you know OR is true if either of operands or both are true).

1.1 If above OR is in mathematical sense, then I see need for other law: law of noncontradiction, which says that proposition can't be both true and false, which would be allowed if above OR was mathematical OR. Isn't it?

1.2 If however, above OR is not mathematical (like used in English) and it means one or other must be true but not both, then why the need for law of non contradiction? Wouldn't law of excluded middle in that case imply the law of non contradiction, since if a proposition must be either true or false (but not both), then it follows that it can't be both.

I was trying to see if one implies the other and came with following observation, maybe someone can also comment if this is true:

"To prove that those two laws are same, we must show one implies other and vice versa right? So if say law of non contradiction was true, which says proposition can't be both true and false, then it doesn't imply that maybe proposition is neither true nor false, right? Hence the need for law of excluded middle maybe? "

Note the use of the either X or Y, which means that we are in the presence of the exclusive or (XOR). — Ertxiem - reinstate Monica, Apr 10 '19 at 20:24
@Ertxiem In that case maybe you or someone else can answer 1.2? — , Apr 10 '19 at 20:27
Well the Wikipedia says that the complement of the law of non-contradiction is the law of the excluded middle and that the law of non-contradiction is logically equivalent to the law of excluded middle by De Morgan's laws.. — Ertxiem - reinstate Monica, Apr 10 '19 at 20:35
@Ertxiem To prove that they are same we must show one implies other and vice versa right? So if say law of non contradiction was true, which says proposition can't be both true and false, then it doesn't imply that maybe proposition is neither true nor false, right? Hence the need for law of excluded middle maybe? — , Apr 10 '19 at 20:38
Just to muddy the waters a bit: In intuitionistic logic, the law of excluded middle $P \vee \lnot P$ is not a tautology, but the law of noncontradiction $\lnot(P \wedge \lnot P)$ is a tautology. — Daniel Schepler, Apr 10 '19 at 20:42
@Ertxiem Typically De Morgan is a consequence of excluded middle. What your statement is actually saying is something like "if you add De Morgan to intuitionistic logic, you get classical logic" which is true, but intuitionistic logic (which has non-contradiction) doesn't include De Morgan. — Derek Elkins left SE, Apr 10 '19 at 21:22
@DanielSchepler, is there a dual (co-?) intuitionistic logic where noncontradiction not a tautology and excluded middle is a tautology? — alancalvitti, Aug 03 '19 at 09:01

score 2 · Answer 1 · answered Apr 10 '19 at 20:40

2

For 1. The law of excluded middle is usually phrased something like "$A\lor\neg A$". The $\lor$ symbol here is an ordinary inclusive "or", so if you somehow managed to find some $A$ where both $A$ and $\neg A$ were true, this would not be a counterexample to the law of excluded middle. There are other reasons why you can't find such $A$, however.

For 1.1. Yes, other laws are needed. So what? I don't think I've ever seen anybody promise that the law of excluded middle would be the only logical law you will ever need for deriving the logical facts you need.

answered Apr 10 '19 at 20:40

hmakholm left over Monica

286,031

So if it inclusive OR it necessiates the other law as I mentioned in 1.1, or the other law makes more sense now – Apr 10 '19 at 20:44
Since Brouwer thanked Bernays for showing him that excluded middle is derivable from double negation, why isn't the latter elevated to a law of thought? – alancalvitti Aug 03 '19 at 09:15

score 2 · Answer 2 · answered Apr 10 '19 at 20:56

The Law of the Excluded Middle (LEM) is the validity (for all proposition variables $P$) of $P\lor\neg P$. The "or" is the "mathematical or" i.e. inclusive or, but that's not the tricky part. Non-contradiction is $\neg(P\land\neg P)$. These could be combined together into a statement like $P\oplus\neg P$ where $\oplus$ stands for the exclusive or.

I'll return to the "tricky part" I mentioned before. You could read $P\lor\neg P$ as "$P$ is true or the negation of $P$ is true", but the "is true" needs to be taken a bit carefully. It is very easy to misread this as something like "$\vDash P$ or $\vDash \neg P$" or "$\vdash P$ or $\vdash \neg P$". The former states "either $P$ is valid or $\neg P$ is valid" and the latter "either $P$ is provable or $\neg P$ is provable". Neither of these are true even in logics where excluded middle holds. Even for a particular classical model $\mathcal M$, it doesn't need to be the case that $\mathcal M\vDash P$ or $\mathcal M\vDash\neg P$. For example, if our model assigns pairs of Booleans to each proposition and (the interpretations of) the connectives work component-wise, we can assign $(0,1)$ to $P$ making $\neg P$ be $(1,0)$ neither of which are "true" $(1,1)$ even though $P\lor\neg P$ evaluates to $(1,1)$.

It would be safer to simply say that LEM means $P\lor\neg P$ is "true" (or better, "valid" or "provable"). Many introductions to logic, especially ones that aren't very technical, make it way too easy to read far more into the Law of Exclude Middle than it actually states. For example, it is often suggested if not outright stated that LEM means that there are only two truth values: "true" and "false". It turns out LEM is neither necessary nor sufficient for there to be only two truth values. I already showed an example where LEM holds in a semantics with four truth values. I'll not go into detail, but you can also have models of constructive logics with only two truth values where all the usual rules of inference hold except for the ones peculiar to classical logic, i.e. LEM doesn't hold.

It is quite possible to have logics where the Law of Excluded Middle is not provable/valid or where the Law of Non-contradiction is not provable/valid or even where neither is provable/valid.

score 2 · Answer 3 · edited Jun 12 '20 at 10:38

The three pinciples : bivalence, excluded middle and non-contradiction are inextricably glued together in the semantics of classical logic.

As explained by other answers, when we leave that semantics, we can develop different logics - with their own semantics - where the logical laws formalizing the above principles may hold or not (separately).

To say that the semantics of classical logic is bivalent is to assume a "world" with exactly two truth-vales : $\text {True}$ and $\text {False}$, and to assume that the process of "semantical evaluation" of a sentence $p$ always comes to an end, producing as output one of them.

In addition, the said semantics assumes that the role of negation is to swap the truth-value of a sentence.

Thus, we can express bivalence this way :

(i) for every sentence $p$ and every valuation $v$ : $v(p) \in \{ \text T, \text F \}$.

(ii) for every sentence $p$ and every valuation $v$ : $v(\lnot p)= \text { T iff } v(p)= \text F$.

From them, excluded middle follows :

(LEM) for every $p$ and every $v : \text { either } v(p)= \text { T or } v(\lnot p)= \text T$, from which : $v(p \text { or } \lnot p)=\text T$, for every valuation.

At this point, the inclusive-exclusive uses of "or" has been by-passed, because - by (ii) above - we cannot have both disjuncts with the same truth-value.

In the same way, we have non-contradiction. From (ii) again, we have :

(LNC) for no $v : v(p)=v(\lnot p)$, from which : $v(p \text { and } \lnot p)= \text F$, for every valuation.

Up to now, we have used the "operations" of negation, disjunction and conjunction in an intuitive way, assuming very limited features of them.

If we formalize the above operations with logical connectives (defined through thier truth tables), De Morgan's laws easily follow :

$v(\lnot (p \land q)) = \text { T iff } v(p \land q) = \text F$. But this holds exactly when at least one of $p,q$ is evaluated to $\text F$, i.e. when at least one of $\lnot p,\lnot q$ is evaluated to $\text T$. And this amounts to $v(\lnot p \lor \lnot q) = \text T$.

On Non-contradiction, see Aristotle, Met, Book IV ($\Gamma$), 1005b34-on :

There are some who, as we have said, both themselves assert that it is possible for the same thing to be and not to be. [...] But we have now posited that it is impossible for anything at the same time to be and not to be, and by this means have shown that this is the most indisputable of all principles.

it is impossible that there should be demonstration of absolutely everything; there would be an infinite regress, so that there would still be no demonstration.

First then this at least is obviously true, that the word ‘be’ or ‘not be’ has a definite meaning, so that not everything will be so and not so.

If, however, they [meanings] were not limited but one were to say that the word has an infinite number of meanings, obviously reasoning would be impossible; for not to have one meaning is to have no meaning, and if words have no meaning reasoning with other people, and indeed with oneself has been annihilated; for it is impossible to think of anything if we do not think of one thing; but if this is possible, one name might be assigned to this thing. Let it be assumed then, as was said at the beginning, that the name has a meaning and has one meaning; it is impossible, then, that being a man should mean precisely not being a man [emphasis addwed].

Understanding relationship between law of excluded middle and law of noncontradiction

3 Answers3