A Book of Abstract Algebra, Second Edition (1982)

APPENDIX A. REVIEW OF SET THEORY

A set is a collection of objects. The objects in the set are called the elements of the set. If x is an element of a set A, we denote this fact by writing x ∈ A (to be read as “x is an element of A”). On the other hand, if x is not an element of A, we write x ∉ A. (This should be read as “x is not an element of A.”)

Suppose that A and B are sets and that A is a part of B. In other words, suppose every element of A is an element of B. In that case, we call A a subset of B and write A ⊆ B. We say that A and B are equal (and we write “A = B”) if A and B have the same elements. It is easy to see that if A ⊆ B and B ⊆ A, then A = B. And conversely, if A = B, then A ⊆ 5 and B ⊆ A.

Sets are often represented pictorially by circular or oval shapes. The fact that A ⊆ B is represented as in the following figure:

Many sets can easily be described in words; for example, “the set of all the positive real numbers,” “the set of all the integers,” or “the set of all the rational numbers between 1 and 2.” However, it is often more convenient to describe a set in symbols. We do this by writing

{x: ________________}

Following the colon, we name the property which all the elements in the set, and no other elements, have in common. For example,

{x: x ∈ and x ≤ 2}

is the set of all the real numbers (elements of ) which are less than or equal to 2. We may also symbolize this set by

{x ∈ : x ≤ 2}

to be read as “the set of all x in satisfying x ≤ 2.”

If A and B are sets, there are several ways of forming new sets from A and B:

1.The union of A and B (denoted by A B) is the set of all those elements which are elements of A or elements of B. Here, the word “or” is used in the “inclusive” sense: An element x is in A B if x is in A, or in B, or in both Aand B. Thus, A B is the shaded area in the figure:

2.The intersection of A and B (denoted by A B) is the set of all those elements which are in A and in B. Thus, x is in A B if x ∈ A and x ∈ B. The set A B is represented by the shaded area in the figure:

3.The difference of two sets is defined as follows: A − B is the set of all those elements which are in A, but not in B. Thus, x is in A − B if x ∈ A and x ∉ B. The set A − B is the shaded area in the figure:

In short,

We define the empty set to be the set with no elements at all. The empty set is denoted by the symbol 0.

There are several basic identities involving the set operations which have just been introduced. As an example of how to prove them, we give a proof of the identity

A B = B A

PROOF: We need to show that every element in A B is in B A, and conversely, that every element in B A is in A B. Well, suppose x ∈ A B; this means that x ∈ A or x ∈ B. But this is the same as saying: x ∈ B or x ∈ A. Thus, x ∈ B A.

The same reasoning shows that if x ∈ B A, then x ∈ A B. ■

Next, we prove the identity

A (B C) = (A B) (A C)

PROOF: First, we will show that every element of A (B C) is an element of (A B) (A C). Well, suppose x ∈ A (B C): This means that

(i)x ∈ A, and

(ii)x ∈ B C.

From (ii), x ∈ B or x ∈ C. If x ∈ B, then from (i), x ∈ A B. If x ∈ C, then from (i), x ∈ A C. In either case, x is in (A B) (A C).

Conversely, suppose x is in (A B) (A C). Then

(i)x ∈ A B, or

(ii)x ∈ A C.

In either case, x ∈ B or x ∈ C, so that x ∈ B C. Also in either case, x ∈ A. Thus, x ∈ A (B C). We’re done. ■

We conclude this section with one more definition: If A and B are sets, then A × B denotes the set of all ordered pairs (a, b), where a ∈ A and b ∈ B. That is,

A × B = {(a, b): a ∈ A and b ∈ B}

We call A × B the cartesian product of A and B. Note, by the way, that (a, b) is not the same as (b, a). Moreover, (a, b) = (c, d) if a = c and b = d. That is, two ordered pairs are equal if they have the same first component and the same second component.

EXERCISES

Prove the following:

1 If A ⊆ B and B ⊆ C, then A ⊆ C.

2 If A = B and B = C, then A = C.

3 A ⊆ A B and B ⊆ A B.

4 A B ⊆ A and A B ⊆ B.

5 A B = B A.

6 A A = A and A A = A.

7 A (B C) = (A B) (A C).

8 A 0 = A and A 0 = 0.

9 A (A B) = A.

10. A (A B) = A.

11 A (B − C) = (A B) − C.

12 (A B) − C = (A − C) (B − C).

13 If A ⊆ B, then A B = B. Conversely, if A B = B, then A ⊆ B.

14. If A ⊆ B, then A B = A. Conversely, if A B = A, then A ⊆ B.

If S is a set, and A is a subset of S, then the complement of A in S is the set of all the elements of S which are not in A. The complement of A is denoted by A′:

Prove the following’.

15 (A B)′ = A′ B′.

16 (A B)′ = A′ B′.

17 (A′)′ = A.

18 A A′ = 0.

19 If A ⊆ B, then A B′ = 0, and conversely.

20 If A ⊆ B and C = B − A, then A = B − C.

Prove the following identities involving cartesian products:

21 A × (B C) = (A × B) (A × C).

22 A × (B C) = (A × B) (A × C).

23 (A × B) (C × D) = (A C) × (B D).

24 A × (B − D) = (A × B) − (A × D).