Weekly Theorem

I realized how types of structured sets can be thought of as faithful copresheaves.

Let $F$ be a type of structured sets, e.g. the type of groups or the type of topological spaces. For every structured set $A$ in $F$ we have the underlying set $F(A)$ of $A$. And for every structure-preserving map $f : A \to B$ between structured sets in $F$, we have the underlying map $F(f)$ of $f$.

Note that $F(A)$ is not $A$ because $A$ has additional structure. In fact it is possible for two structured sets to be distinct and yet have the same underlying set, since they may differ in structure while having the same elements. In contrast, $F(f)$ does not have any additional structure on it, compared to $f$, besides the additional structure on its domain and codomain; this means that $f$ is uniquely determined by $F(f)$, $A$ and $B$. We may therefore think of $f$ as the ordered triple $(F(f), A, B)$.

Now, two conditions it's reasonable to expect structure-preserving maps to satisfy are as follows:

For any two structure-preserving maps $f : A \to B$, $g : B \to C$, the composition $(F(g) \circ F(f), A, C)$ is also structure-preserving.

For every structured set $A$, the identity map $(1_A, A, A)$ is structure-preserving.

It is easy to prove that if these two conditions are satisfied, then by taking the structured sets in $F$ as objects and the structure-preserving maps between structured sets in $F$ as morphisms, we obtain a category, and then $F$ is a faithful copresheaf on this category.

Of course, we can replace $\mathsf{Set}$ with an arbitrary category $X$ to get a notion of “structured $X$-object”; a type of structured $X$-objects is a faithful functor into $X$.

NB: theorems are not necessarily posted weekly

in the blog description, I had intended to achieve a rate of more than 2 posts per year, which I decidedly did not achieve (in fact, the two posts were both in the same week the blog was created, so I basically started the blog and abandoned it within a week).

Definition 1. The filters on a class $I$ are the nonempty subclasses of $\mathcal P(I) \setminus \{\varnothing\}$ closed under supersets in $\mathcal P(I)$ and under binary intersection.

Lemma 1. The union of a nonempty $\subset$-chain of filters on a class $I$ is a filter on $I$.

Proof. Suppose $I$ is a class and $C$ is a nonempty $\subset$-chain of filters on $I$, and let $F$ be the union of $C$.

Every member of $C$ is a filter and hence is nonempty, and $C$ itself is nonempty, so $C$ has a nonempty member, and hence its union is nonempty.

Suppose $\varnothing \in F$. Then there is a $G \in C$ such that $\varnothing \in G$. But this $G$ is a filter on $I$, and no filter on $I$ contains $\varnothing$. So $\varnothing \not \in F$.

Suppose $A \in F$, $B \in \mathcal P(I)$ and $A \subseteq B$. Then there is a $G \in C$ such that $A \in G$. This $G$ is a filter on $I$, and hence is closed under supersets in $\mathcal P(I)$, so we have $B \in G$ and hence $B \in F$.

Suppose $A$ and $B$ are in $F$. Then there are sets $G$ and $H$ in $C$ such that $A \in G$ and $B \in H$. Because $C$ is a $\subset$-chain, we can assume without loss of generality that $G \subseteq H$ and hence both $A$ and $B$ are in $H$. This $H$ is a filter on $I$, and hence is closed under binary intersection, so it follows that $A \cap B \in H$ and hence $A \cap B \in F$.

Definition 2. The ultrafilters on a class $I$ are the $\subset$-maximal filters on $I$.

Theorem (Ultrafilter Lemma). For every set $I$ and every filter $F$ on $I$, there is an ultrafilter on $I$ including $F$.

Proof. Define a sequence $(U_n : n \in \mathsf{On})$ by transfinite recursion like so:

$U_0 = F$.

For every ordinal $n$:

If there is a filter $G$ on $I$ such that $U_n \subset G$, then let $U_{n + 1} = G$ (details 1).

Otherwise, let $U_{n + 1} = U_n$.

For every limit ordinal $n$, let \begin{equation*} U_n = \bigcup_{m < n} U_m. \end{equation*}

We shall prove by transfinite induction that for every ordinal $n$, the class $U_n$ is a filter on $I$ and includes every class of the form $U_m$, where $m < n$.

$U_0 = F$, and $F$ is a filter on $I$.

Suppose $n$ is an ordinal and $U_n$ is a filter on $I$ and includes every class of the form $U_m$, where $m < n$. Then:

If there is a filter $G$ on $I$ such that $U_n \subset G$, then $U_{n + 1} = G$ is a filter on $I$ and if $m \in n + 1$, then either $m \in n$, in which case $U_m \subseteq U_n \subset G$, or $m = n$, in which case $U_m = U_n \subset G$.

Otherwise, we have $U_{n + 1} = U_n$, and $U_n$ is a filter on $I$ and includes every class of the form $U_m$, where $m \in n$.

Suppose $n$ is a limit ordinal and for every $m < n$, the class $U_m$ is a filter on $I$ and includes every class of the form $U_k$, where $k < m$. Then for every pair $i, j$ of distinct ordinals less than $n$ such that $i < j$, we have $U_i \subseteq U_j$; so the set $\{U_m : m < n\}$ is a $\subset$-chain of filters on $I$, and hence its union $U_n$ is a filter on $I$ by Lemma 1.

