Hartogs number

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In mathematics, specifically in axiomatic set theory, a Hartogs number is a particular kind of cardinal number. It was shown by Friedrich Hartogs in 1915, from ZF alone (that is, without using the axiom of choice), that there is a least well-ordered cardinal greater than a given well-ordered cardinal.

To define the Hartogs number of a set it is not necessary that the set be well-orderable: If X is any set, then the Hartogs number of X is the least ordinal α such that there is no injection 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 taking X to α is sometimes called Hartogs's function.

Proof[edit]

Given some basic theorems of set theory, the proof is simple. Let

be the class of all ordinal numbers β for which an injective function exists from β into X.

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.
  3. The class W of all reflexive 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 types of well-orderings in W is a set by the axiom schema of replacement, as
    (Domain(w), w) (β, ≤)
    can be described by a simple formula.

But this last set is exactly α.

Now because a transitive set of ordinals is again an ordinal, α is an ordinal. Furthermore, there is no injection from α into X, because if there were, then we would get the contradiction that αα, and finally, α is the least such ordinal with no injection into X. This is true because, since α is an ordinal, for any β < α, βα so there is an injection from β into X.

Historic remark[edit]

Note that, in 1915, Hartogs could use neither von Neumann-ordinals nor the Replacement Axiom, and so his result is one of Zermelo set theory and looks rather different from the above modern exposition. Instead, he considered the set of isomorphism classes of well-ordered subsets of X and the relation in which the class of A precedes that of B if A is isomorphic with a proper initial segment of B. Hartogs showed this to be a well-ordering greater than any well-ordered subset of X. (This must have been historically the first genuine construction of an uncountable well-ordering.) However, the main purpose of his contribution was to show that Trichotomy for cardinal numbers implies the (then 11 year old) Well-ordering Theorem (and, hence, the Axiom of Choice).

See also[edit]

References[edit]

  • Hartogs, Fritz (1915). "Über das Problem der Wohlordnung". Mathematische Annalen (in German). 76 (4): 438–443. doi:10.1007/BF01458215. JFM 45.0125.01.
  • Jech, Thomas (2002). Set theory, third millennium edition (revised and expanded). Springer. ISBN 3-540-44085-2.
  • Charles Morgan. "Axiomatic set theory" (PDF). Course Notes. University of Bristol. Retrieved 2010-04-10.