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
Previous Page Next Page