0
$\begingroup$

Preliminaries (see e.g. Jech, Set Theory, p. 5): To every formula $\varphi(x)$ of ZF set theory corresponds a class $C = \lbrace x : \varphi(x)\rbrace$, but only to some formulas corresponds a set. Every class is - by definition - definable, but not so every set.

Consider the following handwaving argument:

If the collection of definable sets (which is well-defined but not in first-order language) were a class $\Delta$, there would be a first-order formula $\delta(x)$ such that $\Delta = \lbrace x : \delta(x)\rbrace$.

If the collection of definable sets were a class, it would be a set.

So if it were a class, it would be a set that contains itself (because it is definable). But since there is no set that contains itself (by the axiom of regularity) the collection of definable sets cannot be a class, ergo: there is no formula expressing first-order definability.

Question: Can the emphasized claim - if the collection of definable sets were a class, it would be a set - be proved? E.g. in the line of "it is not too big to be a set (because there are only countably many formulas), so it is a set".

$\endgroup$
  • $\begingroup$ The suggested proof cannot work: while there are only countably many formulae, this can only be seen in the metatheory. $\endgroup$ – Zhen Lin Nov 11 '13 at 14:40
  • $\begingroup$ And there is no other way to prove that the class of definable sets would have to be a set (if it existed)? $\endgroup$ – Hans-Peter Stricker Nov 11 '13 at 14:48
  • 2
    $\begingroup$ Isn't there a model of ZFC in which every set is definable? In which case the class of all definable sets is defined by the formula $x=x$ and is not a set? $\endgroup$ – bof Nov 11 '13 at 17:27
  • 1
    $\begingroup$ Also, I'm just going to quibble here--as Jech uses the term, sets are classes, so not all classes are definable. There is a class for each sentence, but the converse doesn't necessarily (or in this case, actually) hold. $\endgroup$ – Malice Vidrine Nov 11 '13 at 17:33
  • 1
    $\begingroup$ Classes admit parameters. They are definable with parameters. A set $x$ is just $\{y\mid y\in x\}$, the formula here is $\phi(y,z)\equiv y\in z$, with the variable $z$ instantiated by the parameter $x$. $\endgroup$ – Andrés E. Caicedo Nov 11 '13 at 23:42
4
$\begingroup$

No, the claim

if the collection of definable sets were a class, then it would be a set

is not necessarily true. This answer assumes that we formalize the claim as applying to a set-sized model of $\mathsf{ZFC}$, so that the notion of "definable" is definable externally to the model.

As bof points out in the comments, there are models of $\mathsf{ZFC}$ in which every set is definable. In this case the collection of definable sets of the model is equal to the universal class of the model, which of course is not a set of the model. For more information, see this answer of Joel Hamkins to a related question on MathOverflow.

$\endgroup$
2
$\begingroup$

If we're allowed to expand the language with a satisfaction predicate $Sat(x, y)$ and suitable axioms, then something like the argument you give is easily made. For instance, we can say:

$x$ is ${\it definable}$ just in case there is a formula (in the language without $Sat(x, y)$) $\ulcorner\phi(y)\urcorner$ whose only free variable is $y$ and $x = \{y: Sat(\ulcorner\phi(y)\urcorner, y)\}$

Using replacement in the extended language, we can prove that $\{x: x \mbox{ is definable}\}$ is a (countable) set, since there are countably many formulas. Clearly, $\{x: x \mbox{ is definable}\}$ isn't itself definable, for the reason you point out.

We can run a similar argument in higher-order set theory, say NBG with replacement expanded to whole language, defining satisfaction in the usual way.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.