Relations and their properties

Question

I'm studying relations and their properties and trying to understand how to deal with more difficult examples. Given the following properties:

• Reflexive
• Transitive
• Symmetric
• Antisymmetric
• Asymmetric
• Complete $(x,y) \in R \vee (y,x) \in R,\,\forall x,y \in S$, where $R$ is the relation on the set $S$

Which of the above listed properties are true for the following relations:

1. The relation $R_1$ on the set $\mathbb R^2=\{(x,y)\,:\, x,y \in \mathbb R\}$ is $R_1=\{((x_1,y_1),(x_2,y_2)) \,:\,y_1\leq y_2\}$
2. The relation $R_2$ on the set $\mathbb R^2=\{(x,y)\,:\, x,y \in \mathbb R\}$ is $R_2=\{((x_1,y_1),(x_2,y_2)) \,:\,x_1 \leq x_2+1,\, y_1\geq y_2+1\}$
3. The relation $R_3$ on the set $\mathbb N_+=\{1,2,3,4,\ldots\}$ is $R_3=\{(m,n) \,:\,m\cdot n= k\cdot 2,\, k\in \mathbb N_+\}$

My attempt:

1. The relation $R_1$ is Reflexive because for all $$(x,y) \in {\mathbb{R}^2}, y \leq y \Rightarrow ((x,y),(x,y)) \in {\mathbb{R}^2}$$ It is Symmetric because if we have $(({x_1},{y_1}),({x_2},{y_2}))$ we can have $(({x_2},{y_2}),({x_1},{y_1}))$, where we can always choose ${y_1} = {y_2}$ to satisfy ${y_1} \leq {y_2}$. It is Transitive because if $$(({x_1},{y_1}),({x_2},{y_2})) \in {R_1} \wedge (({x_2},{y_2}),({x_3},{y_3})) \in {R_1} \Rightarrow (({x_1},{y_1}),({x_3},{y_3})) \in {R_1},\,\,{y_1} \leq {y_3}$$ It is not Antisymmetric because, for example, $$((1,3),(2,3)) \wedge ((2,3),(1,3)) \in {R_1},\,\,\,(1,3) \ne (2,3)$$ It is not Asymmetric because $$(({x_1},{y_1}),({x_2},{y_2})) \in {R_1}\neg \to (({x_2},{y_2}),({x_1},{y_1})) \notin {R_1},\,\,\forall x,y \in {\mathbb{R}^2}$$ It is Complete because the condition is satisfied.

2. The relation $R_2$ is not Reflexive because for all $$(x,y) \in {\mathbb{R}^2},\,\,0 \leq 1,\,\,0 \geq 1 \Rightarrow ((x,y),(x,y)) \notin {\mathbb{R}^2}$$ It is not Symmetric because if we have $(({x_1},{y_1}),({x_2},{y_2})) \in R_2$ we must have $(({x_2},{y_2}),({x_1},{y_1})) \in R_2 $, such that $$ - 1 \leq {x_1} - {x_2} \leq 1 \wedge {y_1} - {y_2} \geq 1 \wedge {y_1} - {y_2} \leq - 1$$ but the condition on $y$ is not possible. It is Transitive because if $$(({x_1},{y_1}),({x_2},{y_2})) \in {R_2} \wedge (({x_2},{y_2}),({x_3},{y_3})) \in {R_2} $$ we can always pick $({x_3},{y_3})$ that satisfies $${x_3} \geq 2({x_1} - 1) - {x_2},\,\,{y_3} \geq 2({y_1} - 1) - {y_2}$$ It is Antisymmetric because we showed that $R_2$ is not reflexive and is not symmetric, therefore we may have $(({x_1},{y_1}),({x_2},{y_2}))$ but if $(({x_2},{y_2}),({x_1},{y_1}))$ is missing the Antisymmetric condition becomes true. It is Asymmetric because $$(({x_1},{y_1}),({x_2},{y_2})) \in {R_2} \to (({x_2},{y_2}),({x_1},{y_1})) \notin {R_2},\,\,\forall x,y \in {\mathbb{R}^2}$$ It is not Complete because not all $x,y \in {\mathbb{R}^2}$ can be used in the relation.

