Hacker News Reader

For what it's worth, this is only true in Cantor's horrifying paradise. In the world of the intuitionists, none of this is true. Reject Cantor and embrace Brouwer and you can once again live in a world without these horrors, and all you lose is absurd statements about things true "almost everywhere" that are never true, and crazy results like Banach-Tarski that get an impossible result by doing two impossible things to set it up.

How does Brouwer work again? Is it some kind of constructionist or finitist approach?

Yeah, it is the standard idea of limits-of-rationals, but within the intuitionist logic that Brouwer championed.

The easy semantics for intuitionist logic is that every statement is about provability: “A or B or C” is a statement that one or more of these 3 proofs has been supplied.

Where this gets a little bit funky is, you can still take an open mathematical problem and still encode it into the reals: “The nth bit of this number r is 1 if n is a counterexample to the conjecture, or else 0 if not.” If for each n that problem is decidable in a finite number of steps, then this is a perfectly good intuitionistic predicate with which to define a number, and so Goldbach’s conjecture for example can be phrased as “is the Goldbach real equal to 0?” You can do that in the classical approach and Brouwer doesn't limit this too much.

But, now you want to assert that “the Goldbach real number is either 0 or positive.” Because you know it is on the range [0, 1] by construction, right?! But no no no no no, if you want to stay that it is either 0 or positive, you have to furnish me with either a proof that it is 0 (solving the Goldbach conjecture in the affirmative), or a proof that it is positive (solving the Goldbach conjecture in the negative). So you have to come up with alternative ways to talk about the order on the real numbers because ordering statements are this classic example where people love to use the very law of the excluded middle that Brouwer has forbidden.

Interesting, thanks for taking the time to type that.

So you really would have to change the basis of logic to get rid of the strangeness of Cantor's sets, huh? That's quite a leap, I wonder if that would lose other properties of mathematics as well, some that would be nice to actually have?

I mean if you insisted infinities don't exist, you'd get rid of a lot of funky stuff, but lose analytic derivatives and integrals, which definitely is not a good trade-off in my opinion. Some people actually advocate for this, all working on discrete math of course.

> change the basis of logic to get rid of the strangeness

Short answer is yes.

Long answer is that the accepted framework of the "basis of logic", i.e. ZF set theory, is a direct result of Cantor's program -- Cantor was not working from an axiomatic basis, he was creating the formalism for set theory. Where things went wrong were not so much that he was an idiot or anything; clearly he is a tremendous genius and saw implications of his programme that led to incredibly strange and counterintuitive spaces. But instead of revisiting the basis, he found himself drawn to this verdant landscape.

Intuitionists (and its various offshoots and cousins) don't reject the notion of infinity per se; even finitists, the most extreme class, still accept that there is an infinity in the form of a repeated process -- that the positive integers are "infinite" in the sense that you can always produce a larger one than any proposed maximum. Integration and differentiation still exist, but are much easier to formalize, because, essentially, the behavior of any constructible function is completely defined by its behavior on rational numbers (or any other constructive version of dense number systems, like binary or decimal expansions).

In re: "different infinities", this is the big red herring of Cantor's work. This requires that you accept that a 1:1 correspondence of infinite sets yields a class of sets that you can group by into "cardinality", and those cardinality classes have an interesting meaning. But this defies the operational use of infinity -- there are more natural numbers than even numbers if we're thinking about strict subsets, but when we're summing series, they are effectively the same size. So it's not necessary to choose some definition of the "size" of an infinite set; you can just choose what operational characteristic you are looking at in the context you're working in.

Can you tell me more about this? Why are Cantor's discoveries ignored or how do intuitionism deals with the contradictions that would arise from it?

Generally unless you can construct an item, it is not really that relevant. Cantor's argument about the sizes of infinities is only interesting if you accept that the definitions make sense -- i.e. that "cardinality" represents a notion of size, and that 1:1 correspondence means that two infinite sets have the same cardinality. So we have the notion of "countable" sets like the integers, and he proceeds to prove that the reals can not be put in 1:1 correspondence, so are a different cardinality.

But you can just ignore this and treat infinity in an operational sense rather than try to have a general definition. The problem with the uncountable argument is that not only are the rational numbers countable, but so are the algebraic numbers, and so, in fact, are any numbers that can be constructed from a finitely expressed constructive process. Unfortunately, even after you leave all those subsets behind, you are left with an uncountable number of elements, none of which can be constructed. These phantoms are the "everywhere" in "almost everywhere".

