Countable SetYou are currentlybrowsing as guest. Click here to log in 

Since counting is the act of assigning a natural number to each item, Georg Cantor defined a set as countably infinite if it can be put in oneone correspondence with the natural numbers.
Using this definition, trivially the natural numbers themselves are countably infinite, but so are the even numbers, the integers and the square numbers.
Form an (infinite) grid like this. Only the first six rows and columns are shown.
1/1  1/2  1/3  1/4  1/5  1/6  ... 
2/1  2/2  2/3  2/4  2/5  2/6  
3/1  3/2  3/3  3/4  3/5  3/6  
4/1  4/2  4/3  4/4  4/5  4/6  
5/1  5/2  5/3  5/4  5/5  5/6  
6/1  6/2  6/3  6/4  6/5  6/6  
etc 
We want to show that these can be put into onetoone correspondence with the natural numbers, and there are two easy ways to think about this.
Zigzag back and forth through the above table:

List all those whose numerator and denominator add to two, then to three, then to four, etc, like this:

Each of these two ways will form a list of all the rational numbers. Therefore there exists a onetoone correspondence with the natural numbers. So the rational numbers are countably infinite.
The size of countable sets is given the transfinite number $\aleph_0$ (pronounced "aleph null") (see transfinite numbers)
Are all sets countable? (see Uncountable sets)
Last change to this page Full Page history Links to this page 
Edit this page (with sufficient authority) Change password 
Recent changes All pages Search 