226
Sets, Combinatorics, and Probability
holds. If A is a proper subset of B, A’s elements will usually have some additional
characterizing property not shared by all elements of B. (This is the same notion
of “inheritance” that prevails when a child type, or subtype, or derived type is defined in an object-oriented programming language. The child type inherits all of
the properties and operations from the parent type with the addition of specialized
local properties or operations as needed.)
example 4
Let
B = {x 0 x is a multiple of 4}
and let
A = {x 0 x is a multiple of 8}
Then we have A # B. To prove it, let x [ A; note that x is a completely arbitrary
member of A. We must show that x satisfies the characterizing property of B;
in other words, we must show that x is a multiple of 4. Because we have x [ A, x
satisfies the characterizing property of A; that is, x is a multiple of 8 and thus
we can write x = m # 8 for some integer m. This equation can be written as
x = m # 2 # 4 or x = k # 4, where k = 2m, so k is an integer. This shows that x is a
multiple of 4, and therefore x [ B.
There are numbers (like 12) that are multiples of 4 but not multiples of 8, so
A ( B. Another way to describe A is
A = {x 0 x = k # 4 and k is an even number}
In this form it is clear that A’s elements have inherited the characterizing property
of B—being a multiple of 4—but that there is an additional restriction that makes
A less general than B.
PraCtiCe 7 Let
A = {x 0 x [ ℝ and x
2
− 4x + 3 = 0}
B = {x 0 x [ ℕ and 1 ≤ x ≤ 4}
Prove that A ( B.
■
We know that A and B are equal sets if they have the same elements. We can
restate this equality in terms of subsets: A = B if and only if A # B and B # A.
Proving set inclusion in both directions is the usual way to establish the equality
of two sets.