Observational Consequences:

1. Provides a possible explanation for the "Measure Problem" of why we
shouldn't be "extremely surprised" to find we live in a lawful
universe, rather than an extremely chaotic universe, or a homogeneous
cloud of gas.

2. May help solve the Doomsday Argument in a finite universe, since
you probably have at least a little more "measure" than a typical
specific individual in the middle of a Galactic Empire, since you are
"easier to find" with a small search algorithm than someone surrounded
by enormous numbers of people.

3. For similar reasons, may help solve a variant of the Doomsday
Argument where the universe is infinite. This variant DA asks, "if
there's currently a Galactic Empire 10000 Hubble Volumes away with an
immensely large number of people, why wasn't I born there instead of
here?"

4. May help solve the Simulation Argument, again because a search
algorithm to find a particular simulation among all the adjacent
computations in a Galactic Empire is longer (and therefore, by UD
+ASSA, has less measure) than a search algorithm to find you.

5. In basic UD+ASSA (on a typical Turing Machine), there is a probably
a strict linear ordering corresponding to when the events at each
point in spacetime were calculated; I would argue that we should
expect to see evidence of this in our observations if basic UD+ASSA is
true. However, we do not see any total ordering in the physical
Universe; quite the reverse: we see a homogeneous, isotropic Universe.
This is evidence (but not proof) that either UD+ASSA is completely
wrong, or that if UD+ASSA is true, then it's run on something other
than a typical linear Turing Machine. (However, if you still want use
a different machine to solve the "Measure Problem", then feel free,
but you first need to show that your non-Turing-machine variant still
solves the "Measure Problem.")

Decision Theory Consequences (Including Moral Consequences):

Every decision algorithm that I've ever seen is prey to paradoxes
where the decision theory either crashes (fails to produce a
decision), or requires an agent to do things that are bizarre, self-
destructive, and evil. (If you like, substitute 'counter-intuitive'
for 'bizarre, self-destructive, and evil.') For example: UD+ASSA,
"Accepting the Simulation Argument", Utilitarianism without
discounting, and Utilitarianism with time and space discounting all
have places where they seem to fail.

UD+ASSA, like the Simulation Argument, has the following additional
problem: while some forms of Utilitarianism may only fail in
hypothetical future situations (by which point maybe we'll have come
up with a better theory), UD+ASSA seems to fail *right here and now*.
That is, UD+ASSA, like the Simulation Argument, seems to call on you
to do bizarre, self-destructive, and evil things today. An example
that Yudowsky gave: you might spend resources on constructing a unique
arrow pointing at yourself, in order to increase your measure by
making it easier for a search algorithm to find you.

Of course, I could solve the problem by deciding that I'd rather be
self-destructive and evil than be inconsistent; then I could consider
adopting UD+ASSA as a philosophy. But I think I'll pass on that
option. :-)

So, more work would have to be done the morality of UD+ASSA before any
variant of UD+ASSA can becomes a realistically palatable part of a
moral philosophy.

-Rolf

>
> (Warning: This post assumes an familiarity with UD+ASSA and with the
> cosmological Measure Problem.)

I am afraid you should say a little more on UD + ASSA. to make your
points below clearer. I guess by UD you mean UDist (the universal
distribution), but your remark remains a bit to fuzzy (at least for me)
to comment.
Of course I am not convinced by ASSA at the start, but still. The
absence of recation of ASSA defenders is perhaps a symptom that you are
not completely clear for them too?

Bruno

http://iridia.ulb.ac.be/~marchal/

Rolf Nelson wrote:
> 1. Provides a possible explanation for the "Measure Problem" of why we
> shouldn't be "extremely surprised" to find we live in a lawful
> universe, rather than an extremely chaotic universe, or a homogeneous
> cloud of gas.

One thing I still don't understand, is in what sense exactly is the "Measure
Problem" a problem? Why isn't it good enough to say that everything exists,
therefore we (i.e. people living in a lawful universe) must exist, and
therefore we shouldn't be surprised that we exist. If the "Measure Problem"
is a problem, then why isn't there also an analogous "Lottery Problem" for
people who have won the lottery?

I admit that this "explanation" of why there is no problem doesn't seem
satisfactory, but I also haven't been able to satisfactorily verbalize what
is wrong with it.

> Of course, I could solve the problem by deciding that I'd rather be
> self-destructive and evil than be inconsistent; then I could consider
> adopting UD+ASSA as a philosophy. But I think I'll pass on that
> option. :-)

I think our positions are pretty close on this issue, except that I do
prefer to substitute 'counter-intuitive'. :-) The problem is, how can we be
so certain that our intuitions are correct?

> An example
> that Yudowsky gave: you might spend resources on constructing a unique
> arrow pointing at yourself, in order to increase your measure by
> making it easier for a search algorithm to find you.

While I no longer support UD+ASSA at this point (see my posts titled
"against UD+ASSA"), I'm not sure this particular example is especially
devastating. UD+ASSA perhaps implies an ethical theory in which all else
being equal, you would prefer that there was a unique, easy to find arrow
pointing at yourself. But it doesn't say that you should actually spend
resources constructing it, since those resources might be better used in
other ways, and it's not clear how much one's measure would actually be
increased by such an arrow.
 

On Oct 24, 9:25 pm, "Wei Dai" <wei...@weidai.com> wrote:
> Rolf Nelson wrote:
> > 1. Provides a possible explanation for the "Measure Problem" of why we
> > shouldn't be "extremely surprised" to find we live in a lawful
> > universe, rather than an extremely chaotic universe, or a homogeneous
> > cloud of gas.
>
> One thing I still don't understand, is in what sense exactly is the "Measure
> Problem" a problem? Why isn't it good enough to say that everything exists,
> therefore we (i.e. people living in a lawful universe) must exist, and
> therefore we shouldn't be surprised that we exist. If the "Measure Problem"
> is a problem, then why isn't there also an analogous "Lottery Problem" for
> people who have won the lottery?

I don't have anything novel to say on the topic, but maybe if I
restate the existing arguments, that'll help you expand on your
counter-argument.

The "Lottery Problem" would be a problem if I kept winning the lottery
every day; I'd think something was fishy, and search for an
explanation besides "blind chance", wouldn't you?

Let's rank some classes of people, from chaotic (many rules) to lawful
(few rules):

1. An infinite number of people live in "an infinite universe that
obeys the Standard Model until November 1, 2007, and then adopts
completely new laws of physics." If you live here, we predict that
strange things will happen on November 1.

2. An infinite number of people live next-door in "an infinite
universe that obeys the Standard Model through all of 2007, and maybe
beyond." If you live here, expect nothing strange.

3. An infinite number of people live across the street in "a universe
that looks like it obeys the Standard Model through November 1, 2007
because we are in the middle of a thermodynamic fluctuation, but the
universe itself is extremely lawful, to the point where it's just a
homogeneous gas with thermal fluctuations." We predict that strange
things will happen on November 1.

Your observations to date are consistent with all three models. What
are the odds that you live in (2) but not (1) or (3)? Surely the
answer is "extremely high", but how do we justify it *mathematically*
(and philosophically)? If we can find mathematical solutions to
satisfy this "Measure Problem", we can perhaps see what else that
mathematical solution predicts, and test its predictions. Your UD+ASSA
is the best solution I've seen so far, so I'm surprised there's not
more interest in UD+ASSA (or some variant) as a "proto-science".

>From the view of a potential scientific theory (rather than a
philosophical "formalization of induction"), it's a *good* thing that
it predicts "no oracles exist", because that is a falsifiable (though
weak) prediction.

>
> Rolf Nelson wrote:
>> 1. Provides a possible explanation for the "Measure Problem" of why we
>> shouldn't be "extremely surprised" to find we live in a lawful
>> universe, rather than an extremely chaotic universe, or a homogeneous
>> cloud of gas.
>
> One thing I still don't understand, is in what sense exactly is the
> "Measure
> Problem" a problem? Why isn't it good enough to say that everything
> exists,
> therefore we (i.e. people living in a lawful universe) must exist, and
> therefore we shouldn't be surprised that we exist. If the "Measure
> Problem"
> is a problem, then why isn't there also an analogous "Lottery Problem"
> for
> people who have won the lottery?
>
> I admit that this "explanation" of why there is no problem doesn't seem
> satisfactory, but I also haven't been able to satisfactorily verbalize
> what
> is wrong with it.

Perhaps there can be a measure problem with the ASSA, or not. I have no
idea because I think the ASSA idea, before having a measure problem,
has a reference class problem. We don't know what is the set or class
on which the measure can bear. If we say "observer", "observer-moment",
"observer-life" etc... we have to define observer first, and each time
this is done, it looks like I should be a bacteria instead of a human,
or the measure cannot be well defined, or it presuppose a "physical
world", etc. (see my old critics on ASSA, or on the Doomsday Argument.

Now, with the COMP (and thus the RSSA), things change.The reference
class is utterly well defined. For example, in the WM-duplication, it
is the set {W,M}. In front of the UD, the reference class, although it
is a non constructive object, it is, thanks to Church Thesis, a
perfectly well defined mathematical object: it is the set of all
states, going through your current state, generated by the DU. And the
measure problem is made equivalent with the white rabbits problem (due
to the existence of consistent but aberrant computations/histories (an
history, I recall, is a computation as viewed from a first person
perspective).

If you disagress with this, it means you stop somewhere in between the
first seven step of the 8-steps version of the UDA as in the slides
http://iridia.ulb.ac.be/~marchal/publications/SANE2004Slide.pdf
with explanations in
http://iridia.ulb.ac.be/~marchal/publications/SANE2004MARCHAL.htm      
(html document), or
http://iridia.ulb.ac.be/~marchal/publications/SANE2004MARCHAL.pdf      
(pdf document).

I would be interested to know where.

>
>> Of course, I could solve the problem by deciding that I'd rather be
>> self-destructive and evil than be inconsistent; then I could consider
>> adopting UD+ASSA as a philosophy. But I think I'll pass on that
>> option. :-)
>
> I think our positions are pretty close on this issue, except that I do
> prefer to substitute 'counter-intuitive'. :-) The problem is, how can
> we be
> so certain that our intuitions are correct?
>
>> An example
>> that Yudowsky gave: you might spend resources on constructing a unique
>> arrow pointing at yourself, in order to increase your measure by
>> making it easier for a search algorithm to find you.
>
> While I no longer support UD+ASSA at this point (see my posts titled
> "against UD+ASSA"), I'm not sure this particular example is especially
> devastating. UD+ASSA perhaps implies an ethical theory in which all
> else
> being equal, you would prefer that there was a unique, easy to find
> arrow
> pointing at yourself. But it doesn't say that you should actually spend
> resources constructing it, since those resources might be better used
> in
> other ways, and it's not clear how much one's measure would actually be
> increased by such an arrow.

I am not sure who "reads" that arrow, or even what *is* that arrow.

Bruno

http://iridia.ulb.ac.be/~marchal/

Rolf Nelson wrote:
> Your observations to date are consistent with all three models. What
> are the odds that you live in (2) but not (1) or (3)? Surely the
> answer is "extremely high", but how do we justify it *mathematically*
> (and philosophically)?

My current position is, forget the "odds". Let's say there is no odds,
likelihood, probability, degrees of confidence, what have you, that I live
in (2) but not (1) or (3). Instead, I'll consider myself as living in all of
(1), (2), and (3), and whenever I make any decisions, I will consider the
consequences of my choices on all of these universes. But the end result is
that I'll still act *as if* I only live in (2) because I simply do not care
very much about the consequences of my actions in (1) and (3). I don't care
about (1) and (3) because those universes are too arbitrary or random, and I
can defend that by pointing to their high algorithmic complexities. So this
example does not seem to support the notion that the "Measure Problem" needs
to be solved.

> The "Lottery Problem" would be a problem if I kept winning the lottery
> every day; I'd think something was fishy, and search for an
> explanation besides "blind chance", wouldn't you?

If I kept winning the lottery every day, I would have the following
thoughts: There are two types of universe where I've won the lottery every
day, those where there's a reason I've won (e.g., it's rigged to always let
one person win) and those where there's no reason (i.e. I won them fair and
square). I am living in universes of both types, but I care much more about
those of the first type because they have lower algorithmic complexities.
Therefore I should act as if I'm living in the first type of universe and
try to find out what the reason is that I've won.

But what if I've won the lottery only once? I'd still be tempted to ask "why
did I win instead of someone else?" But the above rationale for searching
for an answer doesn't work, because there is no simpler universe where a
reason for my winning exists. The "Measure Problem" seems more like this
situation. In both cases, there is no apparent rationale for asking "why",
but we are tempted (or even compelled) to do so nevertheless.
 

On Oct 25, 3:25 am, Bruno Marchal <marc...@ulb.ac.be> wrote:
> Le 25-oct.-07, à 03:25, Wei Dai a écrit :
>
> > Rolf Nelson wrote:

> >> An example
> >> that Yudowsky gave: you might spend resources on constructing a unique
> >> arrow pointing at yourself, in order to increase your measure by
> >> making it easier for a search algorithm to find you.
>
> > While I no longer support UD+ASSA at this point (see my posts titled
> > "against UD+ASSA"), I'm not sure this particular example is especially
> > devastating. UD+ASSA perhaps implies an ethical theory in which all
> > else
> > being equal, you would prefer that there was a unique, easy to find
> > arrow
> > pointing at yourself. But it doesn't say that you should actually spend
> > resources constructing it, since those resources might be better used
> > in
> > other ways, and it's not clear how much one's measure would actually be
> > increased by such an arrow.
>
> I am not sure who "reads" that arrow, or even what *is* that arrow.
>
> Bruno
>

How about SAI (Super Intelligence)?  Or God?  Seriously, of course.
The problem with generic SAI is the one you brought up: how do you
know the SAI is good?  This problem does not exist with a good God.
Also the problem of what is the arrow, how do you make it, does not
exist with the Christian God, since the Christian God (and no other
one) made the arrow himself.

Tom

> How about SAI (Super Intelligence)?  Or God?  Seriously, of course.
> The problem with generic SAI is the one you brought up: how do you
> know the SAI is good?  This problem does not exist with a good God.
> Also the problem of what is the arrow, how do you make it, does not
> exist with the Christian God, since the Christian God (and no other
> one) made the arrow himself.

Hmmm.... It seems to me you are quite quick here.

Especially after reading Vance novels, as linked by Marc.

Is God good? Well, according to Plato, accepting the rather natural
"theological" interpretation of the Parmenides (like Plotinus), there
is a sense to say that God is "good", but probably not in the Christian
sense (if that can be made precise). Indeed, Plato's God is just Truth.
And Truth is not good as such, but the awareness of truth, or simply
the search of truth,  is, for a Platonist,  a prerequisite for the
*possible* development of goodness.
Truth is necessary for justice, and justice is necessary for goodness.
That's the idea. It makes knowledge (and thus truth) a good thing, in
principle.
But Vance's novel rises a doubt. Actually, that doubt can rise through
the reading of the first Pythagorean writings, which insist so much on  
hiding their knowledge to the non-initiated people, making them secret.
(according to the legend, their kill a disciple who dares to make
public the discovery of the irrationality of the square root of 2).
Maimonides also, in his "Guide for the perplexed" insists that
fundamental knowledge has to be reserved for the initiated or the elite
people.

Fundamentally I don't know. I know a lot of particular case where
knowledge can be bad. But this happens always in "human, too much
human" practical circumstances, like during war, illness, etc.  (it is
not good that your enemies *knows* where are your missiles; it is not
good to tell a bad new to some old dying people, etc. But this never
concerns fundamental truth.

I guess it *is* a question of faith. Of course, something like complete
knowledge, would be bad, making life without any purpose (at least it
is natural to fear that), but in this case both lobianity, and well,
may be things like Christianity, remind us about our finiteness and
about the fact that complete knowledge is inconsistent (even for Gods,
but not for the Unnameable, making it above thinking (something
Plotinus understood, but I am not sure Christians, following here
Aristotle theology,  take this seriously into account but then they do
have confuse temporal and spiritual power isn't it?).

Now, Tom, to come back to the present thread, i.e. Wei Dai's question
on the meaning of the measure problem with respect to the ASSA
philosophy, frankly I am not sure that saying that God is responsible
for the indexical "arrow" will put light. It looks a bit like closing
even the possibility of progressing, given that God can hardly be
invoked in any attempt to scientifically explains something (cf
"scientifically" means based on a clear and doubtable (if not
refutable) theory). So you would have to elaborate, but as we have
already discussed, to use God here would mean that you do have a
doubtable and clear theory of God. OK if you are using lobian theology
(which is cristal clear I think), but which cannot be related so easily
with any human religion without much work on both human and machine and
comp, etc. We would quickly been led to propositions far more
difficult, not to say controversial, than Wei Dai's original question.
Of course, here, those who take the primacy of a physical universe for
granted, somehow, makes the same mistake than those who take God or a
God for granted. Such moves hide the questions through incommunicable
(perhaps even false) "certitude".

Bruno

http://iridia.ulb.ac.be/~marchal/

One thing unclear is whether you're advocating "moral relativism", or
whether you simply want an "escape clause" in your formal decision
theory so that if you don't like what your decision theory tells you
to do, you can alter your decision theory on the spot on a case-by-
case basis.

Wei Dai wrote:

> I simply do not care very much about the consequences of my actions in (1) and (3).

>
> Is God good? Well, according to Plato, accepting the rather natural
> "theological" interpretation of the Parmenides (like Plotinus), there
> is a sense to say that God is "good", but probably not in the Christian
> sense (if that can be made precise). Indeed, Plato's God is just Truth.
> And Truth is not good as such, but the awareness of truth, or simply
> the search of truth,  is, for a Platonist,  a prerequisite for the
> *possible* development of goodness.
> Truth is necessary for justice, and justice is necessary for goodness.
> That's the idea. It makes knowledge (and thus truth) a good thing, in
> principle.
> But Vance's novel rises a doubt. Actually, that doubt can rise through
> the reading of the first Pythagorean writings, which insist so much on  
> hiding their knowledge to the non-initiated people, making them secret.
> (according to the legend, their kill a disciple who dares to make
> public the discovery of the irrationality of the square root of 2).
> Maimonides also, in his "Guide for the perplexed" insists that
> fundamental knowledge has to be reserved for the initiated or the elite
> people.
>
> Fundamentally I don't know. I know a lot of particular case where
> knowledge can be bad. But this happens always in "human, too much
> human" practical circumstances, like during war, illness, etc.  (it is
> not good that your enemies *knows* where are your missiles; it is not
> good to tell a bad new to some old dying people, etc. But this never
> concerns fundamental truth.

But what truth is "fundamental"?  Quantum gravity seems like an esoteric game to most people and so you can say anything you want about it without any ethical implications.  But when quantum gravity seems to provide a non-supernatural cosmogony, religions are threatened and suddenly it's like bad news to a dying man (and we're all dying).

Coincidentally, James Watson has just lost his job because he said some things that, while narrowly true, support a racist view of Africa.  Were they "fundamental"  or does "fundamental" = "of no import in society"?

Brent Meeker

Rolf Nelson wrote:
> In standard decision theory, "odds" (subjective probabilities) are
> separated from utilities. Is "how much you care about the consequences
> of your actions" isomorphic to "odds", or is there some subtlety I'm
> missing here?

Your question shows that someone finally understand what I've been trying to
say, I think.

"how much you care about the consequences of your actions" is almost
isomorphic to "odds", except that I've found a couple of cases where
thinking in terms of the former works (i.e. delivers intuitive results)
whereas the latter doesn't. The first I described in "against UD+ASSA, part
1" at
http://groups.google.com/group/everything-list/browse_frm/thread/dd21cbec7063215b.

The second one is, what if your preferences for two universes are not
independent? For example, suppose you have the following preferences, from
most preferred to least preferred:

1) eat an apple in universe A and eat an orange in universe B
2) eat an orange in universe A and eat an apple in universe B
3) eat an apple in both universes
4) eat an orange in both universes

I don't see why this kind of preference must be irrational if you believe
that both A and B exists. But in standard decision theory, this kind of
preference is not allowed.

To put it more generally, thinking in terms of "how much you care about the
consequences of your actions" *allows* you to have an overall preference
about A and B that can be expressed as an expected utility:

P(A) * U(A) + P(B) * U(B)

since P(A) and P(B) can denote how much you care about universes A and B,
but it doesn't *force* you to have a preference of this form. Standard
decision theory does force you to.

> One thing unclear is whether you're advocating "moral relativism", or
> whether you simply want an "escape clause" in your formal decision
> theory so that if you don't like what your decision theory tells you
> to do, you can alter your decision theory on the spot on a case-by-
> case basis.

That's a very good question. I think if someone were to show me an objective
decision procedure that actually makes sense, I think I would give up "moral
relativism". But in the mean time, I don't see how to avoid these
counterintuitive implications without it.

In other words, I would prioritize "UDASSA doesn't yet make many
falsifiable predictions" and "We don't see a total ordering of points
in spacetime, so UDASSA probably doesn't run on a typical Turing
Machine" as larger problems. But sure, if UDASSA can be improved to
solve the morality edge-cases that you gave, I'm all for the
improvements.

As far as our observations of the Universe, I don't quite follow: how
can you go from "in terms of morality, probability is imperfect" to
"there's no such thing as probability, therefore there's no measure
problem?"

> To put it more generally, thinking in terms of "how much you care about the
> consequences of your actions" *allows* you to have an overall preference
> about A and B that can be expressed as an expected utility:
>
> P(A) * U(A) + P(B) * U(B)
>
> since P(A) and P(B) can denote how much you care about universes A and B,
> but it doesn't *force* you to have a preference of this form. Standard
> decision theory does force you to.

