1.

Functions
Functions, as we defined, are a special case of relations. Recall that a binary
relation R ⊆ S1 × S2 is a (partial) function if for each x ∈ S1, there exists (at most)
one y ∈ S2 such that (x, y) ∈ R.

Predomain, codomain, domain and range.

For a functional relation Rf ⊆ S1 × S2, the set S1 is called the pre-domain and S2 is
called the co-domain of the function. We usually write f : S1 → S2 instead of
Rf ⊆ S1 × S2 and write y = f (x) when (x, y) ∈ Rf . We write predom( f ) = S1 and
codom( f ) = S2; the relation Rf is often referred to as the “extension” or graph of
the function f.

A partial function need not have a value y = f (x) for each x ∈ S1.
We say that function f is defined at x ∈ S1 if there exists a y ∈ S2 such that
(x, y) ∈ Rf . The domain of a partial function f : S1 → S2 is defined as
dom( f ) = {x ∈ S1 | ∃y ∈ S2 : y = f (x)}, i.e., the elements x ∈ S1 for which
f (x) ∈ S2 is defined. Note that dom( f ) ⊆ S1 = predom( f ).
The range of a partial function f : S1 → S2 is defined as
range( f ) = {y ∈ S2 | ∃x ∈ S1 : y = f (x)}, i.e., the elements y ∈ S2 such that
y = f (x) for some x ∈ S1. Note that range( f ) ⊆ S2 = codom( f ) . .

Total function. If the functional relation Rf is total, i.e., for each x ∈ S1 there
exists a y ∈ S2 such that y = f (x), we call f a total function and
dom( f ) = S1 = predom( f ) .

Mappings and notation. We will use the notation of mappings “x ↦ y” to

indicate that the element x ∈ S1 is mapped by a function f : S1 → S2 to the element
y ∈ S2. Note that the “mapping” arrow “↦” tells us how elements are mapped by a
function, and notice the little vertical bar on the left of the arrow. In contrast,
S1 → S2 is a set-level construction that depicts a functional relation between S1, S2.

Function Restriction. Suppose f : S1 → S2 is a function. Let A ⊆ S1. Then the

restriction of function f to (pre)domain A, written as f |A is defined as the mapping
that associates f (x) to each element x ∈ A. (f |A (x) = f (x) for all x ∈ A). That is
f |A behaves just as function f would but takes as its predomain only the set A.

Onto. If a function f (namely, its functional relation Rf) is onto, i.e., for each y ∈ S2
there exists an x ∈ S1 such that y = f (x), then we call f an onto (surjective, epi)
function and range( f ) = S2 = codom( f ) .

(1-1 or injection). A partial function f : S1 → S2 is called 1-1 (injective, mono) if

whenever f (x1) = f (x2) ∈ S2, then x1 = x2 ∈ S1.

(Cardinality) The cardinality of set S2 (written | S2 | ) is at least as great as that of

set S1 (i.e., | S1 | ≤ | S2 | ) if there exists a 1-1 total function f : S1 → S2.
Page 1 of 5
Exercise: If S1 ⊆ S2 then | S1 | ≤ | S2 | .
Exercise. | 0 | ≤ | S | for any set S.

(Bijection) A function f : S1 → S2 is called a bijection if it is both 1-1 and onto.

Note that a bijection has a natural inverse function, written f − or more commonly
f −1, whose graph is defined relationally as the symmetric inverse Rf− of relation Rf.

Exercise: Show that the identity function on any set idS : S → S defined by the
mapping “x ↦ x” is (i) total; (ii) 1-1; (iii) onto and (iv) a bijection.

Two sets S1, S2 are said to be in bijection with each other (written S1 ≅ S2) if there
exists a bijective function f : S1 → S2. Note that if S1 ≅ S2, then | S1 | = | S2 |

Exercise. Recall the set 1, with its canonical element written as ().
[Note: this is the empty tuple, and resembles writing a 0]

Show that S × 1 ≅ S ≅ 1 × S

Natural numbers and Peano’s Axioms:

The set of Natural numbers ℕ is an infinite set defined inductively in terms of two
constructors: (zero) 0 and (successor) s( _). Natural numbers can be defined by the
following Peano’s Axioms.

1. (Base constant Zero) 0 ∈ ℕ.

