- input and/or output values may be integers, strings, characters...
- represent by $f : A → B$, where as A is
**domain**(input) and B is**co-domain**. f(x) is called**image** - For each input value, a function must provide
**one and only one output**value

**Identity function:** represent by $iD_A$, $iD_A : A → A$

## Equal

To be equal, two functions must (obviously) **assign the same output value to each input value**. But, in addition, they must have the **same type signature**.

*they are different functions since they have different signature even if equation is the same*

f : N → N such that f(x) = 2x.

f : R → R such that f(x) = 2x

*they are the same functions since they have same signature and same input corresponding to the same output even if equation is not the same*

f : Z → Z such that f(x) = |x|.

f : Z → Z such that f(x) = max(x, −x).

f : Z → Z such that f(x) = x if x ≥ 0 and f(x) = −x if x ≤ 0.

## Image and Onto

**Image**: for the function f : A → B, image is the set of values produced when f is applied to all elements of A. Represent by f(A)

$$ f(A) = {f(x) : x ∈ A} $$

**Onto**: f : A → B is onto if its **image is its whole co-domain**

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

It critically depend on its type signature, for example

q : N → N q(x) = x + 2 is not onto because no input map onto 0 or 1

**Negating Onto**:

$$ ¬∀y ∈ B, ∃x ∈ A, f(x) = y $$

or

$$ ∃y ∈ B, ∀x ∈ A, f(x) \neq y $$

if we want to show that f is not onto, we need to find some value y in B, such that no matter which element x you pick from A, f(x) isn’t equal to y.

## Nested quantifiers

When quantifiers are nested, the meaning of the statement depends on the **order of the two quantifiers**.

For every person p in the Fleck family, there is a toothbrush t such that p brushes their teeth with t.

$$ \neq $$

There is a toothbrush t, such that for every person p in the Fleck family, p brushes their teeth with t.

- order issued when the statement is mixture of existential and universal quantifiers

## Composing

$$ (g \circ f)(x)=g(f(x)) $$

- the declared domains and co-domains of the two functions aren’t all the same, so
**often you can only compose in one order**

## Terminology

**function**: map

**onto**: subjective

**Image**: $Im(f)$

**range**: refer to image or the co-domain, avoid using it

## Proving

Define the function g from the integers to the integers by the formula g(x) = x − 8. g is onto.

**state the definition of onto**: We need to show that for every integer y, there is an**integer**x such that g(x) = y.**assign value**: So, let y be some arbitrary integer. Choose x to be (y + 8).**state x is integer**: x is an integer, since it’s the sum of two integers**state g(x) = y**: g(x) = (y + 8) − 8 = y**conclusion**: so we’ve found the required pre-image for y and our proof is done

Let f : $\mathbb{Z}^2$→ Z be defined by f(x, y) = x + y. I claim that f is onto.

Let y be an element of Z. Then (0, y) is an element of f : $Z^2$and f(0, y) = 0 + y = y. Since this construction will work for any choice of y, we’ve shown that f is onto

For any sets A, B, and C and for any functions f : A → B and g : B → C, if f and g are onto, then g ◦ f is also onto.

- Let A, B, and C be sets. Let f : A → B and g : B → C be functions. Suppose that f and g are onto.
- We need to show that g ◦ f is onto. That is, we need to show that for any element x in C, there is an element y in A such that (g ◦ f)(y) = x.
- So, pick some element x in C. Since g is onto, there is an element z in B such that g(z) = x. Since f is onto, there is an element y in A such that f(y) = z.
- Substituting the value f(y) = z into the equation g(z) = x, we get g(f(y)) = x. That is, (g ◦ f)(y) = x. So y is the element of A we needed to find.

## One to one

A function is one-to-one if it never assigns two input values to the same output value. Or, said another way, **no output value has more than one preimage**

$$ ∀x, y ∈ A, x \not = y → f(x) \not= f(y) $$

$$ ∀x, y ∈ A, f(x) = f(y) → x = y $$

**pre image**: Suppose that f : A → B is a function from A to B. If we pick a value y ∈ B, then x ∈ A is a pre-image of y if f(x) = y

**prove**

Let f : Z → Z be defined by f(x) = 3x + 7. f is one-to-one

Proof: We need to show that for every integers x and y, f(x) = f(y) → x = y. So, let x and y be integers and suppose that f(x) = f(y). We need to show that x = y. We know that f(x) = f(y). So, substituting in our formula for f, 3x + 7 = 3y + 7. So 3x = 3y and therefore x = y, by high school algebra. This is what we needed to show

**Composition**

For any sets A, B, and C and for any functions f : A → B and g : B → C, if f and g are one-to-one, then g ◦ f is also one-to-one

**Strictly increasing functions**

f is called strictly increasing if, for every x and y in A, x < y implies that f(x) < f(y)

For all strictly increasing functions, they are one-to-one function

## Bijections

A function that is both one-to-one and onto is called bijective or a bijection

**Inverse function**: represent by $f^{-1}$. If f maps from A to B, then $f^{-1}$ maps from B to A.

## Pigeonhole Principle

Suppose you have n objects and assign k labels to these objects. If n > k, then two objects must get the same label.

Among the first 100 powers of 17, there are two (distinct) powers which differ by a multiple of 57

## Permutations

an ordered choice of k objects from a set of n objects is known as a k-permutation of the n objects. There are

$$ n(n-1)...(n-k+1)=\frac{n!}{(n-k)!} $$

different k-permutations of n objects, which is called P(n,k), which is also the number of one-to-one functions from a set of k objects to a set of n objects.

**exception**

$J = (a, p, p, l, e, t, r, e, e, s)$, we have 10! way to arrange. However, there are two duplicate possible which are *p* and *e*, to remove the exception, we do dividing

$$ \frac{10!}{2!3!} $$