Mathematics term often used when investigating sets.

If a set has a one-to-one correspondence to the natural numbers, than that set is called countable.

Denumerable means much the same as countable. Some authors use one of the terms to include finite collections, reserving the other for infinite (but countable / denumerable) collections.

The above writeups, that define a set to be countable if it has a one to one correspondence with the naturals (or a subset of it) are of course correct, but aren't terribly helpful to the layman. For once Webster provides more insight than you might think.

Counting

If I were to ask you to count the socks in a draw you will go through them in some order, counting "one", "two", "three" etc... (or the equivalent in the language of your choice) Subconsciously, you are doing 2 things:

  • You are picking a first element.
  • For each element, you define a next element.
Both of these 2 things can be completely arbitrary. It doesn't matter which sock you count first or which order you count them in, what matters is that you can do this.

From counting to countable

If you read some of the excellent writeups in natural number you will find that this is how one can define the natural numbers. Briefly there is a first natural number, and each natural number has a successor, i.e. a natural number that is after it, and this defines the natural numbers.

It should be trivial that any finite set is countable: you could just put each element of the set on the floor and point your finger at them each in turn (given a big enough floor of course). Technically you have just defined a bijection between your set and a subset of the naturals (for example {1,2,..,n}, where n is the number of elements in the set).

Infinite sets can also be countable, it's just that you will never finish the counting. If you start counting the natural numbers, you will keep on going for ever, but it's a perfectly well defined thing to do. Saying that an infinite set is countable is basically saying that it is like the natural numbers, that it has the same number of elements as the natural numbers. When dealing with infinite sets, the way to define the property of "having the same number of elements" is to look for a bijection (one to one correspondance) between the two sets. In our particular case it means that we want to be able to take an element of our set and put it together with 1, and then find the next element which we'll associate with 2 and so on. You must of course be careful not to miss out any elements of the set.

There are sets that are uncountable. An example would be the the real line. At first you might think that this is because of all the fractions or numbers like √2, but in fact the bulk of the real numbers are the transcendental numbers, which are rather harder to pin down.(a proof of the uncountability of the reals is here).

Examples of countable sets:

  • The integers: one can use the ordering 0,1,-1,2,-2,... a bijection would be f(n)=(-1)nfloor(n/2), where floor is the function that gives you the greatest integer smaller than its argument (so floor(2)=2, floor(1.5)=1).
  • The odd, positive integers: take f(n) to be 2n-1
  • The rationals: a complete proof is here
  • The algebraics: this is the set of roots of polynomial equations with integer coefficients (or equivalently rational coefficients). For example √2 is an algebraic number as it is a solution of the equation x2=2. Proving this by explicitly finding a bijection is rather more difficult.
This can be counterintuitive, as one might expect that the set of odd naturals would be smaller than the naturals or that the set of rationals or algebraics would be bigger.

A useful theorem

The following theorem, due to Cantor, is useful for proving that a set is countable: A countable union of countable sets is finite. One could use this to prove that the algebraics are countable:

  • Define the height of a polynomial to be the sum of the absolute values of its coefficients and its degree. It should be immediate that there are finitely many polynomials of a given height.
  • A polynomial of degree n has at most n roots, so the set of roots of polynomials of given height is also finite.
  • The height of a polynomial is an natural number, so we have split the algebraics into finite sets, of which there are countably many. So the set of algebraics is a countable union of countable sets, and so is countable.

Thanks to krimson for some most helpful comments.

Count"a*ble (-?-b'l), a.

Capable of being numbered.

 

© Webster 1913.

In mathematical logic, a set is enumerable if it is possible to list its members in such a way that every member appears on the list somewhere. Such a list is called an enumeration of the set. Thus, the set of Teenage Mutant Ninja Turtles is enumerable, because I can enumerate them in the following way:

Leonardo, Donatello, Raphael, Michaelangelo.

Repetition and order do not matter, so long as each and every member of the set appears on the list at at least once. Thus, the following is another perfectly good enumeration of the TMNT:

Donatello, Raphael, Michaelangelo, Raphael, Leonardo, Raphael.

More accurately, a set is enumerable if there's a way to arrange its members into a list upon which any single member can be found at a finite position. This does not mean that sets of infinite size cannot be enumerable. For example, the following is an enumeration of the positive integers:

