# Basics: bivalence, excluded middle & noncontradiction

1. Nov 30, 2004

### honestrosewater

I'm trying to achieve a complete, precise understanding of the differences between these laws. A precise clarification of the following terms as they relate to each other is needed: true, not true, false, negation.

2. Nov 30, 2004

### AKG

LNC: $\neg (P \wedge \neg P)$ : It is not true that some proposition P and it's negation are true.

LEM: $P \vee \neg P$ : A proposition is true or it's negation is true, and the two need not be exclusive.

Principle of Bivalence: Either P is true, or it is false, and the two are exclusive.

Now, it is an entirely different subject to define truth, and different theorists will define it differently. Anyhow, given some definition for "true," then "not true" is, quite basically, what you can infer from the laws stated above. "Negation" and "not true" go hand in hand. The negation of P is equivalent to the proposition that P is not true, if we go with the convention that "P" is equivalent to "P is true" or "it is true that P." So explaining what "not true" is can be done by explaining "negation." What is negation, how does it work? Well, it works according to the 2 laws (not talking about the principle yet) above (according to most logics). How does implication work, i.e. what does "implies" mean? To get the answer, you might look at modus ponens and modus tollens, which essentially define how "implies" works. Similarly, the laws above essentially define how negation works.

The principle of bivalence basically says that $\neg P$ implies P is false, or rather, that if P is not true, then it is false (and vice versa). This is a slightly stronger condition. If we say that "this statement is false" is a proposition (which is arguable), then the LNC simply says that it is not both true and not-true. And in fact, it is easy to say that it is not true. By the principle of bivalence, this would render the propsition false, but it's also not-false. We can easily get away with saying that it is not-true and not-false, but if we add the principle of bivalence, then we get contradictions, if we suppose that it is a reasonable proposition. Also, some logics subdivide "not true" into two categories, including "false" and "possible" and some divide up truth values infinitely, and place them on a scale from 0 to 1, 0 representing falsehood, 1 representing truth, and numbers in the middle representing something between truth and falsehood (fuzzy logic).

If you want to think of them as sets, then the law of excluded middle say that:

$$P \cup \neg P = U$$

Where U is the universal set. So these sets together make up the whole unviersal set, but it doesn't say that they don't overlap. The law of non-contradiction says that:

$$P \cap \neg P = \emptyset$$

It says that the two sets do not overlap (but doesn't say that they cover the whole universal set). Together, they say that the two partition U. The principle of bivalence says that $\neg P$ is not divided up into further sets, it is only one set, and it can be labeled "false." Some logics say that it can be divided up into two sets, some say that it can be divided up into infinitely many sets.

3. Nov 30, 2004

### honestrosewater

Oh, you rock! I will read it thoroughly tomorrow and reply. Thank you! :!!)

4. Dec 1, 2004

### honestrosewater

Thanks again. To be sure I understand fully, I'll rephrase your comments.

LNC: a proposition p cannot be both true and not true (in the same instance).
LEM: for all p, "true" or "not true" are the only options.
POB: There is only one reason for p to be not true: because it is false.

Assuming LNC, LEM & POB, if p="There will be a sea battle tomorrow" is not true, then there will not be sea battle tomorrow. Some logics reject or modify LEM so they can have POB's falsifying power while allowing other options in addition to "true" and "not true". Correct?

BTW I like the set explanations, especially the partitioning concept.

Last edited: Dec 1, 2004
5. Dec 1, 2004

### Pavel

Can you please give an example where $$P$$ and $$\neg P$$ overlap while covering the whole set? I always thought the LNC dictates that $$P$$ and $$\neg P$$ must be exclusive in the LEM if you want them to be consistent within the same formal logical system. I'd love to see an example.

Thank you.

6. Dec 1, 2004

### AKG

Yes, but be careful to note that (with regards to LEM) this doesn't mean things can't be "false," they can be false, it is simply that "false" would be a "subset" of the "not true" option. Also, the principle of bivalence states that something is either true, or false. The explanation you gave for POB seems okay, but I think it loses some information if you don't assume the other two laws.
I'm not sure, I don't have any formal education in logic (not until next semester at least), so I can't tell you too much about what the various logics do. Some logics reject LEM to allow for possibilities like "possible" or "indeterminate" that are entirely distinct from "true" and "false." I think intuitionist logics do this, and they, as far as I know, substitute justification for truth, sort of. I think this gets into a more metaphysical/epistemilogical thing, though. Are mathematical propositions true, and our proofs convince us of that, or are they true upon being proven? This depends on which theory of truth you subscribe to, I would think. If mathematical propositions are inherently either true or false (and this has relation to metaphysics, because Platonists will see mathematical propositions as inherently true or false, since mathematical things really exist in a Platonic sense), then it makes no sense to reject LEM. Whether we know if the proposition is true, or even if it is indeterminate such that we can never tell if it is true, does not effect whether it is, "truly" true or not. However, if something is true upon being proven, then "false" can be equivalent to "proven false", true is equivalent to "proven true," possible is equivalent to "not proven to be true or false (yet)," and indeterminate would be equivalent to "can't be proven true nor false."

However, as far as I know, the POB implies LNC and LEM. What does the POB say without LEM? Something can be true, false, or some other option? Well that principle isn't saying anything at all. It is only saying something when it says that a proposition is either true or false, but never both, and never none. In saying that, of course, it implies LEM and LNC. (quickly note that POB without LNC says something can be true or false, and sometimes both, which makes the word "false" pretty meaningless, and again, the POB becomes meaningless). Actually, just disect the word "bivalent." bi:2, valent:values. There are only 2 values, so it certainly implies LEM.

7. Dec 1, 2004

### AKG

I'm not sure what you're asking for. If we assume LNC, then $P$ and $\neg P$ do not overlap, i.e. they are exclusive. On it's own, I don't see the LEM dictating that the two don't overlap, but I can't think of an example when they do. However, I'm sure one can invent a bizarre logic where the two overlap. Indeed, it all depends on how you want to define $\neg$ anyways. If you want to define it in some bizarre, unnatural sense, then you can certainly have overlap. I believe that, in the most natural sense, LNC and LEM are undeniable, however, some people like different theories of truth in which "possible" is a reasonable value for a proposition, and in such theories, logics will differ from logics that use LNC and LEM.

However, if you have LEM and don't have LNC, then you don't have the problem of the two being consistent (I can't tell if that's what you were asking though, you're question is unclear).

8. Dec 2, 2004

### honestrosewater

Great, I appreciate your patience. POB implies LNC and LEM. That's what I needed. I thought I read somewhere that some logics assume POB but reject LEM, and I couldn't figure out how that was possible. It isn't possible.
Right :uhh:

9. Dec 2, 2004

### Pavel

Well, I'm not implying any bizarre logic or some interpretation in an unnatural sense. I'm talking about our traditional classical logic system in which LNC, LEM, and POB are axioms, self evident truths that we have to take for granted. You’re right in that they’re undeniable, as in doing so, you would contradict yourself. It also means that they don’t imply each other, they’re fundamental atomic units of our classical logic system. Now, what I was saying was that for these axioms to play well together in one formal consistent system as our logic, the LEM has to be exclusive. The cat is either dead or not dead. Those both states “occupy” the full set and there’s no intersection between the two. If there is, then that entails there are situations where the cat is both dead and alive, which contradicts another axiom - LNC. That’s the way I see it, the LEM is exclusive. If not, I asked you for an example of the intersection where truth and the denial of a proposition are both asserted.

10. Dec 2, 2004

### loseyourname

Staff Emeritus
Well, the only linguistic formulations of the law of excluded middle that I've seen all that say that any proposition P must either be true or false, not that it must be either true, false, or both. Even if you formulate it symbolically, it still says the same thing. There is an interesting implication there in that non-contradiction might be redundant. I had never thought of that.

11. Dec 2, 2004

### AKG

No, the POB implies LNC and LEM. It also implies that there are strictly two values, so $\neg P$ cannot be subdivided into things like "P is possible" and "P is false," it is "atomic" in a sense, and simply stands for "P is false." Again, the LNC states that $P$ and $\neg P$ are exclusive, so the LEM is "exclusive" in a logic which holds to the LNC. However, you could come up with a logic, I assume, where LNC is denied, but LEM is held, in which case $P$ and $\neg P$ could overlap (by denial of LNC), but they would still "cover the whole set" (by LEM). Suppose that "dead" and "alive" are the only two options. According to some QM interpretations, I believe it is possible to say that the cat is both dead and alive. This would be an example of a case where the LNC is denied but LEM is asserted, so there still are two options that "cover the whole set", those options being dead or alive, but those options do overlap, as the cat can be both dead or alive. Actually, there is something called "quantum logic," I don't know much about it, but it might be a logic where LNC is denied but LEM might be held.

I think the decisions to agree with or deny these varies laws and principles depend mostly on definitions, and don't really show fundamental contradictions in the nature of logic. How do we define "not" and negation? How do we define implication? How do we define truth? How do we define a proposition? The way one chooses to answer these questions will essentially determine the axioms of his logic. Since these are questions have arbitrary answers, (we are essentially free to define things as we please, although I would argue that those definitions which are most rigorous yet, at the same time, most natural and common, are best), the differences between various logics is arbitrary and insignifcant. However, I hope to learn a little more about propositional logic and logic in general next semester, maybe I'll have something different to say then.

12. Dec 2, 2004

### AKG

loseyourname, stictly speaking, $P \vee \neg P$ states $P$ OR $\neg P$, as opposed to $P$ XOR $\neg P$. That lack of an "X" in the expression of LEM means exactly that the P and it's negation are not necessarily exclusive.

13. Dec 2, 2004

### loseyourname

Staff Emeritus
Yeah, you're right. I forgot that logical disjunction is inclusive.

14. Dec 3, 2004

### honestrosewater

That also confused me at first because in PC, LEM and LNC are equivalent tautologies: $$\neg ( P \wedge \neg P ) \equiv P \vee \neg P$$
Of course, this is because PC assumes POB.

15. Dec 4, 2004

### Pavel

16. Dec 4, 2004

### AKG

I would think it's based on the principle of bivalence.
There can be none, since our logical system asserts the prinicple of bivalence (which implies LNC), or, even if we say that it does not assert POB, it does at least assert LNC, which says there can be no overlap. I don't believe there can be an overlap, but the LEM without the LNC does not say that there can be no overlap. Personally, I think it's unnatural to do without the LNC, I'm just saying that if it were to be done, then we could have overlap.
It was never about contradicting the LEM. It was about contradicting the LNC. I'm not sure that you know what it is you're asking, and if you do, it is not clear to me at all what it is.
No, the LEM is not violated, the LNC is violated.

17. Dec 9, 2004

### Pavel

You're probably right: I'm not sure myself what it is I'm asking. I think I'm trying to define the boolean logic with boolean logic, and that's the problem.

But let me try again, if you will. You said
What exactly did you mean by "the two need not be exclusive". Please be specific with an example of it not needing to be exclusive and then, for contrast, an example of it needing to be exclusive. I think it'll be become clear to me as soon as you do it.

Thanks,

Pavel.

18. Dec 10, 2004

### honestrosewater

Pavel,
By definition, $P \vee \neg P$ means there are three possibilities: $P,\ \neg P,\ (P \wedge \neg P)$. The "or" is defined to mean "or/and", and "or/and" is not exclusive; It does not exclude $(P \wedge \neg P)$ as a possibility.
Don't take my word for it though.

As an example, if P is undecidable in X, then the LNC is an axiom or theorem of X. Right? If so, create a system that includes the LEM but not the LNC and translate "This statement is unprovable" into a proposition in the system. Don't take my word for it though.
____
Do you see what I'm saying? The LEM allows P to be 1) true, 2) false, or 3)true and false.
It's the LNC that excludes #3 as a possibility, thus making a proposition whose truth-value is #3 undecidable. Undecidable propositions are the example you are looking for. I think.

Last edited: Dec 10, 2004
19. Dec 10, 2004

### AKG

In the strictly logical sense, "OR" is not exclusive. So, if I ask, what kind of clothing do you want to buy, and you answer, "a shirt OR a pant," then you would find it acceptable if we bought just a shirt, just a pant, or both. "XOR" means "exclusive-OR". If you were to say, "a shirt XOR a pant," then that means you would want just a shirt, just a pant, but not both. I believe, in most situations, we use "or" as logic uses "XOR." When someone asks you what you want to eat, and you say, "italian or chinese" you mean either italian, or chinese, but not both. "XOR" is like saying EITHER option 1 OR option 2, BUT not both.

When I say that LEM says that they need not be exclusive, then that means that the case could be that P, ~P, or both. Now you would ask, "both P and ~P? That's weird." Indeed, it is, and that's what LNC is for. LEM says P, ~P, or both, and LNC says, no, not both. Putting them together, we get either P or ~P, just one or the other, not both. Now, I don't think I can give an example where we have P and ~P. LEM allows it, but LNC does not, so to give an example, I would have to deny LNC. I don't think I could make a rational English sentence using the word "not" if I were to deny LNC. Technically, such an example is possible, but I don't think you would buy it as a reasonable example because it would sound so unnatural.

20. Dec 10, 2004

### AKG

honestrosewater

Are undecidables true and false, or are they just undecidable?