Set theory question: infinite alphabetized list?

[Packbat]

I was just lying down to sleep when this occurred to me, and I wanted to get it out of my head so that someone with some knowledge could give me the standard response:

Consider the set generated as follows: (A, B, C, ..., Y, Z, AA, AB, ..., AZ, BA, ...)

Now, clearly every finite string of capital letters must appear on this list. In fact, given any such string (e.g. CML), one can write the natural number corresponding to its appearance on the list (3*26^2+13*26+12=2378). My question is: what if you reordered the list so that every entry appeared in alphabetical order - ABC before DEF, QED before QER, LMN before LMNO, etcetera? In this reordered list, one will immediately see that every finite-numbered item is a string of that many As. So what happened to the rest of the strings?

[Razaekel]

This, to me, sounds similar to the explanation of different infinities for Real numbers and Integers. For example, if we were to make infinite decimal sequences for each integer, i.e. 1 is 0.1111..., 2 is 0.222..., 12 is 0.121212..., 42 is 0.424242..., etc. Now, if you add a new decimal sequence that doesn't follow this pattern, i.e. change the first digit of of the 1 decimal sequence to any other decimal, for example 5. Now you have a larger infinity than with the integers alone. That's what your post made me think of.

[Kuroneko]

Nothing happened to the strings except you redefining their order such that it's impossible to list them while respecting their new order. There's still countable many strings. None of them went away. (My knee-jerk reaction was to use ordinals, but your dictionary is not well-ordered, since, e.g., arbitrarily long AA...AB precedes AB. Thus you can have sets of strings with no least member.)

As another example, think of the ways in which the rationals can be proved to be equinumerous to the naturals. Take a bijection f:Q→N, and define an order on the naturals by a≺b iff f-1(a)<f-1(b) as rationals. Then you have a set of natural numbers with their order completely messed up in such a way that you can't list them while preserving the new order ≺. But nothing happened to the naturals themselves.

[Darth Holbytlan]

What you're doing is conflating the concept of a bijective sequence with an ordered, countable set.

The former is a mapping from the natural numbers {1,2,3...} to your set such that each element appears exactly once. (The fact that each element appears exactly once is what makes it bijective.)

An ordered set is just the set, which is inherently unordered, together with an ordering relation to tell which of any two members is bigger than the other. A countable set is a set where a mapping exists between it and the natural numbers such that each element appears exactly once.


What you did is define a sequence f(n) = Sn : S1 = A, S2 = B, ... , S2378 = CML, etc.

This defines the set of elements {A,B,C,...,AA,AB,...}. Because the sequence is bijective, the inverse mapping f-1 exists and is also a bijection, mapping each element in the set to a distinct natural number. So, f-1(A) = 1, f-1(B) = 2, ... , f-1(CML) = 2378, ...

This defines an order on the set, ≺, where a ≺ b iff f-1(a) < f-1(b). e.g. A ≺ C, since f-1(A) = 1 < 3 = f-1(C).

Also, since the sequence is a mapping between your set and the natural numbers, the set is countable.

When you ask what happens when you reorder the list, it can be looked at in two ways: Either you want to reorder the set, meaning define a different ordering relation on the set—in this case, the canonical order, <—or you want to reorder the sequence, making a new bijective sequence that preserves the new order of the set. But, as you figured out, such a sequence does not exist.

This is not a problem, however. The new order is still perfectly usable, and the set is still countable since countability is not related to order and the first sequence still works as a mapping between your set and the natural numbers. It's just that this ordering cannot be defined using a sequence like the original ordering was.


@Razaekel: This is not actually similar to proving that the real numbers are a bigger infinity than the integers. Packbat's set is countable, and therefore not bigger than the integers. Proving that the real numbers are bigger requires showing that there is no mapping between it and a countable set, not just that you have a mapping that doesn't work. The problem with your proof is that you can add extra elements to a countable set and still get a countable set. In fact, you can add a countable number of countable sets of elements to a countable set and still get a countable set.

If you look closely at your example, you'll see that every decimal sequence you define is a rational number, including the extra decimal sequence you add. (0.1111... = 1/9, 0.222... = 2/9, 0.121212... = 12/99 = 4/33, 0.424242... = 42/99 = 14/33. 0.51111... = 23/45.) If your proof worked, it would mean that the rational numbers are bigger than the integers, when they actually aren't.

[Packbat]

Thanks, Darth Holbytlan! That explains it about perfectly - the new ordering of the set no longer doubles as a bijection to the natural numbers, but since the new ordered set contains the same elements as the original ordered set, it is also countable.