The meaning of $L_{\alpha}$ and $L_{\alpha}[x_1, x_2, \ldots, x_{n-1}, x_n]$ notations in relation to Infinite Time Turing Machines

logicnotationordinalsset-theory

I thought that the $L_{\alpha}$ notation denotes a set of reals that can occur on the output tape at stage $\beta$, where $\beta$ is any ordinal less than $\alpha$ and the input is an arbitrary real.

Similarly, the $L_{\alpha}[x_1, x_2, \ldots, x_{n-1}, x_n]$ notation would denote a set of reals that can occur on the output tape at stage $\beta$, where $\beta$ is any ordinal less than $\alpha$, assuming that an Infinite Time Turing Machine interprets the input as $n$ separate reals and $x_i$ denotes an $i$-th real.

But then I read that the recognizable closure of Infinite Time Turing Machines is equal to $L_{\sigma}$ (see Lemma 3.2 in the paper “Recognizable sets and Woodin cardinals: Computation beyond the constructible universe”), where $\sigma$ is a particular countable ordinal.

And here my understanding seems to contradict the intended meaning of the notation: assume that the input is a real that encodes any well-order $W$ of order-type greater than $\sigma$ and consider an Infinite Time Turing Machine that checks if $W$ is, in fact, a well-order. This machine will halt at stage $\tau$, where $\tau$ is greater than $\sigma$.

What is the meaning of $L_{\alpha}$ and $L_{\alpha}[x_1, x_2, \ldots, x_{n-1}, x_n]$ notations in relation to Infinite Time Turing Machines?

Best Answer

The $L_\alpha$s are levels of the $L$-hierarchy, which is defined as follows:

  • $L_0=\emptyset$.

  • For $\lambda$ a limit ordinal, $L_\lambda=\bigcup_{\beta<\lambda}L_\beta$.

  • $L_{\alpha+1}$ is the set of all $X\subseteq L_\alpha$ such that $X$ is definable (with parameters) in the structure $(L_\alpha; \in)$.

Note that this definition has nothing to do with ITTMs a priori; all interactions between the two notions are theorems.

"$L$" meanwhile refers to the class $\bigcup_{\alpha\in Ord}L_\alpha$. Note that this is somewhat similar to the $V$-hierarchy, the difference being the much more technical (although ultimately better-behaved) successor step. Also, note that elements of $L_\alpha$s are in general not reals, or sets of ordinals, or anything else particularly nice; for example, $\{\{\{\{\{\{0\}\}\}\}\}\}$ is an element of $L_8$.

It's a good easy exercise to check each of the following:

  • Whenever $\alpha<\beta$ we have both $L_\alpha\in L_\beta$ and $L_\alpha\subseteq L_\beta$.

  • Each $L_\alpha$ (and hence $L$ itself) is transitive.

  • $\alpha\subseteq L_\alpha$ for all ordinals $\alpha$.

  • We have $\vert L_\alpha\vert=\vert\alpha\vert$ for infinite $\alpha$.

Some fundamental, but not-at-all-obvious, facts about the $L$-hierarchy include:

  • Definability: the relation "$x\in L_\alpha$" (and hence the whole class $L$) is definable in the language of set theory.

  • Basic theory: the class structure $(L;\in)$ satisfies ZFC.

  • Condensation: if $M\preccurlyeq L_\beta$ for some $\beta$ then the Mostowski collapse of $M$ is equal to $L_\alpha$ for some $\alpha$. (Actually "$\preccurlyeq$" is overkill here, we just need "$\preccurlyeq_1$," but that's a bit more technical.) While opaque at first this is extremely powerful. For example, it lets us prove that $L\models GCH$ as follows:

    • Fix an infinite $L$-cardinal $\kappa$ and a set $X\in\mathcal{P}(\kappa)^L$; we want to show $X\in L_{(\kappa^+)^L}$.

    • By Lowenheim-Skolem, we get an elementary substructure $M$ of $L_\theta$ (with $\theta$ "large enough") such that $\vert M\vert=\kappa$, $L_\kappa\subseteq M$, and $X\in M$.

    • Let $m$ be the Mostowski collapse map of $M$. By Condensation we have $m: M\cong L_\beta$ for some $\beta$. Then by choice of $M$ we have $\beta<(\kappa^+)^L$ and $m(X)=X$, but this means $X\in L_{(\kappa^+)^L}$.

Similarly, for $x_1,..., x_n$ arbitrary sets (usually sets of ordinals), we can define the levels $L_\alpha[x_1,...,x_n]$ of the "relativized" $L$-hierarchy, and the "relativized" constructible universe $L[x_1,...,x_n]$, as above; the only change is in the successor step, where in order to compute $L_{\alpha+1}$ we look at the more complicated structure $$(L_\alpha; \in, x_1\cap L_\alpha,...,x_n\cap L_\alpha)$$ (that is, we can "identify $x_i$-ness").

Incidentally, we do not in general have $x\subseteq L[x]$ or $x\in L[x]$; for example, it's a good exercise to check that $L[\mathbb{R}]=L$ (basically, we can already tell whether something is a real number), so as long as $\mathbb{R}\not\subseteq L$ we'll have $\mathbb{R}\not\subseteq L[\mathbb{R}]$ and hence by transitivity of $L[\mathbb{R}]$ we won't have $\mathbb{R}\in L[\mathbb{R}]$ either. The notation "$L(x_1,...,x_n)$" refers to a different construction which on the plus side avoids this issue but on the minus(?) side does not generally result in a model of ZFC, but merely ZF. However, we do have $L[x_1,...,x_n]=L(x_1,...,x_n)\supseteq\{x_1,...,x_n\}$ whenever $x_1,...,x_n$ are each sets of ordinals.

Jech's book has a lot of good material on $L$, $L[...]$, and $L(...)$. I personally prefer Devlin's book, but that has a huge caveat - there's a serious mistake in the book one has to work around. Specifically, the development of the theory "$BS$" in Devlin is fundamentally flawed. However, this doesn't affect any of the significant results, and in particular the development of the relativized $L$-hierarchy is fine (see this Mathoverflow question for a description of the error, and how to address it).

Related Question