1. Preliminaries
1. Set operations
A set is a collection of some items such as outcomes of an experiment.
We denote sets using upper case letters, say A and write a ∈ A if a is an element belonging to A.
If A and B are two sets, then the notation A ⊆ B means that the set A is included in B , i.e. each element of A is also an element of B :
A⊆B

iff [∀a ∈ A : a ∈ B ]

If A ⊆ B and A = B then we say that the set A forms a proper subset of B and write A ⊂ B .

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

1 / 49

In what follows all sets will be subsets of a larger set Ω. The complement of A in Ω is denoted by Ac and represents elements of Ω which do not belong to A:
Ac = { ω ∈ Ω : ω ∈ A}
/
The complement of the set Ω is given by the empty set ∅.

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

2 / 49

For any sets A ⊆ Ω, B ⊆ Ω, we denote by A ∪ B and A ∩ B their union and intersection. The union represents points which belong to A or B :
A ∪ B = {ω ∈ Ω : ω ∈ A or ω ∈ B } while intersection corresponds to points which belong to both sets
A ∩ B = {ω ∈ Ω : ω ∈ A and ω ∈ B }
If A and B are disjoint sets, i.e. A ∩ B = ∅, then their union will be denoted by A + B . Finally, the difference and the symmetric difference are defined as
B − A = B ∩ Ac = {ω : ω ∈ B and ω ∈ A} − difference
/
A∆B = (A − B ) ∪ (B − A) − symmetric difference

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

3 / 49

The operations of union and intersection are governed by certain laws.
They are given by
(i) identity laws:
A∪∅ = A

and

A∩Ω = A

(ii) domination laws:
A∪Ω=Ω

and

A∩∅=∅

A∪A = A

and

A∩A=A

A∪B =B∪A

and

A∩B =B∩A

(iii) idempotent laws

(iv) commutative laws:

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

4 / 49

(v) associative laws:
A ∪ (B ∪ C ) = (A ∪ B ) ∪ C

and

A ∩ (B ∩ C ) = (A ∩ B ) ∩ C
(vi) distributive laws:
A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )

and

A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C )
(vii) absorption laws
(A ∩ B ) ∪ B = B

Dorota M. Dabrowska (UCLA)

and

Biostatistics 255

A ∩ (A ∪ B ) = A

September 21, 2011

5 / 49

Lastly, complementation is governed by
(viii) De Morgan laws: if A ⊆ B

then

(A ∩ B )c = Ac ∪ B c

Dorota M. Dabrowska (UCLA)

Biostatistics 255

B c ⊆ Ac and (A ∪ B )c = Ac ∩ B c

September 21, 2011

6 / 49

The operations of union and intersections are also defined for arbitrary families of sets. Let T be an arbitrary index set, and suppose that At ⊆ Ω for each t ∈ T . Then
At = {ω ∈ Ω : ∃ t ∈ T ω ∈ At } t ∈T

At = {ω ∈ Ω : ∀ t ∈ T ω ∈ At } t ∈T

We have
(i)

t ∈T

At ⊆ At0 ⊆

t ∈T

At

for all

t0 ∈ T

(ii) if At ⊆ Bt for all t ∈ T then
At ⊆ t ∈T

Dorota M. Dabrowska (UCLA)

Bt

At ⊆

and

t ∈T

Biostatistics 255

t ∈T

Bt t ∈T

September 21, 2011

7 / 49

(ii) De Morgan laws
At ]c =

