]> Sets

## 1. Sets

Poincaré's quote, on the title page of this chapter could not be more wrong (what was he thinking?). Set theory is the foundation of probability and statistics, as it is for almost every branch of mathematics.

### Sets and subsets

First, a set is simply a collection of objects; the objects are referred to as elements of the set. The statement that $s$ is an element of set $S$ is written $s S$. By definition, a set is completely determined by its elements; thus sets $A$ and $B$ are equal if they have the same elements:

$A B if and only if s A s B$

If $A$ and $B$ are sets then $A$ is a subset of $B$ if every element of $A$ is also an element of $B$:

$A B if and only if s A s B$

Concepts in set theory are often illustrated with small, schematic sketches known as Venn diagrams, named for John Venn. The Venn diagram in the picture below illustrates the subset relation.

Membership is a primitive, undefined concept in naive set theory. Moreover, sets are usually constructed by either listing the elements of the set or by giving a condition that must be satisfied by the elements of the set. However, the following construction, known as Russell's paradox after the mathematician and philosopher Bertrand Russell, shows that we cannot be too cavalier in the construction of sets.

Let $R A A is a set and A A$. Show that $R R$ if and only if $R R$

Usually, the sets under discussion in a particular context are all subsets of a specified set $S$, often called a universal set. The use of a universal set prevents the type of problem that arises in Russell's paradox. That is, if $S$ is a given set and $p x$ is a predicate on $S$ (that is, a valid mathematical statement that is either true or false for each $x S$, then $x S p x$ is a valid subset of $S$.

In contrast to a universal set, the empty set, denoted , is the set with no elements.

Show that $A$ for every set $A$.

Suppose that $A$, $B$ and $C$ are subsets of a set $S$. Prove the following results, which show that the subset relation is a partial order on the collection of subsets of $S$.

1. $A A$ (the reflexive property).
2. If $A B$ and $B A$ then $A B$ (the anti-symmetric property).
3. If $A B$ and $B C$ then $A C$ (the transitive property).

If $S$ is a set, then the set of all subsets of $S$ is known as the power set of $S$ and is denoted $S$.

#### Special Sets

The following special sets are used throughout the project, and often play the role of universal sets.

• : the set of natural numbers (which, in this project, means the nonnegative integers)
• : the set of positive integers
• : the set of integers
• : the set of rational numbers
• : the set of real numbers
• : the set of complex numbers

### Set Operations

We are now ready to review the basic operations of set theory. For the following definitions, suppose that $A$ and $B$ are subsets of a universal set, which we will denote by $S$.

The union of $A$ and $B$ is the set obtained by combining the elements of $A$ and $B$.

$A B s S s A s B$

The intersection of $A$ and $B$ is the set of elements common to both $A$ and $B$:

$A B s S s A s B$

If the intersection of sets $A$ and $B$ is empty, then $A$ and $B$ are said to be disjoint:

$A B$

The set difference of $B$ and $A$ is the set of elements that are in $B$ but not in $A$:

$B A s S s B s A$

The complement of $A$ is the set of elements that are not in $A$:

$A s S s A$

Note that union, intersection, and difference are binary set operations, while complement is a unary set operation.

In the Venn diagram applet, select each of the following and note the shaded area in the diagram.

1. $A$
2. $B$
3. $A$
4. $B$
5. $A B$
6. $A B$

#### Basic Rules

In the following problems, $A$, $B$, and $C$ are subsets of a universal set $S$. The proofs are straightforward, and just use the definitions and basic logic.

Show that $A B A A B$

Prove the identity laws:

1. $A A$
2. $A S A$

Prove the idempotent laws:

1. $A A A$
2. $A A A$

Prove the complement laws:

1. $A A S$
2. $A A$

Prove the double complement law: $A A$

Prove the commutative laws:

1. $A B B A$
2. $A B B A$

Prove the associative laws:

1. $A B C A B C$
2. $A B C A B C$

Thus, we can write $A B C$ and $A B C$ without ambiguity.

Prove the distributive laws:

1. $A B C A B A C$
2. $A B C A B A C$

Prove DeMorgan's laws (named after Agustus DeMorgan):

1. $A B A B$
2. $A B A B$.

Prove that the following statements are equivalent:

1. $A B$
2. $B A$
3. $A B B$
4. $A B A$
5. $A B$

Prove the following results. The first part shows that set difference can be expressed in terms of complement and intersection. The next three parts show that all of the other set operations (complement, union, and intersection) can be expressed in terms of difference.

1. $B A B A$
2. $A S A$
3. $A B A A B$
4. $A B S S A S A S B$

Show that $A B A B A B B A$. This set is called the symmetric difference of $A$ and $B$, and is sometimes denoted $A B$. The elements of this set belong to one but not both of the given sets.

Show that the elements of $A B A B$ belong to both the given sets or to neither of the sets.

Prove that there are 16 different (in general) sets that can be constructed from two given events $A$ and $B$.

In the Venn diagram applet, observe the diagram of each of the 16 sets that can be constructed from $A$ and $B$ using the set operations.

### Product sets

Product sets are sets of sequences. The defining property of a sequence, of course, is that order as well as membership is important.

Let us start with ordered pairs. In this case, the defining property is that $a b c d$ if and only if $a c$ and $b d$. Interestingly, the structure of an ordered pair can be defined just using set theory. The construction in the exercise below is due to Kazamierz Kuratowski

Define $a b a a b$ Show that this definition captures the defining property of an ordered pair given above.

More generally, two ordered sequences of the same size (finite or infinite) are the same if and only if their corresponding coordinates agree:

