A denumerable (or countable) set is one for which there is a correspondence from the set to N, the set of natural numbers. To put it in another way: the cardinality of the set is equal to that of the natural numbers. Every infinite subset S of the natural numbers is countable since the function that takes the least element in S to 1 and the next to least element to 2 and the next to 3 and so on, is a correspondence. This also shows that no infinite set can be "smaller" than the natural numbers. Moreover any infinite set that can be put into correspondence with a denumerable set is denumerable. Hence the integers are denumerable since the function that takes x to 2*X2 + x + 1 is a correspondence from the integers to a subset of the natural numbers. Also if X and Y are denumerable sets then the set XxY of all ordered pairs (x, y) where x is in X and y is in Y is a denumerable set. To prove this, notice that since both X and Y are denumerable, it suffices to prove that NxN is denumerable. The function which takes (x, y) in NxN to x*(x-1)/2 + y is a one-to-one correspondence. Another way to show the NxN is denumerable is to write out the elements of NxN in sequence like so:
(1,1) (1,2) (1,3)...
(2,1) (2,2) (2,3)...
(3,1) (3,2) (3,3)...
and so on. Then draw a zigzagging line which starts at (1,1) and proceeds across successive diagonals so that the sequence of elements it crosses is (1,1), (1,2), (2,2), (3,1), (2,2), (1,3), (1,4), etc. Then the function which maps 1 to the first element in the sequence just given and 2 to the next element and so on, is a correspondence from N to NxN. Any fraction, such as p/q, expressed in lowest terms, can be identified with the ordered pair (p, q). From this identification, the rational numbers are a subset of ZxNwhere Zstands for the set of integers. Since both Z and N are denumerable, so is the set of rationals.
A root of a polynomial P is a number n such that P(n) = 0. If the coefficients of P are rational numbers, then n is called an algebraic number. The set of algebraic numbers is denumerable. To see this, notice that a denumerable union of denumerable sets is denumerable. What this means is that if we have a denumerable "number" of denumerable sets then the total "number" of elements in the sets is denumerable. To prove this, notice that since each set in the union is denumerable, each can be identified with a copy of N. Then since the number of sets is also denumerable, each set can be numbered with a natural number. Therefore the union can be put into correspondence with NxN. Now given any number d, the number of polynomials of degree less than or equal to d with rational coefficients can be put into correspondence with Qd (where Q denotes the rational numbers) since each polynomials can be identified with the ordered set of its coefficients. The union of all such polynomials is therefore denumerable. Since each polynomial has a finite number of roots, the algebraic numbers are countable.
This is the complete article, containing 542 words
(approx. 2 pages at 300 words per page).
