Functions

Intuition

Traditionally, math focuses on unary functions.

Examples of unary functions
A (unary) function f is an assignment/mapping from set X to set Y.
- Notation: f : X → Y
- domain = X
- codomain = Y
Functions as sets: A (unary) function is a set of pairs {(x,y)}, such that each x occurs at most once
Functions as kinds of relations: A (unary) function is a binary relation such that each domain element is associated with at most one codomain element.
Relations as kinds of functions: A relation is a function whose codomain is the set of Booleans.

Esp. in CS, convenient to define functions of other arities.

Either expand the original definitions…
- A×B×C → Y
…or define in terms of unary functions
- How? — You've seen this in COMP 210.
- A → B → C → Y
Comparing the two

Total vs. partial functions

Total function — defined on all domain elements
Partial function — might not be defined on all domain elements
- Beware: "partial" is also commonly used to mean "non-total"
Examples of useful non-total functions?
In CS, partial functions used to model computations which produce an error or never stop
Can convert partial function to total function by adding ⊥ ("bottom") to codomain

In math, values never change. 4 always equals 4. Values are immutable.
In CS, most languages allow assignment. Values (or at least some of them) are mutable.
Typically, PL "function" X→Y corresponds to math function (X×S) → (Y×S), where S is the set of possible "states"
- Specifically what S looks like depends on the language, but it's typically a function itself, e.g., mapping variables to values
- See esp. COMP 311,411 for more details
Some PLs prefer terms such as "procedure" to avoid such terminology confusion.

Draw diagrams of mapping. For each, consider f:X→Y.

onto (surjective)
- Everything in codomain gets mapped to — image = codomain
- ∀ y∈Y, ∃ x∈X, f(x)=y
- Examples?
1-1 (injective)
- Nothing in codomain gets mapped to more than once
- ∀ x₁, x₂∈X, f(x₁)= f(x₂) iff x₁=x₂
- Examples?
1-1 and onto (bijective)
- What does mapping diagram look like?
- Examples?
invertable
- exists function g:Y→X such that both…
  - ∀ x∈X, g(f(x)) = x — "g is a left-inverse of f"
  - ∀ y∈Y, f(g(y)) = y — "g is a right-inverse of f"
- Examples?
- Notation: g = f^-1
- Left partly as a homework exercise: Is a left-inverse of f necessarily a right-inverse of f, and vice versa?
- Example CS use: "Undo" features of editors
- Example CS use: Undoing a cancelled, but partially-completed operation, e.g., a money transfer
idempotent
- ∀ x∈X, f(f(x)) = f(x)
- Examples?
- Example CS use: Describing functions that don't change state, e.g., table lookups
- Example CS use: Describing functions that might get interrupted, and are safely repeatable, e.g., table updates that check if the table already has this update

Intuitively fairly obvious from diagram, but how can we prove this? The proof follows the intuition, but makes some things more explicit.

Given that f is bijective, we'll construct a function g:Y→X. Then we show that this particular g is f's inverse.

Define g: For all y′∈Y, we define g(y′) as the element x′ such that f maps x′ to y′.

Weird wording. Are we sure g is well-defined?

g sounds like an inverse of f, but is it really?

∀ x∈X, what is g(f(x))?
- Plug in f(x) for y₀ in the definition.
- g(f(x)) is the element of X which f maps to f(x);
- So, g(f(x)) = x!
- Thus, g is indeed a left-inverse of f.
Similarly, ∀ y∈Y, what is f(g(y))?
- By our definition of g, g(y) is the thing which f maps to y
- Therefore, f(g(y)) = y.
- And g is indeed a right-inverse of f.
Thus, g is an inverse of f.

Several related questions left for your consideration:

Class might skim or even skip this, depending on time.

You have lots of experience with this. But, here's a few CS-useful specifics you might not be familiar with.