computational philosophy of mathematics

[gusl]

I only believe in mathematical objects with finite information (i.e. with a finite expression). Things can expressed in any way you wish, intensionally, extensionally, whatever. So, while the natural numbers exist, not all subsets of it do.

While the set of real numbers exists (R can be expressed as the power set of N), not all of the traditional real numbers exist (only the computable ones do). So, in my definition, the cardinality of R is aleph_0 (i.e. the same as N). In fact, no set can have greater cardinality, for that would imply it had non-existing elements (since only computable things exist).

Can we design a set theory this way? How much of traditional set theory can be translated? Does we lose any good mathematics this way?

Whereas people seem to view uncomputability as a fundamental property of a problem, I tend to view it as another form of self-reference paradoxes. All "well-defined" problems are computable. Again, this is not a theorem or mathematical insight, but a re-definition, just like my "R only has countably many existing numbers" is a definition. But the point isn't just to change names and keep everything the same... it's to change the intuition that goes with the names.

Comments

[spoonless.livejournal.com]

Interesting theory... I've considered things like this, but they always seem to run into problems and awkwardness, if not outright contradictions.


While the set of real numbers exists (R can be expressed as the power set of N), not all of the traditional real numbers exist (only the computable ones do). So, in my definition, the cardinality of R is aleph_0 (i.e. the same as N). In fact, no set can have greater cardinality, for that would imply it had non-existing elements (since only computable things exist).

I assume you've heard of Cantor's diagonal proof that the cardinality of the reals cannot be the same as the cardinality of the natural numbers... how do you get around that with this definition? It seems to me that he doesn't assume a whole lot in that proof.

So, while the natural numbers exist, not all subsets of it do.

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.

[gustavolacerda.livejournal.com]

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.

[easwaran.livejournal.com]

Actually, I've been thinking about this lately, and I'm pretty sure that the diagonal proof still goes through, because for every computable enumeration of the computable real numbers, there is a natural way to compute the diagonalized number. So it means that although there are actually only countably many computable real numbers, there is no effective way to enumerate them. I was reading a pretty good book on this a couple years ago - I'll look it up and give you the name.

[gustavolacerda.livejournal.com]

So it means that although there are actually only countably many computable real numbers, there is no effective way to enumerate them. I was reading a pretty good book on this a couple years ago - I'll look it up and give you the name.

I'm looking forward to it.

But if the new number is "computable", this means it contains a finite amount of information, right? Yet, all computable real numbers are listed...

Cardinality

[r6.livejournal.com]

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.

Re: Cardinality

[gustavolacerda.livejournal.com]

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?

Re: Cardinality

[r6.livejournal.com]

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.

[pbrane.livejournal.com]

What do you mean by "exist"?

[gustavolacerda.livejournal.com]

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).

[pbrane.livejournal.com]

"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...).

[easwaran.livejournal.com]

I think this position actually gets at least a weak sort of constructivism, so that you have to deny excluded middle. It's possible that there is no computable proof of the Goldbach conjecture, and yet there is no computable procedure that gives an even number that isn't the sum of two primes. Actually, I probably can't even state that in the computable language.

[gustavolacerda.livejournal.com]

I think this position actually gets at least a weak sort of constructivism, so that you have to deny excluded middle.

I'd love to know what you're talking about...

[easwaran.livejournal.com]

That is, if you're only going to admit the existence of things for which a computation can be given, then I think certain existential statements will not be provable, even though a contradiction can be reached from its negation. Thus, neither the statement nor its negation will be "true" in your sense, and this is basically the intuitionist position.

[combinator.livejournal.com]

It's possible that there is no computable proof of the Goldbach conjecture, and yet there is no computable procedure that gives an even number that isn't the sum of two primes.