True. So how would an alternative scheme work, formally? Perhaps
utility can be formally based on the "Measure" of "Qualia" (observer
moments). If you have a halting oracle, certain knowledge of a
Universal Prior, and infinite cognitive resources, you can choose your
action to maximize a utility function U(X); X is the sequence M(Q1),
M(Q2), ..., where the measures of all possible Qualia are enumerated.
In the typical case of everyday life decisions in 2007, M would often
reduce to an objective probability oP; and U(X) = U(M(Q1), M(Q2), ...)
maybe has an affine (in other words, a decision-theory-order-
preserving) transformation, for a typical 2007 human, to some function
U(how good life is expected to be for earthly observer O1, how good
life is expected to be for earthly observer O2, ...), (pretending for
now that you don't have any way of altering the "total measure" taken
up by a human being.)

"How good life is expected to be for observer O1" in turn perhaps
reduces, in typical life, to oP(O1 experiences Q1) * (desirableness of
Q1) + oP(O1 experiences Q2) * (desirableness of Q2) + ...

But now we have to say that no one actually has infinite cognitive
resources, let alone a halting Oracle. So, we probably still want a
"logical probability" lP to deal with things like "To what extent do I
currently believe that the Riemann Hypothesis is true." So you can't
choose an action to maximize U directly, instead you want to maximize
the expected utility, by maximizing the following: lP(X1) * U(X1) +
lP(X2) * U(X2) + ...

Humans would perceive, as "subjective probability", a combination of
the Measure-based "objective probability" and the logic-based "logical
probability".

Clear as mud, I'm sure. Plus the odds are that I got something wrong
in the details. But that's my take on it, anyway.

> One thing I still don't understand, is in what sense exactly is the "Measure
> Problem" a problem? Why isn't it good enough to say that everything exists,
> therefore we (i.e. people living in a lawful universe) must exist, and
> therefore we shouldn't be surprised that we exist. If the "Measure Problem"
> is a problem, then why isn't there also an analogous "Lottery Problem" for
> people who have won the lottery?

thank you Wei Dei, I have expressed something similar concerning the
Doomsday Argument which has the same reasoning flaw.

You can't reason about probabilities "inside" the system and be
surprised that you are in "location" A or B.

Example:

1) If I draw from an urn with 1 Million white balls and 1 black ball, I
should be pretty surprised if I draw the black one.

2) If I am a black ball in an urn (same distribution as above) and I
only become conscious if I am drawn and I suddenly "wake up" to find
myself drawn, I shouldn't be surprised at all - my being drawn was a
condition for being a perceptive being.

I think a mixing up of these two viewpoints underly much of "measure
problem", doomsday and other arguments of the same sort.

Regards,
Günther

--
Günther Greindl
Department of Philosophy of Science
University of Vienna
guenther...@univie.ac.at
http://www.univie.ac.at/Wissenschaftstheorie/

Blog: http://dao.complexitystudies.org/
Site: http://www.complexitystudies.org

Günther Greindl wrote:
> Hi all,
>
>> One thing I still don't understand, is in what sense exactly is the "Measure
>> Problem" a problem? Why isn't it good enough to say that everything exists,
>> therefore we (i.e. people living in a lawful universe) must exist, and
>> therefore we shouldn't be surprised that we exist. If the "Measure Problem"
>> is a problem, then why isn't there also an analogous "Lottery Problem" for
>> people who have won the lottery?

That's a good argument assuming some laws of physics.  But as I understood it, the "measure problem" was to explain the law-like evolution of the universe as a opposed to a chaotic/random/white-rabbit universe.  Is it your interpretation that, among all possible worlds, somebody has to live in law-like ones; so it might as well be us?

Brent Meeker

>
>
> thank you Wei Dei, I have expressed something similar concerning the
> Doomsday Argument which has the same reasoning flaw.
>
> You can't reason about probabilities "inside" the system and be
> surprised that you are in "location" A or B.
>
> Example:
>
> 1) If I draw from an urn with 1 Million white balls and 1 black ball, I
> should be pretty surprised if I draw the black one.
>
> 2) If I am a black ball in an urn (same distribution as above) and I
> only become conscious if I am drawn and I suddenly "wake up" to find
> myself drawn, I shouldn't be surprised at all - my being drawn was a
> condition for being a perceptive being.
>
> I think a mixing up of these two viewpoints underly much of "measure
> problem", doomsday and other arguments of the same sort.
>
> Regards,
> Günther
>
>

Rolf Nelson wrote:
> Wei, your examples are convincing, although other decision models have
> similar problems. If your two examples were the only problems that
> UDASSA had, I would have few qualms about adopting it over the other
> decision models I've seen. Note that even if you adopt a decision
> model, you still in practice (as a human being) can keep an all-
> purpose "escape hatch" where you can go against your formal model if
> there are edge cases where you dislike its results.

For me, this line of thought started with the question "what does
probability mean if everything exists?" (Actually, before that I had thought
about "what does probability mean if brain copying is possible?") I've
entertained many different possible answers. I looked at decision theories
not because I'm looking for a decision procedure to adopt, but because that
is one way probability is interpreted and justified. I'm actually more
interested in the philosophical issues rather than the practical ones.

Besides, if you program a decision procedure into an AI, it had better be
flawless because there may be no "escape hatches".

> In other words, I would prioritize "UDASSA doesn't yet make many
> falsifiable predictions" and "We don't see a total ordering of points
> in spacetime, so UDASSA probably doesn't run on a typical Turing
> Machine" as larger problems. But sure, if UDASSA can be improved to
> solve the morality edge-cases that you gave, I'm all for the
> improvements.

I consider UD+ASSA to be a theory of how people reason, or how they ought to
reason, and as such, it does make falsifiable predictions. In fact, as I
showed in several examples, the predictions have been falsified.

About your comment "We don't see a total ordering of points in spacetime, so
UDASSA probably doesn't run on a typical Turing Machine". I don't follow
your reasoning here as to why UD+ASSA+typical TM implies that we should see
a total ordering of points in spacetime. Isn't it possible that such an
ordering exists internal to the TM's program, but it's not visible to the
people inside the universe that the TM simulates?

> As far as our observations of the Universe, I don't quite follow: how
> can you go from "in terms of morality, probability is imperfect" to
> "there's no such thing as probability, therefore there's no measure
> problem?"

My reasoning goes like this:

1. We need to reinterpret probability, from "subjective degree of belief" to
"how much do I care about something" in order to fix counterintuitive
implications of decision theory.
2. Once we do that, we no longer seem to have a solution to the "measure
problem".
3. Let's look closer at the nature of the problem. It seems to consist of
two parts:
(A) Why am I living in an apparently lawful universe?
(B) Why should I expect the future to continue to be lawful?
4. I think (B) is the easier question, and I answered it in a previous post
in this thread. (A) is more problematic, but my tentative answer is that, as
Brent Meeker stated it, "among all possible worlds, somebody has to live in
law-like ones; so it might as well be us."

I'm out of time today, and will respond to your other post tomorrow.
 

Brent Meeker wrote:
> That's a good argument assuming some laws of physics.  But as I understood
> it, the "measure problem" was to explain the law-like evolution of the
> universe as a opposed to a chaotic/random/white-rabbit universe.  Is it
> your interpretation that, among all possible worlds, somebody has to live
> in law-like ones; so it might as well be us?

Yes. See my other post today.

On Oct 25, 7:59 am, "Wei Dai" <wei...@weidai.com> wrote:
> I don't care
> about (1) and (3) because those universes are too arbitrary or random, and I
> can defend that by pointing to their high algorithmic complexities.

In (3) the universe doesn't have a high aIgorithmic complexity.

Any theory that just says "we only care about universes with low
algorithmic complexity" leads to (3) (assuming that, by "the
universe", you have the usual meaning of "that vast space we seem to
live in" rather than "my immediate perceptions".) The specific reason
I like UDASSA is because it gives you a framework for saying, "the
universe, plus my index in the universe, has a low algorithmic
complexity."

> About your comment "We don't see a total ordering of points in spacetime, so
> UDASSA probably doesn't run on a typical Turing Machine". I don't follow
> your reasoning here as to why UD+ASSA+typical TM implies that we should see
> a total ordering of points in spacetime. Isn't it possible that such an
> ordering exists internal to the TM's program, but it's not visible to the
> people inside the universe that the TM simulates?

It definitely is possible, my only point is that the fact that most
UTM program outputs don't have an easily-observed homogeneous and
isotropic n-dimensional space in their output, *may* be Bayesian
evidence against the plain UDASSA. So if we consider 3 hypotheses:

1. plain UDASSA

2. UDASSA variants, such as the set-theory UDASSA you mentioned, or a
UDASSA on a UTM that can atomically implement higher-level operations
like "multiply two complex numbers to infinite precision" and "apply
an operation uniformly to an infinite manifold".

3. something else

Then the lack of ordering that we see probably gives me a "Bayesian
Shift" from (1) to (2) or (3). However, to demonstrate would probably
be difficult, and if we had something powerful enough to do this, we
might have a theory that allows UDASSA to make novel predictions about
the observed Universe.

> However, to demonstrate would probably
> be difficult, and if we had something powerful enough to do this, we
> might have a theory that allows UDASSA to make novel predictions about
> the observed Universe.

To give examples of how hard this is:

1. What is the probability that our Universe has existed since the Big
Bang, but will abruptly end tomorrow? There have been about 2^16 days
since the Big Bang, so we can get a lower bound of probability in
UDASSA with 1 / 2^((length of a binary program that runs a Universe
for x subjective time, then halts) + (about 16 bits)). I don't know
how to program any of the basic TM's, and can't personally estimate of
the complexity of the first term. And this is just to get an lower
bound, the actual probability is probably much higher.

2. Take a real-world example, like the Pioneer Anomaly; does "new laws
of physics caused the Pioneer Anomaly" have a higher or lower
complexity than "there is a mundane explanation for the Pioneer
Anomaly"? Good luck!

On the plus side, one wouldn't have to solve every problem to make
UDASSA into a science; one would just have to solve (successfully
predict) a handful of novel problems (that aren't solvable by other
methods) to demonstrate that is true and useful.

Rolf Nelson wrote:
> On Oct 25, 7:59 am, "Wei Dai" <wei...@weidai.com> wrote:
>> I don't care
>> about (1) and (3) because those universes are too arbitrary or random,
>> and I
>> can defend that by pointing to their high algorithmic complexities.
>
> In (3) the universe doesn't have a high aIgorithmic complexity.

I should have said that in (3) our decisions don't have any consequences, so
we disregard them even if we do care what happens in them. The end result is
the same: I'll act as if I only live in (2).

From your post yesterday:

> True. So how would an alternative scheme work, formally? Perhaps
> utility can be formally based on the "Measure" of "Qualia" (observer
> moments).

This is one of the possibilities I had considered and rejected, because it
also leads to counterintuitive consequences. For example, suppose someone
gives your the following offer:

I will throw a fair coin. If the coin lands heads up, you will be
instantaneously vaporized. If it lands tails up, I will exactly double your
measure (say by creating a copy of your brain and continuously keeping it
synchronized).

Given your "measure of qualia"-based formalization of utility, and assuming
that you're selfish so that you're only interested in the measure of the
qualia of your own future selves, you'd have to be indifferent between
accepting this offer and not accepting it.

Instead, here's my current approach for a formalization of decision theory.
Let a set S be the description of an agent's knowledge of the multiverse.
For example, for a Tegmarkian version of the multiverse, elements of S have
the form (s, t) where s is a statement of second-order logic, and t is
either "true" or "false". For simplicity, assume that the decision-making
agent is logically omniscient, which means he knows the truth value of all
statements of second-order logic, except those that depend on his own
decisions. We'll say that he prefers choice A to choice B if and only if he
prefers S U C(E,A) to S U C(E,B), where U is the union operator, C(x,y) is
the logical consequences of everyone having qualia x deciding to do y, and E
consists of all of his own memories and observations.

In this most basic version, there is not even a notion of "how much one
cares about a universe". I'm relatively confident that it doesn't lead to
any counterintuitive implications, but that's mainly because it is too weak
to lead to any kind of implications at all. So how do we explain what
probability is, and why the concept has been so useful?

Well, let's consider an agent who happens to have preferences of a special
form. It so happens that for him, the multiverse can be divided into several
"regions", the descriptions of which will be denoted S_1, S_2, S_3, etc.,
such that S_1 U S_2 U S_3 ... = S and his preferences over the whole
multiverse can be expressed as a linear combination of his preferences over
those "regions". That means, there exists functions P(.) and U(.) such that
he prefers the multiverse S to the multiverse T if and only if

P(S_1)*U(S_1) + P(S_2)*U(S_2) + P(S_3)*U(S_3) + ...
> P(T_1)*U(T_1) + P(T_2)*U(T_2) + P(T_3)*U(T_3) ...

I haven't worked out all of the details of this formalism, but I hope you
can see where I'm going with this...

With the RSSA (through the use of the UD) it should be clear that THIRD
person determinism and computability entails FIRST person indeterminacy
and "observable non computability" (like what we can "see" when
preparing many particles in the state 1/sqrt(2)(up+down) and looking
them in the base {up, down}.

Bruno

http://iridia.ulb.ac.be/~marchal/

OK. I should not have talk about "fundamental truth", but about
"fundamental question". By which I mean "where do I come from?", "what
can we hope", "what is the nature of matter", "is life a dream?" etc.
None of those question are really addressed by today's science which
focuses on the physical aspect of reality without really tackling
seriously (in the doubting way) its metaphysical aspect and its psycho
or theo logical aspect.

> Quantum gravity seems like an esoteric game to most people and so you
> can say anything you want about it without any ethical implications.  
> But when quantum gravity seems to provide a non-supernatural
> cosmogony, religions are threatened and suddenly it's like bad news to
> a dying man (and we're all dying).

If a religion is threatened by science, it means it is build on bad
faith. At least with comp science has to be a part of theology. If
theology does not extend science, it means it is wrong. Now sometimes
some scientist talk like if they were priest, and that is two times
more wrong than usual priest talk. Religion, like science, is
threatened by bad science, and even more by bad religion (religion
based on "blind" faith or authoritative argument).
Now, don't tell me that a theory like quantum gravity  provides a non
supernatural cosmogony given that quantum gravity study quantum gravity
and perhaps the physical universe, but not the mind, nor the soul, the
person or consciousness. It is not its subject a priori. To look at
quantum gravity as a cosmogony is a confusion between subject like
physics and theology. This threatens theology, because without making
some very strong physicalist assumption, which are incompatible with
the mechanist thesis, it consists to make physics a religion without
saying! This is just dishonest. Such a physical universe is worst than
a white male God, because it looks scientific (unlike the male God),
but it isn't.

It looks that in winter, people forget all about the 1/3 distinction.
In Quantum gravity this 1/3 distinction is a bit hidden. You have to
postulate comp, and thus Everett before. (Well, as you know, you have
to derive Everett but it is not the point here).

>
> Coincidentally, James Watson has just lost his job because he said
> some things that, while narrowly true, support a racist view of
> Africa.  Were they "fundamental"  or does "fundamental" = "of no
> import in society"?

I love Watson because I discover "the math of computer science" by
myself  in his book "Molecular Biology of the Gene". This book has
played a so big role in my youth that I have been using for years the
word "Watson" as a synonym of "Bible".

But J. Watson has become the worst materialist I have ever heard about.
According to a talk I have followed some years ago (I should search for
the reference) Watson seems to believe only in ATOMS". Someone told him
"Surely you believe in molecules M. Watson". And James Watson would
have answered: "No, I don't, there are only atoms!".
Weird ....

By "fundamental" I really mean the same as in "fundamental science".
Unless in company of theological hypothesis, it has no more impact on
society other than its technical products.
Einstein discovered the relation between matter and energy only through
a deep motivation for fundamental question: what is matter, what is the
nature of light, how could resemble the universe when seen by  a
photon, etc.

But of course, its questioning led him to the discovery of precise and
refutable empirical statements, most of them did have incredible
impacts of our live today.

Bruno

http://iridia.ulb.ac.be/~marchal/

> > In (3) the universe doesn't have a high aIgorithmic complexity.
>
> I should have said that in (3) our decisions don't have any consequences, so
> we disregard them even if we do care what happens in them. The end result is
> the same: I'll act as if I only live in (2).

In the (3) I gave, you're indexed so that the thermal fluctuation
doesn't dissolve until November 1, so your actions still have
consequences.

> I will throw a fair coin. If the coin lands heads up, you will be
> instantaneously vaporized. If it lands tails up, I will exactly double your
> measure (say by creating a copy of your brain and continuously keeping it
> synchronized).

This is one of a larger class of problems related to volition, and the
coupling of my qualia to an external reality, that I don't currently
have an answer for. I want to live on in the current Universe, I don't
to die and have a duplicate of myself created in a different Universe.
I want to eat a real ice cream cone, I don't want you to stimulate my
neurons to make me imagine I'm eating an ice cream cone. I would argue
that a world where I can interact with real people is, in some sense,
better than a world where I interact with imaginary people who I
believe are real.

> Well, let's consider an agent who happens to have preferences of a special
> form. It so happens that for him, the multiverse can be divided into several
> "regions", the descriptions of which will be denoted S_1, S_2, S_3, etc.,
> such that S_1 U S_2 U S_3 ... = S and his preferences over the whole
> multiverse can be expressed as a linear combination of his preferences over
> those "regions". That means, there exists functions P(.) and U(.) such that
> he prefers the multiverse S to the multiverse T if and only if
>
> P(S_1)*U(S_1) + P(S_2)*U(S_2) + P(S_3)*U(S_3) + ...
>
> > P(T_1)*U(T_1) + P(T_2)*U(T_2) + P(T_3)*U(T_3) ...
>
> I haven't worked out all of the details of this formalism, but I hope you
> can see where I'm going with this...

You have a general model, which can encompass classical decision
theory, but can also encompass other models as well. It's not
immediately clear to me what benefit, if any, we get from such a
general model.

Rolf Nelson wrote:
> In the (3) I gave, you're indexed so that the thermal fluctuation
> doesn't dissolve until November 1, so your actions still have
> consequences.

Still not a problem: the space-time region that I can affect in (3) is too
small (i.e., its measure is too small, complexity too large) for me to care
much about the consequences of my actions on it.

> This is one of a larger class of problems related to volition, and the
> coupling of my qualia to an external reality, that I don't currently
> have an answer for. I want to live on in the current Universe, I don't
> to die and have a duplicate of myself created in a different Universe.
> I want to eat a real ice cream cone, I don't want you to stimulate my
> neurons to make me imagine I'm eating an ice cream cone. I would argue
> that a world where I can interact with real people is, in some sense,
> better than a world where I interact with imaginary people who I
> believe are real.

To me, these examples show that we do not care just about qualia, but also
about attributes and features of the multiverse that can not be classified
as qualia, and therefore we should rule out decision theories that cannot
incorporate preferences over non-qualia.

> You have a general model, which can encompass classical decision
> theory, but can also encompass other models as well. It's not
> immediately clear to me what benefit, if any, we get from such a
> general model.

Fair question. I'll summarize:

1. We are forced into considering such a general model because we don't have
a more specific one that doesn't lead to counterintuitive implications.

2. It shows us what probabilities really are. For someone whose preferences
over the multiverse can be expressed as a linear combination of preferences
over regions of the multiverse, a probability function can be interpreted as
a representation of how much he cares about each region. I would argue that
most of us in fact have preferences of this form, at least approximately,
which explains why probability theory has been useful for us.

3. It gives us a useful framework for considering anthropic reasoning
problems such as the Doomsday Argument and the Simulation Argument. We can
now recast these questions into "Do we prefer a multiverse where people in
our situation act as if doom is near?" and "Do we prefer a multiverse where
people in our situation act as if they are in simulations?" I argue that its
easier for us to consider these questions in this form.

4. For someone on a practical mission to write an AI that makes sensible
decisions, perhaps the model can serve as a starting point and as
illustration of how far away we still are from that goal.
 

On Oct 31, 3:28 pm, "Wei Dai" <wei...@weidai.com> wrote:

>
> 4. For someone on a practical mission to write an AI that makes sensible
> decisions, perhaps the model can serve as a starting point and as
> illustration of how far away we still are from that goal.

Heh.  Yes, very interesting indeed.  But a huge body of knowledge and
a great deal of smartness is needed to even begin to grasp all that
stuff ;)

As regards AI I gotta wonder whether that 'Decision Theory' stuff is
really 'the heart of the matter'  - perhaps its the wrong level of
abstraction for the problem.  That is it say, it would be great if the
AI could work out all the decision theory for itself, rather than
having us trying to program it in (and probably failing miserably).
Certainly, I'm sure as hell not smart enough to come up with a working
model of decisions.  So, rather than trying to do the impossible,
better to search for a higher level of abstraction.  Look for the
answers in communication theory/ontology, rather than decision
theory.  Decision theory would be derivative of an effective ontology
- that saves me the bother of trying to work it out ;)

Decisions require some value structure.  To get values from an ontology you'd have to get around the Naturalistic fallacy.

Brent Meeker

On Oct 31, 7:40 pm, Brent Meeker <meeke...@dslextreme.com> wrote:

>
> Decisions require some value structure.  To get values from an ontology you'd have to get around the Naturalistic fallacy.
>

Decision theory has this same problem.  Decision theory doesn't
require values.  The preferences (values) are plugged in from outside
the theory.  Decision theory is merely a way of computing the best way
to achieve the desired outcomes.  It doesn't say what we should desire
though.

Decision theory is too hard for me and too complex.  What I'm
suspecting is that it's not the final word.  I'm looking for a higher
level theory capable of deriving the results in decision theory
indirectly without me having to directly work them out.

My suspicion currently focuses on communication theory, knowledge
representation and data modelling (ontology).  Rather than 'getting
values out' I think values are most likely somehow implicitly built
into the structure of ontology itself.

