FOM: axioms of infinity: first-order versus higher-order

[Stephen G Simpson]

In my recent postings in this thread (July 20), I defined an axiom of
infinity to be a consistent sentence of *first-order* predicate
calculus with no finite model.  But Alan Hazen in his postings (July 6
and July 23) follows Church in considering axioms of infinity in the
context of *higher-order* logic.

To avoid misunderstandings, I want to point out that Hazen and I are
dealing with essentially the same logic and obtaining essentially the
same results.  This is because Hazen has not been considering *full*
higher-order logic (i.e., with the "standard" or full-power-set
semantics).  Rather he has been considering "an axiomatizable fragment
of higher-order logic" (Hazen, FOM, Thu, 06 Jul 2000 15:58:16 +0800).
Here presumably "axiomatizable" entails recursively axiomatizable and
therefore r.e. (recursively enumerable).  Thus Hazen is really dealing
with some variant of what has sometimes been called higher-order logic
with Henkin semantics.  It is not honest-to-God higher-order logic
(what Quine called "set theory in sheep's clothing"), but rather a
species of many-sorted, first-order logic.

See also the "second-order logic is a myth" discussion thread, FOM,
February/March, 1999.  In particular, see Martin Davis, FOM, Mon, 22
Feb 1999 14:36:21 -0800.

For Shavrukov's result (July 20) and my refinement of it, the only
property of the interpretability relation needed is that it is r.e.
This is the case for any reasonable notion of interpretability, both
for first-order logic and for every (recursively) "axiomatizable
fragment of higher-order logic", including those considered by Hazen.
Thus, in all of these settings, there are infinitely many different
axioms of infinity.

On the other hand, if we consider not fragments but rather the *full*
higher-order logic (with "standard" or full-power-set semantics), then
the situation regarding axioms of infinity becomes trivial: there is
only one axiom of infinity, up to logical equivalence.  In the setting
of full higher-order logic, all axioms of infinity are not only
interpretable in each other but logically equivalent to each other.  A
structure is infinite if and only if it satisfies, for example, the
second-order sentence "there exists a linear ordering of the universe
with no top element".  (Here I use the Axiom of Choice, to show that
every infinite set carries a linear ordering with no top element.)

-- Steve