Re: Question on Chaitin


"Timothy Murphy" <tim@xxxxxxxxxxxxxxxxxxxxxx> wrote in message
news:Pt0ie.53311$Z14.44333@xxxxxxxxxxxxxxxxx
> tchow@xxxxxxxxxxxxx wrote:
>
>> Whatever shortcomings Torkel Franzen may have, inability to understand
>> the consequences of Goedel's theorems is not one of them. Read his book
>> "Inexhaustibility" and then judge whether it is his mathematical ability
>> or yours that is greater.
>
> I haven't read this book - I didn't know it existed -
> but I would certainly not claim Franzen lacked mathematical ability.
>
> I thought some of his original criticisms of Chaitin's writings were
> cogent.
> But now he has got into a mode where his main concern seems to be
> to prove Chaitin wrong, rather than work out what he (Chaitin) means.
>
> This is a disease that can attack gifted mathematicians.
> I had a supervisor (L.J. Mordell) who took this attitude to Serge Lang,
> because the latter had criticised one of Mordell's heroes (Bachmann,
> IIRC).
> Mordell spent days poring over Lang's works,
> looking for what he took to be errors.
>
> When Chaitin speaks of the "informational content" of a theorem
> he is using the term in a very special sense,
> as is clear from his formal Theorems.
> One could argue that his use of the term is misleading,
> but not in my view that he has made a mistake.
>

After thinking about this I've come to the conclusion you
are poorly read. Panu Raatikainen has already made a similar
point to Torkel's and published a couple of papers on it. He
was not the first, van Lambalgen (1989) mentions it earlier.
Panu's biggest mistake is to use the weasely phrase
"seems to commit this confusion"

http://www.helsinki.fi/collegium/eng/Raatikainen/chaitinJPL.pdf

"I think there is a clear case of confusion here between use and
mention, a distinction whose inportance has been emphasized especially
by Quine (1940). He has nicely illustrated this distinction by the
example that Boston (word used) contains some 800,000 people, but
"Boston" (word mentioned) contains six letters. It was a related
confusion in statistical information theory that led Carnap and
Bar-Hillel to the fundamental distinction between semantic information
and syntactic information, i.e. between the information content of a
sentence and the probability of its syntactical presentation
(see Bar-Hillel (1964)).

In the present context, the relevance of this distinction is
exemplified by the fact that in a suitable language the sentence
expressing (used) that a particular object has a very large complexity,
e.g. "K (n) > m" (for a large m), may itself have a quite simple (when
mentioned) syntactical form.

Now Chaitin's metaphor that "if one has ten pounds of axioms and
a twenty-pound theorem, then that theorem cannot be derived from
those axioms", if referring to Chaitin's theorem, seems to commit
this confusion, i.e. it compares the complexity of axioms as mentioned
and the complexity asserted by a theorem when used. Now one may ask
what happens if axioms and theorems are compared in the same level.
But of course, one can derive from any axiom system, however simple
in its syntactic form, theorems having arbitrarily complex syntactical
form. Hence, if one compares the complexity of axioms (mentioned) and
theorems (mentioned), the claim is trivially false."

SH: This has also been discussed on the Foundations of Mathematics
(FOM) mailing list. Torkel is hardly standing on Chaitin's shoulders.

http://www.cs.nyu.edu/pipermail/fom/2001-March/004813.html

Stephen G. Simpson wrote:

Speaking of Chaitin's c, Raatikainen says:

> there are codings such that theories with highly different power
> (say, Q and ZFC) have the same finite limit. Also, the size and
> complexity of F are quite irrelevant.
...

> For every theory, there is indeed a finite limit, but that is all -
> the value of this finite limit does not reflect any natural or
> interesting property of F.

"Yes.

Now clearly there is a serious foundational/philosophical problem
here. A crude attempt at formulating the problem:

(*) For well known foundational theories F (e.g. F = PA, Z_2, ZFC,
ZFC + a large cardinal axiom, etc), find versions of the
incompleteness phenomenon, e.g., mathematically natural
statements independent of F, which are sensitive to F.

I invite other FOM participants to give a sharper formulation.

Obviously (*) is a key f.o.m. problem -- some would say THE key
f.o.m. problem. And this problem seems extremely difficult. G"odel's
independent statements, Con(F), do not have the required properties,
nor do Chaitin's statements K(n) > c. The Paris/Harrington theorem is
a well-known major contribution to (*).

Many people underestimate the difficulty of (*) and overestimate
Chaitin's contributions to it."

The correct word is contradiction,
Stephen


.

Relevant Pages

  • Re: Ada vs Ruby
    ... that for any mathematical system based upon a set of axioms there will ... This is why beyond a certain level of complexity it's helpful to use ... an interesting theoretical limitation of all software systems but it ...
    (comp.lang.ruby)
  • Re: Raatikainens Complexity Complex
    ... >>view that complexity of axiom systems (even looking ... Godel number N will either not halt, ... "to prove a twenty pound theorem, one needs twenty pounds ... I agree that twenty pounds of axioms will be enough, ...
    (comp.theory)
  • Re: Raatikainens Complexity Complex
    ... >>view that complexity of axiom systems (even looking ... Godel number N will either not halt, ... "to prove a twenty pound theorem, one needs twenty pounds ... I agree that twenty pounds of axioms will be enough, ...
    (sci.math)
  • Re: Analytic/Synthetic distinction in modern inference engines?
    ... You asked about the analytic/synthetic distinction, ... to ask about logics that treat the a/s distinction in some interesting ... All you have to do is pick appropriate axioms for whatever field ... preexisting axioms) can conflict with that; ...
    (sci.logic)
  • Re: Panu Raatikainens review of two of Chaitins books.
    ... Chaitin has also made various dubious ... > theorem cannot be derived from those axioms". ... Raatikainen's suggestion that the axiom complexity can differ vastly ... Eray Ozkural ...
    (sci.math)