Now, suppose that for every ordinal $n$, there is a filter $G$ on $I$ such that $U_n \subset G$. Then $U_{n + 1} = G$ is a proper superset of $U_n$ and moreover, for every $m < n$, we have $U_m \subseteq U_n \subset U_{n + 1}$. So for every ordinal $n$ and every ordinal $m < n$, we have $m + 1 \le n$, and hence $U_m \subset U_{m + 1} \subseteq U_n$. So $(U_n : n \in \mathsf{On})$ is injective. Because $\mathcal P(I)$ is a codomain of this sequence, it follows that $\mathcal P(I)$ is a proper class (details 1 below) and hence $I$ is a proper class. But $I$ is a set. So there is an ordinal $n$ such that $U_n$ is not properly included by any other filter on $I$, i.e. $U_n$ is an ultrafilter. And $F = U_0 \subseteq U_n$. $\blacksquare$

Details 1. This part of the proof makes use of the axiom of choice. This may be easy to miss because of the linguistic shortcut I have allowed myself to use here: I know that there is some $G$ with the property I want and so then I feel free to assign to $U_{n + 1}$ a definite such $G$. This is not a manoeuvre that can be translated straightforwardly into the language of first-order logic. If I wanted to write in a style that hews more closely to how the proof would be translated into first-order logic, I would add a paragraph to the start of the proof reading like so:

“For every filter $G$ on $I$, let $V_G = \{H : H \text{ is a filter on $I$} \wedge G \subseteq H\}$. Let $X$ be the class of the sets of the form $V_G$, where $G$ is a filter on $I$. By the axiom of choice, there is a mapping $f$ on $X$ such that for every filter $G$ on $I$, we have $f(V_G) \in V_G$, i.e. $f(V_G)$ is a filter on $I$ and $G \subseteq f(V_G)$.”

Then, later on in the proof, rather than saying “let $U_{n + 1} = G$”, I would say “let $U_{n + 1} = f(V_G)$”.

Details 2. $\mathsf{On}$ is a proper class, due to the Burali-Forti paradox (I will not cover this here). The principle of limitation of size says that all proper classes have the same “cardinality”, which is strictly greater than any cardinality a set can have. So if $\mathsf{On}$ is injectable into a class $A$, then by definition this means that the cardinality of $A$ is at least the cardinality of $\mathsf{On}$, and hence $A$ is also a proper class.

Definition 1. A nonzero polynomial $a_0 + a_1 x + \dotsb + a_n x^n$ is monic if and only if $a_n = 1$.

Definition 2. The algebraic integers are the roots of the monic polynomials with integer coefficients.

Theorem. There are no rational algebraic integers that are not integers.

Proof. Suppose $a/b$ is a rational algebraic integer. Assume without loss of generality that $b > 0$ and $a$ and $b$ are coprime. Then there is a monic polynomial $c_0 + c_1 x + \dotsb + c_{n - 1} x^{n - 1} + x^n$ with integer coefficients of which $a/b$ is a root and hence \begin{align*} 0 &= c_0 + c_1 \frac a b + \dotsb + c_{n - 1} \left( \frac a b \right)^{n - 1} + \left( \frac a b \right)^n \\\\ &= c_0 + c_1 \frac a b + \dotsb + c_{n - 1} \frac {a^{n - 1}} {b^{n - 1}} + \frac {a^n} {b^n}. \end{align*} Multiplying both sides by $b^n$, we obtain \begin{equation*} 0 = c_0 b^n + c_1 a b^{n - 1} + \dotsb + c_{n - 1} a^{n - 1} b + a^n \end{equation*} which means $a^n$ is divisible by $b$ (details 1 below). But $a$ and $b$ are coprime, so the only way this can happen is if $b = 1$, i.e. $a/b$ is an integer (details 2 below). $\blacksquare$

Details 1. Whenever an equation of the form \begin{equation*} a_1 + a_2 + \dotsb + a_m = b_1 + b_2 + \dotsb + b_n \end{equation*} holds, where the terms $a_1$, $a_2$, …, $a_m$, $b_1$, $b_2$, …, $b_n$ are integers, and all but one of the terms is known to be divisible by an integer $c$, the remaining term has to be divisible by $c$ too (because we can rearrange to isolate the term on one side, and then factorise on the other side by taking the common factor of $c$ out).

Details 2. Two integers $a$ and $b$, not both 0, are coprime if and only if they share no prime factors. So for every integer $a$, the only factor of $a$ coprime to $a$ is 1, because any other factor would have a prime factor, which would also be a prime factor of $a$. More generally, for every pair of integers $a$ and $b$ with the same prime factors, the only factor of $b$ coprime to $a$ is 1, because any other factor of $b$ would have a prime factor, which would also be a prime factor of $b$, hence would also be a prime factor of $a$. And for every positive integer $n$, the power $a^n$ has the same prime factors as $a$; so the only factor of $a^n$ coprime to $a$ is 1.