- #1

- 996

- 29

- Homework Statement
- Prove that set of all even integers is denumerable

- Relevant Equations
- A set ##A## is called denumerable if ## \mathbb{Z}^+ \sim A##

Now, set of even integers is ## A = \{ \cdots, -4, -2, 0, 2, 4, \cdots \} ##. We need to prove that ## \mathbb{Z}^+ \thicksim A##. Which means that, we need to come up with a bijection from ##\mathbb{Z}^+## to ##A##. We know that ##\mathbb{Z}^+ = \{1,2,3,\cdots \} ##. I define the function ##f : \mathbb{Z}^+ \longrightarrow A ## as follows.

$$ f(x) =

\begin{cases}

x-1 & \text{if } x \text{ odd} \\

-x & \text{if } x \text{ even}

\end{cases}

$$

Now, we will prove this is both one-to-one and onto. Assume ## f(x_1) = f(x_2) ## for some ##x_1, x_2 \in \mathbb{Z}^+##. From the way we have defined this function, we either have ##f(x_1) \geqslant0## or ## f(x_1) < 0 ##. Consider that ##f(x_1) \geqslant0##. It also follows that ##f(x_2) \geqslant 0##. And we have ## f(x_1) = x_1 - 1 = f(x_2) = x_2 - 1##. And it follows from this that ## x_1 = x_2 ##. Other case is that ## f(x_1) < 0 ##. From this, we have ##f(x_2) < 0 ##. And using the function definition, we have, ##f(x_1) = -x_1 = f(x_2) = - x_2##. It follows that ## x_1 = x_2 ##. So, it has been proved in both cases that ##x_1 = x_2## and since ## x_1, x_2## are arbitrary to begin with, it follows that the function is one-to-one. Is this reasoning ok so far ?

##\spadesuit\spadesuit\spadesuit\spadesuit##

$$ f(x) =

\begin{cases}

x-1 & \text{if } x \text{ odd} \\

-x & \text{if } x \text{ even}

\end{cases}

$$

Now, we will prove this is both one-to-one and onto. Assume ## f(x_1) = f(x_2) ## for some ##x_1, x_2 \in \mathbb{Z}^+##. From the way we have defined this function, we either have ##f(x_1) \geqslant0## or ## f(x_1) < 0 ##. Consider that ##f(x_1) \geqslant0##. It also follows that ##f(x_2) \geqslant 0##. And we have ## f(x_1) = x_1 - 1 = f(x_2) = x_2 - 1##. And it follows from this that ## x_1 = x_2 ##. Other case is that ## f(x_1) < 0 ##. From this, we have ##f(x_2) < 0 ##. And using the function definition, we have, ##f(x_1) = -x_1 = f(x_2) = - x_2##. It follows that ## x_1 = x_2 ##. So, it has been proved in both cases that ##x_1 = x_2## and since ## x_1, x_2## are arbitrary to begin with, it follows that the function is one-to-one. Is this reasoning ok so far ?

##\spadesuit\spadesuit\spadesuit\spadesuit##