This would provide an experimental way to measure absolute measure.

I am not a proponent of ASSA, rather I believe in RSSA and in a
cosmological principle for measure: that measure is independent of when
or where the observer makes an observation. However, I thought that
tying cosmic expansion to measure may be an interesting avenue of inquiry.

George Levy

Rolf Nelson wrote:

>(Warning: This post assumes an familiarity with UD+ASSA and with the
>cosmological Measure Problem.)
>
>Observational Consequences:
>
>1. Provides a possible explanation for the "Measure Problem" of why we
>shouldn't be "extremely surprised" to find we live in a lawful
>universe, rather than an extremely chaotic universe, or a homogeneous
>cloud of gas.
>
>2. May help solve the Doomsday Argument in a finite universe, since
>you probably have at least a little more "measure" than a typical
>specific individual in the middle of a Galactic Empire, since you are
>"easier to find" with a small search algorithm than someone surrounded
>by enormous numbers of people.
>
>3. For similar reasons, may help solve a variant of the Doomsday
>Argument where the universe is infinite. This variant DA asks, "if
>there's currently a Galactic Empire 10000 Hubble Volumes away with an
>immensely large number of people, why wasn't I born there instead of
>here?"
>
>4. May help solve the Simulation Argument, again because a search
>algorithm to find a particular simulation among all the adjacent
>computations in a Galactic Empire is longer (and therefore, by UD
>+ASSA, has less measure) than a search algorithm to find you.
>
>5. In basic UD+ASSA (on a typical Turing Machine), there is a probably
>a strict linear ordering corresponding to when the events at each
>point in spacetime were calculated; I would argue that we should
>expect to see evidence of this in our observations if basic UD+ASSA is
>true. However, we do not see any total ordering in the physical
>Universe; quite the reverse: we see a homogeneous, isotropic Universe.
>This is evidence (but not proof) that either UD+ASSA is completely
>wrong, or that if UD+ASSA is true, then it's run on something other
>than a typical linear Turing Machine. (However, if you still want use
>a different machine to solve the "Measure Problem", then feel free,
>but you first need to show that your non-Turing-machine variant still
>solves the "Measure Problem.")
>
>
>Decision Theory Consequences (Including Moral Consequences):
>
>Every decision algorithm that I've ever seen is prey to paradoxes
>where the decision theory either crashes (fails to produce a
>decision), or requires an agent to do things that are bizarre, self-
>destructive, and evil. (If you like, substitute 'counter-intuitive'
>for 'bizarre, self-destructive, and evil.') For example: UD+ASSA,
>"Accepting the Simulation Argument", Utilitarianism without
>discounting, and Utilitarianism with time and space discounting all
>have places where they seem to fail.
>
>UD+ASSA, like the Simulation Argument, has the following additional
>problem: while some forms of Utilitarianism may only fail in
>hypothetical future situations (by which point maybe we'll have come
>up with a better theory), UD+ASSA seems to fail *right here and now*.
>That is, UD+ASSA, like the Simulation Argument, seems to call on you
>to do bizarre, self-destructive, and evil things today. An example
>that Yudowsky gave: you might spend resources on constructing a unique
>arrow pointing at yourself, in order to increase your measure by
>making it easier for a search algorithm to find you.
>
>Of course, I could solve the problem by deciding that I'd rather be
>self-destructive and evil than be inconsistent; then I could consider
>adopting UD+ASSA as a philosophy. But I think I'll pass on that
>option. :-)
>
>So, more work would have to be done the morality of UD+ASSA before any
>variant of UD+ASSA can becomes a realistically palatable part of a
>moral philosophy.
>
>-Rolf
>
>
>>
>
>
>  
>

On Wed, Oct 31, 2007 at 05:11:01PM -0700, George Levy wrote:
>
> Could we relate the expansion of  the universe to the decrease in
> measure of a given observer? High measure corresponds to a small
> universe and conversely, low measure to a large one.  For the observer
> the decrease in his measure would be caused by all the possible mode of
> decay of all the nuclear particles necessary for his consciousness.
> Corresponding to this decrease, the radius of the observable universe
> increases to make the universe less likely.
>
> This would provide an experimental way to measure absolute measure.
>
> I am not a proponent of ASSA, rather I believe in RSSA and in a
> cosmological principle for measure: that measure is independent of when
> or where the observer makes an observation. However, I thought that
> tying cosmic expansion to measure may be an interesting avenue of inquiry.
>
> George Levy
>

There is a relationship, though perhaps not quite what you think. The
measure of an OM will be 2^{-C_O}, where C_O is the amount of
information about the universe you know at that point in time
(measured in bits). The physical complexity C of the universe at a point
in time is in some sense the limit of all that is possible to know
about the universe, ie C_O <= C.

C is related to the size of the universe by the equation H = C + S,
where S is the entropy of the universe (measured in bits), and H is
the maximum possible entropy that would pertain if the universe were
in equilibrium. H is a monotonically increasing function of the size
of the universe - something like propertional to the volume (or
similar - I forget the details). S is also an increasing function (due
to the second law), but doesn't increase as fast as H. Consequently C
increases as a function of universe age, and so C_O can be larger now
than earlier in the universe, implying smaller OM measures.

However, it remains to be seen whether the anthropic reasons for
experiencing a universe 10^9 years and of large complexity we
currently see is necessary...

--

----------------------------------------------------------------------------
A/Prof Russell Standish                  Phone 0425 253119 (mobile)
Mathematics                                 
UNSW SYDNEY 2052                          hpc...@hpcoders.com.au
Australia                                http://www.hpcoders.com.au
----------------------------------------------------------------------------

On Fri, Nov 02, 2007 at 12:20:35PM -0700, George Levy wrote:
> Russel,
>
> We are trying to related the expansion of the universe to decreasing
> measure. You have presented the interesting equation:
>
> H = C + S
>
> Let's try to assign some numbers.
> 1) Recently an article

> appeared in New Scientist stating that we may be living "inside" a black
> hole, with the event horizon being located at the limit of what we can
> observe ie the radius of the current observable universe.
> 2) Stephen Hawking

> entropy of a black hole is proportional to its surface area.
>

>     S_{BH} = \frac{kA}{4l_{\mathrm{P}}^2}
>
> where where k is Boltzmann's constant

> l_{\mathrm{P}}=\sqrt{G\hbar / c^3} is the Planck length

>
> Thus we can say that a change in the Universe's radius corresponds to a
> change in entropy dS. Therefore, dS/dt is proportional to dA/dt and to
> 8PR(dR/dt)  R being the radius of the Universe and P = Pi. Let's assume
> that dR/dt = c
> Therefore
>
> dS/dt = (k/4 L^2) 8PRc = 2kPRc/ L^2
>

>
> which gives a size of the Universe

> edge of the visible universe. Thus R = 46.5 billion light-years in any
> direction; this is the comoving radius

> same as the age of the Universe because of Relativity considerations)
>
> Now I have trouble relating these facts to your equation H = C + S or
> maybe to the differential version dH = dC + dS. What do you  think? Can
> we push this further?
>
> George
>

I think that the formula you have above for S_{BH} is the value that
should be taken for the H above. It is the maximum value that entropy
can take for a volume the size of the universe.

The internal observed entropy S, will of course, be much lower. I
don't have a formula for it off-hand, but it probably involves the
microwave background temperature.

Cheers

--

----------------------------------------------------------------------------
A/Prof Russell Standish                  Phone 0425 253119 (mobile)
Mathematics                                 
UNSW SYDNEY 2052                          hpc...@hpcoders.com.au
Australia                                http://www.hpcoders.com.au
----------------------------------------------------------------------------

Until someone figures out a way of getting all email clients to read
and write mathML (which will probably be never), this is as good as it
gets.

Cheers

--

----------------------------------------------------------------------------
A/Prof Russell Standish                  Phone 0425 253119 (mobile)
Mathematics                                 
UNSW SYDNEY 2052                          hpc...@hpcoders.com.au
Australia                                http://www.hpcoders.com.au
----------------------------------------------------------------------------

I have almost finished the posts on the lobian machine I have promised.
I have to make minor changes and to look a bit the spelling. I cannot
do that this week, so I will send it next week. Thanks for your
patience. I give you the plan, though, which I will actually also
follow for the beginning (and the end) of the ULB-saturday course this
year:

1) Cantor's diagonal
2) Does the universal digital machine exist?
3) Lobian machines,  who and what are they?
4) The 1-person and the 3- machine.
5) Lobian machines' theology
6) Lobian machines' physics
7) Lobian machines' ethics

BTW, if some people are near Belgium, I have been invited for doing a
talk on the UDA at a colloquium on "Logic and Reality" at Namur/Louvain
in BELGIUM. The other talks seems quite interesting (too, if I may say
:). Most will be done in english. Program and informations can be found
here:

http://www.logic-center.be/acts/logrea.html

Best regards to David, and all of you

Bruno

http://iridia.ulb.ac.be/~marchal/

On Nov 6, 2:37 pm, Bruno Marchal <marc...@ulb.ac.be> wrote:

> I have almost finished the posts on the lobian machine I have promised.
> I have to make minor changes and to look a bit the spelling. I cannot
> do that this week, so I will send it next week. Thanks for your
> patience.

Thanks - I'll keep an eye out.

David

Le 11-nov.-07, à 23:33, John Mikes a écrit :

> Bruno, I hope it will be accessible to me, too, by simple computerese
> software.

Normally there should be no difficulties. My goal is not to explain all
the technics, but the minimal things which I estimate to be necessary
for having a basic general idea of what is going on.

My first goal, perhaps my main goal, is to explain Church Thesis CT.  
To explain why CT is a very strong hypothesis, with a uniform deep
impact on everything, and mainly on "theories of everything".

I want also to explain more clearly the difference between Tegmark,
Schmidhuber, and "comp", etc.

But this needs a minimal amount of "modern math", so as to make clear
Cantor's role, and then Church, Kleene.

Not really the time today, but hopefully (normally) I will have more
time tomorrow,

Thanks for letting me know your interest, and your patience,

Best,

Bruno

http://iridia.ulb.ac.be/~marchal/

OK, here is a first try. Let me know if this is too easy, too
difficult, or something in between. The path is not so long, so it is
useful to take time on the very beginning.
I end up with some exercice. I will give the solutions, but please try
to be aware if you can or cannot do them, so as not missing the train.

John, if you have never done what has been called "modern math", you
could have slight notation problem, please ask any question. I guess
for some other the first posts in this thread could look too much
simple. Be careful when we will go from this to the computability
matter.

I recall the plan, where I have added the bijection thread:

Plan

0) Bijections

1) Cantor's diagonal
2) Does the universal digital machine exist?

And for much later, if people are interested or ask question:

3) Lobian machines,  who and/or what are they?

4) The 1-person and the 3- machine.
5) Lobian machines' theology
6) Lobian machines' physics
7) Lobian machines' ethics

But my main goal first is to explain that Church thesis is a very
strong postulate. I need first to be sure you have no trouble with the
notion of bijection.

================
0) Bijections

Suppose you have a flock of sheep. Your neighbor too. You want to know
if you have more, less or the same number of sheep, but the trouble is
that neither you nor your neighbor can count (nor anyone around).

Amazingly enough, perhaps, it is still possible to answer that
question, at least if you have enough pieces of rope. The idea consists
in attaching one extremity of a rope to one of your sheep and the other
extremity to one of the neighbor's sheep, and then to continue. You are
not allow to attach two ropes to one sheep, never.

In the case you and your neighbor have a different number of sheep,
some sheep will lack a corresponding sheep at the extremity of their  
rope, so that their ropes will not be attached to some other sheep.

Exemple (your flock of sheep = {s, r, t, u},  and the sheep of the
neighborgh = {a, b, c, d, e, f}.

s --------- a
r ---------- d
u --------- c
t ----------- f
   ------------e
   ------------b

and we see that the neighbor has more sheep than you, because b and e
have their ropes unable to be attached to any remaining sheep you have,
and this because there are no more sheep left in your flock. You have
definitely less sheep.

In case all ropes attached in that way have a sheep well attached at
both extremities, we can say that your flock and your neighbor's flock
have the same number of elements, or same cardinality. In that case,
the ropes represent a so called one-one function, or bijection, between
the two flocks. If you have less sheep than your neighbor, then there
is a bijection between your flock and a subset of your neighbor's
flock.

If those flocks constitute a finite set, the existence of a bijection
between the two flocks means that both flocks have the same number of
sheep, and this is the idea that Cantor will generalize to get a notion
of "same number of element" or "same cardinality" for couples of
infinite sets.

Given that it is not clear, indeed,  if we can count the number of
element of an infinite set, Cantor will have the idea of generalizing
the notion of "same number of elements", or "same cardinality" by the
existence of such one-one function. The term "bijection" denotes
"one-one function".

Definition: A and B have same cardinality (size, number of elements)
when there is a bijection from A to B.

Now, at first sight, we could think that all *infinite* sets have the
same cardinality, indeed the "cardinality" of the infinite set N. By N,
I mean of course the set {0, 1, 2,  3,  4,  ...}

By E, I mean the set of even number {0, 2, 4, 6, 8, ...}

Galileo is the first, to my knowledge to realize that N and E have the
"same number of elements", in Cantor's sense. By this I mean that
Galileo realized that there is a bijection between N and E. For
example, the function which sends x on 2*x, for each x in N is such a
bijection.
Now, instead of taking this at face value like Cantor, Galileo will
instead take this as a warning against the use of the infinite in math
or calculus.
Confronted to more complex analytical problems of convergence of
Fourier series, Cantor knew that throwing away infinite sets was too
pricy, and on the contrary, will consider such problems as a motivation
for its "set theory". Dedekind will even define an infinite set by a
set which is such that there is a bijection between itself and some
proper subset of himself.

By Z, I mean the set of integers {..., -3, -2, -1, 0, 1, 2, 3, ...}

Again there is a bijection between N and Z.  For example,

0  1  2  3  4  5    6  7  8  9  10 ....
0 -1 1 -2  2  -3   3  -4  4  -5  5 ...

or perhaps more clearly (especially if the mail does not respect the
"blank" uniformely; the bijection, like all function, is better
represented as set of couples:

bijection from N to Z = {(0,0) (1, -1) (2, 1) (3 -2) (4, 2) (5, -3) (6,
3) ... }. Because everyone know the sequence 0, 1, 2, 3, 4, 5, ... we
can also describe a bijection between N and Z (say) just by the
sequence of images:

0 -1 1 -2  2  -3   3  -4  4  -5  5 ...

That bijection can also be given by a rule: send even number x on x/2,
and send odd numbers on x  -((x+1)/2). But it is not necessary to get
those rules to be convinced, the drawing is enough once you interpret
it genuinely.

By AXB, I mean the set of couples (x, y) with x in A and y in B. It is
natural to put them in a cartesian plane.  For exemple, if A = {0, 1}
and B = {a, b, c}, then AXB = {(0, a) (1, a) (0, b) (1, b) (0, c) (1,
c)}, and is best represented by

(0, c) (1, c)
(0, b) (1, b)
(0, a) (1, a)

You see that if A is finite and has n elements and if B is finite and
has m elements, then AXB is finite and has m*n elements. Yet, again,
NXN "has the same number of elements" that N.

NXN is obviously the infinite extension of the following 4X4
approximation:

...
(0,3) (1,3) (2,3) (3,3)...
(0,2) (1,2) (2,2) (3,2)...
(0,1) (1,1) (2,1) (3,1)...
(0,0) (1,0) (2,0) (3,0)...

Do you see a bijection between N and NXN ?

Here is one, which I will call the zigzagger (draw the picture above
and draw the link between the couples, a bit like in little children
drawing puzzles, so as to see the zigzag clearly).

(0,0) (0,1) (1,0) (2,0) (1,1) (0,2) (0,3) (1,2) (2,1) (3,0) (4,0) (3,1)
(2,2) (1,3) (0,4) ...

Here is another one, due to Cantor, I think. To draw it you will have
to raise the pen.

(0,0) (0,1) (1,0) (0,2) (1,1) (2,0) (0,3) (1,2) (2,1) (3,0) (0,4) (1,3)
(2,2) (3,1) (4,0) ...

The inverse of that bijection, which exists and is of course a
bijection from NXN to N  has a nice quasi polynomial presentation.  (x,
y) is send on the half of (x+y)^2 + 3x + y.

You see that (4,0) is send to 14 (ok ?, it is not 13 because we start
from zero), and indeed the half of (4+0)^2 + 3*4 +0 is 14.

And ZXZ extends in a similar way :

...
... (-3, 3) (-2, 3) (-1,3)   (0,3) (1,3)  (2,3)  (3,3)...
... (-3, 2) (-2, 2) (-1,2)   (0,2) (1,2)  (2,2)  (3,2)...
... (-3, 1)  (-2, 1) (-1,1)  (0,1) (1,1)  (2,1)  (3,1)...
... (-3,0)   (-2, 0)  (-1,0) (0,0) (1,0)  (2,0)  (3,0)...
... (-3,-1) (-2,-1)(-1,-1)  (0,-1) (1,-1) (2,-1) (3,-1)...
... (-3,-2) (-2,-2)(-1,-2)  (0,-2) (1,-2) (2,-1) (3,-2)...
... (-3,-3) (-2,-3)(-1,-3)  (0,-3) (1,-3) (2,-1) (3,-3)...
...

Do you see a bijection between N and ZXZ ? Here is the
spiral-bijection, or spiraler:

(0,0) (0,1) (-1,1) (-1,0) (-1,-1) (0,-1) (1,-1) (1,0) (1,1) (1,2) (0,2)
(-1,2) (-2,2) (-2,-1) ....

You see: a bijection between N and ZXZ assigns to each natural number
one and only one couple of integers, and this in such a way that we are
sure that all couples of integers is the image of a natural number by
that bijection.

Little exercises:

1) is there a bijection between N and N?

2) Q is the set of rational numbers, that is length of segment which
can be measured by the ratio of natural numbers (or integers).

(equivalently: = the real with repetitive decimals, like
0,99999999...., or 345,78123123123123123...). By the way, could find n
and m (in N) such that n/m = 345,78123123123123123... ? (and could you
explain why 1,00000000.... = 0, 99999999....?). But this will not been
used later.

Can you see that there is a bijection between N and Q? Hint: transform
the bijection between N and NXN into a bijection between N and Q.

3) The disjoint union of two sets A and B = their formal union together
with a relabelling so as to distinguish the elements: exemple:

N disjoint-union-with N = {0, 1, 2, 3, ...} U {0', 1', 2', 3', ...},
which I will write N U N' (read: N union N prime).

