Page 140 - Discrete Mathematics and Its Applications

2.1 Sets 119

Subsets

It is common to encounter situations where the elements of one set are also the elements of
a second set. We now introduce some terminology and notation to express such relationships
between sets.

DEFINITION 3 The set A is a subset of B if and only if every element of A is also an element of B. We use
the notation A ⊆ B to indicate that A is a subset of the set B.

We see that A ⊆ B if and only if the quantification

∀x(x ∈ A → x ∈ B)

is true. Note that to show that A is not a subset of B we need only find one element x ∈ A with
x/∈ B. Such an x is a counterexample to the claim that x ∈ A implies x ∈ B.
We have these useful rules for determining whether one set is a subset of another:

Showing that A is a Subset of B To show that A ⊆ B, show that if x belongs to A then x
also belongs to B.
Showing that A is Not a Subset of B To show that A ⊆ B, find a single x ∈ A such that
x ∈ B.

EXAMPLE 8 The set of all odd positive integers less than 10 is a subset of the set of all positive integers less
than 10, the set of rational numbers is a subset of the set of real numbers, the set of all computer
science majors at your school is a subset of the set of all students at your school, and the set of
all people in China is a subset of the set of all people in China (that is, it is a subset of itself).
Each of these facts follows immediately by noting that an element that belongs to the first set
in each pair of sets also belongs to the second set in that pair. ▲

EXAMPLE 9 The set of integers with squares less than 100 is not a subset of the set of nonnegative integers
2
because −1 is in the former set [as (−1) < 100], but not the later set. The set of people who
have taken discrete mathematics at your school is not a subset of the set of all computer science
majors at your school if there is at least one student who has taken discrete mathematics who is
not a computer science major. ▲

BERTRAND RUSSELL (1872–1970) Bertrand Russell was born into a prominent English family active in
the progressive movement and having a strong commitment to liberty. He became an orphan at an early age
and was placed in the care of his father’s parents, who had him educated at home. He entered Trinity College,
Cambridge, in 1890, where he excelled in mathematics and in moral science. He won a fellowship on the basis
of his work on the foundations of geometry. In 1910 Trinity College appointed him to a lectureship in logic and
the philosophy of mathematics.
Russell fought for progressive causes throughout his life. He held strong pacifist views, and his protests
against World War I led to dismissal from his position at Trinity College. He was imprisoned for 6 months in
1918 because of an article he wrote that was branded as seditious. Russell fought for women’s suffrage in Great
Britain. In 1961, at the age of 89, he was imprisoned for the second time for his protests advocating nuclear disarmament.
Russell’s greatest work was in his development of principles that could be used as a foundation for all of mathematics. His
most famous work is Principia Mathematica, written with Alfred North Whitehead, which attempts to deduce all of mathematics
using a set of primitive axioms. He wrote many books on philosophy, physics, and his political ideas. Russell won the Nobel Prize
for literature in 1950.