\documentclass[12pt,titlepage]{article} \usepackage{amsmath} \usepackage{mathrsfs} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} \usepackage{mathtools} \usepackage{graphicx} \usepackage{color} \usepackage{ucs} \usepackage[utf8x]{inputenc} \usepackage{xparse} \usepackage{hyperref} %----Macros---------- % % Unresolved issues: % % \righttoleftarrow % \lefttorightarrow % % \color{} with HTML colorspec % \bgcolor % \array with options (without options, it's equivalent to the matrix environment) % Of the standard HTML named colors, white, black, red, green, blue and yellow % are predefined in the color package. Here are the rest. \definecolor{aqua}{rgb}{0, 1.0, 1.0} \definecolor{fuschia}{rgb}{1.0, 0, 1.0} \definecolor{gray}{rgb}{0.502, 0.502, 0.502} \definecolor{lime}{rgb}{0, 1.0, 0} \definecolor{maroon}{rgb}{0.502, 0, 0} \definecolor{navy}{rgb}{0, 0, 0.502} \definecolor{olive}{rgb}{0.502, 0.502, 0} \definecolor{purple}{rgb}{0.502, 0, 0.502} \definecolor{silver}{rgb}{0.753, 0.753, 0.753} \definecolor{teal}{rgb}{0, 0.502, 0.502} % Because of conflicts, \space and \mathop are converted to % \itexspace and \operatorname during preprocessing. % itex: \space{ht}{dp}{wd} % % Height and baseline depth measurements are in units of tenths of an ex while % the width is measured in tenths of an em. \makeatletter \newdimen\itex@wd% \newdimen\itex@dp% \newdimen\itex@thd% \def\itexspace#1#2#3{\itex@wd=#3em% \itex@wd=0.1\itex@wd% \itex@dp=#2ex% \itex@dp=0.1\itex@dp% \itex@thd=#1ex% \itex@thd=0.1\itex@thd% \advance\itex@thd\the\itex@dp% \makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}} \makeatother % \tensor and \multiscript \makeatletter \newif\if@sup \newtoks\@sups \def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}% \def\reset@sup{\@supfalse\@sups={}}% \def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else% \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}% \else \append@sup#2 \@suptrue \fi% \expandafter\mk@scripts\fi} \def\tensor#1#2{\reset@sup#1\mk@scripts#2_/} \def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2% \reset@sup\mk@scripts#3_/} \makeatother % \slash \makeatletter \newbox\slashbox \setbox\slashbox=\hbox{$/$} \def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$} \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa \copy\slashbox \kern-\@tempdima \box\@tempboxa} \def\slash{\protect\itex@pslash} \makeatother % math-mode versions of \rlap, etc % from Alexander Perlis, "A complement to \smash, \llap, and lap" % http://math.arizona.edu/~aprl/publications/mathclap/ \def\clap#1{\hbox to 0pt{\hss#1\hss}} \def\mathllap{\mathpalette\mathllapinternal} \def\mathrlap{\mathpalette\mathrlapinternal} \def\mathclap{\mathpalette\mathclapinternal} \def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}} \def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}} \def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}} % Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2} \let\oldroot\root \def\root#1#2{\oldroot #1 \of{#2}} \renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}} % Manually declare the txfonts symbolsC font \DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n} \SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n} \DeclareFontSubstitution{U}{txsyc}{m}{n} % Manually declare the stmaryrd font \DeclareSymbolFont{stmry}{U}{stmry}{m}{n} \SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n} % Manually declare the MnSymbolE font \DeclareFontFamily{OMX}{MnSymbolE}{} \DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n} \SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n} \DeclareFontShape{OMX}{MnSymbolE}{m}{n}{ <-6> MnSymbolE5 <6-7> MnSymbolE6 <7-8> MnSymbolE7 <8-9> MnSymbolE8 <9-10> MnSymbolE9 <10-12> MnSymbolE10 <12-> MnSymbolE12}{} % Declare specific arrows from txfonts without loading the full package \makeatletter \def\re@DeclareMathSymbol#1#2#3#4{% \let#1=\undefined \DeclareMathSymbol{#1}{#2}{#3}{#4}} \re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46} \re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12} \re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64} \re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6} \re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77} \re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77} \makeatother % \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE \makeatletter \def\Decl@Mn@Delim#1#2#3#4{% \if\relax\noexpand#1% \let#1\undefined \fi \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}} \def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}} \def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}} \Decl@Mn@Open{\llangle}{mnomx}{'164} \Decl@Mn@Close{\rrangle}{mnomx}{'171} \Decl@Mn@Open{\lmoustache}{mnomx}{'245} \Decl@Mn@Close{\rmoustache}{mnomx}{'244} \makeatother % Widecheck \makeatletter \DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}} \def\@widecheck#1#2{% \setbox\z@\hbox{\m@th$#1#2$}% \setbox\tw@\hbox{\m@th$#1% \widehat{% \vrule\@width\z@\@height\ht\z@ \vrule\@height\z@\@width\wd\z@}$}% \dp\tw@-\ht\z@ \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@ \setbox\tw@\hbox{% \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box \tw@}}}% {\ooalign{\box\tw@ \cr \box\z@}}} \makeatother % \mathraisebox{voffset}[height][depth]{something} \makeatletter \NewDocumentCommand\mathraisebox{moom}{% \IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{% \IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}% }{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}% \mathpalette\@temp{#4}} \makeatletter % udots (taken from yhmath) \makeatletter \def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.} \mkern2mu\raise4\p@\hbox{.}\mkern1mu \raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}} \makeatother %% Fix array \newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}} %% \itexnum is a noop \newcommand{\itexnum}[1]{#1} %% Renaming existing commands \newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}} \newcommand{\widevec}{\overrightarrow} \newcommand{\darr}{\downarrow} \newcommand{\nearr}{\nearrow} \newcommand{\nwarr}{\nwarrow} \newcommand{\searr}{\searrow} \newcommand{\swarr}{\swarrow} \newcommand{\curvearrowbotright}{\curvearrowright} \newcommand{\uparr}{\uparrow} \newcommand{\downuparrow}{\updownarrow} \newcommand{\duparr}{\updownarrow} \newcommand{\updarr}{\updownarrow} \newcommand{\gt}{>} \newcommand{\lt}{<} \newcommand{\map}{\mapsto} \newcommand{\embedsin}{\hookrightarrow} \newcommand{\Alpha}{A} \newcommand{\Beta}{B} \newcommand{\Zeta}{Z} \newcommand{\Eta}{H} \newcommand{\Iota}{I} \newcommand{\Kappa}{K} \newcommand{\Mu}{M} \newcommand{\Nu}{N} \newcommand{\Rho}{P} \newcommand{\Tau}{T} \newcommand{\Upsi}{\Upsilon} \newcommand{\omicron}{o} \newcommand{\lang}{\langle} \newcommand{\rang}{\rangle} \newcommand{\Union}{\bigcup} \newcommand{\Intersection}{\bigcap} \newcommand{\Oplus}{\bigoplus} \newcommand{\Otimes}{\bigotimes} \newcommand{\Wedge}{\bigwedge} \newcommand{\Vee}{\bigvee} \newcommand{\coproduct}{\coprod} \newcommand{\product}{\prod} \newcommand{\closure}{\overline} \newcommand{\integral}{\int} \newcommand{\doubleintegral}{\iint} \newcommand{\tripleintegral}{\iiint} \newcommand{\quadrupleintegral}{\iiiint} \newcommand{\conint}{\oint} \newcommand{\contourintegral}{\oint} \newcommand{\infinity}{\infty} \newcommand{\bottom}{\bot} \newcommand{\minusb}{\boxminus} \newcommand{\plusb}{\boxplus} \newcommand{\timesb}{\boxtimes} \newcommand{\intersection}{\cap} \newcommand{\union}{\cup} \newcommand{\Del}{\nabla} \newcommand{\odash}{\circleddash} \newcommand{\negspace}{\!} \newcommand{\widebar}{\overline} \newcommand{\textsize}{\normalsize} \renewcommand{\scriptsize}{\scriptstyle} \newcommand{\scriptscriptsize}{\scriptscriptstyle} \newcommand{\mathfr}{\mathfrak} \newcommand{\statusline}[2]{#2} \newcommand{\tooltip}[2]{#2} \newcommand{\toggle}[2]{#2} % Theorem Environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{prop}{Proposition} \newtheorem{cor}{Corollary} \newtheorem*{utheorem}{Theorem} \newtheorem*{ulemma}{Lemma} \newtheorem*{uprop}{Proposition} \newtheorem*{ucor}{Corollary} \theoremstyle{definition} \newtheorem{defn}{Definition} \newtheorem{example}{Example} \newtheorem*{udefn}{Definition} \newtheorem*{uexample}{Example} \theoremstyle{remark} \newtheorem{remark}{Remark} \newtheorem{note}{Note} \newtheorem*{uremark}{Remark} \newtheorem*{unote}{Note} %------------------------------------------------------------------- \begin{document} %------------------------------------------------------------------- \section*{countable ordinal} \hypertarget{context}{}\subsubsection*{{Context}}\label{context} \hypertarget{foundations}{}\paragraph*{{Foundations}}\label{foundations} [[!include foundations - contents]] \hypertarget{mathematics}{}\paragraph*{{Mathematics}}\label{mathematics} [[!include mathematicscontents]] \hypertarget{contents}{}\section*{{Contents}}\label{contents} \noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak \noindent\hyperlink{definitions}{Definitions}\dotfill \pageref*{definitions} \linebreak \noindent\hyperlink{fixed_points_and_the_veblen_hierarchy}{Fixed points and the Veblen hierarchy}\dotfill \pageref*{fixed_points_and_the_veblen_hierarchy} \linebreak \noindent\hyperlink{ordinal_notations_and_the_fefermanschtte_ordinal}{Ordinal notations and the Feferman-Sch\"u{}tte ordinal}\dotfill \pageref*{ordinal_notations_and_the_fefermanschtte_ordinal} \linebreak \noindent\hyperlink{fundamental_sequences_and_the_bachmannhoward_ordinal}{Fundamental sequences and the Bachmann-Howard ordinal}\dotfill \pageref*{fundamental_sequences_and_the_bachmannhoward_ordinal} \linebreak \noindent\hyperlink{fastgrowing_functions_on_}{Fast-growing functions on $\mathbb{N}$}\dotfill \pageref*{fastgrowing_functions_on_} \linebreak \noindent\hyperlink{recursive_ordinals}{Recursive ordinals}\dotfill \pageref*{recursive_ordinals} \linebreak \noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak \noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak \hypertarget{idea}{}\subsection*{{Idea}}\label{idea} In [[classical mathematics]], a \emph{countable} [[ordinal]] is the [[order type]] of a [[well ordering|well-ordered]] [[set]] whose [[cardinality]] is countable (i.e., either [[finite set|finite]] or [[natural numbers|denumerable]]). Countable ordinals play an important role in [[recursion]] theory, [[computability theory]], and in [[proof theory]], where they are used for example to measure the [[consistency]] strength of formal [[theories]] via [[ordinal analysis]]. They also play a role in [[philosophy of mathematics]], for example to discuss what it means for a notion to be ``[[predicativity|predicative]]''. \hypertarget{definitions}{}\subsection*{{Definitions}}\label{definitions} As indicated above, countable ordinals can be defined structurally as countable well-ordered sets (or ``[[wosets]]''). As is the case with any ordered set, a woset $W$ can be regarded as a [[coalgebra over an endofunctor|coalgebra]] over the covariant [[power-set]] functor, \begin{displaymath} \theta: W \to P(W) \end{displaymath} \begin{displaymath} \, \end{displaymath} \begin{displaymath} x \mapsto \{y: y \lt x\}. \end{displaymath} A coalgebra map $f: W \to W'$ between wosets, aka a [[simulation]], amounts to an inclusion of the domain as an initial segment of the codomain. The [[category]] of countable wosets and simulations, thus ordered by inclusion, is a [[preorder]] and in fact equivalent to a woset. In [[material set theory]], this woset is often identified with the [[first uncountable ordinal]] (well-ordered set under the membership relation), often denoted $\omega_1$. [[structural set theory|Structurally]], we can define $\omega_1$ up to [[isomorphism]] as a [[skeleton]] of the category of countable ordinals, and so the study of countable ordinals becomes a study of the order structure of $\omega_1$. This $\omega_1$ has no top element (of course not: otherwise $\omega_1$ would be a countable ordinal), and much of the interest and fun of the subject lies in playing the childhood game of seeing who can name the bigger number, or in this case the bigger countable ordinal. A key fact is that $\omega_1$ is countably cocomplete, and therefore behaves like a self-contained [[universe]] with respect to countably cocontinuous operations. There is quite a lot of scope in what one can build up to using such operations. After playing the larger ordinal game for a while, and becoming impressed by the sizes of ordinals one can define -- while recognizing at the same time that one is ``never getting anywhere'' relative to $\omega_1$ itself -- it is hard not to become awestruck by the staggering immensity of $\omega_1$. Anyone who is unimpressed by the size of large countable ordinals has almost surely never seriously played with them. For that matter, people who are unimpressed by large \emph{finite} numbers have probably never played around with them either, or at least not all that imaginatively! (And interestingly, one can use large countable ordinals reflectively to construct enormous integers, or one can use large [[uncountable ordinals]] reflectively to construct enormous countable ordinals.) \hypertarget{fixed_points_and_the_veblen_hierarchy}{}\subsection*{{Fixed points and the Veblen hierarchy}}\label{fixed_points_and_the_veblen_hierarchy} Here we discuss the use of [[fixed point]] theory in describing the lower stages of the Veblen hierarchies of countable ordinals, which will lead up to the Feferman-Sch\"u{}tte ordinal. We freely allow ourselves to reason classically and use the [[principle of excluded middle]]. The ordinal $\omega_1$ is countably [[cocomplete category|cocomplete]], and we are primarily interested in functors or order-preserving maps $f: \omega_1 \to \omega_1$ that preserve [[colimits]] of countable (finite or denumerable) diagrams -- or countable chains, without loss of generality. We'll call such maps \emph{continuous}, for short. If $x \leq f(x)$ for all $x \in \omega_1$, then we say that $f$ is \emph{inflationary}. Preservation of colimits of finite nonempty chains comes for free, so we can ignore that. The colimit of the empty chain is the bottom element $0$, and we will make a point of including preservation of that. The first result is a baby form of a general theorem due to [[Adamek|Adámek]] on [[initial algebras of endofunctors]]. \begin{prop} \label{fix}\hypertarget{fix}{} Suppose $f: \omega_1 \to \omega_1$ is inflationary and continuous. Then every $x \in \omega_1$ has an upper bound that is a fixed point under $f$. \end{prop} \begin{proof} For any $x$, the colimit $x'$ of $x \leq f(x) \leq f^2(x) \leq \ldots$ exists, and since $f$ preserves countable colimits, $x'$ is a fixed point of $f$. \end{proof} \begin{lemma} \label{}\hypertarget{}{} If $f: \omega_1 \to \omega_1$ is order-preserving and satisfies $f(\beta) = \sup \{f(\alpha): \alpha \lt \beta\}$ for all limit (i.e., non-successor) ordinals $\beta$, then $f$ is continuous. \end{lemma} The converse of this result is trivially true. \begin{proof} For the case $\beta = 0$, the set $\{f(\alpha): \alpha \lt \beta\}$ is empty and thus has $0$ as its supremum, so $f(0) = 0$. Suppose that $\beta$ is the colimit of a chain $x_1 \leq x_2 \leq \ldots$ with countably infinite image. Then this chain is [[cofinal functor|cofinal]] in the set $\{\alpha: \alpha \lt \beta\}$, and similarly $f(x_1) \leq f(x_2) \leq \ldots$ is cofinal in $\{f(\alpha): \alpha \lt \beta\}$. Therefore the colimit of this chain is the same as the [[supremum]] of $\{f(\alpha): \alpha \lt \beta\}$, which is $f(\beta)$. \end{proof} \begin{prop} \label{}\hypertarget{}{} Suppose $f: \omega_1 \to \omega_1$ is inflationary and continuous. Define $f': \omega_1 \to \omega_1$ to be the function that takes each $x \in \omega_1$ to the least fixed point of $f$ that is greater than $f'(y)$ for all $y \lt x$. Then $f'$ is also inflationary and continuous. \end{prop} \begin{proof} By definition, $f'(y) \lt f'(x)$ whenever $y \lt x$, so $f'$ is order-preserving. That $f'$ is inflationary is proved by [[induction]]: given that $\alpha \leq f'(\alpha)$ for all $\alpha \lt \beta$, we have $\alpha \leq f'(\alpha) \lt f'(\beta)$ i.e. $\alpha \lt f'(\beta)$ for all $\alpha \lt \beta$, whence $\beta \leq f'(\beta)$. To prove $f'$ is continuous, let $\beta$ be a non-successor; by continuity of $f$ we have \begin{displaymath} f(\sup \{f'(\alpha): \alpha \lt \beta\}) = \sup \{f(f'(\alpha)): \alpha \lt \beta\} = \sup \{f'(\alpha): \alpha \lt \beta\} \end{displaymath} so that this supremum is in fact a fixed point of $f$, and thus the least fixed point of $f$ greater than every $f'(\alpha)$ for $\alpha \lt \beta$. It therefore follows by definition of $f'$ that \begin{displaymath} f'(\beta) = \sup \{f'(\alpha): \alpha \lt \beta\} \end{displaymath} and so, by the preceding lemma, $f'$ is continuous. \end{proof} \begin{defn} \label{}\hypertarget{}{} The \emph{Veblen hierarchy} is a family of functions $f_\alpha: \omega_1 \to \omega_1$, one for each $\alpha \in \omega_1$, defined as follows. \begin{itemize}% \item Define $f_0: \omega_1 \to \omega_1$ by $f_0(x) = \sup \{y+2: y \lt x\}$. \end{itemize} This is inflationary, and continuous by the lemma. \begin{itemize}% \item Then define $f_\alpha: \omega_1 \to \omega_1$ by $f_{\alpha + 1} = f_\alpha^'$ and $f_\beta = \sup_{\alpha \lt \beta} f_\alpha$ at limit ordinals $\beta \gt 0$. \end{itemize} By induction and the preceding proposition, $f_\alpha$ is inflationary and continuous at successor cardinals $\alpha$, and also at limit cardinals $\alpha \gt 0$ since countable colimits of inflationary and continuous maps are also inflationary and continuous. \end{defn} It is worth contemplating the growth of the first few $f_\alpha$. For $f_0$, we have $f_0(\alpha) = \alpha + 1$ if $\alpha$ is a successor, and $f_0(\alpha) = \alpha$ if $\alpha$ is a limit ordinal. This means that next we have $f_1(0) = 0$, $f_1(1) = \omega$, $f_1(2) = 2 \omega$, \ldots{}, $f_1(\omega) = \omega^2$, and so on. The first fixed point past $0$ is at $x = \omega^\omega$. Next, we have $f_2(0) = 0$, $f_2(1) = \omega^\omega$, $f_2(2) = \omega^{2\omega}$, \ldots{}, $f_2(\omega) = \omega^{\omega^2}$, and so on. The first fixed point past $0$ is the same as the first fixed point of $x \mapsto \omega^x$ (a countably iterated exponential stack), typically denoted as $\epsilon_0$. We pause to note that $\epsilon_0$ is sometimes considered the first reasonable thing to call a ``large countable ordinal''. An [[ordinal analysis]] first carried by by Gerhard Gentzen asserts, roughly speaking, that the consistency of [[Peano arithmetic]] is provable from [[primitive recursive arithmetic]] (which is weaker than PA) augmented by the principle of induction up to $\epsilon_0$. Pressing on, we have $f_3(0)= 0$, $f_3(1) = \epsilon_0$, $f_3(2) = \epsilon_1$ (the first fixed point of $x \mapsto \omega^x$ past $\epsilon_0$), and so on. The first fixed point past $0$ of $f_3$ is the limit of $\epsilon_0, \epsilon_{\epsilon_0}, \epsilon_{\epsilon_{\epsilon_0}}, \ldots$, sometimes indicated by an infinite descending stack of subscripts $\epsilon$. This ordinal is of size that far, far surpasses any human powers of visualization. And clearly we are only just getting started. Each successive $f_n(1)$ dwarfs its predecessor $f_{n-1}(1)$ to an indescribable degree. To speak nothing of $f_\omega(1)$, and so on. \hypertarget{ordinal_notations_and_the_fefermanschtte_ordinal}{}\subsection*{{Ordinal notations and the Feferman-Sch\"u{}tte ordinal}}\label{ordinal_notations_and_the_fefermanschtte_ordinal} Despite such colossal sizes, it is possible to effectively notate such ordinals using nothing more than finite binary trees, all the way up to the Feferman-Sch\"u{}tte ordinal, which seems to be the first of the ``large countable ordinals'' that the experts consider big enough to honor with human names. (There are others much further down the pike, such as the Bachmann-Howard ordinal or the considerably larger, almost godlike Church-Kleene ordinal.) Before introducing this, we prove the following lemmas. \begin{lemma} \label{}\hypertarget{}{} If $\alpha \lt \beta$, then every value $f_\beta(x)$ is a fixed point of $f_\alpha$. \end{lemma} \begin{proof} This is clear if $\alpha + 1 = \beta$. Suppose $f_\gamma(x)$ is a fixed point of $f_\alpha$ whenever $\alpha \lt \gamma \lt \beta$. If $\beta$ is a successor $\gamma + 1$, then we have \begin{displaymath} f_\beta(x) = f_\gamma(f_\beta(x)) = f_\alpha(f_\gamma(f_\beta(x))) = f_\alpha(f_\beta(x)), \end{displaymath} and if $\beta$ is a limit, then \begin{displaymath} f_\alpha(f_\beta(x)) = f_\alpha(\sup_{\alpha \lt \gamma \lt \beta} f_\gamma(x)) = \sup_{\alpha \lt \gamma \lt \beta} f_\alpha(f_\gamma(x)) = \sup_{\alpha \lt \gamma \lt \beta} f_\gamma(x) = f_\beta(x) \end{displaymath} which completes the proof. \end{proof} \begin{lemma} \label{inflat}\hypertarget{inflat}{} For all $y \in \omega_1$, we have $y \leq f_y(1)$. \end{lemma} \begin{proof} By induction. Suppose $\alpha \leq f_\alpha(1)$ for all $\alpha \lt \beta$. Since $1 \leq f_\beta(1)$, we have \begin{displaymath} \alpha \leq f_\alpha(1) \leq f_\alpha(f_\beta(1)) = f_\beta(1) \end{displaymath} since $f_\beta(1)$ is by the preceding lemma a fixed point of $f_\alpha$. Since $f_\beta(1)$ is both a limit ordinal and an upper bound for every $\alpha \lt \beta$, it follows that $\beta \leq f_\beta(1)$. \end{proof} Notice that by definition, $f_\beta(\gamma)$ is continuous in the argument $\beta$, since we defined $f_\beta = \sup_{\alpha \lt \beta} f_\alpha$ at limit ordinals $\beta$. Therefore the function $x \mapsto f_x(1)$ is inflationary (by lemma \ref{inflat}) and continuous. Applying proposition \ref{fix}, it has a least fixed point. This fixed point is called the \textbf{Feferman-Sch\"u{}tte ordinal}, denoted by $\Gamma_0$. \begin{theorem} \label{}\hypertarget{}{} If $\alpha \gt 0$ is less than $\Gamma_0$, then there exist $\beta, \gamma$, both less than $\alpha$, such that $\alpha = f_\beta(\gamma)$. \end{theorem} \begin{proof} If $\alpha$ is not a limit ordinal, then $\alpha = \gamma + 1$ and hence $\alpha = f_0(\gamma)$. Obviously $\alpha$ cannot be a value of $f_\beta$ for $\beta \gt 0$, since all such values are limit ordinals. If $\alpha$ is a limit ordinal and $\alpha \lt \Gamma_0$, then there is some $\beta \lt \alpha$ for which $\alpha$ is \emph{not} a fixed point of $f_\beta$. Otherwise we would have $f_\beta(\alpha) = \alpha$ for all $\beta \lt \alpha$, and this would force $f_\alpha(\alpha) = \alpha$ (by definition of $f_\alpha$). And in that case \begin{displaymath} \alpha \leq f_\alpha(1) \leq f_\alpha(\alpha) = \alpha \end{displaymath} so that $\alpha$ is a fixed point of $x \mapsto f_x(1)$, contradicting $\alpha \lt \Gamma_0$. Thus, for $\alpha$ a limit ordinal, take $\beta$ to be the least ordinal such that $\alpha \lt f_\beta(\alpha)$. Note that $\beta$ is a successor, $\beta = \beta' + 1$, because we have $\alpha = f_\gamma(\alpha)$ for any $\gamma \lt \beta$, and this would imply $\alpha = f_\beta(\alpha)$ if $\beta$ were a limit. We have $\alpha \leq f_\beta(\gamma)$ for some $\gamma \lt \alpha$ (for if $f_\beta(\gamma) \lt \alpha$ for all $\gamma \lt \alpha$, we could infer $\alpha$ is a fixed point of $f_\beta$). Let $\gamma$ be the least ordinal (less than $\alpha$) such that $\alpha \leq f_\beta(\gamma)$. Then in fact this last inequality is an equality. For suppose $\gamma = \delta + 1$; then by definition of $\gamma$, we have \begin{displaymath} f_\beta(\delta) = f_{\beta' + 1}(\delta) \lt \alpha \end{displaymath} and we also have that $\alpha = f_{\beta'}(\alpha)$ by definition of $\beta$. Since $f_\beta(\gamma) = f_{\beta' + 1}(\gamma) = f_{\beta' + 1}(\delta + 1)$ is by definition the least $f_{\beta'}$-fixpoint greater than $f_{\beta' + 1}(\delta)$, we immediately infer $f_\beta(\gamma) \leq \alpha$, as required. If on the other hand $\gamma$ is a limit, we have \begin{displaymath} f_\beta(\delta) \lt \alpha \end{displaymath} for all $\delta \lt \gamma$, and we again infer $f_{\beta}(\gamma) \leq \alpha$, as required. \end{proof} This theorem gives a canonical finite binary tree representation of any $\alpha \lt \Gamma_0$, by recursion. The binary tree $\tau(0)$ of $0$ consists of just $0$ as root, with no child-pair. Given that every $\beta$ less than $\alpha$ has been assigned a binary tree $\tau(\beta)$, we define $\tau(\alpha)$ to have the child-pair $(\tau(\beta), \tau(\gamma))$ where \begin{itemize}% \item $\beta$ is the least ordinal less than $\alpha$ such that $\alpha \lt f_\beta(\alpha)$, and \item $\gamma$ is the least ordinal less than $\alpha$ such that $\alpha \leq f_\beta(\gamma)$. \end{itemize} The resulting binary tree $\tau$ is finite for every $\alpha \lt \Gamma_0$, since it has binary branching and there are no infinite branches or paths up the tree (since that would yield an infinite descent $\alpha \gt \alpha_1 \gt \alpha_2 \gt \ldots$ with no least element, contradicting well-orderedness). This finite binary tree notation is one of many possible ordinal notations for naming countable ordinals. It is more expressive the Cantor normal form that provides a notation for ordinals $\alpha$ less than $\epsilon_0$, where one writes $\alpha$ uniquely in the form \begin{displaymath} \alpha = \omega^\beta + \gamma \end{displaymath} with $\beta, \gamma \lt \alpha$ and $\gamma \lt \gamma + \omega^\beta$, and continues recursively. \begin{remark} \label{}\hypertarget{}{} However, Cantor normal form has the virtue of uniqueness. For the binary operation $(\beta, \gamma) \mapsto f_\beta(\gamma)$, it is possible to have two distinct pairs $(\beta, \gamma)$, $(\beta', \gamma')$ which are equivalent in the sense that \begin{displaymath} f_\beta(\gamma) = f_{\beta'}(\gamma'); \end{displaymath} we counteracted this by using the pair $(\beta, \gamma)$ which was least in its equivalence class with respect to [[lexicographic order]]. \end{remark} \hypertarget{fundamental_sequences_and_the_bachmannhoward_ordinal}{}\subsection*{{Fundamental sequences and the Bachmann-Howard ordinal}}\label{fundamental_sequences_and_the_bachmannhoward_ordinal} \hypertarget{fastgrowing_functions_on_}{}\subsubsection*{{Fast-growing functions on $\mathbb{N}$}}\label{fastgrowing_functions_on_} \hypertarget{recursive_ordinals}{}\subsection*{{Recursive ordinals}}\label{recursive_ordinals} Of course, having reached $\Gamma_0$ as the least fixed point of $x \mapsto f_x(1)$, there is nothing stopping one from starting all over again with a new Veblen hierarchy, defining $g_0(x) = f_x(1)$ and defining $g_\alpha$ analogously to how we defined $f_\alpha$. In one or another way we can continue extending ordinal notation schemes, but all such schemes are recursive by definition, and at some point we cannot go any further: \begin{defn} \label{}\hypertarget{}{} A countable ordinal $\alpha$ is \textbf{recursive} if there is a computable relation on $\mathbb{N}$ (or a [[recursive subset]] of $\mathbb{N} \times \mathbb{N}$) that well-orders $\mathbb{N}$, so that the resulting woset is isomorphic to $\alpha$. \end{defn} There are countably many computable relations on $\mathbb{N}$, and so the supremum of the recursive ordinals in $\omega_1$ exists. It is called the \textbf{Church-Kleene ordinal}. It is the first non-recursive ordinal. \hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts} \begin{itemize}% \item [[uncountable ordinal]] \item [[countable set]] \item [[ordinal analysis]] \end{itemize} \hypertarget{references}{}\subsection*{{References}}\label{references} For a light-hearted introduction with many useful references, see \begin{itemize}% \item [[John Baez]], Week 236, This Week's Finds in Mathematical Physics, July 26, 2006. (\href{http://math.ucr.edu/home/baez/week236.html}{web}) \end{itemize} A very readable account of countable ordinals up to the Feferman-Sch\"u{}tte ordinal is \begin{itemize}% \item Jean Gallier, \emph{What's so Special about Kruskal's Theorem and the Ordinal $\Gamma_0$?, A Survey of Some Results in Proof Theory}, Annals of Pure and Applied Logic, Vol. 53, 199-260 (1991). (\href{ftp://ftp.cis.upenn.edu/pub/papers/gallier/kruskal2.pdf}{Part II}) \end{itemize} An application of coalgebra theory to ordinal notation systems is described here: \begin{itemize}% \item Peter Hancock, Ordinal notation systems. (\href{http://homepages.inf.ed.ac.uk/v1phanc1/ordinal-notations.html}{web}) \end{itemize} [[ordinal analysis|Ordinal analysis]] as measuring consistency strengths of theories is well-described in this paper: \begin{itemize}% \item [[Michael Rathjen]], The art of ordinal analysis, International Congress of Mathematicians, II, Eur. Math. Soc., Zurich, pp. 45--69. (\href{http://www.icm2006.org/proceedings/Vol_II/contents/ICM_Vol_2_03.pdf}{pdf}) \end{itemize} [[!redirects countable ordinals]] \end{document}