Give a complete set of equivalence class representatives for an equivalence relation on the natural numbers (including zero)

536 Views Asked by At

The full question:

Having an equivalence relation $\sim$ on $\Bbb N$ defined by: $a \sim b$ meaning $a,b\in\Bbb N$ such that $a=b*10^k,$ for some $k\in\Bbb Z$, give a complete set of equivalence class representatives.

I am having trouble visualising these. I'm thinking you would need the whole set $\Bbb Z$. Does anyone have any ideas?

Help would be greatly appreciated! (this is my first post as well, so please say if anything is unclear)

2

There are 2 best solutions below

0
On BEST ANSWER

The numbers that are not multiples of $10$ give us a complete set of representatives, and in fact we have exactly one representative for each class. Let $X$ be the set of all positive numbers not divisible by $10$

To see why it is a complete set of representatives take $n\in\mathbb N$, suppose $10^k$ is the largest power of $10$ dividing $n$ ($k$ might be $0$), notice $n\equiv \frac{n}{10}\equiv\dots\equiv \frac{n}{10^k}\in X$.

To see why it does not contain two elements in the same class notice if $a\equiv b$ then one of $a$ and $b$ is a multiple of $10$.


Edit: I assume $\mathbb N$ does not contain $0$, if we want $0\in\mathbb N$ just notice $0$ would be in a class by itself.

3
On

Here's another answer that may be easier to "visualize". Your equivalence relation says that $a$ and $b$ are equivalent if you can get $a$ by appending zeroes to $b$ or deleting them from the end of $b$. That's the same as saying $a$ and $b$ start with the same sequence of digits before the trailing zeroes (if any) begin). Then the integers with no trailing zeroes represent each class just once.

Since $0$ is in a class by itself, it's the representative of its class.

Those are exactly the numbers in @dREaM 's correct answer.