HOME

TheInfoList




In
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
, a set is countable if it has the same
cardinality In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
(the
number A number is a mathematical object A mathematical object is an abstract concept arising in mathematics. In the usual language of mathematics, an ''object'' is anything that has been (or could be) formally defined, and with which one may do deduct ...
of elements of the set) as some
subset In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...

subset
of the set of
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...
s N = . Equivalently, a set ''S'' is ''countable'' if there exists an
injective function In , an injective function (also known as injection, or one-to-one function) is a that maps elements to distinct elements; that is, implies . In other words, every element of the function's is the of one element of its . The term must no ...

injective function
''f'' : ''S'' → N from ''S'' to N; it simply means that every element in ''S'' has the correspondence to a different element in N. A countable set is either a
finite set In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
or a countably infinite set. Whether finite or infinite, the elements of a countable set can always be counted one at a time and — although the counting may never finish due to the infinite number of the elements to be counted — every element of the set is associated with a unique natural number.
Georg Cantor Georg Ferdinand Ludwig Philipp Cantor ( , ;  – January 6, 1918) was a German mathematician. He created set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence be ...
introduced the concept of countable sets, contrasting sets that are countable with those that are
uncountable In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
. Today, countable sets form the foundation of a branch of mathematics called
discrete mathematics Discrete mathematics is the study of mathematical structures In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geom ...
.


A note on terminology

Although the terms "countable" and "countably infinite" as defined here are quite common, the terminology is not universal. An alternative style uses ''countable'' to mean what is here called countably infinite, and ''at most countable'' to mean what is here called countable. To avoid ambiguity, one may limit oneself to the terms "at most countable" and "countably infinite", although with respect to
concision Concision (also called brevity, laconicism, or conciseness) is a writing principle of eliminating redundancy.UNT Writing Lab. "Concision, Clarity, and Cohesion." Accessed June 19, 2012Link./ref> For example, a sentence of "It is a fact that most a ...
this is the worst of both worlds. The reader is advised to check the definition in use when encountering the term "countable" in the literature. The terms ''enumerable'' and denumerable may also be used, e.g. referring to countable and countably infinite respectively, but as definitions vary the reader is once again advised to check the definition in use.


Definition

The most concise definition is in terms of
cardinality In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
. A set is ''countable'' if its cardinality , S, is less than or equal to \aleph_0 (
aleph-null In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...

aleph-null
), the cardinality of the set of
natural numbers In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...

natural numbers
N. A set is ''countably
infinite Infinite may refer to: Mathematics *Infinite set, a set that is not a finite set *Infinity, an abstract concept describing something without any limit Music *Infinite (band), a South Korean boy band *''Infinite'' (EP), debut EP of American musi ...
'' if , S, = \aleph_0. A set is ''
uncountable In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...

uncountable
'' if it is not countable, i.e. its cardinality is greater than \aleph_0; the reader is referred to
Uncountable set In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
for further discussion. For every set , the following propositions are equivalent: * is countable. * There exists an
injective function In , an injective function (also known as injection, or one-to-one function) is a that maps elements to distinct elements; that is, implies . In other words, every element of the function's is the of one element of its . The term must no ...

injective function
from to N. * is empty or there exists a
surjective function In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

surjective function
from N to . * There exists a
bijective In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
mapping between and a subset of N. * is either
finite Finite is the opposite of Infinity, infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected ...
or countably infinite. Similarly, the following propositions are equivalent: * is countably infinite. * There is an injective and surjective (and therefore
bijective In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

bijective
) mapping between and N. * has a
one-to-one correspondence In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
with N. * The elements of can be arranged in an infinite sequence a_0, a_1, a_2, \ldots, where a_i is distinct from a_j for i\neq j and every element of is listed.


History

In 1874, in his first set theory article, Cantor proved that the set of
real number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
s is uncountable, thus showing that not all infinite sets are countable. In 1878, he used one-to-one correspondences to define and compare cardinalities. In 1883, he extended the natural numbers with his infinite ordinals, and used sets of ordinals to produce an infinity of sets having different infinite cardinalities.


Introduction

