R is the relation defined on the set of integers by xRy when ⌊x/2⌋ = ⌊y/2⌋. Prove that R is an equivalence relation and find the equivalence classes.

1k Views Asked by At

So just to go through this real quick the Relation $R$ is an equivalence relation because it is

Reflexive - Yes, because for all $x$, $⌊x/2⌋ = ⌊x/2⌋$, so $xRx$.

Symmetric - Yes, because for all $x$ and $y$ if $⌊x/2⌋ = ⌊y/2⌋$, then $⌊y/2⌋ = ⌊x/2⌋$.

Transitive - Yes, because for all $x$ and $y$ if $⌊x/2⌋ = ⌊y/2⌋$, $xRy$, and $⌊x/2⌋ = ⌊z/2⌋$ then $xRz$ so $⌊z/2⌋ = ⌊y/2⌋$ so $zRy$.

Since all 3 of these hold true it is an equivalence relation, now I get confused when it comes to defining an equivalence class.

Now I think for this to hold true

$(x +.5) > y > x$

I'm not sure how to put that into terms of an equivalence class, maybe like so?

$[x]_R =$ {$y|(x +.5) > y > x$}

or maybe

$[x,y]_R =$ {$y|(x,y) \in R$}

1

There are 1 best solutions below

2
On BEST ANSWER

As noted in the comments, any equivalence relation on a set is the same as a partition of the set. Each element of the partition is an equivalence class.

The equivalence classes of this relation are sets of the form $\{2n, 2n+1\}$ for some $n \in \Bbb Z$. Note that every integer is in exactly one of these sets -- that's how you know the collection of these sets is a partition.

You also could define this same equivalence relation on $\Bbb R$, in which case the equivalence classes would be sets of the form $[2n, 2n+2)$ for $n \in \Bbb Z$. Again, note that every real number is in exactly one of these half-open intervals, which tells you that the set of these intervals is a partition, and therefore defines an equivalence relation.