alternative definition of cardinality


The concept of cardinality comes from the notion of equinumerosity of sets. To define the cardinality |A| of a set A, one desirable property is that A is equinumerous to B precisely when |A|=|B|. The first attempt, due to Frege and Russel, is to define a relationMathworldPlanetmathPlanetmath on the class V of sets so that AB iff there is a bijection from A to B. This relation is an equivalence relationMathworldPlanetmath on V. Then we can define |A| as the equivalence classMathworldPlanetmath containing the set A. However, |A| is not a set, so we can’t do much with |A| in ZF.

The second attempt, due to Von Neumann, defines |A| to be the smallest ordinalMathworldPlanetmathPlanetmath card(A) equinumerous to A. Now, card(A) exists if A is well-orderable. But in general, we do not know if A is well-orderable unless the well-ordering principle is applied, which is just another form of the axiom of choiceMathworldPlanetmath. Thus, this definition depends on AC, and, in everyday mathematical usage (which assumes ZFC), |A|:=card(A) suffices.

The third way, due to Scott, of looking at |A|, without AC, is to modify the first attempt somewhat, so that |A| is a set. Recall that the rank of a set A is the least ordinal α such that AVα in the cumulative hierarchy. A set having a rank is said to be grounded. By the axiom of foundationMathworldPlanetmath, every set is grounded. For any set A, let R(A):={ρ(B)BA}. Then R(A), as a class of ordinals, has a least element r(A). So r(A)ρ(A). Next, we define (borrowing the terminology used in the first reference below)

kard(A):={BBA and ρ(B)=r(A)},

and set |A|:=kard(A). Since every element in kard(A) is a subset of Vr(A), kard(A)Vr(A)+, so that |A| is a set. This method is known as Scott’s trick. It can also be used in defining other isomorphismPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath types on sets. It is easy to see that |A|=|B| iff AB. However, with this definition, kard(n)n in general, where n is a natural numberMathworldPlanetmath.

Nevertheless, it is known that every finite setMathworldPlanetmath is well-orderable, and so we come to the fourth definition of the cardinality of a set: given a set A:

|A|:={card(A) if A is well-orderable,kard(A) otherwise .

The one big advantage of this definition is clear: it does not require AC, and with AC, it is identical to the second definition above. At the same time, it also resolves the conflict with our intuitive notion about cardinality: the cardinality of a finite set is the number of elements in the set. However, the one big disadvantage in this definition is that we do not have A|A| in general (of course, A is infiniteMathworldPlanetmath). There is no way, without AC, to find a definition of |A|, such that AB iff |A|=|B|, and A|A| at the same time.

References

  • 1 H. Enderton, Elements of Set TheoryMathworldPlanetmath, Academic Press, Orlando, FL (1977).
  • 2 T. J. Jech, Set Theory, 3rd Ed., Springer, New York, (2002).
  • 3 A. Levy, Basic Set Theory, Dover Publications Inc., (2002).
Title alternative definition of cardinality
Canonical name AlternativeDefinitionOfCardinality
Date of creation 2013-03-22 18:50:11
Last modified on 2013-03-22 18:50:11
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 10
Author CWoo (3771)
Entry type Definition
Classification msc 03E10