Skip to main content
realized that one of the questions was trivial
Source Link
zeb
  • 8.8k
  • 6
  • 37
  • 51

Apologies for asking so many questions at once. I'll be happy with any nontrivial results about the nature of the function $\mathcal{T}_X$$\mathcal{T}$ or the set of fresh ordinals $F_X$$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.

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

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.

Source Link
zeb
  • 8.8k
  • 6
  • 37
  • 51

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}_X$ or the set of fresh ordinals $F_X$.