Ordinal: Difference between revisions
no edit summary
RhubarbJayde (talk | contribs) No edit summary |
RhubarbJayde (talk | contribs) No edit summary |
||
Line 1:
In set theory, the '''ordinal numbers''' or '''ordinals''' are an extension of the [[natural numbers]] that describe the order types of [[Well-ordered set|well-ordered sets]]. A set \( S \) is '''well-ordered''' if each non-empty \( T \subseteq S \) has a least element. For example, any finite set of real numbers is well-ordered, as well as the set of natural numbers, while neither the set of nonnegative rationals nor the set of integers is well-ordered. This is in contrast to the [[Cardinal|cardinals]], which only describe cardinality, and which are applicable to non-well-ordered sets.
The idea of ordinals as a transfinite extension of the counting numbers was first invented by Georg Cantor in the 19th century.
==Von Neumann definition==
In a pure set theory such as [[ZFC]], we need a way to define ordinals as objects of study. The Von Neumann definition of ordinals does this, by associating each ordinal \( \alpha \) is defined as the set of all ordinals less than \( \alpha \). In particular:
* \(0 := \{\}\)
Line 9 ⟶ 11:
* If \(X\) is a set of ordinals, then \(\bigcup X\)
By associating the natural number \(0\) with the ordinal \(0\), \(1\) with \(0+1 = \{0\}\), \(2\) with \(0+1+1 = \{0,1\}\), and so on, the natural numbers can be embedded inside the ordinals. However, the set of natural numbers (which is its own union) is also an ordinal, and commonly written as \(\omega\). One convenient property of this definition of ordinals is that \(\alpha < \beta\) can be easily defined to mean \(\alpha \in \beta\), and thus \(\omega\) is an ordinal bigger than all the natural numbers. By continuing on this way, we can form a never-ending ladder of ordinals, and assign an order type to any well-ordered set.▼
One is able to define ordinals without this recursive definition. In particular, in ZFC, the two following statements are equivalent to \(\alpha\) being an ordinal.
* \(\alpha\) is a transitive [[set]] and all elements of \(\alpha\) are transitive.
▲By associating the natural number \(0\) with the ordinal \(0\), \(1\) with \(0+1 = \{0\}\), \(2\) with \(0+1+1 = \{0,1\}\), and so on, the natural numbers can be embedded inside the ordinals. However, the set of natural numbers (which is its own union) is also an ordinal, and commonly written as \(\omega\). One convenient property of this definition of ordinals is that \(\alpha < \beta\) can be easily defined to mean \(\alpha \in \beta\), and thus \(\omega\) is an ordinal bigger than all the natural numbers. By continuing on this way, we can form a never-ending ladder of ordinals, and assign an order type to any well-ordered set.
* \(\alpha\) is a transitive set and the \(\in\) relation restricted to \(\alpha\) is a strict well-order.
Using [[Supertask|supertasks]], it is possible to count up to any given countable ordinal in a finite amount of time. For example, to count to \(\omega\), one takes 30 seconds to count from 0 to 1, 15 seconds to count from 1 to 2, 7.5 seconds to count from 2 to 3, 3.75 seconds to count from 3 to 4, and so on. After a minute, all numbers \(< \omega\) will be exhausted. In general, one can count to \(\omega \cdots n\) in \(n\) seconds. By iterating this process another layer, one can count to \(\omega^2\): one takes 1 minute to count from 0 to \(\omega\), 30 seconds to count from \(\omega\) to \(\omega 2\) (so 15 seconds to count from \(\omega\) to \(\omega + 1\), 7.5 seconds to count from \(\omega + 1\) to \(\omega + 2\), and so on), then 15 seconds to count from \(\omega 2\) to \(\omega 3\), and so on. In general, any countable ordinal can be counted to in a finite amount of time. However, it is impossible to count to [[Countability|\(\omega_1\)]] in any finite amount of time. This idea is closely related to [[Matchstick diagram|matchstick diagrams]] - it is possible to draw a diagram for an arbitrary countable ordinal but not \(\omega_1\).
The order type of a well-ordered set is intuitively its "length". Alternatively, one may think of the order type of a set \(X\) as the smallest ordinal so that the ordinals below are sufficient to number the elements of \(X\), while preserving the order. For example, the order type of a singleton if 1, since pairing 0 with the single element of that set is a [[bijection]] and preserves order, therefore, the ordinals below 1 are sufficient to order-preservingly number the elements of the singleton. For finite sets, the order type and cardinality are equal.
| |||