Set Theory

en · official · sha256:1a99eb58f80ec938bf7d67eda65197e2b702f8a259411fed9c6840a7f083f456

\section{Everything is a set} \label{section-sets-everything} \noindent Most mathematicians think of set theory as providing the basic foundations for mathematics. So how does this really work? For example, how do we translate the sentence ``$X$ is a scheme'' into set theory? Well, we just unravel the definitions: A scheme is a locally ringed space such that every point has an open neighbourhood which is an affine scheme. A locally ringed space is a ringed space such that every stalk of the structure sheaf is a local ring. A ringed space is a pair $(X, \mathcal{O}_X)$ consisting of a topological space $X$ and a sheaf of rings $\mathcal{O}_X$ on it. A topological space is a pair $(X, \tau)$ consisting of a set $X$ and a set of subsets $\tau \subset \mathcal{P}(X)$ satisfying the axioms of a topology. And so on and so forth. \medskip\noindent So how, given a set $S$ would we recognize whether it is a scheme? The first thing we look for is whether the set $S$ is an ordered pair. This is defined (see \cite{Jech}, page 7) as saying that $S$ has the form $(a, b) := \{\{a\}, \{a, b\}\}$ for some sets $a, b$. If this is the case, then we would take a look to see whether $a$ is an ordered pair $(c, d)$. If so we would check whether $d \subset \mathcal{P}(c)$, and if so whether $d$ forms the collection of sets for a topology on the set $c$. And so on and so forth. \medskip\noindent So even though it would take a considerable amount of work to write a complete formula $\phi_{scheme}(x)$ with one free variable $x$ in set theory that expresses the notion ``$x$ is a scheme'', it is possible to do so. The same thing should be true for any mathematical object.

Referencing norms: SmallCategoryByObjectSet, objects_form_a_set, is_set

en · official · sha256:990661ab1294c28899898646e93c5ea4246e988e7f9bde2ecc5d54f0bc41fbb9

\section{Classes} \label{section-classes} \noindent Informally we use the notion of a {\it class}. Given a formula $\phi(x, p_1, \ldots, p_n)$, we call $$ C = \{x : \phi(x, p_1, \ldots, p_n)\} $$ a {\it class}. A class is easier to manipulate than the formula that defines it, but it is not strictly speaking a mathematical object. For example, if $R$ is a ring, then we may consider the class of all $R$-modules (since after all we may translate the sentence ``$M$ is an $R$-module'' into a formula in set theory, which then defines a class). A {\it proper class} is a class which is not a set. \medskip\noindent In this way we may consider the category of $R$-modules, which is a ``big'' category---in other words, it has a proper class of objects. Similarly, we may consider the ``big'' category of schemes, the ``big'' category of rings, etc.

Referencing norms: big_category, is_class, proper_class

en · official · sha256:c907d82e474289977f46e1ce2e94dd5c4e9bc51e7417497c23cb1c93d6f4ddeb

\section{The hierarchy of sets} \label{section-sets-hierarchy} \noindent We define by transfinite recursion $V_0 = \emptyset$, $V_{\alpha + 1} = P(V_\alpha)$ (power set), and for a limit ordinal $\alpha$, $$ V_\alpha = \bigcup\nolimits_{\beta < \alpha} V_\beta. $$ Note that each $V_\alpha$ is a transitive set. \begin{lemma} \label{lemma-axiom-regularity} Every set is an element of $V_\alpha$ for some ordinal $\alpha$. \end{lemma} \begin{proof} See \cite[Lemma 6.3]{Jech}. \end{proof} \noindent In \cite[Chapter III]{Kunen} it is explained that this lemma is equivalent to the axiom of foundation. The {\it rank} of a set $S$ is the least ordinal $\alpha$ such that $S \in V_{\alpha + 1}$. By a {\it partial universe} we shall mean a suitably large set of the form $V_\alpha$ which will be clear from the context.

Referencing norms: LiesInStageByMembership, LiesInStageByRank, element_of, has_rank, is_partial_universe, stage_of

