Answer to Question #284209 in Discrete Mathematics for wajji

Question

 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. 

Answer 1

$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}.$