[ t ∈T

Ac t and

t ∈T

[

At ]c =

t ∈T

Ac t t ∈T

(iv) associativity laws:
At ∪ t ∈T

[At ∪ Bt ] and

Bt = t ∈T

Dorota M. Dabrowska (UCLA)

t ∈T

At ∩ t ∈T

Biostatistics 255

[At ∩ Bt ]

Bt = t ∈T

t ∈T

September 21, 2011

8 / 49

Cartesian products
If Ω and Ω′ are two sets then their Cartesian product Ω × Ω′ represents the collection of ordered pairs (ω, ω ′ ) such that ω ∈ Ω and ω ′ ∈ Ω′ . More generally, if A ⊆ Ω and B ⊆ Ω′ then
A × B = {(ω, ω ′ ) : ω ∈ A

Dorota M. Dabrowska (UCLA)

Biostatistics 255

and

ω′ ∈ B}

September 21, 2011

9 / 49

We have
A × B = ∅ iff

A=∅

or B = ∅

(A1 ∩ A2 ) × (B1 ∩ B2 ) = A1 × B1 ∩ A2 × B2
[A × B ]c = Ac × Ω2 ∪ Ω1 × B c
A × (B1 − B2 ) = A × B1 − A × B2
(A1 − A2 ) × B = A1 × B − A2 × B

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

10 / 49

A×

A × Bt

Bt = t ∈T

A×

t ∈T

A × Bt

Bt = t ∈T

t ∈T

At × B = t ∈T

At × B t ∈T

At × B = t ∈T

At × B t ∈T

Finally if A1 ⊆ A2

and

B1 ⊆ B2

then

A1 × B1 ⊆ A2 × B2

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

11 / 49

2. Extended real line
The extended real line, denoted by R , consists of all real numbers with added ∞ and −∞.
The addition and multiplication of finite reals is defined in the usual way.
We also make the following conventions. For any finite real a

(i )

a+∞=∞+∞=∞ a − ∞ = (−∞) − ∞ = −(∞) + (−∞) = −∞ − (−∞) = ∞

(ii )

if

a > 0 then

a · ∞ = ∞ · ∞ = (−∞) · (−∞) = (−a)(−∞) = ∞ a · (−∞) = (−∞) · ∞ = ∞(−∞) = (−a)∞ = −∞
(iii )

0 · ∞ = 0 = 0 · (−∞)

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

12 / 49

(iv )

a a =
=0
∞
−∞

The remaining operations (such as ∞ − ∞ or

Dorota M. Dabrowska (UCLA)

Biostatistics 255

∞
∞)

are undefined.

September 21, 2011

13 / 49

If A is a subset of reals then the least upper bound of A is denoted by sup A and is defined as the smallest extended real number a such that x ≤ a for all x ∈ A. Thus
∀x ∈ A : x ≤ a if [∀x ∈ A : x ≤ b ] then

a≤b

Similarly, the greatest lower bound of A is denoted by inf A and it represents the largest number c such that c ≤ x for all x ∈ A. Thus
∀x ∈ A : c ≤ x if Dorota M. Dabrowska (UCLA)

[∀x ∈ A : b ≤ x ] then

Biostatistics 255

b≤c

September 21, 2011

14 / 49

If A represents a sequence of numbers A = {xn : n ≥ 1} then we write sup A = supn xn and inf A = infn xn . We further define the upper and the lower limits of the sequence {xn : n ≥ 1} by setting lim inf = sup inf xn n k

n ≥k

lim sup = inf sup xn n k n ≥k

By definition
−∞ ≤ lim inf xn ≤ lim sup xn ≤ ∞ n n

If lim infn xn = lim supn xn then the common value is denoted by lim xn and we say that the sequence {xn : n ≥ 1} has a limit. In particular, if
{xn : n ≥ 1} is monotone then its limit exists (in the extended real line).

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

15 / 49

We further note that the sequence bk = inf xn n ≥k

is increasing. Therefore its limit exists and is equal to supk bk . Thus lim inf xn = lim ( inf xn ). n k →∞ n≥k

Similarly, ck = supn≥k xn forms a decreasing sequence so it has a limit equal to infk ck and we have lim sup xn = lim sup xn . n Dorota M. Dabrowska (UCLA)

k →∞ n≥k

Biostatistics 255

September 21, 2011

16 / 49

3. Sequences of sets For any A ⊆ Ω, its indicator function is
1A (ω ) = 1 if

ω∈A

= 0 if

ω∈A

We have
1A∪B = max{1A , 1B }
1A∩B = min{1A , 1B } = 1A 1B
1Ac

= 1 − 1A

1A∆B = |1A − 1B |

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

17 / 49

Similarly, if A1 , ...., An , ..... is a sequence of subsets of Ω then
∞

ω∈

An

iff

n ≥1

n ≥1
∞

ω∈

An

iff

n ≥1

Dorota M. Dabrowska (UCLA)

sup 1An (ω ) = 1

Biostatistics 255

inf 1An (ω ) = 1

n ≥1

September 21, 2011

18 / 49

We can use this correspondence to define limit superior and limit inferior of a sequence of sets.
Definition Let {An : n ≥ 1} and A be subsets of Ω.
(a) The set
∞

∞

lim sup An = n An k =1 n =k

is the limit superior of the sequence {An : n ≥ 1} In other words, ω ∈ An for infinitely many values of n. We write lim supn An = {An i .o .} and we say that An occurs infinitely often.

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

19 / 49

(b) The set
∞

∞

lim inf An = n An k =1 n =k

is the limit inferior of the sequence {An : n ≥ 1}. In this case ω belongs to An for all but finitely many values of n. We shall often denote this set as lim infn An = {An ev .} and we say that An occurs eventually. (c) The sequence {An : n ≥ 1} converges to A if lim sup An = lim inf An = A n n

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

20 / 49

In terms of characteristic functions
B = lim sup An

iff

1B = lim sup 1An

C = lim inf An

iff

1C = lim inf 1An

n

n

n

n

This implies in particular, lim inf An ⊆ lim sup An n n

We can also verify this directly. For any k ≥ 1 set
Ck =

An

and

Bk =

n ≥k

An n ≥k

We have
Ck ⊆ Ak ⊆ Bk
Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

21 / 49

for all k . If ω ∈ Ck for some k , then k ω∈

Bi i =1

because B1 ⊇ B2 ⊇ . . . is a decreasing sequence. Moreover,
C1 ⊆ C2 . . . ⊆ ... is an increasing sequence so that ω ∈ Ck implies ω ∈ Bi for all i ≥ k .

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

22 / 49

For handling increasing and decreasing sequences of sets, we have the following proposition, paralleling properties of monotone sequence of numbers. Proposition Let A1 , A2 , . . . be subsets of Ω. Then
(a) If A1 ⊆ A2 . . . is an increasing family of sets then
An → A = ∞ 1 An . (this is denoted by An ↑ A). n= (b) If A1 ⊇ A2 . . . is a decreasing family of sets then
An → A = ∞ 1 An . (this is denoted by An ↓ A). n= Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

23 / 49

Proof Let A =

∞ n =1 A n .

a) Since A1 ⊆ A2 ⊆ ...., we have
∞

