Sets

In mathematics, one naturally meets with collections of various kinds of objects. For example, the collection of all points on a line, the collection of all positive integers less than 100, the collection of all lines passing through a given point of the plane, are all collections which arise naturally in elementary mathematics. These collections are typical examples of sets. Roughly speaking, a set is any well-defined collection of objects. When we say "well-defined", we mean that it is possible to tell, without ambiguity, whether or not a given object belongs to the set. The reason we have defined the notion of a set only 'roughly' is that in more formal developments of set theory, "set" is an undefined term, whose properties are described by a system of axioms. Thus, the notion of "set" in set theory is analogous to the notions of "point" and "line" in Euclidean geometry.

Cantor was certainly not the first mathematician to use sets. Sets had come up in connection with particular mathematical problems centuries before Cantor. But it was Cantor who first considered the properties of general sets in a systematic way. And to understand the impact of the theory of sets on mathematics, it is necessary to consider the state of mathematics in the early nineteenth century. The Greek concept of mathematics as a deductive science was firmly entrenched. But the axioms from which mathematicians deduced their results were never quite spelled out. For example, mathematicians worked incessantly with real numbers, without ever knowing precisely what a real number was. One of the great triumphs of Cantor was to give a definition of a real number in terms of sets, which could be described by a rather simple list of properties. It is precisely the simplicity and generality of the notion of a set which makes it so natural a concept on which to lay the foundations of mathematics.

Let A and B be sets. If A=B, then AB and BA. Conversely, if AB and BA, then A=B.

Proof: If A=B, then A and B contain the same elements, so every element of A is contained in B and every element of B is contained in A. Thus AB and BA. Conversely, if AB and BA, then every element of A is contained in B and every element of B is contained in A. Therefore A and B contain the same elements so A=B.

Proposition 1 is extremely useful, because it gives a convenient way of proving that two sets A and B are equal by proving that AB and BA.

If A is a set, we will often display the elements of a set by inserting them in braces. Thus, if A is the set consisting of the first five letters of the English alphabet, then we write A = {a,b,c,d,e}, and if B is the set of natural numbers (that is, the set of all counting numbers, including zero), we will write B = {0,1,2,...}. If A is a set, then we can form subsets of A as follows: Suppose that for every xA, there is a proposition P(x), which may be true or false. Then we can form the subset of A consisting of all those elements of A for which P(x) is true. We will denote this set by {xA | P(x)}. For example, let B be as above and let P(x) be the proposition "x is even." Then

{xB | x is even}={0,2,4,...}.

The set which contains no elements will bet call the null set (or empty set) and will be denoted by . Note that is a subset of every set A, because every element of is contained in A.

Let be a collection of sets that is, let be a set (always assumed to be nonempty) whose elements are sets A, B, C,....It does not matter for the present whether the number of sets in is finite. The union of the collection is the set whose elements are those elements which belong to at least one set of the collection . The intersection of the collection is the set whose elements are those elements which belong to every set of the collection . The union and intersection of the collection are denoted

and

respectively. If consists of a finite number of sets, say

={A₁,...A_n},

then we will denote the union and intersection of by

A₁...A_n

and

A₁...A_n,

respectively.

Let us consider a few examples of the above definitions. Let R denote the set of all real numbers and define C₁,C₂, and C₃ by

C₁={xR | 0<x<1}
C₂={xR | 0<x<3},
C₃={xR | -1<x<½}

Then

C₁ C₂ C₃={xR | -1<x<3},
C₁ C₂={xR | 0<x<3},
C₁ C₃={xR | -1<x<1},
C₁ C₂ C₃={xR | 0<x<½},
C₁ C₂={xR | 0<x<1}

Let A and B be sets. Then the set {xA | xB} is called the difference of A and B, denoted A-B. The difference of A and B consists of precisely those elements of A which are not contained in B. For some graphic demonstrations, see examples.

Thus, using the same sets C₁,C₂, and C₃ as above, we can immediately see that

C₁-C₃={xR | ½<x<1},
C₁-C₂={0},
C₂-C₃={xR | ½<x<3}

There are a number of elementary properties of unions, intersections, and differences which are very useful in manipulating with sets. Let A, B, and C be sets. Then

A(BC)= (AB)C,

AB=BA,

A(BC)= (AB)C,

AB=BA,

A-(BC)=(A-B)(A-C),

A-(BC)=(A-B)(A-C).

Formulas (5) and (6) are called de_Morgan's formulas. All of the above formulas are proved by using Poposition 1. Let us illustrate the technique of proof by giving a proof to (5). Suppose that xA-(BC). Then xA and xBC. Therefore, xA and either xB or xC. If xB, then xA-B; if xC, then xA-C. Thus in either case,

x(A-B)(A-C),

and

A-(BC)(A-B)(A-C).

Suppose that

x(A-B)(A-C).

Then either

xA-B

or

x A-C,

so that xA and x does not belong to both B and C. In other words, xA and xBC, so that xA-(BC). Thus,

(A-B)(A-C)A-(BC).

By Poposition 1, we see that (5) holds.

Let A and B be sets. The Cartesian product of A and B is the set whose elements are pairs (a,b), where aA and bB. The Cartesian product of A and B is denoted by A B. Since we must make a distinction between the first element a and the second element b of the pair (a,b), the elements of A B are called ordered pairs. For example if A={1,2} and B={1,3} then

A B = {(1,1),(1,3),(2,1),(2,3)}.

The most familiar example of a Cartesian product is the plane of analytic geometry, which consists of all ordered pairs (a,b) of real numbers a and b, and is thus the Cartesian product R R. The ordered pair (a,b) equals the ordered pair (c,d), written (a,b) = (c,d), if and only if a = c and b = d by definition.

Let us end this section with a few comments about logic. If P and Q are logical propositions, we will denote the implication "if P then Q" by PQ or QP. We will denote the logical equivalence "P if and only if Q" by PQ. In order to prove and equivalence PQ, it is necessary to prove the two implications PQ and PQ.