Well, we know that if Goldbach's conjecture is false, there exists an even number which is not the sum of two primes. A computable procedure to find it is to search exhaustively. Better yet, the number itself stands as a computable proof. So what you said is equivalent to "It's possible that there is no computable proof of the Goldbach conjecture, but it is still true." On the other hand, if Goldbach's conjecture is true, a computable procedure to find the "prime decomposition" of any even number is to search exhaustively. Then in what sense would the proof be nonconstructive?

It's almost the same with P versus NP. If P =/= NP, well, there isn't much we can do in the way of computation anyway. If P = NP, even if the proof is "noncomputable", we can actually concoct a Turing machine to compute NP in P, by exhaustively trying all Turing machines in an interleaved fashion and verifying the output of each. This procedure will take a polynomial amount of time, since as N approaches infinity, one finite Turing machine will be able to compute SAT quickly, and the overall procedure will only take a quadratic amount of extra time compared to this optimal machine. Do I need to go into more detail?

[r6.livejournal.com]

combinator is right. In other words, the Goldbach conjecture is a Π₁ sentence. Every true Σ₁ sentence is provable in PA. And every Π₂ sentence that is provable in PA is provable in HA, and hence has a computable procedure associated with it.

[rdore.livejournal.com]

How about if the Goldbach conjecture is true, but it's only provable in noncomputable ways? Then certainly there's no computable proof that it's false as well. (It's not exactly clear to me what we'd mean by a noncomputable proof in any case.)

Also I don't see why P =/= NP would have any interesting consequences on what is or isn't computable - just consequences on what is computable efficiently.

[easwaran.livejournal.com]

I should have chosen as an example some sort of existential statement for real numbers, rather than natural numbers, because of course if you prove that such a number exists, there is an effective search procedure for the naturals.

Perhaps even the least upper bound property for sets of real numbers might not turn out to be true. Certainly for recursive sets of real numbers one can construct a least upper bound, but even just recursively enumerable sets might not give an effective least upper bound.

Constructivism

[r6.livejournal.com]

I’m not sure constructivism is needed for his point of view. Perhaps gustavolacerda is just saying that L=V. Would that be sufficient?

Re: Constructivism

[gustavolacerda.livejournal.com]

what are L and V?

[rdore.livejournal.com]

You keep arguing it seems for things that 'you've never seen.' Do you believe that neutrons and protons exist? I suspect you've never 'seen' one. All the justification for them existing is indirect. The same can be true about a lot of the weird stuff physics finds out there. And a lot of that stuff is IMO much more counterintuitive than any of your objections about infinite mathematical objects.

[gustavolacerda.livejournal.com]

Sorry, I should have said "things you necessarily can't see".

I've already made this "apology" to pbrane here.

[pbrane.livejournal.com]

You might still want to be even more specific: due to confinement, you necessarily can never see a free quark, but that doesn't make them not real...

[rdore.livejournal.com]

It's unclear here even what you mean for an arbitrary set to be "computable". For a real number, this is fine. But what do you mean for a set of real numbers to be computable.

Also, as easwaran pointed out elsewhere, the set of computable functions (say from N to N) can't be put in bijection with N in any sort of natural way.

In any case, I think there are definitely "well-defined" problems without computable solutions - It's impossible to even solve all diophantine equations in a computable way, let alone if we start making claims about the real numbers.

In any case, any attempt to "fix" the self-reference paradoxes is probably doomed to failure. (Or you'll end up with a system that's very weak and more contrived than the problems youre trying to avoid.) I guess I also don't understand exactly why you're trying to change things.

[gustavolacerda.livejournal.com]

It's unclear here even what you mean for an arbitrary set to be "computable". For a real number, this is fine. But what do you mean for a set of real numbers to be computable.

This seems intuitive enough: a set S is computable iff there exists a finite terminating algorithm A such that the output of A is S.

[rdore.livejournal.com]

Do you mean any set of the form {A(n): n in N} where A is some algorithm? Or do you mean say a subset of your real numbers so that there is some algorithm A such that {A(r)=1 : r in R}?
(Those are going to be fairly different things I think.)