Countably infinite set: odd integers

  • Thread starter k3k3
  • Start date
  • #1
78
0

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.
 

Answers and Replies

  • #2
65
0
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.
 
  • #3
78
0
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?
 
  • #4
65
0
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?
 
  • #5
78
0
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.
 
  • #6
65
0
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?
 
  • #7
78
0
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
 
  • #8
65
0
How do you know that m is even when n is even? Likewise, how do you know m is odd when n is odd?
 
  • #9
78
0
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?
 
  • #10
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,348
1,022

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?
 

Related Threads on Countably infinite set: odd integers

Replies
1
Views
2K
  • Last Post
2
Replies
29
Views
8K
  • Last Post
Replies
3
Views
2K
Replies
3
Views
10K
Replies
3
Views
3K
Replies
6
Views
8K
Replies
11
Views
3K
Replies
6
Views
2K
  • Last Post
Replies
3
Views
1K
Top