Is there a bijection between N and (with obvious notation) N U N' U N''
U N''' U ...?

I will write NXNXN for NX(NXN)

can you build a bijection between N and NXNXN ?
can you build a bijection between N and NXNXNXN ?
can you build a bijection between N and NXNXNXNXN ?

4) Very important for the sequel. Let A be a finite alphabet (for
exemple: A = {0,1}). Let us denote by A° the set of all finite words
build on A. By a (finite) word a mean any finite sequence of elements
taken in the alphabet (like 000, or 10101, or 1101000011010110). Is
there a bijection between N and A°, with A = {0,1}.

Solutions will be given later, but ask for question if there are any
problem. Don't hesitate to tell me the mistakes, which always exist!
You can also ask question about motivation, like, "for God sake why are
you explaining us all this". Try also to keep those posts for later
considerations.

================
http://iridia.ulb.ac.be/~marchal/

>
> Definition: A and B have same cardinality (size, number of elements)
> when there is a bijection from A to B.
>
> Now, at first sight, we could think that all *infinite* sets have the
> same cardinality, indeed the "cardinality" of the infinite set N. By N,
> I mean of course the set {0, 1, 2,  3,  4,  ...}
>  

> By E, I mean the set of even number {0, 2, 4, 6, 8, ...}
>
> Galileo is the first, to my knowledge to realize that N and E have the
> "same number of elements", in Cantor's sense. By this I mean that
> Galileo realized that there is a bijection between N and E. For
> example, the function which sends x on 2*x, for each x in N is such a
> bijection.
>  

How do you prove that each x in N has a corresponding number 2*x in E?

If m is the biggest number in N, then there will be no corresponding
number 2*m in E, because 2*m is not a number.

> Now, instead of taking this at face value like Cantor, Galileo will
> instead take this as a warning against the use of the infinite in math
> or calculus.
>  

>
> Bruno Marchal skrev:
>> 0) Bijections
>>
>> Definition: A and B have same cardinality (size, number of elements)
>> when there is a bijection from A to B.
>>
>> Now, at first sight, we could think that all *infinite* sets have the
>> same cardinality, indeed the "cardinality" of the infinite set N. By
>> N,
>> I mean of course the set {0, 1, 2,  3,  4,  ...}
>>
> What do you mean by "..."?

Are you asking this as a student who does not understand the math, or
as a philospher who, like an ultrafinist, does not believe in the
potential infinite (accepted by mechanist, finistist, intuitionist,
etc.).

I have already explained that the meaning of "...'" in {I, II, III,
IIII, IIIII, IIIIII, IIIIIII, IIIIIIII, IIIIIIIII, ...}  is *the*
mystery.

A beautiful thing, which is premature at this stage of the thread, is
that accepting the usual meaning of "..." , then we can mathematically
explained why the meaning of "..." has to be a mystery.

>> By E, I mean the set of even number {0, 2, 4, 6, 8, ...}
>>
>> Galileo is the first, to my knowledge to realize that N and E have the
>> "same number of elements", in Cantor's sense. By this I mean that
>> Galileo realized that there is a bijection between N and E. For
>> example, the function which sends x on 2*x, for each x in N is such a
>> bijection.
>>
> What do you mean by "each x" here?

I mean "for each natural number".

>
> How do you prove that each x in N has a corresponding number 2*x in E?
> If m is the biggest number in N,

There is no biggest number in N. By definition of N we accept that if x
is in N, then x+1 is also in N, and is different from x.

> then there will be no corresponding
> number 2*m in E, because 2*m is not a number.

Of course, but you are not using the usual notion of numbers. If you
believe that the usual notion of numbers is wrong, I am sorry I cannot
help you.

Bruno

>> Now, instead of taking this at face value like Cantor, Galileo will
>> instead take this as a warning against the use of the infinite in math
>> or calculus.
>>
> --
> Torgny Tholerus
>
> >
>

Le Thursday 15 November 2007 14:45:24 Torgny Tholerus, vous avez écrit :
>>  Bruno Marchal skrev:
> Le 14-nov.-07, à 17:23, Torgny Tholerus a écrit :

>>> What do you mean by "each x" here?
>
>
>
> >I mean "for each natural number".
>
>
>  What do you mean by "each" in the sentence "for each natural number"?  How
> do you define ALL natural numbers?
>

There is a natural number 0.
Every natural number a has a natural number successor, denoted by S(a).
There is no natural number whose successor is 0.
Distinct natural numbers have distinct successors: if a ≠ b, then S(a) ≠ S(b).

You need at least the successor axiom. N = {0 ,1 ,2 ,3 ,... ,N ,N+1, ..}

All natural numbers are defined by the above.

>
>
> How do you prove that each x in N has a corresponding number 2*x in E?
> If m is the biggest number in N,

By definition there exists no biggest number unless you add an axiom saying
there is one but the newly defined set is not N.

Quentin Anciaux

--
All those moments will be lost in time, like tears in the rain.

Le Friday 16 November 2007 09:33:38 Torgny Tholerus, vous avez écrit :
>  Quentin Anciaux skrev:
> Hi,
>
> Le Thursday 15 November 2007 14:45:24 Torgny Tholerus, vous avez écrit :
>
>   What do you mean by "each" in the sentence "for each natural number"? 
> How do you define ALL natural numbers?
>
>
>
> There is a natural number 0.
> Every natural number a has a natural number successor, denoted by S(a).
>
>
>  What do you mean by "Every" here?  Can you give a *non-circular*
> definition of this word?  Such that: "By every natural number I mean
> {1,2,3}" or "By every naturla number I mean every number between 1 and
> 1000000".  (This last definition is non-circular because here you can
> replace "every number" by explicit counting.)

I do not see circularity here... every means every, it means all natural
numbers possess this properties ie (having a successor), that means by
induction that N does contains an infinite number of elements, if it wasn't
the case that would mean that there exists a natural number which doesn't
have a successor... well as we have put explicitly the successor rule to
defined N I can't see how to change that without changing the axioms.

>
>
> How do you prove that each x in N has a corresponding number 2*x in E?
> If m is the biggest number in N,
>
>
> By definition there exists no biggest number unless you add an axiom saying
> there is one but the newly defined set is not N.
>
>
>  I can prove by induction that there exists a biggest number:
>
>  A) In the set {m} with one element, there exists a biggest number, this is
> the number m. B) If you have a set M of numbers, and that set have a
> biggest number m, and you add a number m2 to this set, then this new set M2
> will have a biggest number, either m if m is bigger than m2, or m2 if m2 is
> bigger than m. C) The induction axiom then says that every set of numbers
> have a biggest number.
>
>  Q.E.D.
>
>  --
>  Torgny Tholerus

Hmm I don't understand... This could only work on finite set of elements. I
don't see this as a proof that N is finite (because it *can't* be by
*definition*).

Quentin Anciaux

--
All those moments will be lost in time, like tears in the rain.

>  Bruno Marchal skrev:Le 14-nov.-07, à 17:23, Torgny Tholerus a écrit :
>>
>>
>>> What do you mean by "..."?
>>>
>>
>> Are you asking this as a student who does not understand the math, or
>> as a philospher who, like an ultrafinist, does not believe in the
>> potential infinite (accepted by mechanist, finistist, intuitionist,
>> etc.).
>>
>
>  I am asking as an ultrafinitist.

Fair enough.
I am not sure there are many ultrafinitists on the list, but just to  
let John Mikes and Norman to digest the bijection post, I will say a  
bit more.
A preliminary remark is that I am not sure an ultrafinitist can really  
assert he is ultrafinitist without acknowledging that he does have a  
way to give some meaning on "...".
But I have a more serious question below.

>
>> I have already explained that the meaning of "...'" in {I, II, III,
>> IIII, IIIII, IIIIII, IIIIIII, IIIIIIII, IIIIIIIII, ...}  is *the*
>> mystery.
>>
>
>  Do you have the big-black-cloud interpretation of "..."?  By that I  
> mean that there is a big black cloud at the end of the visible part of  
> universe,

Concerning what I am trying to convey, this is problematic. The word  
"universe" is problematic. The word "visible" is also problematic.

> and the sequence of numbers is disappearing into the cloud, so that  
> you can only see the numbers before the cloud, but  you can not see  
> what happens at the end of the sequence, because it is hidden by the  
> cloud.

I don't think that math is about seeing. I have never seen a number. It  
is a category mistake. I can interpret sometimes some symbol as  
refering to number, but that's all.

>
>>
>>
>>>> For
>>>> example, the function which sends x on 2*x, for each x in N is such  
>>>> a
>>>> bijection.
>>>>
>>>>
>>> What do you mean by "each x" here?
>>>
>>
>> I mean "for each natural number".
>>
>
>  What do you mean by "each" in the sentence "for each natural  
> number"?  How do you define ALL natural numbers?

By relying on your intuition of "finiteness". I take 0 as denoting a  
natural number which is not a successor.
I take s(0) to denote the successor of 0. I accept that any number  
obtained by a *finite* application of the successor operation is a  
number.
I accept that s is a bijection from N to N \ {0}, and things like that.

>
>>
>>
>>> How do you prove that each x in N has a corresponding number 2*x in  
>>> E?
>>> If m is the biggest number in N,
>>>
>>
>> There is no biggest number in N. By definition of N we accept that if  
>> x
>> is in N, then x+1 is also in N, and is different from x.
>>
>
>  How do you know that m+1 is also in N? 

By definition.

> You say that for ALL x then x+1 is included in N, but how do you prove  
> that m is included in "ALL x"?

I say "for all x" means "for all x in N".

>
>  If you say that m is included in "ALL x", then you are doing an  
> illegal deduction, and when you do an illegal deduction, then you can  
> prove anything.  (This is the same illegal deduction that is made in  
> the Russell paradox.)

?  (if you believe this then you have to accept that Peano Arithmetic,  
or even Robinson arithmetic) is inconsistent. Show me the precise  
proof.

>
>>
>>
>>> then there will be no corresponding
>>> number 2*m in E, because 2*m is not a number.
>>>
>>
>> Of course, but you are not using the usual notion of numbers. If you
>> believe that the usual notion of numbers is wrong, I am sorry I cannot
>> help you.
>>
>
>  I am using the usual notion of numbers. 

You are not. By definition of the usual natural numbers, all have a  
successor.

> But m+1 is not a number. 

This means that you believe there is a finite sequence of "s" of the  
type

A =  
s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(
s(s(s(s( ....s(0)))))))))))))))))))))...)

where "..." here represents a finite sequence, and which is such that  
s(A) is not a number.

> But you can define a new concept: "number-2", such that m+1 is  
> included in that new concept.  And you can define a new set N2, that  
> contains all natural numbers-2.  This new set N2 is bigger than the  
> old set N, that only contains all natural numbers.

  Torgny, have you followed my "fairy tale" which I have explain to Tom  
Caylor. There I have used transfinite sequence of growing functions to  
name a big but finite natural number, which I wrote F_superomega(999),  
or OMEGA+[OMEGA]+OMEGA.

My "serious" question is the following: is your "biggest number" less,  
equal or bigger than a well defined finite number like  
F_superomega(999).

If yes, then a big part of the OM = SIGMA_1 thread will be accessible  
to you, except for the final conclusion. Indeed, you will end up with a  
unique finite bigger universal machine (which I doubt).

If not, let us just say that your ultrafinitist hypothesis is too  
strong to make it coherent with the computationalist hypo. It means  
that you have a theory which is just different from what I propose. And  
then I will ask you to be "ultra-patient", for I prefer to continue my  
explanation, and to come back on the discussion on hypotheses after.  
OK.

Actually, my conversation with Tom was interrupted by Norman who fears  
people leaving the list when matter get too much technical; but I was  
about to introduce a second fairy, capable of non constructive  
reasoning. I recall that the first fairy asked for a big constructively  
nameable number. The second fairy was supposed to ask the same except  
that she drops the constructivity requirement. In that case you can use  
even higher infinities to name (non constructively) a natural number.  
This gives a way to name finite number still *vastly* bigger than  
F_superomega(999).
In case your bigger natural number is bigger than such monstruosity,  
then the whole of the thread will be understandable, although comp can  
be made explicitly wrong (in that case) but somehow approximable in  
practice (even in the local comp practice).

Of course if your bigger natural number is little than  
100^(100^(100^(100^(100^(100^(100^(100^100)], which is already far  
beyond any empirical numbers motivated by the observable empirical  
world, then we can only conclude that we have very different theory.

BTW, do you agree that 100^(100^(100^(100^(100^(100^(100^(100^100)],  
and 100^(100^(100^(100^(100^(100^(100^(100^100)] +1 are numbers? I am  
just curious,

Bruno

http://iridia.ulb.ac.be/~marchal/

>>>>
>> There is a natural number 0.
>> Every natural number a has a natural number successor, denoted by
>> S(a).
>>
>
>  What do you mean by "Every" here? 
> Can you give a *non-circular* definition of this word?  Such that: "By
> every natural number I mean {1,2,3}" or "By every naturla number I
> mean every number between 1 and 1000000".  (This last definition is
> non-circular because here you can replace "every number" by explicit
> counting.)
>
>>
>>> How do you prove that each x in N has a corresponding number 2*x in
>>> E?
>>> If m is the biggest number in N,
>>>
>> By definition there exists no biggest number unless you add an axiom
>> saying
>> there is one but the newly defined set is not N.
>>
>
>  I can prove by induction that there exists a biggest number:
>
>  A) In the set {m} with one element, there exists a biggest number,
> this is the number m.
>  B) If you have a set M of numbers, and that set have a biggest number
> m, and you add a number m2 to this set, then this new set M2 will have
> a biggest number, either m if m is bigger than m2, or m2 if m2 is
> bigger than m.
>  C) The induction axiom then says that every set of numbers have a
> biggest number.

What do you mean by "every" here?
You just give us a non ultrafinitistic proof that all numbers are
finite, not that the set of all finite number is finite.

Bruno

>
>  Q.E.D.

>
>  --
>  Torgny Tholerus
>
>  >
>
http://iridia.ulb.ac.be/~marchal/

> If not, let us just say that your ultrafinitist hypothesis is too
> strong to make it coherent with the computationalist hypo. It means
> that you have a theory which is just different from what I propose.
> And then I will ask you to be "ultra-patient", for I prefer to
> continue my explanation, and to come back on the discussion on
> hypotheses after. OK.
>
> Actually, my conversation with Tom was interrupted by Norman who fears
> people leaving the list when matter get too much technical;

I attend to this list because I learn things from it and I learn a lot
from your technical presentations.  I'm also doubtful of infinities, but
they make things simpler; so my attitude is, let's see where the theory
takes us.

Brent Meeker

Fair enough, thanks.

I give the solution of the little exercises on the notion of bijection.

1) is there a bijection between N and N?

Of course! The identity function is a bijection from N to N, and  
actually any identity function defined on any set is a bijection from  
that set with itself. Here is a drawing of a bijection from N to N (I  
don't represent the "ropes" ...)

0  1  2  3  4  5  6  7  8  ...
0  1  2  3  4  5  6  7  8 ...

So all sets "have the same number of element" than itself.

2) Q is the set of rational numbers, that is length of segment which
can be measured by the ratio of natural numbers (or integers).

There is a bijection between N and Q.   We have already seen a  
bijection between N and ZXZ, which I called the spiraller (I put only  
the image of the bijection, imagine the rope 0----(0,0),   1-----(0,1),  
   2-----(-1,1), ... :

(0,0) (0,1) (-1,1) (-1,0) (-1,-1) (0,-1) (1,-1) (1,0) (1,1) (1,2) (0,2)  
(-1,2) (-2,2) (-2,-1) ....

We can transform that bijection between N and ZXZ into a bijection  
between N and Q in the following way. We start from the bijection above  
between N and ZXZ, but we interpret (x,y) as the fraction x/y, throwing  
it out in case we already met the corresponding rational number, or  
when we met an indeterminate fraction (like 0/0) or spurious one (like  
1/0, 2/0, ...), this gives first

0/0  0/1  -1/1  -1/0   -1/-1 0/-1  1/-1  1/0  1/1  1/2  0/2   -1/2    
-2/2  -2/1 ...., and after the throwing out of the repeated rationals:

0   -1   1   1/2   -1/2   -2 ...

OK?

3) We have seen a bijection between N and NXN. We can use it to provide  
a bijection between N and NX(NXN). Indeed, you can zigzag on NX(NXN)  
like  we have zigzag on NXN, starting from:

...
5
4
3
2
1
0

    (0,0) (0,1) (1,0) (2,0) (1,1) (0,2) (0,3) (1,2) (2,1) (3,0) (4,0)  

All right?

Obviously there is a bijection between NXNXN and NX(NXN)); just send  
(x,y,z) on (x,(y,z)).

In the same manner, you can show the existence of a bijection and any  
of NXNXNXN, NXNXNXNXN, NXNXNXNXNXN, ....

4) (The one important for the sequel). Take any finite alphabet, like  
{0,1}, {a, b},  {a, b, c,  ... z} or all keyboard keys. Then the set of  
all finite words build on any such alphabet is in bijection with N.  
Indeed, to be sure of enumerating all the words, on {a,b,c}, say, just  
enumerate the words having length 1, then length 2, etc. And order just  
alphabetically the words having the same length. On the alphabet  
{a,b,c}, this gives

a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, aac, aba, abb,  
abc, aca, acb, acc, baa, bab, bac, bba, bbb, bbc, bca, bcb, bcc, ...

I hope you see that this gives a bijection between N and A° (the set of  
words on A, which in this example is {a, b, c}. Purist would add the  
empty word in front.
 From this you can give another proof that Q is enumerable (= in  
bijection with N). Indeed all rational numbers, being a (reduced)  
fraction, can be written univocally as a word in the finite alphabet  
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, /}. Example 456765678 / 9898989 (I have  
added blank for reason of readibility, but those are not symbols taken  
from the alphabet).
Another important example, the set of all programs in any programming  
language. For some language, like Python for example, you have to put  
explicitly the "enter", or "carriage return" key symbol in the  
alphabet, of course.

5) Let N be the set {0, 1, 2, 3, 4, 5, 6, ...}, as usual. Let N' be a  
sort of copy or relabeling of N, that is N' = {0', 1', 2', 3', 4', 5',  
6', ...}.
What are really object like 5' is not relevant except that we consider  
that any x is different from any x'. (usually mathematician formalize  
N' by NX{0}, or NX{1}, but that are details).

Is N U N' in bijection with N ?

Sure, NUN' = {0, 0', 1, 1', 2,  2', 3, 3', 4, 4', 5, 5', 6, 6', 7, 7',  
8, 8', ...}, and

0, 0', 1, 1', 2,  2', 3, 3', 4, 4', 5, 5', 6, 6', 7, 7', 8, 8', ... is  
indeed an enumeration of NUN' (bijection from N to the set NUN'). You  
can see it as the result of a zigzagging between

0,  1,  2,  3,   4,  5,  6, ...
0', 1', 2',  3',  4', 5',  6', ...  (do the drawing if you want to see  
the zigzag).

Is the infinite union NUN'UN''UN'''UN''''U ... still enumerable?
Yes, just zigzag on

0,     1,     2,     3,     4,     5,       6, ...
0',     1',    2',    3',     4',    5',      6', ..
0'',    1'',   2'',    3'',    4'',    5'',     6'', ...
0''',   1''',  2''',    3''',   4''',    5''',    6''', ...
0'''',  1'''',  2'''',   3'''',   4'''',   5'''',   6'''', ...
0''''', 1''''',  2''''',  3''''',   4''''',  5''''',  6''''',
...

this gives, starting from up left:

0, 1, 0', 0'', 1', 2, 3, 2', 1'', 0''', 0'''', 1''', 2'', 3', 4, 5, 4',  
3'', 2''', 1'''',  0''''', 0'''''', ...

and gives an enumeration (bijection with N) of the infinite union  
NUN'UN''UN'''UN''''U ...

Remark: for those who recall the transfinite ordinal we have met when  
we have try to give a good answer to the first fairy, you can realize  
that if we put on each set N', N'', N''', etc. the usual order (so that  
3''' < 5''') for example, and if we extend those orders on the all  
infinite union by deciding that x^{n strokes} < y^{m strokes} in case m  
is bigger than n (whatever are x and y),  we get transfinite ordinal  
number.

Example
omega is just N
omega+omega is the ordinal of the order:
   0,     1,     2,     3,     4,     5,       6, ...   0',     1',      
2',     3',     4',     5',       6', ...

omega* omega = omega+omega+omega+omega+omega+omega+omega+ ... = the  
ordinal of the order

0,1,2,3,...0',1',2',3',...0'',1'',2'',3'',...0''',1''',2''',3''',...0'''
',1'''',2'''',3'''',...0''''',1''''',2''''',3''''',...0'''''',1'''''',2'
''''',3'''''',...0''''''',1''''''',2''''''',3''''''', ....

Obviously (ask if this is not clear), the zigzagging showing that  
NUN'UN''UN'''UN''''U ...  is in bijection with N, shows that the  
ordinal
omega* omega is in bijection with N.

Note that all the "..." in

0,1,2,3,...0',1',2',3',...0'',1'',2'',3'',...0''',1''',2''',3''',...0'''
',1'''',2'''',3'''',...0''''',1''''',2''''',3''''',...0'''''',1'''''',2'
''''',3'''''',...0''''''',1''''''',2''''''',3''''''', ....

have the usual interpretation, except the last one, which supposes you  
have grasped the process for generating that ordinal. (Compare may be  
with Thorgny's ultrafinitist rebuilding of the ordinals, but only if  
you grasp well the non-ultrafinitist one before).

All transfinite ordinal we have used with the first fairy (to give her  
a big finite number) were enumerable (= in bijection with N).

This ends the little introduction to the notion of bijection, and of  
(infinite) enumeration (= bijection with N).

Next, I will show the existence of bigger infinities, that is, of  
infinite set which cannot be put in a bijective correspondence with N.  
You can prepare yourself with the set

NXNXNXNXNXNXNXNX ...  (the infinite cartesian product of N with itself)

This is the set of omega-uples of natural number. It is the set of (x,  
y, z, r, s, t, u, ...) with x, z, ... all belonging to N. So it is also  
the set of sequences of natural numbers, and so it is also the set of  
functions from N to N.

or you can take even just, putting 2 for the set {0,1} the infinite  
product of 2 with itself

2X2X2X2X2X2X2X2X2X2X2X ...  (the infinite cartesian product of {0, 1}  
with itself),

This is the set of infinite binary sequences, or the set of functions  
from N to 2, where 2 is put for {0,1}.

I guess many of you knows that such sets are NOT enumerable, and that  
this can be proved by one application of Cantor's diagonal. But I will  
explain this in detail. The reason is not that we will have some use of  
that result, but just because it is the simplest use of a diagonal.

Only after that, I will be able to explain, by a similar but a bit  
subtle diagonal, why Church thesis, and even more generally the  
hypothesis asserting there exist a universal computing machine, is a  
quite strong postulate whose impact on the everything theories, the  
measure problem, etc. is incalculable ...
This is needed to have a thorough understanding of the seventh and  
eighth steps of the UDA. But my main goal long term is to answer  
precisely a question by David about the origin and importance of the  
first person in the comp frame.

So the sequel is:

1) Cantor's diagonal
2) are there universal computing machine? (Kleene's diagonal, and  
Church thesis)

3) A fundamental theorem about universal computing machines. (All such  
machine are imperfect, or insecure)

Please ask questions. To miss math due to notation problem is like to  
miss travels due to mishandling of the use of maps, or to miss love by  
mishandling of the use of clothes ... It is missing a lot, for  
mishandling a few I wanna say.

Bruno

http://iridia.ulb.ac.be/~marchal/

thank you for posting the solutions. Of course, I solved it by myself
and it was a fine relaxing time to do the paper work trying to be
rigorous, however, your solutions gave me additional insights, nice.

I am on the board for the sequel.

Best,
 Mirek

>
> I give the solution of the little exercises on the notion of bijection.
>

>

> So the sequel is:
>
> 1) Cantor's diagonal
> 2) are there universal computing machine? (Kleene's diagonal, and  
> Church thesis)
>
> 3) A fundamental theorem about universal computing machines. (All such  
> machine are imperfect, or insecure)
>
> Please ask questions. To miss math due to notation problem is like to  
> miss travels due to mishandling of the use of maps, or to miss love by  
> mishandling of the use of clothes ... It is missing a lot, for  
> mishandling a few I wanna say.
>

This points on one among many ways to handle Russell's paradox. Type
Theories (TT) are nice, but many logicians prefer some untyped set
theory, like ZF, or a two types theory like von Neuman Bernays Godel
(VBG). Or Cartesian closed categories, toposes, etc. But set theory is
a bit out of the scope of this thread.
All such theories (ZF, VBG, TT) are example of "Lobian Machine", and my
goal is to study all such machine without choosing one in particular,
and using traditional math, instead of working really "in" some
particular theories.

