summaryrefslogtreecommitdiffstats
path: root/ordinal-zoo.tex
blob: 540f8ef862463b0571472ba8f1809a434914025b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
\documentclass[12pt,a4paper]{article}  % -*- coding: utf-8 -*-
\usepackage[a4paper]{geometry}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{times}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{bm}
\usepackage{stmaryrd}
\usepackage{wasysym}
\usepackage{amsthm}
\usepackage{url}
\usepackage{graphicx}
\usepackage[usenames,dvipsnames]{xcolor}
%\usepackage{tikz}
%\usetikzlibrary{matrix,arrows}
%
%
%
\mathchardef\emdash="07C\relax
\mathchardef\hyphen="02D\relax
\DeclareUnicodeCharacter{00A0}{~}
\newcommand{\trans}{\mathop{\mathrm{trans}}\nolimits}
%
%
\newcommand{\TODO}{\textcolor{red}{TODO}}
\newcommand{\REFTHIS}{\textcolor{brown}{REF THIS}}
\newcommand{\CHECKTHIS}{\textcolor{orange}{CHECK THIS}}
\newcommand{\FIXTHIS}{\textcolor{orange}{FIX THIS}}
\newcommand{\FINDTHIS}{\textcolor{orange}{FIND THIS}}
%
\newtheorem{comcnt}{Anything}[section]
%\newcounter{comcnt}[section]
\newcommand\ordinal{%
\refstepcounter{comcnt}\medbreak\noindent•\textbf{\thecomcnt.} }
\newtheorem{prop}[comcnt]{Proposition}
%
%
%
\begin{document}

\title{A zoo of ordinals}
\author{David A. Madore}
\maketitle

