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

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

[easwaran.livejournal.com]

No, that's the point - you can't enumerate the computable numbers in a computable way. You can enumerate all the Turing machines, but many of them just never halt on some inputs, so they don't compute a real number. So the enumeration isn't an enumeration of the computable reals. The diagonal argument doesn't work in that case because some of the diagonal entries will be the non-halting ones, so they can't be flipped.

[gustavolacerda.livejournal.com]

That's even easier then!
When does the diagonalization argument go through then?

[easwaran.livejournal.com]

Diagonalization requires that every entry in the table be well-defined, so we see that there is no recursive enumeration of the recursive functions, though there is of the partial recursive functions. Though I believe there is no enumeration without repetition of the partial recursive functions.

[gustavolacerda.livejournal.com]

Diagonalization requires that every entry in the table be well-defined,

so we see that there is no recursive enumeration of the recursive functions,

Hmmm... ok: if there were a computable enumeration of the computable real numbers, then we could use the diagonalization algorithm to add a new computable real number (since all the inputs are computable) (of course, this also means it has finite information, which I think is equivalent to being computable). Therefore, there is no computable enumeration of the computable real numbers.
Is this your proof?

[easwaran.livejournal.com]

Exactly.

[easwaran.livejournal.com]

The book is "Computability: a mathematical sketchbook", and is a Springer GTM by Bridges. I'm pretty sure that Bridges is actually heavily involved in the project of Bishop's constructive analysis, which I guess makes sense why I would associate this definition of real numbers with intuitionism then.