cardinality of monomials
The proof proceeds by inducion on the cardinality of . If has but one element, then there is but one monomial of degree , namely the sole element of raised to the -th power. Since , the conclusion holds when .
Suppose, then, that the result holds whenver for some . Let be a set with exactly elements and let be an element of . A monomial of degree constructed from elements of can be expressed as the product of a power of and a monomial constructed from the elements of . By the induction hypothesis, the number of monomials of degree constructed from elements of is . Summing over the possible powers to which may be raised, the number of monomials of degree constructed from the elements of is as follows:
If is an infinite set of variable symbols, then the number of monomials of degree constructed from these symbols equals the cardinality of .