In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, specifically in axiomatic set theory, a Hartogs number is a particular kind of cardinal number

Cardinal number

In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...

. It was shown by Friedrich Hartogs

Friedrich Hartogs

Friedrich Moritz Hartogs was a German-Jewish mathematician, known for work on set theory and foundational results on several complex variables.- See also :*Hartogs domain*Hartogs–Laurent expansion...

 in 1915, from ZF alone (that is, without using the axiom of choice), that there is a least well-ordered cardinal

Cardinal number

In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...

 greater than a given well-ordered cardinal.

To define the Hartogs number of a set it is not in fact necessary that the set be well-orderable: If X is any set, then the Hartogs number of X is the least ordinal

Ordinal number

In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...

 α such that there is no injection

Injective function

In mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...

 from α into X. If X cannot be well-ordered, then we can no longer say that this α is the least well-ordered cardinal greater than the cardinality of X, but it remains the least well-ordered cardinal not less than or equal to the cardinality of X. The map

Map (mathematics)

In most of mathematics and in some related technical fields, the term mapping, usually shortened to map, is either a synonym for function, or denotes a particular kind of function which is important in that branch, or denotes something conceptually similar to a function.In graph theory, a map is a...

 taking X to α is sometimes called Hartogs' function.

Proof

Given some basic theorems of set theory, the proof is simple. Let . First, we verify that α is a set.

1. X × X is a set, as can be seen in axiom of power set.
2. The power set of X × X is a set, by the axiom of power set
   Axiom of power set
   In mathematics, the axiom of power set is one of the Zermelo–Fraenkel axioms of axiomatic set theory.In the formal language of the Zermelo–Fraenkel axioms, the axiom reads:...
   
   .
3. The class W of all reflexive
   Reflexive relation
   In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-Related terms:...
   
    well-orderings of subsets of X is a definable subclass of the preceding set, so it is a set by the axiom schema of separation.
4. The class of all order type
   Order type
   In mathematics, especially in set theory, two ordered sets X,Y are said to have the same order type just when they are order isomorphic, that is, when there exists a bijection f: X → Y such that both f and its inverse are monotone...
   
   s of well-orderings in W is a set by the axiom schema of replacement
   Axiom schema of replacement
   In set theory, the axiom schema of replacement is a schema of axioms in Zermelo–Fraenkel set theory that asserts that the image of any set under any definable mapping is also a set...
   
   , as

   (Domain

   Domain (mathematics)

   In mathematics, the domain of definition or simply the domain of a function is the set of "input" or argument values for which the function is defined...

   
   (w) , w) (β, ≤)

   can be described by a simple formula.

But this last set is exactly α.

Now because a transitive set

Transitive set

In set theory, a set A is transitive, if* whenever x ∈ A, and y ∈ x, then y ∈ A, or, equivalently,* whenever x ∈ A, and x is not an urelement, then x is a subset of A....

of ordinals is again an ordinal, α is an ordinal. Furthermore, if there were an injection from α into X, then we would get the contradiction that α ∈ α. It is claimed that α is the least such ordinal with no injection into X. Given β < α, β ∈ α so there is an injection from β into X.