Basic Set Theory

Sets are probably the most important objects in mathematics. The machinery of pure mathematics (numbers, relations, functions, etc.) are all defined in terms of sets. To do this axiomatically (click here) is very abstract and the beginner may be puzzled as to why it is necessary at all.

Instead, we shall begin by defining sets informally and investigating a few of their properties. It is hoped that readers will then be in a better position to read, for example, the link above.

Firstly, we shall take the idea of membership as a primitive notion. That is, we shall assume that we know intuitively what it means to say that one object is a member (or element) of another. We then define a set to be an object which contains certain other objects ( we sometimes describe an object which is not a set as an individual). The simplest way to describe a set is to list its elements between curly braces. Thus {1,2} denotes the set whose only elements are 1 and 2.

We define two sets to be equal when they have precisely the same elements. Thus a set is completely determined by its elements.

Note the following points:

(i) Order of elements is immaterial. Thus {1,2} = {2,1}

(ii) Repetition of elements is irrelevent, so that {1,2,2,1,1} = {1,2}

We use the notation {x : P} to denote the set containing all objects x such that the condition P holds. For example,

{x : x is real}

denotes the set of real numbers,

{x : x has blonde hair}

denotes the set of all objects which have blonde hair, and

{x : x is a dog}

denotes the set of all dogs. In informal contexts we might also denote this last set by {dogs}.

Sets are frequently named by upper-case letters. Thus we might write

A = {x: x is an even integer}

to mean that A is the set of even integers.

Subsets: Given two sets A and B we say that A is a subset of B (or that A is contained in B, or that B contains A) if every element of A is automatically an element of B.
As an illustration, define

A = {x : x is real}

B = {x : x is an integer}

C = {x : x is an odd integer}

D = {x : x is or was a US President}

Then it is true that C is a subset of B, B is a subset of A and C is a subset of A. Note that not all sets are comparable in this way. For example, it is not the case that either A is a subset of D or D is a subset of A. The sets A, B and C illustrate the

PROPOSITION 1: Given any three sets A, B and C, if A is a subset of B and B is a subset of C, then A is a subset of C.

The proof is an easy exercise. It is also the case that

PROPOSITION 2: Two sets A and B are equal if and only if A is a subset of B and B is a subset of A.

Given a set X, we may consider the subset of X consisting of all elements of X for which some further property holds. We write

{x in X : P(x)}

to denote the set of all elements x of X for which P(x) holds; it means the same as

{x : x is in X and P(x)}

Universal Sets and Complements: In certain contexts we may consider all of our sets as being subsets of some given universal set. For instance, if we are investigating properties of real numbers (and sets of reals) then we may take R, the set of all reals, as our universal set. It is important to realise that a universal set is only temporarily defined: there is no such thing as a "universal" universal set, "the set of everything" (see below).

Given a universal set U and a subset A of U, we may define the complement of A ( in U) as

A' = {x in U: x is not in A}

i.e. the set of all elements of U which are not in A. Thus in the above examples, if B is the universal set, then

C' = {x in B : x is not an odd integer} = {x : x is an even integer}

and if A is the universal set, then

B' = {x : x is real and not an integer}

Intersection and Union: Given two sets A and B we may construct their union. This is the set consisting of all objects which are elements of A or of B or of both. Their intersection is the set of all objects which are in both A and B. Symbolically, these are respectively

A \/ B = {x : x is in A or x is in B or both}

A /\ B = {x : x is in A and x is in B} = {x in A : x is in B} = {x in B : x is in A}

To illustrate these ideas, take the universal set U as the set of all living human beings,

A = {x in U : x is left handed}

B = {x in U : x has blonde hair}

Then A /\ B is the set of all left-handed blonde-haired people, while A \/ B is the set of all people who are left-handed or have blonde hair or both.

But now let the universal set U be the set of living things,

E = {x : x is a human being}

F = {x : x is over 200 years old}

What is E /\ F in this case? No human being is over 200 years old, so E /\ F must be a set without any elements at all, an empty set. Since a set is determined completely by its elements there can only be one such set and we denote it O.

PROPOSITION 3: The empty set is a subset of every set.

