# Symmetry, reflexivity and transitivity in set relations

I am really having a difficult time applying the definitions of the above three set relations terms.

For the following problem $R = \{(x,y)|xy \geq 1, x, y \in Z\}$ I have to determine whether the expression is reflexive, symmetric, antisymmetric and/or transitive.

According to the book's answer, it is not reflexive because, for $(a, a) \in Z$ where $a = 0$, $0 \times 0 \ngeq 1$.

However, it states that the expression is symmetric, i.e. $(a,b) \in R \to (b,a) \in R$ for $a \neq b$. But I don't understand how this could hold, because if either $a$ or $b$ are zero then clearly the expression would be false.

I also don't understand how to apply the rule of transitivity to this expression; though the definition states $(a,b) \in R \land (b,c) \in R \to (a,c) \in R$, I don't have a variable $z$ in the expression to work with.

I know I am not understanding this or doing this correctly, but the book pretty much just gives definitions without many examples, as if it should be obvious (well it is not, for thick-headed folk like me).

-
Symmetry means if $(a,b)$ is in the relation then so is $(b,a)$. –  Gerry Myerson Aug 10 '12 at 4:41
Keyword if. If they both always fail together then you're fine. –  Robert Mastragostino Aug 10 '12 at 4:42
@Robert: If that is the case, then why would it also not be antisymmetric then, i.e. $(a,b) \in R \to (b,a) \in R$ for $a=b$? Even if both sides evaluate to false (because $a=b=0$), then the expression would result to true, would it not? –  Dylan Aug 10 '12 at 4:50
@Dylan: anti symmetric means if $a$ is related to $b$ (according to the rules of the relation, in this case, that $ab \ge 1$), and $b$ is related to $a$, then it means that $a = b$. –  ladaghini Aug 10 '12 at 5:01
Think of the integral lattice $\mathbb Z x \mathbb Z$. All integral points in the $(+,+)$ quadrant represent related integers, as do all points in the $(-,-)$ quadrant. Transitivity follows because $(a,b)$ and $(b,c)$ must share the same sign, therefore so do $(a,c)$ - note that $b$ belongs to both pairs in the transitivity clause. –  alancalvitti Aug 10 '12 at 5:03
show 1 more comment

To say that $(a, b) \in R$ means $a$ is related to $b$ (written as $aRb$). Here, two integers are related if their product is greater than or equal to $1$. So for any $a,b \in \mathbb{Z}$

$$aRb \iff ab \ge 1$$

This relation is symmetric since

$$aRb \implies ab \ge 1 \implies ba \ge 1 \implies bRa$$

Clearly, no integer is related to $0$. Transitivity also holds since if $aRb$ and $bRc$, then $ab \ge 1$ and $bc \ge 1$. Note that $a$ and $c$ can't possibly differ in sign, since that would imply $bc$ and $ab$ differ in sign. So $a$ and $c$ are positive integers, which means $ac \ge 1$

-
I don't understand what you mean by "no integer is related to zero". If we are considering the universe of integers, than wouldn't zero have to be considered here? If a or b were zero, wouldn't that contradict the given inequality? Or does that not have anything to do with whether it is "symmetric" or not? –  Dylan Aug 10 '12 at 5:29
@Dylan The implication $(a,b) \in R \implies (b,a) \in R$ always holds in this case. If either $a = 0$ or $b = 0$ then $(a, b) \in R$ is false. In general, an implication $P \implies Q$ is considered true if $P$ is false regardless of what $Q$ is. Is this what you were confused about? –  Vectk Aug 10 '12 at 5:35
ok, so if either a or b is false, either side of the implication operator would thus evaluate to false, therefore the entire expression would be true. Correct? (At least that is how I remember the truth table for the $\to$ operation, i.e $0 \to 0 = 1$). –  Dylan Aug 10 '12 at 5:39
Yes, 15characters –  Vectk Aug 10 '12 at 5:50
Ok, I fixed that. However, I am still not clear on why it cannot be antisymmetric as well. If two values are the same (i.e. for both positive and negative integers and not zero), that could be greater than or equal to one. Furthermore, the definition is $(a,b) \in R \land (b,a) \in R \to (a = b)$, which implies that even if everything left of the $\to$ operator is false (such as in the case that $a=b=0$), since a and b are equal the expression still evaluates to true, since $0\to1=1$. What am I missing here? –  Dylan Aug 10 '12 at 5:50

Again, for transitivity the key word is if:

if $\,(a,b)\,,\,(b,c)\in R\,\,\,,\,\,\text{then also}\,\,(a,c)\in R\,$ .

So, if $\,ab\geq 1\,\,\,\text{and also}\,\,\,bc\geq 1\,,\,\text{then}\,\,ac\geq 1$ , otherwise we'd have $$ac<1\Longrightarrow ac=0\,\,\,or\,\,\,ac\leq -1$$ as all the elements are integers, but then either

