FOM: Reply to Friedman on Arithmetic and Geometry

[Vladimir Sazonov]

Joe Shipman wrote (in reply to Harvey Friedman):
>
> I look forward to seeing more from you on the foundational relevance of
> a finite universe (either physical or set-theoretical).  There are nice
> axiomatizations of the hereditarily finite sets equivalent to PA, as you
> have pointed out.  If V_0={}, V_1={{}}, V_2={{},{{}}},
> V_3={{},{{}},{{{}}},{{},{{}}}}, then V_4 has 16 elements, V_5 has 65536
> elements, V_6 has 2^65536 elements, and V_7 has 2^2^65536 elements.  V_7
> is the first "Universe" in which the elements are of infeasible size.
> Someone who had an oracle for the first-order theory of the finite
> structure (V_7, /in) could rule the world.

Let us represent hereditarily-finite (HF) sets by vertices of 
finite acyclic graphs. (More generally, hereditarily-finite 
anti-founded sets are represented by vertices of arbitrary 
finite graphs.) Thus, the graph *<--*<--* represents three sets:  
the empty set 0, the singleton set {0) and jet another singleton 
set {{0)}. I hope the idea is clear. Then graphs of feasible 
size may represent sets of arbitrary feasible ranks, i.e. 
essentially > 7. I would consider this as more flexible approach 
to feasibly hereditarily-finite (FHF) sets. Cf. also my homepage 
for other issues and papers on so called Bounded Set Theory 
based on such kind of representations of sets by graphs. In 
particular, there is a pure set-theoretic (machine independent) 
description of polytime computability over HF (and over its 
anti-founded version HFA).


Vladimir Sazonov
-- 			   | Tel. +7-08535-98945 (Inst.),
Computer Logic Lab.,	   | Tel. +7-08535-98953 (Inst.),
Program Systems Institute, | Tel. +7-08535-98365 (home),
Russian Acad. of Sci.	   | Fax. +7-08535-20566
Pereslavl-Zalessky,	   | e-mail: sazonov at logic.botik.ru
152140, RUSSIA		   | http://www.botik.ru/~logic/SAZONOV/