Transfinite Cardinality

Following extracted from SetOfAllSets. IanKjos presented an argument in two parts, one about the cardinality of the reals, and the other about the set of all sets. I hope I have done justice to his thoughts by splitting one half off and leaving the other part where it was. -- RiVer

I'm curious about cardinality. I understand, for example, that the cardinality of the rationals is the same as that of the integers; this is the canonical introduction to diagonalization. Diagonalization allows you to use a representational dimension as a trick to establish an infinitely-extensible (by induction) one-one mapping between two infinite sets.

This, BTW, leads me to believe that induction can get you infinity but you have to be pretty darn careful not to leave any cracks along the way, and you have to figure out just which kind of infinity you get to. In particular, you can get to the infinity with the cardinality of the integers.

Anyway, I'm not aware of any diagonalization-related arguments about the cardinality of reals. The simplest version seems to be that you could try diagonalization, but you'd need an infinite number of dimensions (to represent e.g. digits after the decimal point). Thus, you could never get past 0.

By the same token, it seems that reals might be a power set of the integers, but to establish the 1-1 map, you have to figure out how not to leave any holes. The strategy I described above leaves holes unless you accept that they are wiped out by mathematical induction. I don't think that's the case, though, because covering any 10^-K sized gap in the real line has (clearly) the same cardinality as covering the line from 0-1, by scaling your coverage by 10^/K. Therefore each time you go from K to K+1 the size of your problem has not decreased even partially. We can't really demonstrate any real base case. Thus, proving our theorem seems to require accepting its truth, which means that it's not a theorem.

At this point, my real understanding of (infinite) set theory breaks down. I hypothesize that there is no way to map REAL one-to-one with any set-theoretically constructed set, because there is no way to sequence REAL, but there is a way to sequence (at least lexically) every constructed set. An attempt at a lexical sequence on REAL results in the construction of essentially the paragraph above. However, so does the power-set of integers. I think the difference is that in the case of the power-set of integers, you have a base case both times you need one. You don't get one for the REAL set. -- IanKjos

One diagonalization argument with the reals is the one proving that the set of functions on the [0,1] interval has higher cardinality than the [0,1] interval itself. This is similar to the argument proving that the reals have higher cardinality than the integers.

To find a 1-1 mapping between the powerset of naturals and the [0,1] interval, one has merely to work in base 2. The mapping is simple: if the integer n exists in a set, the nth digit after the decimal is a 1, otherwise it is 0. Thus, the set {1,3,5} corresponds to 0.10101 in binary; {} corresponds to 0, and the set of all naturals corresponds to 0.111111111111... or just 1.

Btw, induction can't get you infinity. If it did, there would be no need for the axiom of infinity.

Somebody answered your first question in the previous paragraph: he/she showed a 1-1 map between the Reals and the power set of the Naturals (P(N)). I will answer your second: there is a sort of "lexical sequence" on the Reals. I learned about that in Hebrew, and I'm not sure that the English terms I use are standard.

There is a statement in set theory to the effect that every set can be well-ordered, so the Reals can also be well-ordered. The proof is half-constructive, and relies on the axiom of choice, but we don't know about any choice set of the Reals, so we cannot find a good order for them. Formally, a good order on a set is a relation that behaves like "<", where every subset of your set have a minimum according to this ordering. I will give some examples:

1, 2, 3, 4, ... - The "regular" order on the Naturals. It is called Omega (if I recall correctly).
1, 3, 5, 7, ..., 2, 4, 6, 8, ... - A different order. It seems "abnormal", but it can be defined mathematically. It is called Omega*2.
1,4,9,16,..., 2,5,10,25,..., 3,6,11,26,..., 7,12,27,..., .... - Contains Omega an infinite number of times, hence called Omega*Omega.

The standard order on the Reals isn't a good order, because it's dense. The standard order on the Integers isn't a good order, because there is no minimum. Here is an example of ordering the Integers in Omega*2: 0,1,2,3,...,-1,-2,-3,...

The reals can also be ordered in a good order, but their cardinality is uncountable, so I cannot show this on this page (or even imagine it). -- AmirLivne

Clearly, you can introduce new operators and you will still generate 'only' countably many new numbers if you are simply going to combine the existing numbers. But the question remains, by doing that can you cover all the reals?

When we diagonalize the rational numbers, we find a way to put them in order (1, 2, 1/2, 3, 1/3, 4, 1/4, 2/3, ... ).

Let's do that, removing each in turn from the number line. As the numbers are so thin, let's take a guard band out round each one. Remove 0.1 from around the first (so we chop out from 0.9 to 1.1), 0.01 from around the second (1.99 to 2.01), 0.001 from the third (0.499 to 0.501), (2.9999 to 3.0001), (0.3332 to 0.3334 to contain 1/3), etc.

