03_large_cardinals.tex

\section{Reflection And Large Cardinals}

\subsection{Regular Fixed–Point Axioms}\label{sec:regular_fixed_points}
Lévy's article mentions various schemata that are not instances of reflection per se, but deal with fixed points of normal ordinal functions. 
After proving a helpful lemma, we will introduce them and show that they are equivalent to \emph{First–Order Reflection Schema}\footnote{For the definition, see definition \bref{def:first_order_reflection_schema}.}.

\begin{lemma}{(Fixed–Point Lemma for Normal Functions)}\label{lemma:normal_fixed_point}\\
Let $f$ be a normal function defined for all ordinals\footnote{For the definition of normal function, see definition \bref{def:normal_function}.}. Then all of the following hold:
\bce[(i)]
\item $\forall \lambda(\mbox{``$\lambda$ is a limit ordinal''} \then \mbox{``f($\lambda$) is a limit ordinal''})$
\item $\forall \alpha (\alpha \leq f(\alpha))$
\item $\forall \alpha \exists \beta (\alpha < \beta \et f(\beta) = \beta)$
\item The fixed points of $f$ form a closed unbounded class.\footnote{See definition \bref{def:closed_class} for the definition of a closed class, definition \bref{def:unbounded_class} for the definition of unboundedness.}
\ece
\end{lemma}

\begin{proof}
Let $f$ be a normal function defined for all ordinals.
\bce[(i)]
\item
Suppose $\lambda$ is a limit ordinal. 
For an arbitrary ordinal $\alpha < \lambda$, the fact that $f$ is strictly increasing means that $f(\alpha) < f(\lambda)$ and for any ordinal $\beta$, 
satisfying $\alpha < \beta < \lambda$, $f(\alpha) < f(\beta) < f(\lambda)$. 
We know that there is such $\beta$ from limitness of $\lambda$.
Because $f$ is continuous and $\lambda$ is limit, $f(\lambda) = \bigcup_{\gamma < \lambda} f(\gamma)$.% and since $\beta < \lambda$, $f(\beta) < f(\lambda)$. 
Therefore $\lambda$ is limit, so is $f(\lambda)$.
%So we have found $f(\beta)$ such that $f(\alpha) < f(\beta) < f(\lambda)$, therefore $f(\lambda)$ is a limit ordinal.\\

\item This step will be proved using the transfinite induction.
Since $f$ is defined for all ordinals, there is an ordinal $\alpha$ such that $f(\emptyset) = \alpha$ and because $\emptyset$ is the least ordinal, (ii) holds for $\emptyset$.

Suppose (ii) holds for some $\beta$ from the induction hypothesis. It then holds for $\beta+1$ because $f$ is strictly increasing. 

For a limit ordinal $\lambda$, suppose (ii) holds for every $\alpha < \lambda$. (i) implies that $f(\lambda)$ is also limit, 
so there is a strictly increasing $\kappa$–sequence $\langle \alpha_0, \alpha_1, \ldots \rangle$ for some $\kappa$ such that $\lambda = \bigcup_{i<\kappa} \alpha_i$. Because $f$ is strictly increasing, the $\kappa$–sequence $\la f(\alpha_0), f(\alpha_1), \ldots \ra$ is also strictly increasing, in then holds from the induction hypothesis that $\alpha_i \leq f(\alpha_i)$ for each $i \leq \kappa$. 
Thus, $\lambda \leq f(\lambda)$.

\item For an arbitrary $\alpha$, let there be an $\omega$–sequence $\langle \alpha_0, \alpha_1, \ldots \rangle$, 
such that $\alpha_0 = \alpha$ and $\alpha_{i+1} = f(\alpha_i)$ for each $i < \omega$.
This sequence is stricly increasing because so is $f$. 
Now, there's a limit ordinal $\beta = \bigcup_{i < \omega} \alpha_i$, we want to show that this is a fixed point of $f$. 
Because $f$~is continuous,
\beq
f(\beta) = f(\bigcup_{i < \omega} \alpha_i) = \bigcup_{i < \omega} f(\alpha)\mbox{.}
\eeq 
We have defined the above sequence so that 
\beq
f(\beta) = \bigcup_{i < \omega} f(\alpha) = \bigcup_{i < \omega} \alpha_{i+1}\mbox{,}
\eeq 
which means we are done, since 
\beq
\bigcup_{i < \omega} \alpha_{i+1} = \bigcup_{i < \omega} \alpha_{i}  = \beta\mbox{.}
\eeq

% Todo http://math.stackexchange.com/questions/1865519/when-is-the-union-of-a-set-of-ordinals-a-limit-ordinal/1865527#1865527
\item The class of fixed points of $f$ is obviously unbounded because in (iii), we start with an arbitrary ordinal.
It remains to show that it is closed, this is based on \cite{DrakeBook}, \emph{chapter 4}. 
Let $Y$ be a non–empty set of fixed points of $f$ such that $\bigcup Y \not\in Y$. Since $f$ is defined on ordinals, $Y$ is a set of ordinals, so $\bigcup Y$ is an ordinal.
$\bigcup Y$ is a limit ordinal. 
If it were a successor ordinal, suppose that $\alpha+1 = \bigcup Y$, then $\alpha \in \bigcup Y$, which would mean that there is some~$x$~such that $\alpha \in x \in Y$. 
But the least such~$x$~is $\alpha+1$, so $\bigcup Y~\in~Y$.
%We will show that $\bigcup Y$ is a limit ordinal because $Y$ doesn't have a maximal element.

Note that $\alpha < \bigcup Y \mbox{ iff } \exists \xi \in Y (\alpha < \xi)$. Since $f$ is defined for all ordinals and $\bigcup Y$ is a limit ordinal, $f(\bigcup Y) = \bigcup_{\alpha \in Y} f(\alpha)$, but because $Y$ is a set of fixed points of $f$,
\beq
f(\bigcup Y) = \bigcup_{\alpha \in Y} f(\alpha) = \bigcup Y\mbox{,}
\eeq
so $\bigcup Y$ is a limit point of $Y$.
\ece
\end{proof}

\begin{lemma}\label{lemma:normal_enumerates_club}\
Let $\alpha$ be a limit ordinal. Then the following hold:
%\bce[(i)] % TODO pozor na club / ``closed unbounded''
%\item 
If $C$ is a club subset of $\alpha$, then there is an ordinal $\beta$ and a normal function $f: \beta \then \alpha$ such that $rng(f) = C$. We say that $f$ \emph{enumrates} $C$.
%\item If $\beta$ is an ordinal and $f$ is a normal function such that $f: \beta \then \alpha$ and $rng(f)$ is unbounded in $\alpha$, then $rng(f)$ is a closed unbouded set in $\alpha$.
%\ece
\end{lemma}

This proof in inspired by \cite{MonkGradsets09}.

\begin{proof}
%\bce[(i)]
%\item 
Let $\beta$ be the order–type\footnote{See definition \bref{def:order_type}.} of $C$ and let $f$ be the isomorphism from $\beta$ onto $C$. Since $C \subseteq \alpha$, $f$ is an increasing function from $\beta$ into $\alpha$. To show that $f$ is continuous, let $\gamma$ be a limit ordinal below $\beta$, let $\epsilon = \bigcup_{\delta<\gamma} f(\delta)$. We want to verify that $f(\gamma) = \epsilon$. Since $\epsilon$ is a limit ordinal, we only need to show that $C \cap \epsilon$ is inbounded in $\epsilon$.

Take $\zeta < \epsilon$. Then there is a $\delta < \gamma$ such that $\zeta < f(\delta)$. 
Since $\gamma$ is limit, $\delta + 1 < \gamma$ and also $f(\delta + 1) < f(\gamma)$, we know that $f(\delta) \in C \cap \epsilon$. 
But that means that $C \cap \epsilon$ is unbounded in $\epsilon$, so $\epsilon \in C$. We have also shown that $\epsilon$ is closed unbounded in the image of $\gamma$ over $f$.
Therefore, $f(\gamma) = \epsilon = \bigcup_{\delta < \gamma} f(\delta)$, so $f$ is normal.
% \ece
\end{proof}

