Theorem 4.9: Let S be a nonempty set with n elements. If

then

#(S - {s }) = n - 1.

Proof: If #(S ) = n then by Definition 4.5, there exists a one to one correspondence

Let

j = f-1(s )

Define a function

by

g(j) = n - 1

g(n - 1) = j

Define a function

by

h(x) = fg(x)

We must show that h is a one to one correspondence. To show that it is one to one, let

h(x) = h(y)

By the definition of h,

fg(x) = fg(y)

Since the domain of h does not include n - 1, we know that neither x nor y are equal to n - 1. If

x = j

then

g(x) = j

and

f(j) = s.

Since f is one to one, we conclude that g (y ) = j. The only element that g maps to j is n - 1, so

y = n - 1 = x

Otherwise, g(x) = x, and since f is one to one, it follows that

x = g(y).

Since x is neither j nor n - 1, y is also neither j nor n - 1, and we conclude that

x = y

To see that h is onto, let

If

then

x = h(f -1(x))

If x = f(n - 1), then

x = h (j).