Is mathematics mostly chaos or mostly order?

If I had a semester or two of free time I'd love to hit this subject again. I once told my math prof (logician) who made a comment about transfinite cardinals: careful it's powerful but it's power from the devil. I half regret that comment in retrospect.

I've never made peace with Cantor's diagonaliztion argument because listing real numbers on the right side (natural number lhs for the mapping) is giving a real number including transedentals that pre-bakes in a kind of undefined infinite.

Maybe it's the idea of a completed infinity that's my problem; maybe it's the fact I don't understand how to define (or forgot cauchy sequences in detail) an arbitrary real.

In short, if reals are a confusing you can only tie yourself up in knots using confusing.

Sigh - wish I could do better!

There are a couple of strategies for understanding the real numbers. One is to write down a definition of real numbers, for example using rational numbers and Dedekind cuts, hoping that what you're describing is really what you mean. The other is to write down the properties of real numbers as you understand them as "axioms", and go from there. An important property of real numbers that always comes up (either as a consequence of Dedekind cuts or as an axiom itself) is the least upper bound property -- every set which has an upper bound has a least upper bound. That's what gives you the "completeness" of the real numbers, from which you can prove facts like the completeness of the real numbers (i.e., Cauchy sequences always converge), the Heine-Borel theorem (closed and bounded subsets of the reals are "compact", and vice-versa), and Cantor's intersection theorem (that the nested intersection of a sequence of non-empty compact sets is also compact).

The diagonalization argument is an intuitive tool, IMHO. It is great if it convinces you, but it's difficult to make rigorous in a way that everyone accepts due to the use of a decimal expansion for every real number. One way to avoid that is to prove a little fact: the union of a finite number of intervals can be written as the finite union of disjoint intervals, and that the total length of those intervals is at most the total length of the original intervals. (Prove it by induction.)

THEOREM: [0, 1] is uncountable. Proof: By way of contradiction, let f be the surjection that shows [0, 1] is countable. Let U_i be the interval of length 1/2*i centered on f(i). The union V_n = U_1 + U_2 + ... + U_n has combined length 1 - 1/2*n < 1, so it can't contain [0, 1]. Another way to state that is that K_n = [0, 1] - V_n is non-empty. K_n also compact, as it's closed (complement of V_n) and bounded (subset of [0, 1]). By Cantor's intersection theorem, there is some x in all K_n, which means it's in [0,1] but none of the U_i; in particular, it can't be f(i) for any i. That contradicts our assumption that f is surjective.

Through the right lens, this is precisely the idea of the diagonalization argument, with our intervals of length 2*-n (centered at points in the sequence) replacing intervals replacing intervals of length 10*-n (not centered at points in the sequence) implicit in the "diagonal" construction.

> Maybe it's the idea of a completed infinity that's my problem; maybe it's the fact I don't understand how to define (or forgot cauchy sequences in detail) an arbitrary real.

As someone who also has never fully made his peace with the diagonality argument, but just chosen to accept it as true, as a given, this kind of bumps up against an interesting implication of different cardinalities of infinity.

To precisely define an arbitrary real you'd need some kind of finite string that uniquely identifies that real number. Finite strings can be mapped, 1 to 1, to natural numbers. Therefore there can't be a finite string for any real number that uniquely identifies it. Otherwise we'd have a mapping between natural numbers and real numbers.

In fact, the set of uniquely identifiable real numbers is a countable subset of real numbers. [1]

Somehow, this realization has helped me make peace with the uncountability of real numbers.

[1] Sorry if use words like "unique", "identify", "define" in not quite the right way. I hope the meaning I'm going for comes across.

Cantor’s original proof of the uncountability of the reals didn’t use a diagonalization argument, it used order + completeness and in fact applies to any complete poset. https://en.wikipedia.org/wiki/Cantor%27s_first_set_theory_ar...

Likewise his proof that there is no surjection from a set to its power set uses a more general diagonalization argument that doesn’t make any uncomfortable assumptions: https://en.wikipedia.org/wiki/Cantor%27s_theorem

> The union V_n = U_1 + U_2 + ... + U_n has combined length 1 - 1/2*n < 1, so it can't contain [0, 1].

This argument seems way less convincing to me than the diagonalization argument, because as n is going to infinity that length does become 1.

> I've never made peace with Cantor's diagonaliztion argument

Maybe you'd prefer a purely set-theoretic one:

---

Let R be a set. Let S be a set of all subsets of R.

We want to prove that |S| > |R|, by proving that a bijective function from R to S cannot exist. We will do that by assuming that it can, and then deriving a contradiction.

Assume there is a bijective function f : R -> S. Define D = { r ∈ R | r ∉ f(r) }. Since f is a bijection, there exists some r₀ ∈ R such that f(r₀) = D.

However, by the definition of D, we have:

- If r₀ ∈ D, then r₀ ∉ f(r₀) = D, which is a contradiction.

- If r₀ ∉ D, then r₀ ∈ f(r₀) = D, which is also a contradiction.

Therefore, our assumption that there exists a bijective function f : R -> S must be false.