en · official · sha256:e894791e11547e7bb4c5e3da90a95a09b5016005f729a5dd0c29253fa5af120b

\begin{lemma} \label{lemma-axiom-regularity} Every set is an element of $V_\alpha$ for some ordinal $\alpha$. \end{lemma}

Referencing norms: EverySetLiesInSomeStage

en · official · sha256:b1943eda3cea620fc0f0077cd778a1ccfbf1facb26932223846d20cd3f267122

\section{Cardinality} \label{section-cardinals} \noindent The {\it cardinality} of a set $A$ is the least ordinal $\alpha$ such that there exists a bijection between $A$ and $\alpha$. We sometimes use the notation $\alpha = |A|$ to indicate this. We say an ordinal $\alpha$ is a {\it cardinal} if and only if it occurs as the cardinality of some set $A$---in other words, if $\alpha = |A|$. We use the greek letters $\kappa$, $\lambda$ for cardinals. The first infinite cardinal is $\omega$, and in this context it is denoted $\aleph_0$. A set is {\it countable} if its cardinality is $\leq \aleph_0$. If $\alpha$ is an ordinal, then we denote $\alpha^+$ the least cardinal $> \alpha$. You can use this to define $\aleph_1 = \aleph_0^+$, $\aleph_2 = \aleph_1^+$, etc, and in fact you can define $\aleph_\alpha$ for any ordinal $\alpha$ by transfinite recursion. We note the equality $\aleph_1 = \omega_1$. \medskip\noindent The {\it addition} of cardinals $\kappa, \lambda$ is denoted $\kappa \oplus \lambda$; it is the cardinality of $\kappa \amalg \lambda$. The {\it multiplication} of cardinals $\kappa, \lambda$ is denoted $\kappa \otimes \lambda$; it is the cardinality of $\kappa \times \lambda$. If $\kappa$ and $\lambda$ are infinite cardinals, then $\kappa \oplus \lambda = \kappa \otimes \lambda = \max(\kappa, \lambda)$. The {\it exponentiation} of cardinals $\kappa, \lambda$ is denoted $\kappa^\lambda$; it is the cardinality of the set of (set) maps from $\lambda$ to $\kappa$. Given any set $K$ of cardinals, the {\it supremum} of $K$ is $\sup_{\kappa \in K} \kappa = \bigcup_{\kappa \in K} \kappa$, which is also a cardinal.

Referencing norms: CountableByAlephNull, InfiniteCardinalProductIsMaximum, InfiniteCardinalSumIsMaximum, at_least, at_most_aleph_null, cardinality_of, infinite

en · official · sha256:3335e07077a11caa3b34d0d1412494fa6fa5342f39e9e8b0047a308c3b17a1cd

