In $ \mathbb{R^2}$ we consider the relation $(x,y)R(a,b)$ if and only if exists $n \in \mathbb{Z} $ such that $n-1<y\leq n \ $ and $ n-1<b\leq n \ $. Prove: $ R$ is an equivalence relation.

$R$ is an equivalence relation if it is reflexive, symmetric and transitive .

Reflexive: $\forall (x,y)\in \mathbb{R^2} \Rightarrow (x,y)R(x,y) \Rightarrow n-1<y\leq n \ \wedge n-1<y\leq n $

Symmetric: $\forall (x,y)\in \mathbb{R^2} \Rightarrow (x,y)R(a,b) \Rightarrow n-1<y\leq n \ \wedge n-1<b\leq n\Rightarrow n-1<b\leq n \ \wedge n-1<y\leq n\Rightarrow (a,b)R(x,y) $

Transitive $\forall (x,y)\in \mathbb{R^2} $ \begin{split} (x,y)R(a,b)& \| n-1<y\leq n \ \wedge n-1<b\leq n \\ (a,b)R(c,d)& \|n-1<b\leq n \ \wedge n-1<d\leq n \\ &\Rightarrow n-1<y\leq n \ \wedge n-1<d\leq n\\&\Rightarrow\ (x,y)R(c,d) \end{split}

Is correct my proof ?

  • 3
    $\begingroup$ For reflexivity, what is $n$? For transitivity, you are assuming the $n$ given from $(a,b)R(c,d)$ is the same as the $n$ given by $(x,y)R(a,b)$. It's incorrect to make this assumption. Overall the readability of the proof can be improved by using more words and less symbols. $\endgroup$ – John Griffin Sep 19 '17 at 19:57
  • $\begingroup$ $n$ is an integer number and constant? $\endgroup$ – B. David Sep 19 '17 at 20:08
  • $\begingroup$ The issue is that in order to show $(x,y)R(x,y)$, you must show that the particular $n$ exists. This means you must prove its existence in some way or describe it explicitly. $\endgroup$ – John Griffin Sep 19 '17 at 20:11

To expand on my comment, here's how I would adapt your proof.

Fix $(x,y),(a,b),(c,d)\in\mathbb{R}^2$.

For reflexivity, note that $\cup_{n\in\mathbb{Z}}(n-1,n]=\mathbb{R}$ and hence there exists $n\in\mathbb{Z}$ such that $n-1 < y \le n$. (Alternatively you can define $n:=\lceil y \rceil$ if you are familiar with the ceiling function.) Thus $(x,y)R(x,y)$.

For symmetry, suppose $(x,y)R(a,b)$. Then there exists $n\in\mathbb{Z}$ satisfying $$ n-1 < y \le n \quad \text{and} \quad n-1 < b \le n, $$ which by the symmetry of "and", is equivalent to $$ n-1 < b \le n \quad \text{and} \quad n-1 < y \le n. $$ Consequently $(a,b)R(x,y)$.

For transitivity, suppose $(x,y)R(a,b)$ and $(a,b)R(c,d)$. This means there are $n,m\in\mathbb{Z}$ such that $$ n-1 < y \le n \quad \text{and} \quad n-1 < b \le n $$ and $$ m-1 < b \le m \quad \text{and} \quad m-1 < d \le m. $$ Since $(n-1,n]$ and $(m-1,m]$ are disjoint whenever $n\ne m$ and $b\in(n-1,n]\cap(m-1,m]$, we infer $n=m$. Hence $n-1=m-1 < d \le m = n$ so that we have $$ n-1 < y \le n \quad \text{and} \quad n-1 < d \le n. $$ Therefore $(x,y)R(c,d)$.

This completes the proof that $R$ is an equivalence relation.


the last one should read

\begin{split} (a,b)R(c,d)& \| n-1<b\leq n \ \wedge n-1<d\leq n \\ &\Rightarrow n-1<y\leq n \ \wedge n-1<d\leq n\\ &\Rightarrow\ (x,y)R(c,d) \end{split}

(first evaluation is in $b$, not in $y$)

Also now will need to prove same $n$ for $y,b$ and $d$...

  • $\begingroup$ Thank you, it was a typing mistake $\endgroup$ – B. David Sep 19 '17 at 20:45

Your proof looks good to me, if they issues are fixed that others have pointed out. Using more words is good advice.

Another way to verify this is to make sure that the seeming equivalence relation generates well-defined equivalence classes that partition the underlying set. This particular relation appears to partition the plane into horizontal stripes: $\{(x,y)|n-1<y\leq n\}$ for each integer $n$. Thus, it appears to be an equivalence relation.


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.