Gustavo Lacerda

Cantor's diagonalization argument doesn't work because the new generated real number would contain infinitely-much information. Therefore it doesn't exist.

I'm not sure I see the distinction here. If you can define the natural numbers as an infinite collection of things, why can't you define all subsets of them in the same way? The set of all subsets is just the power set, which you accept above as a way of defining the real numbers.
The power set of the naturals exists, but only intensionally. You can never be presented with it in its entirety. The description of P(N) is finite, and in fact very short: as you can see, I can write it in 4 bytes: 'P(N)'

All the "transfinite nonsense" is in fact also perfectly good mathematical fiction, since they all come in finite books, journal articles, papers, etc. And I will appreciate them if they are useful, whether making in proofs shorter or finding new proofs at all.

From:

The cardinality of ℝ is not ℵ₀. It is still 2^ℵ₀. You just need to realize that a larger cardinality does not mean a larger set. Rather it means the set is more ‘complex’.

You shouldn’t change the definition of cardinality, but you can change your philosophical interpretation of the definition.

From:

well, if we only let R have computable numbers, then there will be a bijection between N and R. So I don't know what you mean by "the cardinality of R will still be 2^aleph_0".

When do you go to Nijmegen, btw?

From:

What do you mean by "exist"?

From:

Very good question!

In a way, all mathematics is fictional, but some mathematics feels more fictional than normal. Transfinite stuff, for instance... It feels bullshitty to me whenever someone talks about higher infinities and other things which we necessarily can't grasp. The point is that we can only talk about them as abstractions, without ever actually seeing them.

Maybe I should talk about intuition, or maybe I should talk about accessibility or understandability (which I am formalizing as computability).

From:

"Intuitive" is a very dangerous concept to introduce to formal systems: our brains are weak, and relying on being able to grasp things intuitively would have stopped us from ever developing quantum mechanics, or general relativity, or more than 3 spatial dimensions, for examples in physics.

In math, it's like those people who don't accept proof by contradiction, you can do it, but you're going to get a hell of a lot less math done, and some of the math you miss is really beautiful stuff.

But also - the contiuum is a pretty intuitive concept to me at least, even if the numbers you get aren't computable, you can compute them as arbitrarily accurately as you want so there's an intuitive idea of what they are if 'convergent limits' are intuitive to you (both the description of a real number as a Dedekind cut or a Cauchy sequence both allow for a deterministic process to tell you whether your rational guess at the number was within any fixed epsilon...).

From:

There is no bijection. No function (algorithm) exists that can map ℕ onto ℝ. I can give you a list of Turning machines, but you cannot pick out all the ones that are real numbers.

I’m in Nijmegen now. I’m giving a talk in Eindoven Tuesday afternoon.

From:

"Intuitive" is a very dangerous concept to introduce to formal systems: our brains are weak, and relying on being able to grasp things intuitively would have stopped us from ever developing quantum mechanics, or general relativity, or more than 3 spatial dimensions, for examples in physics.

Agreed. But uncomputable numbers are more than just "unintuitive". They are fundamentally un-(reachable? accessible?). You've never seen one, and you never will. I take this to mean they don't really exist, except as abstractions.

In math, it's like those people who don't accept proof by contradiction, you can do it, but you're going to get a hell of a lot less math done, and some of the math you miss is really beautiful stuff.

I've also expressed this instrumentalist feeling in my post: what's useful is good!

But also - the contiuum is a pretty intuitive concept to me at least, even if the numbers you get aren't computable, you can compute them as arbitrarily accurately as you want so there's an intuitive idea of what they are if 'convergent limits' are intuitive to you (both the description of a real number as a Dedekind cut or a Cauchy sequence both allow for a deterministic process to tell you whether your rational guess at the number was within any fixed epsilon...).

The point is that any real number you give me, whether through Cauchy sequences or Dedekind cuts, will be given to me in a finite form. Thus, we have a computable expression of the real number. But there are only countably such real numbers. The ones I say don't exist are the ones you can't possibly express finitely.