When we have done, we have chopped out all the algebraic numbers from the number line. The total length removed is 0.2 + 0.02 + 0.002 + 0.0002 +... = 2/9. Almost all of the infinite number line is left, even though we chopped out all the algebraic numbers! (In fact, we removed a little less than 2/9 because some segments got chopped out twice).

What is left is very interesting - a sort of infinitesimal dust because there is a gap between any two points on the line, no matter how close they are. These points represent the transcendental numbers (as the transcend algebra - no mystical significance).

So your hypothesis is justified - no matter how you construct numbers built up from the integers, there will still be vastly more numbers left that transcend your construction.

Given that there are vastly many of them, it is interesting that only three are specifically known: e, pi, and the chaos number [someone help me with its name here please], though we do have simple constructions built up from them, like 2pi, 1/e, etc. -- RiVer

No, there are lots of examples of transcendental numbers that can be written easily. For example,

  0.11010001000000010000000000000001... =

^{-1} + 10^{-2} + 10^{-4} + 10^{-8} + 10-{-16} + ... + 10^{-(2^n)} + ...

and similar examples (use n! instead of 2^{n}, etc.) provide examples of transcendentals. This comes from the fact that numbers that are too well approximated by rationals are transcendental. Not only that, but any power a^b where a is algebraic (but not 0 or 1) and b is an irrational algebraic is transcendental. 2^\sqrt{2}, e^\pi [= i^{-2i}]. Also, natural logarithms of algebraics (except for \ln 1 = 0, of course) are transcendental. It's not hard to find numbers that are transcendental. On the other hand, it's sometimes hard to tell whether a given number is transcendental, even given a good formula. We don't know about \gamma, the Euler constant, for example. And, at least one of e+\pi and e\pi are transcendental, but are both?

Cantor was intrigued by these cardinalities. He suggested a whole sequence of what he called Transfinite Cardinals. The countable infinity is intuitively the smallest possible cardinality of the infinite, let us call that aleph-0. The next infinity, the smallest infinity that is provably bigger than aleph-0 he wanted to call aleph-1, then aleph-2, etc.

Question, is the cardinality of the reals the same as aleph-1? In other words, can we prove that there is no degree of infinity that is both greater than the cardinality of the integers and simultaneously less than that of the reals? Cantor spent a lot of time trying to answer that question, and discovered a lot of interesting things about infinities, but he never found the answer.

Nowadays, people represent the cardinality of the reals with a curly capital C, and almost everyone has stopped wondering if curly C = aleph-1. -- RiVer

Actually, people do worry about that. Mathematicians have [basically] agreed on a particular set of axioms for set theory, Zermelo-Frankel set theory (abbreviated as ZF). ZF is pretty much the minimal set theory required to ask the questions people ask. It does not, however, provide much information on how large sets are and 'how many' sets exist.

Typically, mathematicians adjoin the Axiom of Choice [AC] to ZF, resulting in ZFC. This states that given any collection of sets S, there is a choice set that contains 1 element of each.

You might ask whether AC can be proven from ZF. Godel proved in the 1930s that you can't disprove it, and Paul Cohen in the 1960s proved that you can't prove it either. Neither AC nor its negation can be proved from ZF; AC is independent.

In NewFoundations, OTOH, AC is provably false.

Godel and Cohen proved the same result about the continuum hypothesis, that c = 2^{\aleph_{0}} = \aleph_{1}. CH and its generalization, GCH, are independent of ZF too. Think of AC and CGH as being similar to the Parallel Postulate in geometry.

Some mathematicians (Shelah, for example) think that this just means our axioms are too limited. Perhaps there is a plausible axiom that should be added to the list. If so, what should that be? People have many technical suggestions.

Nonetheless, most mathematicians accept AC as being fundamental and appropriate. CH and GCH are of greater controversy. Some alternative axioms include Martin's Axiom, MA, which says that any set that looks like the reals in a certain way really is the reals, and the Axiom of Projective Determinacy, PD, which deals with whether certain games have winning strategies. Again, which sets of prospective axioms imply which others, and which are truly plausible is of great debate.

-- EricJablow

[Is there a good description on some internet site of the 'method of forcing' that Cohen invented?]

Achilles had overtaken the Tortoise, and had seated himself comfortably on its back. 'So you've got to the end of our race-course?' said the Tortoise. 'Even though it does consist of an infinite series of distances? I thought some wiseacre or other had proved that the thing couldn't be done?'

CategoryMath