Misplaced Pages

#706293

106-560: 30 ( thirty ) is the natural number following 29 and preceding 31 . 30 is an even , composite , pronic number . With 2 , 3 , and 5 as its prime factors , it is a regular number and the first sphenic number , the smallest of the form 2 × 3 × r {\displaystyle 2\times 3\times r} , where r is a prime greater than 3. It has an aliquot sum of 42 ; within an aliquot sequence of thirteen composite numbers (30, 42 , 54 , 66 , 78 , 90 , 144 , 259 , 45 , 33 , 15 , 9 , 4 , 3 , 1 ,0) to

212-500: A ↦ T < a {\displaystyle a\mapsto T_{<a}} defines an order isomorphism between T and the set of all subsets of T having the form T < a := { x ∈ T ∣ x < a } {\displaystyle T_{<a}:=\{x\in T\mid x<a\}} ordered by inclusion. This motivates the standard definition, suggested by John von Neumann at

318-680: A and b with b ≠ 0 there are natural numbers q and r such that The number q is called the quotient and r is called the remainder of the division of a by  b . The numbers q and r are uniquely determined by a and  b . This Euclidean division is key to the several other properties ( divisibility ), algorithms (such as the Euclidean algorithm ), and ideas in number theory. The addition (+) and multiplication (×) operations on natural numbers as defined above have several algebraic properties: Two important generalizations of natural numbers arise from

424-425: A + c = b . This order is compatible with the arithmetical operations in the following sense: if a , b and c are natural numbers and a ≤ b , then a + c ≤ b + c and ac ≤ bc . An important property of the natural numbers is that they are well-ordered : every non-empty set of natural numbers has a least element. The rank among well-ordered sets is expressed by an ordinal number ; for

530-466: A + 1 = S ( a ) and a × 1 = a . Furthermore, ( N ∗ , + ) {\displaystyle (\mathbb {N^{*}} ,+)} has no identity element. In this section, juxtaposed variables such as ab indicate the product a × b , and the standard order of operations is assumed. A total order on the natural numbers is defined by letting a ≤ b if and only if there exists another natural number c where

636-468: A supremum , the ordinal obtained by taking the union of all the ordinals in the set. This union exists regardless of the set's size, by the axiom of union . The class of all ordinals is not a set. If it were a set, one could show that it was an ordinal and thus a member of itself, which would contradict its strict ordering by membership. This is the Burali-Forti paradox . The class of all ordinals

742-401: A × ( b + c ) = ( a × b ) + ( a × c ) . These properties of addition and multiplication make the natural numbers an instance of a commutative semiring . Semirings are an algebraic generalization of the natural numbers where multiplication is not necessarily commutative. The lack of additive inverses, which is equivalent to the fact that N {\displaystyle \mathbb {N} }

848-404: A × 0 = 0 and a × S( b ) = ( a × b ) + a . This turns ( N ∗ , × ) {\displaystyle (\mathbb {N} ^{*},\times )} into a free commutative monoid with identity element 1; a generator set for this monoid is the set of prime numbers . Addition and multiplication are compatible, which is expressed in the distribution law :

954-401: A "lower" step—then the computation will terminate. It is inappropriate to distinguish between two well-ordered sets if they only differ in the "labeling of their elements", or more formally: if the elements of the first set can be paired off with the elements of the second set such that if one element is smaller than another in the first set, then the partner of the first element is smaller than

1060-401: A canonical labeling of the elements of any well-ordered set. Every well-ordered set ( S ,<) is order-isomorphic to the set of ordinals less than one specific ordinal number under their natural ordering. This canonical set is the order type of ( S ,<). Essentially, an ordinal is intended to be defined as an isomorphism class of well-ordered sets: that is, as an equivalence class for

1166-452: A definition is normally said to be by transfinite recursion – the proof that the result is well-defined uses transfinite induction. Let F denote a (class) function F to be defined on the ordinals. The idea now is that, in defining F (α) for an unspecified ordinal α, one may assume that F (β) is already defined for all β < α and thus give a formula for F (α) in terms of these F (β). It then follows by transfinite induction that there

SECTION 10

#1732765057707

1272-474: A digit when it would have been the last symbol in the number. The Olmec and Maya civilizations used 0 as a separate number as early as the 1st century BCE , but this usage did not spread beyond Mesoamerica . The use of a numeral 0 in modern times originated with the Indian mathematician Brahmagupta in 628 CE. However, 0 had been used as a number in the medieval computus (the calculation of

1378-483: A larger ordinal). The smallest uncountable ordinal is the set of all countable ordinals, expressed as ω 1 or ⁠ Ω {\displaystyle \Omega } ⁠ . In a well-ordered set, every non-empty subset contains a distinct smallest element. Given the axiom of dependent choice , this is equivalent to saying that the set is totally ordered and there is no infinite decreasing sequence (the latter being easier to visualize). In practice,

