2

An anti-symmetric relationship says that there is no pair of distinct elements of set $A$ which are related by $R$ to the other. A relation is anti-symmetric if for every pair of distinct elements in the domain one of the following situations holds:

  1. $xRy$, but it is not true that $yRx$
  2. $yRx$, but it is not true that $xRy$
  3. Neither $xRy$ nor $yRx$ is true

The Formal definitions of anti-symmetry: $$\require{cancel}\forall x,y \in A, (xRy \rightarrow y\cancel{R}x) \vee (yRx \rightarrow x\cancel{R}y) \rightarrow x \neq y$$

Or the logically equivalent way to express this is: $$ \forall x,y \in A, (xRy \wedge yRx) \rightarrow x = y$$

How do the formal definitions of anti-symmetry show the above statements? Alternatively, how do the formal definitions show that there is no pair of distinct elements of set $A$ which are related by $R$ to the other? From my understanding, it's saying that for a relation to be anti-symmetric, $\require{cancel}(xRy \rightarrow y\cancel{R}x) \vee (yRx \rightarrow x\cancel{R}y)$, then x cannot equal y, and if $(xRy \wedge yRx)$ then x=y. So why does x have to equal y for $(xRy \wedge yRx)$?

GainzNerd
  • 279

1 Answers1

1

The second one you list is easily seen to be equivalent. It is saying that if $xRy$ and $yRx$, then $x=y$. Taking the contrapositive, if $x\neq y$, then (de Morgan's law) either it is not the case that $xRy$ or it is not the case that $yRx$, which is the same as your list.

Your first formal definition doesn't seem to be equivalent. For any relation, $(xRy\to yRx)\vee (yRx\to xRy)$ is a tautology.

Matt Samuel
  • 58,164
  • Matt, forgive me. In my original post the relations weren't cancelled out so it didn't appear correctly. I fixed that.

    Also, I don't see how $xRy \wedge yRx \rightarrow x=y$ shows there is no pair of distinct elements of set which are related by to the other. Can you please explain further?

    – GainzNerd Mar 15 '20 at 21:26
  • @kvnr There can be distinct elements that are related, but not in both directions. It's the same as $x\neq y\to \neg(xRy\wedge yRx) =\neg(xRy) \vee \neg(yRx) $. – Matt Samuel Mar 15 '20 at 21:32