$ \mathbb{N} \sim \{ n \in \mathbb{N} : ~~ 10 \nmid n \} $

62 Views Asked by At

I'm trying to create a bijection from $ \mathbb{N} $ to the set of natural numbers without numbers divisible by 10, meaning the set $ \{ n \in \mathbb{N} | \forall m \in \mathbb{N}. n \neq 10 \cdot m \} $. This is to show they have the same cardinality ( I can't use CSBT ).

Attempt 1: My Idea is to create a bijection such as $ f(1) = 1, ... , f(9)=9 , f(10)=11,...,f(19)=19,f(20) = 21,... $
so, naively, I wrote $ f(n)= \begin{cases} n+1, & \text{if } \exists m \in \mathbb{N}. n=10\cdot m\\ n & \text{else} \end{cases} $
However, this choice is false because it is not injective ( since $ f(11) = f(10) = 11 $ ).

Attempt 2: Define $ a_1 = 1 , a_2 = 2,..., a_9 = 9 $. Define by recursion the sequence $ a_n = a_{n-9} + 10 ,~~\forall n>9 $. The fact that I've created a sequence implies a bijection to $ \mathbb{N} .$

Attempt 2 works, but initially I wanted to give a specific bijection as I tried to do in attempt 1, do you please have any suggestions to such an explicit bijection?
Thanks in advance!

1

There are 1 best solutions below

0
On BEST ANSWER

If attempt $2$ works then you can rewrite it this way for $n$ not divisible by $9$:

$$f(n) = 10\left\lfloor\dfrac{n}{9}\right\rfloor + n \; \mathrm{mod} \; 9$$

else:

$$f(n) = 10\left\lfloor\dfrac{n}{9}\right\rfloor -1 $$