Pontificia Universidad Católica de Chile

Estudiante: Sebastián Bahamondes Naranjo (sbahamondes@uc.cl)

Profesor: Godofredo Iommi

Demostraciones y resumen: Análisis Real

1 Set Theory
Theorem 1.1. Let A,B and C be any sets. Then. the following identities hold true:

(i) A ∪ B = B ∪ A, A∩B =B∩A

(ii) A ∪ (B ∪ C) = (A ∪ B) ∪ C, A ∩ (B ∩ C) = (A ∩ B) ∩ C
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
(iii)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

Proof. We shall prove the validity of identity number (iii). Let x be any element of the set A ∪ (B ∩ C).
This means:

x ∈ A ∪ (B ∩ C) ⇒ x ∈ A ∨ x ∈ B ∩ C

If x ∈ B ∩ C, then we can see than, since B ⊂ A ∪ B ∧ C ⊂ A ∪ C, then B ∩ C ⊂ (A ∪ B) ∩ (A ∪ C), and

therefore x ∈ (A ∪ B) ∩ (A ∪ C). Now, if x ∈ A, then again we see that A ⊂ (A ∪ B) ∩ (A ∪ C), and so
x ∈ A ⊂ (A ∪ B) ∩ (A ∪ C) once again. This means that A ∪ (B ∩ C) ⊂ (A ∪ B) ∩ (A ∪ C).
Now, let x ∈ (A ∪ B) ∩ (A ∪ C). It follows that x ∈ A ∪ B and x ∈ A ∪ C. If x ∈ A, then both conditions
are satisfied, since x ∈ A ∪ B and x ∈ A ∪ C. If x ∈ B, then the first condition is satisfied (x ∈ A ∪ B). The
second condition will only be true if x ∈ B ∩ C, since we have already ruled out the case in which x ∈ A.
Therefore, x ∈ (A ∪ B) ∩ (A ∪ C) ⇒ x ∈ A ∨ x ∈ B ∩ C. That is, x ∈ A ∪ (B ∩ C).
Theorem 1.2. For any collection C of subsets of a set X,
!c !c
[ \ \ [
A = Ac , and A = Ac
A∈C A∈C A∈C A∈C

S
c
Proof. We shall proof the first of these identities. First, let x ∈ A∈C A . Then, we have:
!c
[ \
x∈ A ⇒ ∀A ∈ C, x ∈ X − A ⇒ ∀A ∈ C, x ∈ Ac ⇒ x ∈ Ac
A∈C A∈C

c
Ac . Now, let x ∈ A∈C Ac . This means:
S T T
Then, we have A∈C A ⊂ A∈C
\
x∈ Ac ⇒ ∀A ∈ C, x ∈ Ac
A∈C

A. However, since x ∈ A∈C Ac , this means that x ∈ X, given

S T
This means that ∀A ∈ C, x ∈
/A⇒x∈ /
S A∈C S
c
that ∀A ∈ C, A ⊂ X. Therefore, x ∈
/ A∈C A ∧ x ∈ X ⇒ x ∈ A∈C A .

c
c
This shows that A∈C Ac ⊂ c
T S T S
A∈C A , and allows us to conclude that A∈C A = A∈C A .

1
1.1 Excercises
(1) Prove that

(B ∪ C) ∩ (C ∪ A) ∩ (A ∪ B) = (B ∩ C) ∪ (C ∩ A) ∪ (A ∩ B)

Solution: First, let x ∈ (B ∪ C) ∩ (C ∪ A) ∩ (A ∪ B). This means that:

x ∈ (B ∪ C) ∩ (C ∪ A) ∩ (A ∪ B) ⇒ x ∈ (B ∪ C) ∧ x ∈ (C ∪ A) ∧ x ∈ (A ∪ B)

If x ∈ A − A ∩ C, then x ∈ B ∩ A. Analogously, if x ∈ B − B ∩ C, then x ∈ A ∩ B, and if

x ∈ A − A ∩ B, then x ∈ A ∩ C. We can see, besides, that of x ∈ A ∩ C or x ∈ B ∩ A or x ∈ B ∩ C (i.e,
x ∈ (B ∩ C) ∪ (C ∩ A) ∪ (A ∩ B)), then it is easily shown that x ∈ (B ∪ C) ∩ (C ∪ A) ∩ (A ∪ B). This,
alongside the previous conclusions, prooves that (B ∪C)∩(C ∪A)∩(A∪B) ⊂ (B ∩C)∪(C ∩A)∪(A∩B),
resulting in the two necessary inclusions.
(2) The symmetric difference A 4 B of the sets A, B is defined as the set of elements in A, or in B, but
not both. Show that:

A 4 B = (A − B) ∪ (B − A) = (A ∪ B) − (A ∩ B) = (A ∪ B) ∩ (Ac ∪ B c )

Solution: First, we see that x ∈ A 4 B ⇔ (x ∈ A ∨ x ∈ B) ∧ x ∈

/ A ∩ B. This means that x ∈ A ∪ B,
however, x ∈
/ A ∩ B. Therefore, x ∈ A ∪ B − A ∩ B. This means that A 4 B ⊂ A ∪ B − A ∩ B. It is
easily shown that A ∪ B − A ∩ B ⊂ A 4 B, and so A ∪ B − A ∩ B = A 4 B.
Now, let x ∈ (A − B) ∪ (B − A). Then, x ∈ A − B ∨ x ∈ B − A. If x ∈ A − B, then x ∈ A ∧ x ∈
/B⇒x∈
A 4 B. If x ∈ B − A, then x ∈ B ∧ x ∈
/ A ⇒ x ∈ A 4 B. Therefore, (A − B) ∪ (B − A) ⊂ A 4 B. Now, if
x ∈ A4B, then (x ∈ A∨x ∈ B)∧x ∈ / A∩B. If x ∈ A, then we have that x ∈ A∧x ∈ / A∩B ⇒ x ∈ A−B,
and therefore, x ∈ (A − B) ∪ (B − A). Now, of x ∈ B, then again x ∈ B ∧ x ∈ / A ∩ B ⇒ x ∈ B − A,
and therefore, x ∈ (A − B) ∪ (B − A).
This proves that A4B ⊂ (A−B)∪(B −A), and allows us to conclude that A4B = (A−B)∪(B −A).
Finally, let us assume A and B to be subsets of a greater set X. According to theorem 1.2, we now
that Ac ∪ B c = (A ∩ B)c , thereforem (A ∪ B) ∩ (Ac ∪ B c ) = (A ∪ B) ∩ (A ∩ B)c = F. Let x ∈ F.
Then x ∈ A ∪ B ∧ x ∈ (A ∩ B)c . The second conditions guarantees that x ∈/ A ∩ B. However, the first
conditions gives us thta x ∈ A ∨ x ∈ B. Therefore, (x ∈ A ∨ x ∈ B) ∧ x ∈
/ A ∩ B ⇒ x ∈ A 4 B.
Now, if we assume that x ∈ A 4 B, then (x ∈ A ∨ x ∈ B) ∧ x ∈/ A ∩ B. We have already proved that
A4B = A∪B −A∩B, so x ∈ A∪B −A∩B. If we assume that x ∈ X, then this condition is equivalent
/ A ∩ B ⇔ x ∈ A ∪ B ∧ x ∈ (A ∩ B)c ⇒ x ∈ (A ∪ B) ∩ (A ∩ B)c = F.
to saying that x ∈ A ∪ B ∧ x ∈
Therefore, we have proved that, indeed, A 4 B ⊂ F, and so, F = A 4 B.
Finally, we have A 4 B = (A − B) ∪ (B − A) = (A ∪ B) − (A ∩ B) = (A ∪ B) ∩ (Ac ∪ B c ) as requested.
(3) Deduce that

(1)A 4 B = ∅ ⇔ A = B (2)Ac 4 B c = A 4 B

Solution: First, let us assume that A 4 B = ∅. This means that:

A 4 B = ∅ ⇔ (A − B) ∪ (B − A) = ∅ ⇒ A − B = ∅ ∧ B − A = ∅ ⇒ A = B

Therefore, A 4 B = ∅ ⇒ A = B. Now, if A = B, then A ∪ B = A ∩ B = A, and therefore,

A ∪ B − A ∩ B = A − A = ∅ ⇒ A 4 B = ∅. This concludes that A 4 B = ∅ ⇔ A = B.
On the other hand, we know that if A and B are subsets of a larger set X, then:

Ac 4 B c = (Ac ∪ B c ) ∩ ((Ac )c ∪ (B c )c ) = (Ac ∪ B c ) ∩ (A ∪ B) = (A ∪ B) = (Ac ∪ B c ) = A 4 B

Therefore, Ac 4 B c = A 4 B.

2
 (4) When E is a finite set (i.e one with finitely many elements), denote by |E| the number of its elements
(cardinality).
Show that, if the sets A, B are finite, then:

|A| + |B| = |A ∪ B| + |A ∩ B|

Solution: Let n = |A|, m = |B|, o = |A ∪ B|, and p = |A ∩ B|. We note that:

n = |A − A ∩ B| + o
m = |B − A ∩ B| + o
p = |A − A ∩ B| + |B − B ∩ A| + o

Therefore, p = (n − o) + (m − o) + o ⇔ p = (n + m) − o ⇔ p + o = n + m ⇔ |A ∩ B| + |A ∪ B| = |A| + |B|.

2 Ordered Pairs
Definition 2.1. Given the non-empty sets X1 , X2 , · · · , Xn , their cartesian product:

X1 × X2 × · · · × Xn

is the collection of all ordered sets (x1 , x2 , · · · , xn ) such that

x1 ∈ X1 ∧ x2 ∈ X2 ∧ · · · ∧ xn ∈ Xn

If X1 = X2 = · · · = Xn , their cartesian product is denoted by X n , with X 1 ≡ X.

Remark: For n > 1, Rn = R×R× · · · ×R. We define an interval in Rn as a set of the form I1 ×I2 × · · · ×In ,
where I1 , I2 , · · · , In are intervals in R.

3 Functions
Let X and Y be two non-empty sets. A relation from X to Y is a subset of X × Y . If a relation f from
X to Y is such that for every x in X there is only one ordered pair (x, y) in X × Y , then f is said to be a
function on X into Y. That is:

f :X→Y

And we call the set X the domain of f . Let (x, y) be any element of the function set f . Then, we say that
y is the image of x under f , and we say that f (x) = y. If E is any subset of X, then the set:

f (E) = {y ∈ Y |y = f (x), for x ∈ E}

Is called the image of E under f . The set f (X) is called the range of X under f .
Example: We denote by Φ the set of all real functions φ defined by an equation of the form

φ(x) = αx + β(x ∈ R)

Where α, β are real numbers. A function f : R2 → Φ is obtained by assigning to each point (a, b) ∈ R2 the
function φa,b (x) = ax + b. Therefore, ∀(a, b) ∈ R2 , f (a, b) = φa,b .
Now, given a function f on X into Y . If f (X) = Y , then we say that the function f is surjective. If for
every x in X, there is a different image through f (i.e if f (x) = f (x0 ) ⇒ x = x0 ), then we say that f is
injective. If f is both injective and surjective, then we say that f is a bijetction of X and Y (f represents a
one-to-one correspondence between the elements of X and Y )

3
3.0.1 Inverse Functions

Suppose that a function f has a domain X and a range Y . to f , which is a subset of x × Y , there corresponds
a relation f −1 of Y × X defined as:

f −1 = {(y, x) ∈ Y × X|(x, y) ∈ f }

Plainly, f −1 is a function with domain Y and range X if and only if f is bijective. If this is the case, f −1
is called the inverse function of f .
If f : X → Y is injective, then clearly the function f |f (X) : X ⇒ f (X) is bijective,and therefore as an
inverse f −1 .

3.0.2 Inverse images

Let f : X → Y be an arbitrary function and let E be any subset of Y . We denote by f −1 (E) the set:

f −1 (E) = {x ∈ X|f (x) ∈ E}

3.0.3 Function composition

Given two functions f : X → Y and g : Y → W , the function h : X → W defined by:

h(x) = g(f (x)), (x ∈ X)

is called the composition of f and g, and is denote g ◦ f .
Theorem 3.1. (i) If the function f : X → Y is surjective and if there existis a function g : Y → X such
that g ◦ f = idX , then f is bijective, and g = f −1 .
(ii) If the function f : X → Y is bijective and if the function g : Y → X is such that f ◦ g = idY , then
g = f −1 .

Proof. (i) Let it be true that f (x) = f (x0 ). Then we have that: g(f (x)) = g(f (x0 )) ⇔ x = x0 . Therefore,
f (x) = f (x0 ) ⇒ x = x0 . So, f is injective, and bijective as well, and so it admits an inverse function.
Now, we have that:
g = g ◦ idY = g ◦ (f ◦ f −1 ) = (g ◦ f ) ◦ f −1 = idX ◦ f −1 = f −1
And so, g = f −1 .
(ii) If f is bijective as stated, then we have that f ◦ f −1 = idY , and f −1 ◦ f = idX . Now, we have:
g = idX ◦ g = (f −1 ◦ f ) ◦ g = f −1 ◦ (f ◦ g) = f −1 ◦ idY = f −1
Finally, g = f −1 .

Theorem 3.2. Let f : X → Y and g : Y → W both be bijective, then g ◦ f is bijective, and (g ◦ f )−1 =
f −1 ◦ g −1 .

Proof. First, lets prove that g ◦ f is surjective. We know that:

∀w ∈ W, ∃y ∈ Y /g(y) = w ∧ ∀y ∈ Y, ∃x ∈ X/f (x) = y ⇒ ∀w ∈ W, ∃x ∈ X/(g ◦ f )(x) = w

Therefore, g ◦ f is surjective. Since both f and g are bijective, then f −1 ◦ g −1 : W → X is well defined, nd
we see that:

(f −1 ◦ g −1 ) ◦ (g ◦ f ) = f −1 ◦ (g −1 ◦ (g ◦ f )) = f −1 ◦ ((g −1 ◦ g) ◦ f ) = f −1 ◦ (idY ◦ f ) = f −1 ◦ f = idX

Then, by our previous theorem, f −1 ◦ g −1 = (g ◦ f )−1 .

4
3.0.4 Restriction and extension of functions

Supose that X2 ⊂ X1 and that f : X1 → Y , and g : X2 → Y , alongside the property g(x) = f (x), for all
x ∈ X2 . We say that g is a restriction of f to X2 and that f is an extension of g to X1 .

3.1 Excercises
(1) Prove that:

(i)(A∪B)×C = (A×C)∪(B×C) (ii)(A∩B)×C = (A×C)∩(B×C) (iii)(A−B)×C = (A×C)−(B×C)

Solution:

(i) Let us assume that x ∈ (A ∪ B) × C. Then, there exist p ∈ A ∪ B and q ∈ C such that x = (p, q). If
p ∈ A, then x = (p, q) ∈ A × C. If p ∈ B, then x = (p, q) ∈ B × C. Then, x ∈ (A ∪ B) × C ⇒ x ∈
(A × C) ∪ (B × C), so (A ∪ B) × C ⊂ (A × C) ∪ (B × C).
Now, if x ∈ (A × C) ∪ (B × C), we have x ∈ A × C ∨ x ∈ B × C. If x ∈ A × C, since A ⊂ A ∪ B,
we have that, since there exist p ∈ A and q ∈ C such that x = (p, q), then there exist p ∈ A ∪ B and
q ∈ C such that x = (p, q), and so, x ∈ (A ∪ B) × C. The same is true if x ∈ B × C. Therefore,
(A ∪ B) × C = (A × C) ∪ (B × C).
(iii) First, let us assume that x ∈ (A − B) × C. We have that there exist p ∈ A − B and q ∈ C such that
x = (p, q). Since p ∈ A − B ⇒ p ∈ A ∧ p ∈/ B. Besides, we have that since p ∈ A − B ⊂ A, we have
that x ∈ A × C. However, we know that x ∈ / B × C, since p ∈
/ B. This means that:
x ∈ (A − B) × C ⇒ x ∈ A × C ∧ x ∈
/ B×C ⇒x∈A×C −B×C

Which implies that (A − B) × C ⊂ A × C − B × C. Now, if x ∈ A × C − B × C, we have that

x ∈ A×C∧x ∈ / B × C. Now, we have that there exist p ∈ A and q ∈ C such that x = (p, q). We
only have to prove that p ∈ A − B. We know that p ∈ A. Now, let us assume that p ∈ A ∩ B. Then,
we have that x ∈ B × C, for p ∈ B which contradicts our initial statement. Therefore, p ∈
/ A ∩ B.
But since p ∈ A, we conclude that p ∈ A − B, and therefore x ∈ (A − B) × C. This proves that
A × C − B × C ⊂ (A − B) × C.

(2) Let C be any collection of subsets of a set X. Prove that for any function f : X → Y ,
! !
[ [ \ \
(i)f A = f (A) (ii)f A ⊂ f (A)
A∈C A∈C A∈C A∈C

Show that, if f is inyective, then identity holds in (ii); and that f is injective if:

f (A ∩ B) = f (A) ∩ f (B)

Solution:
(i) By its very definition:
f (∪A∈C A) = {y ∈ Y |∃x ∈ ∪A∈C A/f (x) = y}
Let y ∈ f (∪A∈C A), then, ∃x ∈ ∪A∈C A/f (x) = y. Now, sinceS x ∈ ∪A∈C A ⇒ ∃A ∈ C/x ∈ A.
Given this statement, we have that, for such A, y ∈ f (A) ⊂ A∈C f (A). So:
! !
[ [ [ [
y∈f A ⇒y∈ f (A), therefore f A ⊂ f (A)
A∈C A∈C A∈C A∈C
S
Now, let us assume S that y ∈ A∈C f (A). This means that, ∃A ∈ C/y S ∈ f (A). We note
S that,
indeed, f (A)
S ⊆ f ( A∈C A),Sfor all A ∈ C. Therefore, y ∈ f (A) ⊆ f ( A∈C A) ⇒ y ∈ f ( A∈C A).
Therefore, A∈C f (A) ⊂ f ( A∈C A), and so we obtain the desired result.

5
 (ii) Again, by its definition:
!
\ \
f A = {y ∈ Y |∃x ∈ A/f (x) = y}
A∈C A∈C
T
T
Let y ∈ f A∈C A , and x ∈ A∈C A, such that f (x) = y. This means that: ∀A ∈ C, x ∈ A.
Therefore, since we have that:
\
∀A ∈ C, x ∈ A ⇒ ∀A ∈ C, y ∈ f (A) ⇒ y ∈ f (A)
A∈C
T
T
Therefore, f A∈C A ⊂ A∈CTf (A). Now, let f : X → Y be injective. This means that:
f (x) = f (x0 ) ⇒ x = x0 . Let y ∈ A∈C f (A). This means that, ∀A ∈ C, y ∈ f (A). We have:
∀A ∈ C, y ∈ f (A) ⇒ ∀A ∈ C, ∃x ∈ A/f (x) = y

Now we shall use the fact that f is injective. Let x1 ∈ A1 and x2 ∈ A2 be such that f (x1 ) = y
and f (x2 ) = y, according to our hypothesis. Since f is injective, and f (x1 ) = f (x2 ) = y ⇒ x1 =
x2 = x, which in term implies that x ∈ A1 ∩ A2 . In general, since f is injective:
∃!x ∈ X/f (x) = y
However, our hypothesis claims that ∀A ∈ C, ∃x ∈ A/f (x) = y. In order to fulfill both statements,
∃!x ∈ ∩A∈C A/f (x) = y. Therefore:
!
\
∃!x ∈ ∩A∈C A/f (x) = y ⇒ y ∈ f A
A∈C
T T

Which gives us that A∈C f (A) ⊂ f A∈C A .
Now, let us assume that ∀(A, B) ∈ C × C, f (A ∩ B) = f (A) ∩ f (B). We want to prove that
f (x) = f (x0 ) ⇒ x = x0 . We shall prove this by contradiction. Let there exist x and x0 , such that
f (x) = f (x0 ) = y ∈ Y , with x 6= x0 . Consider the subsets of X, A = {x}, and B = {x0 }. Then:

∃(x, x0 ) ∈ X×X, with x 6= x0 /f (x) = f (x0 ) ⇒ y ∈ f (A)∩f (B) ⇒ y ∈ f (A∩B) ⇔ y ∈ f (∅) ⇒ y ∈ ∅

Which is clearly a contradiction. Then, we must have that x = x0 .

(3) Show that , if f : A → Y is any function, then
f (A − B) ⊃ f (A) − f (B)
for all subsets A, B of X; and that identity holds if, and only if, f is injective.
Solution: Let y ∈ f (A) − f (B). Then:
y ∈ f (A) − f (B) ⇒ y ∈ f (A) ∧ y ∈ f (B) ⇒ ∃x ∈ A/f (x) = y ∧ @x0 ∈ B/f (x0 ) = y

Considering such an element x in A, we clearly see that x ∈ A − B, for if not, then x ∈ A ∩ B ⇒ x ∈

B ⇒ ∃x ∈ B/f (x) = y ⇒⇐. Then, such an element in A, also is in A − B. Then:
∃x ∈ A − B/f (x) = y ⇒ y ∈ f (A − B)
Then, this proves that f (A) − f (B) ⊂ f (A − B).
Now, let us assume that identity holds. Then, f (A) − f (B) = f (A − B). On the other hand, let’s
assume that there exist (x, x0 ) ∈ X × X, such that f (x) = f (x0 ) = y, and that x 6= x0 . Let A = {x}
and B = {x0 }. Then. we have that, since x 6= x0 , A 6= B. Then, we see that:
A − B = A ⇒ y ∈ f (A − B) ⇒ y ∈ f (A) − f (B) ⇒ ∃z ∈ A/f (z) = y ∧ @z 0 ∈ B/f (z 0 ) = y
Since b = {x0 }, then @z 0 ∈ B/f (z 0 ) = y ⇒ f (x0 ) 6= y, which contradicts the hypothesis that f (x0 ) = y.
Then, if f (x) = f (x0 ), under this assumption, it can’t be that x 6= x0 . Therefore, x = x0 , thus proving
that f is injective.

6
 Now let us assume that f is injective. Therefore, f (x) = f (x0 ) ⇒ x = x0 . Let A, B be two subsets of
X, and y ∈ f (A − B). Then:
∃x ∈ A − B/f (x) = y

This means that there is an x ∈ X that fulfills the conditions x ∈ A ∧ x ∈ / B, that also satisfies that
f (x) = y. We must prove that there does not exist any x0 ∈ B, such that f (x0 ) = y. First, since
x ∈ A − B ⊂ A, then clearly y ∈ f (A). Since f is injective, if there were any x0 ∈ B such that
f (x0 ) = y, then x0 = x ⇒ x0 ∈ A − B ⇒ x0 ∈ / B ⇒⇐. Therefore, there is none x0 ∈ B such that
f (x0 ) = y, and thus, y ∈ f (A) − f (B), which implies that f (A − B) ⊂ f (A) − f (B).

3.2 Similarity of sets

Let A and B be two sets. We say that A and B are similar if there is a one-to-one correspondence between
their elements (i.e if there is a bijection between both sets). Then, we write A ∼ B.
Similarity of sets shows the following properties:

(reflexivity) A ∼ A
(symmetry) A ∼ B ⇔ B ∼ A
(transitivity) if A ∼ B, and B ∼ C, then A ∼ C

Therefore, similarity of sets defines an equivalence relation among all kinds of sets of a given collection C.
Finite sets are similar if, and only if, they have the same number of elements. Infinite sets can be similar
to proper subsets of themselves, just like the set Z, and the set of even integers Zp , for we can define the
bijection y = 2x (x ∈ Z) between both of them.
A set which is similar to the set of all positive integers N is said to be countably infinite (it can be arranged
as a sequence). A set is called countable if it is either finite, or countably infinite.
Theorem 3.3. The set of real numbers in the interval (0, 1) is not countably infinite
Theorem 3.4. Every infinite set contains a countably infinite subset

Proof. We shall prove this by induction. Let A be an infinite set, we denote a1 as an element of A, and
S1 = {a1 }. The set A − S is not empty, and S is countable. Since A − S is note empty, given any sive
of S, then we see that, given Sn = {a1 , a2 , · · · , an }, the set A − S is not empty, and neither is A − Sn+1 .
Therefore, the process can be continued indefinitely, and the set S = {a1 , a2 , · · · } ⊂ A is countable.

Corolary 1. Every infinite set contains a proper subset to which it is similar

Proof. Let A be an inifinite set, and S = {a1 , a2 , · · · } a countably infinite subset of A. We define the function
f : A → S, as:

an+1 ifx = an
f (x) =
x ifx ∈ A − S

We will prove that f is a bijection. First, let y ∈ S, then:

y ∈ S ⇒ ∃n ∈ N/x = an

We know that an−1 ∈ S, and therefore f (an−1 ) = an = y. Therefore, ∀y ∈ S, ∃x ∈ A/f (x) = y, and so, f
is surjective. Now, let f (x) = f (x0 ), for some x, x0 in A.
First, if x, x0 ∈ S, then, ∃n ∈ N/f (x) = f (x0 ) = an . But f (x) = an , if x = an . If x 6= an , then x 6= S. So,
x = an = x0 ⇒ x = x0 .

7
If x ∈ S ∧ x0 ∈ A − S, and f (x) = f (x0 ), then ∃n ∈ N/x = aN , and:
f (x) = an+1
⇒ x0 = an+1 ⇒ x0 ∈ S ⇒⇐
f (x0 ) = x0
Therefore, @(x, x0 ) ∈ A × A − S/f (x) = f (x0 ). So, in conclusion, given the first case we tried, f (x) = f (x0 ) ⇒
x = x0 , and therefore f is injective as well.
Theorem 3.5. Every subset of a countable set is countable

4 Metric Spaces
Definition 4.1. Let X be a non-empty set,and ρ : X × X → R with the following properties:

M1 ρ(x, y) ≥ 0, ∀(x, y) ∈ X × X, and ρ(x, y) = 0 ⇔ x = y

M2 ρ(x, y) = ρ(y, x), ∀(x, y) ∈ X × X

M3 ρ(x, z) ≤ ρ(x, y) + ρ(y, z), ∀(x, y, z) ∈ X × X × X

Then, ρ is called a metric on X, and X, alongside the metric ρ, is called a metric space.

Example . Any set can be given the metric ρ defined by:


0 if x = y
ρ(x, y) =
6 y
1 if x =
Which is known as the discrete metric.
Let (X, ρ) be a metric space, and Y ⊂ X. If σ is the restriction of ρ to Y × Y , then (Y, σ) is a metric space
by itself. We often say that σ is the metric induced by (X, ρ) on Y , and we call (Y, σ) a metric subspace of
(X, ρ).
Definition 4.2. The sequence (xn ) of points in the metric space (X, ρ) is said to converge to the point
x ∈ X if:

ρ(xn , x) → 0, if n→∞
We write, as in classical analysis, xn → x as n → ∞, or limx→∞ xn = x.

Since ρ(x, y) is a real number, we can extend the  − δ definition of convergence in R to this type of
convergence in metric spaces. Thus, we can say that the sequence (xn ) in the metric space (X, ρ) converges
to x if given any  > 0, there exists n0 ∈ N, such that ∀n > n0 , ρ(xn , x) < .
Theorem 4.1. Let (X, ρ) be a metric space. A sequence (xn ) in X cannot converge to two distinct limits.

Proof. We shall prove this by contradiction. Let x1 , x2 ∈ X be the limits of (xn ). Therefore, we have that:

lim ρ(x1 , xn ) = lim ρ(x2 , xn ) = 0, with x1 6= x2

n→∞ n→∞

Stating this fact in an  − δ notation, we have that:

∀1 > 0, ∃n1 ∈ N/ρ(xn , x1 ) < 1 , ∀n > n1 ∧ ∀2 > 0, ∃n2 ∈ N/ρ(xn , x2 ) < 2 , ∀n > n2

Let 1 = 2 = 2, and N = max{n1 , n2 }. Let n > N . Therefore, we have that:

 
ρ(x1 , xn ) < ∧ ρ(x2 , xn ) < ⇒ ρ(x1 , xn ) + ρ(x2 , xn ) ≤ 
2 2

8
 Now, since ρ is a metric, we have that ρ(x1 , x2 ) ≤ ρ(x1 , xn ) + ρ(xn , x2 ). Since x1 6= x2 , then ρ(x1 , x2 ) =
δ > 0, and so:

∃δ > 0/∀n ∈ N, ρ(x1 , xn ) + ρ(x2 , xn ) ≥ δ

Given the −δ definition form above, let 0 <  < ρ(x1 , x2 )/2 Then, we have that ρ(x1 , xn )+ρ(x2 , xn ) ≤ /2,
which is a contradiction.

Example: In R2 , let the sequence {xn }∞

n=1 be defined by:

2n2
 
n
xn = , 2
2n + 1 n − 2

We see that as n → ∞, xn → ( 21 , 2), since:

   s 2  2 s 2  2
1 1 4 1 4
ρ , 2 , xn = + ⇒ lim + =0
2 4n + 2 n2 − 2 n→∞ 4n + 2 n2 − 2

When two metrics ρ, σ on a set X aresuch that a sequence (xn converges in (X, ρ) if and only if it converges
in (X, σ), then ρ and σ are said to be equivalent metrics. A sufficient, but not necessary condition for the
metrics ρ and σ to be equivalent can be shown from the compression theorem of classical analysis, where,
there exist two non-zero constants λ, α ∈ R, such that:

λρ(x, y) ≤ σ(x, y ≤ αρ(x, y), ∀(x, y) ∈ X × X

4.0.1 Exercises

(1) Is the function ρ given by ρ(x, y) = |x2 − y 2 | a metric on (a)(−∞, ∞), (b)[0, ∞) ?
Solution: We must chech that this function ρ agrees with all the conditions given by a metric on a
set X. First, we see that for both cases given in (a) and (b), it holds that ρ(x, y) ≥ 0, ∀(x, y) ∈ X × X.
Now, in the case of (a), let ρ(x, y) = 0, for x, y ∈ R. Now:

ρ(x, y) = 0 ⇔ |x2 − y 2 | = 0 ⇔ |(x − y)(x + y)| = 0 ⇔ |x − y||x + y| = 0 ⇔ |x − y| = 0 ∨ |x + y| = 0

In this case, we have an infinite number of cases for which x 6= y, and still ρ(x, y) = 0. for example,
let x > 0. Then, if y = −x < 0, then |x + y| = 0, and so, |x2 − y 2 | = 0. Therefore, ρ as defined above
is not a metric for R. If we now consider the subset [0, ∞), then we have that:
∀(x, y) ∈ (0, ∞) × (0, ∞), |x + y| > 0 ⇒ |x2 + y 2 | = 0 ⇒ x = y
Being clear that x = y ⇒ ρ(x, y) = 0, we have that ρ(x, y) = 0 ⇔ x = y, if X = [0, ∞). Lastly, we
must test the final condition. Let (x, y, z) ∈ X × X × X. We have that:

ρ(x, z) + ρ(z, y) = |x2 − z 2 | + |z 2 − y 2 |, if z ≤ x, then|z 2 − y 2 | = |y 2 − z 2 | ≥ |x2 − y 2 | ⇒ ρ(x, z) + ρ(z, x) ≥ ρ(x, y)

Taking each possible case for z, we conclude that ∀(x, y, z) ∈ X × X × X, ρ(x, y) ≤ ρ(x, z) + ρ(z, y),
which allows us to conclude that ρ is a metric of X = [0, ∞).
(2) Let C be the set of bounded continous real functions on R, and let ρ be defined by:
Z 
 x+h 
ρ(φ, ψ) = sup [φ(t) − ψ(t)]dt
 

 x 
−∞<x<∞
0<h≤1

Show that ρ is a metric on C.

9
 Solution: Again, we must test all the conditions giben in the definition of a metric of a set X. If
X = C then we have that, once again, ∀(f, g) ∈ C × C, ρ(f, g) ≥ 0, and that ρ(f, g) = ρ(g, f ). Now, we
must test if ρ(f, g) = 0 ⇔ f = g. If f = g, then f − g = 0, and so ρ(f, g) = 0. Now, let ρ(f, g) = 0.
Then:
Z  Z 
 x+h   x+h 
ρ(f, g) = 0 ⇔ sup [f (t) − g(t)]dt = 0 ⇒ ∀(x, h) ∈ R × (0, 1], [f (t) − g(t)]dt = 0
   
 
 x   x 
−∞<x<∞
0<h≤1
Z x+h
⇒ ∀(x, h) ∈ R × (0, 1], [f (t) − g(t)]dt = 0
x

Since f, g are countinous and bounded in R, then f − g is bounded and continous in R. Therefore, we
R x+h
know that, ∀(x, h) ∈ R × (0, 1], ∃c ∈ [x, x + h]/∀t ∈ [x, x + h], h(f − g)(c) ≤ x (f − g)(t)dt . Now,
Ry
this condition implies that, ∀y ∈ R, 0 (f − g)(t)dt = 0. Differentiating with respect to y, we conclude
that:
Z y
d
(f − g)(t)dt = 0 ⇒ (f − g)(y) = 0, ∀y ∈ R ⇒ f = g
dy 0
Therefore, ρ(f, g) = 0 ⇒ f = g, and so ρ(f, g) = 0 ⇔ f = g. Now, we only have to prove that:
∀(f, g, h) ∈ C × C × C, ρ(f, g) ≤ ρ(f, h) + ρ(h, g)

Given f, g, h ∈ C, we have that:

Z  Z 
 x+h   x+h 
ρ(f, h) + ρ(h, g) = sup [f (t) − h(t)]dt + sup [h(t) − g(t)]dt
   
 
 x   x 
−∞<x<∞ −∞<x<∞
0<h≤1 0<h≤1

We note that:
Z  Z  Z 
 x+h   x+h   x+h 
∀(x, h) ∈ R × (0, 1], [f (t) − h(t)]dt +  [h(t) − g(t)]dt ≥  [(f − h)(t) + (h − g)(t)]dt
     

 x   x   x 
Z  Z  Z 
 x+h   x+h   x+h 
⇒ sup [f (t) − h(t)]dt + sup [h(t) − g(t)]dt ≥ sup [(f − g)(t)]dt
     
  
 x   x   x 
−∞<x<∞ −∞<x<∞ −∞<x<∞
0<h≤1 0<h≤1 0<h≤1

Thus proving that ρ(f, h) + ρ(h, g) ≥ ρ(f, g), ∀(f, g, h) ∈ C × C × C. Therefore, ρ is a metric for C.
(3) In Rn , let xk = (ζ1k , ζ2k , . . . , ζnk ). Show that
xk → x = (ζ1 , ζ2 , . . . , ζn )
as k → ∞, if, and only if, ∀i ∈ {1, 2, . . . , n}, ζik → ζi .
Solution: Taking the usual metric of Rn , we have that, for all k:
v
u n
uX
ρ(x, xk ) = t (xik − xi )2
i=1

Now, let us suppose that limk→∞ ρ(x, xk ) = 0. That means that:

v v
u n u n n
uX u X X
lim ρ(x, xk ) = 0 ⇒ lim t 2
(xik − xi ) = 0 ⇒ t lim (xik − xi )2 = 0 ⇒ lim (xik −xi )2 = 0
k→∞ k→∞ k→∞ k→∞
i=1 i=1 i=1

10
 We see that ρ2 is a continous function, and therefore, we can decompose the previous limit as it follows:
n
X n
X
lim (xik − xi )2 = 0 ⇒ lim (xik − xi )2 = 0
k→∞ k→∞
i=1 i=1

It is left as an exercise for the reader to prove that each of these limits exists, allowing us to make this
decomposition unambigously. We note that, ∀i ∈ {1, 2, . . . , n}, limk→∞ (xik − xi )2 ≥ 0, and so:

n
X
lim (xik − xi )2 = 0 ⇒ ∀ı ∈ {1, 2, . . . , n}, lim (xik − xi )2 = 0 ⇒ lim xik = xi
k→∞ k→∞ k→∞
i=1

Now, let us suppose that ∀i ∈ {1, 2, . . . , n}, limk→∞ xik = xi . The rest of the proof is left as an
exercise for the reader.
(4) Let C be the set of real functions continous on the interval [0, 1], and define

ρ(f, g) = sup |f (x) − g(x)|

0≤x≤1
s
Z 1
σ(f, g) = |f (x) − g(x)|2 dx
0
Z 1
τ (f, g) = |f (x) − g(x)|dx
0

Prove that ρ, σ, τ are metrics on C. Show that, for all f, g ∈ C,

ρ(f, g) ≥ σ(f, g) ≥ τ (f, g)
For n = 1, 2, . . ., he functions fn , gn ∈ C are defined by:
 √
1 − nx 0 ≤ x ≤ n−1 n(1 − nx) 0 ≤ x ≤ n−1

fn (x) = −1 gn (x) =
0 n <x≤1 0 n−1 < x ≤ 1
Prove that the sequence (fn ) converges in (C, σ) and in (C, τ ), but not in (C, ρ), and that (gn ) converges
in (C, τ ), but neither in (C, ρ) or (C, σ).
Solution:
First, we must prove that ρ, σ, τ are metrics. In all cases, it is easily shown that propertie M2 holds in
all cases, as well as the first half of propertie M1. We must prove the second half of the latter. In the
case of ρ, we have that:

ρ(f, g) = 0 ⇔ sup |f (x)−g(x)| = 0 ⇒ ∀x ∈ [0, 1], |f (x)−g(x)| ≤ 0 ⇒ ∀x ∈ [0, 1], |f (x)−g(x)| = 0

0≤x≤1

Which obviously implies that f = g. The contrary is clearly true, and so, for ρ, ρ(f, g) = 0 ⇔ f = g.
for σ on the other hand, we have that:
s
Z 1 Z 1
σ(f, g) = 0 ⇔ |f (x) − g(x)|2 dx = 0 ⇔ |f (x) − g(x)|2 dx = 0
0 0

We note that, ∀x ∈ [0, 1], |f (x) − g(x)|2 ≥ 0, and so:

Z 1
|f (x) − g(x)|2 dx = 0 ⇒ ∀x ∈ [0, 1], |f (x) − g(x)|2 = 0 ⇒ f = g
0

Being true that f = g ⇒ σ(f, g) = 0, we have that σ(f, g) = 0 ⇔ f = g. Finallu, in the case of τ , the
reasoning is basically the same as in σ.

11
 We only need prove M3 for all three relations. First, for ρ, we have:

∀(f, g, h) ∈ C×C×C, ρ(f, h)+ρ(h, g) = sup |f (x)−h(x)|+ sup |h(x)−g(x)| ≥ sup |f (x)−g(x)| = ρ(f, g)
0≤x≤1 0≤x≤1 0≤x≤1

In the case of σ, we have that:

s s
Z 1 Z 1
∀(f, g, h) ∈ C × C × C, σ(f, h) + σ(h, g) = |f (x) − h(x)|2 dx + |h(x) − g(x)|2 dx
0 0

5 Norms in vector spaces

Definition 5.1. Let V be a non-empty set,. Given the inner and outer composition law:

+: V ×V → V ·: R×V → V
(~x, ~y ) → ~x + ~y (α, ~x) → α~x

12