FOM: Axioms of Infinity (& Help Request)

[Allen Hazen]

One COMMENT on Axioms of Infinity, and one HELP REQUEST on a related matter.
	Comment, followed by help request.

	COMMENT: The phrase "Axiom of Infinity" can be interpreted in more
than one way.  For the purposes of this FoM string, Steven Simpson
interprets it as denoting FIRST ORDER sentences having only infinite
models.  Much of the discussion has focused on ordering them by
INTERPRETABILITY: can the (first order) theory axiomatized by one AoI be
interpreted in that axiomatized in the other?  Church's discussion (in his
1956 "Introduction to Mathematical Logic") takes it to be a sentence of
Higher Order logic true only in models with an infinite domain of
individuals.  Obviously, an AoI in the first sense can be converted into an
AoI in the second sense by treating its non-logical vocabulary as variables
and binding to initial existential quantifiers.  I'd like to point out
(what I think is the obvious) fact that non-equivalent AoI in the first
sense (not only not logically equivalent, but not even mutually
interpretable) can be converted in this way to logically equivalent Second
Order AoI.

	Consider the following two First Order AoI:
	(1) R is a discrete linear order with bottom but no top
	(2) S is like the successor relation in arithmetic: Every object is
S-related to a unique object, there is an object to which nothing is
S-related (i.e. zero), and two objects S-related to the same object are
identical.
	They are not logically equivalent ((1) requires that R be
transitive; (2) that transitivity fails for S).  The theory axiomatized by
(2) is interpretable in that axiomatized by (1): define S to be the
relation holding between an object and the object that is IMMEDIATELY
R-above it.  I think, however, that it follows from a result of Gaifman's
that the interpretability doesn't hold in the other direction (cf. Haim
Gaifman, "On Local and Non-Local Properties," in J. Stern, ed.,
"Proceedings of the Herbrand Symposium: Logic Colloquium '81," pp.105-135
(book is in the North-Hollan yellow "Studies in Logic" series)).  In
particular, if I understand Gaifman's theorem right, for every dyadic
relation definable in the language of (2), there is some natural number N
such that the relation cannot distinguish between the two cases (a) x is
more than N S-jumps from zero and y comes more than N S-jumps after x, and
(b) y is more than N S-jumps from zero and x comes more than N S-jumps
after y.  (Somebody pleas correct me if I'm wrong: I am still trying to
teach myself about Gaifman's theorem and related matters!)

	HOWEVER, when they are converted into Second Order statements
("There is an R such that (1)," "There is an S such that (2)"), they ARE
mutually interpretable: a suitable R can be defined in Frege's way as the
ancestral (transitive and reflexive closure) of S.  (If the two are
modified slightly, so as to allow that the fields of their relations do not
exhaust the domain, their Second Order versions will be provably equivalent
in quite weak axiomatic systems of Second Order Logic.)

	Now the HELP REQUEST.

	Models of (2) have the feature that no object in their domain is
related by the primitive relation of the theory (in either direction) to
more than finitely many others (in fact, to more than two).  In contrast,
an object in the domain of a model of (1) is R-related to infinitely many
others.  Most foundationally interesting theories are, in this regard, more
like (1): every natural number forms sums with all other natural numbers
(so every object in a model of typical arithmetic theories is related to
infinitely many objects by the ternary addition relation), every set in
models of standard set theories belongs to infinitely many others, etc.  I
think the property of (2) just isolated (I propose to call it "Local
Finiteness," or, if that term has a different established meaning, "Finite
Neighborhoodedness") ought to be of some interest.  It doesn't seem to make
First Order theories trivial: I think I've found an undecidable example
that "interprets" (though not in the standard sense) Pi-0-1 arithmetic.
Can someone give me references to papers discussing this property?

Allen Hazen
Philosophy Department
University of Melbourne