It should be clear that while this lemma works with club subsets of an ordinal, we can formulate analogous statement for club classes, which then yields a normal function defined for all ordinals, with the only exception that there is no such $\beta$ is an the beginning of the above proof because $f$ is then a function from $Ord$ to $Ord$ and proper classes have no order–type.

% TODO lemma ze limity tvori club?
% http://math.stackexchange.com/questions/109292/the-set-of-limit-points-of-an-unbounded-set-of-ordinals-is-closed-unbounded
% Lévy proposes in \cite{Levy60a} those axioms as equivalent to \emph{Reflection\textsubscript{1}}.

\begin{definition}{(\emph{Axiom Schema $M$\textsubscript{1}})}\label{def:levy_m}\\
``Every normal function defined for all ordinals has at least one inaccessible number in its range.''
\end{definition}
Lévy uses ``$M$'' to refer to this axiom but since we also use ``$M$'' for sets and models, for example in definition \bref{theorem:first_order_reflection}, we will call the above axiom ``\emph{Axiom Schema $M$\textsubscript{1}}'' to avoid confusion.

%Now we will express \emph{Axiom $M$\textsubscript{1}} as a formula to make it clear that it is an axiom scheme and the same can be done with \emph{Axiom $M$\textsubscript{2}} as well as \emph{Axiom Schema $M$} introduced immediately afterwards. Since it is an axiom schema and we will later dive into second–order logic, we may also want to refer to \emph{Axiom $M$\textsubscript{2}} as opposed \emph{Axiom $M$\textsubscript{1}}, the former being a single second–order sentence obtained by the obvious modification of \emph{Axiom $M$\textsubscript{1}}.\footnote{Second–order set theory will be introduced in the next subsection.}

In order to be able to meaningfully work with this schema, we must clarify what it actually states. 
Because we are working in first–order logic, and a \emph{normal function defined for all ordinals} is a proper class, we can not quantify over functions that are not sets. 
Instead, we will think of \emph{Axiom Schema $M$\textsubscript{1}} as schema that, given a formula $\varphi$, states % By ``every normal function defined for all ordinals has at least one inaccessible number in its range'', we mean the axiom schema that yields 
``If $\varphi$ is a normal function defined for all ordinals, then $\varphi$ has at least one inaccessible number in its range''%
\footnote{More formally, let $\varphi(x, y, p_1, \ldots, p_n)$ be a first–order formula with no free variables besides $x, y, p_1, \ldots, p_n$. The following is equivalent to \emph{Axiom $M$\textsubscript{1}}.
\begin{equation}
\begin{gathered}
\mbox{``$\varphi$ is a normal function''} \et \forall x (x \in Ord \then \exists y(\varphi(x, y, p_1, \ldots, p_n))) \then\\
\then \exists y (\exists x \varphi(x, y, p_1, \ldots, p_n) \et cf(y) = y \et (\forall x \in \kappa)(\exists y \in \kappa)(x > y))
\end{gathered}
\end{equation}}.
We will approach the following two axiom schemata in a similar manner.

\begin{definition}{(Axiom Schema $M$\textsubscript{2})}\\
``Every normal function defined for all ordinals has at least one fixed point which is inaccessible.''
\end{definition}

\begin{definition}{(Axiom Schema $M$\textsubscript{3})}\\
``Every normal function defined for all ordinals has arbitrarily great fixed points which are inaccessible.''
\end{definition}

Similar axiom is proposed in \cite{DrakeBook}.
\begin{definition}{(Axiom Schema $F$)}\label{def:axiom_f}\\
``Every normal function has a regular fixed point.''
\end{definition}

\begin{lemma}\label{lemma:limit_fixed_normal_function}
Let $f$ be a normal function defined for all ordinals.
\bce[(i)]
\item There is a is normal function $g_1$ defined for all ordinals that enumerates the class $\{\alpha : f(\alpha) = \alpha \}$.
\item There is a is normal function $g_2$ defined for all ordinals that enumerates the class $\{ \lambda : \mbox{``$f(\lambda)$ is a strong limit cardinal.''}\}$. 
\ece
\end{lemma}

\begin{proof}
We know that (ii) holds from lemma \bref{lemma:normal_fixed_point} and lemma \bref{lemma:normal_enumerates_club}.

Clearly, there is no largest strong limit ordinal $\nu$, because the limit of\\
$\la \nu, \power{\nu}, \power{\power{\nu}}, \ldots \ra$ is again a limit ordinal. % pozor na strong limit
The class of strong limit ordinals is closed because a limit of strong limit ordinals of is always a strong limit ordinal.
Let $h$ be a function enumerating limit ordinals that exists from lemma \bref{lemma:normal_enumerates_club}.
Then $g_1(\alpha) = f(h(\alpha))$ for every ordinal $\alpha$ is normal and defined for all ordinals.
\end{proof}

The following is \emph{Theorem 1} in \cite{Levy60a}, the parts dealing with \emph{Axiom Schema $F$} come from \cite{DrakeBook}.

\begin{theorem}
The following are all equivalent:
\bce[(i)]
\item \emph{Axiom Schema $M$\textsubscript{1}},
\item \emph{Axiom Schema $M$\textsubscript{2}},
\item \emph{Axiom Schema $M$\textsubscript{3}},
\item \emph{Axiom Schema $F$}.
\ece
\end{theorem}

\begin{proof}
It is clear that \emph{Axiom Schema $M$\textsubscript{3}} is a stronger version of \emph{Axiom Schema $M$\textsubscript{2}}, which is in turn a stronger version of both \emph{Axiom Schema $M$\textsubscript{1}} and \emph{Axiom Schema $F$\textsubscript{1}}. 

We will now prove that \emph{Axiom Schema $F$} $\then$ \emph{Axiom Schema $M$\textsubscript{2}}. 
Lemma \bref{lemma:limit_fixed_normal_function} tells us that given a normal function $f$ defined for all ordinals, 
there is a normal function $g_1$ defined for all ordinals that enumerates the fixed points of $f$. 
There is also a function $g_2$ that enumerates the strong limit ordinals in $rng(f)$.
By \emph{Axiom Schema $F$}, $g_2$ has a regular fixed point $\kappa$, which is also a strong limit ordinal, so 
\beq
f(\kappa) = g_2(\kappa) = \kappa \mbox{ and $\kappa$ is inaccessible.} 
\eeq
So every normal function defined for all ordinals has a regular fixed point.

We have yet to show that \emph{Axiom Schema $M$\textsubscript{1}} $\then$ \emph{Axiom Schema $M$\textsubscript{3}}. Again by lemma \bref{lemma:limit_fixed_normal_function}, there is a normal function $g$ defined for all ordinals that enumerates the fixed points of $f$. Let $h_\alpha(\beta) = g(\alpha+\beta)$ for any given ordinal $\alpha$, then $h_\alpha$~is a~normal function defined for all ordinals.
Then, given an arbitrary $\alpha$, from \emph{Axiom Schema $M$\textsubscript{1}}, there is a $\beta$ such that $\gamma = h_\alpha(\beta)$ is inaccessible. 
Because $\gamma = g(\alpha+\beta)$, thus $f(\gamma) = \gamma$. 
Since $\alpha \leq f'(\alpha)$ for any ordinal $\alpha$ and any normal function $f'$, we know that $\alpha \leq \alpha + \gamma \leq \gamma$, so $\gamma$ is inaccessible and arbitrarily large, depending on the choice of $\alpha$.
\end{proof}

To see how those schemata relate to reflection, let's introduce a stronger version of \emph{First–Order Reflection Schema}\footnote{See definition \bref{def:first_order_reflection_schema}.} from the previous chapter. 
But in order to do this, we must establish the inaccessible cardinal first.

