*Acknowledgements: ChatGPT for Grammar fixing.*↵
↵
In mathematics, ordinals extend the concept of counting beyond finite numbers and incorporate infinite sequences. From a graph theory perspective, you can think of ordinals as a hierarchy of "layers" or "levels" that represent different sizes and types of infinity.↵
↵
## Basic Concepts↵
↵
In this blog, we define**ordinals** as a (maybe infinite) competitive graphs $\Gamma$ (A directed graph is a **competitive graph**, if, where a competitive graph is a directed graph in which exactly one of $(u, v)$ andor $(v, u)$ is included in the edge set, for every $u \ne v$.) with nopair of distinct vertices $u$ and $v$. These graphs are characterized by the absence of loops and no reversed rays (that is,, where a reversed ray refers to a sequence of vertices $v_0, v_1, v_2, \dots$, where there existsith edges $(v_1, v_0), (v_2, v_1), (v_3, v_2), \dots$).↵
↵
Finite ordinalsarecorrespond to natural numbers. For example, $0$ iinstance, $0$ represents the empty graph, and $1$ idenotes the only graph with ona single vertex. FurtherAn example is asprovided below:↵
↵
↵
↵
In fact, the set of natural numbers $\mathbb N$, usually{Z}{\ge 0}$, often denoted as $\omega$, can be seeninterpreted as an ordinal: $\Gamma_\omega = (V, E)$, where $V = \mathbb N{Z}_{\ge 0}$ and $E = \\{(i, j) : i < j\\}$, but}$. However, $\mathbb Z{Z}$ cannot be seen asconsidered an ordinal in a similar way, because there exists a reversed raymanner, due to the presence of a reversed ray, as exemplified by the sequence of vertices $v_i = -i$.↵
↵
We define $\alpha \le \beta$ if $\beta$ can beseenviewed as a subgraph of $\alpha$, and define. Similarly, $\alpha = \beta$, if and only if $\alpha \le \beta$ and $\beta \le \alpha$. Like what we'reAs is familiar with, we have, the relationship between ordinals is either $\alpha < \beta$, $\alpha = \beta$, or $\alpha > \beta$. ↵
↵
<spoiler summary="Proof (Maybe Mathy)">↵
Every ordinal has an initial element,thatwhich is, a vertex without innercoming edges. Otherwise, we can find an inner edges $v' \to v$ of every vertex $v$, that formsIf this were not the case, then for every vertex $v$, there would exist an incoming edge $v' \to v$, creating a reversed ray: $\dots \to v' ' ' \to v' ' \to v' \to v$. It can be easily proven that the initial element $v_0$ is unique.↵
↵
Let'sWe define a set $S_v$ for every vertex $v$ of $\alpha$ as follows: $S_{v_0} = \varnothing$, and for any vertex $v \ne v_0$, $S_v = \\{{ S_u : (u, v) \in E\\ }$. If there exists a $S_x$ that is undefined, then: (1) $x$ can'not be an initial element, so there exists an innermust be an incoming edge $x' \to x$; (2) For the same reasonSimilarly, $x'$ can'not be an initial element, so there exists an innermust be an incoming edge $x' ' \to x'$. CBy continueing theis logic chain, we can proofdemonstrate that $\dots \to x' ' ' \to x' ' \to x' \to x$ i$ forms a reversed ray. SoTherefore, every $S_x$ is defined.↵
↵
It can beseenobserved that $\alpha \le \beta \if$ if and only if $S_\alpha \le S_\beta$, and $\alpha < \beta \if$ if and only if $S_\alpha \in S_\beta$. Let $S_\alpha = \\{{ S_v : v \in \alpha\\ }$ (mathematicians often define ordinals as such a set instead of a graph) andrather than as a graph). Suppose $S = S_\alpha \cap S_\beta$, i. If $S \ne S_\alpha$ and $S \ne S_\beta$, then $S \in S_\alpha$, $S \in $ is an element of both $S_\alpha$ and $S_\beta$, andso $S \in S_\alpha \cap S_\beta = S$. By the Axiom of Regularity, there doesn't exist a set $S$ such thatno set $S$ can satisfy $S \in S$. Therefore, $S = S_\alpha$ or $S = S_\beta$, which implies that is, $S_\alpha \subseteq S_\beta$ or $S_\beta \subseteq S_\alpha$.↵
</spoiler>↵
↵
In fact, for every set $A$ of ordinals,we can havethere exists an ordinal $\min A$ in the set $A$. The proof is simply gettraightforward: one can obtain $\min A$ by taking the union of all the $S_\alpha$, where $\alpha \in A$ and $S$ is the set constructed beforedefined previously.↵
↵
The successor of an ordinal $\alpha$ is a new graph $G$, where the vertices are the vertex of $\alpha$, together with a new vertex $v$, and link all the edges $(winclude all the vertices of $\alpha$ along with an additional vertex $v$. All edges $(w, v)$, where $w$ is a vertex in $\alpha$, are added. The successor of $\alpha$ is denoted as $\alpha^+$. It is evident that $\alpha < \alpha^+$. Consequently, we can define the $n$-th successor of $\alpha$, denoted as $\alpha + n$.↵
↵
To understand how addition and multiplication of ordinals work, consider the following definitions: For ordinals $\alpha$ and $\beta$, $\alpha + \beta$ is the ordinal with vertices formed by the disjoint union $\alpha \sqcup \beta$ (where $\sqcup$ denotes the disjoint union of sets) and edges of three types: the edges from $\alpha$ itself, the edges from $\beta$ itself, and new edges $(u, v)$ where $u$ is a vertex of $\alpha$ and $v$ is a vertex of $\beta$. Similarly, $\alpha \times \beta$ is the ordinal with vertices formed by pairs $(u, v)$, and edges formed by pairs $((u, v), (u', v'))$, where$weither $(u, u') \in E_\alpha$. We can denote the successor of $\alpha$ as $\alpha^+$. It can be seen that $\alpha < \alpha^+$. then, we can get the $n$-th successor of $\alpha$, denoted $\alpha + n$. or $u = u'$ and $(v, v') \in E_\beta$.↵
↵
It is important to note that commutativity does not hold for ordinals: $1 + \omega = \omega \ne \omega + 1$, and $2 \omega = \omega \ne \omega 2$. However, associativity does hold.↵
↵
Here are some properties of ordinals:↵
↵
* If $\beta < \gamma$, then $\alpha + \beta < \alpha + \gamma$.↵
* If $\alpha < \beta$, there exists a unique $\gamma$ such that $\alpha + \gamma = \beta$.↵
* For ordinals $\gamma$ and $\alpha$, there exists a unique pair of ordinals $\beta$ and $\delta$ such that $\gamma = \alpha \beta + \delta$.↵
* For $\gamma > 0$, there exists a unique Cantor normal form $\gamma = \omega^{\alpha_1} k_1 + \dots + \omega^{\alpha_n} k_n$, where $n \ge 1$, $\alpha_1 > \alpha_2 > \dots > \alpha_n$ are ordinals, and $k_1, k_2, \dots, k_n \in \mathbb{Z}_{> 0}$.↵
↵
## Application in CP/OI↵
To be updated. An example problem will be [problem:1984D].
↵
In mathematics, ordinals extend the concept of counting beyond finite numbers and incorporate infinite sequences. From a graph theory perspective, you can think of ordinals as a hierarchy of "layers" or "levels" that represent different sizes and types of infinity.↵
↵
## Basic Concepts↵
↵
In this blog, we define
↵
Finite ordinals
↵
↵
In fact, the set of natural numbers $\mathbb
↵
We define $\alpha \le \beta$ if $\beta$ can be
↵
<spoiler summary="Proof (Maybe Mathy)">↵
Every ordinal has an initial element,
↵
↵
It can be
</spoiler>↵
↵
In fact, for every set $A$ of ordinals,
↵
The successor of an ordinal $\alpha$ is a new graph $G$
↵
To understand how addition and multiplication of ordinals work, consider the following definitions: For ordinals $\alpha$ and $\beta$, $\alpha + \beta$ is the ordinal with vertices formed by the disjoint union $\alpha \sqcup \beta$ (where $\sqcup$ denotes the disjoint union of sets) and edges of three types: the edges from $\alpha$ itself, the edges from $\beta$ itself, and new edges $(u, v)$ where $u$ is a vertex of $\alpha$ and $v$ is a vertex of $\beta$. Similarly, $\alpha \times \beta$ is the ordinal with vertices formed by pairs $(u, v)$, and edges formed by pairs $((u, v), (u', v'))$, where
↵
It is important to note that commutativity does not hold for ordinals: $1 + \omega = \omega \ne \omega + 1$, and $2 \omega = \omega \ne \omega 2$. However, associativity does hold.↵
↵
Here are some properties of ordinals:↵
↵
* If $\beta < \gamma$, then $\alpha + \beta < \alpha + \gamma$.↵
* If $\alpha < \beta$, there exists a unique $\gamma$ such that $\alpha + \gamma = \beta$.↵
* For ordinals $\gamma$ and $\alpha$, there exists a unique pair of ordinals $\beta$ and $\delta$ such that $\gamma = \alpha \beta + \delta$.↵
* For $\gamma > 0$, there exists a unique Cantor normal form $\gamma = \omega^{\alpha_1} k_1 + \dots + \omega^{\alpha_n} k_n$, where $n \ge 1$, $\alpha_1 > \alpha_2 > \dots > \alpha_n$ are ordinals, and $k_1, k_2, \dots, k_n \in \mathbb{Z}_{> 0}$.↵
↵
## Application in CP/OI↵
To be updated. An example problem will be [problem:1984D].