∞

An = Ak

An = A and n =k

n =k

Therefore
∞

A=A

lim sup An = n k =1
∞

lim inf An = n Ak = A k =1

Part (b) follows by complementation.

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

24 / 49

Disjointification trick
Let A1 , ...An , .... be an arbitrary sequence of sets, An ⊆ Ω. Then
∞

∞

An = n =1

Bn

(1.1)

n =1

for sets n −1

Bn = An −

Ai , B1 = A1 i =1

We have
(a) Bn ∩ Bm = ∅ if n = m;
(b)

k n =1 A n

=

Dorota M. Dabrowska (UCLA)

k n =1 B n

for any k ≥ 1

Biostatistics 255

September 21, 2011

25 / 49

Then (b) implies (1.1) because k k

An =

Ck =

Bn n =1

n =1

is an increasing sequence of sets
C1 ⊆ C2 ⊆ ....Cn ⊆ .... and the union is equal to
∞

∞

Bi = C

Ai = i =1

Dorota M. Dabrowska (UCLA)

i =1

Biostatistics 255

September 21, 2011

26 / 49

4. Metric spaces
Definition If X is a set and d : X × X → R+ is a function satisfying
(i) d (x , y ) = d (y , x );
(ii) d (x , z ) ≤ d (x , y ) + d (y , z ) (triangle inequality);
(iii) d (x , x ) = 0. then d is called a semi-metric. If (iii) is replaced by
(iii’) d (x , y ) = 0 iff x = y then d is called a metric. The pair (X , d ) is correspondingly referred to as a semi-metric or metric space.
Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

27 / 49

The diameter of a set A of metric space X is defined diam (A) = sup{d (x , y ) : x ∈ A, y ∈ A}

An open ball centered at x ∈ X and having radius ε is the set of points y ∈ X whose distance from X is less than ε
B (x , ε) = {y ∈ X : d (x , y ) < ε}

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

28 / 49