Have you heard of Fredkin? He believes everything in the physical universe is discrete.

From:

The point is that I'm restricting R to computable numbers. There are only countably many Turing machines, so only countably many real numbers are computable. Sure, we'll have TMs that don't halt, etc... but that can only make the set smaller.

I'd like to hear your ideas on applications of formal theories to education. I have a bunch of ideas, but they need to be beaten up.

From:

You've never seen one, and you never will. I take this to mean they don't really exist, except as abstractions.

Just because you or I will never see one, why should this mean they don't "exist"? To me, all numbers are abstractions - they're formal constructs which interact with each other according to rules we made up. "x", the variable, takes on the value of some noncomputable number, say. I happen to know some finite amount of information about said number: it's between 0 and 0.00001, yadda yadda. Is it not existent just because I can't write it down in closed form?

The ones I say don't exist are the ones you can't possibly express finitely.

Yeah, I guess when you stick to dealing with only concrete numbers, you're going to inevitably end up with these. It just seems backwards to me - for me, I really do stick with the (finite, very expressable, but abstract) statements like, "to me, 'real numbers' are elements of the abstract set which is the unique-up-to-isomorphism complete ordered field". *That* finite expression encompasses the whole set, and I accept by logical extension that all of its members have equal 'existence' to the set as a whole. Not doing so seems contradictory to me - how can you accept "the set of real numbers" but not accept almost all of them. It seems you would have to not accept that the concept of completeness or continuity, or really limits at all, if you want to stick to only computable things.

Have you heard of Fredkin? He believes everything in the physical universe is discrete.

As a physicist, I tend to think that whenever a philosopher or mathematician posits descriptions about "the entire physical universe", they're talking out their ass. :) The only rational view of the universe I accept is that of the agnostic: we don't know what the hell it is.

From:

you can compute them as arbitrarily accurately as you want

This is untrue, and basically at the heart of gustavolacerda argument. For a concreate example, take the ‘halting probability’ Ω (http://alixcomsi.com/Is_the_Halting_probability.htm).

Robert Solovay ... has constructed a self-delimiting universal Turing machine such that ZFC, if arithmetically sound, cannot determine any single bit of its halting probability ... Rephrased, the most powerful formal axiomatic system is powerless when dealing with the questions of the form “is the m’th bit of Omega 0?” or “is the m’th bit of Omega 1?”.

From:

I'm not sure I follow: does this turing machine have a particular probability of halting on any given input?

From:

I agree the set is smaller. I’m just saying that no bijection exists. In fact no onto function exists, and a set A is countable if there is a function f:ℕ→A that is onto.

Just because the computable reals are a ‘subset’ of Turning machines, doesn’t mean a bijection exists.

From:

This is a universal Turing machine so my understanding is it the probability that a given input (a number representing a Turing machine) will halt.

From:

hmm.. what's the distribution of inputs, though?

From:

So it's actually a function, not a number right? : given an input number N, there is a probability Omega(N) that it halts. And you're saying that this particular turing machine has the property that Omega(N) is a real, yet uncomputable number, for some (all?) N?

From:

This halting probability business... again: self-reference, so I'm not going to be surprised if we get weird things.

I think what

pbrane had in mind was your average uncomputable real number (which I tend to picture as a random point on the real number line), but the problem with those is that we have no idea what they are actually like, since we've never seen one!

From:

Fredkin is a physicist too. He studied with Feynman.

Secondly, while we "don't know what the hell it is", we need metaphysical theories from which to create physical theories. Fredkin predicts that digital physics will be falsifiable one day: from my understanding, it suggests that all symmetries will eventually be broken.

From:

I’m just saying that no bijection exists.

Interesting. How do you know? Is this a consequence of the halting problem?

From:

I really do stick with the (finite, very expressable, but abstract) statements like, "to me, 'real numbers' are elements of the abstract set which is the unique-up-to-isomorphism complete ordered field". *That* finite expression encompasses the whole set, and I accept by logical extension that all of its members have equal 'existence' to the set as a whole. Not doing so seems contradictory to me - how can you accept "the set of real numbers" but not accept almost all of them. It seems you would have to not accept that the concept of completeness or continuity, or really limits at all, if you want to stick to only computable things.

Interesting point (I missed it at first).

I don't want to give up completeness. Yet, I hold that not all limit points need to exist. The only limits that we need to exist are the limit points of computable sequences.

Ok. You're requiring R to be a complete ordered field. So let's take the rationals (Q) and close them under limits.
So, given any sequence of rationals, this set should contain their limit.
Since all possible inputs are computable, we only need to add countably many limits (one for each possible sequence).
So we still only have countably many numbers in R (which we call the "complete ordered field").

I think of mathematics in a lazy way (in analogy with "lazy evaluation"), so things only need to appear as you ask for them. In this view, it seems clear that only computable things exist. No set needs to contain uncomputable numbers, because countably many things are enough to serve all possible requests.

My thoughts on this are still sloppy. Please do criticize.

From:

Hmmm... he sure doesn't read like a physicist - he reads like a computer scientist, and doesn't seem to have that great of a way of describing his ideas in detail, from what I can see on his site.

we need metaphysical theories from which to create physical theories.

I'm not sure what you mean by this: the scientific method is based on inductive, not deductive, reasoning: we describe what we observe, and we model it in a variety of ways. The models which have the fewest moving parts are the ones we prefer. That's physics.

We don't "postulate" that physics is a discrete system, we, for example, observe that GR (in a weakly coupled regime where it's valid), mixed with QFT (in a locally flat piece of space where *it* is valid), predicts that black holes have a temperature, and contain information: a finite number of possible microstates which is the exponential of the area of the event horizon (in units of the planck length).

