Why is $\lor$ used in cases where xor is intended?

115 Views Asked by At

A binary relation $R$ on a set $X$ is trichotomous if the following is true:

$$\forall x,y \in X ([\neg(x <y) \land\neg(x=y) \land (x>y)] \lor [\neg(x <y) \land(x=y) \land \neg(x>y)] \lor [(x <y) \land\neg(x=y) \land \neg(x>y)])$$

At least, that's what this Wikipedia article said.

If they mean inclusive or by "$\lor$", then the above statement is incorrect. If they mean exclusive or, it is correct. However, I thought the notation for exclusive or was $\text{XOR}$ or $\oplus$, and that the notation for inclusive or was $\lor$.

Perhaps this is a case of differing notational conventions in different logics? If so, what logic was used in that article, and if xor is notated as $\lor$, what then is their notation for the inclusive or?

Just for clarity, using the notation the way I'm familiar with would yield this:

$$\forall x,y \in X ([\neg(x <y) \land\neg(x=y) \land (x>y)] \oplus [\neg(x <y) \land(x=y) \land \neg(x>y)] \oplus [(x <y) \land\neg(x=y) \land \neg(x>y)])$$

EDIT:

Not sure I get the explanations here.

I'll just elaborate on my understanding here, so as to maybe illuminate my misunderstanding:

$$(a = b) \lor (a \neq b)$$

This is wrong, because it opens up for the possibility of both $(a = b)$ and $(a \neq b)$ to be true at the same time, which is a contradiction. The inclusive or includes a possiblity here that's self-contradictory. That's my quarrel with the formula from the Wiki article. All of those three sub-formulae are in contradiction with each other, and thus, including the possibilities of several being true is wrong.

At least, that's how I see it.

3

There are 3 best solutions below

2
On BEST ANSWER

Per your edit, you misunderstand what it means to assert an inclusive disjunction.

When we say "$X\vee Y$ is true" we do not mean "each of $X\wedge\neg Y$, $\neg X\wedge Y$, and $X\wedge Y$ is possible and one must be true" - we're simply asserting that either $X$ is true or $Y$ is true or both, leaving the door open to further assertions like "in fact $X\wedge Y$ does not hold" or "in fact $X$ holds outright."

It may arguably be good pedagogical practice to make the strongest assertion immediately justified by context, e.g. "$a=b\oplus a\not=b$" instead of "$a=b\vee a\not=b$," but it's not mathematically necessary to do so. (In fact in my opinion it's not good pedagogical practice, but that's a whole separate discussion.)

7
On

Using the inclusive "or" is correct here.

Notice that the conditions in brackets are like this: $[\neg(x <y) \land\neg(x=y) \land (x>y)]$, and similarly for the other two. So the conditions themselves already exclude the possibility that more than one of the $x>y$, $x=y$, $x<y$ happen, so the "or" symbol itself does not need to do the exclusion.

Additionally, $\oplus$ only means "exclusive or" for two elements. $A \oplus B \oplus C$ means "either exactly one, or all three" of $A, B, C$, and in general, $A_1 \oplus A_2 \oplus \ldots A_n$ means that an odd number of $A_i$'s are true (not exactly one), as you can easily check with the definition of xor.


Addendum. To be clear, that is to say: $$\rm A\oplus B\oplus C = (A\land\neg B\land\neg C)\lor(\neg A\land B\land\neg C)\lor(\neg A\land\neg B\land C)\lor(A\land B\land C)$$

But the trichotomy principle is expressed in the form of: $$\rm (A\land\neg B\land\neg C)\lor(\neg A\land B\land\neg C)\lor(\neg A\land\neg B\land C)$$

Because we do not want to admit $((x{\lt}y)\land(x{=}y)\land(x{\gt}y))$ as a possibility.

0
On

No, using inclusive or is correct:
The statement is: $$\forall x,y \in X ([\neg(x <y) \land\neg(x=y) \land (x>y)] \lor [\neg(x <y) \land(x=y) \land \neg(x>y)] \lor [(x <y) \land\neg(x=y) \land \neg(x>y)])$$
If you notice if any one of the three statements separated by $\lor$ is true then the other two are false,For instance if $ [\neg(x <y) \land\neg(x=y) \land (x>y)]$ is true then the other two are false since ,one of the other has $\neg(x>y)$ and the other has $(x <y)$.