FANDOM

10,612 Pages

Here we define notations for ordinals up to the proof theoretic ordinal for $$\Pi^1_1 - \text{TR}_0$$.

$$\theta$$ function up to $$\theta(\Omega_\omega,0)$$

We have already defined collapsing functions that take ordinals of cardinality $$\Omega$$ to large countable ordinals.  To get larger and larger countable ordinals, then, we merely need to define larger ordinals of cardinality $$\Omega$$.  Our notations already define ordinals up to $$\varepsilon_{\Omega+1}$$;  We can define larger uncountable ordinals using the Veblen function, Extended Veblen function, or the Schutte Klammersymbolen.  But our strongest notation for countable ordinals has been the collapsing functions themselves, so why not define a function that collapses to large ordinals of cardinality $$\Omega$$?  So we add $$\Omega_2$$, the next higher cardinal, to our notation, and collapse ordinals of cardinality $$\Omega_2$$ to ordinals of cardinality $$\Omega$$, which in turn collapse to large ordinals.  Then we can add $$\Omega_3$$, $$\Omega_4$$, etc.  So we get the following version of the $$\theta$$ function.  (again due to Feferman) $$\Omega_0$$ is defined to be $$0$$.

$$C_0 (\alpha, \beta) = \beta \cup \lbrace \Omega_\nu \rbrace , \nu \le \omega$$

$$C_{n+1} (\alpha, \beta) = \lbrace \gamma + \delta, \varphi(\gamma, \delta), \theta(\eta, \gamma) | \gamma, \delta, \eta \in C_n (\alpha, \beta); \eta < \alpha \rbrace$$

$$C (\alpha, \beta) = \bigcup_{n = 1}^{\infty} C_n (\alpha, \beta)$$

$$In (\alpha) = \lbrace \beta | \beta \notin C (\alpha, \beta) \rbrace$$

$$\theta (\alpha, \beta) =$$ the $$\beta$$th ordinal in $$In (\alpha)$$

The ordinal $$\theta(\Omega_\omega, 0)$$ is the proof-theoretic ordinal for $$\Pi^1_1 - \text{CA}_0$$.  The ordinal $$\theta(\varepsilon_{\Omega_\omega + 1}, 0)$$ is the Takeuti-Feferman-Buchholz ordinal.

$$\psi$$ function up to $$\psi_0(\Omega_\omega)$$

Wilfried Buchholz discovered that, using the $$\theta$$ function, one could generate a set of ordinals of the same order type as the full system by using +, $$\varphi$$, and $$\alpha, \nu \mapsto \theta(\alpha, \Omega_\nu)$$.  Using this idea, he defined the following simplified version of the $$\theta$$ function:

$$C_0 (\nu, \alpha) = \Omega_\nu \cup \lbrace 0 \rbrace$$

$$C_{n+1} (\nu, \alpha) = \lbrace \beta + \gamma, \varphi(\beta, \gamma), \psi_\mu(\delta) | \beta, \gamma, \delta \in C_n (\nu, \alpha); \delta < \alpha; \nu \le \mu \le \omega \rbrace$$

$$C (\nu, \alpha) = \bigcup_{n = 1}^{\infty} C_n (\nu,\alpha)$$

$$\psi_\nu (\alpha) = \min \lbrace \beta | \beta \notin C(\nu,\alpha) \rbrace$$

Note that, unlike the $$\theta$$ function, it is not enough to merely add the larger cardinals $$\Omega_\nu$$ to the notation;  one must define additional functions $$\psi_\nu$$ for $$\nu > 0$$ in order to get collapsing at the higher stages.  For $$\theta$$, we automatically get collapsing at higher stages because $$\theta(\alpha, \beta)$$ can have arbitrary cardinality.

Buchholz proved that $$\psi_0 (\varepsilon_{\Omega_\nu + 1}) = \theta (\varepsilon_{\Omega_\nu + 1}, 0)$$ for $$1 \le \nu \le \omega$$.  It follows that $$\psi_0 (\Omega_{\omega}) = \theta (\Omega_{\omega}) =$$ the proof theoretic ordinal of $$\Pi^1_1 - \text{CA}_0$$.

$$\vartheta$$ function up to $$\vartheta(\Omega_\omega)$$

A more modern version is the $$\vartheta$$ function, defined as:

$$C_0 (\nu, \alpha, \beta) = \beta \cup \Omega_\nu \cup \lbrace 0 \rbrace$$

$$C_{n+1} (\nu, \alpha, \beta) = \lbrace \gamma + \delta, \varphi(\gamma, \delta), \vartheta_\mu(\eta) | \gamma, \delta, \eta \in C_n (\nu, \alpha, \beta); \eta < \alpha; \nu \le \mu \le \omega \rbrace$$

