Bridge to Abstract Mathematics: Mathematical Proof and Structures

288 RELATIONS: FUNCTIONS AND MAPPINGS Chapter 8

2. Results about countably infinite sets:

(a) If n E N, then n < KO.

(b) If A is a countably infinite set and B c A, then B is countable.

(c) KO is the smallest infinite cardinal number; that is, if A is an infi-

nite set such that A .< N, then A r N, so that A is countably

infinite.

(d) If (A,^1 d E I) is a collection of countably infinite sets, indexed by a

countably infinite set I (such as I = N), then U,, ,A, is countably

infinite (notation discussed in Article 8.4).

(e) If A and B are nonempty sets with A countable and f: A -+ B a

mapping of A onto B, then B is countable.

(f) If A and B are countable sets, then A x B is countable.

(g) I A,, A,,.. ., A, are countable sets (where EN), then A, x

A, x. x A, is countable.

3. The proofs of these results depend on the axiom of choice (axiom dis-
   cussed in Article 8.4):

(a) Any two cardinal numbers are comparable (recall Definition 4,

Article 7.4), that is, given two sets A and B, either A .< B or B .< A.

(b) Any infinite set has a countably infinite subset.

Exercises

1. Use Definition 1, that is, the definiton of numerical equivalence, to prove:
   (a) R r (0, oo)
   (b) (- n/2,42) r R

• (c) (0, 1) z (7, 13)
  (d) (a, b) r (c, d), where a, b, c, and d are real with a # b and c # d
  (e) (0, 1) R
  (f) (a, b) r R, where a, b E R and a # b
  (g) (09 11 = [A a).

2. *(a) Use Definition 2 to prove that (21 is a finite set.
   (6) Use Definition 2 to prove that if S is any infinite set and S r T, then T is
   infinite.
   (c) Conclude from (b) that any subset of a finite set is finite.
   (d) Conclude from (b) that if A and B are infinite sets, then A u B is infinite.
   (e) Prove that if A is an infinite set and B is a set satisfying B z A, then B is infinite.
   (f) Prove by mathematical induction that the set F, = (1,2,3,... , n) is finite, for
   any positive integer n.


3. (a) Prove that if A is finite and x $ A, then A u {x) is finite.
   (b) Conclude from (a) that if A is infinite and x E A, then A - {x) is infinite.
   (c) Prove by induction that if A is finite and x,, x,,... , x, are all not elements of
   A (where n E N), then A u (x,, x,,... , x,) is finite.