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]

Your definition of complete will not, for instance, imply uniqueness of your Complete_ ordered field. There will be, in fact, uncountably many of them (each including a field completion after adding one new uncomputable real number, and closing under computable sequences).

Well, if you're adding uncomputable real numbers to it, it will obviously not be unique.

But even among those, it is the Complete_ extension of Q one.
All minimal completions_ of Q will yield this same set.


I was never an analyst, but right away, it looks like you'd run into problems all over the place in calculus: taking lim (f(x+h) - f(x)) / h, where you're only allowing computable numbers for x and h, and only a computable function for f, seems like proving that limit even exists *as a computable number* would be really hard without the traditional definition of limits.

Actually, it's easy.

First of all, the fact that you can express it finitely would already mean that it has a computable intension (i.e. 'lim (f(x+h) - f(x)) / h').

Secondly, I think we can easily make an algorithm that converges to this limit... just keep halving h, and it will get arbitrarily close to the limit. Everything is still computable: give me any computable precision >0, and the algorithm will give you a good enough approximation.

I think continuity can be similarly simulated, as well as l.u.b. (we're taking the lub of a computable set. Since the set is computable, take the algorithm generating the set, and whenever an element e is generated, if (e > max) max:= e; ) Although, there is no guarantee on how long it will take the algorithm, it will only take as long as the algorithm generating the set.

A consequence is that the lub will always be contained in the set.

I wonder what happens to open sets, like (0,1), when replaced with (0,1)_ . Maybe we lose topology.

[pbrane.livejournal.com]

Hmmm... like I said, I'm not an analyst, but my intuition is that by giving up uncountability you're going to lose basically all of analysis (and hence topology and differential geometry, etc...), and not just in a "ease of use" way.

I'm just not sure how to demonstrate exactly what you lose, and how. Maybe it's based on the intuition that we never state whether something we're dealing with is computable or not (sometimes it's obvious that we've got something that's associated with an algorithm, sometimes not), and when we aren't sure, the results that pop out are of indeterminite computability, and your system will be very fragile to insertion of any noncomputable elements - whenever they enter, the whole system can come crashing down if they're not dealt with properly.

It seems that Godel's theorem will stick you with undecidables somehow too, but that's a whole 'nother kettle of fish, and one you seem to be willing to ignore because it deals with self-reference (although even this I'm not sure how consistent that view is either...)