Mathematical Structures + subj/obj

From: Marchal <>
Date: Fri Jul 16 12:15:37 1999


Some comments about Devin Harris, Hal Finney, Alasdair Malcolm's
posts concerning mathematical structures.
I finish by a short comment on a short question by Wei Dai to
Hans Moravec, concerning subjectivity/objectivity.

Devin Harris wrote:

> Bruno Marchal wrote:
>> My answer was that I don't see how Tegmark can make this challenge
>> effective because the collection of mathematical structures is
>> not definable in mathematical terms.
>The point could be that there is no collection of mathematical
>structures that are not definable in mathematical terms.

This is rather similar in spirit to some constructive axiom like
Brouwer's "all functions are continuous". Of course such axioms
are in general just in contradiction with classical logic. But
their intended logic are in general weaker logic. For exemple
Brouwer's axiom "all functions are continuous" make perfect sense
in some formalised intuitionistic analysis.

>mathematical structures necessarily have in common an existence.

This does not necessarily help. You could have said that all
mathematical structure have in common the fact that they ere equal
to themselves. But this does not help to give existence to the
set V = {x : x = x} in naive set theory. Of course today we would use
kind of "special" set theory which make possible the mathematical
*structuration* of the mathematical universe.
All first attempts leads to contradiction. Today you can work with
NF (The Quine New Foundation formalisation of set) with a Universal
Set. Nobody is really sure it is consistent, but nobody know for sure
it is not. NF is very different from the better knowed ZF (Zermelo
Fraenkel Theory).
More generaly you can use any sufficiently big untyped universe.
Category theory provides tools for doing this in a clean way.
(I can give you references).

>Existence is fundamental. There is no middle ground or alternative.
>Systems don't partially exist because there is no other state. There
>isn't even a choice between existing or not existing. Non-existence by
>definition cannot be.

Mmmh... My (humble) opinion is that "existence" is relative.

>There is no such thing; no meaning to the
>anomalous idea that something doesn't exist.

I like the idea, but I would put in in the relative way. Everything
exist for the genuine observer who can looks at things from
some angle. I would say that there is no meaning to the
anomalous idea that something doesn't absolutely exist, except that
I don't believe in square circle or transcendantal fraction.

>There is no such
>alternative. There is only being. That existence becomes what we think
>of as a mathematical system and all mathematical structures are subsets
>of the one elementary math.

Euh ... This is a little to vague.

>Consequently it is wrong to imagine two
>mathematical structures that have no relationship to one another or
>somehow form realities that are ultimately incompatible and

This raises a nice question. In this list lot of people seems
to appreciate that, in some sense, every world exists.
But, does this necessarily implies that every worlds are accessible.
I maintain that if you keep classical logic, the all-accessibility
will lead you into a contradiction or trivialness. It is your
choice to choose a weaker logic, or a suitable frame where
all-accessibility axiom can make sense.

>This is to say, there is, always has been, and always
>will be, a universe. And there is no place the universe is not.

As far I can understand what you are saying here, I want to say
I am not quite sure about that. But it is very vague.
Does "universe" means the mathematical universe, the physical
universe, the MW, the universal object in an untyped formalisation
of mathematics ...

You know, I tend to belief in universal turing machines and in their
extravagant dreams ... and not a lot more ...
And this entails curiously enough (perhaps) that I belief in the
MWI interpretation of QM (and of Arithmetical Truth) ...
More on this below.


Hal wrote:

>Does Tegmark attempt to define rigorously what is a "mathematical
>structure"? I recall his chart showing different mathematical objects
>and their relationship, groups, rings, fields, integers, etc.

It seems to me that Tegmark is not really aware of the problem
of what is mathematical truth and all the problematic of the foundation
of mathematics. A recent good book is Feferman's book "In the light
of Logic". I recommand a serious reading for those who (unlike me) want
 pursue Tegmark's idea to put an ontology on the "whole mathematics".
But the whole task will be disappointing.
My feeling is that "mathematics" as a whole simply doesn't exist, neither
objectively, neither subjectively.

