Page 143 - Discrete Mathematics and Its Applications

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

EXAMPLE 14 What is the power set of the set {0, 1, 2}?

Solution: The power set P({0, 1, 2}) is the set of all subsets of {0, 1, 2}. Hence,
P({0, 1, 2}) ={∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}.

Note that the empty set and the set itself are members of this set of subsets. ▲

EXAMPLE 15 What is the power set of the empty set? What is the power set of the set {∅}?

Solution: The empty set has exactly one subset, namely, itself. Consequently,

P(∅) = {∅}.
The set {∅} has exactly two subsets, namely, ∅ and the set {∅} itself. Therefore,
▲
P({∅}) ={∅, {∅}}.
n
If a set has n elements, then its power set has 2 elements. We will demonstrate this fact in
several ways in subsequent sections of the text.

Cartesian Products

The order of elements in a collection is often important. Because sets are unordered, a different
structure is needed to represent ordered collections. This is provided by ordered n-tuples.

DEFINITION 7 The ordered n-tuple (a 1 ,a 2 ,...,a n ) is the ordered collection that has a 1 as its first element,
a 2 as its second element,..., and a n as its nth element.

We say that two ordered n-tuples are equal if and only if each corresponding pair of their
elements is equal. In other words, (a 1 ,a 2 ,...,a n ) = (b 1 ,b 2 ,...,b n ) if and only if a i = b i ,
for i = 1, 2,...,n. In particular, ordered 2-tuples are called ordered pairs. The ordered pairs
(a, b) and (c, d) are equal if and only if a = c and b = d. Note that (a, b) and (b, a) are not
equal unless a = b.

RENÉ DESCARTES (1596–1650) René Descartes was born into a noble family near Tours, France, about
200 miles southwest of Paris. He was the third child of his father’s first wife; she died several days after his
birth. Because of René’s poor health, his father, a provincial judge, let his son’s formal lessons slide until, at
the age of 8, René entered the Jesuit college at La Flèche. The rector of the school took a liking to him and
permitted him to stay in bed until late in the morning because of his frail health. From then on, Descartes spent
his mornings in bed; he considered these times his most productive hours for thinking.
Descartes left school in 1612, moving to Paris, where he spent 2 years studying mathematics. He earned
a law degree in 1616 from the University of Poitiers. At 18 Descartes became disgusted with studying and
decided to see the world. He moved to Paris and became a successful gambler. However, he grew tired
of bawdy living and moved to the suburb of Saint-Germain, where he devoted himself to mathematical study. When his gambling
friends found him, he decided to leave France and undertake a military career. However, he never did any fighting. One day, while
escaping the cold in an overheated room at a military encampment, he had several feverish dreams, which revealed his future career
as a mathematician and philosopher.
After ending his military career, he traveled throughout Europe. He then spent several years in Paris, where he studied mathemat-
ics and philosophy and constructed optical instruments. Descartes decided to move to Holland, where he spent 20 years wandering
around the country, accomplishing his most important work. During this time he wrote several books, including the Discours, which
contains his contributions to analytic geometry, for which he is best known. He also made fundamental contributions to philosophy.
In 1649 Descartes was invited by Queen Christina to visit her court in Sweden to tutor her in philosophy. Although he was
reluctant to live in what he called “the land of bears amongst rocks and ice,” he finally accepted the invitation and moved to Sweden.
Unfortunately, the winter of 1649–1650 was extremely bitter. Descartes caught pneumonia and died in mid-February.