3 Set Theory PDF
3 Set Theory PDF
3 Set Theory PDF
SET THEORY
This chapter gives an in-depth discussion on set theory. Most of the concepts here were already
discussed in Math 17. Some advanced concepts will be included in this chapter such as generalized
operations, field of sets, sigma field, and Borel field. Furthermore, we will learn in this chapter how to obtain the
limit of a sequence of sets. Set theory plays a vital role in Probability theory. Sets and sigma fields will be
called events and event spaces, respectively, in Stat 121.
Definitions:
A set is defined as any well-defined collection of objects. The objects that make up a given set
are called its elements or members. A set is denoted by capital Latin letters, A, B, C,… If an
element belongs in A then this is denoted by A; otherwise, A. That is, A~(A)
The universal set is the set of all points/ elements under consideration. This is denoted by .
An element or point in is denoted by .
It is important to understand that what we mean by the term well-defined. The elements of a well-defined
collection must be distinguishable from one another. However, the order in which these elements are taken
has no significance.
Roster or Tabular method: List or enumerate all of its elements within a pair of curly brackets { }, and to separate
these elements from one another by commas.
Rule method: enclose in brackets a descriptive phrase that specifies the properties that characterize all the
elements in the set. This is also called the set-builder notation or defining property method. This method is
particularly convenient when dealing with infinite sets.
e.g. A = { x : P(x)} is read as “the set of all elements x such that P(x) is true.”
Examples:
1. = collection of letters in the English alphabet = {A, B, C, …, X, Y, Z}
A = {A, E, I, O, U} = {vowels in the alphabet}
Sometimes, it does happen that all the elements of one set A are also elements of another set B. For
instance, if we call A the set of people living in Metro Manila, and B the set of people living in Luzon, then
clearly, every element of A is also an element of B. In a situation such as this, the set A is said to be a subset
of set B, where as the set B is a superset of set A.
Definition:
Remarks:
1. Take note that from the definition of a subset is actually a universally quantified statement. In order to
prove this, we need to take an arbitrarily selected element , then show that A B. Then, use
universal generalization to conclude that A B.
2. Now, in order to show that A B, then, based on the definition of a subset, we need to disprove a
universally quantified statement. So, we need to find at least one element which is in set A but not in set
B.
3. In actual practice, the style of proof writing that mathematicians use in proving less basic results about set
inclusion and equality is not quite so formal. As one becomes more experienced in writing proofs, the
underlying logical principles are used in a (hopefully correct, but) less explicit manner. The point of
departure toward writing such proofs is a method of proof so widely applicable that its importance cannot
be stressed strongly enough. It might be called the “elementhood” method, the “choose” method, or the
“pick-a-point” method. Whatever it’s called, the principle sets forth:
The direct way to prove that a set A is a subset of a set B is to start by letting a symbol x
represent an arbitrary element of A. This element, though generic (i.e. not a specifically
identified or named element of A), is to remain fixed throughout the proof. The proof is carried
out by deducing, through methods depending on the specifics of the problem at hand, that this x
must be an element of B.
Examples:
Yes. Suppose x .
Therefore, E F.
2. Is F E?
Thus, F E.
Exercises:
1. Is D C?
2. Is C B?
3. Is B C?
1. Reflexive property for set inclusion. Any set A is considered to be a subset of itself, that is, A A for
any A.
But, since is an arbitrarily selected element, then, by universal generalization, , A A. ■
Note: An alternative way to prove this is to use the rule of excluded middle (REM). We know that A
~(A) is a tautology then use material implication.
Let be an arbitrary element from . Suppose A B and B C. That means that A B and B C
using universal instantiation.
But, since is an arbitrarily selected element, then, by universal generalization, , A C. ■
Definition:
A is a proper subset of B iff A B and B A. That is, there is at least one element of B
which is not in A.
Example:
We say that A is a proper subset of B since all the elements of A are in B but there is one element in B, which
is z, that is not in A.
Definition:
Two sets A and B are equal iff A B and B A. This is written as A = B.
Example:
Example:
Assuming the theorem “for all real numbers x and y, if xy = 0, then x=0 or y=0,” prove that the set A={5, -7}
equals the set B = {x | x2 + 2x – 35 = 0}
Proof:
a. To prove that A B, let a A be given. To prove that a B, we must prove that a is a real number
satisfying a2 + 2a – 35 = 0. Now since a A, then either a=5 or a=-7. If a=5, a and a2 + 2a – 35 = 52 +
2(5) – 35 = 0, as required. On the other hand, if a=-7, then again a and a2 + 2a – 35 = (-7)2 + 2(-7) –
35 = 0. In either case, we have a B, as desired.
b. Conversely, to prove B A, suppose b B, so that b is a real number satisfying b2 + 2b – 35 = 0. But then,
b2 + 2b – 35 = (b-5)(b+7) = 0 so that by the assumed theorem, either b=5 or b=-7. Thus, b {5, -7} = A, as
desired.
Exercises:
1. A= { x : x2 + x – 6 = 0} B={2 , -3}
Are A and B equal?
(Note: There is a basic difference between an element p and the singleton set {p}.)
Definition:
Let A and B be subsets of ,
It is sometimes helpful to make use of a pictorial representation in dealing with relations between
sets. Such diagrams are called Venn diagrams after the English logician James Venn.
The complement Ac of A A
The union A B A B
The intersection A B A B
Set difference A – B = A Bc A B
Remarks:
1. The elements which are not in set A but in the universal set are included in the complement of A. This
operation is unary rather binary. That is, we obtain a resultant set from a single given set rather than
from two sets.
2. The elements of the intersection of A and B are those elements which are common to A and B. It may
be thought of as the “overlap” of A and B.
3. The elements of the union of A and B are those objects in either A or B, including any objet that
happens to lie in both A and B. The operations of union and intersections are called binary operations
because they are applied to two sets to make a third set.
4. The set theoretic difference, or simply set difference, denoted by A-B, is a binary operation that yields
the complement of B relative to a set A. This set consists of all objects that are elements of set A and
are not elements of B. Note also that we need not know the universal set in order to compute A-B.
Similarly. B-A is the set containing all elements of set B and are not elements of A.
5. The proper difference is similar to set difference but it also requires that a set is a subset of another
set.
6. The elements of the symmetric difference are the objects which are in set A but not in set B or objects
which are in set B but not in set A. In other words, the objects included in the symmetric difference are
those elements in one or the other of the sets A and B, but not in both.
1. Suppose = {1, 2, …, 15}. Let A = {2, 4, 6, 8, 10}. B={6, 8, 10, 12}, C={1, 3, 5, 7, 9, 11}, and
D={4, 6, 8}. Obtain the following:
2. Prove: (A B) A (A U B).
a) To show (A B) A:
b) To show A (A U B)
3. Prove: (A U B)c = Ac Bc
We need to show:
Suppose .
(A U B)c ~((A U B)) def’n of complement
~(A B) def’n of union
~(A) ~(B) de Morgans
Ac Bc def’n of complementation
(Ac Bc) def’n of intersection
Exercises:
1. Prove: (A B) U (A Bc) = A
2. Suppose = set of all real numbers. Let W = (-,3), X=(-3, 5], and Y=[4, ). Compute WX and WY.
a) A U B c) A - B
b) A B d) A B
4. Prove all of the properties of set operations listed down in the next section.
Example:
Suppose is the set of all real numbers. Define A=(-1,0), B=[-10, -2), and C={-0.5}. Which of the
following sets are disjoint?
Associative Laws (A U B) U C = A U (B U C)
(A B) C = A (B C)
Distributive Laws A U (B C) = (A U B) (A U C)
A (B U C) = (A B) U (A C)
Complement Laws A U Ac = A Ac =
0/1 Laws c = c =
A B iff A U B = B
A B iff A B = A
A B iff Ac U B =
A B iff A Bc =
A B iff Bc Ac
1. Ac – Bc = B – A.
Proof:
Ac - Bc = Ac (Bc)c def’n of set difference
= Ac B involution
= B Ac commutation
= B–A def’n of set difference
Proof: Suppose A B.
(B C) U A = (B U A) (C U A) distribution
= B (C U A) A B iff A U B=B
Exercises:
Prove the following using the properties of set operations:
1. A (B – C) = (A B) – (A C).
3. Prove:
a) A – B and AB are disjoint.
b) B – A and AB are disjoint.
Definition:
Let be the index set. Each is called an index.
The generalized union is denoted by
A and the generalized intersection is denoted by A . These
generalized operations are defined as follows:
Remarks:
If the index set is the set of the first n positive integers, that is, ={1,2,…,n}, then the generalized union and
intersection are called finite union and finite intersection, respectively, and we write:
A
i 1
i A1 U A2 U … U An (finite union)
n
A
i 1
i A1 A2 … An (finite intersection)
If the index set is the set of positive integers, that is, =Z+, then the generalized union and intersection are called
countable union and countable intersection, respectively, and we write:
A =A
i 1
i 1U A2 U A3 U … (countable union)
A =A
i 1
i 1 A2 A3 … (countable intersection)
Examples:
4 4
A
i 1
i [0,1] A
i 1
i (0,1)
A [0,1] A {0}
[ 0,1] [ 0 ,1]
A
i 1
i Z A
i 1
i {-1,0,1,2}
d) = Z+ where A = [-,]
3. Suppose is the set of all possible outcomes when a coin is tossed 3 times.
a) List down the elements of
b) Let Bi = {=(1,2, 3) : i =H} , i=1,2,3; that is, Bi = the set containing all elements in
where ith toss results in a head. List down the elements in the following sets and express
each set in terms of Bi.
D = the set of outcomes where only the 1st toss results in a head
= {HTT}
= B1B2cB3c
E = the set of outcomes where the 1st and 2nd tosses result in heads
= {HHH, HHT}
= B1B2
G = the set of outcomes where at least one of the tosses results in a head
= {HTT, THT, TTH, HHT, HTH, THH, HHH}
= B1 U B2 U B3
1. Suppose = set of real numbers. Evaluate the generalized union and intersection of the
following where = Z+:
a) A = [-1/, 2 - 1/]
b) A = (-1/, 2 - 1/)
c) A = [1 + 1/, 2 + 1/]
d) A = (1 – 1/, 2 + 1/)
2. In the tossing of a coin 3 times, let Bi = set of outcomes where the ith toss is a head, i=1,2,3.
List down the elements in the following sets and describe each set in terms of Bi.
n n
3. Find A and A .
i 1
i
i 1
i
4. Find Ai and
i 1
A.
i 1
i
5. Suppose a die is tossed 3 times. Define Aij = the set containing outcomes where i dots appear
on the jth toss. i=1,2,3,4,5,6 j=1,2,3
a) = {1,2,3,…, 50}
A = [ -1/ , 2 ]
b) = {1,2,3,…}
A = (-1/, (+1)/ )
BU( A ) =
(B U A)
B( A ) =
(B A)
Illustration:
n n
BU( A ) = B U (A
i 1
i 1 A2 … An) = (B U A1) (B U A2) … (B U An) =
i 1
(B U Ai)
n n
B( A ) = B (A
i 1
i 1 U A2 U … U An) = (B A1) U (B A2) U … U (B An) =
i 1
(B Ai)
C
n n
Ai = (A1 A2 … An)C = AC1 U AC2 U … U ACn = A C
i
i 1 i 1
Definition:
A class of sets is a collection of subsets of . Classes of sets will be denoted by script letters A,
B, C, …
Example: {{2,3}, {5}, {4,7}} is a class but {{2,3}, 5, {4,7}} is not a class since 5 is not a set.
Remarks:
A class of sets is simply a set containing sets.
Since the class is also a collection then everything that has been discussed on sets will also apply to the class,
except that the elements of a class are now sets and the subset of a particular class must also be a class.
Definition:
The class consisting of all subsets of a set S is called the power set of S and is denoted by 2S.
That is, ℘( ) =2S = {A: A S}.
Example: Let S={1,2,3}. 2S ={, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, S}.
Remarks:
2S and S 2S.
If the set S has no elements, the 2S={} which is not empty.
If S is a finite set containing n elements, then 2S will have 2n elements.
The best way to write down the members of the power set is to list the empty set first, then the subsets of
the set S consisting of singletons, then the doubletons, and so on, eventually writing down the set A itself.
2S is merely a symbol and has no numerical value.
Definition:
A class A = {A1, A2 , …, An} is said to be pairwise disjoint if and only if Ai Aj = for all ij.
Remarks:
The necessary and sufficient condition for a class to be pairwise disjoint as given in the definition is
n(n 1)
actually a conjunction of propositions.
2
A class is not pairwise disjoint if at least one of the pairwise intersections is not equal to the empty
set. That is, if there is at least one pair of sets in the class that have common elements then the class is not
pairwise disjoint.
n
If A = {A1, A2 , …, An} is pairwise disjoint then A
i 1
i . But the converse is not true.
Examples:
1. Let A ={A,B,C,D}. State the necessary and sufficient condition for A to be pairwise disjoint.
n ( n 1)
It is the conjunction of the following 6 propositions:
2
(i) AB = (iv) BC =
(ii) AC = (v) BD =
(iii) AD = (vi) CD =
The first three propositions have been proven to be true in the previous exercises.
Exercise:
Definition:
A class A = { A1, A2 , …, An} where A i A , i = 1,2,…,n, is said to be a partition of the set A iff:
Example:
1. Let A={1,2,3,4,5}.
Verify first that all of the sets in the class are subsets of AUB (Exercise).
To show (ii):
Exercise:
Suppose AB and BC. Show that A = {A, B-A, C-B} is a partition of C.
Definition:
A collection of subsets of , denoted by F, is called a field of sets or algebra of sets iff it satisfies the
following:
(i) F
Examples:
a) {, }
b) {, {1,2}, {3,4,5,6}, }
c) 2
d) {, {1,2}, {3,45}, {6}, }
1. F.
Thus, F.
Thus, A B F.
Remark:
A sigma-field is merely a collection of subsets of Ω. The members of this collection are simply sets and
have the properties that: if set A is in the collection, so is its complement AC; if A1, A2, …, An is a member of the
collection, then so is A1 U A2 U … U An. As a natural consequence, these stipulations ensure that Ω, , A1
A2 … An are also members of the collection.
Let Ci (i I) be the fields indexed by points of a non-empty set I which may be finite, countable, or
uncountable.
n
Let Co = i 1
Ci the class of all sets common to all Ci (by definition of generalized intersection)
n
If set Ak Co (k=1, 2, …, n), then Ak Ci for all i in I. Then, A
k 1
k Ci for all i in I and hence it belongs to Co =
n
i 1
Ci implying that Co is closed under finite intersection.
Therefore, Co is a field.
2. Use mathematical induction to prove that the field is closed under finite union.
3. Use the fact that the field is closed under finite union to prove that the field is closed under finite
intersection.
4. Suppose A is an algebra. Prove that an algebra is closed under the operation of set difference using
the definition of an algebra.
Definition:
Let C be a collection of subsets of . The minimal field containing C , denoted by F (C ), is the
smallest field containing C , that is, it satisfies the following properties:
Suppose F (C) is a minimal field containing C and it is not unique. If it is not unique then there is
another minimal field containing C, say G , that is distinct from F(C).
By definition of a minimal field, we can conclude the following about F(C) and G:
(i) F (C) is a field containing C and if there is another field containing C then F (C) is a
subset of that class; and,
(ii) G is a field containing C and if there is another field containing C then G is a subset of
that class.
Since G is a field containing C then by (i), we can conclude that F (C) G. Likewise, since F (C) is a
field containing C then by (ii), we can conclude that G F(C). Therefore, F (C) = G. This contradicts
the earlier premise that G is distinct from F (C).
Step 1. Obtain the class C 1={, , A, Ac , such that either AC or AcC } where A . Evidently, C 1 is
closed under complementation and contains C.
n
Step 2. Obtain the class C 2 containing B
k 1
k , whenever Bk C 1, n being arbitrary. Now C 2 is closed
Step 3. Obtain the class C 3, the class of all finite unions of pairwise disjoint subsets belonging to C 2.
Since they also contain complements, C 3 is a field and is the minimal field containing C .
Example:
Let = {a,b,c,d}. Construct the minimal field containing C={{a,b}, {c}}
F (C) = C3
Exercises:
1. C ={{1,2}, {3,4}}.
2. C ={{1},{1,2},(2,3}}
Definition:
A class F of subsets of , is called a -field of sets or -algebra of sets iff it satisfies the following:
(i) F
Suppose A is a sigma-field. The first two axioms in the definition of a field are exactly the same as the first
two axioms in the definition of a sigma-field. Thus, all we need to show in order to prove that A is a field is
that A is closed under finite union.
Ai A, i=1,2,….,n, n+1,n+2,…
n n n n
But, Ai Ai U
i 1 i 1
Ai =
i n 1
Ai U
i 1
i n 1
= Ai U =
i 1
A .
i 1
i
n
Thus, A A. A is closed under finite union and is therefore a field.
i 1
i
Let =set of all positive integers and C ={A : A is a finite set or Ac is a finite set}. This class is a field
but not a -field.
A U B is finite. Thus, A U B C.
But A U B = (Ac Bc)c by de Morgan’s law. Since the complement of A U B is a finite set then A U B C.
Since A=(AC)C is a finite set, AC C. Since BC is finite, BC C. Since BC is finite, and the intersection of a finite
set with another set is finite, then BC AC is finite.
Since B = (BC)C, by involution law, is finite set then BC C. Since AC is finite, and then AC C. Since BC is
finite and the intersection of a finite set with another set is finite, then AC BC is finite.
Since AC BC is finite, then BC AC C. By de Morgan’s theorem and involution law, (AC BC)C = (AC)C U
(BC)C = A U B. Since the complement of A U B is finite, by the definition of C, A U B C.
Therefore, C is a field. ■
But A = set of even integers.
i 1
i This is an infinite set. Its complement, the set of odd integers, is also an
infinite set. Thus, A C. C is not closed under countable union and is therefore not a sigma-field. ■
i 1
i
A field containing only a finite number of elements is also a -field. However, a field containing infinitely many
elements is not necessarily a -field.
(i) C (C )
(ii) (C ) is a -field of sets.
(iii) If C D and D is a -field then (C ) D.
The minimal -field generated by C is unique. (The proof is similar to that of a minimal field.)
To obtain (C ) from a given class C, the same steps in the construction of F(C ) are followed except that in
Step 2, n is allowed to be infinite.
Definition:
Let =the set of all real numbers and C = {(-, x): x R}. The Borel field of subsets of the real
line, denoted by B, is the minimal sigma-field containing C. That is, B = (C ). The sets contained in the
Borel field are called Borel sets.
A sigma field which will be of special interest to us is called the Borel Field. It will be denoted, using a
special symbol, as B. In the discussion that follows we shall specifically consider the Borel field of the real line.
Before describing the Borel field of the subsets of R in detail, let us consider some rather elementary situations
which will serve to motivate us.
Suppose = {a, b, c, d}. Then, as can be easily checked, {ø, {a}, {a,b}} is not a sigma-field. For instance, the
complement of {a}, namely {b, c, d}, is missing. Suppose we introduce just those sets we need to make a
sigma field – no more, no less. Thus, we will need the sets
The class of sets {ø, {a}, {a,b}, {b, c, d}, {c, d}, {a, c, d}. {b}, } is a sigma field. Because of the way we
constructed it, it is the smallest sigma field containing the set {ø, {a}, {a,b}}. It is called the sigma field
generated by {ø, {a}, {a,b}}.
We are now in a position to discuss the Borel field of the real line. To construct it, we use the following
procedure:
2. For B to be a sigma field we now require that it contain complements of the intervals that we included in (1).
Since the complement of (-, x) is [x, +), the collection B will contain all the intervals of the type [x, +)
where x is any real number. For example, intervals of the type [1/4, +), [-1, +), [50, +), etc. will be
members of B.
3. Suppose a and be are any two real numbers with a<b. Since by (1), (-, b) is a member of B and by (2), [a,
+) is a member of B, then (-, b) [a, +) = [a, b) is also in B. In other words, all the intervals of the type [a,
b), where a and b are real numbers with a<b, are in B. For example, [-5, 20), [3, 5), [-30, -20), etc. are in B.
4. From (3), we can conclude that intervals of the form [a, a+1/n), where a is any real number and n is any
positive integer (since a<a+1/n), are in B. And, since B is a sigma-field, it should be closed under countable
intersection, i.e.
1
, + = { }.
Thus, for any real number a, {a} is in B, i.e. the singletons are included in the Borel field. For example, the
singletons {1}, {-100}, {1/3}, etc. are in B.
5. Since a sigma field is closed under set difference and by (3) and (4), [a,b)-{a} = (a,b) for any real number a
and b with a<b, is in B. Thus, intervals of the form (1,2), (-9.2, -4.5), (-3, 5.78), etc. are in B.
6. Since a sigma field is closed under union of two sets and by (4) and (5), (a,b) U {b} = (a, b] is in B, for any
real numbers a and b with a<b. Thus, intervals of the form (1,2], (-1/2, 5], etc. are in B.
7. Since by (6) and (4) and by closure under union of two sets, (a, b] U {a} = [a, b] is in B, for any real
numbers a and b with a<b. Thus, intervals of the form [0, 1/5], [-9, 0], [5, 9], etc. are in B.
8. Since singletons are in B, all positive integers {1}, {2}, … are in B. But since a sigma field is closed under
countable union, i.e.
{ }=ℤ ,
The set of positive integers is also in the Borel field. It can easily be verified that the set of negative integers,
set of all integers, set of all even and odds integers, set of rational numbers, etc. are also members of the Borel
field.
Remarks:
The collection B is thus a very large collection of subsets of R which, starting with the sets of the type
(-, x), is obtained by repeatedly carrying out the operations of union, intersection, and
complementation. That is, the Borel field of the real line is the smallest sigma field containing all sets of
the form (-, x). The members of B are called Borel sets of the real line.
The Borel field is also the minimal -field containing C 1 = {(-, x], x R } or C 2={(a,b], a<b, a,b R },
C 3={[a,b], a<b, a,b R }, C 4={(a,b), a<b, a,b R }, C 5={[a,b), a<b, a,b R }, C 6={(x, ), x R }, and so on.
The Borel field and Borel sets play a very important role in the study of probability theory.
Definition:
An indexed class of sets, denoted by {A: } or simply {A}, assigns a set A to each .
When the index set is the set of positive integers, the indexed class {An} = {A1, A2, …} is called a
sequence of sets.
Definition:
Given a sequence of sets {An},
Remarks:
n
For a monotone nondecreasing sequence of sets {An}, Ai An
i 1
and A
i 1
i A1 .
n
For a monotone nonincreasing sequence of sets {An}, Ai An
i 1
and A
i 1
i A1 .
simply denoted as An A.
The limit of a monotone nonincreasing sequence of sets {An} is A= Ai , that is, lim An =
i 1
n
A or simply
i 1
i
denoted as An A.
Remarks:
Exercises:
I. Which of the following are monotone sequences? For monotone sequences, identify whether it is a
monotone nondecreasing or nonincreasing sequence and determine its limit.
II. Consider the following sequences {An} of subsets of R. In each case, state whether the sequence is
contracting or expanding and find the lim →∞ .
1. = |1 + ≤ ≤4−
2. = |1 + < <4−
3. = | >2−
4. = | ≥2−