Page 141 - Discrete Mathematics and Its Applications

120 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

U

A B

FIGURE 2 Venn Diagram Showing that A Is a Subset of B.

Theorem 1 shows that every nonempty set S is guaranteed to have at least two subsets, the
empty set and the set S itself, that is, ∅⊆ S and S ⊆ S.

THEOREM 1 For every set S,(i) ∅⊆ S and (ii) S ⊆ S.

Proof: We will prove (i) and leave the proof of (ii) as an exercise.
Let S be a set. To show that ∅⊆ S, we must show that ∀x(x ∈∅→ x ∈ S) is true. Because
the empty set contains no elements, it follows that x ∈∅ is always false. It follows that the
conditional statement x ∈∅→ x ∈ S is always true, because its hypothesis is always false and
a conditional statement with a false hypothesis is true. Therefore, ∀x(x ∈∅→ x ∈ S) is true.
This completes the proof of (i). Note that this is an example of a vacuous proof.

When we wish to emphasize that a set A is a subset of a set B but that A = B, we write
A ⊂ B and say that A is a proper subset of B. For A ⊂ B to be true, it must be the case that
A ⊆ B and there must exist an element x of B that is not an element of A. That is, A is a proper
subset of B if and only if

∀x(x ∈ A → x ∈ B) ∧∃x(x ∈ B ∧ x ∈ A)

is true. Venn diagrams can be used to illustrate that a set A is a subset of a set B. We draw the
universal set U as a rectangle. Within this rectangle we draw a circle for B. Because A is a subset
of B, we draw the circle for A within the circle for B. This relationship is shown in Figure 2.
A useful way to show that two sets have the same elements is to show that each set is a
subset of the other. In other words, we can show that if A and B are sets with A ⊆ B and B ⊆ A,
then A = B. That is, A = B if and only if ∀x(x ∈ A → x ∈ B) and ∀x(x ∈ B → x ∈ A) or
equivalently if and only if ∀x(x ∈ A ↔ x ∈ B), which is what it means for the A and B to be
equal. Because this method of showing two sets are equal is so useful, we highlight it here.

JOHN VENN (1834–1923) John Venn was born into a London suburban family noted for its philanthropy.
He attended London schools and got his mathematics degree from Caius College, Cambridge, in 1857. He was
elected a fellow of this college and held his fellowship there until his death. He took holy orders in 1859 and,
after a brief stint of religious work, returned to Cambridge, where he developed programs in the moral sciences.
Besides his mathematical work, Venn had an interest in history and wrote extensively about his college and
family.
Venn’s book Symbolic Logic clarifies ideas originally presented by Boole. In this book, Venn presents a
systematic development of a method that uses geometric figures, known now as Venn diagrams. Today these
diagrams are primarily used to analyze logical arguments and to illustrate relationships between sets. In addition
to his work on symbolic logic, Venn made contributions to probability theory described in his widely used textbook on that subject.