Preliminaries | An Introduction to Real Analysis

In this short chapter, we will briefly review some basic set notation, proof methods, functions, and countability. The presentation of these topics is intentionally brief for two reasons: (1) the reader is likely familar with these topics, and (2) we include only the necessary material needed to start doing real analysis.

Sets, Numbers, and Proofs

Let

S

be a set. If

x

is an element of

S

then we write

x \in S

, otherwise we write that

x \notin S

. A set

A

is called a subset of

S

if each element of

A

is also an element of

S

, that is, if

a \in A

then also

a \in S

. To denote that

A

is a subset of

S

we write

A \subset S

. Now let

A

and

B

be subsets of

S

. If

A \subset B

and

B \subset A

then

A

and

B

are said to be equal and we write that

A = B

. The union of

A

and

B

is the set

A \cup B = {x \in S | x \in A or x \in B}

and the intersection of

A

and

B

is the set

A \cap B = {x \in S | x \in A and x \in B} .

A graphical representation of set unions and intersections are shown in Figure 1.1.

figures/set-operations.svg — Set intersection $A \cap B$ and union $A \cup B$

The empty set is the set that does not contain any elements and is denoted by

\emptyset

. We note that

\emptyset \subset S

for any set

S

. The sets

A

and

B

are disjoint if

A \cap B = \emptyset

. The complement of

A

S

is the set

S ∖ A = {x \in S | x \notin A},

in other words,

S ∖ A

consists of the elements in

S

not contained in

A

. We sometimes use the shorter notation

A^{c}

for

S ∖ A

when it is clear that it is the complement of

A

relative to

S

. The Cartesian product of

A

and

B

, denoted by

A \times B

, is the set of ordered pairs

(a, b)

where

a \in A

and

b \in B

, in other words,

A \times B = {(a, b) | a \in A, b \in B} .

A partition of a set

S

is a set

Π

whose elements are subsets of

S

such that

Π

does not contain the empty set, the union of the elements of

Π

equals

S

, and any two distinct elements of

Π

are disjoint. Lastly, for any set

S

, the power set of

S

is the set of all subsets of

S

, and is denoted by

P (S)

Let

A

and

B

be subsets of a set

S

. Show that

(A \cup B)^{c} = A^{c} \cap B^{c} .

We first show that

(A \cup B)^{c} \subset A^{c} \cap B^{c}

. If

x \in (A \cup B)^{c}

then by definition

x \notin (A \cup B)

and therefore

x \notin A

and

x \notin B

. Thus,

x \in A^{c}

and

x \in B^{c}

, that is,

x \in A^{c} \cap B^{c}

. Now suppose that

x \in A^{c} \cap B^{c}

, that is, suppose that

x \in A^{c}

and

x \in B^{c}

. Thus,

x \notin A

and

x \notin B

and thus

x \notin (A \cup B)

. By definition,

x \in (A \cup B)^{c}

and this proves that

A^{c} \cap B^{c} \subset (A \cup B)^{c}

We use the symbol

N

to denote the set of natural numbers, that is,

N = {1, 2, 3, 4, \dots} .

The set of integers is denoted by

Z

so that

Z = {\dots, - 3, - 2, - 1, 0, 1, 2, 3, \dots} .

The set of rational numbers is denoted by

Q = {\frac{p}{q} | p, q \in Z, q \neq 0} .

Notice that we have the following chain of set inclusions:

N \subset Z \subset Q .

We now review the most commonly used methods of proof. To that end, recall that a logical statement is a declarative sentence that can be unambiguously decided to be either true or false. A theorem is a logical statement that has been proved to be true using a sequence of true statements and deductive reasoning. Many theorems are usually written as a conditional statement of the form if

then

or symbolically

. The statement

is called the hypothesis or assumption and

is called the conclusion. Below are the main techniques used to prove the statement

