Functions
A function is a relation between a set of inputs and a set of outputs
 Lambda Notation
 Special Functions
 Special Elements
 Finiteness
 Properties
 Types
 Relationships
 Operations
 Images
A binary relation from to is a considered a function from to if . This is denoted . In fact, is an alternate notation for , which makes the relationship between relations and functions even clearer.
Note that a relation from to is not considered a function if it doesn’t contain one single pair for every element of .
Lambda Notation
This notation allows to easily express functions whose domain is the subset of that satisfies a certain constraint.
For example, we may express division as . Notice the function takes two arguments, where the divisor can’t equal 0. Without lambda notation, we might have expressed this using the following set comprehension: .
The contraint part is optional. We can define .
Special Functions
Identity Function
The identity function of is defined as: .
The identity function is the only relation on that is both an equivalence relation on and also a function from to .
Assuming a function from to that is a onetoone correspondence, and .
Also, given , if and , then .
Constant Function
A constant function is a function that returns the same value given any input. is a constant function if .
Special Elements
Given a function , and elements and :

Identity: The element is an identity element of if

Absorbing: The element is an absorbing element of if

Inverse: The element is an absorbing element of if equals the identity element

Idempotent: The element is an idempotent element of if
In the case of multiplication, 1 is the identity and idempotent element, 0 is the absorbing element, and is the inverse element of . In the case of addition, 0 is the identity and idempotent element, and is the inverse element of . There is no absorbing element in this case.
Finiteness
 If the domain of a function is a finite set, then the function itself is finite
Properties
Onetoone (injection)
A function is onetoone if no two arguments point to the same result. Given , is onetoone if .
If two functions are onetoone, the composition of those two functions is also onetoone.
Given a function , if there is a function such that , then is onetoone.
Onto (surjection)
A function is onto if every element of is returned by the function, which basically means that or more generally, that .
If two functions are onto, the composition of those two functions is also onto.
Given a function , if there is a function such that , then is onto.
Onetoone Correspondence (bijection)
A function is a onetoone correspondence if its both onetoone and onto. If a function is a onetoone correspondence, then .
Giving a bijection between two sets is often a good way to show they have the same size.
Permutation
A function is a permutation if , and is a bijection.
Types
Total
A function is a total function if its defined for every value of . A function is assumed to be total unless explicitly told otherwise.
Partial
A function is a partial function if its only defined for a subset of . This is denoted as or as . Notice that counterintuitively, a partial function not necessarily a function.
We can think of a partial function from to as a total function from to , and instead of saying a function is undefined for some , we say that .
The set of partial functions is a proper superset of the set of total functions, since a partial function is allowed to be defined on all its input elements.
Relationships
Equality
Two functions and from to are considered equal if .
Composition
Since functions are binary relations, they can be composed. Given and , .
 The composition of two onetoone functions is onetoone
 If is onetoone, then there exists an onto function such that , and conversely
 If is onto, then there exists a onetoone function such that
Compatibility
Given and an equivalence relation on , is compatible with * if .
Operations

Range: given , the range of is the set of all the results of the application of such function.

Restriction: given and , the set is called the restriction of to , since it limits the pairs included in the relation. This is usually denoted

Relational Override: given functions and , we can override certain pairs in with their corresponding pairs as . Notice we can’t simply do since it can result in pairs that map the same value to more than one result, violating the definition of a function. Formally,
Note that if , then , and .
Images
Given and , then is called the image of under , which is the set of values returned by for every element in , which can be expressed as .
Then, given , the inverse image of under is the set .
Note that is defined as a set, and thus its not necessary for to be a function, which would imply that is a onetoone correspondence.