On ordinals
Разница между en4 и en5, 2,832 символ(ов) изменены
*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 ordinals 
arecorrespond 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:↵

![ ](https://ibb.co/Qm32dTd)

In fact, the set of natural number
s $\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 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 be 
seenviewed 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 be 
seenobserved that $\alpha \le \beta \if$ if and only i$S_\alpha \le S_\beta$, and $\alpha < \beta \if$ if and only i$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].

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en12 Английский OIer1048576 2024-08-30 08:51:42 11
en11 Английский OIer1048576 2024-08-29 16:56:23 4095
en10 Английский OIer1048576 2024-08-28 17:15:17 0 (published)
en9 Английский OIer1048576 2024-08-28 17:14:52 30 (saved to drafts)
en8 Английский OIer1048576 2024-08-28 17:12:40 6 Tiny change: '[problem:1984D].' -> '[problem:1149E].'
en7 Английский OIer1048576 2024-08-28 17:11:38 2
en6 Английский OIer1048576 2024-08-28 17:10:16 3
en5 Английский OIer1048576 2024-08-28 17:09:02 2832 (published)
en4 Английский OIer1048576 2024-08-28 12:17:14 593
en3 Английский OIer1048576 2024-08-28 11:56:16 2095
en2 Английский OIer1048576 2024-08-28 11:11:53 4 Tiny change: 'ow:\n![](hhttps://ib' -> 'ow:\n![](https://ib'
en1 Английский OIer1048576 2024-08-28 11:11:32 673 Initial revision (saved to drafts)