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."