FOM: No Weakest Axiom of Infinity

[Allen Hazen]

	  Recent posts from Simpson and Urquhart have mentioned the theorem
that "there is no weakest axiom of infinity."  I have been puzzled by this
for a long time.  This probably says more about me than about the intrinsic
difficulty of the issue.  I think I've de-puzzled myself; since I don't
know of a self-contained textbook account, here is mine.  (Thanks to
Urquhart for suggestions.)
--
The Theorem about Axioms of Infinity
A: Trakhtenbrot on finite satisfiability
B: there is no weakest axiom of infinity
C: a surprise about the Axiom of Choice
D: Compactness and a request
--
-----A-----
The key here is the fact that "There is no weakest Axiom of Infinity" is a
corollary of Trakhtenbrot's theorem that the set of first-order formulas
valid in FINITE models (i.e. whose negations are not FINITELY satisfiable)
is undecidable. This follows from G=F6del 1931. There is no complete
axiomatization of the Pi-1-1 sentences of arithmetic (i.e., the set of
Pi-1-1 truths is not r.e.). A proper initial segment of the natural
numbers, however, can be thought of as a finite model. So, (*), if finite
satisfiability was decidable, we'd have have a way of proving arbitrary
Pi-1-1 truths of arithmetic: just carry out the decision procedure and note
that no finite model knocks out the candidate sentence! (The fiddly bit,
(*), has to do with a bit of change to the sentence: finite segments of
omega are not closed under addition and multiplication, so what we would
have to test in finite models was a variant: put a bound on the initial
universal quantifiers of the Pi-1-1 sentence (using a new constant), and
check that the bounded sentence holds in models that go enough higher than
the bound to include denotations for all the terms appearing.)
-----B-----
An axiom of infinity is a sentence of n-th order logic, for some n, which
is true in all and only models with an infinite domain of individuals. We
can limit our attention to sentences containing no non-logical vocabulary,
since a sentence with predicate constants can have them treated as
variables bound by initial existential quantifiers. One axiom of infinity
is said to be WEAKER than another if it is derivable from it in an
axiomatizable fragment of higher-order logic but not vice versa.
(Reference: section 57 of Church 1956, "Introduction to Mathematical
Logic.") 	So. Suppose there were a weakest Axiom of Infinity, Q. It
would have to be derivable from EVERY other axiom of infinity. Now choose
an arbitrary 1st order formula, P. On the supposition that Q exists, we can
test P for finite validity as follows. First, form P* by treating the
non-logical constants of P as variables and existentially quantifying them.
Note that, if P is finitely valid, then P*, if satisfiable at all, is an
axiom of infinity. Now we start two mindless-search algorithms side by
side: (a) search for a finite model falsifying P, (b) search for a formal
proof of (P* -> Q). One of these is bound to terminate; if (a) succeeds P
is not finitely valid, and if (b) does it is.
	Comments: (i) Since P* is formed by existentially quantifying a
1st-order sentence, it doesn't matter whether P* is unsatisfiable or an
axiom of infinity: either way, (P* -> Q) will be provable.
		(ii) Church, op. cit., discusses only 2nd order axioms of
infinity, but the result obviously holds for higher orders as well.
		(iii) If a 1st order sentence (e.g. the negation of P,
above) is finitely satisfiable, an exhaustive search will IN PRINCIPLE find
a model. Note, however, that this is a thoroughly unbounded algorithm. From
Trakhtenbrot's theorem it follows that, for any recursive function f, there
is a natural number i such that for some 1-st order sentence S of length i,
S is finitely satisfiable but its smallest model has size > f(i). We're
talking EFFECTIVE computability, not FEASIBLE! <gr>
-----C-----
	The surprising thing about the result of part B is that it is
DIFFERENT from the other well-known fact about axioms of infinity.
Elementary set-theory textbooks give two definitions of INFINITE SET:
Dedekind-infinite and non-inductive. Famously, these (or the Axioms of
Infinity formed from them) can only be shown equivalent by use of the Axiom
of Choice. Leaving the naive reader (me) with the impression 	"Yes there
are non-equivalent Axioms of Infinity, 	but the Axiom of Choice saves the
day and lets you prove them equivalent."
		WRONG! This is a different phenomenon; even if we include
the Axiom of Choice in the axiomatized fragment of higher order logic
considered above, there is STILL an infinite sequence of ever weaker Axioms
of Infinity.
-----D-----
	In a way this shouldn't surprise us. Consider the infinite sequence
of 1st order (with identity) sentences
 	"There is at least one thing"
	"There are at least two things"
	"There are at least three things"
and so on. They are jointly satisfiable only in infinite domains, so they
can be thought of as constituting, not an Axiom of Infinity, but an
"Axiomatization of Infinity." All of them ought to be derivable from any
sentence calling itself an Axiom of Infinity: any Axiom of Infinity is at
least as strong as this "Axiomatization." By compactness, however, no Axiom
of Infinity is derivable from it! Thus, any Axiom of Infinity is properly
stronger than the 1st order "Axiomatization." So if there were a weakest
Axiom of Infinity, there would be a **gap**. Which would be a surprising
and disturbing fact.
		HOWEVER... I don't actually know of any Axiom of Infinity
weaker than
					(*) There is a nonempty family of
sets containing a proper superset
								of each of
its members.
I am fond of (*) for a number of reasons. It is close to Whitehead and
Russell's Inf Ax. It amounts to saying that the universe is infinite in the
non-Dedekind sense from introductory set theory texts. It is in a language
(Monadic Third Order logic: closely related to the "Framework" of David
Lewis's "Parts of Classes") that I have spent time with. By (B), above,
there are weaker Axioms of Infinity. Can anyone give me an example of a
properly weaker one? (Reasonably short, natural, non-pathological examples
not encoding complex statements about Turing machines preferred.)

Allen Hazen
Philosophy Depaertment
University of Melbourne