1.5 COUNTING PROPERTIES OF FINITE SETS (OPTIONAL) 43We emphasize that the content of this article is restricted to finite sets.
We will deal with the question of relative size of infinite sets under the
heading "cardinality of sets" in Article 8.3.
REMARK 1 If S is a finite set, we use the symbol n(S) to represent the num-
ber of e1ement.s in S, where n(0) = 0 and n(S) = k (for S # @ and k a
positive integer) if and only if k is the positive integer having the property
that the elements in S can be matched, in a one-to-one fashion, with the
positive integers 1, 2,... , k.It is common to describe a finite set F of unspecified elements by such
notation as F = (x,, x,,... , x,), where it is understood that the k elements
are distinct so that n(F) = k.FORMULA FOR n(A u B)
If A and B are sets, then their union contains all the elements from each
of the two sets, combined into a single set. If A and B were disjoint, then
clearly n(A u B) would equal n(A) + n(B). But if an object x is contained
in both A and B, it will be counted doubly in the preceding formula, once
as an element of A and once as an element of B, even though it represents
a single element in A u B. To avoid this overcounting of members of
A u B, we must subtract from n(A) + n(B) the number of elements in
A n B. Thus we arrive at Counting Formula 1.COUNTING FORMULA 1
If A and B are finite sets, then n(A u 6) = n(A) + n(B) - n(A n B).COROLLARY
If A and B are disjoint finite sets, then n(A u B) = n(A) + n(B).The latter result can be viewed as a corollary (i.e., consequence) of the first
one, since if A n B = @, then n(A n B) = n(@) = 0. A rigorous approach
to these results would require a proof of Formula 1 from some predetermined
set of axioms and, in particular, a proof that does not use the result of the.
corollary. Our goal in this article is to provide an intuitive, rather than a
rigorous development, with emphasis on uses of the formulas rather than on
their rigorous derivation.EXAMPLE 1 Thirty-six students are enrolled in either abstract algebra or
advanced calculus. The enrollment in abstract algebra is 28, whereas
advanced calculus has 24 students. How many students are enrolled in
both these classes?
Solution Let A be the set of students in advanced calculus, and B the set
of students in abstract algebra. We wish to calculate n(A n B), knowing