Misplaced Pages

#618381

66-415: Some sets can be enumerated by means of a natural ordering (such as 1, 2, 3, 4, ... for the set of positive integers ), but in other cases it may be necessary to impose a (perhaps arbitrary) ordering. In some contexts, such as enumerative combinatorics , the term enumeration is used more in the sense of counting – with emphasis on determination of the number of elements that a set contains, rather than

132-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

198-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

264-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

330-444: A topological space by using the order topology . When viewed as a topological space, ω 1 {\displaystyle \omega _{1}} is often written as [ 0 , ω 1 ) {\displaystyle [0,\omega _{1})} , to emphasize that it is the space consisting of all ordinals smaller than ω 1 {\displaystyle \omega _{1}} . If

396-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} }

462-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 :

528-484: A counting notion where we are interested in "how many" rather than "in what order." In practice, this broad meaning of enumeration is often used to compare the relative sizes or cardinalities of different sets. If one works in Zermelo–Fraenkel set theory without the axiom of choice, one may want to impose the additional restriction that an enumeration must also be injective (without repetition) since in this theory,

594-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

660-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

726-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

SECTION 10

#1732773173619

792-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

858-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

924-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

990-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

1056-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

1122-454: A set with an enumeration but not a computable enumeration is the complement of the halting set . Furthermore, this characterization illustrates a place where the ordering of the listing is important. There exists a computable enumeration of the halting set, but not one that lists the elements in an increasing ordering. If there were one, then the halting set would be decidable , which is provably false. In general, being recursively enumerable

1188-441: 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 the natural numbers. For example, the integers are made by adding 0 and negative numbers. The rational numbers add fractions, and

1254-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

1320-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,

1386-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

SECTION 20

#1732773173619

1452-412: 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 . First uncountable ordinal In mathematics , the first uncountable ordinal , traditionally denoted by ω 1 {\displaystyle \omega _{1}} or sometimes by Ω {\displaystyle \Omega } ,

1518-410: Is a well-ordered set , with set membership serving as the order relation. ω 1 {\displaystyle \omega _{1}} is a limit ordinal , i.e. there is no ordinal α {\displaystyle \alpha } such that ω 1 = α + 1 {\displaystyle \omega _{1}=\alpha +1} . The cardinality of

1584-454: Is a more general notion of an enumeration than the characterization requiring the domain of the listing function to be an initial segment of the Natural numbers where the domain of the enumerating function can assume any ordinal . Under this definition, an enumeration of a set S is any surjection from an ordinal α onto S . The more restrictive version of enumeration mentioned before

1650-466: Is a theorem of ZF that any well-ordered set can be enumerated under this characterization so that it coincides up to relabeling with the generalized listing enumeration. If one also assumes the Axiom of Choice , then all sets can be enumerated so that it coincides up to relabeling with the most general form of enumerations. Since set theorists work with infinite sets of arbitrarily large cardinalities ,

1716-419: Is a weaker condition than being a decidable set . The notion of enumeration has also been studied from the point of view of computational complexity theory for various tasks in the context of enumeration algorithms . Positive integer In mathematics , 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

1782-422: Is also often used for computably enumerable sets , which are the countable sets for which an enumeration function can be computed with an algorithm. For avoiding to distinguish between finite and countably infinite set, it is often useful to use another definition that is equivalent: A set S is countable if and only if there exists an injective function from it into the natural numbers. In set theory , there

1848-469: Is an arbitrary ordinal, we define ω α {\displaystyle \omega _{\alpha }} as the initial ordinal of the cardinal ℵ α {\displaystyle \aleph _{\alpha }} . The existence of ω 1 {\displaystyle \omega _{1}} can be proven without the axiom of choice . For more, see Hartogs number . Any ordinal number can be turned into

1914-503: Is another countable ordinal. The topological space [ 0 , ω 1 ) {\displaystyle [0,\omega _{1})} is sequentially compact , but not compact . As a consequence, it is not metrizable . It is, however, countably compact and thus not Lindelöf (a countably compact space is compact if and only if it is Lindelöf). In terms of axioms of countability , [ 0 , ω 1 ) {\displaystyle [0,\omega _{1})}

1980-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,

2046-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

Enumeration - Misplaced Pages Continue

2112-404: Is done by means of natural numbers . That is, an enumeration of a set S is a bijective function from the natural numbers N {\displaystyle \mathbb {N} } or an initial segment {1, ..., n } of the natural numbers to S . A set is countable if it can be enumerated, that is, if there exists an enumeration of it. Otherwise, it is uncountable . For example,

2178-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

2244-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

2310-486: Is the smallest ordinal number that, considered as a set , is uncountable . It is the supremum (least upper bound) of all countable ordinals. When considered as a set, the elements of ω 1 {\displaystyle \omega _{1}} are the countable ordinals (including finite ordinals), of which there are uncountably many. Like any ordinal number (in von Neumann's approach ), ω 1 {\displaystyle \omega _{1}}

2376-513: Is the special case where α is a finite ordinal or the first limit ordinal ω. This more generalized version extends the aforementioned definition to encompass transfinite listings. Under this definition, the first uncountable ordinal ω 1 {\displaystyle \omega _{1}} can be enumerated by the identity function on ω 1 {\displaystyle \omega _{1}} so that these two notions do not coincide. More generally, it

2442-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

2508-410: The axiom of countable choice holds, every increasing ω-sequence of elements of [ 0 , ω 1 ) {\displaystyle [0,\omega _{1})} converges to a limit in [ 0 , ω 1 ) {\displaystyle [0,\omega _{1})} . The reason is that the union (i.e., supremum) of every countable set of countable ordinals

2574-595: The continuum hypothesis , the cardinality of ω 1 {\displaystyle \omega _{1}} is ℶ 1 {\displaystyle \beth _{1}} , the same as that of R {\displaystyle \mathbb {R} } —the set of real numbers . In most constructions, ω 1 {\displaystyle \omega _{1}} and ℵ 1 {\displaystyle \aleph _{1}} are considered equal as sets. To generalize: if α {\displaystyle \alpha }

2640-406: 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, the whole numbers refer to all of the integers , including negative integers. The counting numbers are another term for

2706-515: 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

Enumeration - Misplaced Pages Continue

2772-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

2838-523: The default definition among this group of mathematicians of an enumeration of a set tends to be any arbitrary α-sequence exactly listing all of its elements. Indeed, in Jech's book, which is a common reference for set theorists, an enumeration is defined to be exactly this. Therefore, in order to avoid ambiguity, one may use the term finitely enumerable or denumerable to denote one of the corresponding types of distinguished countable enumerations. Formally,

2904-503: The existence of a surjection from I onto S need not imply the existence of an injection from S into I . In computability theory one often considers countable enumerations with the added requirement that the mapping from N {\displaystyle \mathbb {N} } (set of all natural numbers) to the enumerated set must be computable . The set being enumerated is then called recursively enumerable (or computably enumerable in more contemporary language), referring to

2970-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

3036-490: The most inclusive definition of an enumeration of a set S is any surjection from an arbitrary index set I onto S . In this broad context, every set S can be trivially enumerated by the identity function from S onto itself. If one does not assume the axiom of choice or one of its variants, S need not have any well-ordering . Even if one does assume the axiom of choice, S need not have any natural well-ordering. This general definition therefore lends itself to

3102-426: The most natural and common prerequisite is that the index set be well-ordered . According to this characterization, an ordered enumeration is defined to be a surjection (an onto relationship) with a well-ordered domain. This definition is natural in the sense that a given well-ordering on the index set provides a unique way to list the next element given a partial enumeration. Unless otherwise specified, an enumeration

3168-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

3234-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

3300-470: 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 is the third largest city in the country", which are called ordinal numbers . Natural numbers are also used as labels, like jersey numbers on

3366-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

SECTION 50

#1732773173619

3432-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

3498-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

3564-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

3630-437: The objective is to count partitions or graphs that meet certain conditions. In set theory , the notion of enumeration has a broader sense, and does not require the set being enumerated to be finite. When an enumeration is used in an ordered list context, we impose some sort of ordering structure requirement on the index set . While we can make the requirements on the ordering quite lax in order to allow for great generality,

3696-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

3762-491: The production of an explicit listing of those elements. In combinatorics, enumeration means counting , i.e., determining the exact number of elements of finite sets, usually grouped into infinite families, such as the family of sets each consisting of all permutations of some finite set. There are flourishing subareas in many branches of mathematics concerned with enumerating in this sense objects of special kinds. For instance, in partition enumeration and graph enumeration

3828-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

3894-426: The set ω 1 {\displaystyle \omega _{1}} is the first uncountable cardinal number , ℵ 1 {\displaystyle \aleph _{1}} ( aleph-one ). The ordinal ω 1 {\displaystyle \omega _{1}} is thus the initial ordinal of ℵ 1 {\displaystyle \aleph _{1}} . Under

3960-399: The set of the real numbers is uncountable. A set is finite if it can be enumerated by means of a proper initial segment {1, ..., n } of the natural numbers, in which case, its cardinality is n . The empty set is finite, as it can be enumerated by means of the empty initial segment of the natural numbers. The term enumerable set is sometimes used for countable sets. However it

4026-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

SECTION 60

#1732773173619

4092-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

4158-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

4224-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

4290-542: The use of recursion theory in formalizations of what it means for the map to be computable. In this sense, a subset of the natural numbers is computably enumerable if it is the range of a computable function. In this context, enumerable may be used to mean computably enumerable. However, these definitions characterize distinct classes since there are uncountably many subsets of the natural numbers that can be enumerated by an arbitrary function with domain ω and only countably many computable functions. A specific example of

4356-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

#618381