14
$\begingroup$

I don't understand the difference between an anti symmetric and asymmetric relation. From my understanding, it is asymmetric if there is not any element where: if (x,y) (y,x).

But what if you have only one (not all) double arrow (e.g. one where if (x,y) then (y,x)). What is the name for this kind of relation? Anti symmetric?

Same goes for irreflexive and anti-reflexive. From my understanding, it is irreflexive if for no x then (x,x). But what if you have only one element that refers to itself?

I hope I made the question clear.

Thank you.

$\endgroup$
25
$\begingroup$

A binary relation $R$ on a set $X$ is symmetric when :

$\forall a,b \in X ( aRb \rightarrow bRa )$.

An example of symmetric relation : "... is married to ___".

A binary relation $R$ on a set $X$ is asymmetric when :

$\forall a,b \in X ( aRb \rightarrow \lnot(bRa) )$.

An example of asymmetric relation : "... is father of ___".

A binary relation $R$ on a set $X$ is antisymmetric if there is no pair of distinct elements of $X$ each of which is related by $R$ to the other; i.e. :

$\forall a,b \in X ((aRb \land bRa) \rightarrow a = b )$.

An example of antisymmetric relation : The usual order relation ≤ on the real numbers.

Every asymmetric relation is also an antisymmetric relation.

Your proposal for asymmetric is :

  • if there is not any element where: if (x,y), then (y,x);

this "sounds" like :

$\lnot \exists x,y ( xRy \rightarrow yRx )$.

Moving "inward" $\lnot$, it is equivalent to :

$\forall x,y (\lnot ( xRy \rightarrow yRx ))$.

Now we need the equivalence between $\lnot ( p \rightarrow q )$ and $p \land \lnot q$ to get :

$\forall x,y (xRy \land \lnot (yRx) )$.

This is not the same as the formula in the definition.

According to the definition of asymmetric, if $a$ is father of $b$, then $b$ is not father of $a$, which is reasonable.

According to your "rewritten" condition, for every couple of individuals, we have that the first one is father of the second and the second is not father of the first one, which sound quite unreasonable.

Examples about reflexive and irreflexive (or anti-reflexive) :

  • the relation "... is equal to _" between real numbers is reflexive;

  • the relation "... is greater than ___" between real numbers is irreflexive.

$\endgroup$
11
$\begingroup$

Every asymmetric relation is also antisymmetric. But if antisymmetric relation contains pair of the form (a,a) then it cannot be asymmetric.

Antisymmetric means that the only way for both aRb and bRa to hold is if a = b. It can be reflexive, but it can't be symmetric for two distinct elements.

Asymmetric is the same except it also can't be reflexive. An asymmetric relation never has both aRb and bRa, even if a = b.

So an asymmetric relation is just one that is both antisymmetric and irreflexive.

Antisymmetricity is defined as:

 ∀a∀b(((a, b) ∈ R ∧ (b, a) ∈ R) → (a = b))

So if a = b then (a,b) = (a,a) = (b,b) = (b,a) ∈ R. So it implicitly says that if a ≠ b, then either (a, b) ∈ R or (b, a) ∈ R but not both, which indirectly is the part of the defition of asymmetricity

 ∀a∀b((a, b) ∈ R → (b, a) ∉ R)

However the definition above of asymmetricity indirectly adds that if a = b then

 (a,b) = (a,a) = (b,b) = (b,a) ∉ R. 

which is the reason for why asymmetric relation cannot be reflexive.

For example, {<1,1>, <1,2>, <2,3>} is not asymmetric because of <1,1>, but it is antisymmetric.

So in matrix representation of the asymmetric relation, diagonal is all 0s. And in digraph representation, there are no self-loops.

$\endgroup$
2
$\begingroup$

Let's take an analogy.

Relation : Hitting

$x$R$y$ $\equiv$ $x$ is related to $y$ $\equiv$ $x$ hits $y$.

Let's make two types of classification of people.

  • First classification:

    There are two types of people (y):

    1. If you hit them, they will hit you back.

    ($x$ hits $y$ => $y$ hits $x$) $\equiv$ ($x$R$y$ => $y$R$x$).

    1. If you hit them, they will ignore you.

    ($x$ hits $y$ but $y$ does not hits $x$) $\equiv$ ($x$R$y$ but $\lnot$$y$R$x$) .

  • Second classification:

    Insane people, they hit themselves.

    ($y$ hits $y$) $\equiv$ ($y$R$y$)

    And Sane people, they do not hit themselves.

    ($y$ does not hits $y$) $\equiv$ ($\lnot$$y$R$y$)

Now, we collect some people and make a set.

Symmetric relation:

If you make a set of all type (1) people and they are Insane people.

(type (1) $\wedge$ sane) $\equiv$ (($x$R$y$ => $y$R$x$)$\wedge$ ($y$R$y$))

So, Symmetric relation -

  1. If (x,y) is in set, then (y,x) must be in the set.
  2. (x,x) must be in the set.

Antisymmetric relation:

If you make a set of all type (2) people and they may be Sane or Insane people.

(type (2) $\wedge$ (sane $\lor$ Insane)) $\equiv$ (($x$R$y$ but $\lnot$$y$R$x$)$\wedge$ (($\lnot$$y$R$y$) $\lor$ ($y$R$y$)))

So, Antisymmetric relation -

  1. If (x,y) is in set, then (y,x) must not be in the set.
  2. (x,x) may or may not be in the set.

Asymmetric relation:

If you make a set of all type (2) people and they are Sane people.

(type (2) $\wedge$ sane) $\equiv$ (($x$R$y$ but $\lnot$$y$R$x$)$\wedge$ ($\lnot$$y$R$y$))

So, Asymmetric relation -

  1. If (x,y) is in set then, (y,x) must not be in the set.
  2. (x,x) must not be in the set.

Point 2. tells the difference between Antisymmetric and Asymmetric set.

Reflexive relation:

If you make a set of all Insane people. They may be type (1) or type(2).

($y$R$y$) $\wedge$ (type(1) $\lor$ type(2))

So, Reflexive relation -

  1. (x,x) must be in the set.
  2. If (x,y) is in set then, (y,x) may or may not be in the set.

Irreflexive/Anti-reflexive relation:

If you make a set of all Sane people. They may be type (1) or type(2).

($\lnot$$y$R$y$) $\wedge$ (type(1) $\lor$ type(2))

  1. (x,x) must not be in the set.
  2. If (x,y) is in set then, (y,x) may or may not be in the set.
$\endgroup$
0
$\begingroup$

I will consider the matrix representation of relation Now check condition 1} if all diagonal elements are 0 condition 2} transpose of a matrix is not equal to itself matrix A.

If above conditions are satisfies then your relation is asymmetric relation.

$\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.