Functions

The Cartesian Product of A and B,

Cartesian product of a and b is a or b is the empty set

A x B = ∅

relation on A

A relation on A is a subset R of A → A. We write a ⇒ b

to denote that (a, b) belongs to R

equivalence relation on A

s a relation R with the following properties:

(i) Reflexive: ∀ a ∈A, a ~ a.

(ii) Symmetric: ∀a, b ∈ A, a ~ b ⇒ b ⇒~ a

(iii) Transitive: ∀a, b, c ∈ A, a ~ b and b ~ c ⇒ a ~c

function

A function f from A to B is a rule that assigns

to each element of A a unique element of B. We write

f : A → B

where a is domain

b is codomain

injective function

∀x, y ∈ A, f (x) = f (y) ⇒ x = y

1 to 1

surjective functon

A function f : A → B is surjective if Imf = B. This means that

∀y ∈ B, ∃x ∈ A, such that y = f (x)

if every element in the codomain gets mapped to by at least one element in the domain

bijection function

if it is both injective and surjective

composite function,

g ∞ f

roof for f f and g are both injective, then g ∞ f is injective

ssume that f and g are injective. Assume that g ∞ f (x) = g ∞ f (y) for some x, y ↑ A.

Then g(f (x)) = g(f (y)) and since g is injective it follows from the definition that

f (x) = f (y). Since f is injective, this implies that x = y. Therefore g ∞ f is injective

by definition.

inverse

et f : A ↙ B be a function. We say that f is invertible if there exists

a function f ↑1 : B ↙ A such that f ↑1 ∞ f is the identity function on A and f ∞ f ↑1 is the

identity function on B. We call f ↑1 the inverse of f .

roof for A function f : A ↙ B is invertible if and only if f is a bijection

Assume that f is invertible with inverse f ↑1 : B ↙ A. Let f (a1 ) = f (a 2 ) for some

a 1 , a2 ↑ A. Then f ↑1 (f (a1 )) = f ↑1 ((f (a2 )) and so a 1 = a2 . Therefore f is injective.

Let b ↑ B with a = f ↑1 (b) ↑ A. Then f (a) = b and so f is surjective. Therefore f is a

bijection.

Conversely assume that f is a bijection. Let b ↑ B. Since f is surjective, there exists a ↑ A

with f (a) = b and since f is injective, a is unique. Therefore we can define f ↑1 (b) = a. This

defines the function f ↑1 : B ↙ A. For a ↑ A, let f (a) = b. Then f ↑1 ∞ f (a) = f ↑1 (b) = a.

For b ↑ B, let a be the unique element in A such that f (a) = b. Then f ∞f ↑1 (b) = f (a) = b.

Therefore f ↑1 is the inverse of f .