1484-457: A least element is called a well-order . The axiom of choice implies that every set can be well-ordered, and given two well-ordered sets, one is isomorphic to an initial segment of the other. So ordinal numbers exist and are essentially unique. Ordinal numbers are distinct from cardinal numbers , which measure the size of sets. Although the distinction between ordinals and cardinals is not always apparent on finite sets (one can go from one to

1590-577: A limit ordinal α {\displaystyle \alpha } is said to be unbounded (or cofinal) under α {\displaystyle \alpha } provided any ordinal less than α {\displaystyle \alpha } is less than some ordinal in the set. More generally, one can call a subset of any ordinal α {\displaystyle \alpha } cofinal in α {\displaystyle \alpha } provided every ordinal less than α {\displaystyle \alpha }

1696-606: A matter of definition. In 1727, Bernard Le Bovier de Fontenelle wrote that his notions of distance and element led to defining the natural numbers as including or excluding 0. In 1889, Giuseppe Peano used N for the positive integers and started at 1, but he later changed to using N 0 and N 1 . Historically, most definitions have excluded 0, but many mathematicians such as George A. Wentworth , Bertrand Russell , Nicolas Bourbaki , Paul Halmos , Stephen Cole Kleene , and John Horton Conway have preferred to include 0. Mathematicians have noted tendencies in which definition

1802-460: A natural number as the class of all sets that are in one-to-one correspondence with a particular set. However, this definition turned out to lead to paradoxes, including Russell's paradox . To avoid such paradoxes, the formalism was modified so that a natural number is defined as a particular set, and any set that can be put into one-to-one correspondence with that set is said to have that number of elements. In 1881, Charles Sanders Peirce provided

1908-461: A natural number is to use one's fingers, as in finger counting . Putting down a tally mark for each object is another primitive method. Later, a set of objects could be tested for equality, excess or shortage—by striking out a mark and removing an object from the set. The first major advance in abstraction was the use of numerals to represent numbers. This allowed systems to be developed for recording large numbers. The ancient Egyptians developed

2014-425: A natural number) there is another ordinal (natural number) larger than it, but still less than ω. Thus, every ordinal is either zero, or a successor (of a well-defined predecessor), or a limit. This distinction is important, because many definitions by transfinite recursion rely upon it. Very often, when defining a function F by transfinite recursion on all ordinals, one defines F (0), and F (α+1) assuming F (α)

2120-526: A need to improve upon the logical rigor in the foundations of mathematics . In the 1860s, Hermann Grassmann suggested a recursive definition for natural numbers, thus stating they were not really natural—but a consequence of definitions. Later, two classes of such formal definitions emerged, using set theory and Peano's axioms respectively. Later still, they were shown to be equivalent in most practical applications. Set-theoretical definitions of natural numbers were initiated by Frege . He initially defined

2226-482: A number like any other. Independent studies on numbers also occurred at around the same time in India , China, and Mesoamerica . Nicolas Chuquet used the term progression naturelle (natural progression) in 1484. The earliest known use of "natural number" as a complete English phrase is in 1763. The 1771 Encyclopaedia Britannica defines natural numbers in the logarithm article. Starting at 0 or 1 has long been

SECTION 20

#1732765057707

2332-507: A powerful system of numerals with distinct hieroglyphs for 1, 10, and all powers of 10 up to over 1 million. A stone carving from Karnak , dating back from around 1500 BCE and now at the Louvre in Paris, depicts 276 as 2 hundreds, 7 tens, and 6 ones; and similarly for the number 4,622. The Babylonians had a place-value system based essentially on

2438-438: A rather surprising alternative solution to the Burali-Forti paradox of the largest ordinal). Rather than defining an ordinal as an equivalence class of well-ordered sets, it will be defined as a particular well-ordered set that (canonically) represents the class. Thus, an ordinal number will be a well-ordered set; and every well-ordered set will be order-isomorphic to exactly one ordinal number. For each well-ordered set T ,

