In
order theory
Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...
and
model theory
In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the s ...
, branches of mathematics, Cantor's isomorphism theorem states that every two countable
dense
Density (volumetric mass density or specific mass) is the substance's mass per unit of volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' can also be used. Mathematically ...
unbounded
linear orders are
order-isomorphic. For instance, there is an isomorphism (a one-to-one order-preserving correspondence) between the numerical ordering of the
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
s and the numerical ordering of the
dyadic rational
In mathematics, a dyadic rational or binary rational is a number that can be expressed as a fraction whose denominator is a power of two. For example, 1/2, 3/2, and 3/8 are dyadic rationals, but 1/3 is not. These numbers are important in compute ...
s, that can be described by
Minkowski's question-mark function.
The isomorphism theorem is named after
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor ( , ; – January 6, 1918) was a German mathematician. He played a pivotal role in the creation of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of ...
, who used it to characterize the (uncountable) ordering on the
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s. It can be proved by a
back-and-forth method In mathematical logic, especially set theory and model theory, the back-and-forth method is a method for showing isomorphism between countably infinite structures satisfying specified conditions. In particular it can be used to prove that
* any t ...
that is also sometimes attributed to Cantor. The same back-and-forth method also proves that countable dense unbounded orders are highly symmetric, and can be applied to other kinds of structures. However, Cantor's original proof only used the "going forth" half of this method. In terms of
model theory
In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the s ...
, the isomorphism theorem can be expressed by saying that the first-order theory of unbounded dense linear orders is
countably categorical, meaning that it has only one countable model, up to logical equivalence.
One application of Cantor's isomorphism theorem involves
temporal logic In logic, temporal logic is any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time (for example, "I am ''always'' hungry", "I will ''eventually'' be hungry", or "I will be hungry ''until'' I ...
, a method for using logic to reason about time. In this application, the theorem implies that it is sufficient to use intervals of rational numbers to model intervals of time: using irrational numbers for this purpose will not lead to any increase in logical power.
Statement and examples
![Minkowski question mark](https://upload.wikimedia.org/wikipedia/commons/1/1b/Minkowski_question_mark.svg)
Cantor's isomorphism theorem is stated using the following concepts:
*A
linear order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive ...
or total order is defined by a set of elements and a comparison operation that gives an ordering to each pair of distinct elements and obeys the
transitive law. The familiar numeric orderings on the
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s,
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
s, and
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s are all examples of linear orders.
*Unboundedness means that the ordering has no minimum or maximum element. All three of these examples are unbounded. The subset of real or rational numbers in the open
unit interval
In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1. It is often denoted ' (capital letter ). In addition to its role in real analysis, ...
(0,1) is similarly unbounded, but the closed unit interval
,1is not: it has a minimum element, 0, and a maximum element, 1.
*An ordering is
dense
Density (volumetric mass density or specific mass) is the substance's mass per unit of volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' can also be used. Mathematically ...
when every pair of elements has another element between them. This is true for the rational numbers and real numbers, where the
arithmetic mean
In mathematics and statistics, the arithmetic mean ( ) or arithmetic average, or just the ''mean'' or the ''average'' (when the context is clear), is the sum of a collection of numbers divided by the count of numbers in the collection. The colle ...
of any two numbers belongs to the same set and lies between them, but not for the integers. For instance, there is no other integer between 0 and 1, so the integers are not
*The integers and rational numbers both form
countable set
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
s, but the real numbers do not, by a different result of Cantor, his
proof that the real numbers are uncountable.
*Two linear orders are
order-isomorphic when there exists a
one-to-one correspondence
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
between them that preserves their ordering. For instance, the integers and the
even number
In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is a multiple of two, and odd if it is not.. For example, −4, 0, 82 are even because
\begin
-2 \cdot 2 &= -4 \\
0 \cdot 2 &= 0 \\
41 ...
s are order-isomorphic, under a bijection that multiplies each integer by two.
With these definitions in hand, Cantor's isomorphism theorem states that every two unbounded countable dense linear orders are
Within the rational numbers, certain subsets are also countable, unbounded, and dense. The rational numbers in the open unit interval are an example. Another example is the set of
dyadic rational
In mathematics, a dyadic rational or binary rational is a number that can be expressed as a fraction whose denominator is a power of two. For example, 1/2, 3/2, and 3/8 are dyadic rationals, but 1/3 is not. These numbers are important in compute ...
numbers, the numbers that can be expressed as a fraction with an integer numerator and a
power of two
A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer as the exponent.
In a context where only integers are considered, is restricted to non-negative ...
as the denominator. By Cantor's isomorphism theorem, the dyadic rational numbers are order-isomorphic to the whole set of rational numbers. In this example, an explicit order isomorphism is provided by
Minkowski's question-mark function. Another example of a countable unbounded dense linear order is given by the set of real
algebraic number
An algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio, (1 + \sqrt)/2, is an algebraic number, because it is a root of the po ...
s, the real roots of polynomials with integer coefficients. In this case, they are a superset of the rational numbers, but are again It is also possible to apply the theorem to other linear orders whose elements are not defined as numbers.
Proofs
One proof of Cantor's isomorphism theorem, in some sources called "the standard uses the
back-and-forth method In mathematical logic, especially set theory and model theory, the back-and-forth method is a method for showing isomorphism between countably infinite structures satisfying specified conditions. In particular it can be used to prove that
* any t ...
. This proof builds up an isomorphism between any two given orders, using a
greedy algorithm
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...
, in an ordering given by a countable enumeration of the two orderings. In more detail, the proof maintains two order-isomorphic finite subsets
and
of the two given orders, initially empty. It repeatedly increases the sizes of
and
by adding a new element from one order, the first missing element in its enumeration, and matching it with an order-equivalent element of the other order, proven to exist using the density and lack of endpoints of the order. It alternates between the two orders for which one it searches for the first missing element, and which one it uses to find a matching element. Every element of each ordering is eventually matched with an order-equivalent element of the other ordering, so the two orderings are
Although the back-and-forth method has also been attributed to Cantor, Cantor's original publication of this theorem in 1895–1897 used a different In an investigation of the history of this theorem by logician Charles L. Silver, the earliest instance of the back-and-forth proof found by Silver was in a 1914 textbook by
Instead of building up order-isomorphic subsets
and
by going "back and forth" between the enumeration for the first order and the enumeration for the second order, Cantor's original proof only uses the "going forth" half of the back-and-forth It repeatedly augments the two finite sets
and
by adding to
the earliest missing element of the first order's enumeration, and adding to
the order-equivalent element that is earliest in the second order's enumeration. This naturally finds an equivalence between the first ordering and a subset of the second ordering, and Cantor then argues that the entire second ordering is
The back-and-forth proof has been mechanized in
Coq
Coq is an interactive theorem prover first released in 1989. It allows for expressing mathematical assertions, mechanically checks proofs of these assertions, helps find formal proofs, and extracts a certified program from the constructive proof ...
, yielding a strengthened result that when two
computably enumerable
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is an algorithm such that the ...
linear orders have a computable comparison predicate, and computable functions representing their density, and unboundedness properties, then the isomorphism between them is also
Model theory
One way of describing Cantor's isomorphism theorem uses the language of
model theory
In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the s ...
. The
first-order theory
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantif ...
of unbounded dense linear orders consists of sentences in mathematical logic concerning variables that represent the elements of an order, with a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
used as the comparison operation of the ordering. These sentences include both axioms, formulating in logical terms the requirements of a dense linear order, and all other sentences that can be proven as logical consequences from those axioms. The axioms can be formulated logically using either a strict comparison
or a non-strict comparison
but the strict comparison simplifies the expression of the axioms for the properties of being unbounded and dense. The axioms of this system can be expressed
A model of this theory is any system of elements and a comparison relation that obeys all of the axioms; it is a ''countable model'' when the system of elements forms a
countable set
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
. For instance, the usual comparison relation on the rational numbers is a countable model of this theory. Cantor's isomorphism theorem can be expressed by saying that the first-order theory of unbounded dense linear orders is
countably categorical: it has only one countable model, up to logical
Because it is countably categorical, the unique model of a categorical theory is a
saturated model
In mathematical logic, and particularly in its subfield model theory, a saturated model ''M'' is one that realizes as many complete types as may be "reasonably expected" given its size. For example, an ultrapower model of the hyperreals is \al ...
. This is a notion involving
types
Type may refer to:
Science and technology Computing
* Typing, producing text via a keyboard, typewriter, etc.
* Data type, collection of values used for computations.
* File type
* TYPE (DOS command), a command to display contents of a file.
* Typ ...
, which, intuitively, describe the behavior of systems of elements from the model. A finite type is a system of logical formulas, with finitely many elements fixed as constants and finitely many free variables called parameters, for which every finite combination of the formulas is realizable by assigning elements of the model to its parameters. In a (countable) saturated model, every finite type is realizable: there is some way of assigning elements to the parameters that simultaneously satisfies all of the formulas in the type. In contrast, types with countably many constants can describe
Dedekind cut
In mathematics, Dedekind cuts, named after German mathematician Richard Dedekind but previously considered by Joseph Bertrand, are а method of construction of the real numbers from the rational numbers. A Dedekind cut is a partition of the rat ...
s, and there are too many of these for the theory of dense unbounded linear orders to be a
stable theory
In the mathematical field of model theory, a complete theory is called stable if it does not have too many types. One goal of classification theory is to divide all complete theories into those whose models can be classified and those whose model ...
. This implies that this theory is not
categorical for higher cardinalities: for any higher cardinality, there must be multiple inequivalent dense unbounded linear orders with the same
A method of
quantifier elimination Quantifier elimination is a concept of simplification used in mathematical logic, model theory, and theoretical computer science. Informally, a quantified statement "\exists x such that \ldots" can be viewed as a question "When is there an x such t ...
in the first-order theory of unbounded dense linear orders can be used to prove that it is a
complete theory In mathematical logic, a theory is complete if it is consistent and for every closed formula in the theory's language, either that formula or its negation is provable. That is, for every sentence \varphi, the theory T contains the sentence or its ...
, meaning that every logical sentence in the language of this theory is either a theorem or the negation of a theorem. This is closely related to being categorical (a sentence is a theorem if it is true of the unique countable model; see the
Łoś–Vaught test In model theory, a branch of mathematical logic, the Łoś–Vaught test is a criterion for a theory to be complete
Complete may refer to:
Logic
* Completeness (logic)
* Completeness of a theory, the property of a theory that every formula in th ...
) but there can exist multiple distinct models that have the same complete theory. In particular, both the ordering on the rational numbers and the ordering on the real numbers are models of the same theory, even though they are different models. Quantifier elimination can also be used in an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
for deciding whether a given sentence is a
Related results
The same back-and-forth method used to prove Cantor's isomorphism theorem also proves that countable dense linear orders are highly symmetric. Their symmetries are called
order automorphisms, and consist of order-preserving bijections from the whole linear order to itself. By the back-and-forth method, every countable dense linear order has order automorphisms that map any set of
points to any other set of
points. This can also be proven directly for the ordering on the rationals, by constructing a
piecewise linear order automorphism with breakpoints at the
given points. This equivalence of all sets of points is summarized by saying that the group of symmetries of a countable dense linear order is "highly homogeneous". However, there is no order automorphism that maps an
ordered pair
In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
of points to its reverse, so these symmetries do not form a
The isomorphism theorem can be extended to systems of any finite or countable number of disjoint sets, sharing an unbounded linear ordering and each dense in each other. All such systems with the same number of sets are order-isomorphic, under any permutation of their sets. give as an example the partition of the rational numbers into the
dyadic rational
In mathematics, a dyadic rational or binary rational is a number that can be expressed as a fraction whose denominator is a power of two. For example, 1/2, 3/2, and 3/8 are dyadic rationals, but 1/3 is not. These numbers are important in compute ...
s and their complement; these two sets are dense in each other, and their union has an order isomorphism to any other pair of unbounded linear orders that are countable and dense in each other. Unlike Cantor's isomorphism theorem, the proof needs the full back-and-forth argument, and not just the "going forth"
Cantor used the isomorphism theorem to characterize the ordering of the
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s, an uncountable set. Unlike the rational numbers, the real numbers are
Dedekind-complete
In mathematics, the least-upper-bound property (sometimes called completeness or supremum property or l.u.b. property) is a fundamental property of the real numbers. More generally, a partially ordered set has the least-upper-bound property if eve ...
, meaning that every subset of the reals that has a finite upper bound has a real least upper bound. They contain the rational numbers, which are dense in the real numbers. By applying the isomorphism theorem, Cantor proved that whenever a linear ordering has the same properties of being Dedekind-complete and containing a countable dense unbounded subset, it must be order-isomorphic to the real
Suslin's problem In mathematics, Suslin's problem is a question about totally ordered sets posed by and published posthumously.
It has been shown to be independent of the standard axiomatic system of set theory known as ZFC: showed that the statement can neither ...
asks whether orders having certain other properties of the order on the real numbers, including unboundedness, density, and the cardinality of the continuum, must be order-isomorphic to the reals; its truth is independent of
Zermelo–Fraenkel set theory
In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as ...
with the
axiom of choice
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...
Another consequence of Cantor's proof is that every finite or countable linear order can be embedded into the rationals, or into any unbounded dense ordering. Calling this a "well known" result of Cantor,
Wacław Sierpiński
Wacław Franciszek Sierpiński (; 14 March 1882 – 21 October 1969) was a Polish mathematician. He was known for contributions to set theory (research on the axiom of choice and the continuum hypothesis), number theory, theory of functions, and t ...
proved an analogous result for higher cardinality: assuming the
continuum hypothesis
In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states that
or equivalently, that
In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this is equivalent to ...
, there exists a linear ordering of cardinality
into which all other linear orderings of cardinality
can be
Baumgartner's axiom In mathematical set theory, Baumgartner's axiom (BA) can be one of three different axioms introduced by James Earl Baumgartner.
A subset of the real line is said to be \aleph_1-dense if every two points are separated by exactly \aleph_1 other poi ...
concerns sets of real numbers, unbounded sets with the property that every two elements are separated by exactly
other elements. It states that each two such sets are order-isomorphic, providing in this way another higher-cardinality analogue of Cantor's isomorphism theorem. It is consistent with ZFC and the negation of the continuum hypothesis, and implied by the but independent of
In
temporal logic In logic, temporal logic is any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time (for example, "I am ''always'' hungry", "I will ''eventually'' be hungry", or "I will be hungry ''until'' I ...
, various formalizations of the concept of an interval of time can be shown to be equivalent to defining an interval by a pair of distinct elements of a dense unbounded linear order. This connection implies that these theories are also countably categorical, and can be uniquely modeled by intervals of rational
References
{{Mathematical logic
Model theory
Order theory