\section{Cofinality} \label{section-cofinality} \noindent A {\it cofinal subset} $S$ of a well-ordered set $T$ is a subset $S \subset T$ such that $\forall t \in T \exists s\in S (t \leq s)$. Note that a subset of a well-ordered set is a well-ordered set (with induced ordering). Given an ordinal $\alpha$, the {\it cofinality} $\text{cf}(\alpha)$ of $\alpha$ is the least ordinal $\beta$ which occurs as the order type of some cofinal subset of $\alpha$. The cofinality of an ordinal is always a cardinal. Hence alternatively we can define the cofinality of $\alpha$ as the least cardinality of a cofinal subset of $\alpha$. \begin{lemma} \label{lemma-map-from-set-lifts} Suppose that $T = \colim_{\alpha < \beta} T_\alpha$ is a colimit of sets indexed by ordinals less than a given ordinal $\beta$. Suppose that $\varphi : S \to T$ is a map of sets. Then $\varphi$ lifts to a map into $T_\alpha$ for some $\alpha < \beta$ provided that $\beta$ is not a limit of ordinals indexed by $S$, in other words, if $\beta$ is an ordinal with $\text{cf}(\beta) > |S|$. \end{lemma} \begin{proof} For each element $s \in S$ pick a $\alpha_s < \beta$ and an element $t_s \in T_{\alpha_s}$ which maps to $\varphi(s)$ in $T$. By assumption $\alpha = \sup_{s \in S} \alpha_s$ is strictly smaller than $\beta$. Hence the map $\varphi_\alpha : S \to T_\alpha$ which assigns to $s$ the image of $t_s$ in $T_\alpha$ is a solution. \end{proof} \noindent The following is essentially Grothendieck's argument for the existence of ordinals with arbitrarily large cofinality which he used to prove the existence of enough injectives in certain abelian categories, see \cite{Tohoku}. \begin{proposition} \label{proposition-exist-ordinals-large-cofinality} Let $\kappa$ be a cardinal. Then there exists an ordinal whose cofinality is bigger than $\kappa$. \end{proposition} \begin{proof} If $\kappa$ is finite, then $\omega = \text{cf}(\omega)$ works. Let us thus assume that $\kappa$ is infinite. Consider the smallest ordinal $\alpha$ whose cardinality is strictly greater than $\kappa$. We claim that $\text{cf}(\alpha) > \kappa$. Note that $\alpha$ is a limit ordinal, since if $\alpha = \beta + 1$, then $|\alpha| = |\beta|$ (because $\alpha$ and $\beta$ are infinite) and this contradicts the minimality of $\alpha$. (Of course $\alpha$ is also a cardinal, but we do not need this.) To get a contradiction suppose $S \subset \alpha$ is a cofinal subset with $|S| \leq \kappa$. For $\beta \in S$, i.e., $\beta < \alpha$, we have $|\beta| \leq \kappa$ by minimality of $\alpha$. As $\alpha$ is a limit ordinal and $S$ cofinal in $\alpha$ we obtain $\alpha = \bigcup_{\beta \in S} \beta$. Hence $|\alpha| \leq |S| \otimes \kappa \leq \kappa \otimes \kappa \leq \kappa$ which is a contradiction with our choice of $\alpha$. \end{proof}

Referencing norms: OrdinalOfLargeCofinalityExists

en · official · sha256:8b0ef821b6128f988c128f74aa1fff930ed242b42fe202b615cf2dc5a126c2db

\section{Reflection principle} \label{section-reflection-principle} \noindent Some of this material is in the chapter of \cite{Kunen} called ``Easy consistency proofs''. \medskip\noindent Let $\phi(x_1, \ldots, x_n)$ be a formula of set theory. Let us use the convention that this notation implies that all the free variables in $\phi$ occur among $x_1, \ldots, x_n$. Let $M$ be a set. The formula $\phi^M(x_1, \ldots, x_n)$ is the formula obtained from $\phi(x_1, \ldots, x_n)$ by replacing all the $\forall x$ and $\exists x$ by $\forall x\in M$ and $\exists x\in M$, respectively. So the formula $\phi(x_1, x_2) = \exists x (x\in x_1 \wedge x\in x_2)$ is turned into $\phi^M(x_1, x_2) = \exists x \in M (x\in x_1 \wedge x\in x_2)$. The formula $\phi^M$ is called the {\it relativization of $\phi$ to $M$}. \begin{theorem} \label{theorem-reflection-principle} Suppose given $\phi_1(x_1, \ldots, x_n), \ldots, \phi_m(x_1, \ldots, x_n)$ a {\bf finite} collection of formulas of set theory. Let $M_0$ be a set. There exists a set $M$ such that $M_0 \subset M$ and $\forall x_1, \ldots, x_n \in M$, we have $$ \forall i = 1, \ldots, m, \ \phi_i^{M}(x_1, \ldots, x_n) \Leftrightarrow \forall i = 1, \ldots, m, \ \phi_i(x_1, \ldots, x_n). $$ In fact we may take $M = V_\alpha$ for some limit ordinal $\alpha$. \end{theorem} \begin{proof} See \cite[Theorem 12.14]{Jech} or \cite[Theorem 7.4]{Kunen}. \end{proof} \noindent We view this theorem as saying the following: Given any $x_1, \ldots, x_n \in M$ the formulas hold with the bound variables ranging through all sets if and only if they hold for the bound variables ranging through elements of $V_\alpha$. This theorem is a meta-theorem because it deals with the formulas of set theory directly. It actually says that given the finite list of formulas $\phi_1, \ldots, \phi_m$ with at most free variables $x_1, \ldots, x_n$ the sentence $$ \begin{matrix} \forall M_0\ \exists M, \ M_0 \subset M\ \forall x_1, \ldots, x_n \in M \\ \phi_1(x_1, \ldots, x_n) \wedge \ldots \wedge \phi_m(x_1, \ldots, x_n) \leftrightarrow \phi_1^M(x_1, \ldots, x_n) \wedge \ldots \wedge \phi_m^M(x_1, \ldots, x_n) \end{matrix} $$ is provable in ZFC. In other words, whenever we actually write down a finite list of formulas $\phi_i$, we get a theorem. \medskip\noindent It is somewhat hard to use this theorem in ``ordinary mathematics'' since the meaning of the formulas $\phi_i^M(x_1, \ldots, x_n)$ is not so clear! Instead, we will use the idea of the proof of the reflection principle to prove the existence results we need directly.

