cardinality of disjoint union of finite sets

To begin we will need a lemma.


Suppose A, B, C, and D are sets, with AB=CD=, and suppose there exist bijectiveMathworldPlanetmathPlanetmath maps f1:AC and f2:BD. Then there exists a bijective map from AB to CD.


Define the map g:ABCD by

g(x)={f1(x)if xAf2(x)if xB. (1)

To see that g is injectivePlanetmathPlanetmath, let x1,x2AB, where x1x2. If x1,x2A, then by the injectivity of f1 we have

g(x1)=f1(x1)f1(x2)=g(x2). (2)

Similarly if x1,x2B, g(x1)g(x2) by the injectivity of f2. If x1A and x2B, then g(x1)=f1(x1)C, while g(x2)=f2(x2)D, whence g(x1)g(x2) because C and D are disjoint. If x1B and x2A, then g(x1)g(x2) by the same reasoning. Thus g is injective. To see that g is surjective, let yCD. If yC, then by the surjectivity of f1 there exists some xA such that f1(x)=y, hence g(x)=y. Similarly if yD, by the surjectivity of f2 there exists some xB such that f2(x)=y, hence g(x)=y. Thus g is surjective. ∎


If A and B are finite setsMathworldPlanetmath with AB=, then AB=A+B.


Let A and B be finite, disjoint sets. If either A or B is empty, the result holds trivially, so suppose A and B are nonempty with A=n and B=m. Then there exist bijections f:nA and g:mB. Define h:nn+mm by h(i)=m+i for each in. To see that h is injective, let i1,i2, and suppose h(i1)=h(i2). Then m+i1=m+i2, whence i1=i2. Thus h is injective. To see that h is surjective, let kn+mm. By construction, m+1km+n, and consequently 1k-mn, so k-mn; therefore we may take i=k-m to have h(i)=k, so h is surjective. Then, again by construction, the compositionMathworldPlanetmathPlanetmath fh-1 is a bijection from n+mm to A, and as such, by the preceding lemma, the map ϕ:n+mmmAB defined by

ϕ(i)={(fh-1)(i)if in+mmg(i)if im, (3)

is a bijection. Of course, the domain of ϕ is simply n+m, so AB=n+m, as asserted. ∎


Let {Ak}k=1n be a family of mutually disjoint, finite sets. Then k=1nAk=k=1nAk.


We proceed by inductionMathworldPlanetmath on n. In the case n=2, the the preceding result applies, so let n2, and suppose k=1nAk=k=1nAk. Then by our inductive hypothesis and the preceding result, we have

|k=1n+1Ak|=|k=1nAkAn+1|=|k=1nAk|+An+1=k=1nAk+An+1=k=1n+1Ak. (4)

Thus the result holds for n+1, and by the principle of induction, for all n. ∎

Title cardinality of disjoint union of finite sets
Canonical name CardinalityOfDisjointUnionOfFiniteSets
Date of creation 2013-03-22 16:31:05
Last modified on 2013-03-22 16:31:05
Owner mathcam (2727)
Last modified by mathcam (2727)
Numerical id 17
Author mathcam (2727)
Entry type TheoremMathworldPlanetmath
Classification msc 03E10
Related topic Cardinality
Related topic Bijection
Related topic DisjointUnion
Related topic Function