A subset K is bounded if there exists a ball B (of a finite radius) such that
K ⊂ B.
A subset K is totally bounded if for every ε > 0 it can be covered by finitely many balls of radius ε.
Every totally bounded set is bounded, however, a bounded set need not be totally bounded.

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

29 / 49

Example Let X be an arbitrary set and define d (x , y ) = 1 x = y
= 0 x =y
Then d is a metric, usually referred to as the discrete metric. A ball centered at x ∈ X is
B (x , ε) = {x }
=X

if ε ≤ 1 if ε > 1

Thus X is bounded. However, if X is infinite, then it cannot be covered by means of a finite number of balls of radius ε ≤ 1.

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

30 / 49

Example
Let X = R be equipped with the usual metric d (x , y ) = |x − y |.
Then each ball is of the form (x − ε, x + ε), ε > 0.
The set of reals is unbounded hence not totally bounded.
On the other hand, finite intervals [a, b ] or (a, b ), −∞ < a < b < ∞ are both bounded and totally bounded.

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

31 / 49

We say that a sequence of points {xn : n ≥ 1} ⊆ X converges to x , x ∈ X if d (xn , x ) → 0. We write in this case xn → x or lim xn = x . Thus a sequence {xn } converges to x iff every ball centered at x contains all but a finite number of terms of the sequence {xn }.

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

32 / 49

Every convergent sequence is bounded and totally bounded.
In addition, any convergent sequence of a metric space satisfies the
Cauchy condition, i.e. for every ε > 0 there exists N = N (ε) such that d (xn , xm ) < ε for all n, m ≥ N .
A metric space is called complete if the converse holds as well,
i.e. every Cauchy sequence has a limit in X .

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

33 / 49

Example This definition of convergence coincides with the usual definition of convergence of sequences of real numbers in X = R with metric d (x , y ) = |x − y |. Every Cauchy sequence of reals forms a convergent sequence, therefore X = R is a complete metric space with respect to d . However, if we take X = (−1, 1) with the same metric, then the sequence {1 − 1/n : n ≥ 2} satisfies the Cauchy condition but has no limit in X so that (X , d ) is not complete.

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

34 / 49

A common example of metric spaces is provided by vector spaces V equipped with a norm.
Definition Let V be a vector space. A function · : V → R+ satisfying

(i) x + y ≤ x + y (triangle inequality);
(ii) αx = |α| x for any scalar α
(iii) if x = 0 then x = 0 is called a semi-norm. If instead of (iii), the function · satisfies
(iii’)

x =0

iff x = 0

then · is called a norm. The pair (V , · ) is called a semi-normed or a normed space, respectively.
Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

35 / 49

A norm · induces a metric on the vector space V . For any x , y ∈ V we define it as d (x , y ) = x − y
If the resulting metric space is complete then the pair (V , · ) is called a
Banach space.
Example In the case of X = R k , we can choose for example norms k k

x

1

|xi |

= i =1

x

2

xi2

= i =1

x

∞

= max |xi | i =1,...,k

Here · 1 corresponds to the ℓ1 norm, · 2 corresponds to the Euclidean norm and · ∞ to the maximal norm. For each if these choices, the induced metric d (x , y ) turns R k into a complete metric space.

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

36 / 49

Note that the three norms satisfy x ∞ ≤ x 1, x 2≤k x
1
x 1≤ x 2≤k x 1 k ∞

so that they can be viewed as equivalent. More generally, if ·
·

2

1

and

are two norms in a vector space V then we call them equivalent if

there exist constants a > 0, b > 0 such that x 1

≤a x

2

x

2

≤b x

1

for any x ∈ V .

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

37 / 49

5. Topological spaces
A topological space is a set X equipped with an operation of closure or the operation of interior.
The closure operation assigns to an arbitrary subset A ⊆ X a set A ⊆ X such that
(F-i) ∅ = ∅
(F-ii) A ⊆ A
(F-iii) A = A
(F-iv) A ∪ B = A ∪ B
The set A is called closed if A = A.
Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

38 / 49

From this definition it follows that a finite union of closed sets is also closed. Moreover,
(i) if A ⊆ B then A ⊆ B
(ii) A − B ⊆ A − B
(iii) if {At : t ∈ T } is an arbitrary collection of subsets of X then
At ⊆ t ∈T

