Countably infinite set: odd integers

[k3k3]

Homework Statement

Using the definitions, prove that the set of odd integers is countably infinite.

Homework Equations

Definition: The set A is countably infinite if its elements can be put in a 1-1 correspondence with the set of positive integers.

The Attempt at a Solution

I am trying to think of a function that maps the positive integers into the odd integers.

The function I am coming up with is piecewise defined.
I am unsure how to type it, but...
f(n) =
n-2 when n is odd and n>2
-n-1 when n is even
-n when n=1

Testing some values, I got this
f(1)=-1
f(2)=-3
f(3)=1
f(4)=-5
f(5)=3

It looks like this works, but I am unsure how to show a piecewise defined function is 1-1 and onto. I think I am missing something.

 

[alanlu]

You're fine. Actually, you can define the same function in two pieces: n - 2 for odd n and -n - 1 for even n. Furthermore, n for odd n and -n + 1 for even n works as well.

Same way you should show 1-1 and onto for any other function. Show f(n) = f(m) implies n = m. Then show for every odd integer i, there is a natural number n such that f(n) = i.

 

[k3k3]

Thank you for the response!

Running with your suggestion, showing onto is simply stating that:

Let m be an element of the odd integers.

If n is odd, since the sum of an odd and even is odd, then n+(-2)=m for all odd n in the positive integers.

If n is even, since an odd number is defined by 2x-1 for all x in Z, where n=2x, then -n-1=m for all even n in the positive integers.

Is this a satisfactory proof of why f(n) is onto?

 

[alanlu]

I'm not convinced. It doesn't say why m must equal f(n) for some n, but just that it could.

Consider using n for odd n and -n + 1 for even n as your f. It will lead to a simpler proof.

A strategy for examining piecewise functions can be to look at the pieces of the domain where the function is defined separately. For odd n, where does f map n? What about for even n? Is m guaranteed to achieve either of these types of values, and if so, why?

 

[k3k3]

How is this:
Let m be an element in the set of odd integers.

If n is even, then there is a m such that f(n)=m.

Since m is an odd integer, then there exists an element -m+1=n.

Then f(-m+1)=-(-m+1)+1=m

If n is odd, then m=n for all odd n in the set of positive integers.

 

[alanlu]

Yep you showed that f is onto correctly.

Can you show that f is 1-1, or that f(m)=f(n) implies m=n?

 

[k3k3]

I think so.

Assume f(m)=f(n)

If n is even, then
-n+1=-m+1
-n=-m
n=m

If n is odd, then
n=m

 

[alanlu]

How do you know that m is even when n is even? Likewise, how do you know m is odd when n is odd?

 

[k3k3]

I am still assuming that f(n) is piecewise defined. When n is even, f(n)=-n+1 and when n is odd, then f(n)=n

Showing that f(n)=f(m) for both functions is not enough?

 

[SammyS]

Homework Statement

Using the definitions, prove that the set of odd integers is countably infinite.

Homework Equations

Definition: The set A is countably infinite if its elements can be put in a 1-1 correspondence with the set of positive integers.

The Attempt at a Solution

I am trying to think of a function that maps the positive integers into the odd integers.

The function I am coming up with is piecewise defined.
I am unsure how to type it, but...
f(n) =
n-2 when n is odd and n>2
-n-1 when n is even
-n when n=1

Testing some values, I got this
f(1)=-1
f(2)=-3
f(3)=1
f(4)=-5
f(5)=3

It looks like this works, but I am unsure how to show a piecewise defined function is 1-1 and onto. I think I am missing something.

Your function will work just fine, but it's a little complicated.

Consider a function, g(k), going from the odd integers to the positive integers.

You already have f(n) = -n, for n=1, i.e. f(1) = -1. So g(-1)=1, i.e. g(k)=-k, when k=-1. Why not define g(k) = -k for all the negative odd integers. Where would you then map the positive odd integers?