CHAPTER 2

SETS AND FUNCTIONS

ALGEBRA, ENSIA 2021

December 10, 2021 1 / 40

”Young man, in Mathematics you don’t understand
things. You just get used to them.”
John von Neumann

December 10, 2021 2 / 40

SETS AND ELEMENTS

December 10, 2021 3 / 40

SETS AND ELEMENTS

In mathematics, we often encounter ”sets”, for example, real numbers

form a set. Defining a set formally is a delicate matter, so we will use
”naive” set theory, based on the intuitive properties of sets.
Definition
A set is a collection of objects called elements.

December 10, 2021 4 / 40

SETS AND ELEMENTS

We use uppercase letters to label sets, and elements will usually be

represented by lowercase letters. When a is an element of a set A, we write

a ∈ A.

Otherwise, we write
a∈
/ A.
If A contains no elements, it is the empty set, denoted by ∅.
Two sets are equal if they have exactly the same elements. In other words,

A = B ⇔ (x ∈ A ⇔ x ∈ B ).

All the elements that we will consider are assumed to belong to a universe
set U.
We use the bracket notation {} to refer to a set.

December 10, 2021 5 / 40

SETS AND ELEMENTS

Example
The sets {1, 2, 3} and {3, 2, 1} are the same, because the ordering does
not matter. The set {1, 1, 2, 3, 3} is also the same set as {1, 2, 3}, because
we are not interested in repetitions.

One may specify a set explicitly, that is by listing all the elements the set
contains, or implicitly, using a predicate :

{x : P (x )}.

This notation is also known as set-builder notation.

Example
A = {1, 2}, N = {0, 1, 2, · · · } are explicit descriptions.
The set {x : x is a prime number } is implicit.

December 10, 2021 6 / 40

Cardinality

Definition
The Cardinality |A| of a set A is the number of distinct elements of A. If
|A| is finite, then A is said to be finite. Otherwise, A is said to be infinite.

Example
1 | ∅ | = 0 while |{ ∅ }| = 1.

2 |{1, 2, 5}| = 3.

3 The set of prime numbers is infinite.

December 10, 2021 7 / 40

SET OPERATIONS

December 10, 2021 8 / 40

SET OPERATIONS

We now use connectives to define the set operations. These allow us to

build new set from given ones.
Definition
The union of A and B is

A ∪ B = {x : x ∈ A ∨ x ∈ B }.

Definition
The intersection of A and B is

A ∩ B = {x : x ∈ A ∧ x ∈ B }.

December 10, 2021 9 / 40

SET OPERATIONS

Example
If A = {1, 2, 3, 4} and B = {3, 4, 5, 6}, then

A ∪ B = {1, 2, 3, 4, 5, 6}

and
A ∩ B = {3, 4}.

These operations of union and intersection can be illustrated with Venn

diagrams.

December 10, 2021 10 / 40

SET OPERATIONS

Theorem
Let A and B be finite sets. Then we have

|A ∪ B | = |A| + |B | − |A ∩ B |.

December 10, 2021 11 / 40

SET OPERATIONS

Definition
The sets A and B are disjoint when A ∩ B = ∅.

Definition
The set difference of B from A is

A \ B = {x : x ∈ A ∧ x ∈
/ B }.

The complement of A is defined as

A = U \ A = {x : x ∈ U ∧ x ∈
/ A}.

Read A \ B as ”A minus B”.

December 10, 2021 12 / 40

SET OPERATIONS

Example
Let U = {1, 2, · · · , 10}, A = {1, 2, 3, 4, 5} and B = {3, 4, 5, 6, 7, 8}.
Then
A \ B = {1, 2}
and
A = {6, 7, 8, 9, 10}.
Use Venn diagram to illustrate.

Example
R \ Q : irrational numbers.

December 10, 2021 13 / 40

Some properties

As with the logical operations, we need an order to make sense of

expressions that involve many operations.
Example
If we take U = {1, 2, , 3, 4, 5}, A = {5}, B = {3, 4, 5} and C = {2, 3},
then
A ∪ (B ∩ C ) = {5} ∪ {3} = {3, 5},
while
(A ∪ B ) ∩ C = {3, 4, 5} ∩ {2, 3} = {3}.
This shows that, in general,

A ∪ (B ∩ C ) ̸ = (A ∪ B ) ∩ C .

Therefore, we cannot write expressions as A ∪ B ∩ C .

December 10, 2021 14 / 40

Some properties

However, since, as we will see,

A ∪ (B ∪ C ) = (A ∪ B ) ∪ C ,

and
A ∩ (B ∩ C ) = (A ∩ B ) ∩ C ,
then we can write A ∪ B ∪ C and A ∩ B ∩ C .

December 10, 2021 15 / 40

Some properties

From the properties of the logical operators we derive the following.

Theorem
Let U be the universe set, and let A, B, C be sets. Then we have :
1 A∩B = B ∩A
2 A∪B = B ∪A
3 (A) = A
4 A∩B = A∪B
5 A∪B = A∩B
6 (A ∩ B ) ∩ C ) = A ∩ (B ∩ C )
7 (A ∪ B ) ∪ C ) = A ∪ (B ∪ C )
8 A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
9 A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C )