$$C (\nu, \alpha, \beta) = \bigcup_{n = 1}^{\infty} C_n (\nu, \alpha, \beta)$$

$$\vartheta_\nu (\alpha) = \min (\lbrace \beta < \Omega_{\nu + 1} | C(\nu, \alpha, \beta) \cap \Omega_{\nu+1} \subseteq \beta \wedge \alpha \in C(\nu, \alpha, \beta) \rbrace \cup \lbrace \Omega_{\nu+1} \rbrace)$$

Like before, the $$\vartheta_\nu$$ functions differ from the $$\theta$$ and $$\psi$$ functions in that, rather than stabilizing at certain ordinals, it skips over those ordinals and continues increasing.  So the $$\vartheta_\nu$$ functions are 1-1 functions for each $$\nu$$.

We again have $$\vartheta_0 (\varepsilon_{\Omega_\nu + 1}) = \theta (\varepsilon_{\Omega_\nu + 1}, 0)$$ for $$1 \le \nu \le \omega$$ and $$\vartheta_0 (\Omega_{\omega}) = \theta (\Omega_{\omega}) =$$ the proof theoretic ordinal of $$\Pi^1_1 - \text{CA}_0$$.

$$\theta$$ function up to $$\theta(\Omega_{\Omega_{\Omega_\ldots}},0)$$

We can extend the notation much further by allowing any ordinal in our notation as a subscript of $$\Omega$$. So we simply add $$\alpha \mapsto \Omega_{\alpha}$$ to our list of closure functions:

$$C_0 (\alpha, \beta) = \beta \cup \lbrace 0 \rbrace$$

$$C_{n+1} (\alpha, \beta) = \lbrace \gamma + \delta, \varphi(\gamma, \delta), \Omega_{\gamma}, \theta(\eta, \gamma) | \gamma, \delta, \eta \in C_n (\alpha, \beta); \eta < \alpha \rbrace$$

$$C (\alpha, \beta) = \bigcup_{n = 1}^{\infty} C_n (\alpha, \beta)$$

$$In (\alpha) = \lbrace \beta | \beta \notin C (\alpha, \beta) \rbrace$$

$$\theta (\alpha, \beta) =$$ the $$\beta$$th ordinal in $$In (\alpha)$$

Although the change is relatively simple, it represents a great increase in the ordinals that we can denote: instead of being limited to $$\Omega_\omega$$, we can define cardinals $$\Omega_\alpha$$ for any ordinal $$\alpha$$ in our notation. So for example $$\theta(\Omega_{\Omega}, \beta)$$ is the $$\beta$$th ordinal in the set $$\lbrace \gamma | \theta(\Omega_{\gamma}, 0) = \gamma \rbrace$$.

$$\vartheta$$ function up to $$\vartheta(\Omega_{\Omega_{\Omega_\ldots}})$$

We can define similar extensions to the $$\psi$$ and $$\vartheta$$ functions, for example:

$$C_0 (\nu, \alpha, \beta) = \beta \cup \Omega_\nu \cup \lbrace 0 \rbrace$$

$$C_{n+1} (\nu, \alpha, \beta) = \lbrace \gamma + \delta, \varphi(\gamma, \delta), \Omega_{\gamma}, \vartheta_\gamma(\eta) | \gamma, \delta, \eta \in C_n (\nu, \alpha, \beta); \eta < \alpha \rbrace$$

$$C (\nu, \alpha, \beta) = \bigcup_{n = 1}^{\infty} C_n (\nu, \alpha, \beta)$$

$$\vartheta_\nu (\alpha) = \min (\lbrace \beta < \Omega_{\nu + 1} | C(\nu, \alpha, \beta) \cap \Omega_{\nu+1} \subseteq \beta \wedge \alpha \in C(\nu, \alpha, \beta) \rbrace \cup \lbrace \Omega_{\nu+1} \rbrace)$$

Standard form for ordinals up to $$\vartheta(\Omega_{\Omega_{\Omega_\ldots}})$$

Here we define standard form for ordinals up to $$\vartheta(\Omega_{\Omega_{\Omega_\ldots}})$$; this will be similar to the definition in the last article.

The standard form for 0 is 0.

If $$\alpha$$ is not additively principal, then the standard form for $$\alpha$$ is

$$\alpha = \alpha_1 + \alpha_2 + \ldots + \alpha_n$$,

where the $$\alpha_i$$ are principal ordinals with $$\alpha_1 \ge \alpha_2 \ge \ldots \ge \alpha_n$$, and the $$\alpha_i$$ are expressed in standard form.

If $$\alpha$$ is an additively principal ordinal but not a strongly critical ordinal, then the standard form for $$\alpha$$ is

$$\alpha = \phi(\beta, \gamma)$$ where $$\gamma < \alpha$$ where $$\beta$$ and $$\gamma$$ are expressed in standard form.