At ⊆ t ∈T

At ⊆ t ∈T

At t ∈T

(iv) X = X

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

39 / 49

If F is the collection of closed sets in X then the preceding implies
(F’-i) ∅ ∈ F , X ∈ F
(F’-ii) intersection of an arbitrary number of closed sets is also closed
(F’-iii) union of a finite number of closed sets is closed.
In particular, if A ⊂ X then its closure A is the smallest closed set containing A: we have
A=

Dorota M. Dabrowska (UCLA)

{F ∈ F : A ⊂ F }

Biostatistics 255

September 21, 2011

40 / 49

A set A is called open if its complement Ac = X − A is closed. If we denote by G the collection of all open sets in X then
(G’-i) ∅ ∈ G , X ∈ G
(G’-ii) union of an arbitrary number of open sets is also open
(G’-iii) intersection of a finite number of open sets is open.
If A ⊂ X then its interior int A is the largest open set contained in A: we have int A = {G ∈ G : G ⊂ A}
A point x is in the interior of A iff there exists and open set G such that x ∈G

and

G ∩ (X − A) = ∅

Moreover, int A = X − (X − A)
Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

41 / 49

Alternatively, the interior operation assigns to every set A of X a subset such that
(G-i) int X = X
(G-ii) int A ⊆ A
(G-iii) int int A = int A
(G-iv) int A ∩ B = int A ∩ int B
The set A is called open if A = int A. Its closure is given by
A = X − int (X − A).

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

42 / 49

The boundary of a set A is defined as δA = A − int A
The boundary is a closed set and contains points of both A and its complement. Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

43 / 49

In many circumstances, the topology of a space can be defined by specifying its base. A family B of open subsets of X is called a base, if every open set of X is a union of some sets belonging to B .
A base always exists because we can take it equal to G .
However, the base can be often chosen as a smaller collection of open sets.

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

44 / 49

We can now specialize these concepts to metric spaces. If X is a metric space with metric d , then we can define closure of a set A as the collection of points which are limits of sequences contained in A:
A = {x ∈ X : x = lim xn

for some sequence

{xn }∞ 1 ⊆ A}. n= Theorem
(i) We have x ∈ A x ∈B

iff B ∩ A = ∅ for every open ball B such that

(ii) A set is open iff it is a union of some open balls.

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

45 / 49

Separable topological and metric spaces
A set A in a topological space X is called dense if A = X . Alternatively, a set A is dense iff every nonempty open set of X contains points of A.
A topological space is called separable if it has a countable dense set.
In particular, every X with a countable base is separable.
In the case of metric spaces, these two concepts are equivalent.
Separability of a metric space is also equivalent to the assumption that each discrete subspace is at most countable.

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

46 / 49

Example
If X = R with its usual metric d (x , y ) = |x − y | then the set of rationals is dense in R . The countable base of X corresponds to all balls centered at rationals and having a rational radius. The set of irrational numbers,
IR = R − Q is also dense in R because every ball B (x , ε) contains irrational numbers.

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

47 / 49

Example Bounded functions.
If I is an arbitrary set, then ℓ∞ (I ) is the space of all real valued bounded functions x : I → R endowed with supremum norm x ∞

= sup |x (t )| t ∈I

This is a Banach space. It is separable iff I is finite. If I is a finite set then the collection of all scalar functions assuming rational values is a countable dense set of ℓ∞ (I ). On the other hand if I is infinite, then characteristic functions 1A of sets A ⊂ I form an uncountable collection of functions satisfying 1A − 1B ∞ = 1. Therefore, the corresponding
ℓ∞ (I ) space is non-separable.

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

48 / 49

Example
The space C = C ([0, 1]k ) of real valued continuous functions on [0, 1]d equipped with uniform metric x −y

∞

= sup |x (t ) − y (t )| t ∈[0,1]k

is separable and complete.
In particular, for k = 1, the collection of piecewise linear functions with
“kinks” located at rational points form a countable dense set in C ([0, 1]).
For k > 1, the separant can be chosen in a similar fashion.

Dorota M. Dabrowska (UCLA)

Biostatistics 255

September 21, 2011

49 / 49