An Introduction to Elementary Set Theory, Bezhanishvili & Landreth, New Mex. State Univ.

The question we will examine is whether A is a member of itself.

Exercise 2.24.

1. First assume that A ∈ A and conclude that A ∈

/ A. Justify your argument.

2. Next assume that A ∈

/ A and conclude that A ∈ A. Justify your argument.

3. What can you conclude from (1) and (2)? Explain.

4. Discuss why Russell’s paradox contradicts Frege’s program.

5. How would you resolve the situation? Explain.

3 Functions, one-to-one correspondences, and cardinal numbers

So far in this project we have studied such basic relations between sets as membership, subset, and
equality relations. We have also studied basic operations on sets such as union, intersection, set
difference, Cartesian product, and powerset. In the second half of the project we will discuss the
“size” of a set. We have already encountered sets of large and small sizes. Some sets that we have
encountered were finite and some were infinite. Our next goal is to formalize the concept of the
size of a set. As we will see, this can be done by means of functions—one of the key concepts in
mathematics.
We will learn about functions, one-to-one and onto functions, one-to-one correspondences, and
how they allow us to formalize the concept of the size of a set. A formalization of the size of a set is
known as the cardinality of a set. We will discuss what it means for two sets to have the same size,
and study how to compare the sizes of different sets. We will introduce countable sets and show
that many sets are countable, including the set of integers and the set of rational numbers. We
will also discuss Cantor’s diagonalization method which allows us to show that not every infinite
set is countable. This will yield infinite sets of different sizes. In particular, we will show that the
set of real numbers is not countable. We will also examine the cardinal number ℵ0 , the first in
the hierarchy of infinite cardinal numbers, and obtain a method that allows us to create infinitely
many infinite cardinal numbers.

3.1 Functions
You have probably already encountered functions from real numbers to real numbers in the first
course of calculus. More generally, given two sets A and B, a function from A to be B is a rule
associating with each element of A one and only one element of B. This is how Dedekind defines
a function. Note that he refers to functions as transformations (and to sets as systems).

∞∞∞∞∞∞∞∞

By a transformation φ of a system S we understand a law according to which to every determinate

element s of S there belongs a determinate thing which is called the transform of s and denoted by
φ(s); we say also that φ(s) corresponds to the element s, that φ(s) results or is produced from s by
the transformation φ, that s is transformed into φ(s) by the transformation φ. [10, p. 50]

∞∞∞∞∞∞∞∞

11

27
 MAT2611/101/0/2024

An Introduction to Elementary Set Theory, Bezhanishvili & Landreth, New Mex. State Univ.

When there is a function f from A to B, we write f : A → B. The set A is referred to as the

domain of f , and the set B is referred to as the codomain of f . Since the function f associates
with each a ∈ A a unique b ∈ B, we say that f maps a to b and write f (a) = b. A convenient
way to think about a function f : A → B is as the set of ordered pairs (a, b), where a ∈ A, b ∈ B,
and f maps a to b. It follows from the definition of a function that we cannot have two ordered
pairs (a, b) and (a, c) with b 6= c. Thus, we can think of functions from A to B as subsets F of
the Cartesian product A × B which satisfy the following property: For each a ∈ A there exists a
unique b ∈ B such that (a, b) ∈ F .
_______
Exercise 3.1. Are the following functions? Justify your answer.
1. f (x) = x2 with domain and codomain R.

2. g(x) = 2x + 1 with domain and codomain Q.

3. h(x) = ±x with domain and codomain Z.

√
4. u(x) = x with domain and codomain N.
Exercise 3.2. Write each of the following functions as a set of ordered pairs.
1. f : R → [−1, 1] defined by f (x) = cos(x).

2. g : R → R defined by g(x) = 300x.

3. h : R+ → R defined by h(x) = ln(x). Here and below R+ = {x ∈ R : x > 0}.

For a function f : A → B, we call the set of all values of f the range or image of f . Thus, the
image of f is the set
Im(f ) = {b ∈ B : b = f (a) for some a ∈ A}.
Exercise 3.3. Consider the function f = {(1, 2), (2, 3), (3, 3), (4, 5), (5, −1), (6, 2)}. Identify the
domain and image of f .

3.2 Images and inverse images

