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

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

[gustavolacerda.livejournal.com]

hm... well, to define a set of real numbers, we first have to define real numbers. As I've discussed in some comments, we need to think of real numbers as algorithms (for example, pi can only be expressed as an algorithm: its exact value is not computable, and yet we say pi is computable)

A computable subset S of the reals (or a recursive subset) is defined by an algorithm A which, for all real numbers r (actually, I should say "for all algorithms generating real numbers") will return 1 iff r is in S, and 0 otherwise. That is, A returns 1 exactly for the inputs which are in S, and 0 for the ones not in S.

I can imagine, though that some subsets of R, while not recursive, will be recursively-enumerable... i.e. like the above definition, minus the "and 0 otherwise" part. This way you can define sets for which there are numbers which are not in the set, but which you can never know.

[rdore.livejournal.com]

Testing the equality of two real numbers under your system is not possible.
So, for example, the set containing just the real number zero is not a computable set. This set is not recursively enumerable (although its compliment is.)

[gustavolacerda.livejournal.com]

for example, the set containing just the real number zero is not a computable set.

why not? I can imagine an algorithm which will return "1" if and only if the input is a computable expression of 0:

(defun is-in-{0} (x)
"returns 1 if x in {0}, 0 otherwise"
(if (eq (evaluate x) 0) 1
0)))

hmm... one problem is that "evaluate" wouldn't halt if you give it an uncomputable number. But hang on... you can't pass an uncomputable number, because by definition you can't express it.


I can imagine some difficulties in e.g. testing the equality of two different algorithms for pi. So if you had a set with both of them, it might be hard to show that its cardinality is actually 1.

[rdore.livejournal.com]

The problem is, comparison between real numbers is not computable.
Suppose you had Equal(x,y).
Well Equals can only look at finitely many digits in finite time. So you can change the ones beyond that and it gives the same answer.

[gustavolacerda.livejournal.com]

Well Equals can only look at finitely many digits in finite time.

Right, that's the problem I mentioned about comparing the two expressions of pi.

But in a way, this isn't a bad thing about the system: it's simply modeling real life! In real life, we don't have a general way of telling when two expressions are equal.

What concrete thing could do with the standard real numbers that you couldn't do here?

[rdore.livejournal.com]

What concrete thing could do with the standard real numbers that you couldn't do here?

I want to be able to state whether two objects are equal. Similarly, maybe I can't tell whether a given program will terminate or not, but clearly it *does* terminate or it *doesn't*.

Do you seriously want a logic system where
{(x,y,z)| x,y,z reals and x+y=z}
is not an object that exists?

Like I mentioned in another post, determining if multivariate polynomial equations have integer solutions is an uncomputable problem.

Asking questions about what can be done computably is an interesting and worthwhile problem. But I think its a bit goofy to actually define mathematics as only such problems. It seems like saying physics can only talk about things we can see with the naked eye.

[gustavolacerda.livejournal.com]

dang... I screwed up the definitions. That definition was only for extensionally computable sets.

Obviously {(x,y,z)| x,y,z reals and x+y=z} is an existing set, since you expressed it finitely. So of course it's a computable subset of the reals: but only intensionally.

However, membership in this set is not decidable, since equality is not decidable (neither is it in the regular real numbers).


It seems like saying physics can only talk about things we can see with the naked eye.

I think of atoms as having a more objective existence than uncomputable real numbers, whatever this means.

However, your analogy makes sense in some sense: physics must be grounded in the things we can see with our naked senses. Even the things we see through microscopes are eventually interpreted by our naked eyes.

And this is exactly the point. I'm trying to define mathematics in terms of its interaction with real people. And real people never see uncomputable objects: so their status is necessarily "theoretical".

[rdore.livejournal.com]

But a major point of mathematics is that we can infer the existence of things that we can't tangibly deal with.

[gustavolacerda.livejournal.com]

I don't know what point you're trying to make, but to me everything must return to the source: there must be a reason for us to create abstractions.

The reason we do logic is because what we derive syntactically we can also observe to hold semantically. To me, this is essential to the nature of mathematics. (it never lies, as an old teacher of mine used to say)

Theoretical terms are nice: useful, expedient and even perhaps pointing towards some fundamental truth. But uncomputable objects are not theoretical terms, as in fact they are fundamentally inexpressible. In other words, they don't exist.

Can you express your point better-ly?

[rdore.livejournal.com]

But uncomputable objects are not theoretical terms, as in fact they are fundamentally inexpressible. In other words, they don't exist.

Why do you feel that undefinable means doesn't exist? My main objection is that you claim these two things are the same.

(Also, it is possible to quite explicitly describe real numbers which aren't computable. But that's another can of worms.)

The reason we do logic is because what we derive syntactically we can also observe to hold semantically. To me, this is essential to the nature of mathematics.

You seem to view logic as nothing more than rule pushing. From this definition, what you say is trivially true. I think of logic much more as reasoning about how we reason.

Also, you seem to use 'logic' and 'mathematics' interchangably, which seems to me like calling biology a branch of physics - in a sense is is, but that's not how anyone actually studies it.

[rdore.livejournal.com]

My real point is that in addition to being fairly vague, your logical system lacks all sorts of reasonable things. The reality is that the logical paradoxes you're trying so hard to avoid are fairly fundamentally a part of any system which can express much of anything interesting.

[gustavolacerda.livejournal.com]

oh, am I trying to avoid paradoxes?

I thought I was just looking for a way to do mathematics without postulating things that don't exist.