1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I'm sorry, but there are so many problems with what you have written that it would be difficult to correct them in this format. Do you have someone you can talk to in person about this. You really need to sit down with someone have them go through these and work out the various issues 1 by 1. $\endgroup$ – Paul Sinclair Sep 19 '15 at 23:36
  • $\begingroup$ @PaulSinclair yes 3 problems but i need to determine for each problem which properties hold. In other words, each relation should have some properties and i need to list only those. $\endgroup$ – user_777 Sep 19 '15 at 23:45
  • $\begingroup$ When I said "problems", I meant "mistakes you've made and concepts you have misunderstood". The issues you have here are numerous. Which is why I recommend that if there is someone you can talk to in person about this, that would be your best choice. Because explaining the issues over the internet will would be difficult and slow. $\endgroup$ – Paul Sinclair Sep 19 '15 at 23:51
  • $\begingroup$ @PaulSinclair can you point out which parts are wrong, why are they wrong and i would be grateful if you provide some link(s) or literature, which demonstrates how to solve such problems (not the basic ones, but similar to these one). Unfortunately there is no one at the moment i could discuss with these problems in person with or who could explain how to solve them correctly. $\endgroup$ – user_777 Sep 20 '15 at 0:05
  • $\begingroup$ For starters, in (1) reflexive is right (although you should say $((x,y)(x,y))\in R_1$) but symmetric is wrong since $((2,3),(2,4))\in R_1$ but $((2,4),(2,3))\not\in R_1$. I would advise you to ensure that your post has one question only instead of so many. That would increase your chances of getting a reply. $\endgroup$ – Shahab Sep 20 '15 at 0:53
2
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ thank you very much for your efforts and time. I appreciate greatly your feedback and comments. $\endgroup$ – user_777 Sep 20 '15 at 2:49
  • $\begingroup$ I think in part 1) you need to remove Asymmetric because a Reflexive relation on a non empty set cannot be Asymmetric. When $x = y$ from $(x,y) \in R$ (which is true) does not follow that $(y,x) \notin R$ (which is not true). Now in part 2) you need to add Asymmetric because from condition ${y_1} \geq {y_2} + 1$ follows ${y_1} > {y_2}$, therefore ${y_2} > {y_1}$ is impossible. $\endgroup$ – user_777 Sep 20 '15 at 3:22
  • $\begingroup$ You are confusing Asymmetric and Antisymmetric. Antisymmetric means that if $a\,R\,b$ and $b\,R\,a$ are both true, then $a = b$. Asymmetric simply means neither symmetric nor antisymmetric. It is easy for reflexive relations to be neither symmetric nor antisymmetric. And note that reflexive and antisymmetric are not exclusive either. $\le$ is both reflexive and antisymmetric. $\endgroup$ – Paul Sinclair Sep 20 '15 at 3:30
  • $\begingroup$ math.stackexchange.com/a/350299/176596 $\endgroup$ – user_777 Sep 20 '15 at 3:33
  • $\begingroup$ Quoting: "For the asymmetric property, you need to show that if $uRv$, then $v\not Ru$ for all words $u$ and $v$. Note that the relation cannot have this property, because it is reflexive: both $uRu$ and $u \not R u$ cannot hold" $\endgroup$ – user_777 Sep 20 '15 at 3:34

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.