# For each of the following relations, determine whether it is reflexive, symmetric or transitive

a) X is the set of real numbers, n is a natural number $$R = \{(x, y) \mid x, y \in X, x^n = y^n\}.$$

b) X is the set of people in the world $$R = \{ (x, y) \mid x, y \in X, x\text{ and }y\text{ share a parent}\}$$

I believe both relations are reflexive, symmetric and transitive, aren't they?

I mean, for a) you can have $x^n = x^n \rightarrow (x,x)$, you can have $(x,y)$ and $(y,x) \rightarrow$ symmetric and you can have transitivity by $\leq.$

And for b) it's pretty much the same. As it doesn't say $x$ mustn't be equal to $y$, then you can have $(x,x)$ which is true. You can also have $(y,x) \rightarrow$ symmetry and you can also get transitivity for "if $(x,y)$ is true and $(y,z)$ is true, then $(x,z)$ is true", right?

-
You haven't accepted any of the answers to your previous questions, even though in one case you thanked the author and seemed to imply that the answer was satisfactory. Accepting answers is good not also for rewarding people for helping you, but also to mark the questions as answered. – joriki May 14 '11 at 12:01
@joriki :) I forgot to, sorry about that. Just did that. – Sorin Cioban May 14 '11 at 12:03
Your use of "can have" is either unusual or may indicate a misunderstanding. The condition for symmetry is not whether you "can have $(x,y)$ and $(y,x)$", in the sense that there exist $x$ and $y$ for which both $(x,y)$ and $(y,x)$ are in the relation, but rather whether whenever $(x,y)$ is in the relation, $(y,x)$ is also in the relation, and this must hold for all $x$ and $y$. – joriki May 14 '11 at 12:06
This problem has nothing to do with symmetric groups. – Arturo Magidin May 14 '11 at 20:30

Relation (b) isn't transitive: consider half-siblings.

In detail: let $M(x)$ and $F(x)$ be the mother and father of person $x$. If $M(a)=M(b)$ and $F(b)=F(c)$ but $M(a)\ne M(c)$ and $F(a)\ne F(c)$ then we have $(a,b),(b,c)\in R$ but $(a,c)\not\in R$.

-
Exactly. If they're half-siblings, they will still share a parent. Not both, surely. But (b) is only about 1 parent (at least). – Sorin Cioban May 14 '11 at 12:04
@Sorin: mac's point was about transitivity. If $x$ and $y$ are half-siblings and $y$ and $z$ are half-siblings, does it follow that $x$ and $z$ are (at least) half-siblings? – joriki May 14 '11 at 12:09
Oh, I see your point now. No, it doesn't follow that x and z are half-siblings. So then, is my answer for a) ok? and for b) it's symmetric and reflexive? – Sorin Cioban May 14 '11 at 12:10
@Sorin: Yes, for b) it's symmetric and reflexive. For a), your result is correct, but your answer doesn't make any sense to me. It's not clear to me either how you're using "can have", or what role $\le$ is playing in your argument. – joriki May 14 '11 at 12:13
@Sorin: I'm sorry, you really aren't making any sense (to me). I think you need to go back and look at the definitions of these terms. Transitivity is a property of a relation, not a relation (like "less than or equal" is). Neither does "$x$ may be $\le$ than $y \le z$ make any sense" -- a variable can't be less than or equal to an inequality. Further, all this talk of "can be" and "may be" is inappropriate, since to prove transitivity etc. you have to prove that certain relationships hold for all $x$, $y$, $z$, not for some. – joriki May 14 '11 at 12:33

a) $X$ is the set of real numbers, $n$ is a natural number

$R$ = {($x$, $y$) | $x, y \in X, x^n = y^n$ }

You need to be careful, as was pointed out, with your phrasing of "can have" which implies "there exists", and your invocation of the $\leq$ relation to address problem (a).

1. First, reflexivity, symmetry, and transitivity of a relation requires that the properties are true for all elements of the set in question.
2. And secondly, to establish the transitivity of the relation $R$ in (a), you must demonstrate that the given defined relation is transitive (as was pointed out above, the $\leq$ relation is not the relation for which you need to establish transitivity.)

So, if you are going to argue that the relation given in (a) is transitive, you need to show that for all $x, y, z \in N,$ if $x^2 = y^2$ and $y^2 = z^2$, then it must follow that $x^2 = z^2$. To prove transitivity, you assume that the "if" conditions hold: Let $x, y, z$ be arbitrary elements of the set of natural numbers. Assume $x^2 = y^2$ and $y^2 = z^2$. Let $X = x^2, Y = y^2, Z = z^2$. Then our assumption can be expressed as $X = Y$ and $Y = Z$. Since equality is an equivalence relation, it is transitive, and hence $X = Z$, or $x^2 = z^2.$ Since $x, y, z$ were chosen arbitrarily, it follows that for all $x, y, z \in N,$ we have that $R$ is indeed transitive.

-