uniqueness of cardinality


The cardinality of a set is unique.


We will verify the result for finite setsMathworldPlanetmath only. Suppose A is a finite set with cardinality A=n and A=m. Then there exist bijections f:nA and g:mA. Since g is a bijection, it is invertiblePlanetmathPlanetmathPlanetmath, and g-1:Am is a bijection. Then the compositionMathworldPlanetmathPlanetmath g-1f is a bijection from n to m. We will show by inductionMathworldPlanetmath on n that m=n. In the case n=1 we have n=1={1}, and it must be that m={1} as well, whence m=1=n. Now let n1, and suppose that, for all m, the existence of a bijection f:nm implies n=m. Let m and suppose h:n+1m is a bijection. Let k=h(n+1), and notice that 1km. Since h is onto there exists some jn+1 such that f(j)=m. There are two cases to consider. If j=n+1, then we may define ϕ:nm-1 by ϕ(i)=h(i) for all in, which is clearly a bijection, so by the inductive hypothesis n=m-1, and thus n+1=m. Now suppose jn+1, and define ϕ:nm-1 by

ϕ(i)={h(i)if ijkif i=j.

We first show that ϕ is one-to-one. Let i1,i2n, where i1i2. First consider the case where neither i1 nor i2 is equal to j. Then, since h is one-to-one, we have


In the case i1=j, again because h is one-to-one, we have


Similarly it can be shown that, if i2=j, ϕ(i1)ϕ(i2), so ϕ is one-to-one. We now show that ϕ is onto. Let lm-1. If l=k, then we may take i=j to have ϕ(i)=ϕ(j)=k=l. If lk, then, because h is onto, there exists some in such that h(i)=l, so g(i)=h(i)=l. Thus g is onto, and our inductive hypothesis again gives n=m-1, hence n+1=m. So by the principle of induction, the result holds for all n. Returning now to our set A and our bijection g-1f:nm, we may conclude that m=n, and consequently that the cardinality of A is unique, as desired. ∎


There does not exist a bijection from a finite set to a proper subsetMathworldPlanetmathPlanetmath of itself.


Without a loss of generality we may assume the proper subset is nonempty, for if the set is empty then the corollary holds vacuously. So let A be as above with cardinality n, B a proper subset of A with cardinality m<n, and suppose f:AB is a bijection. By hypothesisMathworldPlanetmathPlanetmath there exist bijections g:nA and h:mB; but then h-1(fg) is a bijection from n to m, whence by the preceding result n=m, contrary to assumptionPlanetmathPlanetmath. ∎

The corollary is also known more popularly as the pigeonhole principleMathworldPlanetmath.

Title uniqueness of cardinality
Canonical name UniquenessOfCardinality
Date of creation 2013-03-22 16:26:52
Last modified on 2013-03-22 16:26:52
Owner mathcam (2727)
Last modified by mathcam (2727)
Numerical id 27
Author mathcam (2727)
Entry type Theorem
Classification msc 03E10
Related topic cardinality
Related topic bijection
Related topic function
Related topic set
Related topic subset
Related topic Subset
Related topic Bijection
Related topic Set
Related topic PigeonholePrinciple