cardinality of disjoint union of finite sets
To begin we will need a lemma.
Suppose , , , and are sets, with , and suppose there exist bijective maps and . Then there exists a bijective map from to .
Define the map by
To see that is injective, let , where . If , then by the injectivity of we have
Similarly if , by the injectivity of . If and , then , while , whence because and are disjoint. If and , then by the same reasoning. Thus is injective. To see that is surjective, let . If , then by the surjectivity of there exists some such that , hence . Similarly if , by the surjectivity of there exists some such that , hence . Thus is surjective. ∎
If and are finite sets with , then .
Let and be finite, disjoint sets. If either or is empty, the result holds trivially, so suppose and are nonempty with and . Then there exist bijections and . Define by for each . To see that is injective, let , and suppose . Then , whence . Thus is injective. To see that is surjective, let . By construction, , and consequently , so ; therefore we may take to have , so is surjective. Then, again by construction, the composition is a bijection from to , and as such, by the preceding lemma, the map defined by
is a bijection. Of course, the domain of is simply , so , as asserted. ∎
Let be a family of mutually disjoint, finite sets. Then .
|Title||cardinality of disjoint union of finite sets|
|Date of creation||2013-03-22 16:31:05|
|Last modified on||2013-03-22 16:31:05|
|Last modified by||mathcam (2727)|