3
$\begingroup$

Trevor pointed out, that

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.

That means: the collection of definable sets of a model can be a proper class, i.e. doesn't have to be a set.

But can the collection of definable sets – definable or not – be (co-extensive with) a set?

Added (following Carl Mummerts advice):

A set is a member of a set-theoretic universe, i.e. an element of a model $\mathcal{M}$ of a set theory $\mathsf{ST}$, e.g. $\mathsf{ZFC}$.

A set $x$ is definable if there is a finite formula $\varphi(y)$ in the first-order language of (any) set theory – with signature $\sigma = \lbrace \in \rbrace$ – such that $x = \lbrace y : \varphi(y)\rbrace$, i.e. $(\forall y)\ y \in x \leftrightarrow \varphi(y)$.

What I am - admittedly - unspecific about is whether $(\forall y)\ y \in x \leftrightarrow \varphi(y)$ means

  • there is a model $\mathcal{M}$ of a set theory $\mathsf{ST}$ with $\mathcal{M} \models (\forall y)\ y \in x \leftrightarrow \varphi(y)$

  • for every model $\mathcal{M}$ of a set theory $\mathsf{ST}$ it holds $\mathcal{M} \models (\forall y)\ y \in x \leftrightarrow \varphi(y)$

  • $\mathsf{ST} \vdash (\forall y)\ y \in x \leftrightarrow \varphi(y)$

So for a given set theory $\mathsf{ST}$ my question is threefold.

The question arises what a set theory $\mathsf{ST}$ is supposed to be. I assume: its signature $\sigma$ is $\lbrace \in \rbrace$ and its axioms include the axioms of a naive set theory.

$\endgroup$
2
  • 2
    $\begingroup$ The problem with this sort of question is that you have to work out what you mean by "definable" and what you mean by "be a set". $\endgroup$
    – Carl Mummert
    Nov 19, 2013 at 14:29
  • $\begingroup$ Consider the theory of the quine atom, which is axiomatized by the single axiom $\exists x, \forall y, y\in x \land y=x$, where $y=x$ can be shorthand for $\forall z, [z\in x \iff z\in y] \land [x\in z \iff y\in z]$. This theory has only one model (up to isomorphism), and that model has only one set $q$, which is a quine atom, and thus is also the set of all sets. Since the set of all sets is definable (if it exists), then $q$ is definable. Since $q$ is the only set, the class of definable sets is just $\{q\}$, which is exactly $q$, so the class of all definable sets is a set in this theory. $\endgroup$
    – Jade Vanadium
    Apr 15 at 15:45

2 Answers 2

Reset to default
4
$\begingroup$

(This was written before a significant edit to the question.)

It's somewhat complicated, because you have to pay attention to which metatheory you use to talk about "definable" and "is a set".

Suppose we start with a model $M$ of ZFC in which there is an inaccessible cardinal $\lambda$. Then $M$ satisfies the formula that says $N = V_\lambda$ is a model of ZFC. Moreover, $M$ contains a satisfaction relation on $V_\lambda$, and thus, within $M$, we can formalize a relation $$P(X) \equiv [X \in V_\lambda \land X \text{ is definable over } V_\lambda \text{ without parameters}]$$ But then, within $M$, we can define the set $$ Z = \{ X \in V_\lambda : P(X) \}. $$ Thus $Z$ is a set in $M$. Moreover, $M$ satisfies "$Z$ is countable", because $M$ uses the same set $\omega^M$ to define Goedel numbers for the definability predicate and to test for countability. Thus, by an argument about the ranks of elements of $Z$ all being less than $\lambda$, and $\lambda$ being inaccessible, we have that $M$ satisfies "$Z \in V_\lambda$".

Therefore $M$ satisfies the statement "there is a model $N$ of ZFC such that the definable elements of $N$ form a set in $N$." The argument shows that the consistency of this statement follows from the consistency of ZFC + "there is an inaccessible cardinal".

Upon reflection, you can see what goes wrong without some assumption like an inaccessible cardinal: if $N$ was some other model of ZFC not of the form $V_\lambda$, where $\lambda$ has uncountable cofinality, then there would be no easy way to prove that $Z \in N$, and so the argument would not go through. In particular, if $N$ was countable, it can actually happen that every element of $N$ is definable over $N$.

Also, note that there are two levels of metatheory here: we prove to ourselves that $M$ satisfies various facts about $N$. So:

  • A person living in $N$ would believe "the definable elements of my universe form a set" (if that person could say what "definable" even means - this is an important issue)

  • A person living in $M$ would believe "there is a universe $N$ in which the definable elements form a set" (and a person in $M$ does know what it means for a set to be definable in $N$)

  • We may believe "there is a universe $M$ in which a person would believe that there is a universe $N$ in which the definable elements form a set". We will believe this, for example, if we believe in the consistency of ZFC + "there is an inaccessible cardinal".

$\endgroup$
3
  • 1
    $\begingroup$ Re the addition to the Q: the relation of "definable" is between an object $X$ and a model $M$; $X$ is definable over $M$ if there is a formula $\phi(z)$ in the language of $M$ such that $X$ is the unique element for which $M \models \phi(X)$. This does depend on the model; Hamkins, Rietz and Linetsy have proved that every countable model of ZFC has a forcing extension in which all sets are definable without parameters - see mathoverflow.net/questions/44102/… $\endgroup$
    – Carl Mummert
    Nov 19, 2013 at 15:22
  • $\begingroup$ I think we can weaken the assumption that $V_\lambda$ has uncountable cofinality to "there is a $\kappa \lt \lambda$ such that $V_\kappa \prec V_\lambda$". $\endgroup$
    – Arvid Samuelsson
    Apr 27 at 14:35
  • $\begingroup$ We can also weaken the assumption that $N$ is of the form $V_\lambda$ to being transitive. We still need a $\kappa \in N$ such that $V_\kappa^N \prec N$. This implies that $N \vDash \text{there are stationarily many worldly cardinals}$, so it still has greater consistency strength than ZFC. $\endgroup$
    – Arvid Samuelsson
    Apr 27 at 14:43
2
$\begingroup$

The second two parts of your question for ST have simple answers.

If ST has no models, then every set is definable in every model of ST (trivially). If ST has a model, it has arbitrarily large models by the Lowenheim-Skolem theorem. But at most countably many sets are definable in ${\it all}$ models of ST (since at most countably many sets are definable in any particular model). So, proper class many elements of models of ST fail to be definable in all models of ST.

I'm not quite sure what it would mean for ST to prove ${\it of}$ a set $x$ that it's co-extensive with $\phi$. But if ST is consistent, consists of sentences, contains extensionality, and thinks that there are at least two sets, it will not prove:

(*) $\forall y(y\in x\leftrightarrow \phi(y))$

If it did, it would also prove:

(**) $\forall x\forall y(y\in x\leftrightarrow \phi(y))$

contradicting extensionality and the fact that there are two sets.

$\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.