▯ Review of set theory
▯ Combinatorial methods
2.1 Set theory
2003 Be▯t Champagne Compiled January 12, 2012 2.1 Set theory 13
2.1.1 Basic terminology
De▯nition of a set:
▯ A set is a collection of objects (concrete or abstract), called elements,
that usually share some common attributes, but are not otherwise re-
stricted in any fashion.
▯ The curly brackets f and g are used as delimiters when specifying the
content of a set. This may be achieved by either listing all the elements
of the set explicitly, as is
or by stating the common properties satis▯ed by its elements, as in
fa : a is a positive integer ▯ 6g (2.2)
In the latter case, the notation \a :" should read \all a such that".
▯ To indicate that an object a is an element of a set A, we write a 2 A; we
also say that a is a member of, or belongs to, A. If a is not an element
of A, we write a 62 A.
▯ Two sets A and B are identical (or equal) if and only if (i▯) they have
the same elements, in which case we write A = B. If A and B are not
identical, we write A 6= B.
▯ Example: Let A = f1;2;:::;6g and B = f2;4;6g. Then A 6= B because
1 2 A while 1 62 B.
2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 14
▯ If every element of a set A is also an element of a set B, we say that A
is contained in B, or that A is a subset of B, and write A ▯ B.
▯ If A is a subset of B but there exists b such that b 2 B and b 62 A, we
sometimes say that A is a proper subset of B and write A ▯ B.
▯ The negations of the set relations ▯ and ▯ are denoted by 6▯ and 6▯,
▯ Example: let A = f1;2;:::;6g, B = f2;4;6g and C = f0;1g, then
B ▯ A, B ▯ A, C 6▯ A, etc.
Sample space and empty set:
▯ In practical applications of set theory, all sets of interest in a given situ-
ation are usually subsets of a larger set called sample space, or universal
set, and denoted by the letter S.
▯ It is also common practice to introduce a degenerate set containing no
elements; the latter is called the empty set, or null set, and is denoted
by the symbol ;.
2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 15
Theorem 2.1: Let A, B and C denote arbitrary subsets of a sample space S.
The following relations hold:
(a) A ▯ A
(b) A ▯ B and B ▯ C implies A ▯ C
(c) A = B if and only if A ▯ B and B ▯ A
(d) ; ▯ A ▯ S
Proof: These basic properties follow directly from the preceding de▯nitions;
their proof is left as an exercise to the reader. ▯
2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 16
Commonly used sets of numbers:
▯ Basic sets of numbers:
- Positive integers, or natural numbers: N = f1;2;3;:::g
- Integers: Z = f0;▯1;▯2;:::g
- Rational numbers: Q = f :ba;b 2 Z and b 6= 0g
- Real numbers: R
- Complex numbers: C = fa + jb : a;b 2 Rg, where j = ▯1
Note that N ▯ Z ▯ Q ▯ R ▯ C.
▯ Let a and b be two arbitrary real numbers. The following subsets of R
are called intervals from a to b:
- Open interval: (a;b) = fx 2 R : a < x < bg
- Closed interval: [a;b] = fx 2 R : a ▯ x ▯ bg
- Left semi-open interval: (a;b] = fx 2 R : a < x ▯ bg
- Right semi-open interval: [a;b) = fx 2 R : a ▯ x < bg
Note that these intervals are empty, i.e. identical to the empty set ;,
when a > b.
2003 Beno▯t Champagne Compiled January 12, 2012 2.1 Set theory 17
Finite versus in▯nite sets:
▯ A set is called ▯nite if it is empty or contains a ▯nite number of elements;
otherwise it is called in▯nite.
▯ A set is called countable if it is ▯nite (countably ▯nite) or if it is in▯nite
but can be put into a one-to-one correspondence with the set of positive
integers N (countably in▯nite). In the latter case, the elements of the
set can be indexed sequentially.
▯ A set that is not countable is said to be uncountable or uncountably
- The set S = f1;2;3;4;5;6g is countably ▯nite.
- Examples of countably in▯nite sets include N, Z and Q.
- Examples of uncountably in▯nite sets include R and the open inter-
vals (a;b) for any a < b in R.
2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 18
▯ Let A and B be two arbitrary sets, not necessarily associated to the
same sample space. The product set of A and B, denoted A▯B, is the
set of all ordered pairs (a;b) such that a 2 A and b 2 B. That is,
A ▯ B = f(a;b) : a 2 A and b 2 Bg (2.3)
▯ The product set A ▯ A is also denoted in a more compact form as A .
▯ The generalization of this concept to products of more than two sets is
▯ As an example, the notation R , for n a positive integer, denotes the set
of all n-tuples (a 1a ;2::;a n where a 2 i for i = 1;:::;n.
I (a) Consider a single toss of a coin. The set of all possible observable results, or
outcomes, can be described as
where H denotes heads and T denotes tails.
(b) Consider two consecutive tosses of a coin. The set of all possible outcomes is
where, for example, the ordered sequence HT corresponds to H on the ▯rst toss
and T on the second toss. Observe that
S2= fH;Tg ▯ fH;Tg = S 1
The event that at least one head is observed can be represented by the subset
A = fHH;HT;THg ▯ S 2
2003 Beno^ ▯t Champagne Compiled January 12, 2012 2.1 Set theory 19
2.1.2 Set operations
De▯nitions: Let A and B be arbitrary subsets of a sample space S. We de▯ne
the following operations:
▯ The union of the sets A and B, denoted A[B, is the set of all elements
that belong to at least one of the sets A or B:
A [ B = fx 2 S : x 2 A or x 2 Bg (2.4)
▯ The intersection of the sets A and B, denoted A \ B, is the set of all
elements that belong to both A and B:
A \ B = AB = fx 2 S : x 2 A and x 2 Bg (2.5)
▯ The complement of the set A, denoted A , is the set of all elements of S
that do not belong to A:
A = fx 2 S : x 62 Ag (2.6)
▯ The di▯erence of the sets A and B, denoted A ▯ B, is the set of all
elements of A that do not belong to B:
A ▯ B = fx 2 S : x 2 A and x 62 Bg (2.7)
2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 20
▯ In the above de▯nition of the union, the \or" is a logical one, meaning
that x may be in A or B or both.
▯ In the probability literature, the symbol \ for the intersection is some-
times omitted, so that the notations A \ B and AB are equivalent.
▯ If A \ B = ;, we say that A and B are mutually exclusive (or disjoint).
▯ Finally, note that A = S ▯ A and A ▯ B = A \ B . c
2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 21
Theorem 2.2: Let A, B and C be arbitrary subsets of a sample space S. The
following identities hold:
(a) Basic identities:
A [ A = A and A \ A = A (2.8)
A [ S = S and A \ S = A (2.9)
A [ ; = A and A \ ; = ; (2.10)
(b) Commutative laws:
A [ B = B [ A and A \ B = B \ A (2.11)
(c) Associative laws:
(A[B)[C = A[(B [C) and (A\B)\C = A\(B \C) (2.12)
(d) Distributive laws:
A\(B[C) = (A\B)[(A\C) and A[(B\C) = (A[B)\(A[C)
(e) Complementarity laws:
A [ A = S and A \ A = ; (2.14)
c c c c
(A ) = A; S = ; and ; = S (2.15)
(f) DeMorgan’s laws:
(A [ B) = A \ B c and (A \ B) = A [ B c (2.16)
2003 Beno▯t Champagne Compiled January 12, 2012 2.1 Set theory 22
Proof: The proof of such properties is tedious but otherwise straightforward.
For any of the above equalities, we have to show set inclusion in both direc-
tion, that is: any arbitrary element of the set on the left-hand side is also an
element of the set on the right-hand side, and vice versa. This requires the
use and manipulation of logical assertions and operators. Familiarity with
the latter concepts is assumed.
As an example, consider the DeMorgan’s identity (A \ B) = A [ B . We c c
x 2 (A \ B) c () x 62 A \ B
() x 62 A or x 62 B
() x 2 A or x 2 B c
() x 2 A [ B
The other identities may be proved in a similar way; this is left as an exercise
for the reader. ▯
2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 23
I A die is rolled once. The set of possible outcomes is
S = f1;2;3;4;5;6g
De▯ne the subsets
A = fx 2 S : x ▯ 3g = f1;2;3g
B = fx 2 S : x even g = f2;4;6g
A \ B = f2g
A [ B = f1;2;3;4;6g
A c = f4;5;6g
B c = f1;3;5g
Let us verify DeMorgan’s Laws, i.e. Theorem 2.2 (f). From the above, we have
(A [ B)c = f5g
A \ B c = f5g
which shows that the ▯rst identity in (2.16) is satis▯ed. In the same way,
(A \ B) = f1;3;4;5;6g
A [ B = f1;3;4;5;6g
which shows the validity of the second identity in (2.16). J
2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 24
▯ Venn diagrams provide a useful mechanism for visualizing various set-
▯ Basic idea:
- represent sets as planar areas delimited by closed contours;
- these contours are included in a larger rectangular area representing
the sample space S itself;
- an operation between various sets is shown as a shaded area.
▯ This is illustrated in Figure 2.1 for the following operations: A [ B,
A \ B, A and A ▯ B.
A B A B
(a)A▯ B (b)A▯ B
A B A B
(c)A (d)A− B
Figure 2.1: Use of Venn diagrams to illustrate set operations.
2003 Beno▯t Champagne Compiled January 12, 2012 2.1 Set theory 25
▯ Venn diagrams are often used as an intuitive device for gaining insight
into complex set relations and operations, although their use in the for-
mal proof of set properties is not quite appropriate.
▯ As an example, the following theorem may be easily justi▯ed on the basis
of Venn diagrams.
Theorem 2.3: Let A and B be arbitrary subsets of a sample space S. Anyone
of the following conditions is equivalent to the inclusion A ▯ B:
(a) A \ B = A
(b) A [ B = B
(c) A \ B = ;
(d) A [ B = S
(e) B ▯ A c
Justi▯cation based on Venn diagrams: A Venn diagram’s interpretation of
Theorem 2.3 (a) and (b) is illustrated in Figure 2.2.
(a)A▯ B = A (b)A▯ B = B
Figure 2.2: Interpretation of Theorem 2.3 based on Venn diagrams.
2003 Beno▯t Champagne Compiled January 12, 2012 2.1 Set theory 26
▯ Consider a sequence of indexed subsets of S, say A wiere the index
i 2 I, with I being a subset (▯nite or in▯nite) of the natural numbers N.
▯ The union and intersection of the sets A , i 2 I, are de▯ned as
A = fx 2 S : x 2 A for some i 2 Ig (2.17)
i2I i i
A i fx 2 S : x 2 A fir all i 2 Ig (2.18)
S 1 T 1
When I = N, these may be denoted as i=1 and i=1, respectively.
▯ De Morgan’s laws admit immediate generalization to this case:
S c T c T c S c
( A i = A i and ( A i = Ai (2.19)
i2I i2I i2I i2I
▯ We say that the sequence A ;i 2 N, is increasing if A ▯ A ▯ A ▯ :::
i 1 2 3
In this case, we de▯ne
lim A = A (2.20)
i!1 i i=1 i
▯ We say that the sequence A ii 2 N, is decreasing if 1 ▯ A 2 A ▯ 3::
In this case, we de▯ne
lim A = A (2.21)
i!1 i i
2003 Beno▯t Champagne Compiled January 12, 2012 2.1 Set theory 27
I Consider the real plane, S = R . De▯ne A as tie subsets of all points in on
or inside a circle of radius i centered at the origin, where i is a positive integer.
2 2 2 2
A i f(x;y) 2 R : x + y ▯ i g; i 2 N
A1▯ A ▯2A ▯ :3:
so that the sequence Aiis increasing. This is illustrated in Figure 2.3.
1 2 3 x
Figure 2.3: An increasing sequence of subsets.
Also note that (try to prove it)
A i f(x;y) 2 R : (x;y) 2 A foi some ig = R 2
lim Ai= R 2
2003 Beno^ ▯t Champagne Compiled January 12, 2012 2.1 Set theory 28
2.1.3 Sets of sets
The elements of a set may themselves be sets. Such sets of sets are often
called classes or families of sets. Sets having for elements subsets of a sample
space S play a central role in probability. Below, we develop these concepts.
▯ The set of all the subsets of a set S is called the power set of S and is
denoted by P ,Sor simply P.
▯ Since ; ▯ S and S ▯ S, we have by de▯nition of P that S 2 P and S
S 2 P S
▯ For example, let S = f0;1g. Then P = S;;f0g;f1g;Sg
▯ When the sample space S is uncountably in▯nite (e.g. S = R), the
power set P Sill typically contain undesirable subsets that pose serious
▯ In such situations, it is usually desirable to work with a much smaller
subset of PS, that do not include the undesirable subsets.
▯ This leads to the notion of set algebras.
2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 29
Set algebra: Let F be a set of subsets of S, that is F ▯ P . We saS that F
is an algebra i▯
(a) S 2 F
(b) A 2 F ) A 2 F c
(c) A;B 2 F ) A [ B 2 F
▯ From (a) and (b), it follows that ; 2 F since ; = S .
▯ According to the above de▯nition, the algebra F is closed under the
operations of complementation and union.
▯ Using DeMorgan’s laws, you should be able to show that F is also closed
under the operation of intersection, that is: A;B 2 F ) A \ B 2 F.
I Let S = f0;1g. The corresponding power set is
P S f;;f0g;f1g;Sg:
It is easy to check that P is an algebra...
(a) S 2 P
(b) For any A 2 P S we have A 2 P. For example:
; = S 2 P ;S f0g = f1g 2 P S etc.
(c) For any A;B 2 P ,Swe have A [ B 2 P .SFor example:
; [ ; = ; 2 PS; ; [ f0g = f0g 2 PS; etc.