Referencing norms: reflects_formulas

en · official · sha256:9b9784072cf8e6219a41c5dcf13b590bd3ef16cc19ef3748324d38f1a162b73b

\begin{theorem} \label{theorem-reflection-principle} Suppose given $\phi_1(x_1, \ldots, x_n), \ldots, \phi_m(x_1, \ldots, x_n)$ a {\bf finite} collection of formulas of set theory. Let $M_0$ be a set. There exists a set $M$ such that $M_0 \subset M$ and $\forall x_1, \ldots, x_n \in M$, we have $$ \forall i = 1, \ldots, m, \ \phi_i^{M}(x_1, \ldots, x_n) \Leftrightarrow \forall i = 1, \ldots, m, \ \phi_i(x_1, \ldots, x_n). $$ In fact we may take $M = V_\alpha$ for some limit ordinal $\alpha$. \end{theorem}

Referencing norms: reflects_formulas

en · official · sha256:0527dbd0ac44b3ec93e3bc4e495e2da771a17c81b3af0dad6d9619291f7b057e

\begin{lemma} \label{lemma-construct-category} With notations $\text{size}$, $Bound$ and $\Sch_\alpha$ as above. Let $S_0$ be a set of schemes. There exists a limit ordinal $\alpha$ with the following properties: \begin{enumerate} \item \label{item-inclusion} We have $S_0 \subset V_\alpha$; in other words, $S_0 \subset \Ob(\Sch_\alpha)$. \item \label{item-bounded} For any $S \in \Ob(\Sch_\alpha)$ and any scheme $T$ with $\text{size}(T) \leq Bound(\text{size}(S))$, there exists a scheme $S' \in \Ob(\Sch_\alpha)$ such that $T \cong S'$. \item \label{item-limit} For any countable\footnote{Both the set of objects and the morphism sets are countable. In fact you can prove the lemma with $\aleph_0$ replaced by any cardinal whatsoever in (3) and (4).} diagram category $\mathcal{I}$ and any functor $F : \mathcal{I} \to \Sch_\alpha$, the limit $\lim_\mathcal{I} F$ exists in $\Sch_\alpha$ if and only if it exists in $\Sch$ and moreover, in this case, the natural morphism between them is an isomorphism. \item \label{item-colimit} For any countable index category $\mathcal{I}$ and any functor $F : \mathcal{I} \to \Sch_\alpha$, the colimit $\colim_\mathcal{I} F$ exists in $\Sch_\alpha$ if and only if it exists in $\Sch$ and moreover, in this case, the natural morphism between them is an isomorphism. \end{enumerate} \end{lemma}

