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

[pbrane.livejournal.com]

To reiterate: if you only care about the computable cauchy sequences, then you don't care about your field being complete: it won't be complete without the noncomputable ones added in as well.

[gustavolacerda.livejournal.com]

I'm revising the meaning of "number" all the way to the bottom. Only computable things are considered to exist at all.

So by saying the set is "complete" (or "closed under limit"), it is meant that "the limit of all Cauchy sequences is in the set". However, since noncomputable Cauchy sequences don't exist, then we don't have to worry about those limits.

To make things clearer, let me reconstruct everything from the bottom, with different names... Let N_ be the set of computable natural numbers.
We then define Z_ (the set of computable integers) and Q_ (the set of computable rationals). All of these coincide with their mainstream counterparts.

Then let CauchyQ_ be the set of computable Cauchy sequences with elements in Q (or Q_). This is not equivalent to CauchyQ.

Just like R is defined as the closure of Q under limits(CauchyQ), we shall define R_ to be the closure of Q_ under limits(CauchyQ_) (i.e. the limits of computable Cauchy sequences over Q).

R_ is by definition a complete extension of Q_ (again, it's not complete over noncomputable Cauchy sequences, in the same way that R isn't complete over the complex numbers).

One flaw with my proof in the previous comment, though, is that just one step of adding limits to the set isn't enough to prove closure. But regardless, even with countably many steps, each adding countably many points, you're still in the realm of the countable.

Countably many steps are enough to prove closure: nobody can look farther than that.

[pbrane.livejournal.com]

Then let CauchyQ_ be the set of computable Cauchy sequences with elements in Q (or Q_). This is not equivalent to CauchyQ.

Ok, so in fact, CauchyQ_ is a countable subset of CauchyQ (which is itself an uncountable set of sequences).

Defining R_ as the closure of Q under limits(CauchyQ_) is fine, but it won't be *complete*, in the technical sense: there exist convergent sequences in R_ whose limits are not in R_. R does not have this property: all convergent sequences in R reach a limit which is in R.

You can use your R_, but it's not complete. R doensn't need to be complete over the complexes: completenes isn't like algebraic closure - it's defined completely within the set itself: there are no sequences in R which converge to a complex number not in R.

[pbrane.livejournal.com]

To say it another way: R is closed under repeated application of "take all Cauchy sequences in [ ], and close under limits". R_ is not - this is another way to phrase completeness, and R is the unique (ordered) field with this property.

[gustavolacerda.livejournal.com]

Defining R_ as the closure of Q under limits(CauchyQ_) is fine, but it won't be *complete*, in the technical sense: there exist convergent sequences in R_ whose limits are not in R_.

...namely the non-computable convergent sequences.

Ok. So we need to redefine "complete" as well. But this will make no difference in practice (except perhaps for mathematical expediency). Am I wrong?

---------------------

the following was written before I understood what you meant:

So, it is complete over computable convergent sequences.
We iterate countably many times, each time adding the limits of all the computable Cauchy sequences. After each iteration, we remain countable. Note that at each step, there will be new *uncomputable* sequences possible.

But if there ever exist computable convergent sequences whose limits are not in R_ yet, our algorithm will take care of them in the next iteration.

[pbrane.livejournal.com]

Ok. So we need to redefine "complete" as well. But this will make no difference in practice (except perhaps for mathematical expediency). Am I wrong?


Oh this is different. 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).

But the real practical difference between "complete under computable cauchy sequence limit-taking" and the traditional "complete" is that you don't have any of the nice properties that we use in analysis - existence of least upper bounds, and in general just existence of limits and continuity.

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.

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