Direct Proof: To prove the statement , assume that the statement is true and show by combining axioms, definitions, and earlier theorems that is true. This should be the first method you attempt.
Mathematical Induction: Covered in Section 1.2.
By Contraposition: Proving the statement by proving the logically equivalent statement $\text{not Q\Rightarrow\text{ not } P$}. Do not confuse this with proof by contradiction.
By Contradiction: To prove the statement by contradiction, one assumes that is false and then show that some contradiction results. Assuming that is false is to assume that is true and is false. Using these to latter assumptions, one attempts to derive at a contradiction of the form and not , where is some statement. One disadvantage with proof by contradiction is that the logical contradiction that one is seeking and not is not known in advance so that the goal of the proof is unclear. Proof by contradiction frequently gets confused with proof by contraposition in the following way (do not do this): To prove that , assume that is true and suppose that is not true. After some work using only the assumption that is not true you show that is not true and thus you say that there is a contradiction because you assumed that is true. What you have really done is proved the contrapositive statement. Thus, if you believe that you are proving a statement by contradiction, take a close look at your proof to see if what you have is a proof by contraposition.

In the following example, we use both proof by contradiction and proof by contraposition.

Prove that if

and

are consecutive integers then

is odd.

Assume that

and

are consecutive integers (i.e. assume

) and assume that

is not odd (i.e. assume not

). Since

is not odd then

for all integers

. However, since

and

are consecutive, and assuming without loss of generality that

, we have that

. Thus, we have that

for all integers

and also that

. Since

is an integer we have reached a contradiction. Hence, if

and

are consecutive integers then

is odd. Now we prove the statement by contraposition. Without loss of generality, suppose that

. Assume that

is even. Then there exists an integer

such that

and therefore

. Consequently,

Hence, since

is an integer,

and consequently

and

are not consecutive integers.

In general, if the statement

is true then the converse conditional statement

is not necessarily true. For example, the converse conditional statement in Example 1.1.2 is if

is odd then

and

are consecutive integers is easily shown to be false (e.g.,

and

). The conjoined statement

and

, alternatively written as

if and only if

or symbolically

, is called a biconditional statement. Thus, to prove that the biconditional statement

is true one must prove that both

and

are true.

Let

, and

be subsets of a set

. Prove that

if and only if

and

Exercises

Let

and

be subsets of a set

. Show that

if and only if

Find the power set of

Let

and let

. Find

Let

. Prove that if

is even then

is even. Do not use proof by contradiction.

Prove that if

and

are even natural numbers then

is even. Do not use proof by contradiction.

Prove that if

and

are rational numbers then

is a rational number. Do not use proof by contradiction.

Let

and

be natural numbers. Prove that

and

are odd if and only if

is odd. Do not use proof by contradiction.

Mathematical Induction

Mathematical induction is a powerful proof technique that relies on the following property of

Every non-empty subset of

contains a smallest element.

In other words, if

is a non-empty subset of

then there exists

such that

for all

. The smallest element of

is denoted by

. Thus,

and

for all

. We now state and prove the principle of Mathematical Induction.

Suppose that

is a subset of

with the following properties:

If then also .

Then

Suppose that

is a subset of

with properties (i) and (ii) and let

. Proving that

is equivalent to proving that

is the empty set. Suppose then by contradiction that

is non-empty. By the well-ordering principle of

has a smallest element, say it is

. Because

satisfies property (i) we know that

and therefore

. Now since

is the least element of

, then

(we know that

because

). But since

satisfies property (ii) then

, that is,

. This is a contradiction because we cannot have both

and

. Thus,

is the empty set, and therefore

Mathematical induction is frequently used to prove formulas or inequalities involving the natural numbers. For example, consider the validity of the formula

where

. In words, the identity

says that the sum of all the integers from

equals

. We use induction to show that this formula is true for all

. Let

be the subset of

consisting of the natural numbers that satisfy

, that is,

then

Thus,

is equal to the sum of all the integers from

. Hence,

is true when

and thus

. Now suppose that some

satisfies

, that is, suppose that

. Then we may write that

We will prove that the integer

also satisfies

. To that end, adding

to both sides of

we obtain

Now notice that we can factor

from the right-hand side and through some algebraic steps we obtain that

Hence,

also holds for

and thus

. We have therefore proved that

satisfies properties (i) and (ii), and therefore by mathematical induction

, or equivalently that

holds for all

Use mathematical induction to show that

holds for all

