Prove that the set of all even integers is denumerable

In summary, we need to prove that the set of even integers is denumerable, which means we need to show that there exists a bijection between the set of positive integers and the set of even integers. This is done by defining the function f(x) as x-1 for odd numbers and -x for even numbers. This function is both one-to-one and onto, proving that the sets are equivalent.
  • #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##
 
Physics news on Phys.org
  • #2
IssacNewton said:
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
Thanks PeroK
 

1. What is the definition of a denumerable set?

A denumerable set is a set that can be put into a one-to-one correspondence with the set of natural numbers (1, 2, 3, ...). This means that each element in the set can be counted and assigned a unique natural number.

2. How can we prove that the set of all even integers is denumerable?

To prove that a set is denumerable, we must show that there exists a function that maps each element in the set to a unique natural number. In the case of the set of even integers, we can use the function f(n) = 2n, where n is a natural number. This function maps each even integer to a unique natural number, proving that the set is denumerable.

3. Is there a difference between a countable and denumerable set?

No, countable and denumerable are interchangeable terms and both mean that a set can be put into a one-to-one correspondence with the set of natural numbers.

4. Can a set be both denumerable and uncountable?

No, a set cannot be both denumerable and uncountable. A set is either denumerable, meaning it can be put into a one-to-one correspondence with the set of natural numbers, or uncountable, meaning it cannot be put into a one-to-one correspondence with the set of natural numbers.

5. Can we use the same function to prove that the set of odd integers is denumerable?

Yes, we can use the same function f(n) = 2n to prove that the set of odd integers is denumerable. This function maps each odd integer to a unique natural number, proving that the set is denumerable.

Suggested for: Prove that the set of all even integers is denumerable

Back
Top