**Hitoshi Kitada** (*hitoshi@kitada.com*)

*Tue, 20 Apr 1999 23:40:44 +0900*

**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]**Next message:**Peter Wegner: "[time 252] Re: [time 251] Peter Wegner's paper"**Previous message:**Stephen P. King: "[time 250] Frieden info"**Next in thread:**Peter Wegner: "[time 252] Re: [time 251] Peter Wegner's paper"

Dear Stephen, Peter and Friends,

*> [SPK]
*

*> > > I am trying to think of this in terms of Peter's
*

*> > > Interactive Machine paradigm. If we could show that a LS is equivalent
*

*> > > to a finite IM, we could easily bring in the power of Peter's analysis
*

*> > > in to play. :) http://www.cs.brown.edu/~pw/papers/bcj1.pdf
*

*> [HK]
*

*> > I downloaded the paper, but I could not find time to see it.
*

*>
*

*> I will try hard to be patient. :)
*

I have read Peter's paper bcj1.pdf. :)

It is an impressive paper in the point that it seems to describe one turning

point of science.

I regard the paper as pointing out the most characteristic feature of modern

science that has been called "reductionism." I.e. I read Peter's "inductive

formalism" as the same as the so-called "reductionism." Reductionism reduces

everything to some elementary things. Induction is just a reverse process of

the reduction. Science has not obtained the substitute for its reductive

methodology, in spite of scientists' unanimous critiques about the

reductionism: Their only available method is just the reverse of reduction,

induction. Peter's alternative for this is "coinduction":

from 4.2 of his paper:

*> Coinduction determines a deconstruction paradigm
*

*> that deconstructs composite structures into progressively
*

*> more primitive ones. It reverses the direction of mapping
*

*> (iteration) of inductive construction processes and replaces
*

*> initiality with finality. Non-well-founded sets introduce a larger
*

*> class of sets by eliminating finite termination, corresponding
*

*> to initiality of dual inductive processes.
*

On the concrete level, he proposes two examples. The first is SIMs (Sequential

Interaction Machines) which are equivalent with non-well-founded sets, and

according to his "Thesis for sequential interaction" they correspond to the

intuitive notion of effective computability for sequential (single-stream)

interaction. The MIMs (Multi-Stream Interaction Machines) is the second, which

are more expressive than SIMs.

whose set-theoretic model seems to require nonlinear set equations. On the

basis of the analysis of these machines and Godel's incompleteness theorem, he

proposes a thesis:

*> Coinductive Church-Turing thesis:
*

*> Coinductively specifiable behaviors expressible by axiomatic
*

*> set theory correspond to the intuitive notion of computations
*

*> expressible by finite computing agents.
*

Set-theoretic expression of the coinduction is, in the case of SIMs, in the

"Anti-Foundation Axiom" which implies the existence of an infinitely

descending sequence: ... \in a_{i+1} \in a_i \in a_{i-1} \in ..., whose

existence has been prohibited in the usual ZF set theory by the axiom of

regularity. This corresponds to the "eliminating finite termination" in the

above quotation.

K. Godel states about his Axiom D (which corresponds to the axiom of

regularity) in "The consistency of the continuum hypothesis," Annals of

Mathematics Studies, No. 3, Princeton University Press, 1940, p.6:

"The following axiom [proved consistent by v. Neumann, J, reine angew. Math.

160, p.227] is not indispensable, but it simplifies considerably the later

work."

This made me wonder if the axiom was necessary to avoid the Russell's paradox.

This question seems to be resolved now by Peter's explanation 30 years after

my reading of Godel's lecture note:

*> Finsler's prescient work on set theory in the 1920s [Fi] showed
*

*> the consistency of circular reasoning and anticipated Godel's
*

*> incompleteness result, but was largely ignored because it did
*

*> not conform to the mainstream paradigm of formalist mathematics.
*

This would suggest that Godel must have seen Finsler's paper(s), which might

explain the gap between Godel's writing "not indispensable" in 1940 and the

proof of consistency of Anti-Foundation Axiom by [BM] (J. Barwise and L. Moss,

"Vicious Circles,"... , 1996 [from Peter's references]). (I might be wrong as

I did not try to find the reason for Godel's writing. ;) )

I conclude this brief introduction to Peter's paper with quoting his

interesting observation: C means consistency and E existence hereafter. Then

Peter analyzes the standpoints of Hilbert, Godel, Cantor and Finsler, and

states his own position:

*> Hilbert: C -> E + inductive formalism; inconsistency with objective
*

*> mathematics was proved by Godel
*

*>
*

*> Godel: objective mathematics + inductive formalism; explains Godel's
*

*> rejection of C -> E
*

*>
*

*> Cantor, Finsler: C -> E + objective mathematics; implies rejection
*

*> of inductive formalism
*

*>
*

*> Hilbert's belief in C -> E and inductive formalism was shown by Godel
*

*> to be incompatible with objective mathematics, while Godel's belief
*

*> in objective mathematics and inductive formalism caused him to reject
*

*> C -> E. The realist, coinductive paradigm of mathematics corresponds
*

*> to Cantor and Finsler's belief in C -> E and objective mathematics,
*

*> which require rejection of inductive formalism.
*

I should be grateful for any comments and/or supplements. :)

Best wishes,

Hitoshi

**Next message:**Peter Wegner: "[time 252] Re: [time 251] Peter Wegner's paper"**Previous message:**Stephen P. King: "[time 250] Frieden info"**Next in thread:**Peter Wegner: "[time 252] Re: [time 251] Peter Wegner's paper"

*
This archive was generated by hypermail 2.0b3
on Sun Oct 17 1999 - 22:31:52 JST
*