A function is a relation between a set of inputs and a set of outputs
- Lambda Notation
- Special Functions
- Special Elements
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 .
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 .
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 one-to-one correspondence, and .
Also, given , if and , then .
A constant function is a function that returns the same value given any input. is a constant function if .
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.
- If the domain of a function is a finite set, then the function itself is finite
A function is one-to-one if no two arguments point to the same result. Given , is one-to-one if .
If two functions are one-to-one, the composition of those two functions is also one-to-one.
Given a function , if there is a function such that , then is one-to-one.
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.
One-to-one Correspondence (bijection)
A function is a one-to-one correspondence if its both one-to-one and onto. If a function is a one-to-one correspondence, then .
Giving a bijection between two sets is often a good way to show they have the same size.
A function is a permutation if , and is a bijection.
A function is a total function if its defined for every value of . A function is assumed to be total unless explicitly told otherwise.
A function is a partial function if its only defined for a subset of . This is denoted as or as . Notice that counter-intuitively, 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.
Two functions and from to are considered equal if .
Since functions are binary relations, they can be composed. Given and , .
- The composition of two one-to-one functions is one-to-one
- If is one-to-one, then there exists an onto function such that , and conversely
- If is onto, then there exists a one-to-one function such that
Given and an equivalence relation on , is compatible with * if .
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 .
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 one-to-one correspondence.