A '' set'' is a collection of ''elements'', and may be described in many ways. One way is simply to list all of its elements; for example, the set consisting of the integers 3, 4, and 5 may be denoted , called roster form. This is only effective for small sets, however; for larger sets, this would be time-consuming and error-prone. Instead of listing every single element, sometimes an ellipsis ("...") is used to represent many elements between the starting element and the end element in a set, if the writer believes that the reader can easily guess what ... represents; for example, presumably denotes the set of
integer An integer (from the Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', meaning "to share" or "to ...
s from 1 to 100. Even in this case, however, it is still ''possible'' to list all the elements, because number of elements in the set is finite. Some sets are ''infinite''; these sets have more than ''n'' elements where ''n'' is any integer that can be specified. (No matter how large the specified integer ''n'' is, such as ''n'' = 9 × 1032, infinite sets have more than ''n'' elements.) For example, the set of natural numbers, denotable by , has infinitely many elements, and we cannot use any natural number to give its size. Nonetheless, it turns out that infinite sets do have a well-defined notion of size (or more properly, ''cardinality'', the technical term for the number of elements in a set), and not all infinite sets have the same cardinality. To understand what this means, we first examine what it ''does not'' mean. For example, there are infinitely many odd integers, infinitely many even integers, and (hence) infinitely many integers overall. However, it turns out that the number of even integers, which is the same as the number of odd integers, is also the same as the number of integers overall. This is because we can arrange things such that, for every integer, there is a distinct even integer:\ldots \, -\! 2\! \rightarrow \! - \! 4, \, -\! 1\! \rightarrow \! - \! 2, \, 0\! \rightarrow \! 0, \, 1\! \rightarrow \! 2, \, 2\! \rightarrow \! 4 \, \ldotsor, more generally, n \rightarrow 2n (see picture). What we have done here is arrange the integers and the even integers into a ''one-to-one correspondence'' (or ''
bijection In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

bijection
''), which is a
function Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically. Modern comp ...
that maps between two sets such that each element of each set corresponds to a single element in the other set. However, not all infinite sets have the same cardinality. For example,
Georg Cantor Georg Ferdinand Ludwig Philipp Cantor ( , ;  – January 6, 1918) was a German mathematician. He created set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence be ...
(who introduced this concept) demonstrated that the real numbers cannot be put into one-to-one correspondence with the natural numbers (non-negative integers), and therefore that the set of real numbers has a greater cardinality than the set of natural numbers.


Formal overview

By definition, a set ''S'' is ''countable'' if there exists an
injective function In , an injective function (also known as injection, or one-to-one function) is a that maps elements to distinct elements; that is, implies . In other words, every element of the function's is the of one element of its . The term must no ...

injective function
''f'' : ''S'' → N from ''S'' to the
natural numbers In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...

natural numbers
N = . It simply means that every element in ''S'' has the correspondence to a different element in N''.'' It might seem natural to divide the sets into different classes: put all the sets containing one element together; all the sets containing two elements together; ...; finally, put together all infinite sets and consider them as having the same size. This view is not tenable, however, under the natural definition of size. To elaborate this, we need the concept of a
bijection In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

bijection
. Although a "bijection" may seem a more advanced concept than a number, the usual development of mathematics in terms of set theory defines functions before numbers, as they are based on much simpler sets. This is where the concept of a bijection comes in: define the correspondence :''a'' ↔ 1, ''b'' ↔ 2, ''c'' ↔ 3 Since every element of is paired with ''precisely one'' element of , ''and'' vice versa, this defines a bijection. We now generalize this situation; we ''define'' that two sets are of the same size, if and only if there is a bijection between them. For all finite sets, this gives us the usual definition of "the same size". As for the case of infinite sets, consider the sets ''A'' = , the set of positive
integer An integer (from the Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', meaning "to share" or "to ...
s, and ''B'' = , the set of even positive integers. We claim that, under our definition, these sets have the same size, and that therefore ''B'' is countably infinite. Recall that to prove this, we need to exhibit a bijection between them. This can be achieved using the assignment ''n'' ↔ 2''n'', so that :1 ↔ 2, 2 ↔ 4, 3 ↔ 6, 4 ↔ 8, .... As in the earlier example, every element of A has been paired off with precisely one element of B, and vice versa. Hence they have the same size. This is an example of a set of the same size as one of its proper subsets, which is impossible for finite sets. Likewise, the set of all
ordered pair In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...

ordered pair
s of natural numbers (the
Cartesian product In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
of two sets of natural numbers, N × N) is countably infinite, as can be seen by following a path like the one in the picture: The resulting
mapping Mapping may refer to: * Mapping (cartography), the process of making a map * Mapping (mathematics), a synonym for a mathematical function and its generalizations ** Mapping (logic), a synonym for functional predicate Types of mapping * Animated ...
proceeds as follows: :0 ↔ (0, 0), 1 ↔ (1, 0), 2 ↔ (0, 1), 3 ↔ (2, 0), 4 ↔ (1, 1), 5 ↔ (0, 2), 6 ↔ (3, 0), .... This mapping covers all such ordered pairs. This form of triangular mapping
recursively Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...

recursively
generalizes to ''n''-
tuple In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
s of natural numbers, i.e., (''a1'', ''a2'', ''a3'', ..., ''an'') where ''ai'' and ''n'' are natural numbers, by repeatedly mapping the first two elements of a ''n''-tuple to a natural number. For example, (0, 2, 3) can be written as ((0, 2), 3). Then (0, 2) maps to 5 so ((0, 2), 3) maps to (5, 3), then (5, 3) maps to 39. Since a different 2-tuple, that is a pair such as (''a'', ''b''), maps to a different natural number, a difference between two n-tuples by a single element is enough to ensure the n-tuples being mapped to different natural numbers. So, an injection from the set of ''n''-tuples to the set of natural numbers N is proved. For the set of n-tuples made by the Cartesian product of finitely many different sets, each element in each tuple has the correspondence to a natural number, so every tuple can be written in natural numbers then the same logic is applied to prove the theorem. Theorem: The
Cartesian product In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
of finitely many countable sets is countable. The set of all
integer An integer (from the Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', meaning "to share" or "to ...
s Z and the set of all
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction (mathematics), fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ) ...
s Q may intuitively seem much bigger than N. But looks can be deceiving. If a pair is treated as the
numerator A fraction (from Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power of the Rom ...
and
denominator A fraction (from Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power of the Rom ...
of a
vulgar fraction A fraction (from Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power of the Ro ...
(a fraction in the form of ''a''/''b'' where ''a'' and ''b'' ≠ 0 are integers), then for every positive fraction, we can come up with a distinct natural number corresponding to it. This representation also includes the natural numbers, since every natural number is also a fraction ''N''/1. So we can conclude that there are exactly as many positive rational numbers as there are positive integers. This is also true for all rational numbers, as can be seen below. Theorem: Z (the set of all integers) and Q (the set of all rational numbers) are countable. In a similar manner, the set of
algebraic number An algebraic number is any complex number In mathematics, a complex number is an element of a number system that contains the real numbers and a specific element denoted , called the imaginary unit, and satisfying the equation . Moreover, ev ...
s is countable. Sometimes more than one mapping is useful: a set A to be shown as countable is one-to-one mapped (injection) to another set B, then A is proved as countable if B is one-to-one mapped to the set of natural numbers. For example, the set of positive
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction (mathematics), fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ) ...
s can easily be one-to-one mapped to the set of natural number pairs (2-tuples) because ''p''/''q ''maps to (''p'', ''q''). Since the set of natural number pairs is one-to-one mapped (actually one-to-one correspondence or bijection) to the set of natural numbers as shown above, the positive rational number set is proved as countable. Theorem: Any finite union of countable sets is countable. With the foresight of knowing that there are uncountable sets, we can wonder whether or not this last result can be pushed any further. The answer is "yes" and "no", we can extend it, but we need to assume a new axiom to do so. Theorem: (Assuming the
axiom of countable choice The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom An axiom, postulate or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The ...

axiom of countable choice
) The union of countably many countable sets is countable. For example, given countable sets a, b, c, ... Using a variant of the triangular enumeration we saw above: *''a''0 maps to 0 *''a''1 maps to 1 *''b''0 maps to 2 *''a''2 maps to 3 *''b''1 maps to 4 *''c''0 maps to 5 *''a''3 maps to 6 *''b''2 maps to 7 *''c''1 maps to 8 *''d''0 maps to 9 *''a''4 maps to 10 *... This only works if the sets a, b, c, ... are . If not, then the union is even smaller and is therefore also countable by a previous theorem. We need the
axiom of countable choice The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom An axiom, postulate or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The ...

axiom of countable choice
to index ''all'' the sets a, b, c, ... simultaneously. Theorem: The set of all finite-length
sequence In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

sequence
s of natural numbers is countable. This set is the union of the length-1 sequences, the length-2 sequences, the length-3 sequences, each of which is a countable set (finite Cartesian product). So we are talking about a countable union of countable sets, which is countable by the previous theorem. Theorem: The set of all finite
subset In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...

subset
s of the natural numbers is countable. The elements of any finite subset can be ordered into a finite sequence. There are only countably many finite sequences, so also there are only countably many finite subsets. Theorem: Let ''S'' and ''T'' be sets. # If the function ''f'' : ''S'' → ''T'' is injective and ''T'' is countable then ''S'' is countable. # If the function ''g'' : ''S'' → ''T'' is surjective and ''S'' is countable then ''T'' is countable. These follow from the definitions of countable set as injective / surjective functions.
Cantor's theorem In elementary set theory illustrating the intersection (set theory), intersection of two set (mathematics), sets. Set theory is a branch of mathematical logic that studies Set (mathematics), sets, which informally are collections of objects. ...
asserts that if ''A'' is a set and ''P''(''A'') is its
power set In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities an ...
, i.e. the set of all subsets of ''A'', then there is no surjective function from ''A'' to ''P''(''A''). A proof is given in the article
Cantor's theorem In elementary set theory illustrating the intersection (set theory), intersection of two set (mathematics), sets. Set theory is a branch of mathematical logic that studies Set (mathematics), sets, which informally are collections of objects. ...
. As an immediate consequence of this and the Basic Theorem above we have: Proposition: The set ''P''(N) is not countable; i.e. it is
uncountable In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...

uncountable
. For an elaboration of this result see
Cantor's diagonal argument 250px, An illustration of Cantor's diagonal argument (in base 2) for the existence of uncountable sets. The sequence at the bottom cannot occur anywhere in the enumeration of sequences above. In set theory, Cantor's diagonal argument, also cal ...
. The set of
real number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
s is uncountable, and so is the set of all infinite
sequence In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

sequence
s of natural numbers.


Minimal model of set theory is countable

If there is a set that is a standard model (see
inner model In set theory illustrating the intersection (set theory), intersection of two set (mathematics), sets. Set theory is a branch of mathematical logic that studies Set (mathematics), sets, which informally are collections of objects. Although any t ...
) of ZFC set theory, then there is a minimal standard model (''see''
Constructible universe In mathematics, in set theory, the constructible universe (or Gödel's constructible universe), denoted by , is a particular Class (set theory), class of Set (mathematics), sets that can be described entirely in terms of simpler sets. is the union ...
). The
Löwenheim–Skolem theorem In mathematical logic, the Löwenheim–Skolem theorem is a theorem on the existence and cardinal number, cardinality of model theory, models, named after Leopold Löwenheim and Thoralf Skolem. The precise formulation is given below. It implies th ...
can be used to show that this minimal model is countable. The fact that the notion of "uncountability" makes sense even in this model, and in particular that this model ''M'' contains elements that are: * subsets of ''M'', hence countable, * but uncountable from the point of view of ''M'', was seen as paradoxical in the early days of set theory, see Skolem's paradox for more. The minimal standard model includes all the
algebraic number An algebraic number is any complex number In mathematics, a complex number is an element of a number system that contains the real numbers and a specific element denoted , called the imaginary unit, and satisfying the equation . Moreover, ev ...
s and all effectively computable
transcendental number In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
s, as well as many other kinds of numbers.


Total orders

Countable sets can be
totally ordered In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
in various ways, for example: *
Well-order In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
s (see also
ordinal number In set theory Set theory is the branch of that studies , which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of , is mostly concerned with those that ...
): **The usual order of natural numbers (0, 1, 2, 3, 4, 5, ...) **The integers in the order (0, 1, 2, 3, ...; −1, −2, −3, ...) *Other (''not'' well orders): **The usual order of integers (..., −3, −2, −1, 0, 1, 2, 3, ...) **The usual order of rational numbers (Cannot be explicitly written as an ordered list!) In both examples of well orders here, any subset has a ''least element''; and in both examples of non-well orders, ''some'' subsets do not have a ''least element''. This is the key definition that determines whether a total order is also a well order.


See also

*
Aleph number In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
*
Counting Counting is the process of determining the number of Element (mathematics), elements of a finite set of objects, i.e., determining the size (mathematics), size of a set. The traditional way of counting consists of continually increasing a (mental ...
* Hilbert's paradox of the Grand Hotel *
Uncountable set In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...


Notes


Citations


References

* * * * * * Reprinted by Springer-Verlag, New York, 1974. (Springer-Verlag edition). Reprinted by Martino Fine Books, 2011. (Paperback edition). * * * * {{Set theory Basic concepts in infinite set theory Cardinal numbers Infinity