Let

be a constant. Use mathematical induction to show that

holds for all

Prove that if

then

for all

The statement is trivial for

. Assume that for some

it holds that

. Since

then

and therefore

Therefore,

, and the proof is complete by induction.

There is another version of mathematical induction called the Principle of Strong Induction which we now state.

Suppose that

is a subset of

with the following properties:

If then also .

Then

Do you notice the difference between induction and strong induction? It turns out that the two statements are equivalent, in other words, if

satisies either one of properties (i)-(ii) of induction or strong induction then we may conclude that

. The upshot with strong induction is that one is able to use the stronger condition that

to prove that

Exercises

Prove that

for all

Prove that

for all

Use induction to prove that if

has

elements then

has

elements. Hint: If

is a set with

elements, for instance

, then argue that

where

and

consists of subsets of

that contain

. How many sets are in

and how many are in

? And what is

? Explain carefully.

Functions

Let

and

be sets. A function from

is a rule that assigns to each element

one element

. The set

is called the domain of

and

is called the co-domain of

. We usually denote a function with the notation

, and the assignment of

is written as

. We also say that

is a mapping from

, or that

maps

into

. The element

assigned to

is called the image of

under

. The range of

, denoted by

, is the set

In the above definition of

, we use the symbol

as a short-hand for there exsits. By definition,

but in general we do not have that

, in other words, the range of a function is generally a strict subset of the function's co-domain.

Consider the mapping

defined by

The image of

under

. The range of

Consider the function

defined by

The set

of even numbers is an element of the co-domain

but is not in the range of

. As another example, the set

itself is not in the range of

Function's whose range is equal to it's co-domain are given a special name.

A function

is said to be a surjection if for any

there exists

such that

In other words,

is a surjection if

The function

defined by

is not a surjection. For example,

is clearly not in the range of

since

for all

. On the other hand,

is in the range of

since

. Is

in the range of

Consider the function

defined by

Prove that

is a surjection.

To prove that

is a surjection, we must show that for any element

(the co-domain), there exists

(the domain) such that

. Consider then an arbitrary

. Let

and thus clearly

. Moreover, it is clear that

and thus

. This proves that

is a surjection.

Notice that in Example 1.3.5, given any

there are many sets

such that

. This leads us to the following definition.

A function

is said to be an injection if no two distinct elements of

are mapped to the same element in

, in other words, for any

, if

then

In other words,

is an injection if whenever

then necessarily

The function

defined by

is not an injection. For example,

Consider again the function

defined by

This function is an injection. Indeed, if

then

and therefore

. Hence, whenever

then necessarily

and this proves that

is an injection.

Consider the function

defined by

an injection?

Consider the function

defined by

Show that

is an injection.

A function

is said to be a bijection if it is a surjection and an injection.

Suppose that

is an injection. Prove that the function

defined by

for

is a bijection.

By construction,

is a surjection. If

then

and then

since

is an injection. Thus,

is an injection and this proves that

is a bijection.

Prove that

defined by

is a bijection, where

Suppose that

is a bijection and define the function

as follows: for

let

be the (necessarily unique) element in

such that

. Notice that by definition,

. The function

is called the inverse of

and we write instead

. It is not hard to show that

is a bijection and that

. Given functions

and

, the composition of

and

is the function

defined as

and

are injections (surjections) then the composition

is an injection (surjection).

Assume that

and

are injections. To prove that

is an injection, suppose that

. Then by definition of

, it follows that

. Now since

is an injection then necessarily

and since

is an injection then necessarily

. Thus if

then

and this proves that

is an injection. Now suppose that

and

are surjections. To prove that

is a surjection, let

be arbitrary. Since

is a surjection, there exists

such that

. Since

is a surjection, there exists

such that

. Thus, for

we have that

. Hence, for arbitrary

there exists

such that

and this proves that

is a surjection.

The following result is then an immediate application of Theorem 1.3.14 and the definition of a bijection.

The composition of two bijections is a bijection.

Exercises

Consider the function

defined as

. Is

an injection? Is

a surjection?

Consider the function

defined as

. Is

an injection? Is

a surjection?

Consider the function

