﻿ ﻿REVIEW OF SET THEORY - A Book of Abstract Algebra

## 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 xA (to be read as “x is an element of A”). On the other hand, if x is not an element of A, we write xA. (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 AB. 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 AB and BA, then A = B. And conversely, if A = B, then A5 and BA.

Sets are often represented pictorially by circular or oval shapes. The fact that AB 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,” orthe 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 xA and xB. The set A B is represented by the shaded area in the figure: 3.The difference of two sets is defined as follows: AB is the set of all those elements which are in A, but not in B. Thus, x is in AB if xA and xB. The set AB 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 xA B; this means that xA or xB. But this is the same as saying: xB or xA. Thus, xB A.

The same reasoning shows that if xB A, then xA 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 xA (B C): This means that

(i)xA, and

(ii)xB C.

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

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

(i)xA B, or

(ii)xA C.

In either case, xB or xC, so that xB C. Also in either case, xA. Thus, xA (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 aA and bB. That is,

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

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 AB and BC, then AC.

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

3 AA B and BA B.

4 A BA and A BB.

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 (BC) = (A B) − C.

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

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

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

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 AB, then A B′ = 0, and conversely.

20 If AB and C = BA, then A = BC.

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 × (BD) = (A × B) − (A × D).

﻿