This problem is from Discrete Mathematics and its applications.
Determine whether each of these sets is countable or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set.
$\quad 4a)\;\;$ integers not divisible by 3
The example problem that the author gave is the following.
Solution: To show that the set of odd positive integers is countable, we will exhibit a one-to-one correspondence between this set and the set of positive integers. Consider the function $f(n)=2n-1$ from $\mathbb{Z}^+$ to the set of odd positive integers.
We show that $f$ is a one-one correspondence by showing that it is both one-one and onto. To see that it is one-one, suppose $f(n)=f(m).$ Then $2n-1=2m-1$, and so $n=m$.
To see that $f$ is onto, suppose $t$ is an odd positive integer. Then $t$ is $1$ less than an even integer $2k$, where $k$ is a natural number. Hence $t=2k-1=f(k)$.
For $4a)$, I immediately recognized this set is countable and infinite because you could start listing them out $\{1,2, 5, 7, \dots\}$, and it keeps going on and on, because the set of integers is infinite.
From the example, the author used a function to map the positive counts $(1,2,3,\dots)$ to the set he was testing against (positive odds) with a simple function $f(n) = 2n – 1.$ Having this simple function made it easy for the author to prove one to one (injective). That is if $f(n) = f(m)$, $2n-1 = 2m – 1,$ and so with algebra, $n = m.$
Is there a similar function I could write for my problem as well, to make proving the one-to-one property easier?
Best Answer
It will be easier to show to injections. Let $A$ denote the set of integers not divisible by $3$: $A= \{n \in \mathbb Z: 3 \nmid n\}$. Then $f \colon \mathbb Z \to A$ defined by $f(n) = 3n+1$ is injective, which implies $|\mathbb Z| \le |A|$. On the other hand the function $g \colon A \to \mathbb Z$ defined by $g(n) = n$ is injective too, so $|\mathbb Z| \ge |A|$. Combining these two results and Cantor-Bernstein theorem we get $|A| = |\mathbb Z|$.
[EDIT]: One can actually write the bijection explicitly, $h \colon \mathbb N \to A^+$, where $r_2$ denotes the remainder from division by two. Even simplier function would be $i(n) = 2n-1 - \lfloor n/2 \rfloor$.
$$h(n) = n+1 - r_2(n) + (n + r_2(n))/2$$