Let f : A → B be a function, S ⊆ A, and T ⊆ B. The image of S with respect to f is the set
of those elements of B which the elements of S are mapped to. Therefore, the image of S with
respect to f is the set
f (S) = {f (s) : s ∈ S}.
On the other hand, the inverse image of T with respect to f is the set of those elements of A that
are mapped to some element of T . Thus, the inverse image of T with respect to f is the set

f −1 (T ) = {a ∈ A : f (a) ∈ T }.

Exercise 3.4. For each of the following functions determine the image of S = {x ∈ R : 9 ≤ x2 }.
1. f : R → R defined by f (x) = |x|.

2. g : R → R+ defined by g(x) = ex .

3. h : R → R defined by h(x) = x − 9.
Exercise 3.5. For each of the following functions determine the inverse image of T = {x ∈ R : 0 ≤
x2 − 25}.

12

28
An Introduction to Elementary Set Theory, Bezhanishvili & Landreth, New Mex. State Univ.

1. f : R → R defined by f (x) = 3x3 .

2. g : R+ → R defined by g(x) = ln(x).

3. h : R → R defined by h(x) = x − 9.

3.3 When are two functions equal?

Let f, g : A → B be two functions. We say that f equals g and write f = g if f (a) = g(a) for each
a ∈ A.

Exercise 3.6. Let f : Z → Z be defined by f (a) = 2a2 − a and g : Z → Z be defined by

g(x) = x(2x − 1). Determine whether f is equal to g. Justify your answer.

3.4 Composition
Given two functions f : A → B and g : B → C, we can produce a new function h : A → C by
composing f and g. This is how Dedekind defines the composition of two functions.

∞∞∞∞∞∞∞∞

If φ is a transformation of a system S, and ψ a transformation of the transform S 0 = φ(S), there

always results a transformation θ of S, compounded out of φ and ψ, which consists of this that to every
element s of S there corresponds the transform

θ(s) = ψ(s0 ) = ψ(φ(s)),

where again we have put φ(s) = s0 . This transformation θ can be denoted briefly by the symbol ψ.φ or
ψφ, the transform θ(s) by ψφ(s) where the order of the symbols φ, ψ is to be considered... [10, p. 52]

∞∞∞∞∞∞∞∞

Thus, if f : A → B and g : B → C are two functions, then their composition is defined as the
function h : A → C such that h(a) = g(f (a)) for each a ∈ A. We denote the composition of f and
g by g ◦ f . Dedekind goes on to show that for any functions f : A → B, g : B → C, and h : C → D,
we have h ◦ (g ◦ f ) = (h ◦ g) ◦ f .

∞∞∞∞∞∞∞∞

If now χ signifies a transformation of the system ψ(s0 ) = ψφ(s) and η the transformation χψ of
the system S 0 compounded out of ψ and χ, then is χθ(s) = χψ(s0 ) = η(s0 ) = ηφ(s); therefore the
compound transformations χθ and ηφ coincide for every element s of S, i.e., χθ = ηφ. In accordance
with the meaning of θ and η this theorem can finally be expressed in the form

χ.ψφ = χψ.φ,

and this transformation compounded out of φ, ψ, χ can be denoted briefly by χψφ. [10, pp. 52–53]

∞∞∞∞∞∞∞∞

In the next exercise we examine Dedekind’s proof.

______
Exercise 3.7. Let f : A → B, g : B → C, and h : C → D be functions.

1. State what you need to show to conclude that h ◦ (g ◦ f ) = (h ◦ g) ◦ f .

13

29
 MAT2611/101/0/2024

An Introduction to Elementary Set Theory, Bezhanishvili & Landreth, New Mex. State Univ.