2. (Equality-Reflexive) For all x ∈ ℕ, x = x.
3. (Equality-Symmetric) For all x, y ∈ ℕ, if x = y then y = x
4. (Equality-Transitive) For all x, y, z ∈ ℕ, if x = y and y = z then x = z
5. (Closure-Equality) For all x, y, if x ∈ ℕ, and x = y then y ∈ ℕ.
6. (Closure-Successor) For all x ∈ ℕ, s(x) ∈ ℕ.
7. (Successor-Injective) For all x, y ∈ ℕ, if s(x) = s(y) then x = y.
8. (Zero-not-Successor) For all x ∈ ℕ, s(x) ≠ 0.
9. (Induction-Set) Let A ⊆ ℕ. If (i) 0 ∈ A; and (ii) for all x ∈ ℕ: if x ∈ A then
s(x) ∈ A; then A = ℕ.
(9’) (Induction-Pred) For any unary predicate P: If (i) P(0); and (ii) for all x ∈ ℕ:
if P(x) implies P(s(x)); then for all x ∈ ℕ: P(x).

Axioms 1 and 6 define the constructors, Axioms 2-5 characterise equality and
closure of the set with respect to it, and Axiom 7 and 8 define (non)equality
properties of the constructors. Axiom 9 is an induction scheme. (Axiom 9’) is an
alternative way to state Axiom 9 on predicates.

Finite and Denumerable Sets.

A prefix of cardinality n of the natural numbers ℕ is defined as the set

ℕn = {0,1,…(n − 1)}.

Page 2 of 5
 Let N′ ⊆ ℕ . A set A is called denumerable or countable if there exists a 1-1 total
function f : A → N′, i.e., there is an injective mapping from all of A to a subset of
the natural numbers.

A finite set is a set whose cardinality is equal to some n ∈ ℕ. Clearly every finite set
of size n ∈ ℕ has a 1-1 total function mapping to ℕn.
Note that every natural number is finite, but the set of natural numbers ℕ is
denumerably infinite (countably infinite). ℕ is not in bijection with any ℕn
for n ∈ ℕ.
Every finite set is trivially denumerable.

Finite-domain functions. A function f : S1 → S2 is called a finite-domain

function if its domain is finite. That is dom( f ) is a finite subset of S1. We write
f : S1 →fin S2 to highlight dom( f ) is finite.

Function composition is a special case of relational composition where the

relations involved are (partial) functions: Suppose f : S1 → S2, and g : S2 → S3
are (partial) functions. Then their composition, which we will write as
f ; g : S1 → S3 is defined as the mapping x ↦ g( f (x)) provided element
g( f (x)) ∈ S3 is defined (that is, there must exist y = f (x) ∈ S2, and z = g(y) ∈ S3).

Exercise: Show that function composition is associative, i.e., if f : S1 → S2,

g : S2 → S3 and h : S3 → S4, then f ; (g; h) = ( f ; g); h : S1 → S4.

Exercise: Show that dom( f ; g) = {x ∈ dom( f ) | f (x) ∈ dom(g)} and

range( f ; g) = {g(y) ∈ range(g) | y ∈ range( f ) ∩ dom(g)}.

Exercise: Show that total functions are closed under composition. That is, if
f : S1 → S2 and g : S2 → S3 are total functions, then so is f ; g : S1 → S3.

Exercise: Show that 1-1 functions are closed under composition. That is, if
f : S1 → S2 and g : S2 → S3 are 1-1 functions, then so is f ; g : S1 → S3.

Exercise: Show that onto functions are closed under composition. That is, if
f : S1 → S2 and g : S2 → S3 are onto functions, then so is f ; g : S1 → S3.

Exercise: Show that bijections are closed under composition. That is, if
f : S1 → S2 and g : S2 → S3 are bijections, then so is f ; g : S1 → S3.

Exercise: Show that finite-domain functions are closed under composition. That
is, if f : S1 →fin S2 and g : S2 →fin S3 are finite-domain functions, then so is
f ; g : S1 →fin S3.

Page 3 of 5


Some denumerable sets

Proposition: (i) The set of even natural numbers is denumerable but not finite.
(ii) The set of odd natural numbers is denumerable but not finite.
(iii) The cardinalities of the even naturals (respectively, odd naturals) is the same as
that of ℕ.