Another solution for many paradoxes consists in working with
constructive objects. Soon, this is what we will do, by focusing on the
set of "computable functions" instead of the set of all functions.  The
reason is not to escape paradoxes though. The reason is to learn
something about machines (which are finite or constructive object).
Just wait a bit. I will first explain Cantor's diagonal, which is
simple but rather "transcendental".

>  Compare this with the case of the biggest natural number:
>
>  Construct the set N of all natural numbers.  For this set N there
> will be the rule: For all x, if N contains x, then N contains x+1.
>
>  Suppose that there exists a biggest natural number m in N.  If we
> substitute m for x, then we get: If N contains m, then N contains
> m+1.  This is a contradiction, because m+1 is bigger than m, so m can
> not be the biggest number then.
>
>  But the contradiction is caused by an illegal conclusion, it is
> illegal to substitute m for x in the "For all x"-quantifier above.
>
>  This paradox is solved by "type theory".  If you say that all
> ordinary natural numbers are of type 0, then the natural number m will
> be of type 1.  And every all-quantifiers are restricted to objects of
> a special type.  So the rule above should read: For all x of type 0,
> if N contains x, then N contains x+1.
>
>  In this case you will not get any contradiction, because you can not
> substitute m for x in that rule.
>
>  ===========
>
>  Do you see the similarities in both these cases?
>

Except that naive usual number theory does not lead to any paradox,
unlike naive set theory.
*you* got a paradox because of *your* ultrafinistic constraint.
So you are proposing a medication which could be worst that the disease
I'm afraid.
Very few people have any trouble with the potential infinite N = omega
= {0, 1, 2, 3, 4, 5, ...}. With comp it can be shown that you don't
need more at the ontological third person level. What will happen is
that infinities come back in the first person point of views, and are
very useful and lawful. Now, sound Lobian Machines can disagree on the
real status of some of those infinities, but this does not concern us,
at least, not urgently, I think.

Bruno

http://iridia.ulb.ac.be/~marchal/

Le 19-nov.-07, à 20:14, Mirek Dobsicek a écrit :

>
> Hi Bruno,
>
> thank you for posting the solutions. Of course, I solved it by myself
> and it was a fine relaxing time to do the paper work trying to be
> rigorous, however, your solutions gave me additional insights, nice.
>
> I am on the board for the sequel.

Thanks.

I will explain soon (this "afternoon") how Cantor managed to show that
some infinite set "have more elements" than the infinite set N,  in the
sense that there will be no bijection from N to such set, despite
obvious bijection between N and subset of such set.

I am sure most of you know that proof by diagonal. However, the goal
will be to show later how a similar reasoning can put a serious doubt
on the existence of universal machine, and on serious constraints such
machine have to live with in case we continue to believe in their
existence.

Before doing that, I want to explain briefly the difference between
ordinal and cardinal. This explanation is not necessary for the sequel,
but it could help.

I will also use the set representation of numbers and ordinals. So I
will represent the number 0 by the empty set, and the number n by the
set of numbers strictly little than n.

So 0 = { },  1 = {0} = {{}},   2 = {0, 1} = {{} {{}}},   3 = {0, 1, 2},
4 = {0, 1, 2, 3}, ...
then omega = N =  {0, 1, 2, 3 ...} is the least infinite ordinal. The
advantage of such a representation is that "belongness" modelizes the
strictly-lesser-than relation, and subsetness modelizes the
lesser-than-or equal. I recall that A is a subset of B, if for all x, x
belongs to A entails that x belongs to B. In particular for all set A x
belongs to A entails x belongs to A, so all sets are subset of
themselves.

An ordinal is defined by being a linear well founded order.
Well-foundness means that all subsets have a least element.

The finite ordinal are thus the natural numbers. They all have
different cardinals. That is, two different natural numbers (=
different finite ordinal) have different cardinality (different
"number" of elements). Take 7 and 5, there is no bijection between
them, for example.

So in the finite realm, ordinal and cardinal coincide.

But infinite ordinals can be different, and still have the same
cardinality. I have given examples: You can put an infinity of linear
well founded order on the set N = {0, 1, 2, 3, ...}.
The usual order give the ordinal omega = {0, 1, 2, 3, ...}. Now omega+1
is the set of all ordinal strictly lesser than omega+1, with the
convention above. This gives {0, 1, 2, 3, ... omega} = {0, 1, 2, 3, 4,
....{0, 1, 2, 3, 4, ....}}. As an order, and thus as an ordinal, it is
different than omega or N. But as a cardinal omega and omega+1 are
identical, that means (by definition of cardinal) there is a bijection
between omega and omega+1. Indeed, between  {0, 1, 2, 3, ... omega} and
{0, 1, 2, 3, ...}, you can build the bijection:

0--------omega
1--------0
2--------1
3--------2
...
n ------- n-1
...

All right?    "-----" represents a rope.

To sum up; finite ordinal and finite cardinal coincide. Concerning
infinite "number" there are much ordinals than cardinals. In between
two different infinite cardinal, there will be an infinity of ordinal.
We have already seen that omega, omega+1, ... omega+omega,
omega+omega+1, ....3.omega, ... 4.omega .... ....omega.omega .....
omega.omega.omega, .....omega^omega ..... are all different ordinals,
but all have the same cardinality.

Don't worry, we will not use that.

Question: are there really two different infinite cardinals? That is,
are there two infinite sets with different cardinality? That is, are
there two different infinite sets A and B without any bijection in
between ? The answer is yes, and that is what cantor has discovered by
its diagonal construction, and that is the object of the next post. All
what I did want to say here, is that automatically, in between A and B,
there will be an infinite amount of different ordinals.

Bruno

http://iridia.ulb.ac.be/~marchal/

>
> To sum up; finite ordinal and finite cardinal coincide. Concerning
> infinite "number" there are much ordinals than cardinals. In between
> two different infinite cardinal, there will be an infinity of ordinal.
> We have already seen that omega, omega+1, ... omega+omega,
> omega+omega+1, ....3.omega, ... 4.omega .... ....omega.omega .....
> omega.omega.omega, .....omega^omega ..... are all different ordinals,
> but all have the same cardinality.
>  

--
Torgny

Yes, that is true.

>  So omega^omega can not have the same cardinality as omega.

But addition, multiplication, and thus exponentiation are not the same
operation for ordinals and cardinals. I should have written
omega"^"omega, or something like that. That is why I have written
3.omega instead of 3*omega.