2. Consider now some a ∈ A. Calculate h((g ◦ f )(a)) and (h ◦ g)(f (a)). Are they equal?
3. Use your solutions to (1)–(2) to conclude that h ◦ (g ◦ f ) = (h ◦ g) ◦ f .
Let f and g be functions with the same domain and codomain. Then we can form g ◦ f and
f ◦ g, and both of these functions have the same domain and codomain as f and g. In the next
exercise we examine whether the functions g ◦ f and f ◦ g have to be equal.
Exercise 3.8. Let f, g : A → A be functions with the same domain and codomain A.
1. Give a brief justification of why g ◦ f, f ◦ g : A → A both have the same domain and codomain
A.
2. Either give a proof that g◦f and f ◦g are equal or show that they are not equal by constructing
a counterexample.
One of the simplest functions is the so-called identity function. This is how Dedekind defines
it.
∞∞∞∞∞∞∞∞
The simplest transformation of a system is that by which each of its elements is transformed into
itself; it will be called the identical transformation of the system. [10, p. 50]
∞∞∞∞∞∞∞∞
In other words, the identity function on a set A is the function iA : A → A defined by iA (a) = a
for each a ∈ A.
Exercise 3.9. Let f : A → B be a function.
1. Show that for the identity function iA on A we have f ◦ iA = f .
2. Show that for the identity function iB on B we have iB ◦ f = f .

3.5 One-to-one and onto functions, one-to-one correspondences

We already encountered functions f : A → B that map different elements of A to the same element
of B. For example, the absolute value function of Exercise 3.4 has this property. We say that f is a
one-to-one function (or an injective function) if f maps different elements of A to different elements
of B. Thus, f is one-to-one if for each a1 , a2 ∈ A, from a1 6= a2 it follows that f (a1 ) 6= f (a2 ).
Exercise 3.10. Let f : A → B be a function. Show that the following two conditions are equivalent:
1. f is one-to-one.
2. For each a1 , a2 ∈ A, whenever f (a1 ) = f (a2 ), then a1 = a2 .
In fact, both of these conditions are equivalent to a third condition stating that S = f −1 (f (S))
for each S ⊆ A. But this is a little more challenging to prove. (Try!)
We also encountered functions f : A → B such that the image of f is a proper subset of the
codomain of f . Again, the absolute value function of Exercise 3.4 has this property. We say that
f is an onto function (or a surjective function) if the image of f equals the codomain of f . Thus,
f is onto if for each b ∈ B there exists at least one a ∈ A such that f (a) = b. One can show that
f is onto if and only if T = f (f −1 (T )) for each T ⊆ B. This is a little more challenging to prove.
(Give it a try!)
Let f : A → B be a function. If it happens that f is both one-to-one and onto, then we say
that f is a one-to-one correspondence (or a bijection) between A and B.

14

30
An Introduction to Elementary Set Theory, Bezhanishvili & Landreth, New Mex. State Univ.

Exercise 3.11. Consider the following two functions:

1. f : R → R defined by f (x) = 4x − 15.

2. g : R → R defined by f (x) = 15x3 .

Prove that both f and g are one-to-one correspondences.

Let f : A → B be a one-to-one correspondence. Then to each b ∈ B there corresponds a unique

a ∈ A such that f (a) = b. We define f −1 : B → A by

f −1 (b) = the unique a such that f (a) = b.

Exercise 3.12. Let f : A → B be a one-to-one correspondence.

1. Prove that f −1 is a function.

2. Prove that f −1 is one-to-one.

3. Prove that f −1 is onto.

4. Conclude that f −1 : B → A is a one-to-one correspondence.

Exercise 3.13. Let f : A → B be a one-to-one correspondence. By Exercise 3.12, f −1 : B → A is

also a one-to-one correspondence.

1. Prove that f −1 ◦ f = iA .

2. Prove that f ◦ f −1 = iB .

3.6 Set equivalence

We are finally in a position to give a formal definition of the size of a set and to compare different
sizes of sets. Informally speaking, if f : A → B is a one-to-one function, then since different
elements of A are mapped to different elements of B, the size of B is at least as large as the size of
A. On the other hand, if f is onto, then since each element in B has at least one element in A that
is mapped to it, the size of B is no greater than the size of A. Thus, one-to-one correspondences
provide us with a means to compare the sizes of sets. This key observation of Cantor led him to the
notion of two sets being equivalent. Let us read how Cantor defines that two sets are equivalent.

∞∞∞∞∞∞∞∞

We say that two aggregates M and N are “equivalent,” in signs

M ∼N or N ∼ M,

if it is possible to put them, by some law, in such a relation to one another that to every element of
each one of them corresponds one and only one element of the other. [6, p. 86]

∞∞∞∞∞∞∞∞

Next Cantor states that each set is equivalent to itself, and that if a set is equivalent to two
other sets, then the two sets are also equivalent.

15

31