# discrete problem, counting with functions

• Nov 12th 2012, 10:16 AM
gbux512
discrete problem, counting with functions
So I have this problem to prove, and I can only satisfy it the first way, I can not bring it back the other way.
1. Find a one-to-one correspondence between the set of even integers and the set of all integers. Explain how this shows us that there are the same number of even integers as there are odd integers! Thus, we are showing that ∞ + ∞ = ∞, and thus ∞ does not behave the same as a real number. (Hint: try using the definition of an even number to find a 1-1 correspondence from the integers to the even integers.

I think I can prove it for even numbers to integers, saying that if 2k= an integer where k is an integer, any integer multiplied by another integer = an integer. but how to i prove that there is a 1:1 relationship from integers to even numbers? do i say that 2k= n where k is an integer and n is an even number and k= n/2? that doesnt account for all numbers though right?
• Nov 12th 2012, 10:25 AM
Plato
Re: discrete problem, counting with functions
Quote:

Originally Posted by gbux512
So I have this problem to prove, and I can only satisfy it the first way, I can not bring it back the other way.[COLOR=#000000][FONT=Verdana]
1. Find a one-to-one correspondence between the set of even integers and the set of all integers. Explain how this shows us that there are the same number of even integers as there are odd integers! Thus, we are showing that ∞ + ∞ = ∞, and thus ∞ does not behave the same as a real number. (Hint: try using the definition of an even number to find a 1-1 correspondence from the integers to the even integers.

Let $\displaystyle \mathcal{E}$ be the set of even integers.
Then define $\displaystyle f:\mathbb{Z}\to\mathcal{E}$ by $\displaystyle n\mapsto 2n$.
Show that $\displaystyle f$ is bijective.
• Nov 12th 2012, 01:19 PM
HallsofIvy
Re: discrete problem, counting with functions
Plato gives a function from the set of all even integers which, since this is bijective, is the same as saying it has an inverse function which is the bijective function form the set of even integers to the set of integers that you are looking for.

Yes, any even integer is of the form 2k and can be mapped to k. If we call "2k" n, then f(2k)= k is f(n)= n/2 which is an integer because n is even. To show that it is "surjective", given any integer k, show, as you have, that f(2k)= k. To show that it is "injective" supose we have two even integers n and m such that f(n)= n/2= m/2= f(m). Now show that n= m.