Symmetry, reflexivity and transitivity in set relations

Question

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

Answer 1

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$

Answer 2

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.

Answer 3

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.