December 10, 2021 16 / 40

CARTESIAN PRODUCTS

December 10, 2021 17 / 40

CARTESIAN PRODUCTS
Let A and B be sets. Given elements a ∈ A and b ∈ B, we call (a, b ) an
ordered pair. In this context, a and b are called coordinates.

Definition (Kuratowski, 1921)

If a ∈ A and b ∈ B,
(a, b ) = {{a}, {a, b }}
We have then

(a, b ) = (a′ , b ′ ) ⇔ a = a′ and b = b ′

Definition
The Cartesian product of A and B is

A × B = {(a, b ) : a ∈ A ∧ b ∈ B }.

The Cartesian product R2 = R × R is called the Cartesian plane.

December 10, 2021 18 / 40
CARTESIAN PRODUCTS

Example
If A = {1, 2} and B = {0, 1, 2},

A × B = {1, 2} × {0, 1, 2} = {(1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)}.

If A = {1, 2, 7} and B = {∅, {1, 5}},

A × B = {(1, ∅), (1, {1, 5}), (2, ∅), (2, {1, 5}), (7, ∅), (7, {1, 5})}.

December 10, 2021 19 / 40

CARTESIAN PRODUCTS
We generalize definition of an ordered pair by defining

(a, b, c ) = {{a}, {a, b }, {a, b, c }},

(a, b, c, d ) = {{a}, {a, b }, {a, b, c }, {a, b, c, d }},

and for n ∈ N,

(a1 , a2 , · · · , an ) = {{a1 }, {a1 , a2 }, · · · , {a1 , a2 , · · · , an }},

which is called and ordered n −tuple. Then

A × B × C = {(a, b, c ), a ∈ A ∧ b ∈ B ∧ c ∈ C },

A × B × C × D = {(a, b, c, d ), a ∈ A ∧ b ∈ B ∧ c ∈ C ∧ d ∈ D },
and
An = {(a1 , a2 , · · · , an ) : ai ∈ A ∧ i = 1, 2, · · · , n }.
Rn = R × R × · · · × R (n times) is the Cartesian n −space.
December 10, 2021 20 / 40
SUBSETS

December 10, 2021 21 / 40

SUBSETS

Let A and B be sets. We say that A is a subset of B, and we write

A ⊆ B, when every element of A is an element of B.
Definition
A ⊆ B ⇔ ∀x, (x ∈ A ⇒ x ∈ B ).

If A is not a subset of B, we write A ⊈ B

December 10, 2021 22 / 40

SUBSETS

We have then
A ⊈ B ⇔ ∃x, x ∈ A ∧ x ∈
/ B.

Example
Let A = {1, 2, 3} and B = {1, 2, 5}. Then A ⊈ B because ∃ 3 ∈ A and
3∈/ B.
When A ⊆ B but A ̸= B, we say that A is a proper subset of B, and we
write A ⊂ B ).

Example
N ⊂ Z ⊂ Q ⊂ R ⊂ C.

December 10, 2021 23 / 40

FAMILIES OF SETS

The elements of a set can be sets themselves. We call such a collection a

family of sets and often use capital script letters to name. For example,
let
E = {{1, 2, 3}, {2, 3, 4}, {3, 4, 5}}.
The set E has three elements :{1, 2, 3}, {2, 3, 4}, {3, 4, 5}.
Families of sets can have infinitely many elements. For example, let

