7
$\begingroup$

Let $D$ be the set of definable ordinals. An ordinal s is definable if there is a predicate $p$ (in the language of (first-order) set theory), such that $p(x) \iff x=s$ for all $x$. This is definitely a set (not a proper class), since the list of all syntactically valid predicates is countable, and $D$ is $\le$ to that in size. In particular, $D$ is countable (although most of its elements are not).

We can define two ordinals based on $D$:

  • The ordinal $\delta$ defined as the least ordinal not in $D$. This ordinal is countable (since $D$ is countable, and so can not contain every countable ordinal), and has the property that an ordinal less than $\delta$ iff it is recursively definable (i.e., every ordinal $x<\delta$ is definable and every $y<x$ is also recursively definable). It is also a limit ordinal, since if $\delta-1$ was an ordinal, it would be definable since it is less than $\delta$, and its definition could be used to define $\delta$, which is a contradiction.

  • The ordinal $\Delta$ is the supremum of $D$. It is also not a definable ordinal (since if it where, so would $\Delta+1$, which is greater than $\Delta$). This also means its a limit ordinal, since it is the supremum of a set that does not contain it. However, is it definitely not countable. Indeed, its cardinality is greater than any cardinal definable in set theory. It has the property that any ordinal $x$ is $x<\Delta$ iff it is bounded by a definable ordinal.

My question is, which ordinals are $\delta$ and $\Delta$? In particular, have either or both of them been studied in the literature before? If not, can they be defined in linked to ordinals previously studied?

$\endgroup$
1
  • 1
    $\begingroup$ Perhaps you should start by asking the same question for $\Sigma_n$-definable ordinals instead, which are more manageable (if only because "being $\Sigma_n$-definable" is definable) and can give a sense of what can go on by "passing to the limit". For $n=1$, I think both the smallest un$\Sigma_1$definable $\delta_1$ and the sup of the $\Sigma_1$-definables $\Delta_1$ are the smallest stable ordinal; for $n>1$ I think some things have been said but I can't remember what. $\endgroup$
    – Gro-Tsen
    Jun 24, 2017 at 10:10

2 Answers 2

9
$\begingroup$

In this answer, let me assume as you indicated in the comments that you are working in a second-order set theory with a truth-predicate for first-order truth. Such a theory goes strictly beyond ZFC in consistency strength, but it is provable in Kelley-Morse set theory and indeed, merely in GBC+$\text{ETR}_\omega$, which is weaker than $GBC+\Pi^1_1$-comprehension. So, not too strong.

One thing you can say is that $\Delta$, the supremum of the first-order definable ordinals, is a fully correct cardinal, meaning that $V_\Delta\prec V$. Indeed, $\Delta$ is precisely the smallest correct cardinal. The reason is that $\Delta$ is the supremum of the first $\Sigma_1$-correct ordinal, and the first $\Sigma_2$-correct ordinal, and so on, the first $\Sigma_n$-correct ordinal. So $V_\Delta$ is the union of the increasingly elementary chain, which is therefore itself fully elementary in $V$. And no smaller cardinal can be correct, because the smaller cardinals are bounded by some definable ordinal. So $\Delta$ is the smallest correct cardinal.

Another way to see that $V_\Delta\prec V$ is that $V_\Delta$ satisfies the Tarski-Vaught criterion with respect to $V$, since if $V\models\exists x\ \varphi(x,y)$, where $y\in V_\Delta$, then since $y\in V_\theta$ for some definable $\theta$, one can define the least ordinal $\alpha$ that contains such an $x$ in $V_\alpha$ for all $y\in V_\theta$ that have such an $x$, and so $\alpha$ will be definable and hence less than $\Delta$, and so the desired witness $x$ can be found in $V_\Delta$. Thus, the Tarski-Vaught criterion is fulfilled, and so $V_\Delta\prec V$.

So there is no first-order way to describe $\Delta$, since any first-order property that $\Delta$ has must be shared also by some ordinals below $\Delta$. Of course, $\Delta$ is second-order definable as the supremum of the definable ordinals, and this seems to be a definition of complexity $\Delta^1_1$, since the truth predicate is unique when it exists.

$\endgroup$
2
  • $\begingroup$ Would you mind telling us what $\text{ETR}_\omega$ is? $\endgroup$
    – Wojowu
    Jun 24, 2017 at 7:21
  • 1
    $\begingroup$ $\text{ETR}_\omega$ is the assertion that one may undertake class recursions of length $\omega$. First-order truth is precisely such a recursion, since a truth predicate is the solution of a certain recursion on formulas. $\endgroup$ Jun 24, 2017 at 11:19
9
$\begingroup$

There are several subtle issues with your post.

It is not in general possible to express the notion of "definable", because it leads to contradictions. For example, the class $D$ is not definable in the language of set theory (or whatever language you are using), since if it were, then the least ordinal not in $D$ would be definable, but not in $D$, which is a contradiction.

Meanwhile, there is the phenomenon in set theory of pointwise definable models, which are models of ZFC in which every set is definable without parameters. For example, we discuss this issue at length in my paper:

In a pointwise definable model, there is no least ordinal that is not definable, and there is no ordinal larger than every definable ordinal. In the article, we point out the following, regarding the extent to which definability is first-order expressible:

Let us now turn to the question of the extent to which definability is first-order expressible, by presenting a number of examples that illustrate the range of possibility. We have already observed that the property of a model being pointwise definable is not first order expressible, since it is not preserved by nontrivial elementary extensions. Since pointwise definability is a strong generalization of the axiom V=HOD, it is tempting to introduce such notation as V=D or V=HD to express that a model is pointwise definable, thereby maintaining a parallel to the classical V=HOD notation while emphasizing that the definitions need no parameters. We hesitate to adopt this notation, however, because we fear it would incorrectly suggest that the concept is first-order expressible, which isn't the case.

(i) There is no uniform definition of the class of definable elements. Specifically, there is no formula $\mathop{\rm df}(x)$ in the language of set theory that is satisfied in any model $M\models\text{ZFC}$ exactly by the definable elements. The reason is that if $M_0$ is pointwise definable and $M_0\prec M$ is a nontrivial elementary extension, then the definable elements of $M_0$ and $M$ are precisely the elements of $M_0$, and so $M_0$ should satisfy $\forall x\,\mathop{\rm df}(x)$ but $M$ would satisfy $\exists x\,\neg \mathop{\rm df}(x)$, contrary to $M_0\prec M$.

(ii) The class of definable elements can form a definable class. Although there is no uniform definition of the class of definable elements, it can sometimes happen that a model enjoys a certain structure that allows it to see its collection of definable elements as a definable class. For example, in a pointwise definable model, the class of definable elements includes every object and is therefore defined by the formula $x=x$. See also (iv) and (v) below.

(iii) The collection of definable elements might not form a class. Consider any model $M\models\text{ZFC}$, and let $N$ be an ultrapower of $M$ by an ultrafilter on the natural numbers. The parameter-free definable elements of $N$ are necessarily contained in the range of the ultrapower map, and in particular, do not include any of the newly added nonstandard natural numbers. Thus, the class of definable elements of $N$ is not amenable to $N$, for it would reveal that its natural number are not well-founded.

(iv) The definable elements can form a definable class in a model having no class function $r\mapsto\psi_r$ mapping definable elements to definitions. Suppose that $M$ is a pointwise definable model of \ZFC. The definable elements of $M$ are all of $M$, which is certainly a definable class in $M$. But $M$ cannot have a function $r\mapsto\psi_r$ associating to each element $r$ of $M$, or even to each real of $M$, a defining formula $\psi_r$, since such a map would reveal to $M$ that it has only countably many reals.

(v) The definable elements can be a set in a model that does have a definability map $r\mapsto\psi_r$. Suppose that $\kappa$ is an inaccessible cardinal (this hypothesis can be reduced), and observe by a Lowenheim-Skolem argument that there are numerous $\gamma<\kappa$ with $V_\gamma\prec V_\kappa\models\text{ZFC}$. It follows that the definable elements of $V_\kappa$ are all in $V_\gamma$ and satisfy the same definitions there as in $V_\kappa$. Since $V_\gamma$ is a set in $V_\kappa$, we may construct in $V_\kappa$ the function $r\mapsto \psi_r$ that maps every definable element $r$ of $V_\gamma$ to the smallest definition $\psi_r$ of it, and because $V_\gamma\prec V_\kappa$, this function has the same property with respect to $V_\kappa$, as desired. The large cardinal hypothesis can be reduced; it is sufficient to have an $\omega$-model $M$ with some $M_0\in M$ having $M_0\prec M$.

(vi) No model can have a definable definability map $r\mapsto\psi_r$. If such a map were definable, then since there are only countably many definitions $\psi_r$, we could easily diagonalize against it to produce a definable real not in the domain of the map. In (v), the map is definable from parameter $\gamma$.

Meanwhile, the universal definition shows that there is a single definition that can in principle define any desired object. For example, any set at all, including any ordinal, can be made definable in a forcing extension of the universe.

$\endgroup$
5
  • $\begingroup$ I was thinking that one would work in a second order set theory instead, or ordinary set theory extended with a truth predicate (both of which are strictly more expressive than ordinary set theory). $ZFC_2$ (second order $ZFC$), for example. $\endgroup$ Jun 24, 2017 at 1:08
  • $\begingroup$ That simply puts off the problem, since if one then considers second-order definability, the same problem resurfaces. The least non-second-order-definable ordinal is not definable in second-order set theory. $\endgroup$ Jun 24, 2017 at 1:14
  • $\begingroup$ But I suppose one can ask about $\delta$ and $\Delta$ for first-order definability, defined in a second-order set theory, such as one with a first-order truth predicate. $\endgroup$ Jun 24, 2017 at 1:15
  • $\begingroup$ "But I suppose one can ask about δ and Δ for first-order definability, defined in a second-order set theory" That's what I was talking about. I know that theories can not in general analyze their own semantic properties. $\endgroup$ Jun 24, 2017 at 2:03
  • $\begingroup$ I edited the question to note that I was defined definable ordinals in terms of the language of first order set theory. This answer is still valuable though. $\endgroup$ Jun 24, 2017 at 2:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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