Thursday, December 24, 2009

Cantor's Lost Surjection (Revised)

Revision 2.0: Dec 28, 2009 -- I've made the changes suggested by Chad Groft, and boris in their excellent comments.

Before you go any further, PLEASE read this introductory paragraph fully and carefully. Over the last couple of weeks, I've been writing several posts about a very subtle problem in ZFC set theory, whose results wind through a great deal of the existing work. I may be right, I may be wrong, but I have been very careful to try to stay within the first-principles of set theory, in order to shed some illumination onto the issue. The issue is not as simple as "I am a crank", or "Cantor's proves..." or any other quick knee-jerk reaction to what I am saying. You are welcome to comment, to express your opinions, BUT only if you're read what I've written carefully, and with an open and objective mind. Only if you're not succumbing to your emotions. Mathematics is about careful, objective thought. We must never lose sight of that.

This post is NOT about:

- Reals being (un)countable
- missing irrationals in a bi-infinite spreadsheet
- missing irrational seeds in an infinite number of bi-infinite spreadsheets
- magic sequences


First, I want to talk very explicitly about a wikipedia page:

http://en.wikipedia.org/wiki/Countable_set

In particular I want to closely examine the "Definition" section. This part of the document contains exactly 13 lines (although if your window isn't wide enough some of the lines wrap). In the first four lines, we have the following two definitions:

D1: Line 1 -- a set is "countable" if an injective function exists to N
D2: Line 4 -- a set is "countably infinite" if a bijective function exists to N

Before we go any further: A "formal system", as defined in GEB by Douglas Hofstadter, contains a finite number of axioms, an infinite number of theorems, and a finite number of rules of production. A number of people have also included "definitions" as being separate and distinct pieces from the basic axioms in the system, in particular ZFC set theory differentiates between its base definitions (such as countable) and it's axioms (such as the axiom of choice).

All theorems are built on-top of the many self-evident pieces below, and other theorems.  Everything that isn't self-evident or independent is a theorem. Everything that stands on its own is an axiom or a definition.

In this way, definitions and axioms act as the basic building blocks on which all of the theorems are based. The different pieces may be interspersed with each other, but some are primitive building blocks (axioms and definitions), while the others are composite building blocks (theorems).

Rigor means the entire construction is based on a finite number of solid, self-evident pieces. Neither the axioms, the definitions, nor the theorems should contradiction each other, or be inconsistent. If that happens, there is a problem with the formal system.

Lines 1, and 4 basically specify two definitions. Together we can make the following statements about the way terminology is defined for set theory:

For all sets within set theory:
a1: "countable" is not always equal to "countably infinite"

For all functions within set theory:
a2: bijective is both injective and surjective

Getting back to the wikipedia page, in the next part:

T1: line 7 -- starts a "theorem"

This is then followed by three statements, each of which are all deemed to be equal to each other. They are:

T1-1: S is countable (injective) (f: S -> N)

T1-2: Either S is empty OR there exists a surjection (g: N -> S)

T1-3: Either S is finite OR there exists a bijection (h: N -> S)

The lines T1-1 and T1-3 basically say that for any infinite set, if it is countable, then there exists a bijection between the naturals numbers and it. So that for any infinite set:

S = { a, b, c, ... }

there is a bijection between N and itself.

PLEASE keep in mind that according to the page itself, T1 isn't an axiom or a definition, it is a theorem. The proof for the theorem isn't given in the page, it says it comes from a textbook.

By T1, the following set:

A = { a1, a2, a3, ..., b1, b2, b3, .... }

is claimed to have a bijection between it and N. The idea is that the above can be rewritten as:

B = { a1, b1, a2, b2, a3, b3, ... }

And because this is countable, there is a bijection between this set and N. If we map these two onto each other we get assignments as follows:

1 <- a1, 2 <- b1, 3 <- a2, 4 <- b2, 5 <- a3, 6 <- b3,  ...

That is, it takes the first 6 elements in N to map to the first three elements for each of the ak and bk subsets of elements. This mapping is considered to be a bijective function.

However, if we have the finite set:

D = { a1, a2, a3, b1, b2, b3 }

and another

E = { 1, 2, 3 }

Since E has less elements than D, we can only create an injective function from E to D. The size difference means that no bijective function can exist.  We only get something like:

1 <- a1, 2 <- a2, 3 <- a3

In this sense, it is accepted that in set theory, infinite sets that are countable can have a bijective function between them, even if one set appears to be somewhat "larger", with respect to infinity, then the other one. However, this does not apply to finite sets.

As a comment on my last post, delosgatos said:

"One of the cool and weird things you first encounter with infinite sets is that infinite sets are bijective with their own proper subsets."

Actually, it is far more than that. There is basically a bijective function with "any" other infinite set if that set is considered countable. If you can find an injective function, then you can claim a bijective one based on T1.

In this way set theory essentially splits all (non-empty) sets into three groups:

a) finite
b) countably infinite
c) uncountable