This gedanken-observation hints at the fact that the information contained in any finite volume of space is indeed finite, and yeilds entropy proportional to the area bounding said volume (in units of the planck length). So yes, there are reasons to consider theories that have finite amounts of information density, but you shouldn't assume it from the start. String theory seems to embody this concept *even though* it's completely continuous, all the way down to, and below, the planck scale. Maybe the naive descriptions of string theory are describing information redundantly, but that doesn't mean it's any less real of a description (assuming it's right, of course), just because it uses a completely contiuous basis.

I guess I'm really not sure we need a new "metaphysical theory" from which to create physical ones - direct observation points to continuity down to 10^-19cm, and indirect (looking for violations of relativity, the equivalence principle) observations point further than that. Without a *physical*, not metaphysical, reason to assume discreteness, we shouldn't do it. It may turn out to be *true*, but that doesn't make the arguments for it compelling to me before the fact (especially because it's easy to go too far: it could be that space and time are discrete, but that quantum mechanics is still based on a whole bunch of continuous internal symmetries [i.e. superposition is still true, even if you take the superposition of two states with any complex [not just complex rational or constructable or whatever] coefficients in front of them).

From:

Ok. You're requiring R to be a complete ordered field. So let's take the rationals (Q) and close them under limits.
So, given any sequence of rationals, this set should contain their limit.

If it does contain all of the limits of all of the Cauchy sequences, then you're going to get all of the traditional R - all uncountably many numbers.

Since all possible inputs are computable, we only need to add countably many limits (one for each possible sequence).

But there are uncountably many convergent (cauchy) sequences of rationals, so adding each limit will indeed make your set uncountable (and hence, most of these sequences must not be computable).

If you want to keep completeness, then you're going to be stuck with uncomputable numbers: there is only one complete ordered field, and it contains uncountably many uncomputable numbers.

From:

I meant: we only care about computable Cauchy sequences. There are countably many of those. And so this gives us countably many new limits to add to our set.

Have you ever seen a non-computable Cauchy sequence?

From: