-3
$\begingroup$

Is there a known result to the effect that it cannot be the case that for some natural $n$, there is a formula of length $n$ such that all cardinals can be defined by a formula whose length is shorter than $n$?

I'm speaking in the milieu of some fragment of a standard set theory extending first order logic with identity and membership, for example $\text{ZF-Regularity}$.

I've always expected that as regards the $\aleph_\alpha$ numbers the bigger it is the longer is the shortest definition of it. Or in general there cannot be a finite bound on definability of all of them. Is that correct?

Should the above be un-attainable, then is there a known argument against for example $n=10$ being such an upper bound?

Related is the following question: is it the case that definability of being strictly subnumerous to $\aleph_\alpha$ is always equal or greater than definability of being strictly subnumerous to $\aleph_\beta$ for all $ \beta >\alpha$? By 'definability' I mean the shortest defining expression of course.

After-note: that Joel David Hamkins mentioned that the above linear assumption is FALSE, then my last question is:

is it the case that the definition of $< \aleph_i$ is always shorter than or equal in length to the defintion of $< \aleph_j$ as long as $i,j$ are both finite naturals and $i<j$?

$\endgroup$
7
  • 7
    $\begingroup$ I don't understand the question. There are only finitely many formulas of a given length. For any $n$, there exists a finite cardinal number $k=2^{O(n)}$ (necessarily definable) that is not definable by a formula of length at most $n$. $\endgroup$ – Emil Jeřábek May 11 '18 at 10:24
  • $\begingroup$ Much of this answer is relevant for the question: mathoverflow.net/a/34730/1946 $\endgroup$ – Joel David Hamkins May 11 '18 at 12:35
  • 4
    $\begingroup$ Re: Your edit, why would you expect that to be true? We can have natural numbers $a<b$ such that $a$ is much harder to define than $b$ - e.g. $b=10^{10^{10}}$ and $a=123487984375365781963478923617948371623505835482345978325$ almost certainly has this property - so why should things be any different with $\aleph$s? $\endgroup$ – Noah Schweber May 11 '18 at 17:31
  • 4
    $\begingroup$ @Zuhair My point was just an example. If you prefer, note that you can define $b$ in the language of set theory in a few pages; the number of such definitions is much less than $10^{10^{10}}$ so most numbers $<b$ take longer to define than $b$. $\endgroup$ – Noah Schweber May 11 '18 at 17:45
  • 1
    $\begingroup$ @Zuhair The "or equal to" doesn't make it better. There is no reason to believe that bigger = no less complicated in any context. $\endgroup$ – Noah Schweber May 11 '18 at 19:43
8
$\begingroup$

Yes. This is an easy consequence of the reflection theorem. The point is that we can reason about definability with respect to a small collection of formulas within a model.

Put all formulas of length $\leq n$ (up to renaming variables) in a finite set $S$. Let $V_\alpha$ be such that for all $\phi(x) \in S$, and all $a \in V_\alpha$, $V_\alpha \models \phi(a) \Leftrightarrow V\models \phi(a)$. $V$ can see that there are only finitely many cardinals that can be defined by a formula in $S$ in the structure $V_\alpha$. By the absoluteness of $V_\alpha$ with respect to $S$, the same holds for $V$, so that there is a cardinal $\kappa$ such which is not defined in $V$ by a formula in $S$.

This also shows that only finitely many natural numbers can be defined by a formula in $S$. And the same kind of reasoning can be carried out in the language of PA. We can also draw the same kind of conclusion about Levy complexity.

On the other hand, if $\alpha$ is the least ordinal such that $L_\alpha \models \text{ZFC}$, then every element of $L_\alpha$ is definable. So while ZFC can express, for each $n$ separately, "x is definable by a formula of length/complexity $\leq n$," it cannot express simply, "x is definable."

$\endgroup$
2
  • 8
    $\begingroup$ As $n$ grows, the formula "x is definable by a formula of length $\leq n$" gets longer. There is no uniform definition where we can plug in a number $n$. We have a truth definition for each complexity level, but not for truth as a whole. $\endgroup$ – Monroe Eskew May 11 '18 at 11:39
  • 8
    $\begingroup$ Sorry, I'm not explaining well. There are things going on below the surface. The thing in quotes is not a legitimate formula of set theory. What it stands for is, "there is a formula $\phi(v)$ such that its length is $\leq n$, and $\phi(x)$ is true, and there is no other $y$ such that $\phi(y)$ is true." Now, set theory talks about sets and membeship, not about truth directly. Tarski proved that there is no general way to code "is true." However, for each complexity level, there is a code. (not uniform) $\endgroup$ – Monroe Eskew May 11 '18 at 12:14
9
$\begingroup$

Let me respond to the following statement in your post. You said,

"I've always expected that as regards the $\aleph_\alpha$ numbers the bigger it is the longer is the shortest definition of it."

This is not true. For example, $\aleph_\omega$ is definable, and this definition will have some definite finite length. But as there are only finitely many smaller formulas, only finitely many of the $\aleph_n$ will be definable by a shorter formula. But every $\aleph_n$ for finite $n$ in the meta-theory will be definable by some formula. So there must be many instances where $\aleph_n$ is definable, but only by a formula that is longer than the shortest definition of $\aleph_\omega$. This is a counterexample to the expectation you had expressed.

The same argument shows that for any definable $\aleph_\alpha$, where $\alpha$ itself is infinite, there is some definable $\aleph_n$ with $n<\omega$, such that the shortest definition of $\aleph_n$ is much longer than the shortest definition of $\aleph_\alpha$.

The general phenomenon is that there must always be comparatively large definable cardinals with comparatively short definitions.

$\endgroup$

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