Countable
   

   

 Math Help -> Counting and Combinations -> Countable 

"Counting" may seem like a simple topic, but there's more to it than you might think.

Countable

In this topic, we'll consider whether a set can be counted.  That means whether it can be put in one-to-one correspondence with the "counting numbers".  The counting numbers are the positive integers, which I will denote N.  By definition, N = {1, 2, 3, ...}.  (Note: some authors include zero in the "natural" numbers, but I do not.)  Although N is an infinite set, it is considered "countable" because if you start at the beginning, and keep counting, each element will eventually be counted, even though it will never be the case that all elements will be counted.

"One-to-one correspondence" of set A with set B means there is a function, f, whose domain is A and whose range is B.  This function maps each element of A to a single element of B.  If set A is in one-to-one correspondence with set B and set B is countable, then set A is countable, too.

Adding a finite number of elements to a countable set results in another countable set.  So the set of nonnegative integers, {0, 1, 2, 3, ...} is countable.  If a set can be put in one-to-one correspondence with any countable set, then both sets are countable.

The set of integers is countable.  To show that, you put the set in one-to-one correspondence with the natural numbers this way:

Z N
0 1
1 2
-1 3
2 4
-2 5
3 6
-3 7

It may surprise you to learn that the set of ordered pairs of integers, Z2, is countable, too.  Click here to see the one-to-one correspondence.

That means the set of rationals, Q = {p/q | p is an integer, and q is a nonzero integer} is also countable.  You can show this by putting Q = {p/q} in one-to-one correspondence with Z2 = {(p,q)}

Related Pages in this Website

The Peano Postulates -- Proving the properties of natural numbers using the Peano Postulates, which have been formulated so that zero is not included in the set of natural numbers.  (There's quite a debate about this point.)

Is Zero a Natural Number? -- a discussion of the fact that some authors include zero, and others do not.

Construction -- Construction of sets of numbers, starting with the original Peano Axioms, formulated so that zero is included in the set of natural numbers.

Set Theory -- an introduction to sets, including examples of some standard sets.

Counting Ordered Pairs of Integers -- An explanation of the "square spiral" that puts the set of natural numbers in one-to-one correspondence with the set of rational numbers.

 

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]