We can come back on ordinal later, but now I will focus the attention
on the cardinals, and prove indeed that 2^omega, or 2^N, or
equivalently the infinite cartesian product (of sets)
2X2X2X2X2X2X2X2X... , is NOT enumerable (and indeed vastly bigger that
the ordinal omega"^"omega.

You can look at the thread on the growing functions for a little more
on the ordinals. Actually my point was to remind people of the
difference between ordinal and cardinal, and, yes, they have different
addition, multiplication, etc.

Bruno

http://iridia.ulb.ac.be/~marchal/

David, are you still there? This is a key post, with respect to the
"Church Thesis" thread.

So let us see that indeed there is no bijection between N and 2^N =
2X2X2X2X2X2X... = {0,1}X{0,1}X{0,1}X{0,1}X... = the set of infinite
binary sequences.

Suppose that there is a bijection between N and the set of infinite
binary sequences. Well, it will look like that, where again "----"
represents the "ropes":

0  -------------- (1, 0, 0, 1, 1, 1, 0 ...
1 --------------  (0, 0, 0, 1, 1, 0, 1 ...
2 --------------- (0, 1, 0, 1, 0, 1, 1, ...
3 --------------- (1, 1, 1, 1, 1, 1, 1, ...
4 --------------- (0, 0, 1, 0, 0, 1, 1, ...
5 ----------------(0, 0, 0, 1, 1, 0, 1, ...
...

My "sheep" are the natural numbers, and my neighbor's sheep are the
infinite binary sequences (the function from N to 2, the elements of
the infinite cartesian product 2X2X2X2X2X2X... ).
My flock of sheep is the *set* of natural numbers, and my neighbor's
flock of sheep is the *set* of all infinite binary sequences.

Now, if this:

0  -------------- (1, 0, 0, 1, 1, 1, 0 ...
1 --------------  (0, 0, 0, 1, 1, 0, 1 ...
2 --------------- (0, 1, 0, 1, 0, 1, 1, ...
3 --------------- (1, 1, 1, 1, 1, 1, 1, ...
4 --------------- (0, 0, 1, 0, 0, 1, 1, ...
5 ----------------(0, 0, 0, 1, 1, 0, 1, ...
...

is really a bijection, it means that all the numbers 1 and 0 appearing
on the right are well determined (perhaps in Platonia, or in God's
mind, ...).

But then the diagonal sequence, going from the left up to right down,
and build from the list of binary sequences above:

1 0 0 1 0 0 ...

is also completely well determined (in Platonia or in the mind of a
God).

But then the complementary sequence (with the 0 and 1 permuted) is also
well defined, in Platonia or in the mind of God(s)

0 1 1 0 1 1 ...

But this infinite sequence cannot be in the list, above. The "God" in
question has to ackonwledge that.
The complementary sequence is clearly different
-from the 0th sequence (1, 0, 0, 1, 1, 1, 0 ..., because it differs at
the first (better the 0th)  entry.
-from the 1th sequence (0, 0, 0, 1, 1, 0, 1 ...  because it differs at
the second (better the 1th)  entry.
-from the 2th sequence (0, 0, 0, 1, 1, 0, 1 ...  because it differs at
the third (better the 2th)  entry.
and so one.
So, we see that as far as we consider the bijection above well
determined (by God, for example), then we can say to that God that the
bijection misses one of the neighbor sheep, indeed the "sheep"
constituted by the infinite binary sequence complementary to the
diagonal sequence cannot be in the list, and that sequence is also well
determined (given that the whole table is).

But this means that this bijection fails. Now the reasoning did not
depend at all on the choice of any particular bijection-candidate.  Any
conceivable bijection will lead to a well determined infinite table of
binary numbers. And this will determine the diagonal sequence and then
the complementary diagonal sequence, and this one cannot be in the
list, because it contradicts all sequences in the list when they cross
the diagonal (do the drawing on paper).

Conclusion: 2^N, the set of infinite binary sequences, is not
enumerable.

All right?

  Next I will do again that proof, but with notations instead of
drawing, and I will show more explicitly how the contradiction arise.

Exercice-training: show similarly that N^N, the set of functions from N
to N, is not enumerable.

Bruno

http://iridia.ulb.ac.be/~marchal/

On 20/11/2007, Bruno Marchal <mar...@ulb.ac.be> wrote:

> David, are you still there? This is a key post, with respect to the
> "Church Thesis" thread.

Sorry Bruno, do forgive me - we seem destined to be out of synch at
the moment.  I'm afraid I'm too distracted this week to respond
adequately - back on-line next week at the latest.

David

Bruno Marchal wrote:
> .
>
> But infinite ordinals can be different, and still have the same
> cardinality. I have given examples: You can put an infinity of linear
> well founded order on the set N = {0, 1, 2, 3, ...}.

What is the definition of "linear well founded order"?  I'm familiar
with "well ordered", but how is "linear" applied to sets?  Just curious.

Brent Meeker

>
> But infinite ordinals can be different, and still have the same
> cardinality. I have given examples: You can put an infinity of linear
> well founded order on the set N = {0, 1, 2, 3, ...}.
> The usual order give the ordinal omega = {0, 1, 2, 3, ...}. Now omega+1
> is the set of all ordinal strictly lesser than omega+1, with the
> convention above. This gives {0, 1, 2, 3, ... omega} = {0, 1, 2, 3, 4,
> ....{0, 1, 2, 3, 4, ....}}. As an order, and thus as an ordinal, it is
> different than omega or N. But as a cardinal omega and omega+1 are
> identical, that means (by definition of cardinal) there is a bijection
> between omega and omega+1. Indeed, between  {0, 1, 2, 3, ... omega} and
> {0, 1, 2, 3, ...}, you can build the bijection:
>
> 0--------omega
> 1--------0
> 2--------1
> 3--------2
> ...
> n ------- n-1
> ...
>
> All right?    "-----" represents a rope.
>  

In the last line of this sequence you will have:

? --------- omega-1

But what will the "?" be?  It can not be omega, because omega is not
included in N...

--
Torgny

  Cantor's proof disqualifies any candidate enumeration.  You respond  
by saying, "well, here's another candidate!"  But Cantor's procedure  
disqualified *any*, repeat *any* candidate enumeration.

Barry Brent

Dr. Barry Brent
barry...@earthlink.net
http://home.earthlink.net/~barryb0/

Torgny Tholerus wrote:
  

An ultrafinitist comment to this:
======
You can add this complementary sequence to the end of the list.  That 
will make you have a list with this complementary sequence included.

But then you can make a new complementary sequence, that is not 
inluded.  But you can then add this new sequence to the end of the 
extended list, and then you have a bijection with this new sequence 
also.  And if you try to make another new sequence, I will add that 
sequence too, and this I will do an infinite number of times.  So you 
will not be able to prove that there is no bijection...
======
What is wrong with this conclusion?
    

You'd have to insert the new sequence in the beginning, as there is no 
"end of the list".

  

Why can't you add something to the end of the list?  In an earlier message Bruno wrote:

"Now omega+1 is the set of all ordinal strictly lesser than omega+1, with the convention above. This gives {0, 1, 2, 3, ... omega} = {0, 1, 2, 3, 4, ....{0, 1, 2, 3, 4, ....}}."

>
> On 20/11/2007, Bruno Marchal <mar...@ulb.ac.be> wrote:
>
>> David, are you still there? This is a key post, with respect to the
>> "Church Thesis" thread.
>
> Sorry Bruno, do forgive me - we seem destined to be out of synch at
> the moment.  I'm afraid I'm too distracted this week to respond
> adequately - back on-line next week at the latest.

Take it easy. It is the main advantage of electronical conversation,
unlike the phone, we can answer at the best moment. But I appreciate
you tell me.

"See" you next week.

Bruno

PS I'm afraid I have not the time to comment the last posts today,
except for elementary question perhaps, but I will have more time soon
(probably or hopefully tomorrow).

http://iridia.ulb.ac.be/~marchal/

By linear, I was just meaning a non branching order. A tree can be well
founded too, meaning all its branches have a "length" given by an
ordinal.

Bruno

http://iridia.ulb.ac.be/~marchal/

>
> You're saying that, just because you can *write down* the missing
> sequence (at the beginning, middle or anywhere else in the list), it
> follows that there *is* no missing sequence.  Looks pretty wrong to me.
>
>   Cantor's proof disqualifies any candidate enumeration.  You respond
> by saying, "well, here's another candidate!"  But Cantor's procedure
> disqualified *any*, repeat *any* candidate enumeration.
>
> Barry Brent

Torgny, I do agree with Barry. Any bijection leads to a contradiction,
even in some effective way, and that is enough (for a classical
logician).

But look what you write:

> On Nov 20, 2007, at 11:42 AM, Torgny Tholerus wrote:
>

>>
>> An ultrafinitist comment to this:
>> ======
>> You can add this complementary sequence to the end of the list.
>> That will make you have a list with this complementary sequence
>> included.
>>
>> But then you can make a new complementary sequence, that is not
>> inluded.  But you can then add this new sequence to the end of the
>> extended list, and then you have a bijection with this new sequence
>> also.  And if you try to make another new sequence, I will add that
>> sequence too, and this I will do an infinite number of times.

How could an ultrafinitist refute an argument by saying "... and this I
will do an infinite number of times. "?

>> So
>> you will not be able to prove that there is no bijection...

Actually no. If you do what you described omega times, you will just
end up with a set which can still be put in 1-1 correspondence with N
(as shown in preceding posts on bijections)
To refute Cantor, here, you should do what you described a very big
infinity of times, indeed an non enumerable infinity of times. But then
you have to assume the existence of a non enumerable set at the start.
OK?

Bruno
http://iridia.ulb.ac.be/~marchal/

>> ======
>> What is wrong with this conclusion?
>>
>> --
>> Torgny
>>
>>>
>
> Dr. Barry Brent
> barry...@earthlink.net
> http://home.earthlink.net/~barryb0/
>
>
>
>
> >
>

Adding something to the end or to the middle or to the beginning of an
infinite  list, does not change the cardinality of that list. And in
Cantor proof, we are interested only in the cardinality notion.

Adding something to the beginning or to the end of a infinite ORDERED
list, well, it does not change the cardinal of the set involved, but it
obviosuly produce different order on those sets, and this can give
different ordinal, which denote type of order (isomorphic order).

The ordered set {0, 1, 2, 3, ...} has the same cardinality that the
ordered set {1, 2, 3, 4, ... 0} (where by definition 0 is bigger than
all natural numbers). But they both denote different ordinal, omega,
and omega+1 respectively. Note that {1, 0, 2, 3, 4, ...} is a different
order than {0, 1, 2, 3, ...}, but both order here are isomorphic, and
correspond to the same ordinal (omega).

That is why 1+omega = omega, and omega+1 is different from omega.
Adding one object in front of a list does not change the type of the
order. Adding an element at the end of an infinite list does change the
type of the order. {0, 1, 2, 3, ...} has no bigger element, but {1, 2,
3, ... 0} has a bigger element. So, you cannot by simple relabelling of
the elements get the same type of order (and thus they correspond to
different ordinals).

OK?  (this stuff will not be used for Church Thesis, unless we go very
far ...later).

Bruno

http://iridia.ulb.ac.be/~marchal/

Barry

Dr. Barry Brent
barry...@earthlink.net
http://home.earthlink.net/~barryb0/

Barry

On Nov 21, 2007, at 10:33 AM, Torgny Tholerus wrote:

Dr. Barry Brent
barry...@earthlink.net
http://home.earthlink.net/~barryb0/

Thanks, very interesting indeed. Note that the original paper is
accessible from the  New Scientist entry. Not so easy to read (need of
differential geometry, simple groups, etc.
Quite close to the idea of the importance of 24 which I mention
periodically ... :)

Now such work raises the remark, which I don't really want to develop
now, which is that qualifiying "TOE" a theory explaining "only" forces
and particles or field, is implicit physicalism, and we know (by UDA)
that this is incompatible with comp.

Yet I bet Lisi is quite close to the sort of physics derivable by
machine's or number's introspection. Actually, getting physics from so
"few" symmetries is a bit weird (I have to study the paper in detail).
With comp, we have to explain the symmetries *and* the geometry, and
the quantum logic, from the numbers and their possible stable
discourses ... If not, it is not a theory of everything, but just a
classification, a bit like the Mendeleev table classifies atoms without
really explaining. But Lisi's theory seems beautiful indeed ...

Bruno

http://iridia.ulb.ac.be/~marchal/

>
> The reason it isn't a bijection (of a denumerable set with the set of
> binary sequences):  the  pre-image (the left side of your map) isn't
> a set--you've imposed an ordering.  Sets, qua sets, don't have
> orderings.  Orderings are extra.  (I'm not a specialist on this stuff
> but I think Bruno, for example, will back me up.)  It must be the
> case that you won't let us identify the left side, for example, with
> {omega, 0, 1, 2, ... }, will you? For if you did, it would fall under
> Cantor's argument.

I agree.
Presently, I prefer not talking too much on the ordinals, because it
could be confusing for many.  More later ...

Bruno

http://iridia.ulb.ac.be/~marchal/

>  What do you think of this "proof"?:
>
>  Let us have the bijection:
>
>  0 -------- {0,0,0,0,0,0,0,...}
>  1 -------- {1,0,0,0,0,0,0,...}
>  2 -------- {0,1,0,0,0,0,0,...}
>  3 -------- {1,1,0,0,0,0,0,...}
>  4 -------- {0,0,1,0,0,0,0,...}
>  5 -------- {1,0,1,0,0,0,0,...}
>  6 -------- {0,1,1,0,0,0,0,...}
>  7 -------- {1,1,1,0,0,0,0,...}
>  8 -------- {0,0,0,1,0,0,0,...}
>  ...
>  omega --- {1,1,1,1,1,1,1,...}
>
>  What do we get if we apply Cantor's Diagonal to this?

Note also that in general, we start from what we want to prove, and
then do the math. Your idea of transfinite (ordinal) diagonalisation is
cute though, but I have currently no idea where this could lead. BTW,
it is also funny that such a transfinite idea is proposed by an
ultrafinistist!

I guess you have seen that {(0,0,0,0,0,0,0,...), (1,0,0,0,0,0,0,...),
... does clearly not enumerate the infinite sequences (you don't have
to use the diagonal for showing that. It is also better to use
parentheses instead of accolades, given that the binary sequences are
ordered (notation detail).

Bruno

http://iridia.ulb.ac.be/~marchal/

On Nov 23, 1:10 am, Bruno Marchal <marc...@ulb.ac.be> wrote:

>
> Now such work raises the remark, which I don't really want to develop
> now, which is that qualifiying "TOE" a theory explaining "only" forces
> and particles or field, is implicit physicalism, and we know (by UDA)
> that this is incompatible with comp.

> Yet I bet Lisi is quite close to the sort of physics derivable by
> machine's or number's introspection. Actually, getting physics from so
> "few" symmetries is a bit weird (I have to study the paper in detail).
> With comp, we have to explain the symmetries *and* the geometry, and
> the quantum logic, from the numbers and their possible stable
> discourses ... If not, it is not a theory of everything, but just a
> classification, a bit like the Mendeleev table classifies atoms without
> really explaining. But Lisi's theory seems beautiful indeed ...
>
> Bruno
>

>
> As far as I tell tell, all of physics is ultimately
> geometry.  But as we've pointed out on this list many times, a theory
> of physics is *not* a theory of everything, since it makes the
> (probably false) assumption that everything is reducible to physical
> substances and properties.

I think that everything is reducible to physical substances and
properties.  And I think that all of physics is reducible to pure
mathematics...

I have now read Garrett Lisis paper.  It was interesting, but it is
still to early to say if it is important.  There is a lot of symmetries
in the elementary particles, and there is a lot of symmetries in the E8
Lie group.  So it is not any suprise that they both can be mapped on
each other.  Lisi has mapped 222 elementary particles on the 242
elements of E8, and he has predicted that the rest of the 20 elements
correspond to 20 yet to be discovered elementary particles.  If it is
true, then Lisi will have the Nobel price.  If it is not, then we will
have to look for another TOE.

But it is possible that we will never find any TOE.  Because there is
10^500 different possiblities for our universe, and all of these 10^500
universes exist in the same way.  By experiments we will have to decide
which of those that is our universe, but we will never reach the correct
answer, the number of experiments needed will be too many.

--
Torgny

>  Hi Bruno,
>
>  I am reopening an old thread ( more than a year old) which I found
> very intriguing. It leads to some startling conclusions.
>
>  Le 05-août-06, à 02:07, George Levy a écrit :
>
>  Bruno Marchal wrote:I think that if you want to
>> make the first person primitive, given that neither you nor me can
>>  really define it, you will need at least to axiomatize it in some
>> way.
>>  Here is my question. Do you agree that a first person is a knower,
>> and
>>  in that case, are you willing to accept the traditional axioms for
>>  knowing. That is:
>>
>>  1) If p is knowable then p is true;
>>  2) If p is knowable then it is knowable that p is knowable;
>>  3) if it is knowable that p entails q, then if p is knowable then q
>> is
>>  knowable
>>
>>  (+ some logical rules).
>>
>

>  Bruno, what or who do you mean by "it" in statements 2) and 3).

The same as in "it is raining". I could have written 1. and 2. like

1) knowable(p) -> p
2) knowable(p) -> knowable(knowable(p))

In this way we can avoid using words like "it", or even like "true".  
"p" is a variable, and is implicitly universally quantified over.
"knowable(p) -> p" really means that whatever is the proposition p, if
it is knowable then it is true. The false is unknowable (although it
could be conceivable, believable, even provable (in inconsistent
theory), etc. The "p" in 1. 2. and 3.  is really like the "x" in the
formula (sin(x))^2 + (cos(x))^2 = 1.

"knowable(p) -> p" really means that we cannot know something false.
This is coherent with the natural language use of know, which I
illustrate often by remarking that we never say "Alfred knew the earth
is flat, but the he realized he was wrong". We say instead "Alfred
believed that earth is flat, but then ...". . The axiom 1. is the
incorrigibility axiom: we can know only the truth. Of course we can
believe we know something until we know better.
The axiom 2. is added when we want to axiomatize a notion of knowledge
from the part of sufficiently introspective subject. It means that if
some proposition is knowable, then the knowability of that proposition
is itself knowable. It means that when the subject knows some
proposition then the subject will know that he knows that proposition.
The subject can know that he knows.

> In addition, what do you mean by "is knowable", "is true" and
> "entails"?

All the point in axiomatizing some notion, consists in giving a way to
reason about that notion without ever defining it. We just try to agree
on some principles, like 1.,2., 3., and then derives things from those
principles. Nuance can be added by adding new axioms if necessary.
Of course axioms like above are not enough, we have to use deduction
rules. In case of the S4 theory, which I will rewrite with modal
notation (hoping you recognize it). I write Bp for B(p) to avoid
heaviness in the notation, likewize, I write BBp for B(B(p)).

1) Bp -> p   (incorrigibility)
2) Bp -> BBp  (introspective knowledge)
3) B(p->q) -> (Bp -> Bq)  (weak omniscience, = knowability of the
consequences of knowable propositions).

Now with such axioms you can derive no theorems (except the axiom
themselves). So you need some principles which give you a way to deduce
theorems from axioms. The usual deduction rule of S4 are the
substitution rule, the modus ponens rule and the necessitation rule.
The substitution rule say that you can substitute p by any proposition
(as far as you avoid clash of variable, etc.). The modus ponens rule
say that if you have already derived some formula A, and some formula A
-> B, then you can derive B. The necessitation rule says that if you
have already derive A, then you can derive BA.

> Are "is knowable", "is true" and "entails" absolute or do they have
> meaning only with respect to a particular observer?

The abstract S4 theory is strictly neutral on this. But abstract theory
can have more concrete models or interpretations. In our lobian
setting, it will happen that "formal provability by a machine" does not
obey the incorrigibility axiom (as Godel notices in his 1933 paper).
This means that formal provability by a machine cannot be used to
modelize the knowability of the machine. It is a bit counterintuitive,
but formal provability by a machine modelizes only a form of "opinion"
by the machine, so that to get a knowability notion from the
provability notion, we have to explicitly define knowability(p)  by
"provability(p) and p is true". (Cf Platos's Theaetetus).
Here provability and knowability is always relative to an (ideal)
machine.
I will come back on this in my explanation to David later. But don't
hesitate to ask question before.

> Can these terms be relative to an observer? If they can, how would you
> rephrase these statements?

An observer ? I guess you mean a subject. Observability could obeys
quite different axioms that knowability (as it is the case for machine
with comp).
Just interpret "knowable(p)" by "p is knowable by M".
"M" denotes some machine or entity belonging to some class of
machine/entity in which we are interested.

>  One more question: can or should p be the observer?

"p" has to refer to a proposition. Of course in english (at least in
french) we often use similar word with different denotation or meaning.
For example, you can say "I know Paul". And Paul, a priori is not a
poposition. But such a "know" is not the same as in "I know that Paul
is a good guy".
S4 is a good candidate for the second "know". The "know" (in "I know
Paul") has a quite different meaning, somehow out of topic (to be
short). Actually "I know Paul" really means humans variate and
pragmatic things like "I met Paul before", or "I know Paul is not the
right guy to hire for this job", etc.

With the epistemological sense of "knowing", we cannot know a knower,
nor an observer. We can only know propositions. Those proposition
copuld bear on a knower: like in I know that Paul know that 17 is
prime. Sure.
Of course we can observe an observer. This illustarte already that
observations and knowledge obeys different logics; hopefully related,
of course, as it is with the arithmetical hypostases).

Oops, I must already go. Have a good week-end, George, and all of you,

Bruno

PS Marc, Thorgny: I will comment your post Monday or Tuesday.

http://iridia.ulb.ac.be/~marchal/

>
>
>
> > As far as I tell tell, all of physics is ultimately
> > geometry.  But as we've pointed out on this list many times, a theory
> > of physics is *not* a theory of everything, since it makes the
> > (probably false) assumption that everything is reducible to physical
> > substances and properties.
>
> I think that everything is reducible to physical substances and
> properties.  And I think that all of physics is reducible to pure
> mathematics...

S4 is a normal modal logic with natural Kripke referentials
(transitive, reflexive accessibility relations).

A bit more problematic is your identification of "true" with "exist".  
This hangs on possible but highly debatable and complex relations
between truth and reality. This is interesting per se, but imo a bit
out of topics, or premature (in current thread). Perhaps we will have
opportunity to debate on this, but I want make sure that what I am
explaining now does not depend on those possible relations (between
truth and reality).

Bruno

Le 24-nov.-07, à 21:23, George Levy a écrit :

>>  "p" has to refer to a proposition. Of course in english (at least in
>> french) we often use similar word with different denotation or
>> meaning. For example, you can say "I know Paul". And Paul, a priori
>> is not a poposition. But such a "know" is not the same as in "I know
>> that Paul is a good guy".
>>  S4 is a good candidate for the second "know". The "know" (in "I know
>> Paul") has a quite different meaning, somehow out of topic (to be
>> short). Actually "I know Paul" really means humans variate and
>> pragmatic things like "I met Paul before", or "I know Paul is not the
>> right guy to hire for this job", etc.
>>
>>  With the epistemological sense of "knowing", we cannot know a
>> knower, nor an observer. We can only know propositions. Those
>> proposition copuld bear on a knower: like in I know that Paul know
>> that 17 is prime. Sure.
>>  Of course we can observe an observer. This illustarte already that
>> observations and knowledge obeys different logics; hopefully related,
>> of course, as it is with the arithmetical hypostases).
>>
>>  Oops, I must already go. Have a good week-end, George, and all of
>> you,
>>
>>
>>  Bruno
>>
>>  PS Marc, Thorgny: I will comment your post Monday or Tuesday.
>>
>>
>>
>>
>> http://iridia.ulb.ac.be/~marchal/
>>
>>
>>
>
>
>  >
>

>
>
>
> On Nov 23, 8:49 pm, Torgny Tholerus <tor...@dsv.su.se> wrote:
>> marc.ged...@gmail.com skrev:
>>
>>
>>
>>> As far as I tell tell, all of physics is ultimately
>>> geometry.  But as we've pointed out on this list many times, a theory
>>> of physics is *not* a theory of everything, since it makes the
>>> (probably false) assumption that everything is reducible to physical
>>> substances and properties.
>>
>> I think that everything is reducible to physical substances and
>> properties.  And I think that all of physics is reducible to pure
>> mathematics...
>
> You can't have it both ways.  If physics was reducible to pure
> mathematics, then physics could not be the 'ontological base level' of
> reality and hence everything could not be expressed solely in terms of
> physical substance and properties.

Are you not begging a bit the question here?

>
> Besides which, mathematics and physics are dealing with quite
> different distinctions.  It is a 'type error' it try to reduce or
> identity one with the other.

I don't see why.

>
> Mathematics deals with logical properties,

I guess you mean "mathematical properties". Since the filure of
logicism, we know that math is not really related to logic in any way.
It just happens that a big part of logic appears to be a branch of
mathemetics, among many other branches.

> physics deals with spatial
> (geometric) properties.  Although geometry is thought of as math, it
> is actually a branch of physics,

Actually I do think so. but physics, with comp, has to be the science
of what the observer can observe, and the observer is a mathematical
object, and observation is a mathematical object too (with comp).

> since in addition to pure logical
> axioms, all geometry involves 'extra' assumptions or axioms which are
> actually *physical* in nature (not purely mathematical) .

Here I disagree (so I agree with your preceding post where you agree
that we agree a lot but for not always for identical reasons).
Arithmetic too need extra (non logical) axioms, and it is a matter of
taste (eventually) to put them in the branch of physics or math.

Bruno

http://iridia.ulb.ac.be/~marchal/

some (lay) remarks from another mindset (maybe I completely miss your
points - perhaps even my own ones<G>).
I go with Bruno in a lack of clear understanding what "physical world"
may be. It can be extended into entirely mathematical ideas beside the
likable assumption of it being 'geometrical '  as well as geometry
'completely physical'. I don't see these terms agreed upon as crystal
clearly (maybe my ignorance).
*
Then again "pure"(?) Math, the logical entirety, is in my views
different from the "applied"(?) math of the diverse sciences,
(please note the cap vs lower case distinction, as borrowed from the
late mathematician Robert Rosen)  the latter applying the former's
results to quantities. (I don't want to digress here into my views
about the restricted (topical) aspects of those sciences, omitting the
rest of the totality that, however, may have an effect of those
figments derived as 'scientific quantities' within their boundaries.
It may come up in a separate (different) thread).
To (I think) Torgny's remark

 "> > reality and hence everything could not be expressed solely in

> Arithmetic too need extra (non logical) axioms, and it is a matter of taste (eventually) to put them in the branch of physics or math.<

John M

On Mon, Nov 26, 2007 at 10:51:36AM +0100, Torgny Tholerus wrote:

--

----------------------------------------------------------------------------
A/Prof Russell Standish                  Phone 0425 253119 (mobile)
Mathematics                                 
UNSW SYDNEY 2052                          hpc...@hpcoders.com.au
Australia                                http://www.hpcoders.com.au
----------------------------------------------------------------------------

>When I talk about "pure mathematics" I mean that kind of mathematics you have in GameOfLife.  There you have "gliders" that move in the GameOfLife-universe, and these gliders interact with eachother when they meet.  These gliders you can see as physical objects.  These physical objects are reducible to pure mathematics, they are the consequences of the rules behind GameOfLife.

--
Torgny

On Nov 27, 3:54 am, Bruno Marchal <marc...@ulb.ac.be> wrote:

>
> > Besides which, mathematics and physics are dealing with quite
> > different distinctions.  It is a 'type error' it try to reduce or
> > identity one with the other.
>
> I don't see why.

>
>
>
> > Mathematics deals with logical properties,
>
> I guess you mean "mathematical properties". Since the filure of
> logicism, we know that math is not really related to logic in any way.
> It just happens that a big part of logic appears to be a branch of
> mathemetics, among many other branches.

>
> > physics deals with spatial
> > (geometric) properties.  Although geometry is thought of as math, it
> > is actually a branch of physics,
>
> Actually I do think so. but physics, with comp, has to be the science
> of what the observer can observe, and the observer is a mathematical
> object, and observation is a mathematical object too (with comp).


>
> > since in addition to pure logical
> > axioms, all geometry involves 'extra' assumptions or axioms which are
> > actually *physical* in nature (not purely mathematical) .
>
> Here I disagree (so I agree with your preceding post where you agree
> that we agree a lot but for not always for identical reasons).
> Arithmetic too need extra (non logical) axioms, and it is a matter of
> taste (eventually) to put them in the branch of physics or math.
>
> Bruno
>

> Physics deals with symmetries, forces and fields.
> Mathematics deals with data types, relations and sets/categories.

I'm no physicist, so please correct me but IMHO:

Symmetries = relations
Forces - could they not be seen as certain invariances, thus also
relating to symmetries?

Fields - the aggregate of forces on all spacetime "points" - do not see
why this should not be mathematical relation?

> The mathemtical entities are informational.  The physical properties
> are geometric.  Geometric properties cannot be derived from
> informational properties.

Why not? Do you have a counterexample?

Regards,
Günther

--
Günther Greindl
Department of Philosophy of Science
University of Vienna
guenther...@univie.ac.at
http://www.univie.ac.at/Wissenschaftstheorie/

Blog: http://dao.complexitystudies.org/
Site: http://www.complexitystudies.org

> Geometric properties cannot be derived from
> informational properties.

I don't see why. Above all, this would make the computationalist wrong,
or at least some step in the UDA wrong (but then which one?).
I recall that there is an argument (UDA) showing that if comp is true,
then not only geometry, but physics, has to be derived exclusively from
numbers and from what numbers can prove (and know, and observe, and
bet, ...) about themselves, that is from both extensional and
intensional number theory.
The UDA shows *why* physics *has to* be derived from numbers (assuming
CT + "yes doctor").
The Lobian interview explains (or should explain, if you have not yet
grasp the point) *how* to do that.

Bruno

http://iridia.ulb.ac.be/~marchal/

>  Bruno

Sure. And playing is the best way to learn, as "nature" knows since the
beginning.

> Maybe a computer program could be written to express these staqtements.

I certainly encourage you to do so. Note that for the general modal
theory, S4, or even the comp fist person S4Grz, programs already
exists.
By some aspect your attempt reminds me also of dynamic logic. This is
modal logic applied to computations (and thus a bit away from
"computability" which concerns my more "theological" global concern ;).
You could googelize on "dynamic modal logic". I am not at all an expert
on those logics, to be sure.

Bruno

http://iridia.ulb.ac.be/~marchal/

I have to go, actually. Just to prepare yourself to what will follow,
below are recent links in the list . It could be helpful to revise a
bit, or to ask last questions.
I will ASAP come back on Cantor's Diagonal, (one more post), and then I
will send the key fundamental post where I will present a version of
Church thesis, and explain how from just CT you can already derive what
I will call the first fundamental theorem. This one says that ALL
universal machine (if that exists) are insecure.

It is needed to explain why Lobian machine, which are mainly just
Universal machine knowing that they are universal, cannot not be above
all "theological" machine. As you can guess, knowing that they are
universal, will make them know that they are insecure.

All the term here will be defined precisely. In case you find this
theorem depressing, I suggest you read "The Wisdom of Insecurity" by
Alan Watts (Pantheon Books, Inc. 1951). An amazingly "lobian" informal
philosophical text.

Here are the last posts I send:

1) Bijections 1
http://www.mail-archive.com/everything-lis...m/msg13962.html
2) Bijections 2
http://www.mail-archive.com/everything-lis...m/msg13986.html
3) Bijection 3
http://www.mail-archive.com/everything-lis...m/msg13991.html
4) Cantor's diagonal
http://www.mail-archive.com/everything-lis...m/msg13996.html

Don't hesitate to ask any question if something remains unclear,

Bruno

PS:
I recall the combinators thread, which could help later (but please
don't consult them now, unless you already love lambda calculus or the
combinators).

The old (2005) combinators posts:

http://www.mail-archive.com/everything-list@eskimo.com/msg05920.html
http://www.mail-archive.com/everything-list@eskimo.com/msg05949.html
http://www.mail-archive.com/everything-list@eskimo.com/msg05953.html
http://www.mail-archive.com/everything-list@eskimo.com/msg05954.html
http://www.mail-archive.com/everything-list@eskimo.com/msg05955.html
http://www.mail-archive.com/everything-list@eskimo.com/msg05956.html
http://www.mail-archive.com/everything-list@eskimo.com/msg05957.html
http://www.mail-archive.com/everything-list@eskimo.com/msg05958.html
http://www.mail-archive.com/everything-list@eskimo.com/msg05959.html
http://www.mail-archive.com/everything-list@eskimo.com/msg05961.html

http://iridia.ulb.ac.be/~marchal/

thanks for your posts! I like them very much!
Looking forward to further stuff,

Günther

--

Günther Greindl
Department of Philosophy of Science
University of Vienna
guenther...@univie.ac.at
http://www.univie.ac.at/Wissenschaftstheorie/

Blog: http://dao.complexitystudies.org/
Site: http://www.complexitystudies.org

> Dear Marc,
>
> > Physics deals with symmetries, forces and fields.
> > Mathematics deals with data types, relations and sets/categories.
>
> I'm no physicist, so please correct me but IMHO:
>
> Symmetries = relations
> Forces - could they not be seen as certain invariances, thus also
> relating to symmetries?
>
> Fields - the aggregate of forces on all spacetime "points" - do not see
> why this should not be mathematical relation?
>
> > The mathemtical entities are informational.  The physical properties
> > are geometric.  Geometric properties cannot be derived from
> > informational properties.
>
> Why not? Do you have a counterexample?
>
> Regards,
> Günther
>

>
> > Geometric properties cannot be derived from
> > informational properties.
>
> I don't see why. Above all, this would make the computationalist wrong,
> or at least some step in the UDA wrong (but then which one?).

> I recall that there is an argument (UDA) showing that if comp is true,
> then not only geometry, but physics, has to be derived exclusively from
> numbers and from what numbers can prove (and know, and observe, and
> bet, ...) about themselves, that is from both extensional and
> intensional number theory.
> The UDA shows *why* physics *has to* be derived from numbers (assuming
> CT + "yes doctor").
> The Lobian interview explains (or should explain, if you have not yet
> grasp the point) *how* to do that.
>
> Bruno
>

Sure, but you can't be ultrafinitist and saying things like "And after that

event will follow another more event, and so on unlimited".

Also why do you limit yourself to one computational model ? Turing Machine,
Lambda calcul, cellular automata are all equivalents.

Regards,
Quentin Anciaux

--
All those moments will be lost in time, like tears in the rain.

>
>
>
> On Nov 28, 3:16 am, Bruno Marchal <marc...@ulb.ac.be> wrote:
>> Le 27-nov.-07, à 05:47, marc.ged...@gmail.com a écrit :
>>
>>> Geometric properties cannot be derived from
>>> informational properties.
>>
>> I don't see why. Above all, this would make the computationalist
>> wrong,
>> or at least some step in the UDA wrong (but then which one?).
>
> I'll find the flaw in UDA in due course ;)

Thanks.

>
>> I recall that there is an argument (UDA) showing that if comp is true,
>> then not only geometry, but physics, has to be derived exclusively
>> from
>> numbers and from what numbers can prove (and know, and observe, and
>> bet, ...) about themselves, that is from both extensional and
>> intensional number theory.
>> The UDA shows *why* physics *has to* be derived from numbers (assuming
>> CT + "yes doctor").
>> The Lobian interview explains (or should explain, if you have not yet
>> grasp the point) *how* to do that.
>>
>> Bruno
>>
>
> If the UDA is sound that would certainly refute what I'm claiming
> yes.
> I want to see how physics (which as far I'm concerned *is*
> geometry - at least I think pure physics=geometry) emerges *purely*
> from theories of sets/numbers/categories.

OK. Note that UDA says only why, not how.
"how" is given by the lobian interview, and gives only the
"propositional physics" (as part
of the propositional "theology").

>
> I base my claims on ontological considerations (5 years of deep
> thought about ontology), which lead me to strongly suspect the
> irreducible property dualism between physical and mathematical
> properties.  Thus I'm highly skeptical of UDA but have yet to property
> study it.  Lacking resources to do proper study here at the
> moment.... :-(

We are in the same boat ...

Bruno

http://iridia.ulb.ac.be/~marchal/

OK. Do you agree now that the "real Torgny", by which I mean you from
your first person point of view, cannot known if it belongs to a state
generated by automata 345 or automata 6756, or automata 6756690003121,
or automata  65656700234676611084899 , and so one ...
Do you agree we have to take into account this first person
indeterminacy when making a first person prediction?

Bruno

http://iridia.ulb.ac.be/~marchal/

>
> Dear Bruno,
>
> thanks for your posts! I like them very much!
> Looking forward to further stuff,

Thanks for telling.

In this post I recall Cantor's proof of the non enumerability of the
set of infinite binary sequences. First with a drawing, and then with
mathematical notation. The goal is to train you with the notations.
Then I do the same with the almost exactly identical proof that the set
of functions from N to N is also non enumerable.

I hope you have no more problem with the identification of the set of
functions from N to 2 (where 2 = {0, 1}), with the set of infinite
binary sequences. Please ask in case of any trouble with that. A
function from N to any set A always gives rise to an infinite sequence
of elements of A.

Note that I will never use Cantor's result. I explain it just to
illustrate the use of diagonalization, and to contrast it with the use
in the next post which will illustrate a capital feature of all
universal machine.

                            ***

1) 2^N is not enumerable (proof by drawing)

Cantor argument goes like this. It is a reductio ad absurdo:

Suppose that the set of infinite binary sequence is enumerable.
That means that there is a bijection between N and that set. Such
a bijection will have a shape like:

0    --------     000101101111010100111...
1    --------     011111111010100110000...
2    --------    100011001001000100110...
3    --------    101010101001010100100...
4    --------    100000000001001111010...
5    --------    000111111111100000010...
...

But then I can find an infinite binary sequence which *cannot* be in
the image of that "bijection". Indeed here is one:

1 0 1 1 1 0 ...

It is the complementary sequence build from the diagonal sequence.  QED.

                      ***

1bis) 2^N is not enumerable (proof without drawing).

Suppose that the set of binary infinite sequences is enumerable.
That means there is a bijection between N and that set. It means that
for each natural number i, there is a corresponding sequence s_i, and
that all infinite binary sequences belongs somewhere in the enumeration

s_0  s_1 s_2 s_3 s_4 s_5 ...

Each s_i is a function from N to 2. For example, if s_0 denote the
first sequence in the "drawing" above, it means that s_0(0) = 0, s_0(1)
= 0, s_0(2) = 0, s_0(3) = 1, s_0(4) = 0, s_0(5) = 1, s_0(6) =1, etc.
That is, s_i(j) the jth number (0 or 1) in the sequence s_i.
s_i(j) gives the matrix drawn above, for i and j natural numbers.

Then the number s_i(i), for i natural numbers gives the diagonal
sequence, and the sequence 1- s_i(i) gives the complementary of the
diagonal, and that sequence cannot belongs to the list of the s_i.

We can make explicit the contradiction. If the sequence 1- s_i(i) was
in the list s_i, there would exist a number k such that s_k(x) = 1 -
s_x(x). But then for x = k, s_k(k) = 1 - s_k(k). But s_k(k) has to be
one or zero, and in the first case you get 1 = 1 - 1 = 0, and in the
other case you get 0 = 1 - 0 = 1. Contradiction.

Damn... I must already go. I suggest you work by yourself the very
similar proof that N^N is not enumerable. Of course you can derive this
immediately from what we have just seen, given that a function from N
to 2, is a particular case of a function from N to N. But it is a good
training in *diagonalisation* to find the direct proof.

I hope you can see that the set of all functions from N to N can be
identify with the set NXNXNX... of sequences of natural numbers.

I do quickly the "drawing proof", and let you write the more explicit
proof (without drawing).

Suppose there is such a bijection. It will look like:

0 -------- 23   456   76    67 ...
1 --------  0    8         23    5   ...
2 -------- 67   10     10    123 ...
3 --------  9    0        0      4   ...
...

But then the sequence of numbers:

   24   9  11   5 ....

cannot be in that list. All right?

See you tomorrow,

Bruno

http://iridia.ulb.ac.be/~marchal/

>
>
> Le 28-nov.-07, à 09:56, Torgny Tholerus a écrit :
>

>     You only need models of cellular automata.  If you have a model
>     and rules for that model, then one event will follow after another
>     event, according to the rules.  And after that event will follow
>     another more event, and so on unlimited.  The events will follow
>     after eachother even if you will not have any implementation of
>     this model.  Any physics is not needed.  You don't need any
>     geometric properties.
>
>     In this model you may have a person called Torgny writing a
>     message on a google group, and that event may be followed by a
>     person called Marc writing a reply to this message.  And you don't
>     need any implementation of that model.
>
>
>
> OK. Do you agree now that the "real Torgny", by which I mean you from
> your first person point of view, cannot known if it belongs to a state
> generated by automata 345 or automata 6756, or automata 6756690003121,
> or automata 65656700234676611084899 , and so one ...
> Do you agree we have to take into account this first person
> indeterminacy when making a first person prediction?

I agree that the "real Torgny" belongs to exactly one of those automata,
but I don't know which one.  So I can not tell what will happen to the
"real Torgny" in the future.  I can not do any prediction.

If we call the automata that the "real Torgny" belongs to, for automata
X, then I can look at automata X from the outside, and I will then see
that all that the "real Torgny" will do in the future is completely
determined.  There is no indeterminacy in automata X.

--
Torgny

I'm ready. Luckily, it is not long time ago, I've received my university
degree in CS, so it was rather easy to follow :-)

Sincerely,
 Mirek

Bruno Marchal wrote:
>
> Le 27-nov.-07, à 17:27, Günther Greindl a écrit :
>
>> Dear Bruno,
>>
>> thanks for your posts! I like them very much!
>> Looking forward to further stuff,
>
>
>
> Thanks for telling.
>
>
> In this post I recall Cantor's proof of the non enumerability of the
> set of infinite binary sequences. First with a drawing, and then with
> mathematical notation. The goal is to train you with the notations.
> Then I do the same with the almost exactly identical proof that the set
> of functions from N to N is also non enumerable.

On Nov 28, 9:56 pm, Torgny Tholerus <tor...@dsv.su.se> wrote:

>
> You only need models of cellular automata.  If you have a model and
> rules for that model, then one event will follow after another event,
> according to the rules.  And after that event will follow another more
> event, and so on unlimited.  The events will follow after eachother even
> if you will not have any implementation of this model.  Any physics is
> not needed.  You don't need any geometric properties.
>
> In this model you may have a person called Torgny writing a message on a
> google group, and that event may be followed by a person called Marc
> writing a reply to this message.  And you don't need any implementation
> of that model.
>
> --
> Torgny

Le 28-nov.-07, à 17:32, Mirek Dobsicek a écrit :

>
> Hi Bruno,
>
> I'm ready. Luckily, it is not long time ago, I've received my
> university
> degree in CS, so it was rather easy to follow :-)
>
> Sincerely,
>  Mirek