% zkontorluj jeslti jsme to dokazali
% pak si rekneme, ze jsme to dokazali abychom videli ze existence nedosazitelneho kardinalu neni dokazatelna v ZFC
\subsection{Inaccessible Cardinal}\label{sec:inaccessible}
\begin{definition}
An uncountable cardinal $\kappa$ is \emph{inaccessible} iff it is \emph{regular} and \emph{strongly limit}. We write $In(\kappa)$ to say that $\kappa$ is an inaccessible cardinal.
\end{definition}

An uncountable cardinal that is regular and limit is called a \emph{weakly inaccessible cardinal}, we will only use the (strongly) inaccessible cardinal, but most of the results are similar for weakly inaccessibles, including higher types of ordinals that will be presented later in this chapter.

\begin{theorem}\label{theorem:inaccessible_models_zfc}
Let $\kappa$ be an inaccessible cardinal.
\beq
\langle V_\kappa, \in \rangle~\models~\sf{ZFC}
\eeq
\end{theorem}

We will prove this theorem in a way similar to \cite{KanamoriBook}.

\begin{proof}
Most of this is already done in lemma \bref{lemma:scm_s_is_limit}, we only need to verify that \emph{Replacement} and \emph{Infinity} axioms hold in $V_\kappa$.

\emph{Infinity} holds because $\kappa$ is uncountable, so $\omega \in V_\kappa$.

To verify \emph{Replacement}, let~$x$~be an element of $V_\kappa$ and $f$ a function from~$x$~to $V_\kappa$. Let $y = \{z \in V_\kappa : (\exists q \in x) f(q) = z \}$, so $y \subset V_\kappa$, it remains to show that $y \in V_\kappa$. Because $f$ is a function, we know that $|y| \leq |x| \leq \kappa$. But since $\kappa$ is regular, $\{rank(z) : z \in y\} \subseteq \alpha$ for some $\alpha < \kappa$, and so $x \in V_{\alpha+1} \in V_\kappa$. Therefore $y \in V_\kappa$.
\end{proof}

\begin{definition}{(Inaccessible Reflection Schema)}\label{def:inaccessible_reflection}\\
For every first–order formula $\varphi$, the following is an axiom:
\beq
\forall M_0 \exists \kappa (M_0 \subseteq V_\kappa \et In(\kappa) \et (\varphi(p_1, \ldots, p_n) \iff \varphi(p_1, \ldots, p_n)^{V_\kappa}))
\eeq
We will refer to this axiom schema as \emph{Inaccessible Reflection Schema}. Note that $M$ is a set, even though we often use upper–case letters for classes. 
This is due to fact that ``$M$'' is used in the same meaning in theorem \bref{theorem:first_order_reflection}.
\end{definition}

We have added the requirement that $\alpha$ is inaccessible, which trivially means that there is an inaccessible cardinal. By taking appropriate $M_0$, it can be shown that in a theory that includes the \emph{Inaccessible Reflection Schema}, there is a closed unbounded class of inaccessible cardinals. Since we know that for an inaccessible $\kappa$, $V_\kappa$ is a model of \sf{ZFC}, \emph{Inaccessible Reflection Schema} is equivalent to
\beq
\forall M_0 \exists \kappa (M_0 \subseteq V_\kappa \et \langle V_\kappa, \in \rangle~\models~\sf{ZFC} \et (\varphi(p_1, \ldots, p_n) \iff \varphi(p_1, \ldots, p_n)^{V_\kappa}))
\eeq
because we have proved in the last section that for an inaccessible $\kappa$,
\beq
\langle V_\kappa, \in \rangle~\models~\sf{ZFC}\mbox{.}
\eeq

\begin{theorem}
\emph{Inaccessible Reflection Schema} is equivalent to \emph{Axiom~schema~$F$}.
\end{theorem}

This is \emph{Theorem 4.1} in chapter 4 of \cite{DrakeBook}, also equivalent to \emph{Theorerem 3} in \cite{Levy60a}.

\begin{proof} 
Let's start by showing that \emph{Inaccessible Reflection Schema} implies \emph{Axiom schema $F$}. 
It should be clear from previous results that we can reflect two formulas to a single set, for example by taking the conjunction of universal closures of the formulas.

Given a normal function $f$ defined for all ordinals, we want to show that it has a regular fixed point. 
%Let $\varphi_1$ be the formula $f(\gamma) = \delta$ and let $\varphi_2$ be $\forall \gamma \exists \delta f(\gamma) = \delta$. 
For any ordinal $\alpha$, there is an ordinal $\kappa$ such that 
\beq
\alpha < \kappa \et In(\kappa) \et (\forall \gamma, \delta \in V_\kappa)(f(\gamma) = \delta \iff (f(\gamma) = \delta)^{V_\kappa})
\eeq
and
\beq
\alpha < \kappa \et In(\kappa) \et \forall \gamma \exists \delta (f(\gamma) = \delta) \iff (\forall \gamma \exists \delta f(\gamma) = \delta)^{V_\kappa}\mbox{.}
\eeq
Since $V_\kappa$ is the set of all sets of rank less than $\kappa$ and since every ordinal is the rank of itself, there is an inaccessible ordinal $\kappa$ such that
\beq
(\forall \gamma < \kappa)(\exists \delta < \kappa)(f^{V_\kappa} (\gamma) = \delta)\label{eq:reflected_function}\mbox{.}
\eeq
We also know that $f(\gamma) = \delta$ iff $(f(\gamma) = \delta)^{V_\kappa}$. 
Now since $\kappa$ is a limit ordinal and $f$ is continuous we get
\beq
f(\kappa) = \bigcup_{\gamma < \kappa} f^{V_\kappa}(\gamma) = \bigcup_{\gamma < \kappa} f(\gamma)\mbox{.}
\eeq
From \eref{eq:reflected_function} and the fact that $f$ is increasing, we know that $\kappa \leq \bigcup_{\gamma < \kappa} f(\gamma) \leq \kappa$. Therefore $\kappa$ is an inaccessible fixed point of $f$.

For the opposite direction, it suffices to show that since there is an inaccessible cardinal due to \emph{Axiom schema $F$}, given a first–order formula $\varphi$, there is an arbitrarily large inaccessible cardinal $\kappa$ for which 
\beq
%\varphi \iff \langle V_\kappa, \in \rangle~\models~\varphi\mbox{.}\label{eq:ch3_f_iff_m_1}
\varphi \iff \varphi^{V_\kappa}\mbox{.}\label{eq:ch3_f_iff_m_1}
\eeq
Note that the arbitrary size of $\kappa$ means given an arbitrary ordinal $\alpha$, there is a $\kappa$ satisfying $\alpha \in \kappa$ and \eref{eq:ch3_f_iff_m_1}.
In the previous chapter, in theorem \bref{theorem:first_order_reflection}, we have shown that we can easily obtain a limit ordinal satisfying \eref{eq:ch3_f_iff_m_1}. Note that since for any set $M_0$, there is such $\alpha$ that $M_0 \subseteq V_\alpha$, there is a closed unbounded class of sets satisfying \eref{eq:ch3_f_iff_m_1}, which are levels in the cumulative hierarchy, so there is a club class of $\kappa$s satisfying \eref{eq:ch3_f_iff_m_1}.

Let $f$ be a normal function defined for all ordinals that enumerates this club class, there is such $f$ by lemma \bref{lemma:normal_enumerates_club}. 
Let $g$ be the function that enumerates strong limit ordinals in $rng(f)$, there is one by lemma \bref{lemma:limit_fixed_normal_function}. 
Then $g$ has a regular fixed point $\kappa$, which is also a regular fixed point of $f$, so \eref{eq:ch3_f_iff_m_1} holds for $\kappa$.
\end{proof}

\begin{definition}{(\sf{ZMC})}\\
We will call $\sf{ZMC}$ an axiomatic set theory that contains all axioms and schemas of $\sf{ZFC}$ together with \emph{Axiom Schema $M$\textsubscript{1}}.
\end{definition}
We have decided to call it $\sf{ZMC}$, because Lévy uses $\sf{ZM}$, derived from $\sf{ZF}$, which is more intuitive, but we also need the axiom of choice, thus, $\sf{ZMC}$.

