Prove that the set of all even integers is denumerable

  • #1
912
19
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##
 

Answers and Replies

  • #2
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
19,379
10,869
Homework Statement:: Prove that set of all even integers is denumerable
Homework 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##

Yes. Looks fine.
 
  • #3
912
19
Thanks PeroK
 

Related Threads on Prove that the set of all even integers is denumerable

Replies
16
Views
4K
Replies
21
Views
17K
Replies
2
Views
2K
Replies
2
Views
1K
Replies
1
Views
4K
Replies
2
Views
5K
Replies
16
Views
3K
Replies
3
Views
1K
Top