# Identifying properties of relations

I was studying binary relations and, while solving some exercises, I got stuck in a question.

I am sharing the question and my thoughts on solving it, and I am looking for some advice and comments about my attempt (what is wrong or what should I do to improve it).

Question. Let $$A = \mathbb{N} \setminus \{1\}$$ and consider the following binary relations on $$A.$$ $$R_1 = \{(x,X) : X \in \mathcal{P}(A) \wedge x \in X\}, \quad R_2 = \{(x,y) \in A^2 : x < y\}, \quad \quad R_3 = \{(x,y) \in A^2 : y > x^2\}.$$

Determine, justifying, if each of the above relations are reflexive, symmetric, transitive or antisymmetric.

Sketch. Of course, to solve this problem, one must understand what does it mean for a binary relation to be reflexive, symmetric, transitive or antisymmetric. So, let’s, first, recall the definition of each concept.

Let $$A$$ be a set $$R \subseteq A^2$$ a binary relation on $$A.$$ The binary relation $$R$$ is

$$1.\quad$$ reflexive, if $$\quad \forall a \in A, aRa$$;

$$2.\quad$$ symmetric, if $$\quad \forall a,b \in A, aRb \implies bRa$$;

$$3.\quad$$ transitive, if $$\quad \forall a, b, c \in A, aRb \wedge bRc \implies aRc$$;

$$4.\quad$$ antisymmetric, if $$\quad \forall a,b \in A, aRb \wedge bRa \implies a = b.$$

Hence, we must check if these conditions are satisfied for each of the above relations.

Attempt.

$$\qquad 1. \quad R_1.$$

This relation was include in this exercise, but I don’t agree with this. Because, $$R_1 \subseteq \mathcal{P}(A) \times A,$$ and the question states that the relations that we are working on are relation on $$A.$$

But forgetting this for a moment, those properties were only defined for binary relations on a set $$A$$ and not for a binary relation from $$A$$ to $$B.$$ Therefore, it makes no sense in talking about those properties in this example.

$$\qquad 2. \quad R_2.$$

Let $$n \in A.$$ The proposition $$n < n$$ is false, hence $$(n,n) \notin R_2.$$ Therefore, $$R_2$$ is not reflexive.

Let $$m, n \in A.$$ Suppose that $$(m,n) \in R_2.$$ Then, by definition of $$R_2$$ we have that $$m < n.$$ Then, it is not true that $$n < m.$$ So, $$(n,m) \notin R_2.$$ Therefore, $$R_2$$ is not symmetric.

Let $$m, n, p \in A.$$ Suppose that $$m R_2 n$$ and $$n R_2 p.$$ Then, $$m < n$$ and $$n < p.$$ Since $$<$$ is transitive, then $$m < p$$ and so $$m R_2 p.$$ Therefore, $$R_2$$ is transitive.

Let $$m, n \in A.$$ Suppose that $$m R_2 n$$ and $$n R_2 m.$$ Hence, we have that $$m < n$$ and $$n < m$$ which is a contradiction and so $$\forall a,b \in A, aRb \wedge bRa \implies a = b$$ is vacuously true, Therefore, $$R_2$$ is antisymmetric.

$$\qquad 3. \quad R_3.$$

Let $$n \in A.$$ Since $$n \geq 2,$$ then $$n^2 > n.$$ So, it is not true, that $$n > n^2.$$ Hence, $$(n,n) \notin R_3.$$ Therefore, $$R_3$$ is not reflexive.

Let’s $$m, n \in A.$$ Suppose that $$m R_3 n.$$ Then, $$n > m^2.$$ It follows that $$n^2 > m^4$$ and $$m^4 > m.$$ Hence, $$n^2 > m.$$ Therefore, $$R_3$$ is symmetric.

Let’s $$m, n, p\in A.$$ Suppose that $$mR_3n$$ and $$nR_3p.$$ Then, $$n > m^2$$ and $$p > n^2.$$ Because $$n^2 > n,$$ then $$p > m^2.$$ Therefore, $$R_3$$ is transitive.

Let’s $$m,n \in A.$$ Suppose that $$mR_3n$$ and $$nR_3m.$$ Then $$n > m^2$$ and $$m > n^2.$$ Since, $$m^2 > m$$ then $$n > m.$$ So $$n \neq m.$$ Therefore, $$R_3$$ is not antisymmetric.

My biggest doubt is definitely on $$R_3.$$ I don’t know why, but that looks a bit suspicious to me. Although I have no clue of what is wrong. Can you help me?

• Your suspicion for $R_3$ is right, there's an issue with one of the proofs. Maybe try checking each property with an example like $(2,5)$. – Dan Simon Jan 3 at 19:45
• @DanSimon it is clear that $(5,2) \notin R_3$ and for that $R_3$ can’t be symmetric... but what was the error with my argument? – Air Mike Jan 3 at 20:05
• "It follows that $n^2>m^4$ and $m^4>m$. Hence, $n^2>m$." This is technically a true statement, but it's not showing symmetry for $R_3$. Just pay really close attention to what you're actually saying vs what you need to prove. – Dan Simon Jan 3 at 21:28

You’re right about $$R_1$$, except that it’s a subset of $$X\times\wp(A)$$, not of $$\wp(A)\times A)$$.

Your analysis of $$R_2$$ is correct.

Note that $$R_3$$ would not be reflexive even if $$1$$ were in $$A$$: as long as there is at least one $$a\in A$$ such that $$\langle a,a\rangle\notin R_3$$, $$R_3$$ is not reflexive.

$$R_3$$ is not symmetric: if $$\langle n,m\rangle,\langle m,n\rangle\in R_3$$, then $$m>n^2$$ and $$n>m^2$$, so

$$m>n^2>n>m^2\,,$$

and hence $$m>m^2$$, which is false for every $$m\in A$$. Thus, not only is $$R_3$$ not symmetric, it is asymmetric: if $$m\mathrel{R_3}n$$, then $$n\not\mathrel{R_3}m$$. It is true that if $$n>m^2$$, then $$n^2>m^4>m$$, so $$n^2>m$$, but that actually implies that $$n\not\mathrel{R_3}m$$: $$n\mathrel{R_3}m$$ means that $$m>n^2$$.

Your argument for transitivity of $$R_3$$ is correct. But as I showed above, $$R_3$$ is asymmetric, so it, like $$R_2$$, is vacuously antisymmetric.

• Thank you so much for the answer. At first I didn’t understood why $R_1$ was not a subset of $A \times \mathcal{P}(A)$ but now it is all clear in my mind. Also, in fact, there was a mistake that I did (it was required to prove that $m > n^2$ and not $n^2 > m$). – Air Mike Jan 4 at 15:19
• Once again, thank you for the answer. Just one short question. I would really like to know more about binary relations. Is there any books or texts that you would recommend as a good introduction to the study of binary relations? – Air Mike Jan 4 at 15:21
• @AirMike: You’re welcome. Most of the common sophomore-level discrete math texts have basic coverage, some more than others; I’ve been retired long enough that I no longer have a good picture of what’s available, but I seem to remember that the chapter on relations in the text by Kolman, Busby, and Ross had a bit more than some others that I used over the years. – Brian M. Scott Jan 4 at 18:14
• Once again, thank you, i really appreciate it. I will take a look at those texts :) – Air Mike Jan 5 at 14:53