## Pointwise algebraic models of set theory

Let $\mathfrak{M} = \langle M, E \rangle$ be a structure for the language of set theory, and take some $B \subseteq M$ and $m \in M$. Say that $m$ is definable over $B$ iff there is a formula $\phi(x,\overline{y})$ in the language and a sequence $\overline{b}$ from $B$ such that $\mathfrak{M} \models \phi[a, \overline{b}]$ iff $a = m$. 'Definable' means definable over the empty set. Call $\mathfrak{M}$ pointwise definable over $B$ iff each of its elements is.

I learned here on MO that the pointwise definable models of ZFC are precisely the prime models of the theory ZFC + V = HOD. (A model of a theory is prime iff it embeds elementarily into every other model of the theory.) In particular, the minimal transitive model of ZFC is pointwise definable, and every countable model of ZFC has a pointwise definable forcing extension. Another thing I learned, in a paper by Marek and Srebrny called "Gaps in the Constructible Universe", is that if a new set of natural numbers appears at level $L_{\alpha+1}$ of the constructible universe, then $L_{\alpha}$ is pointwise definable. Though I haven't learned much about models that are pointwise definable over $B$, I would be delighted if someone schooled me.

Related to definability is the notion of algebraicity. An element $m$ of $M$ is algebraic over $B$ iff there is a formula $\phi(x,\overline{y})$ and a sequence $\overline{b}$ from $B$ such that $\mathfrak{M} \models \phi[m, \overline{b}] \wedge \psi[\overline{b}]$, where $\psi$ is the formula $\exists_{\leqslant n}x\phi(x,\overline{y})$ for some natural number $n$. One question:

Do we expect notable differences between the theory of pointwise algebraic models of ZFC (or of weaker foundational set theories) and that of pointwise definable models?

For instance, is there a pointwise algebraic $L_{\alpha}$ such that no new set of naturals appears at $L_{\alpha+1}$? Is there a model theoretic characterization (along the lines of the prime model of ZFC + V = HOD result) of the class of pointwise algebraic models of ZFC? Another question:

Are there any open questions, relevant to foundations, about the theories of pointwise definable and pointwise algebraic models of set theory?

-

It is a very nice question.

If you restrict to well-founded models, and this includes your $L_\alpha$ examples, then a model is pointwise definable if and only if it is pointwise algebraic. The forward implication is clear. For the backward implication, suppose that $M$ is pointwise algebraic; let us prove that $M$ is pointwise definable by induction on rank. Consider any element $a$, and assume all sets of lower rank are definable in $M$. Since $M$ is algebraic, there is a definable finite collection $a_0,a_1,\ldots, a_n$ that includes $a=a_0$, with this set of minimal finite size. These sets must all have the same rank, since otherwise we could make a smaller definable family including $a$, and so all their elements are definable. Thus, if $a\neq a_i$, there must be some element in one of them that is not in the other. But that element is definable, and so we can again make a smaller family by adding to the definition the requirement that the set must contain (or omit, whatever $a$ does) that new element. This would make a smaller definable set, violating the minimality of the finite set, unless indeed our minimal set had only one element. So $a$ is definable after all.

This argument works only in well-founded models, however, since the induction is not internal.

Update. In a conversation with Leo Harrington at math tea here at the National University of Singapore, where I am visiting, we worked out the general ZFC case with the following observation:

Theorem. Every pointwise algebraic model of ZFC is pointwise definable.

Proof. Suppose that $M\models\text{ZFC}$ and is pointwise algebraic. Note that this implies that every ordinal of $M$ is definable, since if we can define a finite set of ordinals containing some ordinal $\alpha$, then since the ordinals are definably linearly ordered, $\alpha$ is the $k^{th}$ member of that set and hence definable. Now, we argue that every set $A$ of ordinals in $M$ is pointwise definable. Well, since $A$ is algebraic, it is a member of a finite definable set. But the lexical order on sets of ordinals is definable and linear, and so again we may find a definition of $A$, since it will be the $k^{th}$ element in that finite set for some $k$. Thus, every set of ordinals in $M$ is definable in $M$. But by ZFC, every set $a$ is coded by a set of ordinals, and since that set of ordinals is definable, it follows that the original set $a$ is also definable. Thus, every set in $M$ is definable without parameters. QED

After this, I realized that we can actually omit the use of choice.

Corollary. Every pointwise algebraic model of ZF is a pointwise definable model of ZFC+ V=HOD.

Proof. Suppose that $M\models\text{ZF}$ and is pointwise algebraic. It follows as in the theorem above that every ordinal of $M$ is definable without parameters. Thus, every object in the HOD of $M$ is also definable in $M$ without parameters. If $M$ is not equal to its HOD, then let $A$ be an $\in$-minimal element of $M-\text{HOD}$. Since $A$ is algebraic, there is a finite definable set containing $A$. By minimality, every element of $A$ is in HOD, and so we have a definable well-ordering on the elements of the members of the definable set containing $A$. Thus, there is a definable linear ordering (induced from the lexical order on the definable HOD order) on the subsets of HOD, and so $A$ is the $k^{th}$ element of the finite definable set for some finite $k$, and so $A$ is definable in $M$ without parameters. In this case, since $A\subset\text{HOD}$, it would mean that $A$ should be an element of HOD, contrary to assumption. Thus, $M=\text{HOD}^M$, and so $M$ is a model of ZFC+V=HOD, and also pointwise definable by the theorem.QED

-
 Nice! I was wondering whether algebraicity would yield anything new. What's "internal" induction? Google suggests it may be related to overspill, another thing I've heard of but haven't learned about. – Cole Leahy Jul 29 2011 at 1:18 By internal induction, I would mean an inductive argument that could be carried out inside the model. A non-well-founded model $M$, for example, would be unable to undertake the argument I gave, even though it satisfies the foundation axiom, since the "class" of definable elements is not definable. Thus, my answer is not the whole story---perhaps there can be an ill-founded pointwise algebraic model of ZFC that is not pointwise definable. I'm not currently sure. – Joel David Hamkins Jul 29 2011 at 4:33 Leo Harrington and I figured out the general ZFC case, which is that pointwise algebraic is the same as pointwise definable, and so I have added an update. – Joel David Hamkins Jul 29 2011 at 9:17 Your answer exceeds my expectations. Thank you! May I ask why you became interested in pointwise definability? – Cole Leahy Jul 29 2011 at 15:41 @Joel: very nice! Now this raises the next question of whether in your theorem $ZF$ can be weakened to $ZF$\{Power set}; I suspect that the answer is negative, but from what I can tell the answer becomes positive if we add the assumption that $V$ is $H(\kappa)$ for some cardinal $\kappa$ to $ZF$\{Power set}. – Ali Enayat Jul 29 2011 at 17:49