# How many reals can we construct by iteratively writing down truth tables for ZFC?

For the purposes of this question, pretend that there is a platonic, "standard" model $$V$$ of ZFC - so that every set theoretic statement has a meaningful truth value.

Fix a bijection between $$\mathbb{N}$$ and the set of formulas $$\varphi(x)$$ with one free variable $$x$$ in the language of set theory, and let $$\varphi_i(x)$$ be the $$i$$th formula according to this bijection. For every set $$X \in V$$, let $$T(X) \in 2^\mathbb{N}$$ be the truth table for statements involving the set $$X$$, that is, the $$i$$ bit of $$T(X)$$ is set to $$1$$ iff $$\varphi_i(X)$$ is true in $$V$$.

Note that we can't prove that the truth table $$T(X)$$ is a set or even define $$T(X)$$ within the formal framework of ZFC - assume a strong enough metatheory that we can talk about $$T(X)$$ as representing a well-defined thing. Additionally, if we take the idea that $$V$$ is standard seriously, then we should assume that $$T(X)$$ is a set in $$V$$, for every $$X \in V$$.

Starting from the truth table $$T(\emptyset)$$ which encodes all true statements of $$V$$, we can then build the truth table $$T(T(\emptyset))$$ which encodes all the true statements about the nature of truth in $$V$$. The new set $$T(T(\emptyset))$$ is really new: it is not computable from $$T(\emptyset)$$, since $$T(T(\emptyset))$$ can be used to solve the halting problem for Turing machines with oracle access to $$T(\emptyset)$$. In particular, $$T(T(\emptyset)) \ne T(\emptyset)$$.

I want to iterate this construction as boldly as possible. To this end, inductively define a class function $$\mathcal{T} : \operatorname{Ord} \rightarrow 2^\mathbb{N}$$ as follows: for every ordinal $$\alpha$$, if $$V$$ is truly standard then the restriction $$\mathcal{T}|_\alpha : \alpha \rightarrow 2^\mathbb{N}$$ should be a set in $$V$$, so we can define

$$\mathcal{T}(\alpha) = T(\mathcal{T}|_\alpha)$$.

By the same argument as the one showing that $$T(T(\emptyset)) \ne T(\emptyset)$$, if $$\alpha < \beta \in \operatorname{Ord}$$ and if $$\alpha$$ is definable given $$\beta$$ as a parameter, then $$\mathcal{T}(\beta)$$ is not computable from $$\mathcal{T}(\alpha)$$.

Call an ordinal $$\alpha$$ "fresh" if $$\mathcal{T}(\alpha) \ne \mathcal{T}(\beta)$$ for all $$\beta < \alpha$$, and let $$F \subseteq \operatorname{Ord}$$ be the set of fresh ordinals. The restriction of $$\mathcal{T}$$ to $$F$$ gives an injection $$F \hookrightarrow 2^\mathbb{N}$$.

Question(s) 1: What can we say about the order type of $$F$$ (with the induced ordering from $$\operatorname{Ord}$$)? Is $$F$$ uncountable? Could $$|F|$$ be strictly larger than $$\aleph_1$$ (assuming that the continuum hypothesis is false)? Can we determine whether the order type of $$F$$ is a limit ordinal? What can we say about the least ordinal which is not contained in $$F$$ (i.e., the first "stale" ordinal) - could it be definable? Are these questions independent of large cardinal hypotheses/forcing axioms?

We can also ask interesting questions about the long-term behavior of the function $$\mathcal{T}$$. For every $$\alpha \in F$$, let $$S(\alpha)$$ be the collection of ordinals $$\beta$$ such that $$\mathcal{T}(\beta) = \mathcal{T}(\alpha)$$ (so all but one element of $$S(\alpha)$$ is stale). Note that at least one $$S(\alpha)$$ must be a proper class, and that for any definable $$\alpha \in F$$, we have $$S(\alpha) = \{\alpha\}$$.

Question(s) 2: For how many $$\alpha \in F$$ is the collection $$S(\alpha)$$ a proper class? Is there an undefinable $$\alpha \in F$$ such that $$S(\alpha)$$ is a singleton? How many distinct cardinalities show up among the $$S(\alpha)$$s?

Generalizing the problem, we can also build iterated truth tables involving any set $$X \in V$$ as a parameter. Define the function $$\mathcal{T}_X : \operatorname{Ord} \rightarrow 2^\mathbb{N}$$ inductively by

