0
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Dan Simon Jan 3 at 19:45
  • $\begingroup$ @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? $\endgroup$ – Air Mike Jan 3 at 20:05
  • $\begingroup$ "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. $\endgroup$ – Dan Simon Jan 3 at 21:28
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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$). $\endgroup$ – Air Mike Jan 4 at 15:19
  • $\begingroup$ 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? $\endgroup$ – Air Mike Jan 4 at 15:21
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Jan 4 at 18:14
  • 1
    $\begingroup$ Once again, thank you, i really appreciate it. I will take a look at those texts :) $\endgroup$ – Air Mike Jan 5 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.