4Continuous functions
IA Analysis I
4.2 Continuous induction*
Continuous induction is a generalization of induction on natural numbers. It
provides an alternative mechanism to prove certain results we have shown.
Proposition (Continuous induction v1). Let
a < b
and let
A ⊆
[
a, b
] have the
following properties:
(i) a ∈ A
(ii) If x ∈ A and x 6= b, then ∃y ∈ A with y > x.
(iii) If ∀ε > 0, ∃y ∈ A : y ∈ (x − ε, x], then x ∈ A.
Then b ∈ A.
Proof.
Since
a ∈ A
,
A 6
=
∅
.
A
is also bounded above by
b
. So let
s
=
sup A
.
Then ∀ε > 0, ∃y ∈ A such that y > s − ε. Therefore, by (iii), s ∈ A.
If s 6= b, then by (ii), we can find y ∈ A such that y > s.
It can also be formulated as follows:
Proposition (Continuous induction v2). Let A ⊆ [a, b] and suppose that
(i) a ∈ A
(ii) If [a, x] ⊆ A and x 6= b, then there exists y > x such that [a, y] ⊆ A.
(iii) If [a, x) ⊆ A, then [a, x] ⊆ A.
Then A = [a, b]
Proof.
We prove that version 1
⇒
version 2. Suppose
A
satisfies the conditions
of v2. Let A
0
= {x ∈ [a, b] : [a, x] ⊆ A}.
Then
a ∈ A
0
. If
x ∈ A
0
with
x 6
=
b
, then [
a, x
]
⊆ A
. So
∃y > x
such that
[a, y] ⊆ A. So ∃y > x such that y ∈ A
0
.
If
∀ε >
0
, ∃y ∈
(
x − ε, x
] such that [
a, y
]
⊆ A
, then [
a, x
)
⊆ A
. So by (iii),
[
a, x
]
⊆ A
, so
x ∈ A
0
. So
A
0
satisfies properties (i) to (iii) of version 1. Therefore
b ∈ A
0
. So [a, b] ⊆ A. So A = [a, b].
We reprove intermediate value theorem here:
Theorem (Intermediate value theorem). Let
a < b ∈ R
and let
f
: [
a, b
]
→ R
be continuous. Suppose that
f
(
a
)
<
0
< f
(
b
). Then there exists an
x ∈
(
a, b
)
such that f(x) = 0.
Proof.
Assume that
f
is continuous. Suppose
f
(
a
)
<
0
< f
(
b
). Assume that
(∀x) f(x) 6= 0, and derive a contradiction.
Let
A
=
{x
:
f
(
x
)
<
0
}
Then
a ∈ A
. If
x ∈ A
, then
f
(
x
)
<
0, and by
continuity, we can find
δ >
0 such that
|y −x| < δ ⇒ f
(
y
)
<
0. So if
x 6
=
b
, then
we can find y ∈ A such that y > x.
We prove the contrapositive of the last condition, i.e.
x 6∈ A ⇒ (∃δ > 0)(∀y ∈ A) y 6∈ (x − δ, x].
If
x 6∈ A
, then
f
(
x
)
>
0 (we assume that
f
is never zero. If not, we’re done).
Then by continuity, ∃δ > 0 such that |y −x| < δ ⇒ f(y) > 0. So y 6∈ A.
Hence by continuous induction, b ∈ A. Contradiction.
Now we prove that continuous functions in closed intervals are bounded.
Theorem. Let [
a, b
] be a closed interval in
R
and let
f
: [
a, b
]
→ R
be continuous.
Then f is bounded.
Proof.
Let
f
: [
a, b
] be continuous. Let
A
=
{x
:
f is bounded on
[
a, x
]
}
. Then
a ∈ A
. If
x ∈ A, x 6
=
b
, then
∃δ >
0 such that
|y − x| < δ ⇒ |f
(
y
)
− f
(
x
)
| <
1.
So
∃y > x
(e.g. take
min{x
+
δ/
2
, b}
) such that
f
is bounded on [
a, y
], which
implies that y ∈ A.
Now suppose that
∀ε >
0,
∃y ∈
(
x, −ε, x
] such that
y ∈ A
. Again, we can
find
δ >
0 such that
f
is bounded on (
x −δ, x
+
δ
), and in particular on (
x −δ, x
].
Pick
y
such that
f
is bounded on [
a, y
] and
y > x − δ
. Then
f
is bounded on
[a, x]. So x ∈ A.
So we are done by continuous induction.
Finally, we can prove a theorem that we have not yet proven.
Definition (Cover of a set). Let
A ⊆ R
. A cover of
A
by open intervals is a set
{I
γ
: γ ∈ Γ} where each I
γ
is an open interval and A ⊆
S
γ∈Γ
I
γ
.
A finite subcover is a finite subset
{I
γ
1
, ··· , I
γ
n
}
of the cover that is still a
cover.
Not every cover has a finite subcover. For example, the cover
{
(
1
n
,
1) :
n ∈ N}
of (0, 1) has no finite subcover.
Theorem (Heine-Borel*). Every cover of a closed, bounded interval [
a, b
] by
open intervals has a finite subcover. We say closed intervals are compact (cf.
Metric and Topological Spaces).
Proof.
Let
{I
γ
:
γ ∈
Γ
}
be a cover of [
a, b
] by open intervals. Let
A
=
{x
: [
a, x
]
can be covered by finitely many of the I
γ
}.
Then a ∈ A since a must belong to some I
γ
.
If
x ∈ A
, then pick
γ
such that
x ∈ I
γ
. Then if
x 6
=
b
, since
I
γ
is an open
interval, it contains [
x, y
] for some
y > x
. Then [
a, y
] can be covered by finitely
many I
γ
, by taking a finite cover for [a, x] and the I
γ
that contains x.
Now suppose that ∀ε > 0, ∃y ∈ A such that y ∈ (x − ε, x].
Let
I
γ
be an open interval containing
x
. Then it contains (
x −ε, x
] for some
ε >
0. Pick
y ∈ A
such that
y ∈
(
x − ε, x
]. Now combine
I
γ
with a finite
subcover of [a, y] to get a finite subcover of [a, x]. So x ∈ A.
Then done by continuous induction.
We can use Heine-Borel to prove that continuous functions on [
a, b
] are
bounded.
Theorem. Let [
a, b
] be a closed interval in
R
and let
f
: [
a, b
]
→ R
be continuous.
Then
f
is bounded and attains it bounds, i.e.
f
(
x
) =
sup f
for some
x
, and
f(y) = inf f for some y.
Proof. Let f : [a, b] → R be continuous. Then by continuity,
(∀x ∈ [a, b])(∃δ
x
> 0)(∀y) |y −x| < δ
x
⇒ |f(y) − f(x)| < 1.
Let
γ
= [
a, b
] and for each
x ∈ γ
, let
I
x
= (
x − δ
x
, x
+
δ
x
). So by Heine-Borel,
we can find x
1
, ··· , x
n
such that [a, b] ⊆
S
n
1
(x
i
− δ
x
i
, x
i
+ δ
x
i
).
But
f
is bounded in each interval (
x
i
− δ
x
i
, x
i
+
δ
x
i
) by
|f
(
x
i
)
|
+ 1. So it is
bounded on [a, b] by max |f(x
i
)| + 1.