1, 2, 3, 4, 5...

However, the following is NOT an enumeration of the positive integers:

1, 3, 5, 7, 9...{insert infinity of odd integers here}...2, 4, 6, 8...

The difference is that the location of any even integer on the second list is NOT finite; they are all located at infinity. On the first list, however, each and every number has a finite location on the list -- namely, itself. Another example:

0, 1, -1, 2, -2, 3, -3, 4...

The above is a perfectly good enumeration of the set of all integers. The following, however, is not:

0, 1, 2, 3, 4...{insert all the positive integers here}...-1, -2, -3...

Just because such an arrangement is possible does not mean that the set of all integers is not enumerable. So long as a good enumeration of a set can be created, the set is considered to be enumerable. Sets like the set of all integers or the set of all positive integers that are both infinite and enumerable are called enumerably infinite sets.

Finally, two sets are considered to be equinumerous, or the same size, when a one-to-one correspondence can be set up between the sets. For example, the set of Teenage Mutant Ninja Turtles and the set of living members of the Incandenza family in Infinite Jest are equinumerous, as is demonstrated below:
Leonardo ↔ Avril Incandenza
Donatello ↔ Hal Incandenza
Michaelangelo ↔ Orin Incandenza
Raphael ↔ Mario Incandenza
We can now redefine an enumerable set as one that is equinumerous with some subset of the positive integers. It is for this reason that an enumerable set is sometimes called a countable set. (Similarly, "enumerably infinite" and "countably infinite" mean the same thing.)

Now, why is any of this important? Mostly because it's requisite knowledge for most of the biggest mindfucks in mathematics, logic, and metalogic, including diagonalization, Cantor's Theorem, Gödel's first incompleteness theorem, and the halting problem. Here's a small taste of the sort of thing I'm talking about:

Say that you own a hotel with an infinity of rooms; specifically, your rooms are numbered with positive integers, starting at 1 and going off into infinity. Not only that, but your hotel’s very popular, and every room is occupied. Despite this fact, you still have the “Vacancy” sign lit outside the hotel. Why? Simple. Say that a lone traveller comes to your lobby and asks for a room. You can give him one. All you have to do is call up the person in room #1 and tell her, “Hey, move over to room #2, and tell the guy in there to move over to the next room, and pass it on.” Room #1 opens up, and you send your new guest into that room. Your hotel is still full, and yet you have one more guest. Nonetheless, this works -- you can set up a correspondence between the old room numbers of the guests and the new ones as follows:
1 ↔ 2
2 ↔ 3
3 ↔ 4
4 ↔ 5
etc.

So from this we can conclude that infinity + 1 = infinity. But there’s more. Say that an enumerably infinite convention of Everythingians now shows up at your hotel. You have more than enough room for them as well. Simply address the hotel on your PA system and tell everyone to move to the room that is double the number of the one that they are now in. Your odd-numbered rooms are now empty, and since there’s an enumerable infinity (a.k.a. countable infinity) of odd numbers, you can simply send the Everythingians to the odd-numbered rooms and there will be enough rooms for everybody. Once again, this works because you can set up a correspondence between the old room numbers and the new ones:
1 ↔ 2
2 ↔ 4
3 ↔ 6
4 ↔ 8
etc.

So infinity + infinity = infinity (for countable infinity, at least), or in other words there are just as many even integers as there are integers . Nifty, no? There’s far more where that came from, and most of it is even stranger. For example, despite the fact that enumerably infinite sets exist, some sets are NOT enumerable. Of course, that's for another node.

NB: Philosophers of language may have a problem with the way I'm playing fast and loose with the use-mention distinction. I'm aware of the problem, but it's a technicality that isn't really related to the heart of what I'm talking about here, and use/mention issues would only muddy the waters further. I'm also well aware that some of the statements above should really say things like "aleph-null + 1 = aleph-null", but I am attempting to keep things as simple as possible.

Also, just to clarify: "enumerable" is the same as "denumerable" is the same as "countable." "Nonenumerable" (the opposite of enumerable) is the same as "uncountable."

Log in or registerto write something here or to contact authors.