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.
Best Answer
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.