> Perhaps we candefine a mathematical structure as a formal system?
>A formal system consists of axioms and rules of inference. Its
>theorems are those things which can be proven by starting with the
>axioms and applying the rules of inference.

Only a very tiny part of the possible mathematical structures can be
formalised or axiomatized.
There is no possible formalisation of Arithmetical Truth.
This is a consequence of Godel's Theorem.

This is not a problem for the daily mathematician which
work with formalisable structures by construction. But it is a problem
those who want make real the whole mathematics, especially
if they want put some kind of measure on it.
The daily mathematicien is more concern with organising his knowledge
than to find an ontological foundation for it. I guess that category
theory will provided some helps for them. I don't know.

>At a somewhat lower level, it consists of a language, which is the set
>of letters or characters in which theorems are written, and possibly
>some rules about which strings of characters are well formed. The
>axioms are then strings, and the rules of inference tell how to turn
>one string into another.
>We can enumerate all possible theorems by starting with all axioms and
>applying all possible rules of inference in turn. This procedure is
>somewhat like the dovetailing universal computation we have discussed
>which runs all programs at once.
>There are obvious similarities between formal systems and Turing Machine
>computations. In each case we start with an initial state and have rules
>for evolving the state forward. The set of possible successor states
>is implicitly determined by the initial state and rules, but usually
>the only way to actually learn what they are is to work the procedure
>forward and see what states (theorems) develop.

Indeed. Note that you can add "differential equation". For them too:
we start with an initial state and have rules for evolving the state
forward. The set of possible successor states is implicitly
determined by the initial state and rules, but usually the only way to
actually learn what they are is to work the procedure forward and see
what states (theorems) develop.

>Can this analogy be made tighter? Can we say that for each TM there
>is a formal system whose theorems are the successor states of the TM
>(tape + head)? Contrariwise, can we say that for each formal system
>there is a TM which implements it? I'm sure these questions have been
>studied but I am not familiar with the literature.