3. The relation $R_3$ is not Reflexive because for all $$(m,n) \in \mathbb N_+,\,\,{m^2} = 2k,\,\,k \in \mathbb N_+ \Rightarrow \forall (m,n) \notin \mathbb N_+$$ It is Symmetric because if we have $(m,n) \in R_3$ we must have $(n,m) \in R_3$, such that $$m \cdot n = n \cdot m = 2k$$ It is not Transitive because if $$(m,n) \wedge (n,s) \in R_3 \Rightarrow (m,s) \notin R_3$$ since $(m,s)$ can be both odd and so it cannot be in $R_3$. For instance, $(3,2)$ and $(2,3)$ are both in $R_3$, however, $(3,3)$ cannot be in $R_3$. It is not Antisymmetric - counter example $(1,2) \wedge (2,1) \in {R_3}$ but $1 \ne 2$. It is not Asymmetric because $$(m,n) \in {R_3} \to (n,m) \in {R_3}\,\,$$ It is not Complete because not all $m,n \in {\mathbb N_+}$ can be used in the relation.

Please post your feedback and tell me if i made some mistake.

Answer 1

I am going to use the much simpler infix notation for relations: $ x\, R\, y \iff (x, y) \in R$. It makes the notations easier to follow.

(1) (Also, I will call this $R$ instead of $R_1$. Since this whole section is about this single relation, there should be no confusion.)

$$ (x_1, y_1)\,R\,(x_2, y_2) \iff y_1 \le y_2$$ This relation is reflexive, transitive, asymmetric, and complete. It is not symmetric or antisymmetric.

• Reflexivity: Your reasoning here was correct. For all $x, y$, since $y \le y$, we have $(x, y) \,R\, (x, y)$.
• Transitive: You are correct, but the reason you offered was not. To prove something is transitive, you need to show that if $a\,R\,b$ and $b\,R\,c$ are both true, then it must also be that $a\,R\,c$ is true. In your reasoning you just assumed transitivity was true, and claimed as a result that something else was true. Well, you are correct that transitivity does imply that $y_1 \le y_3$, but that does not prove that transitivity itself is true. To prove transitivity, we assume the hypothesis, $(x_1, y_1)\,R\,(x_2, y_2)$ and $(x_2, y_2)\,R\,(x_3, y_3)$, holds. Then we must use this to show that the conclusion, $(x_1, y_1)\,R\,(x_3, y_3)$, also holds. But the hypothesis implies that $y_1 \le y_2$ and $y_2 \le y_3$. Since $\le$ is transitive, we have that $y_1 \le y_3$, and therefore by the definition of $R$, $(x_1, y_1)\,R\,(x_3, y_3)$ is true.
• Symmetry: We don't get to pick $y_1$ and $y_2$. Symmetry says if $a\,R\,b$, then we also have $b\,R\,a$. Note that $(0, 1) \,R\, (0,2)$, but it is not true that $(0, 2) \,R\, (0,1)$.
• AntiSymmetry: Your example here was correct. $(1, 3) \,R\, (2,3)$ and $(2, 3) \,R\, (1,3)$, but $(1, 3) \ne (2,3)$.
• ASymmetry: $R$ is neither symmetric nor antisymmetric, so it is asymmetric.
• Complete: You are correct, but you didn't prove it so. Of course the problem didn't ask you to prove it, but I don't know if you got the right answer because you figured it out correctly, or because there are only two possibilities, and so random chance gives the right answer 50% of the time. To prove it, let $x_1, y_1,x_2, y_2 \in \Bbb R$. Because $\le$ is complete, either $y_1 \le y_2$ or $y_2 \le y_1$. Therefore either $(x_1, y_1)\,R\,(x_2, y_2)$ or $(x_2, y_2)\,R\,(x_1, y_1)$.

(2) $$ (x_1, y_1)\,R\,(x_2, y_2) \iff x_1 \le x_2 + 1 \text{ and } y_1 \ge y_2 + 1$$

This relation is antisymmetric. It is not reflexive, transitive, symmetric, asymmetric, or complete.