F = {[n, n + 1[: n ∈ Z}.

The set Z plays the role of an index set, a set whose only purpose is to
enumerate the elements of the family. Each element of an index set is
called an index. If we let I = Z and Ai = [i, i + 1[, the family can be
written as
F = {Ai : i ∈ I }.

December 10, 2021 24 / 40

SUBSETS

Theorem
Let A, B, C be sets. Then
1 ∅ ⊆ A.
2 A = B ⇔ A ⊆ B ∧ B ⊆ A.
3 If A ⊆ B and B ⊆ C , then A ⊆ C .

December 10, 2021 25 / 40

FAMILIES OF SETS

There is a natural way to construct a family of sets. Take a set A. The

collection of all subsets of A is called the power set of A and denoted by
P (A).
Definition
For any set A,
P (A) = {B, B ⊆ A}.

Example

P ({1, 2, 3}) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

December 10, 2021 26 / 40

FUNCTIONS

December 10, 2021 27 / 40

Functions

Let E , F be sets. A function f : E → F assigns to each x ∈ E a unique

element f (x ) ∈ F . Functions are also called maps, mappings, or
transformations.
Definition
Let f : E → F be a function. Then E is called the domain of f and F is
called the codomain of f .
We write f : x 7→ f (x ) to indicate that is the function that maps x to
f (x ).

December 10, 2021 28 / 40

Functions

Definition
Let f : E → F be a function.
1 If x ∈ E , f (x ) is the image of x under f .

2 If y ∈ F is such that y = f (x ) for some x ∈ E , then x is the

preimage of y under f .

December 10, 2021 29 / 40

Functions

Example
Let E = {1, 2, 3} and F = {a, b }. Then we can define a function
f : E → F by setting f (1) = f (2) = a and f (3) = b.
a is the image of 1 under f .
1 is the preimage of a under f .

This can be represented by the following pictures.

Definition
Let f : E → F be a function and A ⊂ E . The restriction of f to A is the
function denoted f|A : A → F defined by f|A (x ) = f (x ), ∀x ∈ A.

December 10, 2021 30 / 40

Image and inverse image of a set

Definition
For a function f : E −→ F , A ⊆ E , and B ⊆ F , the image of A is

f (A) = {y ∈ F : ∃x ∈ A, y = f (x )}.

The inverse image of B is

f −1 (B ) = { x ∈ E : f (x ) ∈ B } .

Example
Let f : R −→ R, f (x ) = x 2 , Then
1 f ([−1, 1]) = [0, 1].
2 f −1 ({1}) = {1, −1}.
3 f −1 ({−1}) = ∅.

December 10, 2021 31 / 40

Remarkable examples

1 The identity function on a set E is the function IdE : E → E

defined by IdE (x ), ∀x ∈ E .
2 If E ⊆ F , the inclusion map is the function i : E → F defined by
i (x ) = x, ∀x ∈ E .
3 Let E = E1 × E2 × · · · × En . Define, for each i, πi : E → Ei as
follows :
πi (x1 , x2 , · · · , xn ) = xi .
The function πi is the i th projection.
4 A constant function is a map f : E → F such that
f (x ) = c, ∀x ∈ E , where c ∈ F is fixed.

December 10, 2021 32 / 40

Remarkable examples

5 Suppose A ⊆ E . The characteristic function of A, χA : E → {0, 1},

is defined by 
1 if x ∈ A
χA (x ) =
0 if x ∈
/A
6 A boolean function is a function

f : {0, 1}n → {0, 1},

where n is a positive integer.

For n = 2, we can define the following functions :
i f (0, 0) = 0, f (1, 0) = 1, f (0, 1) = 1, f (1, 1) = 1.
ii g (0, 0) = 0, g (1, 0) = 0, g (0, 1) = 0, g (1, 1) = 1.
iii h (0, 0) = 0, g (1, 0) = 1, h (0, 1) = 1, h (1, 1) = 0.
Did you recognize these functions ?

December 10, 2021 33 / 40

Injective function

Definition
A function f : E → F is injective if we have

∀x1 , x2 ∈ E , f (x1 ) = f (x2 ) ⇒ x1 = x2 .

An injection is also known as a one to one function.

Example
The function f : Z → Z defined by f (x ) = x 2 , ∀x ∈ Z, is not injective
since f (1) = f (−1).
The function g : N → N defined by g (x ) = x 2 , ∀x ∈ N, is injective.

December 10, 2021 34 / 40

Surjective function

Definition
A function f : E → F is surjective if we have

∀y ∈ F , ∃x ∈ E , y = f (x ).

A surjection is also known as an onto function. From the definition, f is

surjective if, and only, if f (E ) = F .

Example
The function f : Q → Q defined by f (x ) = 2x is surjective. Indeed,
y y
∀y ∈ Q, ∃x = ∈ Q : f (x ) = 2 · = y .
2 2
The function g : Z → Z defined by g (x ) = 2x is not surjective. Indeed,

∃y = 1 ∈ Z, ∀x ∈ Z, g (x ) = 2x ̸= 1.
December 10, 2021 35 / 40
Bijective function

Definition
A function that is both injective and surjective is said to be bijective.

Example
f : [0, +∞[ → [0, +∞[
x 7 → f (x ) = x 2
is bijective.

December 10, 2021 36 / 40

Inverse function

Theorem
Let f : E → F be a function. Then f is bijective if and only if

∀y ∈ F , ∃!x ∈ E : f (x ) = y .

From this theorem, we obtain a unique function f −1 : E → F defined by :

f (x ) = y ⇔ x = f −1 (y )

Definition
f −1 is called the inverse of f

December 10, 2021 37 / 40

Inverse function

Example
f : [0, +∞[−→ [0, +∞[ defined by √ f (x ) = x 2 is bijective.
Its inverse is given by f −1 (x ) = x.

December 10, 2021 38 / 40

Composition

Definition
Let f : E −→ F and g : F −→ G be functions. The composed function
g ◦ f : E −→ G is defined by :

∀x ∈ E , g ◦ f (x ) = g (f (x )).

Example
Let f , g : R −→ R where f (x ) = x 2 and g (x ) = x + 1. Then

(g ◦ f )(x ) = g (x 2 ) = x 2 + 1,

while
(f ◦ g )(x ) = f (x + 1) = (x + 1)2 = x 2 + 2x + 1.
Therefore, in general
g ◦ f ̸= f ◦ g .
December 10, 2021 39 / 40
Composition

Theorem
Let f : E −→ F , g : F −→ G and h : G −→ H be functions. Then we
have
h ◦ (g ◦ f ) = (h ◦ g ) ◦ f .

Theorem
Let f : E −→ F be a bijective function, then f −1 ◦ f = IdE and
f ◦ f −1 = IdF .

December 10, 2021 40 / 40