Page 24 - Chapter 2

• EXAMPLE 3:

Prove any finite, nonempty set is countable (the elements can

be arranged in a list)

Solution: Let P(n) be the predicate that if A is any set with

|A|=n>0, then A is countable

Basis Step: P(1) is true ( A ={x} )

Induction Step: assuming P(k) is true

Let B denotes any finite, nonempty set with k+1 elements.

We first pick any element x in B, then B-{x} is a set with k

elements, and it is countable (P(k) is true), and listed by

x 1,x 2,…x k . Then we can also list the elements of B as x 1,x 2,…x k ,

x (P(k+1) is true)

• EXAMPLE 5:

Consider the following function given in pseudocode

Function SQ(A)

1. C <－ 0

2. D <－ 0

3. WHILE (D is not A)

a. C <－ C+A

b. D <－ D+1

4. RETURN (C)

End of Function SQ