# The Language of Mathematics Functions

## 1 Functions

**1.1 Functions**

Functions

•A function f from one set X to another set Y is a subset of the Cartesian

product X*Y such that for any x ∈X, there is exactly one y with (x, y)
∈f .

•Denote a function by f : X -> Y

•We usually write f (x) = y if (x, y) ∈f .

•The domain of f : X -> Y is X.

•The range of f : X -> Y is the set {y | (x, y) ∈f for some x ∈X}

Example.

1. f : R -> R given by f (x) = x^{2} is a function.

2. Let X = {a, b, c} and Y = {v, c}. Then f = {(a, v), (b, c), (c, c)} is a

function.

3. g = {(v, a), (c, b), (c, c)} is not a function. (We call this a relation)

### 2 Specifying Functions

**2.1 Arrow Diagrams**

Arrow Diagrams

•For small enough functions, we can denote them with an arrow diagram

Example. Let X = {a, b, c}, Y = {v, c} and f = {(a, v), (b, c), (c, c)} as
before.

2.2 Rules

Rules

•You are probably familiar with functions given by rules.

Example. 1. f (x) = x^{2}

2. g(x) = e^{x}

3. h(x) = sin x

**2.3 Graphs**

Graphs

•Suppose that f is a function whose domain and range are both subsets of R.

The graph of f is obtained by plotting each element of f as a point.

Example. The graph of f (x) = sin x

## 3 Specific Functions

**3.1 Modulus Operator**

Modulus Operator

•Recall Z denotes the set of integers.

•For x, y ∈Z with y > 0, define x mod y to be the remainder on dividing x

by y.

•x mod y is always nonnegative.

**3.2 Floor and Ceiling Functions**

Floor and Ceiling Functions

•The ceiling of a number, denoted
is the least integer greater than or

equal to x. (Round up!)

•The floor of a number, denoted is the greatest integer less than or equal

to x. (Round down!)

**3.3 Operators**

Operators

Let X be a set. A binary operator on X is a function X*X -> X (Two

inputs).

Let X be a set. A unary operator on X is a function X -> X.

Example. 1. If X is the set of all propositions in arithmetic, then
is

a unary operator on X.

2. If U is a universal set, then f (A, B) =
is a binary operator on

3. f (x, y) = 3x - 2y is a binary operator on Z.

## 4 Properties of Functions

**4.1 One-to-One Functions**

One-to-One Functions

• A function f is one-to-one (or injective) if for each y ∈Y, there is at
most

one x ∈X with f (x) = y.

**4.2 Onto Functions**

Onto Functions

• A function f is onto (or surjective) if for each y ∈Y, there is at least
one

x ∈X with f (x) = y.

**4.3 Bijective Functions and Inverses**

Bijective Functions

•A function f is bijective if it is both one-to-one and onto.

•Bijective functions f have inverses f^{-1}

Inverses

•The inverse f^{-1} of a bijective function “undoes” f

•Reverses the arrow diagram

Logarithms

•The function f (x) = lg x is the inverse of g(x) = 2x

•Called the base ∈logarithm of x

Example.

1. lg 64 = 6

2. lg 1000 ≈ 9.96578

**4.4 Composition of Functions**

Composition of Functions

•If g : X -> Y and f : Y -> Z are functions, we can define a new function

,
called the composition of f with g.

•Perform g, then f .

•The target of g and the domain of f must agree.

## 5 Hashing

**5.1 Hashing**

Hashing

•Want to organize stored data so that retrieval is efficient.

– Determine whether a particular item has been stored

– Edit or delete a particular item

– Find a place to insert a new item

•Hash tables are a commonly used method

– Have a hash function h : {Data} -> {Memory Locations}

Suppose we have 6 students in a computing class, with student IDs:

We also have 13 memory locations, indexed 0 to 12.

Define a hash function by h(x) = x mod 13.

Suppose we now have 8 students in a computing class, with student IDs:

We may end up having a collision, i.e., two or more items trying to be placed
in the same position.

We need a collision resolution policy. One simple one is simply to move to the
next unoccupied

location.

## Summary

Summary

You should be able to:

•Use functions and basic function terminology

•Identify functions using different methods

•Use the modulus operator and lg x

•Understand one-to-one and onto functions

•Understand and use hashing functions

•Deal with hashing collisions