0
$\begingroup$

I have the set

$$ S = \{a,b,c,d\} $$

and the relation

$$G = \{(a,a)(b,b)(c,c)(d,d)(a,b)(b,a)(b,c)(c,b)\}$$

I want to define other various relations, such as symmetric, asymmetric, antisymmetric.

G is already symmetric because of the presence of $(a,b)(b,a)(b,c)(c,b)$, so for every element in the set S $ xRy => yRx $ holds. It's also reflexive.

If I add $(a,c)(c,a)$ to G it also becomes transitive. If I remove $(a,a)(b,b)(c,c)(d,d)$ it becomes irreflexive. If I were to leave $(a,a)$ in G it would be neither reflexive nor irreflexive.

If in G I only had $(a,b)(b,c)$ it would be an asymmetric relation, which is also automatically antisymmetric (if $aRb\;and\;bRa => a=b$) and irreflexive. Right?

If I had $(a,a)(b,b)(a,b)(b,c)$ it would only be antisymmetric, because there are some elements for which we have $xRy$, even if in this case it's always $x=y$ (it's not reflexive, but it could be if I added $(c,c)(d,d)$).

Is my reasoning right? I'm having some problems with asymmetric and antisymmetric relations (mostly because my professor inverted their names). Thank you for everyones help and time!

$\endgroup$
1
$\begingroup$

Yes, as a general theorem you have that a relation $R$ is asymmetric if and only if it is anti-symmetric and irreflexive, because:

$R$ is asymmetric if and only if there are not $x$ and $y$ such that $xRy$ and $yRx$.

So, assuming $R$ to be asymmetric:

if $R$ would not be irrelexive, then there would be some $x$ such that $xRx$, and therefore there are $x$ and $y$ (pick both to be that $x$) such that $xRy$ and $yRx$, and hence it would not be assymmetric. So: assymetric implies irreflexive

Also: $R$ is (trivially) anti-symmetric, since there simply is not a $x$ and $y$ such that $xRy$ and $yRx$, and hence the antecedent of $(xRy \land yRx) \to x = y$ is false, and hence the whole conditional true. So: assymetric implies anti-symmetric.

Indeed, both asymmetric and anti-symmetric agree on the claim that there is no $x \not = y$ such that $xRy$ and $y Rx$, meaning that the only difference between asymmetric and anti-symmetric is that for an anti-symmetric $R$ may contain elements $x$ such that $xRx$, while this is not true for an asymmetric $R$. Thus, if $R$ is anti-symmetric, but we then also rule out any $x$ such that $xRx$ (i.e. if $R$ is also irreflexive), then $R$ becomes asymmetric. In other words: if $R$ is anti-symmetric and irreflexive, then $R$ is asymmetric.

Which adds up to: $R$ is asymmetric if and only if $R$ is anti-symmetric and irreflexive.

Finally, some concrete examples may help to grasp the idea of asymmetric and anti-symmetric:

The 'smaller than' relation $<$ for numbers is asymmetric (and therefore also anti-symmetric): if $x<y$ we clearly can't have $y<x$. Note that $<$ is indeed irreflexive.

But the 'smaller or equal than' relation $\le$ is anti-symmetric: we can;t have two different $x$ and $y$ such that $x \le y$ and $y \le x$, but of course we do have that $x \le x$ fpor any $x$ (so it is reflexive ... and not asymmetric)

Similarly, the strict subset relation $\subset$ is asymmetric, but the 'normal' subset relation $\subseteq$ is anti-symmetric.

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