Hacker News Reader

Comment by CJefferson | Hacker News Reader

As time goes by, I increasingly view things like uncountable infinities and the axiom of choice as "a fun maths game", rather than having any intrinsic truth or falsity. Other's view may differ.

Here is an interesting thing I've never seen anyone write down (I should do it myself) -- we don't need uncountable infinities.

* How many natural numbers are there? Countable

* How many rational numbers are there? Countable

* How many numbers are solution to a polynomial? Countable

* How many numbers are the output of any turing machine (including programs that run forever, producing an infinite decimal)? Countable

* How many numbers are the answer to any maths problem anyone can write down (where the problem has at most a countable number of answers)? Countable.

If the set of all numbers any can express in any sensible way, and the solution to any problem any could ever have, is countable, why do we need the other uncountables?

View on HN

This is discussed heavily in topics around constructing the reals and constructivism. Wikipedia has a short section about using the computables instead of the reals: https://en.m.wikipedia.org/wiki/Computable_number

It is pretty fascinating to think about: that almost all real numbers are not computable ("almost all" of course meaning "all but a countable set"). And yet you almost certainly will never run into a noncomputable real except in computer science when you're specifically defining one to illustrate something about computability (like Chaitin's constant).

Are there any good books on this topic?

Yes. An uncountable number are in the Library of Babel.

(actually - I'm guessing there's actually a countable number in the Library of Babel but it didn't read quite so amusingly that way. In any case - all the ones I flicked through were trash.)

Edit - The Library of Babel is actually finite isn't it? Fixed alphabet and fixed book length? It's a while since I read it.

the number of possible distinct books is finite but it's unknown if the library itself is finite. iirc it ended with the narrator speculating that, although the books themselves are devoid of meaning, perhaps the overall structure of the library is ordered, i.e. the same finite pattern of books repeats endlessly in infinite space.

The Library of Babel is finite if the books are unique. Interestingly, Borges does mention that one of the books in the library must be an index of the other books. This is similar to the notion of a universal computably enumerable language.

However, I doubt that Borges' claim is accurate. If the set of programs is finite, then I think there cannot be a comprehensive index of all programs. A finite set is a regular language, and there is no universal regular language in the set of regular languages.

I recommend Gregory Chaitin's book intended for a popular audience. It is short, and a good introduction to algorithmic information theory for non-mathematicians. Chaitin's Constant (Omega) is a non-computable number that is equivalent to the halting problem.

[0]: https://www.amazon.com/Meta-Math-Quest-Gregory-Chaitin/dp/14...

One of the great theorems in logic is the Lowenheim-Skolem theorem [1], which says that if a countable first-order model has an infinite model, then there is a countably infinite model. For example, there is a countably infinite model for the theory of reals.

I have heard that Skolem [2] used this theorem as a basis for his belief that uncountable sets can be avoided, and countably infinite sets suffice.

[1] https://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_...

[2] http://www-gap.dcs.st-and.ac.uk/history/Biographies/Skolem.h...

    the solution to any problem any could ever have

That's a pretty tall claim to make.

Once upon a time people thought irrationals and transcendentals like pi and e didn't even exist. It wasn't until the past century that people realized abstract algebra and its ilk had practical applications. The same goes for chaos theory and fractals as well.

Admittedly it's hard for me to envision a world where notions of countability will ever have real-world uses, but I also consider calling it "a fun maths game" rather reductionist, and frankly, poor taste (especially if you're going to say something like "intrinsic truth or falsity").

    Give him three pence, since he must make gain out of what he learns.

The reason I say "the solution to any problem anyone could ever make" is a maths argument!

If you can write down a problem as a finite string, then the set of all problems must be countable.

Are you aware of the concept of periods ? This is a quite fascinating, countable, ring of numbers, that captures all of the above:

Kontsevich and Zagier introduce and develop this concept quite far:

http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf

No, but this looks interesting. Thanks for the reference!

Just to give a little bit more attention to this link: Wikipedia link to one of the authors:

> https://en.wikipedia.org/wiki/Maxim_Kontsevich

Proof that one of the authors really is no other "M. Kontsevich" (I openly admit that I wanted to be sure since I associate Maxim Kontsevich mostly with other mathematical areas):

> http://www.ihes.fr/~maxim/publicationsanglais.html

