[FOM] Definable Sets in ZFC

[Ali Enayat]

This note is in response to the recent questions posed by Florian Rabe
about definable sets in ZFC, some of which have been answered by Max
Weiss and Monroe Eskew.

Let me point out at the outset that the axiom of choice does not play
any role in the discussion, so I will use ZF instead of ZFC.

[Re: question 1]. The easiest example of an undefinable set within ZF
is the collection of ``true" ZF statements. More concretely, given a
model M of ZF [or of any sufficiently strong theory] the Godel-numbers
of the collection of first order sentences that are true in M cannot
be a definable set in M, by Tarski's classical ''undefinability of
truth" theorem.

[Re: questions 3-6; q2 was answered by Weiss]. There are models of ZF,
and indeed ZFC, in which *every* element is definable [assuming the
consistency of ZF]. This is true, for example, of  the
[Shepherdson-Cohen] minimal model of set theory [this was also pointed
out by Monroe Eskew].

At first sight this is paradoxical since [quoting Rabe] "Clearly, not
all sets are definable because there are only countably many formulas
F". But there is no paradox here since the argument that establishes
"there are only countably many definable objects" can only be
formulated in an *extension* of ZF, not ZF itself.  One such
well-known extension is KM [Kelley-Morse theory of classes], since
within KM one has access to a "satisfaction predicate" for the class
of all sets.

The next question is whether the collection of definable elements of M
can be definable by a parameter-free formula F(x) in M. This is of
course possible, since if every element of a model M is definable in
M, then the formula F(x) can be chosen as x=x. Indeed, one can
characterize those models of ZF in which the collection of definable
elements form a definable class. This characterization uses the
following key definition.

Definition. A model M of ZF is a **Paris model** if every ordinal of M
is definable in M by a parameter-free formula.

Characterization Theorem. The collection of definable elements of a
model M of ZF is a definable class of M iff M is a Paris model.

The left-to-right direction of the theorem is handled by a classical
argument: suppose not, and consider the least undefinable ordinal. The
converse is handled by the notion of "ordinal definability" since in a
Paris model, being ordinal definable is the same as being definable .
Note that in particular, in any generic extension of the minimal model
of set theory the collection of definable elements form a definable
class.

Note 1. The collection OD of elements of M that are definable with
*ordinal parameters* form a definable class of M, thanks to the
reflection theorem; Godel noticed this fact in unpublished work, as
pointed out in the classical Myhill-Scott paper on the subject (1970);
this is explained in many graduate level set theory texts; I recommend
Kunen's thorough account.

Note 2. What I am referring to as a `Paris model' was dubbed `DO
model' by Jeff Paris, who proved in his 1973 paper that every
consistent extension T of ZF has a Paris model; and that a Paris model
of T is unique up to isomorphism iff T includes the axiom V=OD. See my
paper [Models of set theory with definable ordinals, Arch. Math.
Logic, vol.44, pp.363-385 (2005)] for more detail.

Finally, let me point out that the collection of definable elements of
M can form a *set* d in a model M [but no such d can be definable in
M, since the least ordinal not in d leads to a contradiction]. For
example, M can be chosen to be the rank initial segment of the
universe determined by an inaccessible cardinal.

Regards,

Ali Enayat