Let 8Z be the set of all integers that are multiples of 8. Prove that 8Z has the same cardinality as 3Z, the set of all integers multiples of 3.

$8\mathbb{Z}=\{8x\ |\ x\in\mathbb{Z}\}$ and $3\mathbb{Z}=\{3x\ |\ x\in\mathbb{Z}\}$

We need to define a bijective map from $8\mathbb{Z}$ to $3\mathbb{Z}$ . If there exists such map, then $8\mathbb{Z}$ and $3\mathbb{Z}$ have the same cardinality.

Let us define f:\ 8\mathbb{Z}\rightarrow 3\mathbb{Z},\ $f(8x)=3x$ where $x\in \mathbb{Z}.$

1) $f$ is one to one:

If $f(8x_1)=f(8x_2)$ , then $3x_1=3x_2$ . This implies that $x_1=x_2.$

2) $f$ is onto:

If $y\in 3\mathbb{Z}$ , then $y=3z$ . We need to find $x\in8\mathbb{Z}$ such that $f(x)=y.$

$f(x)=f(8w)=3w$ and $f(x)=y=3z$ .

It means that $w=z$ .

So, $x/8=y/3$ .

Therefore, for all $y\in 3\mathbb{Z}$ there exists $x=8y/3\in8\mathbb{Z}$ such that $f(x)=y.$

Hence, $8\mathbb{Z}$ has the same cardinality as $3\mathbb{Z}.$