As a sidenote, we should note that \sf{ZMC} is extension of \sf{ZFC}, which is in turn an extension of \sf{S}. 
This way, reflection can be seen as a natural continuation of the \emph{Axiom of Infinity} and \emph{Replacement Schema}. % TODO Levy to hodne resi.

\subsection{Mahlo Cardinals}
We have shown that \sf{ZMC} contains arbitrarily large inaccessible cardinals. To return to reflection–style argument, is there a set that satisfies this property? To be able to properly answer this question, we have to formulate the notion of ``containing arbitrarily large cardinals'' more carefully. While we have previously used club sets, this is not an option in this case because inaccessibles don't form a club class in \sf{ZMC}\footnote{Note that cofinality of the limit of the first $\omega$ inaccessibles is $\omega$, which makes is singular.}. % we could try to formulate stronger versions of \emph{Axiom Schame $M$\textsubscript{1}}. 

%  Let's shortly review what \emph{Axiom Schema $M$\textsubscript{1}} says in order to formulate even stronger version.  % ??
We have shown earlier in this chapter that there is a simple relation between normal functions defined for all ordinals and closed unbounded classes.
We will now use a similar approach utilising normal functions.
By saying that for a class of ordinals $C$, a normal function $f$ has at least one element of $C$ in its range, we say that $C$ is stationary. 
Or, as Drake writes in \cite{DrakeBook} when dealing with the class of inaccessible cardinals, and a cardinal $\kappa$, in which inaccessibles are stationary:
\begin{displayquote}
`` The class of inaccessible cardinals is so rich that there are members $\kappa$ of the class such that no normal function on $\kappa$ can avoid this class; however we climb though $\kappa$, provided we are continuous at limits (so that we are enumerating a closed subset of $\kappa$), we shall eventually have to hit an inaccessible.''
\end{displayquote}

\begin{definition}{(Mahlo Cardinal)}\label{def:mahlo_cardinal}\\
We say that $\kappa$ is a \emph{Mahlo Cardinal} iff it is an inaccessible cardinal and the set $\{\lambda < \kappa : \lambda \mbox{ is inaccessible}\}$ is stationary in $\kappa$.
\end{definition}

Alternatively, $\kappa$ is Mahlo iff $\langle V_\kappa, \in \rangle~\models~\sf{ZMC}$ as shown above, this is also sometimes written as \emph{Ord is Mahlo}. There are also \emph{weakly Mahlo cardinals}, that are defined via weakly inaccessible cardinals below them, Mahlo cardinals are then also called \emph{strongly Mahlo} to highlight the difference, but we will only use the term \emph{Mahlo cardinal}.

Mahlo cardinals are related to reflection principles in an interesting way. Note that given a formula $\varphi$, \emph{First–Order Reflection Schema} gives us a club set of ordinals $\alpha$ such that $V_\alpha$ reflects $\varphi$, all below the first inaccessible cardinal. We have then used a different reflection schema to obtain arbitrarily high inaccessible cardinals $\kappa$ such that $V_\kappa$ refpects $\varphi$. Now we have a cardinal in which this reflection schema holds, so we are in fact reflecting reflection. Beware that this is done rather informally, because \emph{Axiom Schema $M$\textsubscript{1}} is a countable set of axioms, which can not be reflected via the schemas introduced so far. One way to deal with this would be to extend reflection for second– and possibly higher–order formulas, but we would have to be very careful with the notion of satisfaction. % TODO citace Tait, Welch
For now, let us explore where can stationary sets take us because as we have shown, their connection to reflection is quite clear.

What would happen if we strengthened \emph{Axiom Schema $M$\textsubscript{1}} to say that every normal function has a Mahlo cardinal in its range?

\begin{definition}{(hyper–Mahlo cardinal)}\label{def:hyper_mahlo_cardinal}\\
We say that $\kappa$ is a \emph{hyper–Mahlo cardinal} iff it is inaccessible and the set 
\beq
\{\lambda < \kappa : \lambda \mbox{ is Mahlo}\}
\eeq
is stationary in $\kappa$.
\end{definition}

\begin{definition}{(hyper–hyper–Mahlo cardinal)}\label{def:hyper_hyper_mahlo_cardinal}\\
We say that $\kappa$ is a \emph{hyper–hyper–Mahlo cardinal} iff it is inaccessible and the set 
\beq
\{\lambda < \kappa : \lambda \mbox{ is hyper–Mahlo}\}
\eeq
is stationary in $\kappa$.
\end{definition}

It is clear that one can continue in this direction, but the nomenclature gets increasingly confusing even if we rewrite them as \emph{hyper\textsuperscript{$\alpha$}–Mahlo cardinals} instead of repeating the prefix.
To see there is a more elegant way to reach those cardinals, we will now establish an operation that elegantly exhausts all such cardinals.

