On ordinals

Revision en8, by OIer1048576, 2024-08-28 17:12:40

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 competitive graphs $$$\Gamma$$$, where a competitive graph is a directed graph in which exactly one of $$$(u, v)$$$ or $$$(v, u)$$$ is included in the edge set for every pair of distinct vertices $$$u$$$ and $$$v$$$. These graphs are characterized by the absence of loops and reversed rays, where a reversed ray refers to a sequence of vertices $$$v_0, v_1, v_2, \dots$$$ with edges $$$(v_1, v_0), (v_2, v_1), (v_3, v_2), \dots$$$.

Finite ordinals correspond to natural numbers. For instance, $$$0$$$ represents the empty graph, and $$$1$$$ denotes the graph with a single vertex. An example is provided below:

https://ibb.co/Qm32dTd

In fact, the set of natural numbers $$$\mathbb{Z}_{\ge 0}$$$, often denoted as $$$\omega$$$, can be interpreted as an ordinal: $$$\Gamma_\omega = (V, E)$$$, where $$$V = \mathbb{Z}_{\ge 0}$$$ and $$$E = {(i, j) : i < j}$$$. However, $$$\mathbb{Z}$$$ cannot be considered an ordinal in a similar manner, 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 be viewed as a subgraph of $$$\alpha$$$. Similarly, $$$\alpha = \beta$$$ if and only if $$$\alpha \le \beta$$$ and $$$\beta \le \alpha$$$. As is familiar, the relationship between ordinals is either $$$\alpha < \beta$$$, $$$\alpha = \beta$$$, or $$$\alpha > \beta$$$.

Proof (Maybe Mathy)

In fact, for every set $$$A$$$ of ordinals, there exists an ordinal $$$\min A$$$ in the set $$$A$$$. The proof is straightforward: one can obtain $$$\min A$$$ by taking the union of all the $$$S_\alpha$$$, where $$$\alpha \in A$$$ and $$$S$$$ is the set defined previously.

The successor of an ordinal $$$\alpha$$$ is a new graph $$$G$$$ where the vertices include 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 either $$$(u, u') \in E_\alpha$$$ 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 1149E - Election Promises.

Tags ordinal, minimum excluded ordinal, mex, math, graph, game theory, sg function

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en12 English OIer1048576 2024-08-30 08:51:42 11
en11 English OIer1048576 2024-08-29 16:56:23 4095
en10 English OIer1048576 2024-08-28 17:15:17 0 (published)
en9 English OIer1048576 2024-08-28 17:14:52 30 (saved to drafts)
en8 English OIer1048576 2024-08-28 17:12:40 6 Tiny change: '[problem:1984D].' -> '[problem:1149E].'
en7 English OIer1048576 2024-08-28 17:11:38 2
en6 English OIer1048576 2024-08-28 17:10:16 3
en5 English OIer1048576 2024-08-28 17:09:02 2832 (published)
en4 English OIer1048576 2024-08-28 12:17:14 593
en3 English OIer1048576 2024-08-28 11:56:16 2095
en2 English OIer1048576 2024-08-28 11:11:53 4 Tiny change: 'ow:\n![](hhttps://ib' -> 'ow:\n![](https://ib'
en1 English OIer1048576 2024-08-28 11:11:32 673 Initial revision (saved to drafts)