Finite sets differ based on size, and thus there are an infinitely large number of different possiblies. By definition there are also an infinite number of uncountable sets.

But for countably infinite sets, since there exists a bijective function between any pair of sets, they are all essentially isomorphic to the same underlying set N. A bijection can always be found.

This behavoir of the system is very different for all sets that are countably infinite then it is for finite sets.

As a consequence, the "definitions" of injective and surjective become watered down for countably infinite sets. They can still exist as function types, in that you can create an injective function, but by definition, you can also always create a bijective one between the same two sets.

Rephrased as I did earlier, we get the following relationships in the terminology:

For all countably infinite sets within set theory:
b1: "countable" is always equal to "countably infinite"

For all functions on countably infinite sets within set theory:
b2: a bijective function exists whenever there exists a function that is injective and surjective OR just injective

Under the theorem T1, as an example, we can find an f: N -> NxN  that is considered to be a bijection, for exactly this reason. Where the set NxN is:

{ {0,0}, {0,1}, {1,0}, {0,2}, {1,2}, {2,2}, {2,1}, ... }

Which is interesting, given that if NxN were finite, it would contain n^2 more elements than a finite N, if both were limited to the base elements (like 1, 2 and 3).  If f was between finite sets, then there could be no bijection, but because these are infinite sets, that is ingored.

Thus f is widely believed to be bijective, and it's underlying sets are considered countable, and countably infinite.

BUT, the above statement is only true because of the "theorem" T1, not because of the two basic definitions D1 and D2. By themselves the definitions are not strong enough to say that.

Just to be sure I figured I'd check a source other than wikipedia. The following:

http://plato.stanford.edu/entries/set-theory/primer.html

is a well-written introduction to set theory. It uses the term "one-to-one" often, but it is careful to define this in section 3 as being "injective". It avoids the word bijection.

Read through section 7, very carefully. It starts with defining countable as having the same cardinality as N, but then it says in the comments that the definition of "countable" is actually injective. Also it defines "most countable" as being finite or countable (wikipedia warned of this). 

Throughout the various theorems, "countable" keeps falling back on being one-to-one (injective). The authors carefully avoid using "bijective" through-out the entire document. 

Later in section 9, they do something really weird, they say:

"Naturally, a question arises whether perhaps all infinite sets are countable."

But then they use Cantor's diagonal argument to show that this can't be true.

Still, note that throughout this entire reference, the authors never once go back to the idea that "countable" is "bijective" for infinite sets. Countable stays as a definition which is injective.

So the wikipedia page probably isn't wrong. It accurately describes how the definition starts with countable, and because of a theorem gets to bijection for all infinite sets that are deemed to not be "uncountable".


"That's just the way ZFC set theory is ..."

Well, maybe thus is the way it is taught, but the "definitions" initially state that it is not the case. The wikipedia page clearly casts all of the blame on the unnamed theorem T1. A theorem whose proof is causing inconsistencies within set theory.

For finite and uncountable sets, there can be diffents sets within those groups where the the relationship between the sets in terms of functions is "only-injective", or "only-surjective". That is, no bijection exists or can exist. They are clearly and consistently defined.