$$\mathcal{T}_X(\alpha) = T((\mathcal{T}_X|_\alpha, X))$$,

where $$(\mathcal{T}_X|_\alpha, X)$$ is the Kuratowski ordered pair. Call an ordinal $$\alpha$$ "fresh for $$X$$" if $$\mathcal{T}_X(\alpha) \ne \mathcal{T}_X(\beta)$$ for all $$\beta < \alpha$$, and let $$F_X$$ be the set of ordinals which are fresh for $$X$$.

If we choose $$X$$ such that for every countable ordinal $$\alpha$$ there is a bijection from $$\mathbb{N}$$ to $$\alpha$$ which can be defined from $$X$$ and $$\alpha$$, then every countable ordinal will be fresh, so we will have $$\omega_1 \subseteq F_X$$.

Question 3: How large can $$F_X$$ be, if we choose the set $$X \in V$$ to make $$F_X$$ as large as possible?

Apologies for asking so many questions at once. I'll be happy with any nontrivial results about the nature of the function $$\mathcal{T}$$ or the set of fresh ordinals $$F$$.

Edit: I just realized that Question 3 isn't nearly as interesting as I had thought it was - if we take $$X$$ to be an injection from an ordinal $$\alpha$$ into $$2^\mathbb{N}$$, then it is easy to prove that $$\alpha \subseteq F_X$$, so Question 3 is really just asking how big the continuum is.

• Note that we can remove the philosophical flavor here by just working inside an appropriate class theory, e.g. $\mathsf{NBG}$ (at a glance I think that should be enough for what you want here). In particular, in this ambient class theory we can legitimately talk about $T$ and so forth without difficulty. Feb 6 at 3:20
• @NoahSchweber It seems to me that the class theory you want should be MK rather than NBG, so that truth in $V$ becomes definable. Feb 6 at 5:08
• @AndreasBlass Yes, I meant MK. Not my finest moment. Feb 6 at 5:28
• Every real definable in $V_\alpha$ will be computable from $T(\alpha)$ since $\alpha$ is coded into $T\restriction \alpha$. So every ordinal definable real is computable from a $T(\alpha)$. Also every real you enumerate will be ordinal definable: in MK, there is a proper class of $\alpha$ with $V_\alpha\prec V$. So the set of fresh ordinals has cardinality the continuum in $\text{HOD}$. Not sure about the order type. I'll post an answer later if I haven't completely misunderstood the question. Feb 6 at 17:22
• I have to think a bit more about the ordertype, which is interesting. Seems the same as the question of whether the canonical wellorder of OD sets restricts to a wellorder of the OD reals in ordertype $\mathfrak{c}^\text{HOD}$. That might be independent. Feb 6 at 18:00

I think it is easier to think about the question generalized to an arbitrary transitive model of ZFC, resisting the natural urge to grasp towards the Absolute. So fix such a model $$M$$, and let $$\mathcal T^M(\alpha)$$, $$F^M$$, and $$S^M(\alpha)$$ be as you defined them, replacing $$V$$ with $$M$$. Let's omit the superscripts, though.

The ordertype of $$F$$ is a limit ordinal: if $$\alpha$$ is fresh, so is $$\alpha+1$$, since in general, one can recover $$\mathcal T(\beta)$$ from $$\mathcal T(\beta+1)$$.

Note that if $$\alpha$$ is definable in $$M$$, $$\mathcal T(\alpha)$$ is fresh since it is the unique value of the function $$\mathcal T$$ containing the index of the formula $$\varphi(\text{dom}(x))$$ where $$\varphi$$ defines $$\alpha$$. In particular, an ordinal that is not fresh is not definable, and so your least stale ordinal is not definable.

Note that if every ordinal of $$M$$ is definable in $$M$$, then every ordinal is fresh. More interestingly, even models with undefinable ordinals can have only fresh ordinals. (I think Con(ZFC) does not suffice to build a model of ZFC whose fresh ordinals form a set.) To avoid these examples, assume from now on that $$(M,S)$$ satisfies the Axiom of Replacement where $$S$$ is the satisfaction predicate of $$M$$.

