Why is this relation antisymmetric?

42 Views Asked by At

$\mathcal{R} = \{(1,2), (2,3), (3,4)\} \:\: \mathcal{A} = \{1, 2, 3, 4\}$

The definition of antisymmetric states if $(a,b)$ and $(b,a)$ are both elements of $\mathcal{R} \implies a = b$. However, $(b,a)$ is not an element and yet it is considered antisymmetrical. What is the reasoning behind this?

3

There are 3 best solutions below

0
On

When the statement does not say anything about what happens when both are not elements of $R$ as in this case, we can say that this statement is true because for a statement $p$, $F \implies p$ is always $T$ (For $p = F$, $F \implies F = T$ and for $p = T$, $F \implies T = T$).

3
On

You are confused with the definition of symmetric relation here, for symmetric relation we need $(b,a)$ if we have $(a,b)$ in $R$. In other hand, we call a relation anti-symmetric, if it contains $(a,b)$ and $(b,a)$ then $a=b$. That means- if there exist some pair $(a,b)$ and also $(b,a)$ with $a\neq b$, then the relation is not anti-symmetric. More simply,in anti-symmetric relation we can't have $(a,b)$ with unequal elements $a$ and $b$ such that both $(a,b),(b,a)\in R$.

For visual aid, you can think of a $n\times n$ table, with $n$ elements of the set(on which you are defining the relation) on top and $n$ in left. We will write $1$ in $(i,j)$ position if $i$ is related to $j$ and $0$ otherwise. Observe that, for anti-symmetric relation, if you have $1$ in $(h,k)$ for some $h$ and $k$ with $h\neq k$ then you can't have $1$ at $(k,h)$(though entries at $(i,i)$ will be $1$). But for symmetric relation, if you have $1$ at $(a,b)$ then you must have $1$ at $(b,a)$.

For the given relation follow the tables below: $$ \begin{array}{c|lcr} \text{Fig I} & 1 & 2 & 3 & 4 \\ \hline 1 & 0 & 1 & 0 & 0 \\ 2 & 0 & 0 & 1 & 0 \\ 3 & 0 & 0 & 0 & 1\\ 4 & 0 & 0 & 0 & 0 \end{array}~~~~~~\begin{array}{c|lcr} \text{Fig II} & 1 & 2 & 3 & 4 \\\hline 1 & 0 & 1 & 0 & 0 \\ 2 & 1 & 0 & 1 & 0 \\ 3 & 0 & 1 & 0 & 1\\ 4 & 0 & 0 & 1 & 0 \end{array} $$

Observe that, $\text{Fig I}$ doesn't contain the $1$ at the diagonally opposite position where $1$ is placed. Hence, is the anti-symmetric relation. $\text{Fig II}$ contains $1$ for every diagonally opposite position where $1$ is placed above the diagonal-this type of table corresponds to symmetric relation.

Both may contain $1$ at the diagonal, means $(i,i)$ position for $i\in\{1,2,3,4\}$.

Hope it will help to distinguish between different kind of relations. (Can you work out how the table will look like reflexive or say asymmetric?)

0
On

The definition of an anti-symmetric relation can be thought of as follows: $$\forall a, b \in \mathcal{A} \,\, \left[((a \neq b) \longrightarrow ((a,b) \not\in \mathcal{R}) \vee ((b,a) \not\in \mathcal{R}))\right].$$

So the implication is false ONLY when we have $a,b \in \mathcal{A}$ such that $a \neq b$ and BOTH $(a,b)$ and $(b,a)$ are in the relation $\mathcal{R}$.

Consider $a=1,b=2$. Here $a \neq b$ is true, so the hypothesis of the implication is true. Now $(1,2) \in \mathcal{R}$ and $(2,1) \not\in \mathcal{R}$. This means the conclusion of the (above) implication $$((1,2) \not\in \mathcal{R}) \vee ((2,1) \not\in \mathcal{R})$$ is true. So the whole implication is true. Now you can check the remaining pairs as well.