TOPICS
Search

Finite Set


A set X whose elements can be numbered through from 1 to n, for some positive integer n. The number n is called the cardinal number of the set, and is often denoted |X| or #X. In other words, X is equipollent to the set {1,...,n}. We simply say that X has n elements. The empty set is also considered as a finite set, and its cardinal number is 0.

A finite set can also be characterized as a set which is not infinite, i.e., as a set which is not equipollent to any of its proper subsets. In fact, if Y subset X, and Y!=X, a certain number a of elements of X do not belong to Y, so that |Y|=n-a<n.

For all k=0,...,n, the number of subsets having exactly k elements (the so-called k-subsets, or combinations of k elements out of n) is equal to the binomial coefficient

C(n,k)=(n; k)
(1)
=((n-k+1)(n-k+2)...n)/(1·2...k).
(2)

Hence the number of subsets of X (i.e., the cardinal number of its power set) is

sum_(k=0)^n(n; k)=sum_(k=0)^n(n; k)1^k1^(n-k)
(3)
=(1+1)^n
(4)
=2^n
(5)

by virtue of the binomial theorem.

Assigning to each k-subset of X its complement set defines a one-to-one correspondence between the set of k-subsets and the set of (n-k)-subsets of X. This proves the identity

 (n; k)=(n; n-k).
(6)

The possible arrangements of the elements of X are called permutations of order n. They all give rise to the same finite ordinal n, since they are essentially the same; they can be transformed into each other simply by renaming the elements. The number of permutations of order n is

 1·2...n=n!
(7)

This is called n factorial. In fact, when constructing an arrangement by placing the elements in n given positions, there are exactly n possible choices for the first element, there are n-1 left for the second, and so on.

With respect to this notation, the number of combinations of k elements can be written as

 C(n,k)=(n!)/((n-k)!k!).
(8)

The elements of each k-subset give rise to k! different permutations, so that the total number of possible permutations of k elements out of n is

 P(n,k)=C(n,k)k!=(n!)/((n-k)!).
(9)

See also

Empty Set, Infinite Set, Set, Universal Set

This entry contributed by Margherita Barile

Explore with Wolfram|Alpha

Cite this as:

Barile, Margherita. "Finite Set." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/FiniteSet.html

Subject classifications