# Functions: Surjective, Bijective, Injective

## Definition:

A function ffrom a set P to a set Q is an assignment of exactly one element of Q to each element of P.
We write f(p) = q
if q is the unique element of Q assigned by the function f to the element p of P.
If f is a function from P to Q, we write f: P→Q
Here is what we say about this function:
• If f: P→Q, we say that P is the domain of f and Q is the codomain of f.
• If f(p)  q, we say that q is the image of p and p is the pre-image of q.
• The range of f: P→Qis the set of all images of elements of P.
• We say that f: P→Q maps P to Q.

### Example

Assume the following function f:  P→Q with
P = {Adam, Mariam, Omar, Lina}
Q = {London, Dubai, Istanbul, Paris}
f(Adam) = Paris
f(Mariam) = London
f(Omar) = Istanbul)
f(Lina) = Dubai
Here is the range of f is Q.
If we make the following changes:
f(Adam) = Dubai then f is still a function but the range is {Dubai, London, Istanbul}

#### Another way to represent f: ## Injections, Surjections and Bijections

A function f: P→Q is said to be one-to-one (or injective), if and only if
∀x,  y∈P (f(x) = f(y) →  x=y)
Basically, f is one-to-one if and only if it does not map two distinct elements of P onto the same element of Q.

### Example

Is f one-to-one? f(Adam) = Dubai
f(Mariam) = London
f(Omar) = Istanbul)
f(Lina) = Dubai
The answer is no because Adam and Lina are mapped onto the same element of the image.

### Properties of Functions

• A function f: P→Q is called onto, or surjective, if and only if for every element q∈Q there is an element p∈P with f(p) = q.
• In other words, f is onto if and only if its range is its entire codomain.
• A function f: P→Q is a one-to-one correspondence, or a bijection, if and only if it is both one-to-one and onto.
• Obviously, if f is a bijection and P and Q are finite sets, then ▕P▏=▕Q▏

#### Examples

See the below function and check if it is injective, surjective, or bjiective. Answer: f is neither.
Question: What if Omar is also connected to Dubai? Answer: Here, f is not even a function.
Question: What if Lina is also connected to Dubai? Answer: In that case, f is injective, surjective, as well as bijective.

### Composition

Let f: O→P , g: Q→O. The composition of f with g, denoted f∘g, is the function from Q to P defined by
f∘g(x) = f(g(x))

#### Example

let f(x) = x2 and g(x)=x ‒ 3 are functions from R to R
Find the compositions f∘g and g∘f
Answer
f∘g(x) = f(g(x)) = f(x ‒ 3) = (x ‒ 3)2
g∘f(x) = g(f(x)) = g(x2) = x2 ‒ 3
Which means that f∘g and g∘f are generally different.

## Sequences and Summations

Definition:A sequence is a function from a subset of the natural numbers (usually of the form {0, 1, 2, . . . } to a set S.
Note: the sets {0, 1, 2, 3, . . . , k} and {1, 2, 3, 4, . . . , k} are called initial segments of N.
Notation: if f is a function from {0, 1, 2, . . .} to S we usually denote f(i) by ai and we write. where k is the upper limit (usually ∞). ### Example ### Geometric Progression

A geometric progression is a sequence of the form a, ar, ar2, ar3, ar4, . . . .
Try to prove that (Try to figure out what it is if r = 1).
You should also be able to determine the sum
• if the index starts at k vs. 0
• if the index ends at something other than n (e.g., n– 1, n+1, etc.).
For more details, please contact me here.
Date of last modification: February 20, 2019