FOM: Interpreting Set Theory in Higher Order Logic

[Allen Hazen]

	This is a followup (correction) to my "Mysteriousness of
Membership" and follow up (comment) to Randall Holmes's "Are sets made up
of their members?" posts.
	One of the views called "structuralism" in the philosophy of
mathematics is the idea that mathematics is NOT interested in particular
mathematical objects, but only in certain kinds of structures.  Thus:
Frege's effort to identify the natural numbers as particular objects is
unmotivated, because arithmetic is not about numbers, but rather about the
structure of the omega-sequence; it is enough to postulate that there is a
class of objects ordered like the natural numbers without specifying what
they are, and the theorems of arithmetic hold in ANY such class.  If
something like Second-Order Logic is taken as a background, this leads to a
(small) research program: formulate the notion of a standard model of some
mathematical theory as a condition on a relation (e.g. an omega-sequence is
a successor-like relation: one-one, relating every obect in its field to
another, and with precisely one object in its field not having another
related to it), and then show that the axioms of the theory either amount
to theorems of Second-Order Logic or follow from some assumption about the
number of individuals in the universe.  David Lewis does this very
elegantly for ZF in his book "Parts of Classes" and in the article
"Mathematics is Megethology" ("Philosophia Mathematica" series 3, vol. 1
(1993); repr. in Lewis's "Essays in Philosophical Logic"), using his
"framework" instead of Second Order Logic.  (The article is a condensation
of book, incorporating a few improvements.)
	Holmes, in his FoM posting of 7.vi.2000, presents a different way
of doing it.  (Holmes's interpretation is not quite of the form I describe:
rather than defining a single relation to represent a standard model of ZF,
he allows each set to be represented by a different relation.  I think the
"spirit" of the interpretation is similar.)
	Now, COMMENT: just which axioms of ZF turn out to be theorems of
Second-Order Logic (or Lewis's "Framework") and which require hypotheses
about the number of individuals depends on the particular interpretation
used.  I will illustrate with an interpretation I sketched in "Journal of
Philosophical Logic" 1997.  As background logic I use Monadic Third Order
Logic (a close relative of Lewis's "framework"), and interpret ZF with
Foundation.
	Terminology: I use "individual," "species," and "genus" for items
in the ranges of the three sorts of quantified variables (sorry if you
don't like nonstandard terminology, but in discussing the axiomatization of
set theory it is least confusing to use resolutely non-set-theoretic
terms!).
	A STANDARD MODEL can be represented by two genera, one representing
the system of RANKS in the model, and the other, with its help,
representing the MEMBERSHIP relation.  The first genus is a genus of nested
species: species linearly ordered by inclusion.  Think of the individuals
of some species of this genus as the sets of less than or equal to a given
rank.  A symmetric irreflexive relation can be represented in Monadic 3rd
O.L. by a genus of species each containing precisely two individuals (i.e.
by a genus of unordered pairs).  Since, of any two sets related by
membership, one will be of a lower rank, the membership relation can be
recovered from its symmetric closure.  So we stipulate that the individuals
belonging to species of the second genus are precisely those in the union
of the species of the first genus, and of the two indivudials in a species
of the second genus, one will belong to some species of the first genus
that the other does not belong to.  Add a few more definitional
stipulations: (i) the smallest rank contains just one individual (the null
set), (ii) given a species of individuals (in the union of the ranks) such
that there is SOME rank with each of them belonging to some one of its
PROPER subranks, there is a LEAST rank such that all of them belong to its
proper subranks, (iii) given such a species, there is a UNIQUE individual
in the least "outside" rank that (in effect) is the set of them, ... and
one or two more.
	A MAXIMAL standard model is one which (because there aren't enough
individuals in the universe) can't be extended to a bigger one by adding a
new, larger, rank.  A sentence is a TRUTH OF SET THEORY if it is true in
all maximal standard models.
	The sentences of set theory which come out true on THIS
interpretation independent of any assumption about the size of the universe
are those of Montague's "Second-Order Rank-Free Set Theory" (cf. his "Set
Theory and Higher-Order Logic," in Crossley & Dummett, eds., "Formal
Systems and Recursive Functions"): this includes the ZF axioms of Null-set,
Extensionality, Aussonderung,  Union, and Foundation, but not the
rank-increasing Pair-set and Power-set.  (In my earlier post I carelessly
suggested that it was Holmes's interpretation that yielded this fragment
without cardinality assumptions.)
	Comparing a variety of such interpretations and proving which
standard set-theoretic axioms depend on which cardinality assumptions might
be a good project for an undergraduate thesis.  (Since the Montague, Scott,
and Tarski monograph that was to contain the details never appeared,
showing the adequacy of Montague's axioms for Rank-Free set theory might be
be a good term-paper project.)

Allen Hazen
Philosophy Department
University of Melbourne