Therefore, |S| > |R|.

Then we can crank that 2 up to 3 or 4.

Then let U_i be the interval of length 1/3^i centered on f(i), so that the total length is 1/2, far less than 1.

Even though the supposed "surjection" is infinite, it's still the case that every x in [0,1] would be in in one of the finite U_n and therefore V_n. But every K_n clearly has measure > 0 and is therefore non-empty, and since the K_n are nested subsets, there is at least one special point x_omega that is in all of the K_n.

The "intuitive" problem (not logical problem) with PP's proof is that it relies on measure and completeness, which is far more technologically complex than the decimal diagonizalization argument.

Here is intuitive "rebuttal": the same proof strategy seemingly proves that the rationals are uncountable! (This is of course technically false, because rational intervals are incomplete and all have measure 0 in the first place. But understanding this is much more complicated than imagining an 2-D infinite spreadsheet of decimal numbers between 0 and 1.)

A way to make peace with the Reals is to understand them as "potential numbers". Every where you look, there is Real number. Everyone logical agrees about that.

But what about where you don't look? Either you take the orthodox axiomatic view that Real numbers are there too, or you take the constuctivist or finitist (or perhaps quantum mechanical?) view that nothing is there until you look, because the act of looking is the same as the act of creation.

Then use 1/3 instead of 1/2 for a combined length of 2/3 -- the total length of the intervals can be as small as you like. This hints at the fact that any countable subset of the real numbers is Lebesgue measure zero.

Even using 1/2, the set that remains is nonempty due to the Cantor intersection theorem. The total length of the intervals is 1, which means that the remainder has no "interior" (i.e., contains no open interval), but the converse is not true: removing intervals whose lengths sum to less than one does not mean that the remainder will contain any interval. This is the consideration that allows you to create what are called "fat Cantor sets" -- the middle thirds Cantor set has Lebesgue measure zero, but by removing smaller intervals you can get other, homeomorphic sets that have positive measure.

If it's the idea of completed infinity that's the objection, then it's the first step, constructing the powerset, that would be problematic. Various forms of finitism would not accept that one can 'take all the subsets, finite or infinite, and quantify over them' and obtain a meaningful result past the formal level.

> I once told my math prof (logician) who made a comment about transfinite cardinals: careful it's powerful but it's power from the devil. I half regret that comment in retrospect.

You're in good company -- from Penelope Maddy's "Believing the Axioms"[0]:

---

Measurable cardinals were introduced by Ulam in [1930], where he proved that they are inaccessible. They are now known to be much larger than that, larger than all the hyperinaccessibles, Mahlos and weakly compacts. Indeed, because of their power, they are probably the best known large cardinals of all. The voice of caution reminds us that they were invented by the same fellow who invented the hydrogen bomb.

---

0: https://jwood.faculty.unlv.edu/unlv/Articles/Maddy1.pdf

I wouldn’t call it quantum mechanical. The “looking” in math is not like the measurement of an observable/operator in quantum mechanics. When you consider a thing in math, there’s no alternative thing that you could have considered instead which would correspond to a different operator that doesn’t commute with the first one.

They should still then accept that there is no surjection from a set to a set that is a set of all subsets of that set (because of there being no such set).

I'm will give this more consideration; thank you for the comment.

For now I just want to add you hit a bit closer into the slight of hand in Cantors argument (for me) which is alluring but hard to surmount in the last 10% of the argument.

The natural numbers are constructible, finite. They are finite to write down. It requires a finite amount of code (tape) to output one etc. The 1:1 mapping business gets the concept of infinity onto the table but without engaging a completed infinity. So far, it's solid followable etc ... now the next 5% you toss real numbers in rhs ... then produce another real off the diagonal for 5% more ... and |Z| /= |R|.

Here real numbers live under the shadow or reflect the light of nats, which is misleading. The reals are not well defined objects.

Now, the realist (the mathematician) will argue: the point of Cantor's argument is not to construct reals as part of the solution to |Z| /= |R|. The point is only to establish there's no bijection. In truth I agree: the focus is on the mapping not getting dragged into the mud of construction.

However, I remain unclear if too much got swept under the rug that (practical minded) argument. I will have to re-read Chatin/Kolmogorov ... so I need 4 semesters now. This is my spooky action at a distance problem.

Are these the same proof?

If I let U_i be the interval of length 1/10^(i) centered on f(i), than what I'm saying is pick a different decimal digit to avoid this particular real.

Like your setup! I'll give this thought with pen and paper. Thank you

There would be no such surjection, but there would also be no such |S| to talk about in the conclusion.

In the diagonalization you don't need to assume the existence of any real numbers. Just on the left hand side you write down, formally, any sort of numbers that have decimal expansions that may be infinite. Rational numbers have infinite decimal expansions too, it's just that they will eventually repeat, but at this stage it's not necessary to think about what the properties of these infinite decimal expansions actually mean. Then the diagonalization argument shows that this set of numbers with infinite decimal expansions are uncountable and also contain the rationals. This still doesn't define the real numbers yet: to do so one needs to think about the Euclidean metric on the rationals and how to complete it.