What is the difference between Law of Excluded Middle and Law of Non Contradiction?

Question

In spite of reading the SEP entry under Contradiction several times I have difficulty distinguishing between the two.

We can translate the Aristotelian language, with some loss of faithfulness, into the standard modern propositional versions in (4a,b) respectively, ignoring the understood modal and temporal modifications:

(4a) LNC: ¬(Φ ∧ ¬Φ)

(4b) LEM: Φ ∨ ¬Φ

In words:

(5a) LNC: No proposition may be simultaneously true and false.

(5b) LEM: Every proposition must be either true or false.

Plugging in truth value yields that they are equivalent. Is this necessarily so? As a side-note: Is this equivalent of asking the interpretation behind "biconditional Law of Double Negation (LDN)" as in the following:

(LDN), ¬(¬Φ) ≡ Φ ?

Answer 1

The difference between the Law of Non-Contradiction and the Law of the Excluded Middle is subtle; fortunately, it's also irrelevant to most purposes.

The distinction becomes most evident if we contrast classical logic to the Indian Catuṣkoṭi, where four positions are available:

1. P
2. Not P
3. Both P and Not P
4. Neither P Nor Not P

These can be conveniently recast as

1. P is true
2. P is false
3. P is both true and false
4. P is neither true nor false

For Aristotle (and classical logic), the bottom two options are forbidden-- "Both P and Not P" because of the Law of Non-Contradiction (there exists no P such that P is both true and false), and "Neither P Nor Not P" because of the Law of the Excluded Middle (there exists no P such that P is neither true nor false, but some third state.)

So, they are not equivalent-- but are only relevant if you are looking to exclude deviant logics. If you are already playing by the rules of classical logic, the effect of each is the same (P is either true or false).

Answer 2

In classical propositional and first order predicate logic, they are equivalent as you noted by the truth table method. In classical FOL, 'and' and 'or' are dual (for every theorem with an 'and' there is a corresponding theorem where it is replaced by 'or' (and other things are rearranged accordingly.

As to necessity, well, one can redefine anything, but then you might be talking about something different, and one can doubt anything, but doubting doesn't make something true or false.

Which is to say... 'or' is considered a little more nuanced than 'and'. One can imagine certain circumstances where one is not so sure of 'P or -P'. For example, in the intuitionist judgement of the normality of pi), there is the idea that one can't really know one way or the other if every possible finite subsequence of digits occurs in the infinite sequence of digits of pi.

There is large amount of study of logics where 'P or -P' is not a theorem (not that it is false everywhere or even false once but simply that it is not provable in that system).

On the other hand, no one really bothers trying to doubt 'and'/LNC, because you don't have a very useful proof system without it. As an intellectual exercise one could deny LNC, but that little machine doesn't do too much. In contrast, one can still do lots of interesting mathematics while denying LEM (to be clear, when denying LEM, you're not using classical FOL anymore).

In the end, 'or' has the slightest bit of extra doubt to it than 'and', so LNC is pretty indispensable, but the lack of LEM doesn't make everything fall apart.

Answer 3

In Lukasiewicz three valued logic, Neither the LNC nor the LEM is a necessary truth for all propositions. They are contingent statements, true for some propositions but not necessarily true for all. It may be of interest to note that neither is ever actually false. They are, however, equivalent as in classical logic. This is true for the standard negation, in which the LDN also holds.

However, the extension to three values also permits definition of a strong negation, (not possible not Φ) in which the LNC holds but the LEM fails. The biconditional LDN fails: if Φ then ¬(¬Φ) but not conversely. This resembles the logic of intuitionism.

It also permits a weak negation (not necessarily not Φ) in which the LNC fails but the LEM holds. In this case, the biconditional LDN also fails, but in the opposite direction: if ¬(¬Φ) then Φ but not conversely.

Answer 4

Plenty of people choose to cling to the LNC, and they claim that ''I am not able to reason without the LNC, so the LNC is mandatory and reasoning without the LNC is not possible''. This strategy, from any rationalist, of claiming that something is impossible because he cannot think otherwise is a timeless fallacy, and, of course, there is nothing wrong with ditching the LNC. What can be done is found here:

Robert K. Meyer (1976) seems to have been the first to think of an inconsistent arithmetical theory. At this point, he was more interested in the fate of a consistent theory, his relevant arithmetic R#. There proved to be a whole class of inconsistent arithmetical theories; see Meyer & Mortensen 1984, for example. In a parallel with the above remarks on rehabilitating logicism, Meyer argued that these arithmetical theories provide the basis for a revived Hilbert Program. Hilbert's program was widely held to have been seriously damaged by Gödel's Second Incompleteness Theorem, according to which the consistency of arithmetic was unprovable within arithmetic itself. But a consequence of Meyer's construction was that within his arithmetic R# it was demonstrable by simple finitary means that whatever contradictions there might happen to be, they could not adversely affect any numerical calculations. Hence Hilbert's goal of conclusively demonstrating that mathematics is trouble-free proves largely achievable.

The arithmetical models used by Meyer-Mortensen later proved to allow inconsistent representation of the truth predicate. They also permit representation of structures beyond natural number arithmetic, such as rings and fields, including their order properties. Recently, these inconsistent arithmetical models have been completely characterised by Graham Priest; that is, Priest showed that all such models take a certain general form. See Priest 1997 and 2000. Strictly speaking, Priest went a little too far in including “clique models”. This was corrected by Paris and Pathmanathan (2006), and extended into the infinite by Paris and Sirokfskich (2008).

http://plato.stanford.edu/entries/mathematics-inconsistent/#Ari

The PEM can be seen as a weak axiom of choice, as explained here

Excluded middle can be seen as a very weak form of the axiom of choice (a slightly more controversial principle, doubted or denied by a slightly larger minority, and true internally in even fewer categories). In fact, the following are equivalent.

The principle of excluded middle.
Finitely indexed sets are projective (in fact, it suffices 2-indexed sets to be projective).
Finite sets are choice (in fact, it suffices for 2 to be choice).

https://ncatlab.org/nlab/show/excluded+middle#pem_versus_ac

Of course, the PEM is dubious and can be ditched in constructive predicative logic; yet still in 2016, a few people choose to cling to it...