defined as

. Is

an injection? If

a surjection?

Let

be the function defined as

Prove that

is a bijection.

The sign of a rational number

is defined as

, where

is the absolute value of

, and

. For example,

and

. Prove that the function

defined as

is a bijection.

Countability

A non-empty set

is said to be finite if there is a bijection from

onto

for some

. In this case, we say that

contains

elements and we write

. If

is not finite then we say that

is infinite.

Let

be an injection. If

is an infinite set then

is an infinite set.

The proof is by contraposition. Suppose that

is a finite set containing

elements. Then there exists a bijection

. The function

defined as

for

is a bijection (Example 1.3.12) and therefore

is a bijection. Thus

is a finite set and completes the proof.

We now introduce the notion of a countable set.

Let

be a set.

The set is countably infinite if there is a bijection from onto .
The set is countable if is either finite or countably infinite.
The set is uncountable if is not countable.

Roughly speaking, a set

is countable if the elements of

can be listed or enumerated in a systematic manner. To see how, suppose that

is countably infinite and let

be a bijection. Then the elements of

can be listed as

Hence, although sets have no predetermined order, the elements of a countable set can be ordered.

The set

of odd natural numbers is countable. Recall that

is an odd positive integer if

for some

. A bijection

from

. The function

can be interpreted as a listing of the odd natural numbers in the natural way:

The natural numbers

are countable. A bijection

, i.e., the identity mapping.

The set of integers

is countable. A bijection

from

can be defined by listing the elements of

as follows:

To be more precise,

is the function

It is left as an exercise to show that

is indeed a bijection.

The set

is countable. There are many bijections from

but a particularly interesting one is the function defined as follows. Consider the family of lines

for

. There are

points on the line

, namely

for

, and we say that

is the

th point on the line

. The point

is contained in the line

where

. Thus, one way to enumerate the points in

is to assign to each

the number

obtained by adding all points on the lines

and adding the position of

on line

, namely

. Thus,

The function

is called the Cantor pairing function. Alternatively, we use a modified version of

which we call

and defined as

We now find a formula for the inverse of

which we call the Cantor snake. To write down the formula for

, we first let for each

and we note that

is the smallest integer such that

. We then set

a then

We note that the point

is on the line

with

. The range of

The sequence of pairs

generated by

for

are shown in Figure 1.2.

figures/cantor-snake.svg — The image of the Cantor snake

Suppose that

is a bijection. Prove that

is countable if and only if

is countable.

Suppose that

is countable. Then by definition there exists a bijection

. Since

and

are bijections, the composite function

is a bijection. Hence,

is countable. Now suppose that

is countable. Then by definition there exists a bijection

. Since

is a bijection then the inverse function

is also a bijection. Therefore, the composite function

is a bijection. Thus,

is countable.

As the following theorem states, countability, or lack thereof, can be inherited via set inclusion.

Let

and

be sets and suppose that

If is countable then is also countable.
If is uncountable then is also uncountable.

To prove (i), let

be a countable set and let

be a bijection. Define the mapping

. By Example 1.3.12,

is a bijection. Therefore, since

is a subset of

, and thus countable, then

is countable. The proof of (ii) is left as an exercise.

Let

be the set of odd natural numbers. In Example 1.4.3, we proved that the odd natural numbers are countable by explicitly constructing a bijection from

. Alternatively, since

is countable and

then by Theorem 1.4.8

is countable. More generally, any subset of

is countable.

is known to be a finite set then by Definition 1.4.2

is countable, while if

is infinite then

may or may not be countable (we have yet to encounter an uncountable set but soon we will). To prove that a given infinite set

is countable we could use Theorem 1.4.8 if it is applicable but otherwise we must use Definition 1.4.2, that is, we must show that there is a bijection from

, or equivalently from

. However, suppose that we can only prove the existence of a surjection

from

. The problem might be that

is not an injection and thus not a bijection. However, the fact that

is a surjection from

somehow says that

is no larger than

and gives evidence that perhaps

is countable. Could we use a surjection

to construct a bijection

? Or, what if instead we had an injection

; could we use

to construct a bijection