en · official · sha256:4195e3edf455fdeac8582a676e8bf938cd413702539e7796a555a6f1f3116e79

\begin{lemma} \label{lemma-abelian-injectives} Suppose given a big category $\mathcal{A}$ (see Categories, Remark \ref{categories-remark-big-categories}). Assume $\mathcal{A}$ is abelian and has enough injectives. See Homology, Definitions \ref{homology-definition-abelian-category} and \ref{homology-definition-enough-injectives}. Then for any given set of objects $\{A_s\}_{s\in S}$ of $\mathcal{A}$, there is an abelian subcategory $\mathcal{A}' \subset \mathcal{A}$ with the following properties: \begin{enumerate} \item the inclusion functor $\mathcal{A}' \to \mathcal{A}$ is exact, \item $\Ob(\mathcal{A}')$ is a set, \item $\Ob(\mathcal{A}')$ contains $A_s$ for each $s \in S$, \item $\mathcal{A}'$ has enough injectives, and \item an object of $\mathcal{A}'$ is injective if and only if it is an injective object of $\mathcal{A}$. \end{enumerate} \end{lemma}

Referencing norms: SmallAbelianSubcategoryWithEnoughInjectives

en · official · sha256:69fe1c3ec32c702394ce2230e9d5b5cf171600ef30319c1677999b12df9cec56

\section{Ordinals} \label{section-ordinals} \noindent A set $T$ is {\it transitive} if $x\in T$ implies $x\subset T$. A set $\alpha$ is an {\it ordinal} if it is transitive and well-ordered by $\in$. In this case, we define $\alpha + 1 = \alpha \cup \{\alpha\}$, which is another ordinal called the {\it successor} of $\alpha$. An ordinal $\alpha$ is called a {\it successor ordinal} if there exists an ordinal $\beta$ such that $\alpha = \beta + 1$. The smallest ordinal is $\emptyset$ which is also denoted $0$. If $\alpha$ is not $0$, and not a successor ordinal, then $\alpha$ is called a {\it limit ordinal} and we have $$ \alpha = \bigcup\nolimits_{\gamma \in \alpha} \gamma. $$ The first limit ordinal is $\omega$ and it is also the first infinite ordinal. The first uncountable ordinal $\omega_1$ is the set of all countable ordinals. The collection of all ordinals is a proper class. It is well-ordered by $\in$ in the following sense: any nonempty set (or even class) of ordinals has a least element. Given a set $A$ of ordinals, we define the {\it supremum} of $A$ to be $\sup_{\alpha \in A} \alpha = \bigcup_{\alpha \in A} \alpha$. It is the least ordinal bigger or equal to all $\alpha \in A$. Given any well-ordered set $(S, <)$, there is a unique ordinal $\alpha$ such that $(S, <) \cong (\alpha, \in)$; this is called the {\it order type} of the well-ordered set.

Referencing norms: is_ordinal

en · official · sha256:d459e58c7c1e897290e6c291efaeb3df3db4bd4cdb94b2675b1925e8595d04de

\begin{lemma} \label{lemma-map-from-set-lifts} Suppose that $T = \colim_{\alpha < \beta} T_\alpha$ is a colimit of sets indexed by ordinals less than a given ordinal $\beta$. Suppose that $\varphi : S \to T$ is a map of sets. Then $\varphi$ lifts to a map into $T_\alpha$ for some $\alpha < \beta$ provided that $\beta$ is not a limit of ordinals indexed by $S$, in other words, if $\beta$ is an ordinal with $\text{cf}(\beta) > |S|$. \end{lemma}

en · official · sha256:fc00416f9824e4edb92cba43cb0ef88fb86d64ed45b97a28975634d546dda125

\begin{proposition} \label{proposition-exist-ordinals-large-cofinality} Let $\kappa$ be a cardinal. Then there exists an ordinal whose cofinality is bigger than $\kappa$. \end{proposition}

Referencing norms: OrdinalOfLargeCofinalityExists