Functions

Intuition

• Already familiar idea
• How would you define?
• Review features seen in 210/212

Defining "functions"

Traditionally, math defines only unary functions.

• Examples of unary functions
• A (unary) function is an assignment/mapping from set X to set Y.
  • domain = X
  • codomain = Y
• Functions as sets: A (unary) function is a set of pairs {(x,y)}, …
• 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.

• How?
• Notation

Total vs. partial functions

• Total function -- defined on all domain elements
• Partial function -- not defined for some domain elements
• Examples of partial 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

Math functions vs. Programming language functions

• In math, values never change. 4 always equals 4. Values are immutable.
• In CS, most languages allow assignment. Values are mutable.
• Typically, PL "function" A→B corresponds to math function (A×S) → (B×S), where S is the current "state"
  • 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
  Many PLs prefer terms such as "procedure" to avoid such terminology confusion.

Defining specific functions

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.

• Integer math
  • Floor and ceiling
    • Useful in CS because of the common use of integer math
  • Modulo
    • One common CS usage: Accounting for fixed-sized integer math
    • Will discuss interesting properties later in course
• Composition
  • Example?
  • Composition is a function -- what is its type?
  • Esp. useful in functional programming
    • PL semantics typically written as math functions -- essentially functional programs
    • A composition-heavy form of FP is "combinator"-style programming -- e.g., favored in the PL "Haskell"
• Notation
  • Case notation
  • Extending/generalizing functions
    • From elements to sets of elements -- e.g., A+2, A+B -- example, definition
    • From elements to functions -- e.g., f+2, f+g -- example, definition

Some properties of functions

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

• onto (surjective)
  • Everything in codomain gets mapped to -- image = codomain
  • forall y∈Y, exist x∈X, f(x)=y
• 1-1 (injective)
  • Nothing in codomain gets mapped to more than once
  • forall x1,x2∈X, f(x)=f(y) iff x=y
• 1-1 and onto (bijective)
  • What does mapping diagram look like?
• invertable -- exists function g:Y→X such that both…
  • forall x∈X, g(f(x)) = x ["g is a left-inverse of f"]
  • forall y∈Y, f(g(y)) = y ["g is a right-inverse of f"]
  • Notation: g = f^-1
  • Left as a homework exercise: Is a left-inverse of f necessarily a right-inverse of f, and vice versa?
• idempotent -- forall x∈X, f(f(x)) = f(x)

Example proof: If f is bijective, then f is invertable.

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. Is g well-defined?

• x₀ exists because f is onto.
• x₀ is unique because f is 1-1.

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

• forall x∈X, what is g(f(x))? g(f(x)) is the element of X which f maps to f(x); this is x. So g(f(x)) = x, and g is indeed a left-inverse of f.
• Similarly, forall y∈Y, what is f(g(y))? By our construction of g, g(y) is the thing which f maps to y, so therefore f(g(y)) = y. And g is indeed a right-inverse of f.