{\footnotesize
\immediate\write18{sh ./vc > vcline.tex}
Git: \input{vcline.tex}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\textbf{\textcolor{red}{Preliminary version:}} the labels in this
document are subject to change.

\section{Recursive ordinals}

\setcounter{comcnt}{-1}

\ordinal $0$ (zero).  This is the smallest ordinal, and the only one that is
neither successor nor limit.

\ordinal $1$ (one).  This is the smallest successor ordinal.

\ordinal $2$.

\ordinal $42$ (cf. \cite[chapter 27]{Adams1981}).

\ordinal $\omega$.  This is the smallest limit ordinal, and the
smallest infinite ordinal.

\ordinal $\omega+1$.  This is the smallest infinite successor ordinal.

\ordinal $\omega2$.

\ordinal $\omega^2$.

\ordinal $\omega^\omega$.

\ordinal $\omega^{\omega^\omega}$.

\ordinal $\varepsilon_0 = \varphi(1,0)$.  This is the limit of
$\omega, \omega^\omega, \omega^{\omega^\omega}, \ldots$, smallest
fixed point of $\xi \mapsto \omega^\xi$; in general, $\alpha \mapsto
\varepsilon_\alpha = \varphi(1,\alpha)$ is defined as the function
enumerating the fixed points of $\xi \mapsto \omega^\xi$.  This is the
proof-theoretic ordinal of Peano arithmetic.

\ordinal $\varepsilon_1 = \varphi(1,1)$.

\ordinal $\varepsilon_\omega$.

\ordinal $\varepsilon_{\varepsilon_0}$.

\ordinal $\varphi(2,0)$.  This is the limit of $\varepsilon_0,
\varepsilon_{\varepsilon_0}, \ldots$, smallest fixed point of $\xi
\mapsto \varepsilon_\xi$; in general, $\alpha \mapsto
\varphi(\gamma+1,\alpha)$ is defined as the function enumerating the
fixed points of $\xi \mapsto \varphi(\gamma,\xi)$.

\ordinal $\varphi(\omega,0)$.  This is the smallest ordinal closed
under primitive recursive ordinal functions.

\ordinal The Feferman-Schütte ordinal $\Gamma_0 = \varphi(1,0,0)$
(also $\psi(\Omega^{\Omega})$ for an appropriate collapsing
function $\psi$).  This is the limit of $\varepsilon_0, \penalty0
\varphi(\varepsilon_0,0), \penalty0 \varphi(\varphi(\varepsilon_0)),
\ldots$, smallest fixed point of $\xi \mapsto \varphi(\xi, 0)$.  This
is the proof-theoretic ordinal of $\mathsf{ATR}_0$.

\ordinal The Ackermann ordinal $\varphi(1,0,0,0)$ (also
$\psi(\Omega^{\Omega^2})$ for an appropriate collapsing
function $\psi$).

\ordinal The “small” Veblen ordinal ($\psi(\Omega^{\Omega^\omega})$ for
an appropriate collapsing function $\psi$).  This is the limit of
$\varphi(1,0), \penalty0 \varphi(1,0,0), \penalty0 \varphi(1,0,0,0),
\ldots$, the range of the Veblen functions with finitely many
variables.

\ordinal The “large” Veblen ordinal ($\psi(\Omega^{\Omega^\Omega})$
for an appropriate collapsing function $\psi$).  This is the range of
the Veblen functions with up to that many variables.

\ordinal The Bachmann-Howard ordinal ($\psi(\varepsilon_{\Omega+1}) =
\psi(\Omega_2)$ for an appropriate collapsing function $\psi$).  This
is the proof-theoretic ordinal of Kripke-Platek set
theory ($\mathsf{KP}$).

\ordinal The collapse of $\Omega_\omega$ (“Takeuti-Feferman-Buchholz
ordinal”), which is the proof-theoretic ordinal of
$\Pi^1_1$-comprehension.  [\CHECKTHIS: there may be a confusion
  between $\Omega_\omega$ and $\Omega_{\omega+1}$ in the collapse.]

\ordinal\label{CollapseInaccessible} The collapse of an inaccessible
(= $\Pi^1_0$-indescribable) cardinal.  This is the proof-theoretic
ordinal of Kripke-Platek set theory augmented by the recursive
inaccessibility of the class of ordinals ($\mathsf{KPi}$), or, on the
arithmetical side, of $\Delta^1_2$-comprehension.
See \cite{JaegerPohlers1983}.
(Compare •\ref{RecursivelyInaccessible}.)

\ordinal\label{CollapseMahlo} The collapse of a Mahlo cardinal.  This
is the proof-theoretic ordinal of $\mathsf{KPM}$.
See \cite{Rathjen1990}.  (Compare •\ref{RecursivelyMahlo}.)

\ordinal\label{CollapseWeaklyCompact} The collapse of a weakly compact
(= $\Pi^1_1$-indescribable) cardinal.  This is the proof-theoretic
ordinal of $\mathsf{KP} + \Pi_3\hyphen\mathsf{Ref}$.
See \cite{Rathjen1994}.  (Compare •\ref{RecursivelyWeaklyCompact}.)

\ordinal\label{CollapsePiTwoZeroIndescribable} The collapse of a
$\Pi^2_0$-indescribable cardinal.  This is the proof-theoretic ordinal
of $\mathsf{KP} + \Pi_\omega\hyphen\mathsf{Ref}$.
See \cite[part I]{Stegert2010}.  (Compare •\ref{WeaklyStable}.)

\ordinal The proof-theoretic ordinal of $\mathsf{Stability}$:
see \cite[part II]{Stegert2010}.

%
\section{Recursively large countable ordinals}

\ordinal\label{ChurchKleene} The Church-Kleene ordinal
$\omega_1^{\mathrm{CK}}$: the smallest admissible ordinal $>\omega$.
This is the smallest ordinal which is not the order type of a
recursive (equivalently: hyperarithmetic) well-ordering on $\omega$.
The $\omega_1^{\mathrm{CK}}$-recursive
(resp. $\omega_1^{\mathrm{CK}}$-semi-recursive) subsets of $\omega$
are exactly the $\Delta^1_1$ (=hyperarithmetic) (resp. $\Pi^1_1$)
subsets of $\omega$, and they are also exactly the subsets recursive
(resp. semi-recursive) in $\mathsf{E}$ (or $\mathsf{E}^\#$,
\CHECKTHIS).

\ordinal $\omega_\omega^{\mathrm{CK}}$: the smallest limit of
admissibles.  This ordinal is not admissible.  This is the smallest
$\alpha$ such that $L_\alpha \cap \mathscr{P}(\omega)$ is a model of
$\Pi^1_1$-comprehension.

\ordinal\label{RecursivelyInaccessible} The smallest recursively
inaccessible ordinal: this is the smallest ordinal which is admissible
and limit of admissibles.  This is the smallest ordinal $\alpha$ such
that $L_\alpha \models \mathsf{KPi}$, or, on the arithmetical side,
such that $L_\alpha \cap \mathscr{P}(\omega)$ is a model of
$\Delta^1_2$-comprehension.  (Compare •\ref{CollapseInaccessible}.)

This is the smallest ordinal $\omega_1^{\mathsf{E}_1}$ not the order
type of a well-ordering recursive in the Tugué
functional $\mathsf{E}_1$ (\cite[chapter VIII, theorem 6.6 on
  p. 421]{Hinman1978}), or equivalently, recursive in the hyperjump;
and for this $\alpha$ the $\alpha$-recursive
(resp. $\alpha$-semi-recursive) subsets of $\omega$ are exactly the
subsets recursive (resp. semi-recursive) in $\mathsf{E}_1$
(\cite[chapter VIII, corollary 4.16 on p. 412]{Hinman1978}).

This is the smallest $\alpha$ such that $L_\alpha \models
\mathsf{KP}+\mathit{Beta}$, where $\mathit{Beta}$ asserts the
existence of a transitive collapse for any well-founded relation, or
equivalently, the smallest admissible $\alpha$ such that any ordering
which $L_\alpha$ thinks is a well-ordering is, indeed, a
well-ordering: see \cite[theorem 6.1 on p. 291]{Nadel1973}
(compare \cite{Harrison1968} for the negative result concerning the
ordinal $\omega_1^{\mathrm{CK}}$ of •\ref{ChurchKleene}).

\ordinal The smallest recursively hyperinaccessible ordinal: i.e., the
smallest recursively inaccessible which is a limit of recursively
inaccessibles.

\ordinal\label{RecursivelyMahlo} The smallest recursively Mahlo
ordinal: i.e., the smallest admissible ordinal $\alpha$ such that for
any $\alpha$-recursive function $f \colon \alpha \to \alpha$ there is
an admissible $\beta<\alpha$ which is closed under $f$.  This is the
smallest ordinal $\alpha$ such that $L_\alpha \models \mathsf{KPM}$.
(Compare •\ref{CollapseMahlo}.)

This is the smallest ordinal not the order type of a well-ordering
recursive in the superjump (\cite{AczelHinman1974} and
\cite{Harrington1974}); and for this $\alpha$ the $\alpha$-recursive
(resp. $\alpha$-semi-recursive) subsets of $\omega$ are exactly the
subsets recursive in the superjump (resp. semirecursive in the partial
normalization of the superjump, \cite[theorem 5 on
  p. 50]{Harrington1974}).

Also note concerning this ordinal: \cite[corollary 9.4(ii) on
  p. 348]{RichterAczel1974}.

\ordinal\label{RecursivelyWeaklyCompact} The smallest
$\Pi_3$-reflecting (``recursively weakly compact'') ordinal.  This can
also be described as the smallest ``$2$-admissible'' ordinal:
see \cite[theorem 1.16 on p. 312]{RichterAczel1974}.
(Compare •\ref{CollapseWeaklyCompact}.)

Also the sup of the closure ordinals for $\Sigma_3$ inductive
operators: \cite[theorem A on p. 303]{RichterAczel1974}.  For this
$\alpha$ the $\alpha$-semi-recursive subsets of $\omega$ are exactly
the $\Sigma_3$-inductively definable subsets of $\omega$
(\cite[theorem A on p. 303 and theorem D on p. 304]{RichterAczel1974};
see also \cite[example 4.12 on p. 370]{Simpson1978}).

\ordinal\label{WeaklyStable} The smallest $(+1)$-stable ordinal, i.e.,
the smallest $\alpha$ such that $L_\alpha \mathrel{\preceq_1}
L_{\alpha+1}$.  This is the smallest $\Pi^1_0$-reflecting (i.e.,
$\Pi_n$-reflecting for every $n\in\omega$) ordinal: \cite[theorem 1.18
  on p. 313 and 333]{RichterAczel1974}.

(Compare •\ref{CollapsePiTwoZeroIndescribable}.)

\ordinal\label{PiOneOne} The smallest $(^+)$-stable ordinal, i.e., the
smallest $\alpha$ such that $L_\alpha \mathrel{\preceq_1}
L_{\alpha^+}$ where $\alpha^+$ is the smallest admissible
ordinal $>\alpha$.  This is the smallest $\Pi^1_1$-reflecting ordinal:
\cite[theorem 1.19 on p. 313 and 336]{RichterAczel1974}.  Also the sup
of the closure ordinals for $\Pi^1_1$ inductive operators:
\cite[theorem B on p. 303 or 10.7 on p. 355]{RichterAczel1974} and
\cite[theorem A on p. 222]{Cenzer1974}.  For this $\alpha$ the
$\alpha$-semi-recursive subsets of $\omega$ are exactly the
$\Pi^1_1$-inductively definable subsets of $\omega$ (\cite[theorem D
  on p. 304]{RichterAczel1974}; see also \cite[example 4.13 on
  p. 370]{Simpson1978}).

This is the smallest ordinal $\omega_1^{\mathsf{G}_1^\#}$ not the
order type of a well-ordering recursive in the nondeterministic
functional $\mathsf{G}_1^\#$ defined by $\mathsf{G}_1^\#(f) \approx
\{f(0)\}_{(\omega_1^f)^+}(f(1))$; and for this $\alpha$ the
$\alpha$-recursive (resp. $\alpha$-semi-recursive) subsets of $\omega$
are exactly the subsets recursive (resp. semi-recursive) in
$\mathsf{G}_1^\#$ (\cite[theorem 7.4 on p. 238]{Cenzer1974}).

\ordinal\label{SigmaOneOne} The smallest $\Sigma^1_1$-reflecting
ordinal.  Also the sup of the closure ordinals for $\Sigma^1_1$
inductive operators: \cite[theorem B on p. 303 or 10.7 on
  p. 355]{RichterAczel1974}.  For this $\alpha$ the
$\alpha$-semi-recursive subsets of $\omega$ are exactly the
$\Sigma^1_1$-inductively definable subsets of $\omega$
(\cite[theorem D on p. 304]{RichterAczel1974}; see
also \cite[example 4.14 on p. 370]{Simpson1978}).

That this ordinal is gerater than that of •\ref{PiOneOne}:
\cite[corollary 1 to theorem 6 on p.213]{Anderaa1974}; also see:
\cite[theorem 6.5]{Simpson1978}.

This is the smallest ordinal $\omega_1^{\mathsf{E}_1^\#}$ not the
order type of a well-ordering recursive in the nondeterministic
version $\mathsf{E}_1^\#$ of the Tugué functional $\mathsf{E}_1$; and
for this $\alpha$ the $\alpha$-recursive
(resp. $\alpha$-semi-recursive) subsets of $\omega$ are exactly the
subsets recursive (resp. semi-recursive) in $\mathsf{E}_1^\#$ (combine
\cite[theorem 1 on p. 313, theorem 2 on p. 318]{Aczel1970} and
\cite[theorem D on p. 304]{RichterAczel1974}).

[\FINDTHIS: how stable is this ordinal?]

\ordinal The smallest $(^{++})$-stable ordinal, i.e., the smallest
$\alpha$ such that $L_\alpha \mathrel{\preceq_1} L_{\alpha^{++}}$
where $\alpha^+,\alpha^{++}$ are the two smallest admissible
ordinals $>\alpha$.  This is $\Sigma^1_1$-reflecting and greater than
the ordinal of •\ref{SigmaOneOne} (\cite[theorem 6.4 on
  p. 376]{Simpson1978} and
proposition \ref{PlusPlusStableOrdinalIsSigmaOneOneReflecting} below).

\ordinal The smallest inaccessibly-stable ordinal, i.e., the smallest
$\alpha$ such that $L_\alpha \mathrel{\preceq_1} L_\beta$ where
$\beta$ is the smallest recursively inaccessible
(cf. •\ref{RecursivelyInaccessible}) ordinal $>\alpha$.

\ordinal The smallest Mahlo-stable ordinal, i.e., the smallest
$\alpha$ such that $L_\alpha \mathrel{\preceq_1} L_\beta$ where
$\beta$ is the smallest recursively Mahlo
(cf. •\ref{RecursivelyMahlo}) ordinal $>\alpha$.

\ordinal The smallest doubly $(+1)$-stable ordinal, i.e., the smallest
$\alpha$ such that $L_\alpha \mathrel{\preceq_1} L_\beta
\mathrel{\preceq_1} L_{\beta+1}$ (cf. •\ref{WeaklyStable}).

\ordinal\label{NonprojectibleStable} The smallest stable ordinal under
a nonprojectible ordinal, i.e., the smallest $\alpha$ such that
$L_\alpha \mathrel{\preceq_1} L_\beta$ where $\beta$ is the smallest
nonprojectible (the ordinal of •\ref{Nonprojectible}).

This is the smallest ordinal $\omega_1^{\mathbf{R}}$ not the order
type of a well-ordering recursive in a certain type $3$ functional
$\mathbf{R}$ defined in \cite{Harrington1975}; and for this $\alpha$
the $\alpha$-recursive subsets of $\omega$ are exactly the subsets
recursive in $\mathbf{R}$.  (See also \cite{John1986} and
\cite[example 4.10 on p. 369]{Simpson1978}.)

\ordinal\label{Nonprojectible} The smallest nonprojectible ordinal,
i.e., the smallest $\beta$ such that $\beta$ is a limit of
$\beta$-stable ordinals (ordinals $\alpha$ such that $L_\alpha
\mathrel{\preceq_1} L_\beta$ (cf. •\ref{NonprojectibleStable}); in
other words, the smallest $\beta$ such that $L_\beta \models
\mathsf{KPi}+$“the stable ordinals are unbounded”.  This is the
smallest ordinal $\beta$ such that $L_\beta \models
\mathsf{KP}\omega+\Sigma_1\hyphen\textsf{Sep}$ (cf. \cite[chapter V,
  theorem 6.3 on p. 175]{Barwise1975}), or such that $L_\beta \cap
\mathscr{P}(\omega)$ is a model of $\Pi^1_2$-comprehension
(cf. \cite[theorem VII.3.24 on p. 267 and theorem VII.5.17 on
  p. 292]{Simpson2009}).

In Jensen's terminology (\cite{Jensen1972}), this is the smallest
ordinal $\beta$ such that $\rho_1^\beta > \omega$, and in fact the
smallest $\beta>\omega$ such that $\rho_1^\beta = \beta$: that is, the
smallest ordinal $\beta$ such that every $\Sigma_1(L_\beta)$ subset
of $\omega$ is $\beta$-finite.  Sometimes also called the smallest
“strongly admissible” (or “strongly $\Sigma_1$-admissible”) ordinal.

\ordinal The smallest (weakly) $\Sigma_2$-admissible ordinal.  This is
the smallest ordinal $\beta$ such that $L_\beta \models
\mathsf{KP}\omega+\Delta_2\hyphen\textsf{Sep}$, or such that $L_\beta
\cap \mathscr{P}(\omega)$ is a model of $\Delta^1_3$-comprehension
(cf. \cite[theorem VII.3.24 on p. 267 and theorem VII.5.17 on
  p. 292]{Simpson2009}).

In Jensen's terminology (\cite{Jensen1972}), this is the smallest
ordinal $\beta$ such that $\eta_2^\beta > \omega$, and in fact the
smallest $\beta>\omega$ such that $\eta_2^\beta = \beta$: that is, the
smallest ordinal $\beta$ such that every $\Delta_2(L_\beta)$ subset
of $\omega$ is $\beta$-finite.

In the terminology of \cite[appendix]{MarekSrebrny1973}, this is the
first $\Delta_2$-gap ordinal.

\ordinal The ordinal of ramified analysis (often written $\beta_0$).
This is the smallest $\beta$ such that $L_\beta \models \bigwedge_n
\Sigma_n\hyphen\textsf{Sep}$ (the full separation scheme), or such
that $L_\beta \cap \mathscr{P}(\omega)$ is a model of full
second-order analysis (second-order comprehension), and in fact
$L_\beta \models \mathsf{ZFC}^-$ (that is, $\mathsf{ZFC}$ minus the
powerset axiom).

This starts the first gap in the constructible universe, and this gap
is of length $1$: see \cite{Putnam1963} and \cite[corollary 4.5 on
  p. 374]{MarekSrebrny1973}.

Note that this ordinal is $(+1)$-stable (cf. •\ref{WeaklyStable}) but
not $(+2)$-stable: \cite[corollary to theorem 6.14 on
  p. 384]{MarekSrebrny1973}.

\ordinal The start of the first gap of length $2$ in the constructible
universe.  If $\beta$ is this ordinal then $\beta$ is the $\beta$-th
gap ordinal (\cite[theorem 4.17 on p. 377]{MarekSrebrny1973}).

\ordinal The first ordinal $\beta$ which starts a gap of
length $\beta$ in the constructible universe.

\ordinal\label{OmegaOneSmallestModelKPWithOmegaOne} The ordinal $\beta
= \omega_1^{L_\alpha}$ where $\alpha$ is ordinal
of •\ref{SmallestModelKPWithOmegaOne}.  Then by construction $\beta$
starts a gap of length $\alpha = \beta^+$ (the next admissible
ordinal).

\ordinal\label{SmallestModelKPWithOmegaOne} The smallest ordinal
$\alpha$ such that $L_\alpha \models \mathsf{KP}+$“$\omega_1$ exists”,
i.e., the smallest admissible $\alpha$ which is not locally countable,
or equivalently, the smallest $\alpha$ such that $L_\alpha \models
\mathsf{KP}+$“$\mathscr{P}(\omega)$ exists”
(cf. proposition \ref{KPExistenceOfOmegaOneImpliesExistenceOfPOmega}).

\ordinal The smallest ordinal $\alpha$ such that $L_\alpha \models
\mathsf{ZFC}^-+$“$\omega_1$ exists”, or equivalently such that
$L_\alpha \models \mathsf{KP}+$“$\mathscr{P}(\omega)$ exists”
(cf. proposition \ref{KPExistenceOfOmegaOneImpliesExistenceOfPOmega}).
This is the start of the first third-order gap (\cite[theorem 3.7 on
  p. 372]{MarekSrebrny1973}) in the constructible universe.

%
%
%

\ordinal\label{OmegaOneSmallestModelZFC} The smallest uncountable
ordinal $\omega_1^{L_\alpha}$ in the smallest model $L_{\alpha}$
of $\mathsf{ZFC}$, assuming it exists (see •\ref{SmallestModelZFC}).
This ordinal is $\alpha$-stable.

\ordinal\label{SmallestModelZFC} The smallest ordinal $\alpha$ such
that $L_\alpha \models \mathsf{ZFC}$ (assuming it exists), i.e., the
height of the minimal model of $\mathsf{ZFC}$.

\ordinal\label{Stable} The smallest stable ordinal $\sigma$, i.e., the
smallest $\sigma$ such that $L_\sigma \mathrel{\preceq_1} L$, or
equivalently $L_\sigma \mathrel{\preceq_1} L_{\omega_1}$.  The set
$L_\sigma$ is the set of all $x$ which are $\Sigma_1$-definable in $L$
without parameters (\cite[chapter V, corollary 7.9(i) on
  p. 182]{Barwise1975}).

This ordinal is projectible to $\omega$ (i.e., in Jensen's
terminology), $\rho_1^\sigma = \omega$ (\cite[chapter V,
  theorem 7.10(i) on p. 183]{Barwise1975}).

This is the smallest ordinal $\delta^1_2$ which not the order type of
a well-ordering $\Delta^1_2$ on $\omega$; and in fact, for this
$\sigma = \delta^1_2$, the $\sigma$-recursive
(resp. $\sigma$-semi-recursive) subsets of $\omega$ are exactly the
$\Delta^1_2$ (resp. $\Sigma^1_2$) subsets of $\omega$
(\cite[chapter V, theorem 8.2 on p. 189 and corollary 8.3 on
  p. 191]{Barwise1975}).

This is also the smallest $\Sigma^1_2$-reflecting ordinal
(\cite{Richter1975}).

\bigbreak

\textbf{\textcolor{orange}{Note:}} This document should probably not
start listing large cardinals, because \textbf{(0)} the fact that one
implies the other nonwithstanding, this is about “ordinals”, not
“cardinals”, \textbf{(1)} they are already well covered elsewhere
(see, e.g., \cite{Kanamori1997}) and \textbf{(2)} we don't want to
start making assumptions, e.g., about whether $\omega_1^L$ is or is
not equal to $\omega_1$, but without making such assumptions it is no
longer possible to correctly order definitions.  Perhaps a median way
would be to assume $V=L$ for ordering, forget about measurable
cardinals and whatnot, and still include inaccessibles, Mahlo, weakly
compact, etc.

%
%
%

\section{Various statements}

\begin{prop}\label{PlusPlusStableOrdinalIsSigmaOneOneReflecting}
If $\alpha$ is such that $L_\alpha \mathrel{\preceq_1}
L_{\alpha^{++}}$ (where $\alpha^+,\alpha^{++}$ are the two smallest
admissible ordinals $>\alpha$) then $\alpha$ is
$\Sigma^1_1$-reflecting.  (Stated in \cite[theorem 6.4 on
  p. 376]{Simpson1978}.)
\end{prop}
\begin{proof}
Assume $L_\alpha \models \exists U(\varphi(U))$ where $\varphi$ is a
$\Pi^1_0$ (=first-order) formula with constants in $L_\alpha$ and the
extra relation symbol $U$.  We want to show that there exists
$\beta<\alpha$ such that $L_\beta \models \exists U(\varphi(U))$.

Now by \cite[theorem 6.2 on p. 334]{RichterAczel1974} (applied to the
negation of $\exists U(\varphi(U))$) we can find a $\Pi_1$ formula
$\forall z(\psi(S,z))$ (with the same constants as $\varphi$) such
that for any countable transitive set $A$ containing these constants
and any admissible $B\ni A$ we have $B \models \forall z(\theta(A,z))$
iff $A \models \exists U(\varphi(U))$.

In particular, $L_{\alpha^+} \models \forall z(\theta(L_\alpha,z))$.
So $L_{\alpha^+} \models \exists A(\trans(A) \land \penalty0
(A\models\Theta+V{=}L) \land \penalty0 \forall z(\theta(A,z)))$, were
$\Theta$ is a statement which translates the adequacy of $A$ (see
\cite{Jech1978} (13.9) and lemmas 13.2 and 13.3 p. 110–112, or
\cite{Jech2003}, (13.12) and (13.13) p. 188).  So in turn
$L_{\alpha^{++}} \models \exists C(\trans(C) \land \penalty0
(C\models\mathsf{KP}+V{=}L) \land \penalty0 (C \models \exists
A(\trans(A) \land \penalty100 (A\models\Theta+V{=}L) \land \penalty100
\forall z(\theta(A,z)))))$.  But this is a $\Sigma_1$ formula with
constants in $L_\alpha$, so by the assumption we have $L_\alpha
\models$ the same thing.  So there is $C \in L_\alpha$ transitive and
containing the constants of $\varphi$, and which is necessarily an
$L_\gamma$ (for $\gamma<\alpha$) because $C \models
\mathsf{KP}+V{=}L$, such that $L_\gamma \models \exists A(\trans(A)
\land \penalty0 (A\models\Theta+V{=}L) \land \penalty0 \forall
z(\theta(A,z)))$.  So in turn there exists $A \in L_\gamma$
transitive, which is necessarily an $L_\beta$ (for $\beta<\gamma$)
because $A \models \Theta+V{=}L$, such that $L_\gamma \models \forall
z(\theta(L_\beta,z))$.  So $L_\beta \models \exists U(\varphi(U))$.
\end{proof}

\begin{prop}\label{KPExistenceOfOmegaOneImpliesExistenceOfPOmega}
The following holds in $\mathsf{KP}$: if $A\subseteq \omega$ is
constructible, then $A \in L_\gamma$ for some countable
ordinal $\gamma$.

In particular, in $\mathsf{KP} + V=L$, if there exists an uncountable
ordinal $\delta$, then $\mathscr{P}(\omega)$ exists and can be defined
as $\{A \in L_\delta : A\subseteq\omega\}$.
\end{prop}
\begin{proof}
We have to verify that the usual proof (cf. \cite[chapter II,
  lemma 5.5 on p. 84]{Devlin1984} or \cite[lemma 13.1 on
  p. 110]{Jech1978} or \cite[theorem 13.20 on p. 190]{Jech2003})
works in $\mathsf{KP}$.

Working in $L$, we can assume that $V=L$ holds.  Also, we can assume
that $\omega$ exists because if every set is finite the result is
trivial.

Since $A$ is constructible there is $\delta$ limit such that $A \in
L_\delta$.  We can define $\Delta_1$-Skolem functions for $L_\delta$
inside $\mathsf{KP}$, and because $\omega$ exists we can use induction
(cf. \cite[remarks following definition 9.1 on p. 38]{Barwise1975}) to
construct the Skolem hull $M$ of $L_\omega \cup \{A\}$ inside
$L_\delta$ (or use \cite[chapter II, lemma 5.3 on p. 83]{Devlin1984}).
Since $M$ is extensional, we can now use the Mostowski collapse $\pi
\colon M \buildrel\sim\over\to N$ (cf. \cite[theorem 7.4 on
  p. 32]{Barwise1975}) to collapse $M$ to a transitive set $N$, which
is necessarily an $L_\gamma$.  Now $M$ is countable by construction,
so $N = L_\gamma$ is also, so $\gamma$ is.  And we have $\pi(A) = A$
so $A \in L_\gamma$ with $\gamma$ countable, as asserted.
\end{proof}

%
%
%

\begin{thebibliography}{}

\bibitem[Aczel1970]{Aczel1970} Peter Aczel, “Representability in Some
  Systems of Second Order Arithmetic”, \textit{Israel J. Math}
  \textbf{8} (1970), 308–328.

\bibitem[AczelHinman1974]{AczelHinman1974} Peter Aczel \& Peter
  G. Hinman, “Recursion in the Superjump”, \textit{in}: Jens Erik
  Fenstad \& Peter G. Hinman (eds.), \textit{Generalized Recursion
    Theory} (Oslo, 1972), North-Holland (1974), ISBN 0-7204-2276-0,
  5–41.

\bibitem[Adams1981]{Adams1981} Douglas Adams, \textit{The Hitchiker's
  Guide to the Galaxy}, Pocket Books (1981), ISBN 0-671-46149-4.

\bibitem[Anderaa1974]{Anderaa1974} Stål Anderaa, “Inductive
  Definitions and their Closure Ordinals”, \textit{in}: Jens Erik
  Fenstad \& Peter G. Hinman (eds.), \textit{Generalized Recursion
    Theory} (Oslo, 1972), North-Holland (1974), ISBN 0-7204-2276-0,
  207–220.

\bibitem[Barwise1975]{Barwise1975} Jon Barwise, \textit{Admissible
  sets and structures, An approach to definability theory},
  Perspectives in Mathematical Logic \textbf{7}, Springer-Verlag
  (1975), ISBN 3-540-07451-1.

\bibitem[Cenzer1974]{Cenzer1974} Douglas Cenzer, “Ordinal Recursion
  and Inductive Definitions”, \textit{in}: Jens Erik Fenstad \& Peter
  G. Hinman (eds.), \textit{Generalized Recursion Theory} (Oslo,
  1972), North-Holland (1974), ISBN 0-7204-2276-0, 221–264.

\bibitem[Devlin1984]{Devlin1984} Keith Devlin,
  \textit{Constructibility}, Perspectives in Mathematical
  Logic \textbf{6}, Springer-Verlag (1984), ISBN 3-540-13258-9.

\bibitem[Harrington1974]{Harrington1974} Leo Harrington, “The
  Superjump and the first Recursively Mahlo Ordinal”, \textit{in}:
  Jens Erik Fenstad \& Peter G. Hinman (eds.), \textit{Generalized
    Recursion Theory} (Oslo, 1972), North-Holland (1974),
  ISBN 0-7204-2276-0, 43–52.

\bibitem[Harrington1975]{Harrington1975} Leo Harrington, “Kolmogorov's
  $R$-operator and the first nonprojectible ordinal”, unpublished
  notes (1975).

\bibitem[Harrison1968]{Harrison1968} Joseph Harrison, “Recursive
  pseudo-well-orderings”, \textit{Trans. Amer. Math. Soc.}
  \textbf{131} (1968), 526–543.

\bibitem[Hinman1978]{Hinman1978} Peter G. Hinman,
  \textit{Recursion-Theoretic Hierarchies}, Perspectives in
  Mathematical Logic \textbf{9}, Springer-Verlag (1978),
  ISBN 3-540-07904-1.

\bibitem[JaegerPohlers1983]{JaegerPohlers1983} Gerhard Jäger \&
  Wolfram Pohlers, “Eine beweistheoretische Untersuchung von
  ($\Delta^1_2$-$\mathsf{CA}$)+($\mathsf{BI}$) und verwandter
  Systeme”, \textit{Bayer. Akad. Wiss.,
    Math.-Natur. Kl. Sitzungsber. 1982} (1983), 1–28.

\bibitem[Jech1978]{Jech1978} Thomas Jech, \textit{Set theory}, Pure
  and Applied Mathematics \textbf{79}, Academic Press (1978),
  ISBN 0-12-381950-4.

\bibitem[Jech2003]{Jech2003} Thomas Jech, \textit{Set theory, The
  third millennium edition, revised and expanded}, Springer Monographs
  in Mathematics, Springer-Verlag (2003), ISBN 3-540-44085-2.

\bibitem[Jensen1972]{Jensen1972} Ronald Björn Jensen, “The fine
  structure of the constructible hierarchy”, \textit{Ann. Math. Logic}
  \textbf{4} (1972), 229–308.

\bibitem[John1986]{John1986} Thomas John, “Recursion in Kolmogorov's
  $R$-operator and the ordinal $\sigma_3$”, \textit{J. Symbolic Logic}
  \textbf{51} (1986), 1–11.

\bibitem[Kanamori1997]{Kanamori1997} Akihiro Kanamori, \textit{The
  Higher Infinite} (corrected first edition), Perspectives in
  Mathematical Logic, Springer-Verlag (1997), ISBN 3-540-57071-3.

\bibitem[MarekSrebrny1973]{MarekSrebrny1973} Wiktor Marek \& Marian
  Srebrny, “Gaps in the Constructible Universe”,
  \textit{Ann. Math. Logic} \textbf{6} (1974), 359–394.

\bibitem[Nadel1973]{Nadel1973} Mark Nadel, “Scott Sentences and
  Admissible Sets”, \textit{Ann. Math. Logic} \textbf{7} (1974),
  267–294.

\bibitem[Putnam1963]{Putnam1963} Hilary Putnam, “A Note on
  Constructible Sets of Integers”, \textit{Notre Dame J. Formal Logic}
  \textbf{4} (1963), 270–273.

\bibitem[Rathjen1990]{Rathjen1990} Michael Rathjen, “Ordinal Notations
  Based on a Weakly Mahlo Cardinal”, \textit{Arch. Math. Logic}
  \textbf{29} (1990), 249–263.

\bibitem[Rathjen1994]{Rathjen1994} Michael Rathjen, “Proof theory of
  reflection”, \textit{Ann. Pure Appl. Logic} \textbf{68} (1994),
  181–224.

\bibitem[Richter1975]{Richter1975} Wayne Richter, “The Least
  $\Sigma^1_2$ and $\Pi^1_2$ Reflecting Ordinals”, \textit{in}: Gert
  H. Müller, Arnold Oberschelp \& Klaus Potthoff,
  \textit{$\models$ISILC Logic Conference} (Kiel, 1974),
  Springer-Verlag \textit{Lecture Notes in Math.} \textbf{499} (1975),
  ISBN 3-540-07534-8, 568–578.

\bibitem[RichterAczel1974]{RichterAczel1974} Wayne Richter \& Peter
  Aczel, “Inductive Definitions and Reflecting Properties of
  Admissible Ordinals”, \textit{in}: Jens Erik Fenstad \& Peter
  G. Hinman (eds.), \textit{Generalized Recursion Theory} (Oslo,
  1972), North-Holland (1974), ISBN 0-7204-2276-0, 301–381.

\bibitem[Simpson1978]{Simpson1978} Stephen G. Simpson, “Short Course
  on Admissible Recursion Theory”, \textit{in}: Jens Erik Fenstad,
  R. O. Gandy \& Gerald E. Sacks (eds.), \textit{Generalized Recursion
    Theory II} (Oslo, 1977), North-Holland (1978), ISBN 0-444-85163-1,
  355–390.

\bibitem[Simpson2009]{Simpson2009} Stephen G. Simpson,
  \textit{Subsystems of Second-Order Arithmetic} (second edition),
  Perspectives in Logic, ASL (2009), ISBN 978-0-521-88439-6.

\bibitem[Stegert2010]{Stegert2010} Jan-Carl Stegert, \textit{Ordinal
  Proof Theory of Kripke-Platek Set Theory Augmented by Strong
  Reflection Principles}, PhD dissertation (Westfälischen
  Wilhelms-Universität Münster), 2010.

\end{thebibliography}

\end{document}