Countably_infinite

Reference mathematics

Something is countably infinite if a one to one mapping

can be made between it and the natural numbers or a subset of the natural numbers.

For example, positive even numbers are countably infinite

as displayed by the mapping:

*2 maps to 1

*4 maps to 2

*6 maps to 3

*...

*N maps to (N/2) where N is a positive even number

Sometimes it is necessary to use more than one mapping.

This is where you map the set you want to show as countably infinite to another set. You then map this other set to the natural numbers.

For example, rational numbers can be mapped:

A rational number is of the form

N / D

where N and D are integers and D cannot be zero.

First, we want to map N to positive integers and

map D to negative integers.

• map N to the positive integers by:
• if N > 0, map N to (2*N)
• if N < 0, map N to (1 + -2*N)
• if N = 0, map N to 0

• map D to the negative integers by:
• if D > 0, map D to (-2*N)
• if D < 0, map D to (1 + 2*N)

Now we've mapped the rational numbers to the set of all

integers.

Second, we will map the set of all integers to the

set of positive integers:

• map 0 to 1
• map 1 to 2
• map 2 to 4
• map 3 to 6
• ...
• map X to (2*X) where X > 0 and X is an integer

• map -1 to 3
• map -2 to 5
• map -3 to 7
• ...
• map Y to (-2*Y + 1) where Y < 0 and Y is an integer