Make your own free website on Tripod.com

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.

An object belonging to a set A is called an element of A. If x is an element of A then we write xelement ofA; if x is not an element of A, we write xnot an element ofA. If every element of the set A is contained in the set B, then we say A is a subset of B, denoted Asubset ofB. The two sets A and B are the same if they contain the same elements; in this case we write A=B. There is a simple relationship between equality of sets and the notion of subsets, which is expressed in the following result.

Sets:Proposition 1: Let A and B be sets. If A=B, then Asubset ofB and Bsubset ofA. Conversely, if Asubset ofB and Bsubset ofA, then A=B.

Let A and B be sets. If A=B, then Asubset ofB and Bsubset ofA. Conversely, if Asubset ofB and Bsubset ofA, 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 Asubset ofB and Bsubset ofA. Conversely, if Asubset ofB and Bsubset ofA, 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 Asubset ofB and Bsubset ofA.

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 xelement ofA, 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 {xelement ofA | P(x)}. For example, let B be as above and let P(x) be the proposition "x is even." Then

{xelement ofB | 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 empty set. Note that empty set is a subset of every set A, because every element of empty set is contained in A.

Let collection be a collection of sets that is, let collection 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 collection is finite. The union of the collection collection is the set whose elements are those elements which belong to at least one set of the collection collection. The intersection of the collection is the set whose elements are those elements which belong to every set of the collection collection. The union and intersection of the collection collection are denoted

general union

and

general intersection

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

collection={A1,...An},

then we will denote the union and intersection of collection by

A1union...unionAn

and

A1intersection...intersectionAn,

respectively.

Let us consider a few examples of the above definitions. Let R denote the set of all real numbers and define C1,C2, and C3 by

C1={xelement ofR | 0<x<1}
C2={xelement ofR | 0<x<3},
C3={xelement ofR | -1<x<½}

Then

C1union C2union C3={xelement ofR | -1<x<3},
C1union C2={xelement ofR | 0<x<3},
C1union C3={xelement ofR | -1<x<1},
C1intersection C2intersection C3={xelement ofR | 0<x<½},
C1intersection C2={xelement ofR | 0<x<1}

Let A and B be sets. Then the set {xelement ofA | xnot an element ofB} 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 C1,C2, and C3 as above, we can immediately see that

C1-C3={xelement ofR | ½<x<1},
C1-C2={0},
C2-C3={xelement ofR | ½<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

(1)
Aunion(BunionC)= (AunionB)unionC,
(2)
AunionB=BunionA,
(3)
Aintersection(BintersectionC)= (AintersectionB)intersectionC,
(4)
AintersectionB=BintersectionA,
(5)
A-(BintersectionC)=(A-B)union(A-C),
(6)
A-(BunionC)=(A-B)intersection(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 xelement ofA-(BintersectionC). Then xelement ofA and xnot an element ofBintersectionC. Therefore, xelement ofA and either xnot an element ofB or xnot an element ofC. If xnot an element ofB, then xelement ofA-B; if xnot an element ofC, then xelement ofA-C. Thus in either case,

xelement of(A-B)union(A-C),

and

A-(BintersectionC)subset of(A-B)union(A-C).

Suppose that

xelementof(A-B)union(A-C).

Then either

xelement ofA-B

or

x element ofA-C,

so that xelement ofA and x does not belong to both B and C. In other words, xelement ofA and xnot an element ofBintersectionC, so that xelement ofA-(BintersectionC). Thus,

(A-B)union(A-C)subset ofA-(BintersectionC).

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 aelement ofA and belement ofB. The Cartesian product of A and B is denoted by A cross 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 cross B are called ordered pairs. For example if A={1,2} and B={1,3} then

A cross 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 cross 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 PimpliesQ or Qbackward implicationP. We will denote the logical equivalence "P if and only if Q" by Pequivalent toQ. In order to prove and equivalence Pequivalent toQ, it is necessary to prove the two implications Pforward implicationQ and Pbackward implicationQ.