For all of the infinite sets in the middle (between finite and uncountable), there is always a bijectiion between any two sets, no matter what. That is a fundumental inconsistency in the way the formal system treats its different mathematical objects.

It starts with pretty clear and simple definitions about how there is a difference between injective and bijective functions, but for one huge segment of the sets, those differences become negligable.Meaningless.

Just for countably infinite sets, the theorem T1 essentially "hides" any differences in the size of the sets. It is just one big giant special case, that does not match with the behavoir of the rest of set theory. With the behavoir set forth by the definitions and the axioms.

And what's going on with counting? The wikipedia page starts with a nice intuitive definition. "We can count things, one at a time, ...". But because of the T1 theorem the terminology and usage become extremely complex. Counting the elements of finite sets, is radically different than counting the elements of infinite sets.

Why?

According to the wikipedia page, the theorem T1 is proven in Lang's text. I don't have access to that proof, but from the other text I included, we can guess that the problem is probably Cantor's diagonal argument. Everything is fine in ZFC set theory when the text is talking about "countable" as just being "injective". It's a pretty simple definition.

The existance of theorem T1, however causes a strange ripple throught-out the system that effectivily treats all countably infinite sets in a special and strange way, inconsistent with the basic foundations of set theory.

That's one potential problem, but I've already shown that there are more problems lurking about. The magic sequences, for example. I provided an example of one, but because of T1, everybody believes that an infinite set that is countable automatically has a bijection to N. This means that the example can just be "bijected" away. The set:

C = { a1, a2, ..., b1, b2, ..., ... }

where the third "..." means creating elements such as c1, c2, ..., has two very different uses of "...", each of which head off to a different type of infinity.

With T1, numerous commenters have shown that this is now countably infinite, and has a bijection to N.

Thus we can pound this thing down into a sequence (even though it doesn't actually fit). This probably shows up another inconsistency because at very least I would expect C to be classed with R as being "uncountable", but it seems to fall the other way, as countably infinite.

So we have three problems now, all acting as a perfect storm with each other:

- Cantor's diagonal argument relies solely on regular sequences.
- magic sequences are believed to not exist.
- T1 allows claims a bijection between 'all' countably infinite sets.

The net result is that T1 declares that where there is any mapping that is injective there is automatically a bijective one too, whether or not it really is. This basically undoes the meaning of injective and surjective for all functions on infinite sets (except those that are proven to be uncountable).

It is this T1 theorem which starts a chain of problems within set theory (although I suspect that the diagonal argument is still the originator of all of this).

Ultimately, what happens is that given any possible structure for reals that could fit into set theory, forcing it to be bijective with T1 incorrectly stuffs it into a sequence. No sequence can get past Cantor's argument. And T1 reduces anything larger than a sequence, to just being a sequence. Thus they all work together to insure that set theory can't be applied to complex structures. 

Thus any potential structure to hold R, no matter if it is correct or not, cannot be examined objectively. They all fail regardless of what they hold, or how they hold it.

To some, this is the essence of the proof that reals are uncountable. That there is no way to get around these behaviors. To me this appears to be circular logic, with each flaw protecting each other from detection.

But if we remove T1, and use only D1 and D2 instead, then countable and countably infinite don't blur (and we can ignore countably infinite). Then the rationals are only countable, and any structure with multiple infinities isn't incorrectly flattened into a single infinity. Then magic sequences really do exist and they get past Cantor's and then there is actually a chance (although not definite) that R is in fact countable (injective).

Removing T1 starts a landslide in set theory. And given that parts of it are inconsistent with it's own initial definitions, it is a good thing to question this.

PLEASE, before you rush off and comment, accusing me of missing something elementary, please reread this post very carefully. Over the last few weeks, I have had an excellent stream of comments from which to learn. In writing this, I took many of them into account, and tried to make sure that I didn't pass over anything obvious. I reread my references, and tried to account for all of the details. I do really appreciate comments, but I hope that people can stay constructive, and really dig into the substance of the problem. The problem is subtle, deep and has wedged its way past a great number of people.