Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 14 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer
Can we equivalently say that a Relation is (always) either symmetric or antisymmetric but never both? – Sufyan Naeem May 10 '15 at 11:50
A relation can be symmetric and antisymmetric, take $R= \{ (x,x) \}$. – copper.hat May 10 '15 at 16:19
Ah, I see...... – Sufyan Naeem May 10 '15 at 16:36

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).

share|cite|improve this answer

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.

share|cite|improve this answer
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? – user1234440 Dec 10 '12 at 19:00
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. – Doug Chatham Dec 10 '12 at 19:10

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.

share|cite|improve this answer
good example but it doesn't answer the question. – chharvey Jul 7 '15 at 18:53

protected by Zev Chonoles Dec 14 '15 at 10:20

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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