EF Activities

Without cheating and looking at the proofs in this chapter, prove each of the following statements. You may wish to make use of the characterization of countability in Fact 13.1.2 instead of the technical definition of countable set.

🔗

Note: Each statement except the first two can be proved directly from the preceding statements.

🔗

(a)

🔗

Every subset of

N

is countable.

🔗

(b)

🔗

If two sets have the same size and one of them is countable, then so is the other.

🔗

(c)

🔗

Every set that is the same size as a subset of

N

is countable.

🔗

(d)

🔗

Every subset of a countable set is countable.

🔗

(e)

🔗

Every set that is the same size as a subset of a countable set is countable.

🔗

(f)

🔗

A set that contains an uncountable subset is uncountable.

🔗

Activity 13.3.

🔗

(a)

🔗

Prove that

N \times N

is countable.

Hint.

Use a zig-zag-through-a-grid method similar to the proof of the countability of the rational numbers. (See Theorem 13.1.4 and its proof.)

🔗

(b)

🔗

Prove that if

A

and

B

are both countable, then so is

A \times B .

Hint.

You could do more zig-zagging, or you could use the statement of Task a.

🔗

(c)

🔗

Prove that if

X,

Y,

and

Z

are each countable, then so is

X \times Y \times Z .

Hint.

Use the statement of Task b twice.

🔗

(d)

🔗

What proof method do you think you would use to prove the following statement?

🔗

🔗
If $A_{1}, A_{2}, \dots, A_{n}$ are all countable, then so is

$A_{1} \times A_{2} \times \dots \times A_{n} .$

🔗

Activity 13.4. The Infinite Orchard Problem.

🔗

You own a magical apple orchard that contains an infinite number of trees, each of which bears an infinite number of apples. Describe a method to pick all of the apples in the orchard, one apple at a time. (No shaking the trees, please! However, you may assume an infinite amount of time.)

🔗