Answer to Question #159644 in Discrete Mathematics for J

Question

Show that {1, 2, 3, 4, . . .} and {2, 4, 6, 8, . . .} have the same cardinality.

Hint: find a mapping and show it is 1–1 and onto.

Answer 1

Let $A=\{ 1,2,3,4..........\}$ and $B=\{ 2,4,6,8......\}$ .

Define a map,

$f:A\rightarrow B$ by $f(x)=2x$ .

Claim: $f$ is one-one and onto .

Let $f(x)=f(y)$

$\implies 2x=2y$

$\implies x=y$ ( Dividing both side by 2 )

Hence , $f$ is one - one .

Again for each $y\in B$ there exist a $\frac{y}{2}$ in $A$ ($\frac{y}{2}$ exists because $B$ is a set of even number )such that $f(\frac{y}{2})=2×\frac{y}{2}=y$

Hence $f$ is onto .

Therefore $f$ is one-one onto function.

Hence $A$ and $B$ have the same cardinality .