Mathematics for Statistics
Set Theory
Ruzzel D. Ragas
UP School of Statistics
Ruzzel D. Ragas Basic Concepts
Introduction
Starting from the theory of sets, one can construct all the number systems, functions,
calculus, and other areas of mathematics. Thus, the study of sets is the foundation for
the entire structure of mathematics.
This chapter does not develop these constructions but does provide some set-theoretic
concepts used throughout the text and advanced mathematics.
To designate a set, we use the notation {x : P(x)}, where P(x) is an open sentence
description of the property that defines the set.
Example and Notation:
aZ = {ax : x ∈ Z} = integer multiples of a.
Caution:
Not all P(x) can be used to define a set. (Let A = {x : x ∈
/ x}. Is A ∈ A?)
The universe of discourse must be known or understood from context.
Ruzzel D. Ragas Basic Concepts
Definitions
Definition
Let ∅ = {x : x 6= x}. Then ∅ is a set, called the empty set or null set.
It is an axiom that ∅ is a set.
The statement x ∈ ∅ is false for any element in the universe.
There are no elements in the set ∅.
We could define other empty collections, but we will soon prove that all such
collections are equal, so there really is just one empty set.
Definition
Let A and B be sets.
A ⊆ B iff (∀x)(x ∈ A → x ∈ B).
A = B iff (∀x)(x ∈ A ↔ x ∈ B).
Ruzzel D. Ragas Basic Concepts
Proving A ⊆ B and A = B
Direct Proof of A ⊆ B
Let x be any element in the universe.
Suppose x ∈ A.
..
. (statements allowed in a proof.)
Thus, x ∈ B.
Therefore, A ⊆ B.
Two Part Proof of A = B
Prove that A ⊆ B (using any method).
Prove that B ⊆ A (using any method).
Therefore, A = B.
Ruzzel D. Ragas Basic Concepts
Example 1
Example: Let a, b ∈ N, Prove that if a divides b, then bZ ⊆ aZ.
Proof.
We begin by proving this directly. Let a, b ∈ N. Suppose a divides b.
⇒ b = ak, ∃k ∈ Z. (Why?)
Now we begin the proof for bZ ⊆ aZ.
Let x ∈ bZ
⇒ x = bm, ∃m ∈ Z. (Why?)
⇒ x = (ak)m = a(km), ∃km ∈ Z. (Why?)
⇒ x ∈ aZ. (Why?)
Ruzzel D. Ragas Basic Concepts
Example 2
Example: Let A = {x ∈ R : x 2 − 1 = 0} and B = {−1, 1}. Prove that A = B.
Proof.
(Proof that A ⊆ B.)
Suppose z ∈ A.
⇒ z is a solution to x 2 − 1 = 0.
⇒ z 2 − 1 = 0 → (z + 1)(z − 1) = 0.
⇒ z + 1 = 0 → z = −1 or z − 1 = 0 → z = 1. ((z + 1)(z − 1) = 0. Theorem 2.7.6)
⇒ z ∈ B.
(Proof that B ⊆ A.)
Suppose z ∈ B.
⇒ z = −1 or z = 1.
⇒ ((−1)2 − 1 = 0 and (1)2 − 1 = 0) → z is a solution to x 2 − 1 = 0.
⇒ z ∈ A.
Ruzzel D. Ragas Basic Concepts
Some Results
Theorem 3.0.1
Let A, B, C be sets.
1 ∅ ⊆ A.
2 A ⊆ A.
3 If A ⊆ B and B ⊆ C , then A ⊆ C .
Proof.
(Proof of 1:) Observe that x ∈ ∅ → x ∈ A true for any A since the antecedent is false.
(Proof of 2:) Since P → P is a tautology, then x ∈ A → x ∈ A is true for any A.
(Proof of 3:) Suppose A ⊆ B and B ⊆ C , then x ∈ A → x ∈ B and x ∈ B → x ∈ C .
By Hypothetical Syllogism, x ∈ A → x ∈ C .
Ruzzel D. Ragas Basic Concepts
Some Results
Theorem 3.0.2
If A and B are sets with no elements, then A = B.
Proof.
Since A has no elements, x ∈ A is false for any x. Thus, (∀x) (x ∈ A → x ∈ B) is
true. Therefore A ⊆ B. Similar argument will yield B ⊆ A. ∴ A = B.
Theorem 3.0.3
If A ⊆ B and A =
6 ∅, then B 6= ∅.
Proof.
Since A 6= ∅, ∃x ∈ A. Since A ⊆ B, then x ∈ A → x ∈ B. Let t ∈ A, then t ∈ B.
Thus, ∃x ∈ B. ∴ B 6= ∅.
Ruzzel D. Ragas Basic Concepts
Power Set of A
It is an axiom in set theory that for a given set A, the collection of all its subset is also
a set. (Note that the elements of this set are also sets.)
Definition
Let A be a set. The power set of A is the set whose elements are the subsets of A and
is denoted by P(A); i.e. P(A) = {B : B ⊆ A}.
When we work with sets whose elements are sets, it is important to recognize the
distinction between “is an element of” and “is a subset of.” To use A ∈ B correctly, we
must consider whether the object A (which happens to be a set) is an element of the
set B, whereas A ⊆ B requires determining whether all objects in the set A are also in
B. If x ∈ A and A ⊆ B, the correct terminology is that A contains x and B includes A.
Example: Let A = {1, 2, 3, 4}
P(A) = {∅, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4},
{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4} = A}
Ruzzel D. Ragas Basic Concepts
Element vs. Subset
Let X = {{a, b, z}, {1, 2}, 3}.
P(X ) = {∅, {{a, b, z}}, {{1, 2}}, {3}, {{a, b, z}, {1, 2}}, {{a, b, z}, 3}, {{1, 2}, 3}, X }
Exercises: (True or False)
1 a ∈ X. 10 {3} ⊆ P(X ). 19 {{1, 2}, 3} ∈ P(X ).
2 3 ∈ X. 11 {a, b, z} ⊆ X . 20 ∅ ∈ P(X ).
3 {a, b, z} ∈ X . 12 {{a, b, z}} ⊆ X . 21 ∅ ⊆ P(X ).
4 {1} ∈ {1, 2}. 13 {a, b, z} ⊆ P(X ). 22 {∅} ∈ P(X ).
5 {1} ⊆ {1, 2}. 14 {{a, b, z}} ⊆ P(X ). 23 {∅} ⊆ P(X ).
6 {3} ⊆ X . 15 {1, 2} ∈ P(X ). 24 {{{a, b, z}}} ∈ P(X ).
7 {3} ∈ X . 16 {{1, 2}} ∈ P(X ). 25 {{{a, b, z}}} ⊆ P(X ).
8 {1, 2} ⊆ X . 17 X ∈ P(X ). 26 {{{a, b, z}}} ∈ P(P(X )).
9 {3} ∈ P(X ). 18 X ⊆ P(X ). 27 {{{a, b, z}}} ⊆ P(P(X )).
Ruzzel D. Ragas Basic Concepts
Theorem about Power Sets
Theorem 3.0.4
Let A and B be sets. A ⊆ B iff P(A) ⊆ P(B).
Proof.
⇒) Suppose A ⊆ B.
Let x ∈ P(A).
⇒ x ⊆ A. (Why?)
⇒ x ⊆ B. (Why? Theorem 3.0.1)
⇒ x ∈ P(B). (Why?)
∴ P(A) ⊆ P(B)
⇐) Suppose P(A) ⊆ P(B).
⇒ A ∈ P(A). (Why? Theorem 3.0.1)
⇒ A ∈ P(B). (Why?)
⇒ A ⊆ B. (Why?)
Ruzzel D. Ragas Basic Concepts