0

pf. Assume x $\equiv _m y$. Then $\bar{x}$ = y (mod m). By equivalence y = x (mod m). Then y $\in $ [0,m-1]. Thus, $\bar{y}$ = y (mod m). Therefore, $\bar{x}$ = $\bar{y}$.

Is this proof correctly written? I just did a direct proof. I feel like this statement is obvious, but when that is the case the proofs seem difficult.

Let R be an equivalence relation on a set A. For x $\in$ A, the equivalence class of x determine by R is the set. x/R = {y $\in$ A : xRy}. x/R is equivalent to [x] and $\bar{x}$

Edit: Assume x $\equiv$ $_m$ y. Then x=y+mk for some k $\in$ $\mathbb{Z}$. There exists some z such that z $\equiv _m x$, then $$z=x+ml$$ $$z=y+mk+ml$$ $$z=y+m(k+l)$$ $$z\equiv _m y$$ Therefore $\bar{x} = \bar{y}$.

JWigz
  • 87
  • You'll have to say precisely what you mean by $\overline{x}$ and $\overline{y}$. – Daniel McLaury Oct 28 '16 at 04:28
  • @DanielMcLaury I wrote the definition if that helps. Let me know. – JWigz Oct 28 '16 at 04:33
  • @DanielMcLaury I edited my question. I think I understood what you were trying to say. – JWigz Oct 28 '16 at 04:56
  • Okay, the updated proof makes more sense, but it's not written all that well. Like, instead of "There exists some z such that $z\equiv_m x$, then..." (which doesn't make sense), you want to say "If z \in \overline{x}, then $z \equiv_m x$, so..." Then once you conclude that $z \in \overline{y}$, what you've shown is that $\overline{x} \subseteq \overline{y}$. To get equality you also need to establish $\overline{y} \subseteq \overline{x}$, either by running the same argument in reverse (or saying that you could) or arguing by symmetry. – Daniel McLaury Oct 28 '16 at 05:01

1 Answers1

2

No, this proof doesn't really make sense.

I'm not entirely clear on the definitions you're using, but let's take some usual ones:

  • We say that $x \equiv_m y$ if there is some integer $k$ for which $x = y + m k$.
  • We write $\overline{x}$ for the equivalence class of $x$ under the relation $\equiv_m$, i.e. $\overline{x} = \{ x' \; | \; x' \equiv_m x\}$.

You need to assume that $x \equiv_m y$, i.e. that $x = y + m k$ for some $k$, and show that $\overline{x} = \overline{y}$, i.e. that if $z \equiv_m x$ then $z \equiv_m y$. (This amounts to showing that $\equiv_m$ is a transitive relation.)

Daniel McLaury
  • 24,656