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?
Thank you in advance for your attention.