How to know this statement with classes & modulo is incorrect?

50 Views Asked by At

Suppose we try to define $\le$ on $\Bbb Z_m$ by saying that for $\hat x, \hat y \in \Bbb Z_m$, $\hat x \le \hat y$ if $x \le y$. What is wrong with this definition?

I am not too sure if I should show this by picking two values for $x$ and $y$ and finding an example.

2

There are 2 best solutions below

6
On BEST ANSWER

Think of $\hat 0, \hat 1 \in \Bbb Z_3$. You might say that $\hat 0 \le \hat 1$ because $0 \le 1$. On the other hand, $\hat 0 = \hat 3$, so we would also have $\hat 3 = \hat 0 \le \hat 1$. But wait, this would imply that $3 \le 1$! Do you get it now?

8
On

Whether the definition works or not depends on what you mean by $\hat x, \hat y \in \mathbb Z_m$. Taking $\mathbb Z_3$ as an example, we only need three equivalence classes and we really only need three names for them, so our definition of $\mathbb Z_3$ could say $\hat x$ is defined only for $0 \leq x < 3$, and $\mathbb Z_3 = \{ \hat 0, \hat 1, \hat 2 \}$.

If that's how $\mathbb Z_3$ is defined then for $\hat x, \hat y \in \mathbb Z_m$, we already know that $0 \leq x < 3$ and $0 \leq y < 3$, and we will not cause any contradictions by saying that $\hat x \leq \hat y$ if $x \leq y$.

On the other hand, if the definition of $\mathbb Z_3$ says that $\hat 3$ is another name for $\hat 0$, then your definition of $\leq$ does not work. (And yes, the way to show it does not work is to give an example with specific numbers that shows a contradiction.)

So you really should make sure that whatever you're doing is in agreement with the definition of $\mathbb Z_3$ that you happen to be using in your particular context. If it's an exercise for a university course, the textbook or course notes should have given a definition of $\mathbb Z_3$ already and that's the definition to use in that context, not the definition you get from some random person on the internet or even from another textbook.