How many sets of natural numbers are there? An uncountable number.

Of course, you could throw out some axioms so that you create an axiom system in which I can't define such a thing as "a subset of the natural numbers", but such a world doesn't feel "real" (in a platonic sense) to me.

In this case, what you "throw out" are uncomputable (or non-recursive, depending on terminology you like) sets; i.e. sets for which the membership function is not decidable. Yes, there are an uncountable number of these sets, but they can't be defined in any useful way.

Indeed, if you consider a real number to just be a decimal representation formed by concatenating all the natural numbers in a set (not at all a rigourous construction of the reals, but hopefully sufficient for this argument), the equivalence is clear.

I've always found dedekinds construction (where sqrt 2 is represented by the set of rationals {x in Q : x^2 < 2}) to be a nice natural place where powersets of countable infinite sets come up (in addition to being a great way to construct R)

I tend to prefer considering the sets to encode bitstrings (encode a set as sum(2 ^ -x for x in X)), but yes the equivalence between computable sets and computable numbers is straightforward.

For sure - as I understand it in most formulations you throw out lots of sets but keep all the finite sets of natural numbers, the set of even numbers, the set of prime numbers etc

One thing I never found satisfactory is that any axiom system like this has to define things in terms of decidability etc, so it's "more verbose" (or less axiomlike) than ZFC

This is a fair point.

