Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 13 down vote accepted

Update, May 27, 2013. Cole Leahy and I have now written a joint paper arising from issues originating in this question, and here is an excerpt from the post I made on my blog about it, which is adapted from the introduction of the paper.

J. D. Hamkins and C. Leahy, Algebraicity and implicit definability in set theory (also at the arxiv), under review.

We aim in this article to analyze the effect of replacing several natural uses of definability in set theory by the weaker model-theoretic notion of algebraicity and its companion concept of implicit definability. In place of the class HOD of hereditarily ordinal definable sets, for example, we consider the class HOA of hereditarily ordinal-algebraic sets. In place of the pointwise definable models of set theory, we examine its (pointwise) algebraic models. And in place of Gödel's constructible universe L, obtained by iterating the definable power set operation, we introduce the implicitly constructible universe Imp, obtained by iterating the algebraic or implicitly definable power set operation. In each case we investigate how the change from definability to algebraicity affects the nature of the resulting concept. We are especially intrigued by Imp, for it is a new canonical inner model of ZF whose subtler properties are just now coming to light. Open questions about Imp abound.

Before proceeding further, let us review the basic definability definitions. In the model theory of first-order logic, an element $a$ is definable in a structure $M$ if it is the unique object in $M$ satisfying some first-order property $\varphi$ there, that is, if $M\models\varphi[b]$ just in case $b=a$. More generally, an element $a$ is algebraic in $M$ if it has a property $\varphi$ exhibited by only finitely many objects in $M$, so that $\{b\in M \mid M\models\varphi[b]\}$ is a finite set containing $a$. For each class $P\subset M$ we can similarly define what it means for an element to be $P$-definable or $P$-algebraic by allowing the formula $\varphi$ to have parameters from $P$.

In the second-order context, a subset or class $A\subset M^n$ is said to be definable in $M$, if $A=\{\vec a\in M\mid M\models\varphi[\vec a]\}$ for some first-order formula $\varphi$. In particular, $A$ is the unique class in $M^n$ with $\langle M,A\rangle\models\forall \vec x\, [\varphi(\vec x)\iff A(\vec x)]$, in the language where we have added a predicate symbol for $A$. Generalizing this condition, we say that a class $A\subset M^n$ is implicitly definable in $M$ if there is a first-order formula $\psi(A)$ in the expanded language, not necessarily of the form $\forall \vec x\, [\varphi(\vec x)\iff A(\vec x)]$, such that $A$ is unique such that $\langle M,A\rangle\models\psi(A)$. Thus, every (explicitly) definable class is also implicitly definable, but the converse can fail. Even more generally, we say that a class $A\subset M^n$ is algebraic in $M$ if there is a first-order formula $\psi(A)$ in the expanded language such that $\langle M,A\rangle\models\psi(A)$ and there are only finitely many $B\subset M^n$ for which $\langle M,B\rangle\models\psi(B)$. Allowing parameters from a fixed class $P\subset M$ to appear in $\psi$ yields the notions of $P$-definability, implicit $P$-definability, and $P$-algebraicity in $M$. Simplifying the terminology, we say that $A$ is definable, implicitly definable, or algebraic over (rather than in) $M$ if it is $M$-definable, implicitly $M$-definable, or $M$-algebraic in $M$, respectively. A natural generalization of these concepts arises by allowing second-order quantifiers to appear in $\psi$. Thus we may speak of a class $A$ as second-order definable, implicitly second-order definable, or second-order algebraic. Further generalizations are of course possible by allowing $\psi$ to use resources from other strong logics.

The main theorems of the paper are:

Theorem. The class of hereditarily ordinal algebraic sets is the same as the class of hereditarily ordinal definable sets: $$\text{HOA}=\text{HOD}.$$

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

In the latter part of the paper, we introduce what we view as the natural algebraic analogue of the constructible universe, namely, the implicitly constructible universe, denoted Imp, and built as follows:

$$\text{Imp}_0 = \emptyset$$

$$\text{Imp}_{\alpha + 1} = P_{imp}(\text{Imp}_\alpha)$$

$$\text{Imp}_\lambda = \bigcup_{\alpha < \lambda} \text{Imp}_\alpha, \text{ for limit }\lambda$$

$$\text{Imp} = \bigcup_\alpha \text{Imp}_\alpha.$$

Theorem. Imp is an inner model of ZF with $L\subset\text{Imp}\subset\text{HOD}$.

Theorem. It is relatively consistent with ZFC that $\text{Imp}\neq L$.

Theorem. In any set-forcing extension $L[G]$ of $L$, there is a further extension $L[G][H]$ with $\text{gImp}^{L[G][H]}=\text{Imp}^{L[G][H]}=L$.

Open questions about Imp abound. Can $\text{Imp}^{\text{Imp}}$ differ from $\text{Imp}$? Does $\text{Imp}$ satisfy the axiom of choice? Can $\text{Imp}$ have measurable cardinals? Must $0^\sharp$ be in $\text{Imp}$ when it exists? (An affirmative answer arose in conversation with Menachem Magidor and Gunter Fuchs, and we hope that $\text{Imp}$ will subsume further large cardinal features. We anticipate a future article on the implicitly constructible universe.) Which large cardinals are absolute to $\text{Imp}$? Does $\text{Imp}$ have fine structure? Should we hope for any condensation-like principle? Can CH or GCH fail in $\text{Imp}$? Can reals be added at uncountable construction stages of $\text{Imp}$? Can we separate $\text{Imp}$ from HOD? How much can we control $\text{Imp}$ by forcing? Can we put arbitrary sets into the $\text{Imp}$ of a suitable forcing extension? What can be said about the universe $\text{Imp}(\mathbb{R})$ of sets implicitly constructible relative to $\mathbb{R}$ and, more generally, about $\text{Imp}(X)$ for other sets $X$? Here we hope at least to have aroused interest in these questions.


Original answer:

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

share|improve this answer
    
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 '11 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 '11 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 '11 at 9:17
    
Your answer exceeds my expectations. Thank you! May I ask why you became interested in pointwise definability? –  Cole Leahy Jul 29 '11 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 '11 at 17:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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