Functions: Definition, Domain, and Codomain

Definition of a Function

• Given nonempty sets A and B, a function f from A to B, denoted by f: A → B, is an assignment of each element of A to exactly one element of B
• f(a) = b if b is the unique element of B assigned by the function f to the element a of A.
• Functions are called mappings or transformations

Function as a Relation

• A function f: A → B can be defined as a subset of A×B (a relation), restricted to relations where no two elements have the same first element
• A function f from A to B contains one and only one ordered pair (a, b) for every element a ∈ A (first element).
• ∀x[x ∈ A → ∃y[y∈ B∧ (x, y) ∈ f]]
• ∀x, y1, y2[[(x, y1) ∧ (x, y2)] ∈ f → y1 = y2]

Domain and Codomain

• Given a function f: A → B, we say f maps A to B
• A is called the domain of f
• B is called the codomain of f
• If f(a) = b, then b is called the image of a under f
• If f(a) = b, then a is called the preimage of b
• f(a) is also known as the range
• Two functions are equal when they have the same domain, the same codomain, and map each element of the domain to the same element of the codomain

Representing Functions

• Explicit statement of the assignment
• Formula: f(x) = x + 1
• A computer program that calculates the function

Question on functions and sets

• If f: A→B and S is a subset of A, then f(S) = {f(s) | s ∈ S}

Injections (One-to-One Functions)

• A function f is one-to-one if and only if for all a and b in the domain, f(a) = f(b) implies that a = b
• A function is an injection if it is one-to-one

Surjections (Onto Functions)

• A function f from A to B is onto if and only if for every element b ∈ Y, there is an element a ∈ X with f(a) = b
• A function f is called a surjection if it is onto

Bijections (One-to-One Correspondence)

• A function f is a bijection if it is both one-to-one (injective) and onto (surjective)

Inverse Functions

• If f is a bijection from A to B, the inverse of f, denoted by f⁻¹, is the function from B to A defined as f⁻¹(y) = x if and only if f(x) = y
• No inverse exists unless f is a bijection

Composition

• Given f: B → C and g: A → B, the composition of function f with function g, denoted by f ∘ g, is a function from A to C defined by f ∘ g(x) = f(g(x))

Graphs of Functions

• If f is a function from the set A to the set B, the graph of f is the set of ordered pairs {(a, b) | a ∈ A and f(a) = b}

Floor Function

• Denoted f(x) = ⌊x⌋, is the largest integer less than or equal to x

Ceiling Function

• Denoted f(x) = ⌈x⌉, is the smallest integer greater than or equal to x

Factorial Function

• Given f: N → Z+, factorial function denoted by f(n) = n! is the product of the first n positive integers when n is a nonnegative integer.
• f(n) = 1 × 2 × ... × (n − 1) × n
• f(0) = 0! = 1
• For example:
• f(1) = 1! = 1
• f(2) = 2! = 1 × 2 = 2
• f(6) = 6! = 1 × 2 × 3 × 4 × 5 × 6 = 720
• f(20) = 2,432,902,008,176,640,000
• Definition valid, because {0, 1, 2, 3, ...} → {1, 2, 3, ...}