$s 1 s 2 s n t 1 t 2 t n if and only if s i t i for i 1 2 n$ $s 1 s 2 t 1 t 2 if and only if s i t i for i 1 2$

Suppose now that we have a sequence of sets $S 1 S 2 S n$. The Cartesian product of the sets (named for René Descartes) is defined as follows:

$S 1 S 2 S n s 1 s 2 s n i 1 2 n s i S i$

If $S i S$ for each $i$, then the product set can be written compactly as $S n$. In particular, recall that  denotes the set of real numbers so that $n$ is $n$-dimensional Euclidean space, named after Euclid, of course.

Finally, suppose that we have an infinite sequence of sets $S 1 S 2$. The Cartesian product of the sets is defined by

$S 1 S 2 s 1 s 2 i 1 2 s i S i$

The elements of $0 1 n$ are called bit strings of length $n$. As the name suggests, we sometimes represent elements of this product set as strings rather than sequences (that is, we omit the parentheses and commas). Since the coordinates just take two values, there is no risk of confusion.

#### Rules for Product Sets

We will now see how the set operations relate to the Cartesian product operation. Suppose that $S$ and $T$ are sets and that $A S$, $B S$ and $C T$, $D T$. The sets in the exercises below are subsets of $S T$

The most important rules that relate Cartesian product with union, intersection, and difference are the distributive rules. Show that

1. $A C D A C A D$
2. $A B C A C B C$
3. $A C D A C A D$
4. $A B C A C B C$
5. $A C D A C A D$
6. $A B C A C B C$

Show that

1. $A B C D A C A D B C B D$
2. $A C B D A B C D$

In general, the product of unions is larger than the corresponding union of products.

On the other hand, the product of intersections is the same as the corresponding intersection of products. Show that

$A C B D A B C D$

In general, the product of differences is smaller than the corresponding difference of products. Show that

1. $A B C D A C A D B C B D$
2. $A B C D A C B D$

### General Operations

The operations of union and intersection can easily be extended to a finite or even an infinite collection of sets.

#### Definitions

Suppose that $A$ is a nonempty collection of subsets of a universal set $S$. In some cases, the subsets in $A$ may be naturally indexed by a nonempty index set $I$, so that $A A i i I$. (In a technical sense, any collection of subsets can be indexed--by itself!)

The union of the collection of sets $A$ is the set obtained by combining the elements of the sets in $A$:

$A s S A A s A$

If $A A i i I$, so that the collection of sets is indexed, then we use the more natural notation:

$i I A i s S i I s A i$

The intersection of the collection of sets $A$ is the set of elements common to all of the sets in $A$:

$A s S A A s A$

If $A A i i I$, so that the collection of sets is indexed, then we use the more natural notation:

$i I A i s S i I s A i$

The collection of sets $A$ is pairwise disjoint if the intersection of any two sets in the collection is empty:

$A B for every A A and B A with A B$

The collection of sets $A$ is said to partition a set $B$ if the collection $A$ is pairwise disjoint and $A B$. Partitions are intimately related to equivalence relations.

#### Basic Rules

In the following problems, $A A i i I$ is a collection of subsets of a universal set $S$, indexed by a nonempty set $I$, and $B$ is a subset of $S$.

Prove the general distributive laws

$i I A i B i I A i B$ $i I A i B i I A i B$

Then restate the laws in the notation where the collection $A$ is not indexed.

Prove the general De Morgan's laws:

$i I A i i I A i$ $i I A i i I A i$

Restate the laws in the notation where the collection $A$ is not indexed.

Suppose that the collection $A$ partitions $S$. Show that for any subset $B$, the collection $A B A A$ partitions $B$.

### Computational Exercises

#### Coins and Dice

Let $S 1 2 3 4 1 2 3 4 5 6$. This is the set of outcomes when a 4-sided die and a 6-sided die are tossed. Further let $A x y S x 2$ and $B x y S x y 7$. Give each of the following sets in list form:

1. $A$
2. $B$
3. $A B$
4. $A B$
5. $A B$
6. $B A$

Let $S 0 1 3$. This is the set of outcomes when a coin is tossed 3 times (0 denotes tails and 1 denotes heads). Further let $A x 1 x 2 x 3 S x 2 1$ and $B x 1 x 2 x 3 S x 1 x 2 x 3 2$. Give each of the following sets in list form, using bit-string notation:

1. $S$
2. $A$
3. $B$
4. $A$
5. $B$
6. $A B$
7. $A B$
8. $A B$
9. $B A$

Let $S 0 1 2$. This is the set of outcomes when a coin is tossed twice (0 denotes tails and 1 denotes heads). Give $S$ in list form.

#### Cards

A standard card deck can be modeled by the product set

$D 2 3 4 5 6 7 8 9 10$

where the first coordinate encodes the denomination or kind (ace, 2-10, jack, queen, king) and where the second coordinate encodes the suit (clubs, diamonds, hearts, spades). Sometimes we represent a card as a string rather than an ordered pair (for example ). For the problems in this subsection, the card deck $D$ is the universal set.

Let $H$ denote the set of hearts and $F$ the set of face cards. Find

1. $H F$
2. $H F$
3. $F H$
4. $H F$

#### General unions and intersections

For the problems in this subsection, the universal set is .

Let $A n 0 1 1 n$ for $n$. Find

1. $n 1 A n$
2. $n 1 A n$
3. $n 1 A n$
4. $n 1 A n$

Let $A n 2 1 n 5 1 n$ for $n$. Find

1. $n 1 A n$
2. $n 1 A n$
3. $n 1 A n$
4. $n 1 A n$