\begin{definition}{(Mahlo Operation)}\label{def:mahlo_operation}\\
Let $A$ be a class of ordinals. Let
\beq
H(A) = \{\alpha \in A: A \cap \alpha \mbox{ is stationary in }\alpha\}\mbox{.}
\eeq
We call $H$ the \emph{Mahlo's operation}.
\end{definition}

If we pick for $A$ the class of all inaccessible cardinals, $H(A)$ is the class of Mahlo cardinals.
It is easy to see that is $A$ is the class of all $\alpha$–Mahlo cardinals, $H(A)$ is the class of $\alpha+1$–Mahlo cardinals, $H(H(A))$ is the class of $\alpha+2$–Mahlo cardinals and so on.

\begin{definition}{(Iterated Mahlo Operation)}\label{def:iterated_mahlo_operation}\\
Let $A$ be a class of ordinals. We shall extend the Mahlo operation in the following way:
\bce[(i)]
\item $H^0(A) = A$,
\item $H^{\alpha+1}(A) = H(H^{\alpha}(A))$,
\item $H^{\lambda}(A) = \bigcap_{\alpha < \lambda} H^{\alpha}(X)$ for limit $\lambda$.
\ece
\end{definition}

Clearly if $A$ is the class of inaccessibles, $H^{\alpha}(A)$ is the class of $\alpha$–Mahlo cardinals. To get to hyper–Mahlo cardinals, we can diagonalise the operation.

\begin{definition}{(Diagonal Mahlo Operation)}\label{def:diagonal_mahlo_operation}\\
Let $A$ be a class of ordinals. Then the \emph{diagonal Mahlo operation} is defined as follows:
\beq
H^{\Delta}(A) = \{\alpha \in Ord: \forall \beta < \alpha (\alpha \in H^{\beta}(X))\}\mbox{.}
\eeq
\end{definition}

We can further diagonalise the diagonal version and continue this process ad libitum in order to reach all large cardinals accessible \emph{from below}. 
To see what is meant by \emph{from below}, note that the approach that led us to the \emph{Mahlo operation} was taking a property, for example regularity, that is already available in our current theory, e.g. \sf{ZFC}, and making an assertion of the height of the universe such that there are ``enough'' other ordinals holding this property in a sense that a normal function defined on ordinals inevitably has at least one such ordinal in its range.

\subsection{Indescribable Cardinals}

Indescribability is another approach towards large cardinals that is based on reflection. 
We will briefly introduce the basic definitions and show that it yield large cardinals, but most of them are not reachable from below in a sense established at the end of previous subsection.
Most of the results presented in this subchapter come from \cite{KanamoriBook}.
Since this chapter uses higher–order logic, we need to introduce the hierarchy of formulas first.

\begin{definition}{(Higher–Order Variables)}\label{def:higher_order_variables}\\
Let $M$ be a structure and $D$ its domain. In first–order logic, variables range over individuals, that is, over elements of $D$. We shall call those \emph{type~1 variables} for the purposes of higher–order logic. Type~2 variables then range over collections, that is, the elements of $\power{D}$. Generally, type $n$ variables are defined for any $n \in \omega$ such that they range over $\mathscr{P}^{n-1}(D)$.
\end{definition}
We will use lowercase latin letters for type~1 variables for backward compatibility with first–order logic, type~2 variables will be represented by uppercase letters, mostly $P, X, Y, Z$, higher–order variables won't be needed in this thesis. If we wanted to define satisfaction for second–order formulas in a model $\la V_\alpha, \in \ra$ that we have often used in this thesis, type~2 variables would be interpreted to range over a set is isomorphic to $V_{\alpha+1}$\footnote{It might be useful to keep a separate version instead of using $V_{\alpha+1}$ so that we can distinguish between sets and classes that turn out to have the same extension. See \cite{Koellner2009ORP} for details.}.

\begin{definition}{(Full Prenex Normal Form)}\label{def:pnf}\\
We say a formula is in the \emph{prenex normal form} if it is written as a block of quantifiers followed by a quantifier–free part.\\
We say a formula is in the \emph{full prenex normal form} if it is written in \emph{prenex normal form} and if there are type $n+1$ quantifiers, they are written before type $n$ quantifiers.
\end{definition}
It is an elementary that every formula is equivalent to a formula in the full prenex normal form.

% ===================================================== TODO check ===============================================
\begin{definition}{(Hierarchy of Formulas)}\label{def:analytical_hierarchy}\\
Let $\varphi$ be a formula in the prenex formal form.
\bce[(i)]
\item We say $\varphi$ is a $\Delta^0_0$–formula if it contains only bounded quantifiers.
\item We say $\varphi$ is a $\Sigma^0_0$–formula or a $\Pi^0_0$–formula if it is a $\Delta^0_0$–formula.
\item We say $\varphi$ is a $\Pi^{m+1}_0$–formula if it is a $\Pi^m_n$– or $\Sigma^m_n$–formula for any $n \in \omega$ or if it is a $\Pi^m_n$– or $\Sigma^m_n$–formula with additional free variables of type $m+1$.
\item We say $\varphi$ is a $\Sigma^m_0$–formula if it is a $\Pi^m_0$–formula.
\item We say $\varphi$ is a $\Sigma^m_n+1$–formula if it is of a form $\exists P_1, \ldots, P_i \psi$ for any non–zero $i$, where $\psi$ is a $\Pi^m_n$–formula and $P_1, \ldots, P_i$ are type $m+1$ variables.
\item We say $\varphi$ is a $\Pi^m_n+1$–formula if it is of a form $\forall P_1, \ldots, P_i \psi$ for any non–zero $i$, where $\psi$ is a $\Sigma^m_n$–formula and $P_1, \ldots, P_i$ are type $m+1$ variables.
\ece
\end{definition}


\begin{definition}{(Describability)}\label{def:describability}\\
We say an ordinal $\alpha$ is described by a sentence $\varphi$ in the language $\mathscr{L}$ with relation symbols $P_1, \ldots, P_n$ given iff
\begin{equation}
\langle V_\alpha, \in, P_1, \ldots, P_n \rangle~\models~\varphi
\end{equation}
but for every $\beta < \alpha$
\begin{equation}
\langle V_\beta, \in, P_1 \cap V_\beta, \ldots, P_n \cap V_\beta \rangle \not\models \varphi\mbox{.}
\end{equation}
\end{definition}

For the definition of a $\Pi^m_n$–formula and a $\Sigma^m_n$–formula, see definition \bref{def:analytical_hierarchy}.

\begin{definition}{($\Pi^m_n$–Indescribable Cardinal)}\label{def:pi_mn_indescribable}\\
We say that $\kappa$ is $\Pi^m_n$–indescribable iff it is not described by any $\Pi^m_n$–formula.
\end{definition}
\begin{definition}{($\Sigma^m_n$–Indescribable Cardinal)}\label{def:sigma_mn_indescribable}\\
We say that $\kappa$ is $\Sigma^m_n$–indescribable iff it is not described by any $\Sigma^m_n$–formula.
\end{definition}

To see that this notion is based in reflection, let us recall the opening quote of this thesis by Gödel which says \emph{``The Universe of sets cannot be uniquely characterised (i.~e.~distinguished from all its initial elements) by any internal structural property of the membership relation on it.''}. A cardinal $\kappa$ is $\Pi^m_n$–indescribable\footnote{This holds for $\Sigma^m_n$–formulas alike.} iff every $\Pi^m_n$–formula fails to describe $V_\kappa$ and describes an initial segment instead.
In a sense, $V_\kappa$ reflects the ``property''\footnote{In this case, we are not using the word to refer to a definable class, but on a meta level to refer to a property expressible in the natural language, hence the quotation marks.} of indescribability of the universal class with respect to certain classes of formulas.

% Since we are interested inaccessing cardinals from below, we will limit ourselves to $\Pi^1_n$–formulas, with the exception of the measurable cardinal, that is included for context.

\begin{lemma}
Let $\kappa$ be a cardinal, then the following holds for any $n \in \omega$. $\kappa$ is $\Pi^1_n$–indescribable iff $\kappa$ is $\Sigma^1_{n+1}$–indescribable.
\end{lemma}

\begin{proof}
The forward direction is obvious, we can always add a spare quantifier over a type~2 variable to turn a $\Pi^1_n$ formula $\varphi$ into a $\exists P \varphi$ which is then a $\Sigma^1_{n+1}$–formula.\footnote{Note that unlike in previous sections, it is worth noting that $\varphi$ is now a sentence so we don't have to worry whether $P$ is free in $\varphi$.}

To prove the opposite direction, suppose that $\langle V_\kappa, \in \rangle~\models~\exists X \varphi(X)$ where $X$ is a type~2 variable and $\varphi$ is a $\Pi^1_n$–formula with one free variable of type~2. 
This means that there is a set $S \subseteq V_\kappa$ that is a witness of $\exists X \varphi(X)$, in other words, $\varphi[S]$ holds. 
We can replace every occurence of $X$ in $\varphi$ by a new predicate symbol $S$, this allows us to say that $\kappa$ is $\Pi^1_n$–indescribable (with respect to $\langle V_\kappa, \in, R, S \rangle$).\footnote{A different yet interesting approach is taken by Tate in \cite{Tait_constructingcardinals}. He states that for $n\geq 0$, a formula of order $\leq n$ is called a $\Pi^n_0$ and a $\Sigma^n_0$ formula. Then a $\Pi^n_{m+1}$ is a formula of form $\forall Y \psi(Y)$ where $\psi$ is a $\Sigma^n_m$ formula and $Y$ is a variable of type $n$. Finally, a $\Sigma^n_{m+1}$ is the negation of a $\Pi^n_m$ formula. So the above holds ad definitio.}
\end{proof}

The above lemma makes it clear that, without the loss of generality, we can suppose that all formulas with no higher than type~2 variables are $\Pi^1_n$–formulas.

\begin{lemma}\label{lemma:inaccessible_clubset}
If $\kappa$ is an inaccessible cardinal and given $R \subseteq V_\kappa$, then the following is a club set in $\kappa$:
\begin{equation}
\{\alpha \in \kappa : \langle V_\alpha, \in, R \cap V_\alpha \rangle \prec \langle V_\kappa, \in, R \rangle \}\label{eq:inacc_lemma_set}\mbox{.}
\end{equation}
\end{lemma}

\begin{proof}
To see that \eref{eq:inacc_lemma_set} is closed, let us recall that a $A \subseteq \kappa$ is closed iff for every ordinal $\alpha$ such that $\emptyset < \alpha < \kappa$, it holds that if $A \cap \alpha$ is unbounded in $\alpha$ then $\alpha \in A$. Since $\kappa$ is an inaccessible cardinal, thus strong limit, it is closed under limits of sequences of ordinals smaller than $\kappa$.
%TODO neco s $V_\kappa$, ze je tranzitivni a tak jso vsechny $V_\alpha$ pro $\alpha<\kappa$ $V_\alpha \in V_\kappa$
In order to verify that it is unbounded, we will use a recursively defined $\kappa$–sequence $\la \alpha_0, \alpha_1, \ldots \ra$
to build $\la V_\alpha, \in, R \cap V_\alpha \ra$, an elementary substructure of $\la V_\kappa, \in, R \ra$ such that $\alpha > \alpha_0$ for an arbitrary ordinal $\alpha_0 < \kappa$.
% that is built above an arbitrary $V_{\alpha_0}$, $\alpha_0 <\kappa$.
Let us fix one such $\alpha_0$. Given $\alpha_n$, $\alpha_{n+1}$ is defined as the least $\beta$, $\alpha_n \leq \beta$ that satisfies 
the following for any formula $\varphi$ for $p_1, \ldots, p_m \in V_{\alpha_{n}}, m \in \omega$:
\begin{equation}
\begin{gathered}
\mbox{If }\langle V_\kappa, \in, R \rangle~\models~\exists x \varphi(p_1, \ldots, p_n)\mbox{,}\\
\mbox{then }\exists x \in V_\beta \mbox{ such that }\langle V_\kappa, \in, R \rangle~\models~\varphi(x, p_1, \ldots, p_n)\mbox{.}
\end{gathered}
\end{equation}

Let $\alpha = \bigcup_{n < \omega} \alpha_n$. Then 
\beq
\langle V_\alpha, \in, R \cap V_\alpha \rangle \prec \langle V_\kappa, \in, R \rangle\mbox{,}
\eeq
in other words, for any $\varphi$ with given arbitrary parameters $p_1, \ldots, p_n \in V_\alpha$, it holds that
\beq
\langle V_\alpha, \in, R \cap V_\alpha \rangle~\models~\varphi(p_1, \ldots, p_n) \iff \langle V_\kappa, \in, R \rangle~\models~\varphi(p_1, \ldots, p_n)\mbox{.}
\eeq
Which should be clear from the construction of $\alpha$.
\end{proof}

\begin{theorem}
Let $\kappa$ be an ordinal. The following are equivalent.
\bce[(i)]
\item $\kappa$ is inaccessible.
\item $\kappa$ is $\Pi^1_0$–indescribable.
\ece
\end{theorem}

Note that $\Pi^1_0$ formulas are those that contain zero unbound quantifiers over type–2 variables, they are in fact first–order formulas, but with additional type~2 free variables allowed.

\begin{proof}
$\Pi^1_0$–sentences contain type~2 variables, but only type~1 quantifiers. We want to prove that $\kappa$ is an inaccessible cardinal iff whenever a formula tries to describe $\kappa$ in the sense of definition \bref{def:describability}, the formula fails to do so and describes a initial segment thereof instead.
We have already shown in theorem \bref{theorem:inaccessible_models_zfc} that there is no way to climb the cumulative hierarchy to the height of an inaccesible cardinal via first–order formulas in $\sf{ZFC}$. We will now prove that adding unqantified type~2 variables does not make it possible, note that all of the axiom schemata used in the previous chapter can be rewritten to use a type~2 variable instead of a given function.

For (i)$\then$(ii), suppose that $\kappa$ is inaccessible.

Then there is, by lemma \bref{lemma:inaccessible_clubset} a club set of ordinals $\alpha$ such that $V_\alpha$ is an elementary substructure of $V_\kappa$. 
For $\kappa$ to be $\Pi^1_0$–indescribable, we need to make sure that given an arbitrary $\Pi^1_0$–formula $\varphi$ satisfied in the structure $\langle V_\kappa, \in, R \rangle$, there is an ordinal $\alpha < \kappa$, such that $\langle V_\alpha, \in, R \cap V_\alpha \rangle~\models~\varphi$. But this follows from the definition of elementary substructure.

For (ii)$\then$(i), suppose $\kappa$ is not inaccessible, so it is either singular, or there is a cardinal $\nu < \kappa$ such that $\kappa \leq \power{\nu}$ or $\kappa=\omega$. 


%For the successor case, there is some $\nu$ so that $\nu+1=\kappa$. 
%Let us take $R = \{\nu\}$ and $\varphi = \exists x \psi(x)$ such that
%\begin{eqaution}
Suppose $\kappa$ is singular. Then there is a cardinal $\nu~<~\kappa$ and a function $f:~\nu~\then~\kappa$ such that $rng(f)$ is cofinal in $\kappa$. Since $f \subseteq V_\kappa$, we can add $f$ as a relation to the language. We can do the same with $\{\nu\}$. That means $\langle~V_\kappa,~\in,~P_1,~P_2\ra$ with $P_1~=~f, P_2~=~\{\nu\}$ is a structure.
Let 
\beq
\varphi = (P_1 \neq \emptyset \et rng(P_1) = P_2)\footnote{$rng(x)=y$ is a first–order formula, see definition \bref{def:rng}.}\mbox{.}
\eeq
Since for every $\alpha~<~\nu$, $P_1 \cap V_\alpha = \emptyset$, $\varphi$ is false and therefore describes $\kappa$. That contradicts the fact that $\kappa$ was supposed to be $\Pi^1_0$–indescribable, but $\varphi$ is a first–order formula.

Suppose there is a cardinal $\nu$ satisfying $\kappa \leq \power{\nu}$. Let there be a function $f: \power{\nu} \then \kappa$ that is onto. Then, like in the previous paragraph, we can obtain a structure $\langle V_\kappa, \in, P_1, P_2 \rangle$, where $P_1 = f$ like before, but this time $P_2 = \power{\nu}$. Again, 
\beq
\varphi = (P_1 \neq \emptyset \et rng(P_1) = P_2)
\eeq
describes $\kappa$.

Finally, suppose $\kappa = \omega$, then the first-order sentence $\varphi = \forall x \exists y (x \in y)$ describes $\kappa$, which is a contradiction.
\end{proof}

Generally, it should be clear that it a cardinal $\kappa$ is $\Pi^m_n$–indescribable, it is also $\Pi^{m'}_{n'}$–indescribable for every $m'<m, n'<n$. By the same line of thought, if a cardinal $\kappa$ satisfies the property implied by $\Pi^m_n$–indescribability, it satisfies all properties implied by $\Pi^{m'}_{n'}$–indescribability for $m'<m, n'<n$. For example, if $\kappa$ is $\Pi^m_n$–indescribable for $m \geq 1$ then it is also an inaccessible cardinal.

% TODO pozorovani ze kdyz je $\kappa$ $\Pi$

\begin{theorem}\
If a cardinal $\kappa$ is $\Pi^1_1$–indescribable, then it is a Mahlo cardinal.
\end{theorem}

\begin{proof}
Assuming that $\kappa$ is $\Pi^1_1$–indescribable, we want to prove that every club set of in $\kappa$ contains an inaccessible cardinal. 

Consider the following $\Pi^1_1$–sentence $\varphi$:
\beq
\begin{gathered}
\varphi = \forall P (``\mbox{P is a function}''\then \forall x \exists y \forall z (z \in y \iff (\exists q \in x)(P(x, y, p_1, \ldots, p_n))))\\
\et \forall x \exists y \forall z (z \in y \iff z \subseteq x)
\end{gathered}
\eeq
%\begin{gathered}\label{eq:inac}
% \forall P (\mbox{``$P$ is a function''} \et \exists x(x = dom(P) \lor \power{x} = dom(P)) \then\\
%\then \exists y(y = rng(P)))
%\end{gathered}
%\end{equation}
where $P$ is a type~2 variable and the rest are type~1 variables,  ``$P$ is a function'' is a first–order formula defined in definition \bref{def:function}. 
As has been shown earlier in this chapter, given a cardinal $\mu$, the following holds if and only if $\mu$ is inaccessible:
\begin{equation}
\langle V_\mu, \in \rangle~\models~\varphi\mbox{.}
\end{equation}

Now fix an arbitrary $C \subset \kappa$, a club set in $\kappa$. We want to show that it contains an inaccessible cardinal. 
Since $C$ is a subset of $\kappa$ and therefore a subset of $V_\kappa$, we can use the structure $\langle V_\kappa, \in, C \rangle$ instead of $\langle V_\kappa, \in \rangle$. 
Then the following holds:
\begin{equation}
\langle V_\kappa, \in, C \rangle~\models~\varphi \et \mbox{``$C$ is unbounded''.}\footnote{``$C$ is unbounded'' is a first–order formula, see definition \bref{def:unbounded_class}.}
\end{equation}
Note that this holds because $\kappa$ is $\Pi^1_1$–indescribable, and therefore also $\Pi^1_0$–indescribable.
So $\kappa$ is itself inaccessible and therefore $\langle V_\kappa, \in, C \rangle~\models~\varphi$.

Since  $\kappa$ is $\Pi^1_1$–indescribable and $\varphi \et \mbox{``$C$ is unbounded''}$ is equivalent to a $\Pi^1_1$–formula, there must be an ordinal $\alpha$ that satisfies
\begin{equation}
\langle V_\alpha, \in, C \cap V_\alpha \rangle~\models~\varphi \et \mbox{``$C$ is unbounded'',}
\end{equation}
which implies that $\alpha$ is inaccessible; it is regular because it reflects \emph{Replacement} and it is limit because if $\alpha$ were a successor ordinal, it couldn't contain an unbounded class of ordinals.

We only need to verify that $\alpha \in C$, which is clear from the fact that $C$ is a club set in $\kappa$ and it is unbounded in $\alpha$.
\end{proof}

There is an even stronger large cardinal property implied by $\Pi_1^1$–indescribability that is based on reflection.

\begin{definition}{(Extension Property)}\label{def:extension_property}\\
We say a cardinal $\kappa$ has the \emph{extension property} iff for all $U \subset V_\kappa$ there exists a transitive set $X$ such that $\kappa \in X$, and a set $S \subset X$, such that $(V_\kappa, \in, U)$ is an elementary substructure of $(X, \in, S)$.
\end{definition}

\begin{definition}{(Weakly Compact Cardinal)}\label{def:weakly_compact_cardinal}\\
We say that a cardinal $\kappa$ is \emph{weakly compact} iff it has the extension property.
\end{definition}

\begin{theorem}\
A cardinal $\kappa$ is $\Pi_1^1$–indescribable iff it is weakly compact.
\end{theorem}
For the proof, see \cite{KanamoriBook}.
Note that the extension property is also very similar to reflection

We will now introduce the measurable cardinal, which is not based on reflection from below in our sense, but illustrates the fact that indescribability leads to cardinals that contradict \emph{Axiom of Constructibility}, that will be introduced right after the measurable cardinal.

\begin{definition}{(Ultrafilter)}\\
Given a set $x$, we say $U \subset \power{x}$ is an \emph{ultrafilter} over $x$ iff all of the following hold:
\bce[(i)]
\item $\emptyset \not\in U$,
\item $\forall y, z (y \subset x \et z \subset x \et y \subset z \et y \in U \then z \in U)$,
\item $(\forall y, z \in U)(y \cap z) \in U$,
\item $\forall y (y \subset x \then (y \in U \lor (x \setminus y) \in U))$.
\ece
\end{definition}

\begin{definition}{($\kappa$–Complete Ultrafilter)}\\
We say that an ultrafilter $U$ is $\kappa$–complete iff it is closed under intersection of $\kappa$–many elements. More precisely,
\beq
(\forall \gamma < \kappa)(\{a_\alpha : \alpha < \gamma \} \subseteq U \then \bigcup_{\alpha < \gamma} a_\alpha \in U)\mbox{.}
\eeq
\end{definition}

\begin{definition}{(Measurable Cardinal)}\\
We say that a cardinal $\kappa$ is a \emph{measurable cardinal} iff there is a $\kappa$–complete ultrafilter over $\kappa$.
\end{definition}

\begin{theorem}
Let $\kappa$ be a cardinal. If $\kappa$ is a measurable cardinal then the following hold:
\bce[(i)]
\item $\kappa$ is $\Pi^2_1$–indescribable.
\item Given $U$, a normal ultrafilter over $\kappa$, a relation $R \subseteq V_\kappa$ and a $\Pi^2_1$–formula $\varphi$ such that $\langle V_\kappa, \in, R \rangle \models \varphi$, then
\beq
\{ \alpha < \kappa : \langle V_\alpha, \in, R \cap V_\alpha \rangle \models \varphi \} \in U\mbox{.}
\eeq
\ece
\end{theorem}
For a proof, see \emph{Proposition 6.5} in \cite{KanamoriBook}.

%\begin{theorem}
%If $\kappa$ is a measurable cardinal and $U$ is a normal ultrafilter over $\kappa$, the following holds:
%\begin{equation}
%\{ \alpha < \kappa: \mbox{"$\alpha$ is totally indescribable"}\} \in U\mbox{.}
%\end{equation}
%\end{theorem}
%For a proof, see \emph{Proposition 6.6} in \cite{KanamoriBook}.

\subsection{The Constructible Universe}

The constructible universe, denoted $L$, is a cumulative hierarchy of sets, presented by Kurt Gödel in his paper \cite{Godel1940consistency}.
Assertion of its equality to the \emph{Von Neumann's hierarchy}, $V=L$, is called the \emph{Axiom of Constructibility}. 
The axiom implies $GCH$ and $AC$ and contradicts the existence of some\ large cardinals, our goal is to decide whether those introduced earlier are among them.

On order to formally establish this class, we need to formalise the notion of definability first. 
\begin{definition}{(Definability)}\label{def:definability}\\ % musi ta fle byt prvoradova?
We say that a set $X$ is \emph{definable} over a model $\langle M, \in \rangle$ if there is a formula $\varphi$ together with parameters $p_1, \ldots, p_n \in M$ such that
\begin{equation}
X = \{x: x \in M \et \langle M, \in \rangle~\models~\varphi(x, p_1, \ldots, p_n)\}
\end{equation}
\end{definition}

\begin{definition}{(The Set of Definable Subsets)}\label{def:definable_powerset}\\
The following is a set of all definable subsets of a given set $M$, denoted Def($M$).
\begin{equation}
\begin{gathered}
Def(M) = \{\{y : x \in M \et \langle M, \in \rangle~\models~\varphi(y, u_1, \ldots, i_n) \} :\\
\mbox{ $\varphi$ is a~first–order formula, }p_1, \ldots, p_n \in M \}
\end{gathered}
\end{equation}
\end{definition}

We will use $Def(M)$ in the following construction in the way the power set operation is used when constructing the usual Von Neumann's hierarchy of sets\footnote{For that reason, some authors use $\mathscr{P}^{*} (M)$ instead of $Def(M)$, see section 11 of \cite{PinterBook} for one such example.}.

% Now we can recursively build $L$.
\begin{definition}{(The Constructible Universe)}\label{def:constructible_universe}\\
The \emph{constructible universe} is a collection of sets similar to the Von Neumann's hierarchy but consisting only of definable sets.
\bce[(i)]
\item
\beq
L_0 = \emptyset\mbox{,}
\eeq

\item
\beq
L_{\alpha+1} = Def(L_{\alpha})\mbox{ for any ordinal $\alpha$,}
\eeq
\item
\beq
L_{\lambda} = \bigcup_{\alpha < \lambda} L_{\alpha}\mbox{ For a~limit ordinal }\lambda\mbox{,}
\eeq
\item
\beq
L = \bigcup_{\alpha\in Ord} L_{\alpha}\mbox{.}
\eeq
\ece
\end{definition}

Note that while $L$ bears very close resemblance to $V$, the difference is, that in every successor step of constructing $V$, we take every subset of $V_\alpha$ to be $V_{\alpha+1}$, whereas $L_{\alpha+1}$ consists only of definable subsets of $L_\alpha$. Also note that $L$ is transitive.

%In order to 
\begin{theorem}
Let $L$ be as in definition \bref{def:constructible_universe}.
\begin{equation}
\la L, \in \ra \mbox{ is a model of \sf{ZFC}}
\end{equation}
\end{theorem}
For details, refer to Theorem 13.3 in \cite{JechBook}.

\begin{definition}{(Constructibility)}\\
The axiom of constructibility states that every set is constructible. It is usually denoted as $L = V$.
\end{definition}

Without providing a proof, we will introduce two important results established by Gödel in \cite{Godel1940consistency}. 
% \sf{ZF} stands for Zermelo–Fraenkel set theory as introduced in definition \bref{def:zf}. % wtf

\begin{theorem}{(Constructibility $\then$ Choice)}
\begin{equation}
\sf{ZF} \proves \mbox{\emph{Constructibility}} \then \mbox{\emph{Axiom of Choice}} 
\end{equation}
\end{theorem}

The $GCH$ refers to the \emph{Generalised Continuum Hypothesis}, see definition \bref{def:gch}.
\begin{theorem}{(Constructibility $\then$ Generalised Continuum Hypothesis)}\label{theorem:l_then_gch}
\begin{equation}
\sf{ZF} \proves \mbox{\emph{Constructibility}} \then \mbox{\emph{GCH}} 
\end{equation}
\end{theorem}
It is worth mentioning that Gödel's proof of \emph{Construcibility} $\then$ \emph{GCH} featured the first formal use of a reflection principle. 
For the actual proofs, see for example \cite{Kunen_independence},

Since \emph{GCH} implies that $\kappa$ is a limit cardinal iff $\kappa$ is a strong limit cardinal for every $\kappa$, the distinctions between inaccessible and weakly inaccessible cardinals as well as between Mahlo and weakly Mahlo cardinals vanish.

% =============================================================================================

\begin{theorem}{(Inaccessibility in $L$)}\label{theorem:inaccessible_in_l}\\
Let $\kappa$ be an inaccessible cardinal. Then $In(\kappa)^L$.
\end{theorem}
\begin{proof}
We want to show that the following are all true for an inaccessible cardinal $\kappa$:
\bce[(i)] 
\item $\mbox{``$\kappa$ is a cardinal''}^L$,
\item $(\omega < \kappa)^L$,
\item $\mbox{``$\kappa$ is regular''}^L$,
\item $\mbox{``$\kappa$ is limit''}^L$.\footnote{While inaccessible cardinals are strong limit cardinals, since \emph{GCH} holds in $L$, $\mbox{``$\kappa$ is limit''}^L$,
implies $\mbox{``$\kappa$ is strong limit''}^L$.}
\ece

Suppose $\mbox{``$\kappa$ is not a cardinal''}^L$ holds, then there is a cardinal $\mu$, $\mu < \kappa$ and a function $f:\mu\then\kappa$, $f \in L$, such that $\mbox{``$f:\mu\then\kappa$ is onto''}^L$. But since ``$f$ is onto'' is a $\Delta_0$ formula and $\Delta_0$ formulas are are absolute in transitive structures\footnote{See lemma \bref{lemma:delta_0_absoluteness}.} and $L$ is a transitive class, $\mbox{``$f$ is onto''}^L \iff \mbox{``$f$ is onto''}$, this contradicts the fact that $\kappa$ is a cardinal.
$(\omega < \kappa)^L$ holds because $\omega \in \kappa$ and because ordinals remain ordinals in $L$, so $(\omega \in \kappa)^L$.

In order to see that $\mbox{``$\kappa$ is regular''}^L$, we can repeat the argument by contradiction used to show that $\kappa$ is a cardinal in $L$. If $\kappa$ was singular, there is a $\mu < \kappa$ together with a function $f: \mu \then \kappa$ that is onto, but since ``$f$ is onto'' implies $\mbox{``$f$ is onto''}^L$, we have reached a contradiction with the fact that $\kappa$ is regular, but singular in $L$.

It now suffices to show that $\mbox{``$\kappa$ is a limit cardinal''}^L$. That means, that for any given $\lambda<\kappa$, we need to find an ordinal $\mu$ such that $\lambda < \mu < \kappa$ that is also a cardinal in $L$. But since cardinals remain cardinals in $L$ by an argument with surjective functions just like above, it holds.\end{proof}

\begin{theorem}{(Mahloness in $L$)}\label{theorem:mahlo_in_l}\\
Let $\kappa$ be a Mahlo cardinal. Then $\mbox{``$\kappa$ is Mahlo''}^L$.
\end{theorem}
% http://math.stackexchange.com/questions/1791631/reference-mahlo-cardinals-remain-mahlo-in-l/1792486#1792486
% TODO citace webu?

\begin{proof}
Let $\kappa$ be a Mahlo cardinal. From the definition of Mahloness in definition \bref{def:mahlo_cardinal}, it should be clear that we want prove that $\kappa$ is inaccessible in $L$ and 
\begin{equation}
\mbox{``The set }\{\alpha : \alpha \in \kappa \et \mbox{'$\alpha$ is inaccessible'}\}\mbox{ is stationary in $\kappa$''}^L
\end{equation}

Since we have shown that an inaccessible cardinals remain inaccessible in $L$ in the previous theorem, $In(\kappa)^L$ holds.

Now consider the two following sets:
\beq
S = \{\alpha \in \kappa : In(\alpha)\}\label{eq:mahloness_l_eq_1}
\eeq
\beq
T = \{\alpha \in \kappa : In(\alpha)^L\}\label{eq:mahloness_l_eq_2}
\eeq
Since inaccessible cardinals are inaccessible in $L$ from theorem \bref{theorem:inaccessible_in_l}, $S \subseteq T$.
So if $T$ is stationary in $\kappa$, we are done. Suppose for contradiction that it is not the case. 
Therefore there is a $C \subset \kappa$ satisfying $\mbox{``$C$ is a club set in $\kappa$''}^L$, but it is the case that $T \cap C = \emptyset$.
But because $\mbox{``$C$ is a club set in $\kappa$''}$ is equivalent to a $\Delta_0$ formula, 
\beq
\mbox{``$C$ is a club set in $\kappa$''}^M \iff \mbox{``$C$ is a club set in $\kappa$'',}
\eeq
ergo $C$ is a club set in $\kappa$. But since it has o intersection with $T$, it can't have an intersection with a subset thereof, which contradicts the fact that $S$ is stationary in $\kappa$.

$\kappa$ remains Mahlo in $L$.
\end{proof}

It should be clear that the above process can be iterated over again. Since Mahlo cardinals are absolute in $L$, the same argument using stationary sets can be carried out for hyper–Mahlo cardinals and so on. It is clear that since a regular and an inaccessible cardinal in consistent with \emph{Constructibility}, so should be the higher properties acquired from assuring the existence of regular, inaccessible and Mahlo fixed points of normal functions.


\begin{theorem}
If there is a measurable cardinal, then $V \neq L$.
\end{theorem}
This is proved in \cite{scott_measurable_constructible} or \cite{KanamoriBook}.
% Measurable cardinals yield inconsistency with the \emph{Axiom of Constructibility}, which was shown by Dana S. Scott in his article \cite{scott_measurable_constructible}. 

\subsection{Conclusion}
To have an intuitive idea of why apart from measurability, every large cardinal property we have established is absolute in $L$, let us stress that measurability is the only one that does not deal with the height of the cumulative hierarchy of sets.
The assertion of the existence of an inaccessible cardinal can be informally rephrased as
``The universe of all sets is so big in terms of height, there are ordinals unreachable by the power set operation''\footnote{This approach is embodied in the definition of \sf{Q}–inaccessibility used by Lévy, see definition \bref{def:levy_inaccessible_q}, that can be understood as ``given a set theory with some means of traversing the cumulative hierarchy upwards, a cardinal is inaccessible with respect to \sf{Q} if it can't be reached by those means alone''.}. 
Gödel's Constructible universe deals only with the width of the universe, which is kept as small as possible, so there is no way it can be inconsistent with assertions that deal with height and have no implications in terms of width. Similarly, the Mahlo operation only deals with ordinals, therefore it's not surprising that it has no implications on width of the universe alone. 
This is not the case with measurability. 
Measurability is such a strong statement that even though it seems to explicitly speak of height only, 
the existence of a measurable cardinal implies the existence of non–constructible subsets of $\omega$\footnote{See \cite{DrakeBook}, p. 196.}.

% TODO ze meritelny resi sirku a ne vysku, ale nase karidnaly mluvi o vysce WATT