Proof: Given any set A, we wish to prove that O is a subset of A. This involves showing that all elements of O are elements of A. But there are no elements of O. For the experienced mathematician, the inference " O has no elements so all elements of O are elements of A" is immediate, but it may be more troublesome for the beginner. Since O has no members at all, how can "they" be members of anything else? It may help to think of it the other way round. In order to prove that O was not a subset of A, we would have to find an element of O which was not also an element of A. Since there are no elements of A, this is impossible and hence O is indeed a subset of A

We list without proof a few other simple properties of sets.

PROPOSITION 4: For any sets A, B, C

(a) A /\ B = B /\ A

(b) A \/ B = B \/ A

(c) (A /\ B) /\ C = A /\ (B /\ C)

(d) (A \/ B) \/ C = A \/ (B \/ C)

(e) A is a subset of B if and only if A \/ B = B

(f) A is a subset of B if and only if A /\ B = A

(g) A /\ B is a subset of A, which is a subset of A \/ B

(h) A /\ O = O

(i) A \/ O = A

(j) If A and B are subsets of a universal set U, then A is a subset of B if and only if B' is a subset of A'

We can also prove the so-called distributive laws

PROPOSITION 5: For any sets A, B, C

(a) A /\ ( B \/ C) = (A /\ B) \/ (A /\ C)

(b) A \/ ( B /\ C) = (A \/ B) /\ (A \/ C)

Proof: We shall prove (a) and leave (b) as an exercise. Each side of equation (a) defines a set and we wish to prove that these sets are equal. By Proposition 2, a possible strategy is to show that each side is a subset of the other.

(i) Pick any element x of the left-hand side (LHS). Then, by definition of /\, x is in A and x is in B \/ C; that is x is in A and either x is in B or x is in C. In the first case, x is in both A and B, so is in A /\ B and a fortiori in (A /\ B) \/ (A /\ C). In the second case x is in both A and C and so is again in (A /\ B) \/ (A /\ C). Thus in either case x is in (A /\ B) \/ (A /\ C). we have shown that every element of the LHS is automatically in the RHS. But this is precisely what we mean by saying that the LHS is a subset of the RHS.

(ii) Pick any element x of the RHS. Then x is in (A /\ B) or x is in (A /\ C); in the first case x is in A and x is in B; in the second, x is in A and x is in C. In either case x is in A. Also x in the first case x is in B and hence in B \/ C; in the second case x is in C and thus in B \/ C.

We have proved that whatever x is, if it is a member of the RHS then it is in both A and B \/ C and hence by definition is in A /\ (B \/ C). We have proved that the RHS is a subset of the LHS.

By Proposition 2, (i) and (ii) together prove that LHS = RHS, as required.

Paradoxes: We referred earlier to the need for a formal, axiomatic approach. What problems arise in the treatment we have given? The problems relate to the formation of sets. One's first intuition might be that we can form any sets we want,but this view leads to inconsistencies. For any set we can ask whether x is a member of itself. Define

Z = {x : x is not a member of itself}

Thus for every object x, x belongs to Z if and only if x does not belong to x. Now for the problem: is Z a member of Z? If yes, then by the defining quality of Z, Z is not a member of itself i.e. Z is not a member of Z. This forces us to declare that Z is not a member of Z. Then Z is not a member of itself and so, again by definition of Z, Z is a member of Z. Thus both options lead us to a contradiction and we have an inconsistent theory. Axiomatic developments place restrictions on the sort of sets we are allowed to form and thus prevent problems like our set Z arising. The penalty is a much more difficult development.

Cartesian Product: We resume the formal development. Given objects a, b the ordered pair containing a and b is denoted (a, b). For the time being we shall take this as a primitive notion ( but see also here). That is we shall assume that (a , b) has the property that if (a , b) = (x , y) then a = x and b = y. The objects a and b are called respectively the first and second components of (a , b). Now, given two sets A and B, we define their Cartesian Product to be

A * B = { (a , b) : a is in A and b is in B }

That is, A * B is the set of all ordered pairs whose first component is an element of A and whose second component is an element of B.

We can extend this definition to a set A * B * C of ordered triples, and more generally to sets of ordered n-tuples for any positive integer n. It is even possible to define infinite Cartesian products, but to do this we need a more recondite definition of the product.

Cartesian products play an important role in analytic geometry. If R denotes the set of all real numbers, then R² represents the Euclidean plane and R³ represents three-dimensional Euclidean space.

---

/Talk