Hitoshi Kitada (hitoshi@kitada.com)
Tue, 20 Apr 1999 23:40:44 +0900
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
This archive was generated by hypermail 2.0b3 on Sun Oct 17 1999 - 22:31:52 JST