$$(1)\,\,a=0\,\,\,or\,\,\,c=0\Longrightarrow (a,b)\notin R\,\,\,or\,\,\,(b,c)\notin R\,\,,\,contradiction\,\,,\,\text{or}$$

$$(2)\,\,a>0\,,\,c<0\,\,\,or\,\,\,a<0\,,\,c>0$$ I'll leave it to you to show that any of the last two cases in (2) leads to contradiction, too.

-

I think it's important you understand how reflexivity, symmetry, and transitivity apply to relations.

### Relations

Before talking about the reflexivity, symmetry, transitivity of a relation, first let's talk about binary relations. A binary relation on a set $A$ is simply a subset of the Cartesian product $A \times A$. We choose what goes into that subset when we define the relation. Usually, the relation is defined by some mathematical rule or model, such as the one in your question, but it need not be so. It could just be a random selection of elements in $A \times A$ with no apparent coherent pattern or relationship. Fortunately this discussion will only consider relations defined by rules.

So a relation on $A$ is like a filtering of elements in $A \times A$ according to the rules. If $(a, b) \in A \times A$ "passes" the filter (which is the relation $R$), then we say that $a$ is related to $b$. Note that $(a, b)$ is an ordered pair, which means that $a$ coming before $b$ has significance and $(a, b)$ is not equivalent to $(b, a)$, as we'll see below.

The following statements are equivalent with respect to a relation $R$:

• $a$ is related to $b$
• $a R b$
• $(a, b) \in R$

### Reflexivity

This property is pretty straight forward. Is $a$ related to itself under the "rules" of the relation. Or, in other words, is $(a, a)$ in the set $R$? For example, if the relation is defined as $$R = \{(a, b) \mid a \ge b \quad a, b \in \mathbb{Z} \} \tag{1}$$ then simply apply $(a, a)$ to the definition of the relation: $a \ge a$ is true, so $a$ is related to itself. It is reflexive.

There's no reason that a relation be reflexive. Take for example the relation $$a R b \iff a > b \tag{2}$$. Here, $a \not > a$, so $a$ is not related to $a$, hence this relation is not reflexive.

### Symmetry

The symmetry of a relation indicates that if $a$ is related to $b$, then $b$ is related to $a$. It is easy to see that neither $(1)$ nor $(2)$ is symmetric. According to $(1)$, $2 R 1$ because $2 \ge 1$. However, $1 \not \ge 2$, so $(1, 2) \not \in R$. That $(2, 1) \in R$ but $(1, 2) \not \in R$ implies that $(1)$ is not symmetric. The same can be said about $(2)$. All it takes is finding counter examples.

A real life example could be: $$(a, b) \in R \iff b \mbox{ is } a\mbox{'s spouse} \tag{3}$$ Since marriage is a two way relationship, then $(3)$ is a symmetric relation.

### Anti-symmetry

The definition of an anti-symmetric relation is: for all $a, b$, if $a$ is related $b$ and $b$ is related to $a$, then it is necessary that $a = b$. Formally, $$\forall a, b \in X, \; (a, b) \in R \wedge (b, a) \in R \Rightarrow a = b \tag{4}$$

Let's look at $(1)$. If $a \ge b$ and $b \ge a$ then obviously it is necessary that $a = b$. Hence $(1)$ is anti-symmetric.

What about $(2)$? Well, the contraposition of the implication in $(4)$ states that if $R$ is not reflexive, it can't be anti-symmetric. Since $(2)$ is not reflexive, it's not anti-symmetric.

"A relation can be both symmetric and antisymmetric (e.g., the equality relation)" (Wikipedia).

### Transitivity

"If $a$ is related to $b$ and $b$ is related to $c$, then $a$ is related to $c$."

Both $(1)$ and $(2)$ are evidently transitive. When purely monogamous marriages are considered, $(3)$ is transitive too, but you'll be hard pressed to find distinct $a$, $b$, and $c$.

Consider the relation $a$ is related to $b$ if $a$ and $b$ have a parent in common. This is not a transitive relation because it could be that $a$ is the child of parents $A$ and $B$, $b$ is the child of $B$ and $C$, and $c$ is the child of $C$ and $D$, where $A$, $B$, $C$, and $D$ are distinct. $a$ is related to $b$ since they share a common parent $B$. Similarly, $b$ is related to $c$ because $C$ is their common parent. However, it is not the case that $a$ is related to $c$ since $a$'s parents are $A$ and $B$ and $c$'s parents are $C$ and $D$, and we've established that all four parents are unique. Since $a$ and $c$ are not related, then the transitivity of this relation does not hold. Note, however, that this relation is both reflexive and symmetric. It is not anti-symmetric.

-