Proof hint: (Trivial) Define a total 1-1 function from the even (respectively odd)
natural numbers to a subset of the naturals. (More interesting) Also show that the
cardinality of these sets is at least that of the natural numbers by showing a total 1-1
function from the naturals to each of them.

Proposition: The set of integers ℤ is denumerable (countably infinite).

Proof hint: Define a total 1-1 function from ℤ to (a subset of) ℕ.

Proposition: (First diagonal argument — Cauchy) The set of pairs of natural

numbers ℕ × ℕ is denumerable (countably infinite).
Proof hint: Define a total 1-1 function from ℕ × ℕ to (a subset of) ℕ.

Proposition: (Corollary) The set of pairs of integers ℤ × ℤ is denumerable

(countably infinite).

Proposition: (Corollary) The set of rational numbers ℚ is denumerable

(countably infinite).
Proof: ℚ = {m /n | m, n ∈ ℤ ∧ n > 0 ∧ m, n co-prime}.
Consider f : ℚ → ℤ × ℤ defined by the mapping (for q ∈ ℚ = m /n), q ↦ (m, n).

Proposition: (Corollary) Let A be a denumerable set. Let us define

A0 ≅ 1
A s(n) ≅ A × A n
For each n ∈ N, the set A n of lists over A of length n is a denumerable set.
Proof Hint: Proof by induction on n ∈ N.

Theorem (Cauchy): The denumerable union of denumerable sets is denumerable.

Proposition: (Corollary) Let A be a denumerable set. Let us define

An
⋃
A* =
n≥0
Then the set A* of all lists (sequences) built over elements from A is a denumerable
set.

Proposition: The cardinality | ℝ | of the set of real numbers ℝ is the same as that
of any open interval (a, b), in particular (0,1) or (−π /2, π /2).

Theorem (Cantor: Second Diagonal Argument): The set of real numbers ℝ is not
denumerable.
Proof by Cantordiction.
We rely on the fact that if any subset of a ℝ is not denumerable, then ℝ is not
denumerable.

Page 4 of 5
 (1) Assume (0,1) is denumerable.
(2) Consider the set D of all non-terminating decimals in (0,1). D is a subset of
(0,1), and so must be denumerable (a subset of a denumerable set is also
denumerable). That is, there is an total 1-1 function e : D → ℕ.
Therefore we can write down all the non-terminating decimal elements of (0,1),
i.e., the elements of D, in some enumerated order as a series of “rows”:
r0 = d00 d01…d0j…
r1 = d10 d11…d1j…
⋮⋮⋮ ⋮…⋮…
ri = di0 di1… dij…
⋮⋮⋮ ⋮…⋮…
where each of the rows (ri ) represents a non-terminating decimal of the form
0.di0 di1… dij… [ Note ri ∈ (0,1), and if e(x) = i, then x is represented as
the i th row ri.]

(Note that all finite decimals, which have finitely many digits followed by an
infinite number of 0’s at the end can instead be represented by an
indistinguishable form “in the limit”— with one less in the last non-zero digit
and then an infinite series of 9’s. For example, instead of 0.5 let us write
0.49999…)

(Note: we don’t know — and don’t care — what the order of enumeration is.
It is not at all likely to be the usual < ordering).

Now consider a number represented as r′ = r′0r′1…r′i… such that for each

j ∈ ℕ: r′j ≠ djj ∧ r′j ≠ 0. (The second conjunct is to ensure we do not get a
terminating decimal). That is, the r′j is different from the “diagonal digit” djj.
[ Note: There are many many such choices for r′. ]

Claim: r′ ∈ D. By construction, r′ = r′0r′1…r′i… is a non-terminating

decimal in (0,1).

Therefore by (2), r′ = rk for some k ∈ ℕ, since D is assumed denumerable,

and so e(r′) = k for some k ∈ ℕ.

But r′ ≠ rk because its k th digit r′k ≠ dkk, which is k th digit of the rk. (Note
that by construction, for each j ∈ ℕ, the j th digit r′j ≠ djj).
Therefore r′ ∈ D but e(r′) ∉ ℕ. So e is either not total, or not 1-1.

So D is not denumerable. This contradicts (2), and thus contradicts

Assumption (1). So ℝ is not denumerable.

Page 5 of 5