2
$\begingroup$

I am learning of Equivalence Relations and for something to be one is has to be:

  • Reflexive (i.e., $aRa$)
  • Symmetric (i.e., $aRb$ $\Rightarrow$ $bRa$)
  • Transitive (i.e., $aRb$ & $bRc$ $\Rightarrow$ $aRc$)

Where we let $R \subseteq A\times A$ be a relation on a non-empty set $A$.

I see that Irreflexive is the 'opposite' of Reflexive. Similarly that Symmetric and Asymmetric are opposites.

Would Antisymmetric be the opposite of Transitive? Why is that the case, if so? If not, is it a complete separate property of relations and can it be true that something can be an equivalence relation and also Antisymmetric?

|cite|improve this question
$\endgroup$
  • $\begingroup$ How do you define antisymmetric? $aRb\; \& \! \! \! \! / \; bRa $? Isn't any relation, that isn't symmetric, then antisymmetric? Sorry I'm a little confused. Please help clarifying... $\endgroup$ – draks ... Jul 17 '12 at 17:36
  • $\begingroup$ Irreflexive is not the opposite of Reflexive. Irreflexive means not all elements are related to themselves, whereas Antireflexive means no elements are related to themselves. $\endgroup$ – alancalvitti Jul 17 '12 at 18:00
  • $\begingroup$ @alancalvitti: Many texts use "irreflexive" and "nonreflexive" (respectively) instead of "antireflexive" and "irreflexive". $\endgroup$ – Cameron Buie Jul 17 '12 at 23:03
  • $\begingroup$ @CameronBuie, that's true; many texts - and even communities of researchers - differ on a range of definitions, eg, groupoids, free vs. non-principal ultrafilters, isotone vs. monotone in posets $\endgroup$ – alancalvitti Jul 18 '12 at 2:30
1
$\begingroup$

Well, let's consider what such a property would entail. $R$ is said to be antisymmetric iff $$\forall a,b\in A(a\:R\:b\:\wedge\:b\:R\:a\:\Rightarrow\: a=b).$$ Observe that if $p,q$ are statements, then $p\Rightarrow q$ is logically equivalent to $q\vee\neg p$, and its negation would be $p\wedge\neg q$.

In this case, by "opposite", it seems you're intending the opposed universal statement, rather than simply the negation. That is, we're only negating the latter part, e.g: $\forall p(q)$ becomes $\forall p(\neg q)$. Thus, $R$ is the "opposite" of antisymmetric iff $$\forall a,b\in A(a\:R\:b\:\wedge\:b\:R\:a\:\wedge\:a\neq b).$$ Consider that statement, though. The only set $A$ on which it could hold would be $A=\emptyset$. (Why?) Thus, only the empty relation is the "opposite" of antisymmetric. But the empty relation is also antisymmetric, so this isn't really a useful or particularly relevant property.

As to the latter part of your question, an equivalence relation can be antisymmetric. Consider the identity relation $R:=\bigl\{\langle a,b\rangle\in A\times A:a=b \bigr\}$, for example. In fact, this is the only antisymmetric equivalence relation on $A$.

Proof: Let $S$ be an antisymmetric equivalence relation on $A$. It suffices to show that for all $a,b\in A,$ we have $a\:S\:b$ if and only if $a\:R\:b$. By reflexivity, we have that $a\:R\:b$ implies $a\:S\:b$. On the other hand, if $a\:S\:b$, then $b\:S\:a$ by symmetry, and then by antisymmetry we have $a\:R\:b$.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

As explained in the wikipedia entry on Intransitivity, Antitransitivity: $aRb \wedge bRc \Rightarrow \neg aRc$ is to Intransitivity what Antisymmetric is to Symmetric and Antireflexive is to Reflexive.

Intuitively, this more closely corresponds to opposite of the relations than do Intransitive, Asymmetric, Irreflexive (resp), in terms of the behavior of the quantifiers.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.