The Theory of Sets
Lester M.K. Kwong ∗
Department of Economics
Brock University
Version: 3.1.1
Revised: September 18, 2012
∗
Copyright ' 2004-2012 Lester M.K. Kwong. Department of Economics, Brock Uni-
versity, 500 Glenridge Ave.Catharines, Ontario, L2S 3A1, CanEmail: lk-
[email protected] Tel: +1 (905) 688-5550, Ext. 5137. This document was typeset with
the LE XDocumentation System usingYthe X -pic and the MnSymbol packages. 1 Introduction
Much of advanced economic theory is described using the notion of sets.
For example, a consumer’s objective is to maximize his utility by choosing a
bundle from the set of all a▯ordable bundles. Conversely, a player is to choose
a strategy from the set of all possible strategies to maximize his expected
payo▯ in a game theoretical scenario. Due to the wide usage of sets across
the discipline, any progress into an understanding of economic theory will
require a clear and precise understanding of the fundamental concepts often
used in set theory.
The remainder of this chapter is organized as follows. Section 2 intro-
duces the basic concepts used in set theory. Namely, the notion of elements,
empty sets, subsets, and power sets will be discussed. The introduction of
elementary binary operations such as union, intersection, and complementa-
tion are then discussed in Section 3. The discussion to include extended set
operations and subsequently an introduction to concepts such as indexing
and partitions are found in Section 4. Lastly, some review exercises follows.
2 Sets
A set, in a nutshell, is simply some collection of objects which satisfy some
characteristics de▯ning the set. An object which belongs to, or is a member
of, a set is called an element. For example, the set N is the set of natural
numbers whose members, or elements are the individual counting numbers.
However, sets need not be restricted to numbers. A set of textbooks, for
example, can have as elements the title of textbooks for certain courses or
the set of teams in the NHL will have as elements teams in the National
Hockey League such as the Vancouver Canucks.
It is standard convention to denote sets using capital letters and its ob-
jects, whether it is a member of the set or not, using lowercase letters. So
for example, x is an object and X is a set. If x is an element of the set
X, we denote this by writing x ∈ X read \x is in X," \x belongs to X," or
just simply \x is an element of X." In the event that the object x does not
belong to the set X, that is ∼ (x ∈ X), we write x ∉ X read \x is not an
element of X." So for example, if N denotes the set of all teams in the NHL
then Vancouver Canucks ∈ N whereas the New York Yankees ∉ N.
Since a set is a collection of objects which satisfy some prede▯ned char-
1 acteristics, it is standard to write:
X = {x ∶ S(x)}
where S(x) is the predicate de▯ning such characteristics. The above notation
is read \the set X is equal to the objects x (from the universe) so that
S(x) is true." So, for example, if the universe is the set of all integers and
S(x) =\x is a number strictly between 2 and 5," then the set X = {x ∶ S(x)} =
{3;4}. Similarly, if the universe is the set of all NHL teams and S(x) =\x
is a team in the Northwest Division," then X = {Calgary Flames, Colorado
Avalanche, Edmonton Oilers, Minnesota Wild, Vancouver Canucks}. Note 1
that much like the \square" bracket as in [a;b], is used to denote the interval
of real numbers from a to b inclusive, the usage of the \curly" brackets (i.e.,
the pair {;}) in the description of a set is also by convention. Hence, it is
unconventional and rather meaningless to denote, for example, the set of odd
numbers from 1 to 5 as [1;3;5] just as it is incorrect to refer to the closed
interval from a to b, with a < b as {a;b}.
It is also important to note that the symbolic de▯nition of a set given by
X = {x ∶ S(x)} is merely a shortcut to the statement \the set X contains
the objects x for which the predicate S(x) is true." Since the predicate is
a description of characteristics explainable in words, the de▯nition of sets
could be equally de▯ned using words as we have in the above examples.
Additionally, since a set is de▯ned using predicates, the universe at hand
should be precisely de▯ned unless the context under which the predicate
appears makes it clear. For example, consider the set X = {x ∶ x = 4}. Under
normal circumstances, it is appropriate to think that X = {−2;2}. However,
if the universe is not the real numbers,R, (or integers, Z), but rather the set
of natural numbers, N, then X = {2}. Clearly, the objects belonging to a set
is precisely de▯ned relative to the universe concerned. For this reason, the
universe is precisely stated in the characterization of the set. For example,
if the universe is the set of real numbers, R, and we are characterizing the
objects x from the universe so that x > 3, we may write {x ∈ R ∶ x > 3} for
its de▯nition. This notation is read \the set of objects x from the set of real
numbers so that x is strictly greater than 3." Alternatively, it could also
be condensed further to read \the set of real numbers for which is strictly
greater than 3."
1Of course, one may be tempted to use the example S(x) =\x is the best team in the
NHL" in which case X = {Vancouver Canucks}. However, since the notion of best is rather
subjective, we will treat this example as merely a credible, yet hypothetical possibility.
2 Consider the set {x ∶ x ≠ x}. This is the collection of objects from the
universe so that the object x is not equal to the object x. On surface, this is a
rather bizarre statement but will have important usages later on. Since every
object from the universe, in principle, is equal to itself, the set {x ∶ x ≠ x}
contains no elements. For this reason, we refer to this set as the empty set
to literally imply a set containing no elements and denoted ∅ or sometimes
{}. Since the empty set is a set containing no elements, the statement x ∈ ∅
is false for every x from the universe. This will be a very important point to
remember for what follows.
Also note that for the simple reason that the notation ∅ refers to a very
speci▯c set and is written identically to the number 0 with a slash across it,
it is poor habit to use ∅ with the number 0 interchangeably. Readers are
strongly encouraged to abandon such poor habits from herein. Not only is it
misleading, but also incorrect usage of standard notation in mathematics.
Example 2.1 The”following are all examples of empty sets;
(i) {x ∈ R ∶ x = −1}
(ii) {x ∈ Z ∶ 2x + 2 = 7}
(iii) {x ∈ N ∶ x + 2 = −1}.
Let X and Y be two sets. The set X is said to be a subset of Y if and
only if for every element of X is also an element of Y . If X is a subset of Y ,
we write X ⊆ Y . Symbolically, we can therefore de▯ne a subset by:
X ⊆ Y ⇔ ƒx;x ∈ X ⇒ x ∈ Y
If the conditions for X to be a subset of Y is violated, that is, ∃x ∈ X
so that x ∉ Y , we say that X is not a subset of Y denoted symbolically as
X ⊈ Y .
Theorem 2.1 For every set X, (i) ∅ ⊆ X and (ii) X ⊆ X.
Proof: Take any set X. (i) By the de▯nition of a subset, we need to show
that x ∈ ∅ ⇒ x ∈ X. Since the antecedent of this statement (x ∈ ∅) is false,
this conditional statement is always true. Hence, ∅ ⊆ X. (ii) Here, we need
to show that x ∈ X ⇒ x ∈ X. For any proposition P (here, x ∈ X), P ⇒ P is
a tautology, hence, X ⊆ X. ∎
Consider two sets X and Y . We say that the set X is equal to the set Y ,
denoted X = Y , if and only if X ⊆ Y and Y ⊆ X. Clearly, if either conditions
3 Universe Universe
’$ ’▯▯
▯▯ xq
x
▯▯ ▯▯
&%Y &%Y
Figure 1: Venn diagrams.
required for the equality of two sets are not satis▯ed, the sets are said to
be not equal, denoted X ≠ Y . By Theorem 2.1, since the sets ∅ and X are
always subsets of a set X they are referred to as improper subsets of X. In
the case that for some set X, X ≠ Y , X ≠ ∅, and X ⊆ Y , we say that X is
2
a proper subsIt is convention to use the notation X ‘ Y if X is a
proper subset of Y .
A simple but useful visual tool when dealing with elementary relationships
between sets is a Venn diagram named after its inventor John Venn. For
example, in Figure 1, the left panel illustrates the case where X ⊈ Y . In
particular, the element x ∈ X but that x ∉ Y . Conversely, the right panel of
Figure 1 illustrates the case where X ⊆ Y .
Example 2.2 Suppose we have the sets A = {1;2;3;4;5;8}, B = {3;4;5},
and C = {8}. Then B ‘ A and C ‘ A.
Example 2.3 Let X = {x ∈ R ∶ 0 ≤ x ≤ 10} and Y = {x ∈ R ∶ 0 ≤ x ≤ 5}. Then
Y ‘ X. This follows since 5 < 10 and hence, if x ≤ 5, then x ≤ 10 (in fact,
x < 10). Therefore, if x ∈ Y , then x ≤ 5 (and hence x < 10) and x ≥ 0. In
other words, x ∈ X. Therefore, x ∈ Y ⇒ x ∈ X and so Y ‘ X.
Theorem 2.2 (Transitivity of ⊆) Let X, Y , and Z be sets. If X ⊆ Y and
Y ⊆ Z, then X ⊆ Z.
Proof: Suppose X ⊆ Y and Y ⊆ Z. It follows that for all x ∈ X, x ∈ Y . And
since Y ⊆ Z, if x ∈ Y then x ∈ Z. Since x∎∈ X implies that x ∈ Z, X ⊆ Z.
2
Note that it is possible to write X ≠ Y and X ≠ ∅ as simply X ∉ {Y;∅}. Here {Y;∅}
is the set containing the sets Y and the empty set.
3The de▯nition of transitivity is formally de▯ned in Section ??.
4 For any given set X, the collection of all subsets of X is referred to as
the power set of X denoted P(X). In other words, P(X) = {Y ∶ Y ⊆ X}.
It follows from Theorem 2.1 that ∅ ∈ P(X) and X ∈ P(X). It is perhaps
worth pointing out the somewhat obvious but often overlooked fact that the
power set of X contains sets as elements. That is, every element of P(X) is
a set itself. Hence, if x ∈ X, x ∉ P(X). Rather, {x} ∈ P(X) since {x} ⊆ X.
Clearly, the distinction to be made here is that x ∈ X whereas {x} ⊆ X.
Example 2.4 Suppose X = {1;2;3}. Then:
P(X) = {∅;X;{1;2};{1;3};{2;3};{1};{2;};{3}}
Example 2.5 Suppose X = {1;2;{3;4}}. Then:
P(X) = {∅;X;{1;2};{1;{3;4}};{2;{3;4}};{1};{2};{{3;4}}}
Note that in Example 2.5, the element {{3;4}} in the power set of X is
a set containing as an element, the set {3;4}. Hence, {3;4} ∉ P(X) whereas
{{3;4}} ∈ P(X). This follows since {3;4} ⊈ X rather {3;4} ∈ X.
Theorem 2.3 Let X and Y be sets. X ⊆ Y if and only if P(X) ⊆ P(Y ).
Proof: Note that since this is a biconditional statement we need to prove
the two statements (i) if X ⊆ Y then P(X) ⊆ P(Y ), and (ii) if P(X) ⊆ P(Y )
then X ⊆ Y .
(i) Suppose X ⊆ Y and Z ∈ P(X). Since Z ∈ P(X), this implies that
Z ⊆ X. By Theorem 2.2, we have Z ⊆ Y . Hence, Z ∈ P(Y ). Therefore,
P(X) ⊆ P(Y ).
(ii) Suppose P(X) ⊆ P(Y ). It follows from Theorem 2.1 that X ⊆ X and
hence X ∈ P(X). Since P(X) ⊆ P(Y ), we have X ∈ P(Y ). By de▯nition,
this implies that X ⊆ Y . ∎
3 Operations on Sets
Here, we discuss the most elementary operations on sets. For simplicity in
exposition su▯cient for the purpose of introduction, we will only be concerned
with operations between two sets. The extension to include operations over
multiple sets will be discussed in Section 4. An operation between two objects
5 is referred to as a binary operation. The fundamental binary operations on
sets consists of the intersection and the union.
The intersection of two sets X and Y is the set of elements which belong
to both X and Y denoted X ∩ Y (read \X intersect Y "). Symbolically, the
intersection is de▯ned as X ∩ Y = {x ∶ x ∈ X ∧ x ∈ Y }. Intuitively, the inter-
section comprises of the following; an element x belongs to the intersection
of sets X and Y (i.e., x ∈ X ∩ Y ) if and only if x belongs to X (i.e., x ∈ X)
and x belongs to Y (i.e., x ∈ Y ). For any two sets X and Y , if X ∩ Y = ∅,
then X and Y are said to be disjoint.
Example 3.1 Let X and Y be two sets.
(i) If X = {1;2;3} and Y = {2;3;4}, then X ∩ Y = {2;3} since both 2 and
3 are elements common to both X and Y .
(ii) If X = {1;2;3} and Y = {4;5;6}, then X ∩ Y = ∅. This follows
since there are no common elements between X and Y . Hence, X and Y are
disjoint.
Theorem 3.1 Let X, Y , and Z be sets. We have; (i) (Commutativity)
X∩Y = Y ∩X, (ii) (Associativity) (X∩Y )∩Z = X∩(Y ∩Z), (iii) X∩Y = X
if and only if X ⊆ Y , and (iv) ƒX, X ∩ ∅ = ∅.
The proof of these properties regarding the intersection operation are
obvious and hence omitted. All readers, to this point, should be able to
construct such proofs without aid.
The union of two sets X and Y is the set of all elements which belong to
X or Y (or both) denoted X ∪ Y (read \X union Y "). The union may be
represented symbolically as X∪Y = {x ∶ x ∈ X∨x ∈ Y }. In words, The union of
the sets X and Y consists of every element that either belongs to X, or to Y .
Using Example 3.1, if X = {1;2;3} and Y = {2;3;4} then X ∪Y
