20 2. Background

Notice that in the ⊆ direction we used two cases that could over-

lap, and did not worry whether we were in the overlap or not. In

the ⊇ direction, we could only assert x ∈ B and x ∈ C if we knew

x / ∈ A (although it is certainly possible for x to be in all three sets),

so forbidding the first case was part of the second case.

Exercise 2.2.8. Using any of the three options listed above, as long

as it is applicable, do the following.

(i) Prove intersection distributes over union (i.e., for all A, B, C,

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)).

(ii) Prove de Morgan’s Laws.

(iii) Prove that A ∪ B = (A − B) ∪ (B − A) ∪ (A ∩ B) for any sets A

and B.

Our final topic in the realm of sets is cardinality. The cardinality

of a finite set is the number of elements in it. For example, the cardi-

nality of the set of positive integer divisors of 6 is 4: |{1, 2, 3, 6}| = 4.

When we get to infinite sets, cardinality separates them by “how infi-

nite” they are. We’ll get to its genuine definition in §2.3, but it is fine

now and later to think of cardinality as a synonym for size. The way

to tell whether set A is bigger than set B is to look for a one-to-one

function from A into B. If no such function exists, then A is bigger

than B, and we write |B| |A|. The most important result is that

|A| |P(A)| for any set A (see §A.3).

If we know there is a one-to-one function from A into B but we

don’t know about the reverse direction, we write |A| ≤ |B|. If we

have injections both ways, |A| = |B|. It is a significant theorem of

set theory that having injections from A to B and from B to A is

equivalent to having a bijection between A and B; the fact that this

requires work is a demonstration of the fact that things get weird when

you work in the infinite world. Another key fact (for set theorists;

not so much for us) is trichotomy: for any two sets A and B, exactly

one of |A| |B|, |A| |B|, or |A| = |B| is true.

For us, infinite cardinalities are divided into two categories. A

set is countably infinite if it has the same cardinality as the natural

numbers. The integers and the rational numbers are important ex-

amples of countably infinite sets. The term countable is used by some