Thanks for telling me that you are ready. Now I feel a bit guilty
because today and tomorrow I get unexpected work, and next week I am
teaching again.
I hope that those who have no university degree in CS have been able to
follow the thread too.

I will try to resume the last exercise tomorrow, (one last post on
Cantor's diagonal), and then, I will write, during next week, the key
post, which will prove an absolutely fundamental theorem on the
Universal Machines, a theorem without which UDA would be stuck in the
sixth step, and without which the lobian interview would not make
sense. The theorem says that ALL universal machines are insecure or
imperfect. I guess some of you can already guess or produce the proof
(in company of a general definition of "secure machine", 'course).

Torgny,

You should be clearer about when you work *in* your ultrafinistic
theory and when you work in its metatheory. If not, Quentin is right to
ask you not to mention any sort of "infinite" of any kind. Most of the
time, it is very hard to make sense of your approach, due to the lack
of a clear distinction between the ultrafinistic theory and the
informal metatheory you do refer to, very often.
Note that without the movie graph (the 8th step of the UDA), comp
remains coherent *only* through an explicitly physicalist version of
ultrafinitism and an explicitly dualist theory of Mind (perhaps you
should collaborate with Marc?). Mind would need matter (but then why,
and what is it?), and the UDA would not go through because we would
live in a unique and then very little universe. I guess everythingers
would be skeptical at the start, here. Also the quantum facts are going
in an opposite direction, imo.
Actually, the movie-graph prevents such a move, I think. We can go back
on this, later. To be sure I am open to critics there, I am not
entirely satisfied with my presentation of the argument, and both
George and Russell did succeed in making me thinking a lot more on that
issue,  or of the way to present it perhaps (more than I was
expecting).

Bruno

http://iridia.ulb.ac.be/~marchal/

> Hi,
>
> Le Wednesday 28 November 2007 09:56:17 Torgny Tholerus, vous avez écrit :
>  
>>

>> You only need models of cellular automata.  If you have a model and
>> rules for that model, then one event will follow after another event,
>> according to the rules.  And after that event will follow another more
>> event, and so on unlimited.  The events will follow after eachother even
>> if you will not have any implementation of this model.  Any physics is
>> not needed.  You don't need any geometric properties.
>>
>>    

> Sure, but you can't be ultrafinitist and saying things like "And after that
> event will follow another more event, and so on unlimited".
>  

There is a difference between "unlimited" and "infinite".  "Unlimited"
just says that it has no limit, but everything is still finite.  If you
add something to a finite set, then the new set will always be finite.  
It is not possible to create an infinite set.

So it is OK to use the word "unlimited".  But it is not OK to use the
word "infinite".  Is this clear?

Another important word is the word "all".  You can talk about "all
events".  But in that case the number of events will be finite, and you
can then talk about "the last event".  But you can't deduce any
contradiction from that, because that is forbidden by the type theory.  
And there will be more events after "the last event", because the number
of events is "unlimited".  As soon as you use the word "all", you will
introduce a limit - all up to this limit.  And you must then think of
only doing conclusions that are legal according to type theory.

So the best thing is to avoid the word "all" (and all synonyms of that
word).

--
Torgny

Le Thursday 29 November 2007 17:22:59 Torgny Tholerus, vous avez écrit :
> Quentin Anciaux skrev:
> > Hi,
> >
> > Le Wednesday 28 November 2007 09:56:17 Torgny Tholerus, vous avez écrit :
> >> You only need models of cellular automata.  If you have a model and
> >> rules for that model, then one event will follow after another event,
> >> according to the rules.  And after that event will follow another more
> >> event, and so on unlimited.  The events will follow after eachother even
> >> if you will not have any implementation of this model.  Any physics is
> >> not needed.  You don't need any geometric properties.
> >
> > Sure, but you can't be ultrafinitist and saying things like "And after
> > that event will follow another more event, and so on unlimited".
>
> There is a difference between "unlimited" and "infinite".  "Unlimited"
> just says that it has no limit, but everything is still finite.  If you
> add something to a finite set, then the new set will always be finite.
> It is not possible to create an infinite set.

I'm sorry I don't get it... The set N as an infinite numbers of elements still
every element in the set is finite. Maybe it is an english subtility that I'm
not aware of... but in french I don't see a clear difference between "infini"
and "illimité".

> So it is OK to use the word "unlimited".  But it is not OK to use the
> word "infinite".  Is this clear?

No, I don't see how a set which have not limit get a finite number of
elements.

> Another important word is the word "all".  You can talk about "all
> events".  But in that case the number of events will be finite, and you
> can then talk about "the last event".  But you can't deduce any
> contradiction from that, because that is forbidden by the type theory.
> And there will be more events after "the last event", because the number
> of events is "unlimited".  

If there are events after the last one, how can the last one be the last ?

> As soon as you use the word "all", you will
> introduce a limit - all up to this limit.  And you must then think of
> only doing conclusions that are legal according to type theory.

o_O... could you explain what is type theory ?

> So the best thing is to avoid the word "all" (and all synonyms of that
> word).

like everything ?

Regards,
Quentin Anciaux

--
All those moments will be lost in time, like tears in the rain.

> Le Thursday 29 November 2007 17:22:59 Torgny Tholerus, vous avez écrit :
>  
>>

>> There is a difference between "unlimited" and "infinite".  "Unlimited"
>> just says that it has no limit, but everything is still finite.  If you
>> add something to a finite set, then the new set will always be finite.
>> It is not possible to create an infinite set.
>>    
>
> I'm sorry I don't get it... The set N as an infinite numbers of elements still
> every element in the set is finite. Maybe it is an english subtility that I'm
> not aware of... but in french I don't see a clear difference between "infini"
> and "illimité".
>  

As soon as you talk about "the set N", then you are making a "closure"
and making that set finite.  The only possible way to talk about
something without limit, such as natural numbers, is to give a
"production rule", so that you can produce as many of that type of
objects as you want.  If you have a natural number n, then you can
"produce" a new number n+1, that is the successor of n.

>
>  
>> So it is OK to use the word "unlimited".  But it is not OK to use the
>> word "infinite".  Is this clear?
>>    
>
> No, I don't see how a set which have not limit get a finite number of
> elements.
>  

It is not possible for "a set" to have no limit.  As soon as you
construct "a set", then that set will always have a limit.  Either you
have to accept that the set N is finite, or you must stop talking about
"the set N".  It is enough to have a production rule for natural numbers.

>  
>> Another important word is the word "all".  You can talk about "all
>> events".  But in that case the number of events will be finite, and you
>> can then talk about "the last event".  But you can't deduce any
>> contradiction from that, because that is forbidden by the type theory.
>> And there will be more events after "the last event", because the number
>> of events is "unlimited".  
>>    
>
> If there are events after the last one, how can the last one be the last ?
>  

The last event is the last event in the set of "all" events.  But
because you have a production rule for the events, it is always possible
to produce new events after the last event.  But these events do not
belong to the set of "all" events.

>  
>> As soon as you use the word "all", you will
>> introduce a limit - all up to this limit.  And you must then think of
>> only doing conclusions that are legal according to type theory.
>>    
>
> o_O... could you explain what is type theory ?
>  

Type theory is one of the solutions of Russel's paradox.  You have a
hierarchy of "types".  Type theory says that the "all quantifiers" only
can span objects of the same "type" (or lower types).  When you create
new objects, such that "the set of all sets that do not belong to
themselves", then you will get an object of a higher "type", so that you
can not say anything about if this set belongs to itself or not.  The
same thing with "the set of all sets".  You can not say anything about
if it belongs to itself.

>  
>> So the best thing is to avoid the word "all" (and all synonyms of that
>> word).
>>    
>
> like everything ?
>  

--
Torgny

Le Thursday 29 November 2007 18:25:54 Torgny Tholerus, vous avez écrit :
> Quentin Anciaux skrev:
> > Le Thursday 29 November 2007 17:22:59 Torgny Tholerus, vous avez écrit :
> >> There is a difference between "unlimited" and "infinite".  "Unlimited"
> >> just says that it has no limit, but everything is still finite.  If you
> >> add something to a finite set, then the new set will always be finite.
> >> It is not possible to create an infinite set.
> >
> > I'm sorry I don't get it... The set N as an infinite numbers of elements
> > still every element in the set is finite. Maybe it is an english
> > subtility that I'm not aware of... but in french I don't see a clear
> > difference between "infini" and "illimité".
>
> As soon as you talk about "the set N", then you are making a "closure"
> and making that set finite.  

Ok then the set R is also finite ?

> The only possible way to talk about
> something without limit, such as natural numbers, is to give a
> "production rule", so that you can produce as many of that type of
> objects as you want.  If you have a natural number n, then you can
> "produce" a new number n+1, that is the successor of n.

What is the production rules of the "no"set R ?

> >> So it is OK to use the word "unlimited".  But it is not OK to use the
> >> word "infinite".  Is this clear?
> >
> > No, I don't see how a set which have not limit get a finite number of
> > elements.
>
> It is not possible for "a set" to have no limit.  As soon as you
> construct "a set", then that set will always have a limit.  

I don't get it.

> Either you
> have to accept that the set N is finite, or you must stop talking about
> "the set N".  It is enough to have a production rule for natural numbers.

I don't accept and/or don't understand.

> >> Another important word is the word "all".  You can talk about "all
> >> events".  But in that case the number of events will be finite, and you
> >> can then talk about "the last event".  But you can't deduce any
> >> contradiction from that, because that is forbidden by the type theory.
> >> And there will be more events after "the last event", because the number
> >> of events is "unlimited".
> >
> > If there are events after the last one, how can the last one be the last
> > ?
>
> The last event is the last event in the set of "all" events.  But
> because you have a production rule for the events, it is always possible
> to produce new events after the last event.  But these events do not
> belong to the set of "all" events.

There exists no last element in the set N.

> >> As soon as you use the word "all", you will
> >> introduce a limit - all up to this limit.  And you must then think of
> >> only doing conclusions that are legal according to type theory.
> >
> > o_O... could you explain what is type theory ?
>
> Type theory is one of the solutions of Russel's paradox.  You have a
> hierarchy of "types".  Type theory says that the "all quantifiers" only
> can span objects of the same "type" (or lower types).  When you create
> new objects, such that "the set of all sets that do not belong to
> themselves", then you will get an object of a higher "type", so that you
> can not say anything about if this set belongs to itself or not.  The
> same thing with "the set of all sets".  You can not say anything about
> if it belongs to itself.
>
> >> So the best thing is to avoid the word "all" (and all synonyms of that
> >> word).
> >
> > like everything ?
>
> Yes...   :-)

What you are saying seems like to me "So the best thing is to avoid words at
all (and any languages)"...

Regards,
Quentin Anciaux

--
All those moments will be lost in time, like tears in the rain.

Quentin Anciaux skrev:
> Le Thursday 29 November 2007 18:25:54 Torgny Tholerus, vous avez écrit :
>  
>>

>> As soon as you talk about "the set N", then you are making a "closure"
>> and making that set finite.  
>>    
>
> Ok then the set R is also finite ?
>  

Yes.

>  
>> The only possible way to talk about
>> something without limit, such as natural numbers, is to give a
>> "production rule", so that you can produce as many of that type of
>> objects as you want.  If you have a natural number n, then you can
>> "produce" a new number n+1, that is the successor of n.
>>    
>
> What is the production rules of the "no"set R ?
>  

How do you define "the set R"?

--
Torgny

Le Thursday 29 November 2007 18:52:36 Torgny Tholerus, vous avez écrit :
> Quentin Anciaux skrev:
> > Le Thursday 29 November 2007 18:25:54 Torgny Tholerus, vous avez écrit :
> >> As soon as you talk about "the set N", then you are making a "closure"
> >> and making that set finite.
> >
> > Ok then the set R is also finite ?
>
> Yes.

o_O

> >> The only possible way to talk about
> >> something without limit, such as natural numbers, is to give a
> >> "production rule", so that you can produce as many of that type of
> >> objects as you want.  If you have a natural number n, then you can
> >> "produce" a new number n+1, that is the successor of n.
> >
> > What is the production rules of the "no"set R ?
>
> How do you define "the set R"?

http://en.wikipedia.org/wiki/Construction_of_real_numbers

Choose your method...

Regards,
Quentin Anciaux
--
All those moments will be lost in time, like tears in the rain.

Quentin Anciaux skrev:
> Le Thursday 29 November 2007 18:52:36 Torgny Tholerus, vous avez écrit :
>  
>> Quentin Anciaux skrev:
>>    
>>

>>> What is the production rules of the "no"set R ?
>>>      
>> How do you define "the set R"?
>>    
>
> http://en.wikipedia.org/wiki/Construction_of_real_numbers
>
> Choose your method...
>  

The most important part of that definition is:

4. The order ? is /complete/ in the following sense: every non-empty
subset of *R* bounded above <http://en.wikipedia.org/wiki/Upper_bound>
has a least upper bound <http://en.wikipedia.org/wiki/Least_upper_bound>.

This definition can be translated to:

"If you have a production rule that produces rational numbers that are
bounded above, then this production rule is producing a real number."

This is the production rule for real numbers.

--
Torgny

>>
>>    
>> As soon as you talk about "the set N", then you are making a "closure"
>> and making that set finite.
>>    
>
>
> Why is that? How do you define the word "set"?
>
>
>   The only possible way to talk about
>  
>> something without limit, such as natural numbers, is to give a
>> "production rule", so that you can produce as many of that type of
>> objects as you want.  If you have a natural number n, then you can
>> "produce" a new number n+1, that is the successor of n.
>>    
>
>
> Why can't I say "the set of all numbers which can be generated by that production ruler"?

As soon as you say "the set of ALL numbers", then you are forced to
define the word ALL here.  And for every definition, you are forced to
introduce a "limit".  It is not possible to define the word ALL without
introducing a limit.  (Or making an illegal circular definition...)

>  It almost makes sense to say a set is *nothing more* than a criterion for deciding whether something is a member of not, although you would need to refine this definition to deal with problems like Russell's "set of all sets that are not members of themselves" (which could be translated as the criterion, 'any criterion which does not match its own criterion'--I suppose the problem is that this criterion is not sufficiently well-defined to decide whether it matches its own criterion or not).
>  

A "well-defined criterion" is the same as what I call a "production
rule".  So you can use that, as long as the criterion is well-defined.

(What does the criterion, that decides if an object n is a natural
number, look like?)

>  
>>
>> It is not possible for "a set" to have no limit.  As soon as you
>> construct "a set", then that set will always have a limit.
>>    
>
>
> Is there something intrinsic to your concept of the word "set" that makes this true? Is your concept of a set fundamentally different than my concept of well-defined criteria for deciding if any given object is a member or not?
>  

Yes, the definition of the word "all" is intrinsic in the concept of the
word "set".

--
Torgny

Geometry seems to be in between(????) and symmetry can be both, I think.

I am no physicist AND no mathematician, (not even a logician), so I
pretend to keep an objective eye on things in which I am not
prejudiced by knowledge. (<G>).

John M

>
>
>  
>> Date: Thu, 29 Nov 2007 19:55:20 +0100
>> From: tor...@dsv.su.se
>>
>>    

>> As soon as you say "the set of ALL numbers", then you are forced to
>> define the word ALL here.  And for every definition, you are forced to
>> introduce a "limit".  It is not possible to define the word ALL without
>> introducing a limit.  (Or making an illegal circular definition...)
>>    
>
> Why can't you say "If it can be generated by the production rule/fits the criterion, then it's a member of the set"? I haven't used the word "all" there, and I don't see any circularity either.

What do you mean by a "well-defined criterion"?  Is this a well-defined
criterion? :

The set R is defined by:

(x belongs to R) if and only if (x does not belong to x).

If it fits the criterion (x does not belong to x), then it's a member of
the set R.

Then we ask the question: "Is R a member of the set R?".  How shall we
use the criterion to answer that question?

If we substitute R for x in the criterion, we will get:

(R belongs to R) if and only if (R does not belong to R)...

What is wrong with this?

--
Torgny

>
> Quentin Anciaux skrev:
>> Hi,
>>
>> Le Wednesday 28 November 2007 09:56:17 Torgny Tholerus, vous avez  
>> écrit :
>>
>>>
>>> You only need models of cellular automata.  If you have a model and
>>> rules for that model, then one event will follow after another event,
>>> according to the rules.  And after that event will follow another  
>>> more
>>> event, and so on unlimited.  The events will follow after eachother  
>>> even
>>> if you will not have any implementation of this model.  Any physics  
>>> is
>>> not needed.  You don't need any geometric properties.
>>>
>>>
>> Sure, but you can't be ultrafinitist and saying things like "And  
>> after that
>> event will follow another more event, and so on unlimited".
>>
>
>
> There is a difference between "unlimited" and "infinite".  "Unlimited"
> just says that it has no limit, but everything is still finite.  If you
> add something to a finite set, then the new set will always be finite.
> It is not possible to create an infinite set.

Come on! Now you talk like a finitist, who accepts the idea of  
"potential infinity" (like Kronecker, Brouwer and the intuitionnist)  
and who rejects only the so called actual infinities, like ordinal and  
cardinal "numbers" (or sets).

At the ontic level, (or ontological, I mean the minimum we have to bet  
on at the third person pov), comp is mainly finitist. Judson Webb put  
comp (he calls it mechanism) in Finitism. But that is no more  
ultrafinitism. With finitism: every object of the "universe" is finite,  
but the universe itself is infinite (potentially or actually). With  
ultrafinitism, every object is finite AND the universe itself is finite  
too.

Jesse wrote:

How would the set "omega-1" be defined? It doesn't make sense unless  
you believe in a "last finite ordinal", which of course a  
non-ultrafinitist will not believe in.

Actually this makes sense in what is called non standard model of  
arithmetic. In Peano Arithmetic you cannot define what is a finite  
number (the notion of finiteness is typically a second order notion).  
So it is consistent to add some "infinite numbers" in the model of PA.  
But you can prove in PA that any number, except zero, has a  
predecessor, so a non standard model of arithmetic can have infinite  
objects, but then also its predecessor, and all their successive  
predecessors. A non standard model will have the following order on it:

0 1 2 ...     ... infinity-1  infinity  infinity+1 ....   (and possibly  
other so called Z-chain).  Such order are NOT ordinals, note.

All this is not important now, but I say this in passing.

> My instinct would be to say that a "well-defined" criterion is one  
> that, given any mathematical object, will give you a clear answer as  
> to whether the object fits the criterion or not. And obviously this  
> one doesn't, because it's impossible to decide where R fits it or not!  
> But I'm not sure if this is the right answer, since my notion of  
> "well-defined criteria" is just supposed to be an alternate way of  
> conceptualizing the notion of a set, and I don't actually know why  
> "the set of all sets that are not members of themselves" is not  
> considered to be a valid set in ZFC set theory.

Frege and Cantor did indeed define or identify sets with their defining  
properties. This leads to the Russell's contradiction. (I think Frege  
has abandoned his work in despair after that).
One solution (among many other one) to save Cantor's work from that  
paradox consists in formalizing set theory, which means using  
"belongness" as an undefined symbol obeying some axioms. Just two  
examples of an axiom of ZF (or its brother ZFC = ZF + axiom of choice):  
is the extensionality axiom:
AxAyAz ((x b z <-> y b z)  -> x = y)   "b" is for "belongs". It says  
that two sets are equal if they have the same elements.
AxEy(z included-in x -> z b y) with "z included-in x" is a macro for  
Ar(r b z -> r b x). This is the power set axiom, saying that the set of  
all subsets of some set is also a set).