If $$\alpha$$ is of the form $$\Omega_\beta$$, then $$\Omega_\beta$$ is the standard form for $$\alpha$$.

If $$\alpha$$ is a strongly critical ordinal but not of the form $$\Omega_\beta$$, then $$\alpha$$ is expressible in the form $$\vartheta_\nu(\gamma)$$. Then the standard form for $$\alpha$$ is

$$\alpha = \vartheta_\nu(\gamma)$$

where $$\gamma$$ and $$\nu$$ are expressed in standard form.

Fundamental sequences up to $$\vartheta(\Omega_{\Omega_{\Omega_\ldots}})$$

We define fundamental sequences for countable limit ordinals going up to $$\vartheta(\Omega_{\Omega_{\Omega_\ldots}})$$. In order to do so, we will define fundamental sequences for all ordinals denotable by the $$\theta$$ notation, where "fundamental sequence for $$\alpha$$" means a well-ordered set of order type equal to the cofinality of $$\alpha$$.

We assume that the ordinal $$\alpha$$ is expressed in standard form.

0 has cofinality 0 and has fundamental sequence the empty set.

$$\varphi(0,0) = 1$$ has cofinality 1 and fundamental sequence $$\lbrace 0 \rbrace$$.

If $$\alpha = \alpha_1 + \alpha_2 + \ldots + \alpha_m$$, then

cof $$(\alpha)$$ = cof $$(\alpha_n)$$ and

$$\alpha [\eta] = \alpha_1 + \alpha_2 + \ldots + \alpha_m [\eta]$$

If $$\alpha = \varphi(\beta, \gamma)$$ and $$\gamma$$ is a limit ordinal then

cof $$(\alpha)$$ = cof $$(\gamma)$$ and

$$\alpha [\eta] = \varphi (\beta, \gamma[\eta])$$.

If $$\alpha = \varphi (0, \gamma + 1)$$ then

cof $$(\alpha) = \omega$$ and

$$\alpha [\eta] = \varphi (0, \gamma) + \varphi(0, \gamma) + \ldots + \varphi(0, \gamma)$$ ($$\eta$$ occurrences of $$\varphi(0, \gamma)$$)

If $$\alpha = \varphi (\beta + 1,0)$$ then

cof $$(\alpha) = \omega$$ and

$$\alpha [0] = 0$$

$$\alpha [\eta+1] = \varphi (\beta, \alpha [\eta])$$

If $$\alpha = \varphi (\beta + 1, \gamma + 1)$$ then

cof $$(\alpha) = \omega$$ and

$$\alpha [0] = \varphi (\beta + 1, \gamma) + 1$$

$$\alpha [\eta + 1] = \varphi (\beta, \alpha [\eta])$$

If $$\beta$$ is a limit ordinal and $$\alpha = \varphi(\beta, 0)$$ then

cof $$(\alpha)$$ = cof $$(\beta)$$ and

$$\alpha [\eta] = \varphi (\beta [\eta], 0)$$

If $$\beta$$ is a limit ordinal and $$\alpha = \varphi(\beta, \gamma + 1)$$ then

cof $$(\alpha)$$ = cof $$(\beta)$$ and

$$\alpha [\eta] = \varphi (\beta [\eta], \varphi(\beta, \gamma) + 1)$$

If $$\alpha = \Omega_{\beta + 1}$$ then

cof $$(\alpha) = \Omega_{\beta + 1}$$ and

$$\alpha [\eta] = \eta$$

If $$\alpha = \Omega_\beta$$ where $$\beta$$ is a limit ordinal then

cof $$(\alpha) =$$ cof $$(\beta)$$ and

$$\alpha [\eta] = \Omega_{\beta [\eta]}$$

If $$\alpha = \vartheta_\nu (\beta + 1)$$ then

cof $$(\alpha) = \omega$$ and

$$\alpha [0] = \vartheta_\nu (\beta) + 1$$

$$\alpha [\eta + 1] = \varphi (\alpha [\eta], 0)$$

If $$\alpha = \vartheta_\nu (\beta)$$ and $$\omega \le$$ cof $$(\beta) \le \Omega_\nu$$ then

cof $$(\alpha) =$$ cof $$(\beta)$$ and

$$\alpha [\eta] = \vartheta_\nu (\beta [\eta])$$

If $$\alpha = \vartheta_\nu (\beta)$$ and cof $$(\beta) = \Omega_{\mu + 1} > \Omega_\nu$$ then

Cof $$(\alpha) = \omega$$ and

$$\alpha[\eta] = \vartheta_\nu (\beta [\gamma [\eta]])$$

$$\gamma [0] = \Omega_\mu$$

$$\gamma [\eta + 1] = \vartheta_\mu (\beta [\gamma[\eta]])$$

Phew!