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]

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

[pbrane.livejournal.com]

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.

[gustavolacerda.livejournal.com]

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.

[pbrane.livejournal.com]

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

[gustavolacerda.livejournal.com]

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.

Unless you're doing it for expediency reasons, the fact that you use Occam's razor is due to your metaphysical theory. (i.e. we believe simple explanations tend to be true more often than complicated ones)

"Those who explicitly have a philosophy use an implicit one without realizing it."

Fredkin starts from an interesting metaphysical assumption. I know way too little to judge it further. But who knows, maybe it will be easier to understand things / make new discoveries if physicists start thinking this way.

[pbrane.livejournal.com]

The only part which uses Occam's razor is the "preferring fewer moving parts" part of it - the rest is just, "we describe what we observe", and so far, we've reached most of the conclusions of modern science with the premise of continuity. It's not *logically necessary* for there to be arbitrarily accurate continuity, but so far, that's all we have evidence for. But in some sense, Occam's razor in science is just for expediency: we don't claim that any model "is" the real world - it's just a model of it, and the more accurate the model, for the least amount of work, the better.

But who knows, maybe it will be easier to understand things / make new discoveries if physicists start thinking this way.

Possible, but so far, in the history of science, we typically have discretized continous things for computational purposes (recently) or to avoid singular problems that were artifacts of the construction (which we could remove and then take the discretization length to zero at the end of the day).

It still doesn't seem like *meta*physical assumption, but an actual physical one, and an unjustified one at that. Show me some evidence for discreteness, or else show me some nice theoretical problems solved by the proposal, or at least show me how it simplifies current descriptions, or else I'm not sure why it's being done: just because we're scared of the infinite? Seems pretty arbitrarily limiting.

[gustavolacerda.livejournal.com]

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.

[pbrane.livejournal.com]

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.

[gustavolacerda.livejournal.com]

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?

[pbrane.livejournal.com]

Have you ever seen a non-computable Cauchy sequence?

Dude - I've only seen *finitely many* Cauchy sequences, let alone countably many. Does this mean I only believe in a finite number of them?

I believe in the intuitive concept of continuity, and I can't have that without all the noncomputable numbers, hence I believe in them too.

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