? The following theorem says that it is indeed possible to do both.

Let

be a set.

If there exists an injection then is countable.
If there exists a surjection then is countable.

(i) Let

be an injection. Then the function

defined by

for

is a bijection. Since

then

is countable. Therefore,

is countable also. (ii) Now let

be a surjection. For

let

. Since

is a surjection,

is non-empty for each

. Consider the function

defined by

. Then

for each

. We claim that

is an injection. Indeed, if

then

and thus

, and the claim is proved. Thus,

is an injection and then by (i) we conclude that

is countable.

We must be careful when using Theorem 1.4.10; if

is known to be an injection then we cannot conclude that

is countable and similarly if

is known to be a surjection then we cannot conclude that

is countable.

In this example we will prove that the union of countable sets is countable. Hence, suppose that

and

are countable. By definition, there exist bijections

and

. Consider the function

defined as follows:

We claim that

is a surjection (Loosely speaking, if

and

, then the function

lists the elements of

.). To see this, let

. If

then

for some

. Then

. If on the other hand

then

for some

. Then

. In either case, there exists

such that

, and thus

is a surjection. By Theorem 1.4.10, the set

is countable. This example can be generalized as follows. Let

be countable sets and let

. Then

is countable. To prove this, we first enumerate the elements of each

as follows:

Formally, we have surjections

for each

. Consider the mapping

defined by

It is clear that

is a surjection. Since

is countable, there is a surjection

, and therefore the composition

is a surjection. Therefore,

is countable.

The following theorem is perhaps surprising.

The set of rational numbers

is countable.

Let

be the set of all positive rational numbers and let

be the set of all negative rational numbers. Clearly,

, and thus it is enough to show that

and

are countable. In fact, we have the bijection

given by

, and thus if we can show that

is countable then this implies that

is also countable. In summary, to show that

is countable it is enough to show that

is countable. To show that

is countable, consider the function

defined as

By definition, any rational number

can be written as

for some

. Hence,

and thus

is in the range of

. This shows that

is a surjection. Now, because

is countable, there is a surjection

and thus

is a surjection. By Theorem 1.4.10, this proves that

is countable and therefore

is countable.

We end this section with Cantor's theorem named after mathematician Georg Cantor (1845-1918). Cantor is considered as the creator of set theory. Originally interested in analytical problems having as their root problems in physics, and in particular in characterizing solutions to equations describing heat conduction, Cantor discovered that infinite sets come in many possible sizes. One of Cantor's fascinating discoveries, which initially were very controversial at the time, led to the following theorem \cite{GC:91}.

For any set

, there is no surjection of

onto the power set

Suppose by contradiction that

is a surjection. By definition, for each

is a subset of

. Consider the set

Since

is a subset of

then

. Since

is a surjection, there exists

such that

. One of the following must be true: either

. If

then

by definition of

. But

and thus we reach contradiction. If

then by definition of

we have

. But

and thus we reach a contradiction. Hence, neither of the possibilities are true, and thus we have reached an absurdity. Hence, we conclude that there is no such surjection

Cantor's theorem implies that

is uncountable. Indeed, if we take

in Cantor's Theorem then there is no surjection from

, and thus certainly no bijection from

. In summary:

The set

is uncountable.

Exercises

Let

and

be infinite sets. Prove that if

is a bijection then

is uncountable if and only if

is uncountable. Do not use proof by contradiction.

In this exercise you will provide another proof that

is countable.

Prove that is odd for each .
Consider the function defined as . Prove that is an injection. Hint: Use part (a) in some way.
Explain how part (b) proves that is countable.

Prove that if

and

are countably infinite then

is countable.

Recall that a sequence

of numbers is an infinite list

where each element

is a number (We will cover sequences in detail but you are already familiar with them from calculus.). Let

be the set of sequences whose elements are either

, in other words,

For example, the following sequences are elements of the set

Give two non-trivial examples of functions from to .
Consider the function defined as where is the power set of . Hence, takes a sequence and outputs the indices where is equal to . For example: Prove that is a bijection.
Combine part (b), Exercise 1.4.1, and Cantor's theorem to thoroughly explain whether is countable or uncountable.