You can make an tight analogy between a decidable (completetely
axiomatizable) system and a recursive set (a total machine) and you can
make a tight analogy between a semi-decidable (axiomatizable system)
with a recursively enumerable set (a partial machine).
This is known as Post-Turing thesis, and
formidable papers are those by Reinhaerdt (I will look for the
My feeling is that Post-Turing thesis and Church Thesis are equivalent,
you know, these question themselves has been formalized. I can even ask
question to my (quantified version of) etalon philosophy (G, G*, S4Grz,
Z, Z1, Z*, Z1*). Sometimes I suspect that some internal version of
Church's Thesis could be unsastified.

Now the whole problem is to extend that analogy in the tranfinite.

You can see *theoretical computer science* as a branch of mathematics.
You can even see it as a branche of integer number theory. But
computer science is typically not *completely* formalisable.
Now you can axiomatize portion of it.
The parts which will provably accessible by a Turing Machine will
to some constructive or recursive ordinal. And beyond ?
Beyond : because you can also be interested in parts accessible by some
Turing Machine but in a necessary non provable ways. Or in a provable
 but not in a bornable time, or space.
Or in provable time relatively to the halting problem. After all
we can also be interested in Turing Machine embedded in a kind of
dovetailer and which bet "NON-STOPPING", in front of any machine
non-stopping machine. In each case a machine is wrong, she will "know
it". In some sense such machine is less and less wrong. And there is a
sense to study mathematically the projection or the limit of the set of
"beliefs" of these machines...
So we will arrived to descriptive set theory and eventually to analytical
sets, ...

So your question is really extraordinarily complex. With comp, it is
ultimately linked to the question of the mathematical learning abilities
of sequence of evolving collection of Turing machines.
A very good recent textbook is "Systems that Learn" by Jain, Osherson,
Royer,Sharma. MIT press 1999. It is at the intersection of
limit computing (Gold) and theoretical artificial intelligence (Putnam,
Myhill, Case etc.). It relies heavily on recursion theory.
The whole field is going in the direction that in the limit the machine
will ask more questions than solve problems (my modest intuition).

>If the answers turned out to be affirmative, it would unify the
>Schmidhuber and Tegmark approaches [...]

I think so. I think that Church Thesis and some 'constructive'
mathematics could unify both approach.
The problem is that neither Schmidhuber nor Tegmark seems aware
of the measure problem linked to the reversal entailed by,
essentially the fact that, like Everett, they embeds the "observer" in
the "observed thing".
This is a little weird because the very originality of Everett, is that
he takes into account the discourse of the machine, and, in physics,
is the first to explicitely distinguish the first person (subjective)
view and the third person (objective) view.
The distinction is implicit in Galilee and Einstein.

> [...] and move us closer to the goal of a
>model which is so simple that it must be true.

Although, as an (Arithmetical or Pythagorean !) Platonist I like
very much the idea of equating truth and simplicity, I must say
that my pragmatical realism attracts my attention to the fact that
the very presence
of only one universal turing machine in our neighborhood will make the
relation between truth and simplicity a glorious and Platonic ideal.

But there is another problem here. And it is linked with the problem of
talking of the *whole mathematical reality.*
Chris proposes us today model theory as a tools for our investigations.
Good idea, but proof theory is needed here too.
To prevent misunderstanding, model, for the logician (and the painter),
a "reality" (essentially a valuation of the propositions of a language in
some truth set, for exemple {0, 1}). A theory (the painting) is the little
syntactical capture of the intended model.

Now, with theories sufficiently rich to add and multiply numbers, we know,
by Godel first incompleteness, that you can never syntactically defined
the big pictures, at each step (even recursive transfinite) you get still
an infinity of non-isomorphic models.
In fact it is the relation between theories/proof and
models/transformation-of-model which are interestings.
There is a *Galois connection* between theorie and models.
Adding axiomes in a theory = substracting models for that theory.

If we take your principle of simplicity, we should choose the simplest
theory which has ever existed : the empty theory. This theory is one
which admit the most models. Indeed in no model at all could you make the
theory wrong. But here the link is rather trivial.

But I have the same intuition than you and I take the next simplest
theory which is: "there is a universal turing machine here".
And then the miracle occurs for, as Godel admits, Church's thesis makes
computability an absolute notion, the UTM gives a sort of universal object
 and a kind of untyped universe, and ... and everything we need to unify
Tegmark and Schmidhuber (your term).

The galois connection and the weakness of the axiom of UTM existence
make possible a very large "everything" theory or frame, yet nameable!


Alasdair Malcolm wrote:

>The general problem here seems to be that if one has a scheme that differs
>in any way from Tegmark's hypothesis, then it is subject to Tegmark's
>category 1b
>challenge: 'why are only *these* mathematical structures implemented?'

In fact both Tegmark and Deutsch (in his critics of Wheeler) don't
realise (IMHO) that mathematical (even arithmetical) truth in not
analytical (in Kant's sense).
There is no completely objectifiable mathematics (notion of proofs).
With Church's thesis, there is an absolute notion of computability + the
immense variety of definable truth sets associated with machines.

So the answer is :only *these* mathematical structures are meaningfull for
an UTM, in term of UTMs.
There is no equivalent notion of 'whole' for mathematical truth as the
term is used by Tegmark.

With Church's thesis (and stronger version ...) it is not at all a
restriction. And with comp, in some way the splashed UTM (UD*) is a
well defined, shallow, mathematical whole.


Wei Dai wrote (to Hans Moravec):

>Why do you believe that subjectivity is a subjective attribute? Could
>subjectivity not be an objective attribute?

Good question (IMHO). I would also ask:
Do you think there is an objective notion of 'objectivity'. Or is
'objectivity' a purely subjective notion ?

Those who follows my posts can guess that my objective notion
of 'objectivity' is inter-subjectivity or 'relative subjectivity'
So I need an 'objective' notion of subjectivity.
Here, in the UTM interview (alias chapter 5, alias etalon philosophy)
I use the theetetic definition of the knower.

But, in the mechanist thought experiments, I use the first/third
person distinction for memory-machine like Everett.
Note that Everett use 'inside' and 'outside'
instead of 1/3-person, but it is equivalent.


Have a nice week-end or a nice week, Bruno.
Received on Fri Jul 16 1999 - 12:15:37 PDT

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:06 PST