2544-509: A set (because of Russell's paradox ). The standard solution is to define a particular set with n elements that will be called the natural number n . The following definition was first published by John von Neumann , although Levy attributes the idea to unpublished work of Zermelo in 1916. As this definition extends to infinite set as a definition of ordinal number , the sets considered below are sometimes called von Neumann ordinals . The definition proceeds as follows: It follows that

2650-412: A slight modification, for classes of ordinals (a collection of ordinals, possibly too large to form a set, defined by some property): any class of ordinals can be indexed by ordinals (and, when the class is unbounded in the class of all ordinals, this puts it in class-bijection with the class of all ordinals). So the γ {\displaystyle \gamma } -th element in the class (with

2756-574: A subscript (or superscript) "0" is added in the latter case: This section uses the convention N = N 0 = N ∗ ∪ { 0 } {\displaystyle \mathbb {N} =\mathbb {N} _{0}=\mathbb {N} ^{*}\cup \{0\}} . Given the set N {\displaystyle \mathbb {N} } of natural numbers and the successor function S : N → N {\displaystyle S\colon \mathbb {N} \to \mathbb {N} } sending each natural number to

2862-428: Is ω ⋅ γ {\displaystyle \omega \cdot \gamma } (see ordinal arithmetic for the definition of multiplication of ordinals). Similarly, one can consider additively indecomposable ordinals (meaning a nonzero ordinal that is not the sum of two strictly smaller ordinals): the γ {\displaystyle \gamma } -th additively indecomposable ordinal

2968-400: Is ⁠ ω {\displaystyle \omega } ⁠ , which can be identified with the set of natural numbers (so that the ordinal associated with every natural number precedes ω {\displaystyle \omega } ). Indeed, the set of natural numbers is well-ordered—as is any set of ordinals—and since it is downward closed, it can be identified with

3074-513: Is consistent (as it is usually guessed), then Peano arithmetic is consistent. In other words, if a contradiction could be proved in Peano arithmetic, then set theory would be contradictory, and every theorem of set theory would be both true and wrong. The five Peano axioms are the following: These are not the original axioms published by Peano, but are named in his honor. Some forms of the Peano axioms have 1 in place of 0. In ordinary arithmetic,

3180-437: Is a bijection f that preserves the ordering. That is, f ( a ) ≤' f ( b ) if and only if a ≤ b . Provided there exists an order isomorphism between two well-ordered sets, the order isomorphism is unique: this makes it quite justifiable to consider the two sets as essentially identical, and to seek a "canonical" representative of the isomorphism type (class). This is exactly what the ordinals provide, and it also provides

3286-505: Is a free monoid on one generator. This commutative monoid satisfies the cancellation property , so it can be embedded in a group . The smallest group containing the natural numbers is the integers . If 1 is defined as S (0) , then b + 1 = b + S (0) = S ( b + 0) = S ( b ) . That is, b + 1 is simply the successor of b . Analogously, given that addition has been defined, a multiplication operator × {\displaystyle \times } can be defined via

30 (number) - Misplaced Pages Continue

3392-433: Is a proper subset of T . Moreover, either S is an element of T , or T is an element of S , or they are equal. So every set of ordinals is totally ordered . Further, every set of ordinals is well-ordered. This generalizes the fact that every set of natural numbers is well-ordered. Consequently, every ordinal S is a set having as elements precisely the ordinals smaller than S . For example, every set of ordinals has

3498-466: Is a subset of m . In other words, the set inclusion defines the usual total order on the natural numbers. This order is a well-order . Ordinal number A finite set can be enumerated by successively labeling each element with the least natural number that has not been previously used. To extend this process to various infinite sets , ordinal numbers are defined more generally using linearly ordered greek letter variables that include

3604-757: Is also the cardinality of ω or ε 0 (all are countable ordinals). So ω can be identified with ⁠ ℵ 0 {\displaystyle \aleph _{0}} ⁠ , except that the notation ℵ 0 {\displaystyle \aleph _{0}} is used when writing cardinals, and ω when writing ordinals (this is important since, for example, ℵ 0 2 {\displaystyle \aleph _{0}^{2}} = ℵ 0 {\displaystyle \aleph _{0}} whereas ω 2 > ω {\displaystyle \omega ^{2}>\omega } ). Also, ω 1 {\displaystyle \omega _{1}}

3710-552: Is based on set theory . It defines the natural numbers as specific sets . More precisely, each natural number n is defined as an explicitly defined set, whose elements allow counting the elements of other sets, in the sense that the sentence "a set S has n elements" means that there exists a one to one correspondence between the two sets n and S . The sets used to define natural numbers satisfy Peano axioms. It follows that every theorem that can be stated and proved in Peano arithmetic can also be proved in set theory. However,

3816-584: Is based on an axiomatization of the properties of ordinal numbers : each natural number has a successor and every non-zero natural number has a unique predecessor. Peano arithmetic is equiconsistent with several weak systems of set theory . One such system is ZFC with the axiom of infinity replaced by its negation. Theorems that can be proved in ZFC but cannot be proved using the Peano Axioms include Goodstein's theorem . The set of all natural numbers

3922-488: Is closed and unbounded, the intersection of a stationary class and a closed unbounded class is stationary. But the intersection of two stationary classes may be empty, e.g. the class of ordinals with cofinality ω with the class of ordinals with uncountable cofinality. Rather than formulating these definitions for (proper) classes of ordinals, one can formulate them for sets of ordinals below a given ordinal α {\displaystyle \alpha } : A subset of

4028-430: Is closed for the order topology on that ordinal, this is again equivalent). Of particular importance are those classes of ordinals that are closed and unbounded , sometimes called clubs . For example, the class of all limit ordinals is closed and unbounded: this translates the fact that there is always a limit ordinal greater than a given ordinal, and that a limit of limit ordinals is a limit ordinal (a fortunate fact if

4134-600: Is defined, and then, for limit ordinals δ one defines F (δ) as the limit of the F (β) for all β<δ (either in the sense of ordinal limits, as previously explained, or for some other notion of limit if F does not take ordinal values). Thus, the interesting step in the definition is the successor step, not the limit ordinals. Such functions (especially for F nondecreasing and taking ordinal values) are called continuous. Ordinal addition, multiplication and exponentiation are continuous as functions of their second argument (but can be defined non-recursively). Any well-ordered set

4240-406: Is equal to {0, 1} and so it is a subset of {0, 1, 2, 3} . It can be shown by transfinite induction that every well-ordered set is order-isomorphic to exactly one of these ordinals, that is, there is an order preserving bijective function between them. Furthermore, the elements of every ordinal are ordinals themselves. Given two ordinals S and T , S is an element of T if and only if S

4346-461: Is exactly what definition by transfinite recursion permits. In fact, F (0) makes sense since there is no ordinal β < 0 , and the set { F (β) | β < 0} is empty. So F (0) is equal to 0 (the smallest ordinal of all). Now that F (0) is known, the definition applied to F (1) makes sense (it is the smallest ordinal not in the singleton set { F (0)} = {0} ), and so on (the and so on is exactly transfinite induction). It turns out that this example

30 (number) - Misplaced Pages Continue

4452-399: Is greater than ⁠ ℵ 1 {\displaystyle \aleph _{1}} ⁠ , and so on, and ω ω {\displaystyle \omega _{\omega }} is the limit of the ω n {\displaystyle \omega _{n}} for natural numbers n (any limit of cardinals is a cardinal, so this limit is indeed

4558-483: Is indexed as ⁠ ω γ {\displaystyle \omega ^{\gamma }} ⁠ . The technique of indexing classes of ordinals is often useful in the context of fixed points: for example, the γ {\displaystyle \gamma } -th ordinal α {\displaystyle \alpha } such that ω α = α {\displaystyle \omega ^{\alpha }=\alpha }

4664-631: Is less than or equal to some ordinal in the set. The subset is said to be closed under α {\displaystyle \alpha } provided it is closed for the order topology in ⁠ α {\displaystyle \alpha } ⁠ , i.e. a limit of ordinals in the set is either in the set or equal to α {\displaystyle \alpha } itself. There are three usual operations on ordinals: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an explicit well-ordered set that represents

4770-410: Is not closed under subtraction (that is, subtracting one natural from another does not always result in another natural), means that N {\displaystyle \mathbb {N} } is not a ring ; instead it is a semiring (also known as a rig ). If the natural numbers are taken as "excluding 0", and "starting at 1", the definitions of + and × are as above, except that they begin with

4876-403: Is not very exciting, since provably F (α) = α for all ordinals α, which can be shown, precisely, by transfinite induction. Any nonzero ordinal has the minimum element, zero. It may or may not have a maximum element. For example, 42 has maximum 41 and ω+6 has maximum ω+5. On the other hand, ω does not have a maximum since there is no largest natural number. If an ordinal has a maximum α, then it

4982-453: Is one and only one function satisfying the recursion formula up to and including α. Here is an example of definition by transfinite recursion on the ordinals (more will be given later): define function F by letting F (α) be the smallest ordinal not in the set { F (β) | β < α} , that is, the set consisting of all F (β) for β < α . This definition assumes the F (β) known in the very process of defining F ; this apparent vicious circle

5088-511: Is similar (order-isomorphic) to a unique ordinal number α {\displaystyle \alpha } ; in other words, its elements can be indexed in increasing fashion by the ordinals less than ⁠ α {\displaystyle \alpha } ⁠ . This applies, in particular, to any set of ordinals: any set of ordinals is naturally indexed by the ordinals less than some ⁠ α {\displaystyle \alpha } ⁠ . The same holds, with

5194-414: Is so important in relation to ordinals that it is worth restating here. That is, if P (α) is true whenever P (β) is true for all β < α , then P (α) is true for all α. Or, more practically: in order to prove a property P for all ordinals α, one can assume that it is already known for all smaller β < α . Transfinite induction can be used not only to prove things, but also to define them. Such

5300-429: Is standardly denoted N or N . {\displaystyle \mathbb {N} .} Older texts have occasionally employed J as the symbol for this set. Since natural numbers may contain 0 or not, it may be important to know which version is referred to. This is often specified by the context, but may also be done by using a subscript or a superscript in the notation, such as: Alternatively, since

5406-422: Is stationary if it has a nonempty intersection with every closed unbounded class. All superclasses of closed unbounded classes are stationary, and stationary classes are unbounded, but there are stationary classes that are not closed and stationary classes that have no closed unbounded subclass (such as the class of all limit ordinals with countable cofinality). Since the intersection of two closed unbounded classes

SECTION 50

#1732765057707

5512-430: Is that a limit ordinal is the limit in a topological sense of all smaller ordinals (under the order topology ). When ⟨ α ι | ι < γ ⟩ {\displaystyle \langle \alpha _{\iota }|\iota <\gamma \rangle } is an ordinal-indexed sequence, indexed by a limit γ {\displaystyle \gamma } and

5618-456: Is the third largest city in the country", which are called ordinal numbers . Natural numbers are also used as labels, like jersey numbers on a sports team, where they serve as nominal numbers and do not have mathematical properties. The natural numbers form a set , commonly symbolized as a bold N or blackboard bold ⁠ N {\displaystyle \mathbb {N} } ⁠ . Many other number sets are built from

5724-446: Is the next ordinal after α, and it is called a successor ordinal , namely the successor of α, written α+1. In the von Neumann definition of ordinals, the successor of α is α ∪ { α } {\displaystyle \alpha \cup \{\alpha \}} since its elements are those of α and α itself. A nonzero ordinal that is not a successor is called a limit ordinal . One justification for this term

5830-500: Is the only number less than 60 that is neither a prime nor of the aforementioned form. Therefore, 30 is the only candidate for the order of a simple group less than 60, in which one needs other methods to specifically reject to eventually deduce said order. The SI prefix for 10 is Quetta- (Q), and for 10 (i.e., the reciprocal of 10) quecto (q). These numbers are the largest and smallest number to receive an SI prefix to date. Thirty is: Natural number In mathematics ,

5936-426: Is the smallest uncountable ordinal (to see that it exists, consider the set of equivalence classes of well-orderings of the natural numbers: each such well-ordering defines a countable ordinal, and ω 1 {\displaystyle \omega _{1}} is the order type of that set), ω 2 {\displaystyle \omega _{2}} is the smallest ordinal whose cardinality

6042-422: Is used, such as algebra texts including 0, number theory and analysis texts excluding 0, logic and set theory texts including 0, dictionaries excluding 0, school books (through high-school level) excluding 0, and upper-division college-level books including 0. There are exceptions to each of these tendencies and as of 2023 no formal survey has been conducted. Arguments raised include division by zero and

6148-511: Is variously called "Ord", "ON", or "∞". An ordinal is finite if and only if the opposite order is also well-ordered, which is the case if and only if each of its non-empty subsets has a greatest element . There are other modern formulations of the definition of ordinal. For example, assuming the axiom of regularity , the following are equivalent for a set x : These definitions cannot be used in non-well-founded set theories . In set theories with urelements , one has to further make sure that

6254-600: Is written ⁠ ε γ {\displaystyle \varepsilon _{\gamma }} ⁠ . These are called the " epsilon numbers ". A class C {\displaystyle C} of ordinals is said to be unbounded , or cofinal , when given any ordinal ⁠ α {\displaystyle \alpha } ⁠ , there is a β {\displaystyle \beta } in C {\displaystyle C} such that α < β {\displaystyle \alpha <\beta } (then

6360-430: Is written ⁠ ω α {\displaystyle \omega _{\alpha }} ⁠ , it is always a limit ordinal. Its cardinality is written ⁠ ℵ α {\displaystyle \aleph _{\alpha }} ⁠ . For example, the cardinality of ω 0 = ω is ⁠ ℵ 0 {\displaystyle \aleph _{0}} ⁠ , which

6466-530: Is ω+ω), ω·2+1, ω·2+2, and so on, then ω·3, and then later on ω·4. Now the set of ordinals formed in this way (the ω· m + n , where m and n are natural numbers) must itself have an ordinal associated with it: and that is ω . Further on, there will be ω , then ω , and so on, and ω , then ω , then later ω , and even later ε 0 ( epsilon nought ) (to give a few examples of relatively small—countable—ordinals). This can be continued indefinitely (as every time one says "and so on" when enumerating ordinals, it defines

SECTION 60

#1732765057707

6572-720: The Principia Mathematica , defines the order type of a well-ordering as the set of all well-orderings similar (order-isomorphic) to that well-ordering: in other words, an ordinal number is genuinely an equivalence class of well-ordered sets. This definition must be abandoned in ZF and related systems of axiomatic set theory because these equivalence classes are too large to form a set. However, this definition still can be used in type theory and in Quine's axiomatic set theory New Foundations and related systems (where it affords

6678-418: The equivalence relation of "being order-isomorphic". There is a technical difficulty involved, however, in the fact that the equivalence class is too large to be a set in the usual Zermelo–Fraenkel (ZF) formalization of set theory. But this is not a serious difficulty. The ordinal can be said to be the order type of any set in the class. The original definition of ordinal numbers, found for example in

6784-426: The natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers 0, 1, 2, 3, ... , while others start with 1, defining them as the positive integers 1, 2, 3, ... . Some authors acknowledge both definitions whenever convenient. Sometimes, the whole numbers are the natural numbers plus zero. In other cases,

6890-447: The whole numbers refer to all of the integers , including negative integers. The counting numbers are another term for the natural numbers, particularly in primary school education, and are ambiguous as well although typically start at 1. The natural numbers are used for counting things, like "there are six coins on the table", in which case they are called cardinal numbers . They are also used to put things in order, like "this

6996-457: The Prime in the 3 -aliquot tree. From 1 to the number 30 this is the longest Aliquot Sequence. It is also: Furthermore, In a group G , such that | G | = p n × m {\displaystyle |G|=p^{n}\times m} , where p does not divide m , and has a subgroup of order p n {\displaystyle p^{n}} , 30

7102-399: The age of 19, now called definition of von Neumann ordinals : "each ordinal is the well-ordered set of all smaller ordinals". In symbols, ⁠ λ = [ 0 , λ ) {\displaystyle \lambda =[0,\lambda )} ⁠ . Formally: The natural numbers are thus ordinals by this definition. For instance, 2 is an element of 4 = {0, 1, 2, 3}, and 2

7208-728: The axiom of choice, a cardinal may be represented by the set of sets with that cardinality having minimal rank (see Scott's trick ). One issue with Scott's trick is that it identifies the cardinal number 0 {\displaystyle 0} with ⁠ { ∅ } {\displaystyle \{\emptyset \}} ⁠ , which in some formulations is the ordinal number ⁠ 1 {\displaystyle 1} ⁠ . It may be clearer to apply Von Neumann cardinal assignment to finite cases and to use Scott's trick for sets which are infinite or do not admit well orderings. Note that cardinal and ordinal arithmetic agree for finite numbers. The α-th infinite initial ordinal

7314-534: The class must be a proper class, i.e., it cannot be a set). It is said to be closed when the limit of a sequence of ordinals in the class is again in the class: or, equivalently, when the indexing (class-)function F {\displaystyle F} is continuous in the sense that, for δ {\displaystyle \delta } a limit ordinal, F ( δ ) {\displaystyle F(\delta )} (the δ {\displaystyle \delta } -th ordinal in

7420-419: The class) is the limit of all F ( γ ) {\displaystyle F(\gamma )} for γ < δ {\displaystyle \gamma <\delta } ; this is also the same as being closed, in the topological sense, for the order topology (to avoid talking of topology on proper classes, one can demand that the intersection of the class with any given ordinal

7526-412: The convention that the "0-th" is the smallest, the "1-st" is the next smallest, and so on) can be freely spoken of. Formally, the definition is by transfinite induction: the γ {\displaystyle \gamma } -th element of the class is defined (provided it has already been defined for all β < γ {\displaystyle \beta <\gamma } ), as

7632-574: The date of Easter), beginning with Dionysius Exiguus in 525 CE, without being denoted by a numeral. Standard Roman numerals do not have a symbol for 0; instead, nulla (or the genitive form nullae ) from nullus , the Latin word for "none", was employed to denote a 0 value. The first systematic study of numbers as abstractions is usually credited to the Greek philosophers Pythagoras and Archimedes . Some Greek mathematicians treated

7738-490: The definition excludes urelements from appearing in ordinals. If α is any ordinal and X is a set, an α-indexed sequence of elements of X is a function from α to X . This concept, a transfinite sequence (if α is infinite) or ordinal-indexed sequence , is a generalization of the concept of a sequence . An ordinary sequence corresponds to the case α = ω, while a finite α corresponds to a tuple , a.k.a. string . Transfinite induction holds in any well-ordered set, but it

7844-444: The elements of any given well-ordered set (the smallest element being labelled 0, the one after that 1, the next one 2, "and so on"), and to measure the "length" of the whole set by the least ordinal that is not a label for an element of the set. This "length" is called the order type of the set. Any ordinal is defined by the set of ordinals that precede it. In fact, the most common definition of ordinals identifies each ordinal as

7950-470: The expense of continuity. Interpreted as nimbers , a game-theoretic variant of numbers, ordinals can also be combined via nimber arithmetic operations. These operations are commutative but the restriction to natural numbers is generally not the same as ordinary addition of natural numbers. Each ordinal associates with one cardinal , its cardinality. If there is a bijection between two ordinals (e.g. ω = 1 + ω and ω + 1 > ω ), then they associate with

8056-409: The first axiomatization of natural-number arithmetic. In 1888, Richard Dedekind proposed another axiomatization of natural-number arithmetic, and in 1889, Peano published a simplified version of Dedekind's axioms in his book The principles of arithmetic presented by a new method ( Latin : Arithmetices principia, nova methodo exposita ). This approach is now called Peano arithmetic . It

8162-401: The importance of well-ordering is justified by the possibility of applying transfinite induction , which says, essentially, that any property that passes on from the predecessors of an element to that element itself must be true of all elements (of the given well-ordered set). If the states of a computation (computer program or game) can be well-ordered—in such a way that each step is followed by

8268-746: The natural numbers and have the property that every set of ordinals has a least or "smallest" element (this is needed for giving a meaning to "the least unused element"). This more general definition allows us to define an ordinal number ω {\displaystyle \omega } (omega) to be the least element that is greater than every natural number, along with ordinal numbers ⁠ ω + 1 {\displaystyle \omega +1} ⁠ , ⁠ ω + 2 {\displaystyle \omega +2} ⁠ , etc., which are even greater than ⁠ ω {\displaystyle \omega } ⁠ . A linear order such that every non-empty subset has

8374-450: The natural numbers are defined iteratively as follows: It can be checked that the natural numbers satisfy the Peano axioms . With this definition, given a natural number n , the sentence "a set S has n elements" can be formally defined as "there exists a bijection from n to S ." This formalizes the operation of counting the elements of S . Also, n ≤ m if and only if n

8480-403: The natural numbers naturally form a subset of the integers (often denoted Z {\displaystyle \mathbb {Z} } ), they may be referred to as the positive, or the non-negative integers, respectively. To be unambiguous about whether 0 is included or not, sometimes a superscript " ∗ {\displaystyle *} " or "+" is added in the former case, and

8586-435: The natural numbers, this is denoted as ω (omega). In this section, juxtaposed variables such as ab indicate the product a × b , and the standard order of operations is assumed. While it is in general not possible to divide one natural number by another and get a natural number as result, the procedure of division with remainder or Euclidean division is available as a substitute: for any two natural numbers

8692-649: The natural numbers. For example, the integers are made by adding 0 and negative numbers. The rational numbers add fractions, and the real numbers add infinite decimals. Complex numbers add the square root of −1 . This chain of extensions canonically embeds the natural numbers in the other number systems. Natural numbers are studied in different areas of math. Number theory looks at things like how numbers divide evenly ( divisibility ), or how prime numbers are spread out. Combinatorics studies counting and arranging numbered objects, such as partitions and enumerations . The most primitive method of representing

8798-439: The next one, one can define addition of natural numbers recursively by setting a + 0 = a and a + S ( b ) = S ( a + b ) for all a , b . Thus, a + 1 = a + S(0) = S( a +0) = S( a ) , a + 2 = a + S(1) = S( a +1) = S(S( a )) , and so on. The algebraic structure ( N , + ) {\displaystyle (\mathbb {N} ,+)} is a commutative monoid with identity element  0. It

8904-430: The notion of size, which leads to cardinal numbers , and the notion of position, which leads to the ordinal numbers described here. This is because while any set has only one size (its cardinality ), there are many nonisomorphic well-orderings of any infinite set, as explained below. Whereas the notion of cardinal number is associated with a set with no particular structure on it, the ordinals are intimately linked with

9010-413: The number 1 differently than larger numbers, sometimes even not as a number at all. Euclid , for example, defined a unit first and then a number as a multitude of units, thus by his definition, a unit is not a number and there are no unique numbers (e.g., any two units from indefinitely many units is a 2). However, in the definition of perfect number which comes shortly afterward, Euclid treats 1 as

9116-490: The numerals for 1 and 10, using base sixty, so that the symbol for sixty was the same as the symbol for one—its value being determined from context. A much later advance was the development of the idea that  0 can be considered as a number, with its own numeral. The use of a 0 digit in place-value notation (within other numbers) dates back as early as 700 BCE by the Babylonians, who omitted such

9222-550: The operation or by using transfinite recursion. The Cantor normal form provides a standardized way of writing ordinals. It uniquely represents each ordinal as a finite sum of ordinal powers of ω. However, this cannot form the basis of a universal ordinal notation due to such self-referential representations as ε 0 = ω . Ordinals are a subclass of the class of surreal numbers , and the so-called "natural" arithmetical operations for surreal numbers are an alternative way to combine ordinals arithmetically. They retain commutativity at

9328-434: The ordinal associated with it. Perhaps a clearer intuition of ordinals can be formed by examining a first few of them: as mentioned above, they start with the natural numbers, 0, 1, 2, 3, 4, 5, ... After all natural numbers comes the first infinite ordinal, ω, and after that come ω+1, ω+2, ω+3, and so on. (Exactly what addition means will be defined later on: just consider them as names.) After all of these come ω·2 (which

9434-599: The ordinary natural numbers via the ultrapower construction . Other generalizations are discussed in Number § Extensions of the concept . Georges Reeb used to claim provocatively that "The naïve integers don't fill up N {\displaystyle \mathbb {N} } ". There are two standard methods for formally defining natural numbers. The first one, named for Giuseppe Peano , consists of an autonomous axiomatic theory called Peano arithmetic , based on few axioms called Peano axioms . The second definition

9540-486: The other just by counting labels), they are very different in the infinite case, where different infinite ordinals can correspond to sets having the same cardinal. Like other kinds of numbers, ordinals can be added, multiplied, and exponentiated , although none of these operations are commutative . Ordinals were introduced by Georg Cantor in 1883 in order to accommodate infinite sequences and classify derived sets , which he had previously introduced in 1872 while studying

9646-462: The partner of the second element in the second set, and vice versa. Such a one-to-one correspondence is called an order isomorphism , and the two well-ordered sets are said to be order-isomorphic or similar (with the understanding that this is an equivalence relation ). Formally, if a partial order ≤ is defined on the set S , and a partial order ≤' is defined on the set S' , then the posets ( S ,≤) and ( S' ,≤') are order isomorphic if there

9752-404: The same cardinal. Any well-ordered set having an ordinal as its order-type has the same cardinality as that ordinal. The least ordinal associated with a given cardinal is called the initial ordinal of that cardinal. Every finite ordinal (natural number) is initial, and no other ordinal associates with its cardinal. But most infinite ordinals are not initial, as many infinite ordinals associate with

9858-525: The same cardinal. The axiom of choice is equivalent to the statement that every set can be well-ordered, i.e. that every cardinal has an initial ordinal. In theories with the axiom of choice, the cardinal number of any set has an initial ordinal, and one may employ the Von Neumann cardinal assignment as the cardinal's representation. (However, we must then be careful to distinguish between cardinal arithmetic and ordinal arithmetic.) In set theories without

9964-479: The same natural number, the number of elements of the set. This number can also be used to describe the position of an element in a larger finite, or an infinite, sequence . A countable non-standard model of arithmetic satisfying the Peano Arithmetic (that is, the first-order Peano axioms) was developed by Skolem in 1933. The hypernatural numbers are an uncountable model that can be constructed from

10070-528: The sequence is increasing , i.e. α ι < α ρ {\displaystyle \alpha _{\iota }<\alpha _{\rho }} whenever ι < ρ , {\displaystyle \iota <\rho ,} its limit is defined as the least upper bound of the set { α ι | ι < γ } , {\displaystyle \{\alpha _{\iota }|\iota <\gamma \},} that is,

10176-428: The set of ordinals that precede it. For example, the ordinal 42 is generally identified as the set {0, 1, 2, ..., 41}. Conversely, any set S of ordinals that is downward closed — meaning that for any ordinal α in S and any ordinal β < α, β is also in S — is (or can be identified with) an ordinal. This definition of ordinals in terms of sets allows for infinite ordinals. The smallest infinite ordinal

10282-399: The size of the empty set . Computer languages often start from zero when enumerating items like loop counters and string- or array-elements . Including 0 began to rise in popularity in the 1960s. The ISO 31-11 standard included 0 in the natural numbers in its first edition in 1978 and this has continued through its present edition as ISO 80000-2 . In 19th century Europe, there

10388-401: The smallest element greater than the β {\displaystyle \beta } -th element for all ⁠ β < γ {\displaystyle \beta <\gamma } ⁠ . This could be applied, for example, to the class of limit ordinals: the γ {\displaystyle \gamma } -th ordinal, which is either a limit or zero

10494-437: The smallest ordinal (it always exists) greater than any term of the sequence. In this sense, a limit ordinal is the limit of all smaller ordinals (indexed by itself). Put more directly, it is the supremum of the set of smaller ordinals. Another way of defining a limit ordinal is to say that α is a limit ordinal if and only if: So in the following sequence: ω is a limit ordinal because for any smaller ordinal (in this example,

10600-449: The special kind of sets that are called well-ordered . A well-ordered set is a totally ordered set (an ordered set such that, given two distinct elements, one is less than the other) in which every non-empty subset has a least element. Equivalently, assuming the axiom of dependent choice , it is a totally ordered set without any infinite decreasing sequence — though there may be infinite increasing sequences. Ordinals may be used to label

10706-433: The successor of x {\displaystyle x} is x + 1 {\displaystyle x+1} . Intuitively, the natural number n is the common property of all sets that have n elements. So, it seems natural to define n as an equivalence class under the relation "can be made in one to one correspondence ". This does not work in all set theories , as such an equivalence class would not be

10812-412: The terminology is to make any sense at all!). The class of additively indecomposable ordinals, or the class of ε ⋅ {\displaystyle \varepsilon _{\cdot }} ordinals, or the class of cardinals , are all closed unbounded; the set of regular cardinals, however, is unbounded but not closed, and any finite set of ordinals is closed but not unbounded. A class

10918-402: The two definitions are not equivalent, as there are theorems that can be stated in terms of Peano arithmetic and proved in set theory, which are not provable inside Peano arithmetic. A probable example is Fermat's Last Theorem . The definition of the integers as sets satisfying Peano axioms provide a model of Peano arithmetic inside set theory. An important consequence is that, if set theory

11024-423: The two uses of counting and ordering: cardinal numbers and ordinal numbers . The least ordinal of cardinality ℵ 0 (that is, the initial ordinal of ℵ 0 ) is ω but many well-ordered sets with cardinal number ℵ 0 have an ordinal number greater than ω . For finite well-ordered sets, there is a one-to-one correspondence between ordinal and cardinal numbers; therefore they can both be expressed by

11130-434: The uniqueness of trigonometric series . A natural number (which, in this context, includes the number 0 ) can be used for two purposes: to describe the size of a set , or to describe the position of an element in a sequence. When restricted to finite sets, these two concepts coincide, since all linear orders of a finite set are isomorphic . When dealing with infinite sets, however, one has to distinguish between

11236-430: Was mathematical and philosophical discussion about the exact nature of the natural numbers. Henri Poincaré stated that axioms can only be demonstrated in their finite application, and concluded that it is "the power of the mind" which allows conceiving of the indefinite repetition of the same act. Leopold Kronecker summarized his belief as "God made the integers, all else is the work of man". The constructivists saw

#706293