• Reflexive: you are correct, but I cannot even begin to figure out what you meant by your reason. To show that $R$ is not reflexive, it suffices to give a single counter-example: $(0, 0)\,\not R\,(0, 0)$, since $0 \not{\ge}\, 0 + 1$. (Though in truth we can show more - that $(x, y)\,\not R\,(x,y)$ for all $x, y$ - we only need to show it for one case. The condition that $a\,R\,a$ never holds is called "AntiReflexive".)
• Transitive: Once again, we don't get to pick $(x_3, y_3)$. These are values that are defined in the hypothesis. We can't change them to get our conclusion. In fact you can check that $(1.8,6)\,R\,(0.9,4)$ and $(0.9,4)\,R\,(0,2)$, but $(1.8,6)\,\not R\,(0,2)$.
• Symmetric: You are correct, and your reasoning is good, but you could have just provided a single counter-example: $(0, 1)\,R\,(0,0)$, but $(0,0)\,\not R\,(0,1)$.
• Antisymmetric: You are correct, but your reason is false. Not being symmetric or reflexive does not imply antisymmetry (even if this relation was transitive). It is actually antisymmetric because of the argument you gave for not being symmetric: $y_1 \ge y_2 + 1$ and $y_2 \ge y_1 + 1$ cannot hold at the same time, so it is impossible for $(x_1, y_1)\,R\,(x_2, y_2)$ and $(x_2, y_2)\,R\,(x_1, y_1)$ to both be true.
• Asymmetric means not symmetric nor antisymmetric. Since this relation is antisymmetric, it is not asymmetric.
• Complete: You are correct, but again didn't demonstrate why. One example is $(0, 0)$ and $(1,0)$ Since $0 \not{\ge}\, 0 + 1$, neither $(0, 0)\,R\,(1, 0)$ nor $(1, 0)\,R\,(0, 0)$ holds.

(3) $$ m\,R\,n \iff 2 | mn$$

(The notation $2 | mn$ means "$2$ divides $mn$", which is equivalent to the version you gave, but simpler to write.)

This relation is symmetric, but not reflexive, transitive, antisymmetric, asymmetric or complete. (So your answers are correct on this one, though the reasons are not always so.)

• Reflexive. Your reason for this is non-sensical. [As an aside on notation: $(m, n) \in \Bbb N_+$ means "the ordered pair $(m, n)$ is an element of $\Bbb N_+$". Since $\Bbb N_+$ is a collection of numbers, not ordered pairs, this is impossible. What you meant was $m, n \in \Bbb N_+$, which just means "$m$ and $n$ are two elements of $\Bbb N_+$".] First of all, why is $n$ even there? Reflexivity is a condition on one object, $m$. We don't throw in a second object "just because". (Note that in the other two relations the objects were ordered pairs, so we did have ordered pairs showing up there. But there was still only one involved in the Reflexivity condition.) Then you end with $m^2 = 2k, k \in \Bbb N_+ \implies \forall m \notin \Bbb N_+$. Even after removing the pointless $n$, this makes no sense. (By the way, $\implies$ means "implies" and only "implies". You should never use it unless you mean that "the statement on the right is logically deduced from the statement on the left".) $m^2$ being divisible by 2 does not imply that all $m$ are not positive integers. To really show $R$ is not reflexive, simply note that $1 \cdot 1$ is not divisible by 2, so $1\,\not R\,1$.
• Transitive: Your idea is correct, though your notation is bad: $m\,R\,n$ and $n\,R\,s$ does not imply $m\,\not R\,s$. But if $n$ is even and $m$ and $s$ are odd, then it is true that transitivity fails. Your counterexample by itself would have been sufficient, but it is fine to have explained it in more detail (other than the notation problem).
• Symmetry: Your argument is correct.
• Antisymmetry: Your counterexample is correct. (Note that the only way a relation can be both symmetric and antisymmetric is if there is only zero or one element in its domain. So other than these two uninteresting cases, proving symmetry disproves antisymmetry, and vice versa.)
• Asymmetry: it is symmetric, so it is not asymmetric (this is effectively what you argue, so you are correct, though unnecessarily verbose).
• Complete: again you offer no evidence to back up your statement, but $1, 3$ provide an obvious counterexample.