20
$\begingroup$

Given a set $\{1,2,3,4\}$, how is the following relation $R$ antisymmetric?

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

Note: Antisymmetric is the idea that if $(a,b)$ is in $R$ and $(b,a)$ is in $R$, then $a = b$. In my textbook it says the above is antisymmetric which isn't the case as whenever $(a,b)$ is in $R$, $(b,a)$ is not.

$\endgroup$
26
$\begingroup$

Try this: consider a relation to be antisymmetric, UNLESS there exists a counterexample: unless there exists $(a, b) \in R$ and $(b, a) \in R$, AND $a\ne b$.

Since no such counterexample exists in for your relation, it is trivially true that the relation is antisymmetric.

Another way to put this is as follows: a relation is NOT antisymmetric IF AND ONLY IF there exist $a, b$ such that BOTH $\;(a, b)\in R\;$ AND $\;(b, a) \in R\;$ BUT $\;a\ne b$.

This is true of other properties as well: a property holds for a relation unless there exists a counterexample such that the property fails to hold. Put differently, a property FAILS to hold IF AND ONLY IF a counterexample exists.

$\endgroup$
8
$\begingroup$

$R$ is antisymmetric iff whenever both $(a,b)$ and $(b,a)$ are in $R$ then $a=b$.

In your example, there is no pair $(a,b) \in R$ that also has $(b,a) \in R$, so the statement is vacuously true.

Another (equivalent) way of looking at it is that $R$ is not antisymmetric iff there are elements $a,b$ with $a\neq b$ and both $(a,b),(b,a) \in R$.

$\endgroup$
  • $\begingroup$ Can we equivalently say that a Relation is (always) either symmetric or antisymmetric but never both? $\endgroup$ – Sufyan Naeem May 10 '15 at 11:50
  • 2
    $\begingroup$ A relation can be symmetric and antisymmetric, take $R= \{ (x,x) \}$. $\endgroup$ – copper.hat May 10 '15 at 16:19
4
$\begingroup$

In my opinion your misunderstanding is in the logic, not in the set theory.

If $p$ is false, then the conditional statement “if $p$ then $q$” is vacuously true. This does not mean that $q$ is true, it means the entire statement is true.

As @Doug Chatham says,

For example, consider the implication, "If 2+2=5, then you will pass the course." Since 2+2 is not 5, the statement is a true statement, regardless of whether or not you pass the course.

Regarding your question, if $(a,b)\in R$ and $(b,a)\in R$ together imply $a=b$, and either one (or both) of $(a,b)\in R$ or $(b,a)\in R$ is false, then the entire statement is true: R is antisymmetric.

The definition of antisymmetry does not state

if $(a,b) \in R$ then $(b,a) \in R$

(that would be the definition of symmetry).

$\endgroup$
2
$\begingroup$

Here is an example that is going to show that the below relation is not anti-symmetric.

Let $R$ be the relation $$\bigl\{ (1,2), (1,3), (3,1), (1,1), (3,3), (3,2), (1,4), (4,2), (3,4)\bigr\} $$

First step is to find 2 members in the relation such that $(a,b) \in R$ and $(b,a) \in R$. If no such pair exist then your relation is anti-symmetric. If any such pair exist in your relation and $a \ne b$ then the relation is not anti-symmetric, otherwise it is anti-symmetric.

$$(1,3) \in R \text{ and } (3,1) \in R \text{ and } 1 \ne 3$$

therefore the relation is not anti-symmetric.

$\endgroup$
  • $\begingroup$ good example but it doesn't answer the question. $\endgroup$ – chharvey Jul 7 '15 at 18:53
1
$\begingroup$

You just need to check the cases. You are given a set $A=\{1,2,3,4\}$ and the relation $$\sim\; =\{(1,2),(2,3),(3,4)\}$$

Note that $a\sim b\iff a+1=b$. Thus, it will be never the case that the other pair you're looking for is in $\sim$, and the relation will be antisymmetric because it can't not be antisymmetric, i.e. the truth holds vacuously.

$\endgroup$
  • $\begingroup$ So it is similar to the idea of implications, if we don't know if the premise is true for sure, the conclusion is always true? $\endgroup$ – user1234440 Dec 10 '12 at 19:00
  • 3
    $\begingroup$ user123440: Not quite. If the premise is never true, then the implication is true, regardless of the truth of the conclusion. For example, consider the implication, "If 2+2=5, then you will pass the course." Since 2+2 is not 5, the statement is a true statement, regardless of whether or not you pass the course. $\endgroup$ – Doug Chatham Dec 10 '12 at 19:10

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