Question

8. Definition: A set A is finite if there exists a non-negative integer c such that there exists a bijection from A to {n ∈ N : n ≤ c}. (The integer c is called the cardinality of A.)

(a) Let A be a finite set, and let B be a subset of A. Prove that B is finite. (Hint: induction on |A|. Note that our proof can’t use induction on |B|, or indeed refer to “the number of elements in B” at all, because we don’t yet know that B is finite!)

(b) Prove that the union of two disjoint finite sets is finite.

(c) Prove that the union of any two finite sets is finite. (Hint: A ∪ B = A ∪ (B − A))

Answer 1

Denote : [c] = { n in N : n c } = {1,2,3,4,...,c}, then, |[c]| = c, is the cardinality of the finite set [c].

(a) let, A be a finite set and assume that B is a finite subset of A. If B is empty, then, B is finite. So we assume that B is non-empty.
Since A is finite, there exists a bijection f : A ----> [c] for some c in N.

We need to show that B is equivalent to a finite set.

To do this, we define g : B ----> f(B) by g(x) = f(x) for each x in B.

Since A is finite, so, f is an injection, we conclude that g is an injection.

Now let y belongs to f(B).
Then there exists an b in B such that f(b) = y. But by the definition of g, this means that g(b) = y, and hence g is a surjection. This proves that g is a bijection.
Hence, we have proved that B is equivalent to f(B). Since f(B) is a subset of [c], we conclude that f(B) is finite and consequently, B is finite (since, B and f(B) are equivalent)

(b) let, X & Y be two finite sets,

Then, there exists bijection, f : X ----> [c] and g : Y ----> [d] for some positive integers c & d.

Define, h : XY -----> [c+d] by,

h(k) = f(k) if, k belongs to X

&, h(k) = g(k) + c if, k belongs to Y

The inverse h - : [c+d] ----> XY is defined by,

h^-1 (k) = f^-1(k) if, 1 k c

&, h^-1(k) = g^-1(k - c) if, c+1 k c+d

So, h and its inverse both exist.

Then, h is a bijection.

So, XY is finite.

(c) let, A & B be 2 finite sets,

Then, AB = A(B-A) is the union of 2 disjoint sets & hence finite, by part (b).

Hence, AB is finite