The short version, I guess, is that those phantom numbers are artifacts of a formalism that allows you to deduce the existence of something by disproving its non-existence rather than constructing an element. The core of most intuitionist mathematics is that the law of the excluded middle (that something must be either true or false) is disallowed under most circumstances. That pretty much ends up taming most of the crazy counterintuitive junk. Still plenty of unexpected and exciting results, and places where intuition breaks down, but far fewer instances of "this clearly is not true" stuff.

> it is only possible to describe 0% of the rational numbers between 0 and 1 with text

It is possible to describe 100% of the rational numbers with text. You describe the numerator, make a space, then describe the denominator. The length of the text document depends on the number described and can be arbitrarily long.

Sorry, phone autocorrected “irational” to “rational” rather than “irrational.” fixed!

> You start to appreciate that logic itself is this Lovecraftian eldritch-horror abomination, and that we only live in the Bliss of Sanity because we live in ignorance, never staring into its depths lest the abyss stare directly back into our souls.

Oh poppycock. We are the eldritch horror. We are the universe experiencing itself. Humans are space orcs, if Reddit is to be believed.

> describe 0% of the rational numbers between 0 and 1

I think you mean irrational :)

No, the statement holds perfectly fine for the rationals.

There is a 1-to-1 mapping between integers and rationals.

The basis for this statement holds, but what the statement implies does not.

That is, the numbers are a subset of the rationals, but it does not follow that we can't describe a rational with a number. In fact the rationals between [0, 1) have a well known numbering,

    [ 0/1, 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 
      1/6, 5/6, 1/7, 2/7, 3/7, 4/7, 5/7, 6/7, 1/8, 3/8, ... ]

where one increments the denominator and then goes through all numerators but keeps only numerators which have GCD 1 with the denominator (since if they share a factor they were already listed).

What you were probably thinking of is that 0% of the irrational numbers between 0 and 1 can be described by language as single entities. Or phrased differently: If you had a magic machine that could pick a random real number between 0 and 1, with 100% probability you would get a number that no finite phrase / definition / program / book could define. That is because everything we can abstractly define is part of a countable set and the set of irrational number (and real numbers) is uncountable.

For that reason, quite a few mathematicians view the real numbers as a useful, but ultimately absurd set. Much more sane is the set of computable numbers, that is the set of numbers for which you can find an algorithm that computes the number to arbitrary precision. (More formal: A number x is computable if there exists a Turing machine that gets as input a natural number n, terminates on all inputs, and outputs a rational number y such that |x-y|<10^-n .) Every number you ever thought of is computable, but as a mathematician, working with the set of computable numbers is much more tedious than working with real numbers.

> Much more sane is the set of computable numbers, that is the set of numbers for which you can find an algorithm that computes the number to arbitrary precision.

But perhaps still not as sane as one may hope. It would be very sane to be able to compute, for any two numbers, which one is larger (or whether they're equal), but sadly this is not computable for the computable numbers.

> Every number you ever thought of is computable, but as a mathematician, working with the set of computable numbers is much more tedious than working with real numbers.

I mean, I've thought of noncomputable reals like Chaitin constants.

> It would be very sane to be able to compute, for any two numbers, which one is > larger (or whether they're equal), but sadly this is not computable for the > computable numbers.

I'd like to understand - Can you explain this? It seems like it would be easy to have a Turing machines that uses the other two Turing machines, adding one digit at a time until it finds a difference.

> I mean, I've thought of noncomputable reals like Chaitin constants.

Heh, but how many digits can you actually provide? Not too many. So have you really thought of the number in any meaningful sense when you barely know any of its digits?

Also interesting that computer languages themselves are countable, so while it's hard to specify the digits algorithmically for the Chaitin constant of any computer language, you already know that the set of ALL Chaitin constants are countable.

>I'd like to understand - Can you explain this? It seems like it would be easy to have a Turing machines that uses the other two Turing machines, adding one digit at a time until it finds a difference.

I assume it runs into problems when you try to check if 2 > 2.

It's very funny how that's a really good example and made it click instantly. Thank you.

> Heh, but how many digits can you actually provide? Not too many. So have you really thought of the number in any meaningful sense when you barely know any of its digits?

I’ve never thought through very many digits of pi either. Or even 1/3 for that matter!

What about numbers computable with random draws? Doesnt that create the chance of hitting something totally irrational among the reals? Or how is computable numbers defined to avoid this?