➔ Functions
◆ Let X and Y be sets. A function f from X to Y is a correspondence that assigns to
each element x ∈ X, a unique element of Y, f(x)
◆ Denoted f: X→Y and defined by:
1. f, the rule / correspondence / formula
2. X, the domain
3. Y, the codomain
◆ Examples:
➔ Injective, Surjective & Bijective
1. f : X → Y is injective (or one to one) if
(∀ x1, x2 ∈ X) [ f (x1) = f (x2) ⇒ x1 = x2 ]
equivalently, (∀ x1, x2 ∈ X) [ x1 ≠ x2 ⇒ f(x1) ≠ f(x2) ]
2. f : X → Y is surjective (or onto) if
(∀ y ∈ Y)(∃ x ∈ X) [ f(x) = y ]
(all elements of the codomain are attained by the domain)
3. f : X → Y is bijective if it is both injective and surjective
◆ Given set X with n elements and Y with m elements,
1. If f : X → Y is injective then n ≤ m
2. If f : X → Y is surjective then n ≥ m
3. If f : X → Y is bijective then n = m
➔ Range
◆ Let X and Y be sets, and let f : X → Y,
The range or image of f is the set
{ y ∈ Y | (∃x ∈ X) (y = f(x) } = { f(x) ∈ Y | x ∈ X }
◆ The range is a subset of the codomain
◆ The function f will always be onto its range
➔ Injective / Bijective / Surjective Practice
.
➔ Identity Function
◆ The identity function on a set X, denoted IX : X → X
is defined as, for all x∈X, IX (x) = x
➔ Function Compositions
◆ Let f : A → Y and g : B → C be functions with Y⊆B.
The composition of f and g, denoted g॰f : A → C
Is defined by the rule g॰f (x) = g (f (x))
◆ Note: even if f : A → A & g : A → A are both defined,
◆ f॰g = g॰f need not be true
◆ Example:
● f(x) = 2x ● (g॰f)(2) = 16
● g(x) = x2 ● (f॰g)(2) = 8
◆ Properties:
Let X, Y, Z and W be sets.
Let f : X → Y, g : Y → Z, and h : Z → W
1. (h॰g)॰f = h॰(f॰g)(composition is associative)
2. f॰IX = f = IY ॰f
➔ Inverse Functions
◆ Let f be the invertible function s.t., f : X → Y,
Its inverse, is denoted f -1 : Y → X
◆ Invertibility Theorem: (all equivalently T / F)
● The function, f : X → Y, is invertible
● f is bijective (both injective and surjective)
(m = n & each x goes to a unique y, s.t. f is onto & 1-to-1)
● g॰f = IX and f॰g = IY
● ∀ x∈X and y∈Y, f(x) = y ⇔ g(y) = x
◆ An invertible function has only 1 unique inverse
◆ The inverse of f-1 is f
◆ Inverse Properties:
Let functions f and g be defined that f : X → Y and g: Y → Z
1. If f and g are both injective, then g॰f is injective
2. If f and g are both surjective, then g॰f is surjective
3. If f and g are both bijective, then g॰f is bijective
4. If g॰f is injective, then f is injective but g need not be
5. If g॰f is surjective, then g is surjective but f need not be
