11 MATH 131AH notes

3. R ELATIONS AND FUNCTIONS

Once the axioms of set theory are in place, we can review some elementary albeit very
useful constructions that these axioms enable. To make out notations easier, we will
henceforth abandon our convention that all sets be written using the capital letters.

3.1 Cartesian product.

Given two sets A and B, a natural object to consider is the set of pairs px, yq with the
first taken from A and the second from B. This is formalized using the notion of their
Cartesian product,
(
A ˆ B :“ px, yq P P pP pA Y Bqq : x P A, y P B , (3.1)
in which px, yq denotes an ordered pair that, in set theory, is defined as
(
px, yq :“ txu, tx, yu , (3.2)
(This is sometimes called the Kuratowski pair.) Here the set on the right exists by Pairset
Axiom. An exercise in the use of Axiom of Extensionality shows:
Lemma 3.1 Let A and B be sets. Then
@x, x̃ P A @y, ỹ P B : px, yq “ px̃, ỹq ô px “ x̃ ^ y “ ỹq. (3.3)
In particular, the pair identifies its entries uniquely. The Cartesian product A ˆ B is a set
by Axiom of Separation.
The construction of the Cartesian product can naturally be iterated to construct the
Cartesian product of three, four, etc sets. The problem is that order of operation matters,
at least as far as the above definition is concerned.
î To demonstrate this, given three sets
A, B and C and abbreviating D :“ P pP pP p tA, B, Cuqqq, the above gives
! ( )
A ˆ pB ˆ Cq :“ txu, ttyu, ty, zuu P D : x P A ^ y P B ^ z P C (3.4)
while

pA ˆ Bq ˆ C
! ( )
:“ ttxu, ttxu, tx, yuu, tttxu, ttxu, tx, yuuu, zu P D : x P A ^ y P B ^ z P C (3.5)

Yet, both sets should intuitively give the set of all triplets px, y, zq and thus describe the
same object modulo identification. This identification requires proving that
( (
txu, ttyu, ty, zuu ބ ttxu, ttxu, tx, yuu, tttxu, ttxu, tx, yuuu, zu . (3.6)
defines a bijection of (3.4) onto (3.5); thus showing that the Cartesian product is associa-
tive. Once this is done, we drop the parentheses and write the “result” as A ˆ B ˆ C.
Unfortunately, any specific use of the triple product still requires specifying which of
the two sets we refer to, and the issues with the identification become only worse when
more sets are involved in the product. So we will ultimately abandon this approach and
come up with a unified definition of the Cartesian product of any number of sets that is
void of these complications. For that we need the concept of a function which is in turn
a special case of a relation, which is, however, based on the definition in (3.1).

Preliminary version (subject to change anytime!) Typeset: January 19, 2023

MATH 131AH notes 12

3.2 Relations.

With the Cartesian product in hand, we can put foward:

Definition 3.2 Given sets A and B, a relation on A and B is a subset R Ñ A ˆ B. We say
that x P A is in relation to y P B, with the notation xRy, if the pair px, yq lies in R, i.e.,
xRy :“ px, yq P R. (3.7)
If B “ A, we say that R Ñ A ˆ A is a relation on A.
An example of a relation is the set-inclusion Ñ on the power set P pAq of a set A. To
describe this (and similar) relations formally, we give:
Definition 3.3 Let A be a set and R Ñ A ˆ A a relation on A. We say that R is
‚ reflexive, if @x P A : xRx,
‚ antisymmetric, if @x, y P A : xRy ^ yRx ñ x “ y, and
‚ transitive, if @x, y, z P A : xRy ^ yRz ñ xRz.
A relation which is reflexive, antisymmetric and transitive is called a partial order.
We leave it to homework for the reader to prove:
Lemma 3.4 For any sets, the subset relation Ñ on P pAq is a partial order.
Perhaps more familiar example of a relation that is reflexive, antisymmetric and tran-
sitive is the inequality § on the number sets N, Z, Q and R (but not C). As we will see
when we construct these number sets from the foundations of set theory, the inequality
relation § will in fact be induced by Ñ applied to suitable sets.
In other to define our next frequent example of a relation, we put forward:
Definition 3.5 A relation R on a set A is said to be symmetric if
@x, y P A : xRy ô yRx. (3.8)
Note that a symmetric relation need not be reflexive because we do not require xRx
to actually hold. Nor are all pairs required to be in relation; all what symmetry says that
if xRy then also yRx and vice versa. Also note that not being symmetric does not mean
being antisymmetric, and vice versa. The role of symmetry is seen from:
Definition 3.6 A relation „ on a set A that is reflexive, symmetric and transitive is
called equivalence. For each x P A, the set
rxs :“ ty P A : y „ xu (3.9)
is said to be the equivalence class of x.
The proof of the following lemma has been relegated to homework:
Lemma 3.7 Let „ be an equivalence relation on a set A. Then
@x, y P A : rxs X rys ‰ H ñ rxs “ rys (3.10)
This means that two equivalence classes are either disjoint or equal. Any element
z P rxs is called a representative of rxs. In particular, x is a representative of rxs.

Preliminary version (subject to change anytime!) Typeset: January 19, 2023

13 MATH 131AH notes

An example of an equivalence relation is the equality “, which is reflexive, symmetric

and transitive. This is a very fine version of equivalence because (by Axiom of Exten-
sionality) each equivalence class contains exactly one element; i.e., @x P A : rxs “ txu. To
give a more representative example, consider the following:
Lemma 3.8 Writing Z for the set of integers and denoting by “¨” the standard operation of
multiplication on Z, let (
A :“ pm, nq P Z ˆ Z : n ‰ 0 (3.11)
and let „ be the relation on A defined as
pm, nq „ pm,
r nrq :“ m ¨ n
r“m
r ¨n (3.12)
Then „ is an equivalence.

Proof. Symmetry and reflexivity are checked readily; all that needs a bit of work is tran-
sitivity. Assume pm, nq „ pm,
r nrq and pm,
r nrq „ pm,
p npq. This means
m¨n
r“m
r ¨n ^ m
r¨n
p“m r.
p ¨n (3.13)
Multiplying the first equality by n
p results in
m¨n
r¨n
p“m
r¨n¨n
p“m
r ¨n
p¨n “ m
p¨n
r¨n (3.14)
where where we used commutativity and associativity of multiplication throughout and
invoked the second equality in (3.13) in the last step. Since n
r ‰ 0, the fact that
@k, l, m P Z : pk ‰ 0 ^ k ¨ l “ k ¨ mq ñ l “ m (3.15)
implies m ¨ n p ¨ n meaning that pm, nq „ pm,
p“m p npq. ⇤
The punchline of this example is that the equivalence class rpm, nqs then contains all
pairs pm,
r nrq such that, informally (because division is not defined on Z), obey mnrr “ mn .
The set of equivalence classes thus provides a construction of the set of rationals Q.

3.3 Functions.

We now move to a concept central to analysis:

Definition 3.9 Let A and B be sets. A relation F Ñ A ˆ B satisfying
@x P A @y, z P B : xFy ^ xFz ñ y “ z (3.16)
is called a function. We will use notation Fpxq for the unique y P B such that xFy.
Moving to the convention that functions can be denoted by lowercase letters, we will
naturally think of a function f as an assignment of a value in B to a value in A, with the
notation f : A Ñ B. The relation f Ñ A ˆ B corresponding to a function f is then the
graph of f . Not every x P A may appear as the first member of a pair in relation R; those
that do are collected in the domain of R, i.e.,
(
DompRq :“ x P A : pDy P B : xRyq (3.17)
Similarly, not every y P B is in relation with some x P A; those that are form the range
of R denoted as (
RanpRq :“ y P B : pDx P A : xRyq . (3.18)

Preliminary version (subject to change anytime!) Typeset: January 19, 2023

MATH 131AH notes 14

We will write Domp f q, resp., Ranp f q for the domain, resp., range of the relation that is
a function f . We remark that one often writes f : A Ñ B without necessarily requiring
that Domp f q “ A.
If R Ñ A ˆ B and S Ñ B ˆ C are two relations, then their composition RS is the relation
defined by
@x P A @y P C : xpRSqy :“ Dz P B : xRz ^ zSy. (3.19)
If R and S are (graphs of) functions r and s, then their composition is also a function but
(beware!) for functions the composition is written in reverse order; namely,
RS is the graph of s ˝ r (3.20)
This is because functions “act” on the variable to the right while relations “act” on the
variable to the left. Note also that for any transitive relation R we have RR “ R.
The inverse R´1 of a relation R is the subset of B ˆ A defined by
@x P A @y P B : yR´1 x :“ xRy (3.21)
Note that RR´1 is an identity relation on DompRq (which is a subset of A) and R´1 R is
an identity relation on RanpRq (which is a subset of B). If F is (the graph of) a function f ,
then F´1 is (the graph of) a function if and only if
` ˘
@x, x̃ P A @y P B : y “ f pxq ^ y “ f pyq ñ x “ x̃ (3.22)
The inverse function is then denoted by f ´1 .
Given a function f : A Ñ B, for each C Ñ A we define the image f pCq of C by
(
f pCq :“ y P B : pDx P C X Domp f q : y “ f pxqq (3.23)
sometimes written simply as t f pxq : x P Cu ignoring that f pxq may not be defined for
all x P C. The image of the domain is then the range, Ranp f q “ f pDomp f qq. Similarly,
for all D Ñ B we define the preimage f ´1 pDq of D by
(
f ´1 pDq :“ x P A : x P Domp f q ^ f pxq P D (3.24)
which we at times write as tx : f pxq P Du ignoring domain restrictions. The preimage
of the range is the domain, f ´1 pRanp f qq “ Domp f q. We caution the reader that the use
of f ´1 in the preimage map does not require the inverse f ´1 of f to exist. Notwithstand-
ing, if f ´1 does exist, then f ´1 pDq is the image of D under f ´1 .
While functions in analysis are generally of interest for their analytic properties, in the
rest of mathematics functions are primarily used to identify sets with one another. For
this we need the following concepts:
Definition 3.10 A function f : A Ñ B is
‚ injective if Domp f q “ A and @x, y P A : f pxq “ f pyq ñ x “ y
‚ surjective if Ranp f q “ B meaning @y P BDx P A : f pxq “ y,
‚ bijective if it is both injective and surjective.
Exhibiting a bijection between two sets puts these in one-to-one or bijective correspon-
dence, which are simply different ways to talk about a bijection. For instance, the map
(3.6) defines a bijection f : pA ˆ Bq ˆ C Ñ A ˆ pB ˆ Cq that permits us to write this as
A ˆ B ˆ C. A very fruitful use of above concepts is in the following insightful definition
due to G. Cantor:

Preliminary version (subject to change anytime!) Typeset: January 19, 2023

15 MATH 131AH notes

Definition 3.11 (Equinumerosity) Sets A and B are said to be equinumerous, or are of

the same cardinality, if there exists a bijection f : A Ñ B.
Note that given a set of sets, equinumerosity is another example of equivalence rela-
tion. Indeed, reflexivity is provided by the identity map, symmetry by the inverse map
(which uses that the inverse of a bijection is a bijection) and transitivity by composed
maps (which uses that a composition of two bijections is a bijection). Related to this is:
Definition 3.12 A set A is said to be Dedekind infinite if there is an injection f : A Ñ A
such that Ranp f q ‰ A.
This is one way to define the notion of an infinite set, albeit one that is not generally
used in mathematics. We will return to these concepts when we discuss the question of
cardinality in more detail.

3.4 General Cartesian products.

Relying on the concept of a function, the notion of the Cartesian product can be gener-
alized to products of arbitrary collections of sets. Such collections is typically written as
tAa : a P Iu, where a represents the index of Aa and I denotes the index set. While this
concept is quite intuitive, the reader may wonder what this is in the formal language of
the set theory. This comes in:
Definition 3.13 (Collections of sets) Given sets I and A, a collection tAa : a P Iu of
subsets of A indexed by I is the set Ranpfq for a map f : I Ñ P pAq such that Domphq “ I.
Under this map, the sets in the collection are identified by Aa :“ fpaq.
We note that, formally, f P P pI ˆ P pAqq and so Ranpfq is indeed a set. (This is why
we need all Aa ’s be subsets of one set.) We then put forward:
Definition 3.14 (General Cartesian product) Given a set I and a collection tAa : a P Iu
of sets (all of which have to be subsets of a given set) indexed by I,

° " ´ § ¯ *
Aa :“ f PP Iˆ Aa : function ^ Domp f q “ I ^ p@a P I : f paq P Aa q (3.25)
aPI aPI

is the Cartesian product of the sets in tAa : a P Iu.

î
The notation is easier
î to parse once we note that a function f : I Ñ aPI Aa is for-
mally a subset of I ˆ aPI Aa , which (by Unionset and Powerset axioms and our earlier
construction of the Cartesian product) means that (3.25) is a set.
To see that (3.25) subsumes our earlier definition of the Cartesian product, note that a
function f defined on two-point set t0, 1u is determined by the pair of values p f p0q, f p1qq.
The set of all functions with f p0q P A and f p1q P B is thus in a bijective correspondence
with the set of all pairs pa, bq with a P A and b P B. This identifies A ˆ B with the set all
functions f : t0, 1u Ñ A Y B satisfying f p0q P A and f p1q P B, and thus the above general
Cartesian product for I :“ t0, 1u, A0 :“ A and A1 :“ B. We will henceforth not make a
distinction between the two ways to define the Cartesian product of two sets.
A special case (mainly notation) of above definition is:

Preliminary version (subject to change anytime!) Typeset: January 19, 2023

MATH 131AH notes 16

Definition 3.15 Let I and A be sets. Then

° (
A :“ f P P pI ˆ Aq : function (3.26)
aPI

is the Cartesian power denoted, in short, by A I .

For instance, the set of all real-valued sequences form the set RN while RR denotes the
set of all real-valued functions of one real-valued variable.
The Cartesian product of two non-empty sets is non-empty (which is witnessed by a
pair px, yq such that x P A and y P B), and the same applies to Cartesian products three,
four, etc sets. However, a perplexing issue arises once I is infinite where this argument
can no longer be made because we have no way to string an infinite number of such
statements together. In the ZFC theory, this is resolved by imposing yet another axiom:
‚ Axiom of Choice: For each nonempty set I and all collections
î tAa : a P Iu of sets
satisfying @a P I : Aa ‰ H, there exists a function f : I Ñ aPI Aa such that
Domp f q “ I ^ @a P I : f paq P Aa (3.27)
In short,
´ ` ¯ °
@I @tAa : a P Iu : I ‰ H ^ @a P I : Aa ‰ Hq ñ Aa ‰ H (3.28)
aPI
ë
The name arises from the observation that a function f P aPI Aa gives us a choice,
simultaneously for all a P I, of a representative f paq P Aa provided, of course, Aa ‰ H.
In sets with some underlying structure, this can sometimes be guaranteed constructively
but that will not work in general which is why such an axiom is needed.
Following up on a question from class, here is one instance where Axiom of Choice is
definitely NOT required:
Lemma 3.16 (Picking representatives from singletons) Let I ‰ H and let tAa : a P Iu be
a collection of subsets of a set A that are all singletons. Then there exists a function f : I Ñ A
such that Domp f q “ I and @a P I : f paq P Aa . In short
` ˘ °
I ‰ H ^ @a P I Dx P A : Aa “ txu ñ Aa ‰ H (3.29)
aPI
Axiom of Choice is not required.

Proof. Let tAa a P Iu be as in the statement and let F be the set of all functions f : I Ñ A
such that f paq P Aa for all a P Domp f q. We write this as
! ` ˘)
F :“ F Ñ I ˆ A : @a P I@x P A : aFx ñ x P Aa (3.30)
First we check that each F P F is the graph of a function. Indeed, if F P F and a P
DompFq then for any x, y P A,
aFx ^ aFy ñ x P Aa ^ y P Aa (3.31)
The fact that Aa is a singleton then forces x “ y and so F is the graph of a function.
The same argument also implies that if F, G P F , then (switching to the notation for
functions)
@a P DompFq X DompGq : Fpaq “ Gpaq (3.32)

Preliminary version (subject to change anytime!) Typeset: January 19, 2023

17 MATH 131AH notes

Now define §
Fp :“ F (3.33)
Then (3.32) ensures that also Fp is the graph of a function. It remains to show that
p “ I. For this pick any a P I and check that F :“ tpa, xq P I ˆ A : x P Aa u is
Domp Fq
p proving a P Domp Fq.
the graph of a function in F . Hence, F Ñ F, p ⇤
A similar conclusion is obtained even without the requirement that the sets Aa be
singletons provided there is a way to pick a “distinguished element” or a representa-
tive in each non-empty subset of A. Technically, this means that A admits a function
f : P pAq r tHu Ñ A such that
@B P P pAq r tHu : fpBq P B (3.34)
ë
That aPI Aa is non-empty is demonstrated ë by applying theëprevious lemma for sets
1 1
Aa :“ tfpAa qu and then noting that f P aPI Aa implies f P aPI Aa .
As stated before, in sets A with some underlying structure a “distinguished element”
can often be “picked” constructively, but this is not possible in general. The requirement
that there be a function satisfying (3.34) is generally as strong as the Axiom of Choice
itself. Indeed, one way to state the Axiom of Choice is by demanding that a function f
satisfying (3.34) exists for all non-empty sets A.
Notwithstanding the above discussion, mathematicians find the Axiom of Choice
generally less acceptable than the rest of Zermelo’s axioms, and so it is a good practice
(to which we will adhere) to caution the reader whenever it is invoked.

Preliminary version (subject to change anytime!) Typeset: January 19, 2023