Try the Free Math Solver or Scroll down to Tutorials!

 

 

 

 

 

 

 

 
 
 
 
 
 
 
 
 

 

 

 
 
 
 
 
 
 
 
 

Please use this form if you would like
to have this math solver on your website,
free of charge.


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) = x2 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) = x2
2. g(x) = ex
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