The fresh ordinals $$F$$ then form a set in $$M$$. Moreover, $$(\mathcal T(\alpha))_{\alpha \in F}$$ is definable in $$M$$ from any sufficiently large ordinal $$\kappa$$ such that $$V_\kappa^M\prec M$$ (and there are cofinally many). It follows that $$(\mathcal T(\alpha))_{\alpha \in F}$$ belongs to $$\text{HOD}^M$$, which I will denote by $$H$$. Therefore $$F$$, has cardinality at most $$\mathfrak c$$ in $$H$$. For any ordinal $$\alpha < \mathfrak{c}^H$$, the $$\alpha$$-th real in the canonical wellorder of $$H$$ is $$\Sigma_2$$-definable from $$\alpha$$ and hence is recoverable from $$\mathcal T(\alpha)$$. It follows that $$\alpha$$ is fresh. This shows $$\mathfrak{c}^H\subseteq F$$. Also $$\mathfrak{c}^H\in F$$, being definable in $$M$$. So the ordertype of $$F$$ is strictly between $$\mathfrak{c}^H$$ and $$\mathfrak{c}^{+H}$$.

Now it is clear that $$F$$ is uncountable if and only if $$M$$ thinks $$H$$ contains uncountably many ordinal definable reals, which of course depends on the choice of $$M$$. The cardinality of $$F$$ is larger than $$\aleph_1$$ if and only if $$H$$ contains at least $$\aleph_2$$-many reals, which is independent of $$\neg\text{CH}$$.

Assuming Martin's Maximum, every subset of $$\omega$$ is coded into the pattern of stationary reflection for any infinite stationary partition of $$\{\alpha < \kappa : \text{cf}(\alpha) = \omega\}$$ where $$\kappa\geq \omega_2$$. (This is part of the proof of Theorem 10 in Foreman-Magidor-Shelah's Martin's Maximum, saturated ideals, and nonregular ultrafilters.) So assuming $$M$$ satisfies MM, large cardinals, and Woodin's HOD Hypothesis, every real is in $$H$$. Therefore it is conceivable that your question decided by the conjunction of forcing axioms and large cardinals, but this is open...

For the second question, note that by the pigeonhole principle there is an unbounded class $$C\subseteq M$$ of ordinals such that for all $$\kappa_0,\kappa_1\in C$$, the theory of $$\kappa_0$$ in $$(M,S)$$ with real parameters is the same as that of $$\kappa_1$$. Let $$\langle-,-\rangle$$ be an $$M$$-definable pairing function. It follows that $$\mathcal T\langle\kappa_0,\alpha\rangle$$ is equal to $$\mathcal T\langle\kappa_1,\alpha\rangle$$ for all $$\alpha < \mathfrak{c}^H$$, since $$\alpha$$ is interdefinable over $$M$$ with the $$\alpha$$-th real in the canonical wellorder of $$H$$ and $$\mathcal T\langle\kappa_0,\alpha\rangle$$ depends only on the theory of $$\kappa_0$$ and $$\alpha$$ in $$(M,S)$$. But similarly, for each $$\kappa\in C$$, the $$\mathcal T\langle\kappa,\alpha\rangle$$ are distinct for $$\alpha < \mathfrak{c}^{H}$$; let $$\xi_{\alpha}$$ be the least ordinal $$\xi$$ such that $$\mathcal T(\xi) = \mathcal T\langle\kappa,\alpha\rangle$$. Letting $$E\subseteq F$$ be the set of ordinals $$\alpha$$ such that $$S(\alpha)$$ a proper class in $$M$$, it follows that $$\{\xi_\alpha : \alpha < \mathfrak{c}^{H}\}\subseteq E$$, so $$E$$ has cardinality $$\mathfrak{c}$$ in $$H$$. So much of what was said above applies to $$E$$ as well.

• I don't see how $\mathcal{T}(\alpha)$ is Turing equivalent to the $1$-type of $\alpha$: this doesn't seem to be true for $\alpha = 1$, for instance (the $1$-types of $0$ and $1$ are Turing equivalent, but $\mathcal{T}(1)$ is not computable from $\mathcal{T}(0)$).
– zeb
Feb 8 at 17:29
• No, you're right. I confused myself! Let me fix it up Feb 8 at 18:36
• Should be fixed now Feb 8 at 18:49
• This is a remarkably complete answer!
– zeb
Feb 8 at 22:34
• Wow, what an amazing answer. Martin's Maximum... was not expecting that.
– user141903
Feb 9 at 0:36