6 CHAPTER 1 Sets, Proof Templates, and Induction
Definition 2. Let A and B be sets. A is a subset of B, written as A C B, if every element
of A is also an element of B. A is a proper subset of B, written A C B, if A c B but
A#B.
"Is not a subset" is denoted with 9, whereas "is not a proper subset" is denoted
with ýt. For example, {1, 2, 3} 7 {1, 3, 4}, since 2 E {1, 2, 31 and 2 0 {1, 3, 4}. Similarly,11, 4} 5 11,2, 3}, since 4 e (1, 4} and 4 0 11,2, 3). Also, (1,2,3,2, 1} C {1, 2, 3}, but
{1, 2, 3, 2,41} ý1 [1, 2, 3}1.
We now state formally two facts that follow immediately from the definitions.
Theorem 1. Let A be a set.
(a) A C A.
(b) 0 c A.Proof.
(a) To say that A C A, according to Definition 2, means that each element of A is an
element of A, which is clearly true.
(b) Since 0 has no elements, the statement "for every element x, if x E 0, then x e A"
cannot be false, because 0 has no elements. In this case we say the statement is vacuously
true. U
We use the filled box that appears at the end of a Proof for a theorem or the end of
Solution for an example as a separator. In some instances, when an example includes a
discussion, we also use this to separate the example from the following text.
The idea behind proving that one set is a subset of a second set involves proving that
every element of the first set is an element of the second set. It would not be very convenient
if each element of the first set had to have its own proof of membership in the second set.
Example 3 uses a proof that each element of the first set is an element of the second set by
simply proving the result for a completely arbitrary element of the first set. A completely
arbitrary element is one that has no property to use in the proof except that it is a member of
the first set. An "arbitrary element of a set" is a (hypothetical) element whose only property
is that it belongs to that set. In mathematics, the phrase "let x E A" means "x is my name
for an arbitrary element of A." Assuming that we are dealing with a completely arbitrary
element allows us to prove the membership of every element with a single proof.Example 3. Prove that the sets A = (2^1 , 2^2 , 2', 24.. .. and B = (2, 4, 6, 8, .... satisfy
AC B.
Solution. An arbitrary element of A is of the form 2i for some i E 11, 2, 3, .1..1. An
arbitrary element of B is of the form 2. j for some j c {1, 2, 3, ...). Clearly, 2' = 2. j
for the integer j = 2i-1. Since an arbitrary element of A is an element of B, we concludeAC B. U
If and Only If
Mathematical statements about how facts are related, including many mathematical the-
orems, are implications. For example, "if you eat your carrots, you will grow big and
strong," or "if Sally is in the science lab, then she is doing her chemistry experiment," or
"if x > 1, then x2 > x" are all implications. An implication starts with a hypothesis that
is assumed to be true and then uses various means to prove a conclusion. We denote an
implication as a =ý b, where a is the hypothesis and b is the conclusion. Two implications