On ordinals

Правка en4, от OIer1048576, 2024-08-28 12:17:14

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.

In this blog, we define ordinals as a (maybe infinite) competitive graph $$$\Gamma$$$ (A directed graph is a competitive graph, if exactly one of $$$(u, v)$$$ and $$$(v, u)$$$ is in the edge set, for every $$$u \ne v$$$.) with no loops and no reversed rays (that is, a sequence of vertices $$$v_0, v_1, v_2, \dots$$$, where there exists edges $$$(v_1, v_0), (v_2, v_1), (v_3, v_2), \dots$$$).

Finite ordinals are natural numbers. For example, $$$0$$$ is the empty graph, and $$$1$$$ is the only graph with one vertex. Further example is as below:

In fact, the set of natural number $$$\mathbb N$$$, usually denoted $$$\omega$$$, can be seen as an ordinal: $$$\Gamma_\omega = (V, E)$$$, where $$$V = \mathbb N$$$ and $$$E = \{(i, j) : i < j\}$$$, but $$$\mathbb Z$$$ cannot be seen as an ordinal in similar way, because there exists a reversed ray $$$v_i = -i$$$.

We define $$$\alpha \le \beta$$$ if $$$\beta$$$ can be seen as a subgraph of $$$\alpha$$$, and define $$$\alpha = \beta$$$, if $$$\alpha \le \beta$$$ and $$$\beta \le \alpha$$$. Like what we're familiar with, we have either $$$\alpha < \beta, \alpha = \beta$$$, or $$$\alpha > \beta$$$.

Proof (Maybe Mathy)

In fact, for every set $$$A$$$ of ordinals, we can have a ordinal $$$\min A$$$ in the set $$$A$$$. The proof is simply get the union of all the $$$S_\alpha$$$, where $$$\alpha \in A$$$ and $$$S$$$ is the set constructed before.

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 $$$(w, v)$$$, where $$$w \in \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$$$.

Теги ordinal, minimum excluded ordinal, mex, math, graph, game theory, sg function

История

 
 
 
 
Правки
 
 
  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)