I think the only axiom you need to rethink from ZF is powersets (since I think that's the only axiom that produces uncomputable sets from computable ones (ignoring the AC, briefly)). What you'd replace it with (some sort of one based on comprehension, presumably) I couldn't say though.

> How many sets of natural numbers are there? An uncountable number.

But, at most countably many of those sets will ever be individually thought about by any human being. So there are only countably many (and maybe more strongly finitely many) subsets which any human being could ever possibly think about, and an uncountable remainder which are unthinkable. In order to do mathematics, do we really need to posit the existence of an uncountable number of objects no human mind will ever be able to individually consider?

> Of course, you could throw out some axioms so that you create an axiom system in which I can't define such a thing as "a subset of the natural numbers", but such a world doesn't feel "real" (in a platonic sense) to me.

You could introduce a set theory where from a countable set you can only infer the existence of its computable subsets, or its first order definable subsets, or something like that. Not sure why that should feel any less "real" than an uncountable infinity of mathematical objects about which no one will ever individually think.

> But, at most countably many of those sets will ever be individually thought about by any human being.

If your arguments are tied to such physical constraints, then there aren't even countably infinite natural numbers unless the Universe is infinite in space or in time (such that there can be infinite humans or "thinkers").

Indeed, that's why I'm an ultrafinitist.

https://en.wikipedia.org/wiki/Ultrafinitism

Interesting. I was aware of finitism, of course, and even strict finitism, but not this particularly strict version of it.

That took a Wittgensteinian turn, lol.

I meant it doesn't feel real to me in a subjective sense, and of course I acknowledge other people might not feel the same way.

Better yet, just consider all deduction as "a fun language game," rather than having any intrinsic truth or falsity. If you assume a whole bunch of stuff and the axiom of choice, you can get these interesting things over here. If you assume that same bunch of stuff but not the axiom of choice, you get this other interesting stuff over there.

Which assumptions to use at any given time just depend on what you're trying to do. If I'm trying to count my sheep, I just need enough axioms to get me addition of natural numbers. If I'm trying to model some mechanical trajectory, maybe I ought to grab some reals. Got circles? Adding imaginary numbers to the reals makes that easy, even though imaginary numbers are totally "fake." Using sentences that might not make sense? Maybe avoiding the excluded middle is a good idea.

Good luck developing analysis with only countable infinities. Limits will take you out of the realm of countable spaces.

Most of your derivatives and integrals won't exists, if you force them to take values in countable sets.

Why not, can you give an example.

Most of the "common" derivatives and integrals I can think of would work just fine, unless I'm missing something obvious?

No, for example the integral sqrt(1 - x^2) from x = 0 to x = 1. Or any other integral over a circle/sphere for that matter.

Nothing wrong with that, it's still a computable number -- I'm not suggesting doing away with all real numbers, just the non-computable ones.

I don't claim to have thought through every detail, but having now gone and done some reading, this seems fine in the world of constructivism, which only requires computable numbers (and therefore only countable infinities of numbers)

Are the computable numbers continuous? If not, is that a problem for analysis? If so, can you construct some computable analogue of continuity which is sufficient?

- Every real number can be represented as a limit of rational numbers, which are uncountable. - So for every countable subset you can find a (Cauchy) sequence of rationals that does not converge.

Hence, you loose one of the most important tools in Analyisis (Cauchy criterium for convergence). You can still work with the remaining set, but formulating and proving theorems, is going to be much harder.

- If integrals over f and g exists, then the integral over f * g does not need to exists. - E.g. Integrals over bounded regions will not always exists. - Theorem of Montonic convergence fails - Function spaces will not be complete (L2).

A nice theory of constructible "periods" has been developed by Kontsevich and Zagier (http://www.maths.ed.ac.uk/~aar/papers/kontzagi.pdf) but it relies heavily on the existing body of Analysis being available.

I"m not sure what you're saying. There are only countably many computable sequences of rational numbers, so why shouldn't they all converge?

My argument aws: The constructible numbers are not "complete". You can always find cauchy sequences of constructible numbers that do not converge to a constructible number.

If you add the requirement that the sequence itself must be constructible things _might_ change. It depends on how you define constructible sequence.

I thought Cantors argument would show that there are uncountable constructible sequences: - Assume there are countable many C[1], C[2] - Construct a new one D = C[1][1] + 1, C[2][2] + 1, ... - D in constructible, hence it's on the list: C[j] = D - But D[j] =/= C[j][j] - Contradiction. This proof is however not correct. The sequence D does not need to be constructible.

One of the observations in programming language semantic proofs is that one doesn't need coinduction. Statements can be proven by good old fashion induction, by indexing them with the number of steps in the computation, then proving they hold for any finite number of steps.

I suspect the same technique applies to analysis. We don't need to prove a statement holds for reals with "infininte" number of digits, but merely for all rationals with finite k digits, where k is a parameter of the proof, thus can be arbitrarily large.

Reminds me of computing points in a Mandelbrot or Julia set

> As time goes by, I increasingly view things like uncountable infinities and the axiom of choice as "a fun maths game", rather than having any intrinsic truth or falsity.

Is a hammer true or false? I don't know, but it's good for hitting nails.

Yeah, a hammer is definitely useful, but I think the point he's trying to make is that the notion of uncountable sets isn't very useful outside of things like set theory.

You could have answered all of your questions with "finitely many", because, after all, we can each only perform a finite number of actions in the world.

In general, the infinite hierarchy of infinite sets "exists" because we can define it.

> If the set of all numbers any can express in any sensible way, and the solution to any problem any could ever have is countable

This is trivially true, since there are only countable (finite) expressions and problems.

> why do we need the other uncountables?

You can't do calculus without reals.

http://math.stackexchange.com/questions/1880741/why-cant-cal...

And calculus is pretty important (e.g. for any branch of physics ever).

No mathematical object exists exactly in the real world. E.g. you will never see a physically perfect square. The whole point of mathematics is that it's a simplified model of reality that's easier to work with for some purposes, and that's as true of uncountable infinities as it is of anything else in maths.

How many real numbers are there?

> How many real numbers are there?

2^ℵ₀

Which I just managed to encode using a finite number of symbols :)

Euler held that infinities in general were nothing more than a way of reasoning about limits.

The are uncountably many polynomial over the reals. There are uncountably many functions from N to N. The premise of your question is incorrect.

OP never claimed there were countably many functions from N to N, only that there are countably many Turing machines which is true.

By "polynomials" OP doesn't mean polynomials over the reals but over, for example, the rationals – the point is that there's a countable subset of R that's algebraically closed.

I know those things. OP does not claim that the set of functions from N to N is uncountable. One gives up things if only countable things are considered. For instance those things that I mentioned.

Oh, I see, you're addressing the "we don't need uncountable sets" statement by giving examples of intuitively obvious things which are uncountable. But I think OP's claim is that we don't "need" those things because we could do mathematics with the set of Turing machines instead of the set of functions, etc.

Yes, but can Turing machines do enough mathematics? The second order Peano Axioms are categorical and the first order axioms are not. The Incompleteness Theorem tells us that there are statements that are true in the standard model of N that are not provable by a Turing Machine.

Reply on news.ycombinator.com