# Functions

A function is a relation between a set of inputs and a set of outputs

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 one-to-one 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

### One-to-one (injection)

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.

### 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.

### 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.

### 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 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.

## 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 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

### 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 one-to-one correspondence.