Paradoxes a-la Russell are evacuated by restricting Jesse's  
"well-defined criteria" by
1) first order formula (in the set language, that is with "b" as unique  
relational symbols (+ equality) ... like the axioms just above.
2) but such first order formula have to be applied only to an already  
defined set.
For example, you can defined the set of x such that x is in y and has  
such property P(x). With P defined by a set formula, and y an already  
defined set.

Also, ZFC has the foundation axiom which forbids a set to belong to  
itself. In particular the informal collection of all sets which does  
not belongs to themselves is the universe itself, which cannot be a set  
(its power set would be bigger than the universe!).
But there are version of ZF without foundation, or even with diverse  
versions of the negation of the foundation axiom, like Stephen Paul  
King appreciates so much.

Actually, I will not use set theory at all, but I will mention often ZF  
and its many brothers (like ZFC, ZF+<some big cardinal>, ...) as  
example of very rich lobian machine. ZF can prove the complete  
(propositional) theology of a lesser rich (in provability power)  
machine like PA.

Bruno

PS BTW, on the FOR list Charles gives this interesting reference on  
Everett. It looks his son has made a movie on his father:
http://www.newscientist.com/channel/opinion/mg19626311.800-interview-
parallel-lives-can-never-touch.html

http://iridia.ulb.ac.be/~marchal/

I recall the proof that N^N is not enumerable.

I recall that N^N is the set of functions from N to N. Such functions
associate a natural number to each natural number. Example:

factorial = {(0, 1) (1, 1) (2, 2) (3, 6) (4, 24) (5 120) ...}

of course the same information is provided by the sequence:

1, 1, 2, 6, 24, 120, ....      which is an element of the infinite
cartesian product NXNXNXNXNX ....

So N^N is in bijection with NXNXNXNXNX ...., and giving that we are
interested in cardinality, for all practical purpose we can identify
both sets.

Theorem; N^N is not enumerable

Proof 1 (by absurdo):

If a bijection exists between N and N^N, then it will look like (cf the
identification above):

0   ----------    4  1  2  6  24  57  ...
1   ----------    0  0  5  0  45    7  ...
2   ----------    0  9  7  0    1    0  ...
...

Well, at least in the mind of a God capable of seeing the whole
infinite table.
Again, for such a God, the diagonal is entirely well defined:

4 1 8 ....

So we can  consider the sequence of the diagonal elements, each added
to one:

4+1  1+1 8+1 ..., that is

5 2 9 ...

By construction this sequence is not in the list above, because it
differs:

from the 0th sequence, at the 0th "decimal" let us say,
from the1st sequence, at the 1st "decimal",
from the 2nd sequence, at the 2nd "decimal",
from the 3rd sequence, at the 3nd "decimal"
from the 4th sequence, at the 4th "decimal"
from the 5th sequence, at the 5th "decimal"
from the 6th sequence, at the 6th "decimal"
from the 7th sequence, at the 7th "decimal"
from the 8th sequence, at the 8th "decimal"
...
from the n-th sequence, at the n-th "decimal"
...

All right? This works for any tentative bijection proposed by any Gods.

Now I give you the same proof, but with the traditional functional
notation. This is for helping those who could have some notation
problems. Please make you sure that you see I am giving the same proof,
but with better notations:

proof 2 (by absurdo)

If a bijection exists between N and N^N, then it means there is an
enumeration of all functions from N to N, it looks like:

f_0  f_1  f_2  f_3  f_4  f_5  f_6 ...

All those f_i are well-defined (in Platonia) functions from N to N. So,
the following function g is also well defined. By definition:

g(n) = f_n(n) + 1   (this is the diagonal "+1" described above).

Now g cannot be in the list f_0  f_1  f_2  ...
Why?
Because if g is in the list, it means there is a number k such that g =
f_k  (and thus for all n, g(n) = f_k(n)).

But g(n) = f_k(n) + 1 by definition of g. Now we have, by applying g on
its code k (cf g = f_k):

g(k) = f_k(k) (by the assumption that g is in the list), and
g(k) = f_k(k) + 1  (by definition of g)

Thus (by Leibniz rule)

  f_k(k) = f_k(k)+1.

But those are well defined numbers   (cf: the f_k are functions from N
to N), thus we can subtract f_k(k) on both sides, and this gives

0 = 1

Contradiction. Thus g cannot be in the list, and appears as a sheep
without a rope. N^N has "more element than N", and is thus non
enumerable. QED (OK?).

NEXT: the key post. It should be even more simple, because, although we
will be obliged to stay in Platonia, we will not invoke any God
anymore. Instead we will invoke its quasi antipode, not the devil (!),
but the humble finite earthly creature. The idea is to concentrate
ourself on computable functions from N to N, instead of *all* functions
from N to N.
Computable?
By who? Computability is an epistemic notion, it seems to involve a
subject.
Well, as you can guess, computable will mean "computable by that humble
finite earthly creature" ... Now, what does that mean ...

Soon on a screen near you ;) ..., asap ...

Good week-end,

Bruno

http://iridia.ulb.ac.be/~marchal/

>
>
> Le 29-nov.-07, à 17:22, Torgny Tholerus a écrit :
>

>     There is a difference between "unlimited" and "infinite". "Unlimited"
>     just says that it has no limit, but everything is still finite. If
>     you
>     add something to a finite set, then the new set will always be
>     finite.
>     It is not possible to create an infinite set.
>
> Come on! Now you talk like a finitist, who accepts the idea of
> "potential infinity" (like Kronecker, Brouwer and the intuitionnist)
> and who rejects only the so called actual infinities, like ordinal and
> cardinal "numbers" (or sets).

Yes, I am more like a finitist than an ultrafinitist in this respect.  I
accept that something can be without limit.  But I don't want to use the
word "potential infinity", because "infinity" is a meaningless word for me.

>
> At the ontic level, (or ontological, I mean the minimum we have to bet
> on at the third person pov), comp is mainly finitist. Judson Webb put
> comp (he calls it mechanism) in Finitism. But that is no more
> ultrafinitism. With finitism: every object of the "universe" is
> finite, but the universe itself is infinite (potentially or actually).
> With ultrafinitism, every object is finite AND the universe itself is
> finite too.

Here I am an ultrafinitist.  I believe that the universe is strictly
finite.  The space and time are discrete.  And the space today have a
limit.  But the time might be without limit, that I don't know.

>
> Jesse wrote:
>
>     My instinct would be to say that a "well-defined" criterion is one
>     that, given any mathematical object, will give you a clear answer
>     as to whether the object fits the criterion or not. And obviously
>     this one doesn't, because it's impossible to decide where R fits
>     it or not! But I'm not sure if this is the right answer, since my
>     notion of "well-defined criteria" is just supposed to be an
>     alternate way of conceptualizing the notion of a set, and I don't
>     actually know why "the set of all sets that are not members of
>     themselves" is not considered to be a valid set in ZFC set theory.
>
> Frege and Cantor did indeed define or identify sets with their
> defining properties. This leads to the Russell's contradiction. (I
> think Frege has abandoned his work in despair after that).
> One solution (among many other one) to save Cantor's work from that
> paradox consists in formalizing set theory, which means using
> "belongness" as an undefined symbol obeying some axioms. Just two
> examples of an axiom of ZF (or its brother ZFC = ZF + axiom of
> choice): is the extensionality axiom:
> AxAyAz ((x b z <-> y b z) -> x = y) "b" is for "belongs". It says that
> two sets are equal if they have the same elements.
> AxEy(z included-in x -> z b y) with "z included-in x" is a macro for
> Ar(r b z -> r b x). This is the power set axiom, saying that the set
> of all subsets of some set is also a set).

For me "belongness" is not a problem, because everything is finite.  For
me the axiom of choice always is true, because you can always do a
chioce in a finite world.

>
> Paradoxes a-la Russell are evacuated by restricting Jesse's
> "well-defined criteria" by
> 1) first order formula (in the set language, that is with "b" as
> unique relational symbols (+ equality) ... like the axioms just above.
> 2) but such first order formula have to be applied only to an already
> defined set.

This 2) rule is a very important restriction, and it is just this that
my "type theory" is about.  When you construct new things, those things
can only be constructed from things that are already defined.  So when
you construct the set of all sets, then that new set will not be
included in the new set.

> For example, you can defined the set of x such that x is in y and has
> such property P(x). With P defined by a set formula, and y an already
> defined set.
>
> Also, ZFC has the foundation axiom which forbids a set to belong to
> itself.

This is a natural consequence of my type theory.  When you construct a
set, that set can never belong to itself, because that set is not
defined before it is constructed.

> In particular the informal collection of all sets which does not
> belongs to themselves is the universe itself, which cannot be a set
> (its power set would be bigger than the universe!).

Yes, the set of all sets which does not belongs to themselves is the
universe itself.  But this is not a problem for me, because you can
always extend the universe by creating new objects.  So you can create
the power set, and the power set will then be bigger than the universe.  
But this power set will not be part of the universe.

--
Torgny

> On Nov 28, 9:56 pm, Torgny Tholerus <tor...@dsv.su.se> wrote:
>
>  
>> You only need models of cellular automata.  If you have a model and
>> rules for that model, then one event will follow after another event,
>> according to the rules.  And after that event will follow another more
>> event, and so on unlimited.  The events will follow after eachother even
>> if you will not have any implementation of this model.  Any physics is
>> not needed.  You don't need any geometric properties.
>>
>> In this model you may have a person called Torgny writing a message on a
>> google group, and that event may be followed by a person called Marc
>> writing a reply to this message.  And you don't need any implementation
>> of that model.
>>
>>    

> A whole lot of unproven assumptions in there.   For starters, we don't
> even know that the physical world can be modelled solely in terms of
> cellular automata at all.

Why can't our universe be modelled by a cellular automata?  Our universe
is very complicated, but why can't it be modelled by a very complicated
automata?  An automata where you have models for protons and electrons
and photons and all other elementary particles, that obey the same laws
as the particles in our universe?

>   Digital physics just seems to be the latest
> 'trendy' thing, but actual evidence is thin on the ground.
> Mathematics is much richer than just discrete math.  Discrete math
> deals only with finite collections, and as such is just a special case
> of algebra.

Isn't it enough with this special case?  You can do a lot with finite
collections.  There is not any need for anything more.

>   Algebraic relations extend beyond computational models.
> Finally, the introduction of complex analysis, infinite sets and
> category theory extends mathematics even further, beyond even
> algebraic relations.  So you see that cellular automata are only a
> small part of mathematics as a whole.  There is no reason for thinking
> for that space is discrete and in fact physics as it stands deals in
> continuous differential equations, not cellular automata.
>  

The reason why physics deals in continuous differential equations is
that they are a very good approximation to a world where the distance
between the space points and the time points are very, very small.  And
if you read a book in Quantum Field Theory, they often start from a
discrete model, and then take the limit when the distances go to zero.

> Further, the essential point I was making is that an informational
> model of something is not neccesserily the same as the thing itself.
> An informational model of a person called Marc would capture only my
> mind, not my body.  The information has to be super-imposed upon the
> physical, or embodied in the physical world.
>  

--
Torgny

And how this render the *set R* ]-infinity,infinity[ finite/limited or even
the set N [0,infinity[ ?

If as you say you have elements/events/... after the last element/event/... it
is totally contradictory and meaning less to call it last... If I take it as
a demonstration by absurd, then you've just demonstrated that there exists no
last element/event/... How can you avoid this contradiction ?

Regards,
Quentin Anciaux

--
All those moments will be lost in time, like tears in the rain.

> Here I am an ultrafinitist.  I believe that the universe is strictly
> finite.  The space and time are discrete.  And the space today have a
> limit.  But the time might be without limit, that I don't know.

Then you are physicalist before being ultrafinitist.

Now ultrafinitism implies comp (OK?, 'course comp does not imply
ultrafinitism!)

But I have already argued that comp implies the falsity of physicalism
(UDA), so?

BTW, you often quote wiki or other standard definition of math concept.
But few are justifiable in the ultrafinitist realm, so many of your
statements seems contradictory to me.

Bruno

http://iridia.ulb.ac.be/~marchal/

> Why can't our universe be modelled by a cellular automata?

By UDA, this is just  a priori impossible.

What *is* still possible, is that you can "modelize" the emergence of
the appearance of a universe by modelling, with a cellular automata, a
couple "observer + a quantum cellular automata", or by modelling all
possible observers through universal dovetaling. Normally the
appearance of the quantum will be generated as well.

If you are a machine, the physical universe (the sharable third person
pov) is not describable in term of working machine. Unless you are the
whole universe yourself, which I doubt.
If, you are the whole universe, and if you (the universe) exist, and if
comp is false and ultrafinitism true, then you are right. But then,
about the mind body problem, you are reintroducing the material bullet
making even impossible to really addressed the question. Imo: it would
be a regression.

This comment assumes a good understanding of the seven first steps of
the UDA.

> Our universe
> is very complicated, but why can't it be modelled by a very complicated
> automata?

Because, by assuming comp, the (physical) universe has to emerge non
locally from an infinity of infinite computations.

> An automata where you have models for protons and electrons
> and photons and all other elementary particles, that obey the same laws
> as the particles in our universe?

Of course I talk here on exact emulation. FAPP, you can simulate
electron and photon. About  "reality", I am not even sure there are
photons and electrons, we have non local (in our local
histories/branches) wavy interacting fields.
Note that Newton's law, taken seriously enough, are also not turing
emulable, like almost everything in naïve math.

Bruno

http://iridia.ulb.ac.be/~marchal/

>
> On Nov 20, 4:40 pm, Bruno Marchal <marc...@ulb.ac.be> wrote:
>
>> Conclusion: 2^N, the set of infinite binary sequences, is not
>> enumerable.
>>
>> All right?
>
> OK.  I have to try to catch up now, because I've had to be away longer
> than I expected, but I'm clear on this diagonal argument.

OK. I hope you have done the exercise  below, which consists to show
that N^N is also not enumerable. It is the same reasoning, of course.
(Of course it is also a consequence of the non enumerability of 2^N,
because 2^N is included in N^N, but in the exercise I was asking for a
direct diagonal argument).
You can look at the solution:
http://www.mail-archive.com/everything-list@eskimo.com/msg14063.html

I will send the "key post" asap. It is written, but I am currently
hesitating to add more explanations, but sometimes when I do that, I
introduce just more confusion. I guess I will send some part so that
you have something to think about (of 'course I don't doubt you have
many things to think about ...).

Bruno

===================================================================

http://iridia.ulb.ac.be/~marchal/

In the preceding post, I gave you an informal proof in naïve set theory
that the set of functions from N to N was not enumerable.

Note: the preceding post =
http://www.mail-archive.com/everything-list@eskimo.com/msg14063.html

It is not in my intention at all to convince you that Cantor's result
is true. A problem which occurs is the many invocation of Gods. Cantor
himself will hide paradoxes and also will discuss with theologians on
those problems.

Today we know Cantor's theorem is provable in reasonably sound accounts
of sets, like Zermelo Fraenkel Set Theory, ZF.

But it is not my purpose to dwelve into set theory. My purpose is
computability theory.

What happens if we try to restrict ourselves to *computable* functions

from N to N, instead of *all* functions from N to N.

In this case we would not be obliged to refer to Gods, those who were
able to "see" an arbitrary and infinite long sequence of numbers.

But we get somehow the anti-problem. How to define what is a computable
function?

We can hardly be satisfied by an anti-solution like:

Anti-definition: A function from N to N is computable if it can be
computed without any invocation to any Gods.

So we have to find a more positive definition, and invoke *finite and
humble* creature instead. Humble, because we have to be sure not
attributing to them any magical and hard to define qualities like
cleverness, intelligence, intuition or any god-like predicate.

So here is an informal "definition" of what is an (intuitively)
computable function from N to N.

"Definition": a function f is computable if there is a finite set of
instructions such that a complete asshole can, on each n compute in a
finite time the result f(n).

OK. "complete asshole" is probably a bit popular, and I will use the
adverb "unambiguously" instead.

Also, what are the instructions? Whatever they are, they have to be
described in some language, which has to be unambiguous (understandable
by that humble finite creature).

So here is a better "definition" of what is a computable function from
N to N.

A function f from N to N is said (intuitively) computable if there is a
language L in which it is possible to describe unambiguously through a
finite expression in L how, for any n to compute f(n) in a finite time.

The finite expression are intended to express the instructions. A
language is the given of a finite alphabet A, and a subset L of
unambiguous expressions. If A is a finite or enumerable alphabet, then
I will denote by A°, the set of finite expressions written with the
alphabet A. I recall that If A is finite or enumerable, then A° is
enumerable too. Indeed, you can put an alphabetical order on all
sequences of length 1, and then of length 2, etc.
Exemple: A = {S, K, (, ) }
Ordering the finite expressions, using the order "K < S <  ( < )" on
the alphabet:

finite expressions=
K, S, (, ),     [length one]
KK, KS, K(, K), SK, SS, S(, S), (K, (S, ((, (), )K, )S, )(, )),    
[length two]
KKK , ...  [length 3]
KKKK, ... [length 4]

Note that ")))KK))S())" is a finite expression on the alphabet. It is
does not refer to a combinator, which are associated only to
well-formed expressions, like, if you remember,  (K(SK)), or
((S(KS))K), making a subset of the set of all (finite) expressions.

Now, two fundamental definitions:

Universal Language:  A language L is universal if all computable
functions (from N to N) can be described in L.

Universal Machine: A machine M is universal if M understands L, and so
M can actually compute the value f(n) of any computable function from
its description in the universal language L and the input n.
(Note that  such a universal *machine*, should be describable itself by
an expression in the universal language. We will come back on this
later).

Now the question is: Is there an universal language?  Is there a
universal machine?