Rank

The word "rank" refers to several related concepts in mathematics involving graphs, groups, matrices, quadratic forms, sequences, set theory, statistics, and tensors.

In graph theory, the graph rank of a graph  is defined as , where  is the number of vertices on  and  is the number of connected components (Biggs 1993, p. 25).

In set theory, rank is a (class) function from sets to ordinal numbers. The rank of a set is the least ordinal number greater than the rank of any member of the set (Mirimanoff 1917; Moore 1982, pp. 261-262; Rubin 1967, p. 214). The proof that rank is well-defined uses the axiom of foundation.

For example, the empty set  has rank 0 (since it has no members and 0 is the least ordinal number),  has rank 1 (since , its only member, has rank 0),  has rank 2, and  has rank . Every ordinal number has itself as its rank.

Mirimanoff (1917) showed that, assuming the class of urelements is a set, for any ordinal number , the class of all sets having rank  is a set, i.e., not a proper class (Rubin 1967, p. 216) The number of sets having rank  for , 1, ... are 1, 1, 2, 12, 65520, ... (OEIS A038081), and the number of sets having rank at most  is , 1, 2, 4, 16, 65536, ... (OEIS A014221).

The rank of a mathematical object is defined whenever that object is free. In general, the rank of a free object is the cardinal number of the free generating subset .

---

REFERENCES

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, p. 73, 1993.Mirimanoff, D. "Les antinomies de Russell et de Burali-Forti et le problème fondamental de la théorie des ensembles." Enseign. math. 19, 37-52, 1917.Moore, G. H. Zermelo's Axiom of Choice: Its Origin, Development, and Influence. New York: Springer-Verlag, 1982.Rubin, J. E. Set Theory for the Mathematician. New York: Holden-Day, 1967.Sloane, N. J. A. Sequences A014221 and A038081 in "The On-Line Encyclopedia of Integer Sequences."

مواضيع ذات صلة

Subset

Set Class

Set

Second Category

Proper Subset

Power Set

Matroid

Inductive Set

Independent Vertex Set

Independent Set

Graphoid

G_delta Set