Composition, inverse and recursive functions
Composition combines functions by feeding the output of one to another; inverses undo bijections and follow a reverse order rule; recursive functions are defined by base cases and rules and are used to compute sequences like factorials and Fibonacci numbers.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Functions model input–output relationships in engineering: signal transformations, address translations, hash maps, and state updates are functions. Composition models pipelines (output of one stage becomes input of next). Inverse functions undo transformations (decrypting, decoding, solving for input). Recursive functions define sequences and algorithms (factorial, Fibonacci, divide-and-conquer), and are the basis for many program proofs and recurrence relations.
Key ideas
Start with simple terms.
- Function: A function f from set A to set B, written f: A → B, is a rule that assigns to every element x in domain A exactly one element f(x) in codomain B. (Assume well-defined: no ambiguity for any x in A.)
- Domain: the set A of allowed inputs of f.
- Codomain: the set B that contains possible outputs (may be larger than actual outputs).
- Image or range of f: the set { f(x) | x ∈ A }, a subset of the codomain B.
Properties of functions (definitions universities expect):
- Injective (one-to-one): f: A → B is injective if for all x1,x2 ∈ A, f(x1)=f(x2) implies x1=x2.
- Surjective (onto): f: A → B is surjective if for every y ∈ B there exists x ∈ A with f(x)=y.
- Bijective: f is bijective if it is both injective and surjective.
Composition:
- Composition: Given f: A → B and g: B → C, the composition g ∘ f is the function g∘f: A → C defined by (g∘f)(x) = g(f(x)) for all x ∈ A. (Requires the codomain of f equals or is compatible with the domain of g. More precisely, it is enough that Im(f) ⊆ Dom(g).)
- Associativity of composition (law): If f: A→B, g: B→C, h: C→D, then h∘(g∘f) = (h∘g)∘f. Proof (standard): compute both sides on an arbitrary x ∈ A: left gives h(g(f(x))) and right gives h(g(f(x))) — identical for all x, so functions equal.
Identity and inverses:
- Identity function: For a set A, the identity function I_A: A→A is defined by I_A(x)=x for all x ∈ A.
- Inverse function: If f: A→B is bijective, then the inverse f^{-1}: B→A is the unique function satisfying f^{-1}(f(x)) = x for all x ∈ A and f(f^{-1}(y)) = y for all y ∈ B. (Exists iff f is bijective.)
Theorem (existence of inverse): A function f: A→B has an inverse function f^{-1}: B→A if and only if f is bijective. Proof (two directions):
- If f has an inverse g: B→A with g∘f = I_A and f∘g = I_B, then f is injective: if f(x1)=f(x2) apply g to both sides to get x1=x2; and f is surjective: for any y∈B, y = f(g(y)).
- If f is bijective, define g: B→A by for each y∈B pick the unique x with f(x)=y (existence and uniqueness from bijectivity). Then g is the inverse: g(f(x)) = x and f(g(y)) = y. Uniqueness: any inverse must equal g.
Inverse of a composition (important law): If f: A→B and g: B→C are bijections, then g∘f is a bijection and (g∘f)^{-1} = f^{-1}∘g^{-1}. Proof: For any x∈A, (f^{-1}∘g^{-1})(g(f(x))) = f^{-1}(f(x)) = x, and similarly on C; uniqueness implies equality.
Left and right inverses (useful when not bijective): If f: A→B and g: B→A satisfies g∘f = I_A, then g is a left-inverse of f and f is injective. If f∘h = I_B, then h is a right-inverse of f and f is surjective. A function with both left- and right-inverse is bijective and inverses coincide.
Recursive functions:
- Recursive function: a function defined using simpler values of itself, with two parts: a base case (explicit values for small inputs) and a recursive step (rule expressing f(n) in terms of f(k) for smaller k).
- Well-definedness and termination: a recursive definition must reach base cases in finitely many steps for every input (otherwise it is not a valid function). In exams, show termination or use induction to prove correctness.
Describe diagrams to draw (exam instruction):
- Composition diagram: draw three labelled sets A, B, C as three circles left to right. Mark an element x in A, arrow from x to f(x) in B, arrow from f(x) to g(f(x)) in C. Label arrows f and g. This shows (g∘f)(x).
- Inverse diagram: draw A and B, show bijection arrows both directions between matched points; label forward arrow f and backward arrow f^{-1}.
Formulas
(g∘f)(x) = g(f(x)) — f: A→B, g: B→C; applies when the image of f is a subset of the domain of g (a sufficient condition is Codom(f) ⊆ Dom(g)); units: none.
I_A(x) = x — identity on A; units: none. Composition with identity: for f: A→B, f∘I_A = f and I_B∘f = f.
f is injective ⇔ (∀x1,x2 ∈ A, f(x1)=f(x2) ⇒ x1=x2) — predicate; units: none.
f is surjective ⇔ (∀y ∈ B, ∃x ∈ A such that f(x)=y) — predicate; units: none.
f is bijective ⇔ f is injective and surjective — predicate. If f and g are injective, then g∘f is injective. If f and g are surjective, then g∘f is surjective. If f and g are bijective, then g∘f is bijective. Also: g∘f injective ⇒ f injective, and g∘f surjective ⇒ g surjective.
(g∘f)^{-1} = f^{-1}∘g^{-1} — requires f,g bijections. Also, if f is bijective then f^{-1} is bijective and (f^{-1})^{-1} = f.
Factorial: n! = 1 if n=0; n! = n·(n-1)! for n≥1 — recursive definition; units: none. Domain: n ∈ N (nonnegative integers).
Fibonacci: F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2} for n≥2 — recursive; units: none. Domain: n ∈ N.
Left-inverse: g∘f = I_A ⇒ f injective — consequence; units: none.
Right-inverse: f∘h = I_B ⇒ f surjective — consequence; units: none.
Worked examples
Example 1 — finite sets and composition (exam-style answer): Given A={1,2,3}, B={a,b,c}, C={X,Y}. Let f: A→B with f(1)=a, f(2)=b, f(3)=a. Let g: B→C with g(a)=X, g(b)=Y, g(c)=X.
- Compute g∘f: for each x∈A, (g∘f)(1)=g(f(1))=g(a)=X; (g∘f)(2)=g(b)=Y; (g∘f)(3)=g(a)=X.
- Is f injective? No, because f(1)=f(3)=a but 1≠3.
- Is g surjective? Yes, images {X,Y} = C.
- Is g∘f injective? No: (g∘f)(1)=(g∘f)(3)=X but 1≠3. Show failure matches theorem that composition inherits injectivity only if inner f is injective. Final answer: g∘f = {1↦X,2↦Y,3↦X}. (State reasons for injective/surjective.)
Example 2 — algebraic functions, inverses and composition order: Let f: R→R given by f(x)=2x+3. Let g: R→R given by g(x)=x-1. Both are bijections R→R.
- Find inverses: f^{-1}(y) = (y-3)/2; g^{-1}(y) = y+1.
- Compute (g∘f)(x) = g(f(x)) = (2x+3)-1 = 2x+2.
- Compute inverse of (g∘f) directly: solve y=2x+2 ⇒ x=(y-2)/2.
- Compute f^{-1}∘g^{-1}: f^{-1}(g^{-1}(y)) = f^{-1}(y+1) = ((y+1)-3)/2 = (y-2)/2. Conclusion: (g∘f)^{-1} = f^{-1}∘g^{-1} as expected. Final answers boxed: f^{-1}(y)=(y-3)/2, g^{-1}(y)=y+1, (g∘f)^{-1}=(y-2)/2.
Example 3 — recursive computation and trace (factorial and Fibonacci): (a) Compute 5! with the recursive definition n!= n·(n-1)!, base 0!=1. Steps: 5! = 5·4!; 4! = 4·3!; 3! = 3·2!; 2! = 2·1!; 1! = 1·0!; 0! =1. Substitute up: 1!=1; 2!=2; 3!=6; 4!=24; 5!=120. Final: 120. (b) Compute F_6 with F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}. Steps: F_2=1, F_3=2, F_4=3, F_5=5, F_6=8. Final: 8. Showing recursion trace for F_6: expand F_6 = F_5+F_4 = (F_4+F_3)+F_4 = ... until base values reached; count and show you eventually reduce to F_1 and F_0.
Common mistakes
- Forgetting to check domains when composing functions (g∘f undefined if f(x) lands outside domain of g).
- For recursive definitions: omitting base cases or giving a recursive step that does not reduce to the base case (leading to non-termination).
- Mistaking left-inverse for full inverse: a left-inverse guarantees injectivity but not surjectivity.
- Arithmetic slip in algebraic inverses: solve y=2x+3 properly for x.
- Assuming composition is commutative: in general f∘g ≠ g∘f; order matters.
For your exam
Types of questions you will see:
- Definitions: define injective/surjective/bijective, composition, inverse, recursive function. Include examples and counterexamples.
- Short proofs: prove associativity of composition; prove that if f and g are injective then g∘f is injective; show existence of inverse iff bijection.
- Calculations: compute specific compositions from given tables or formulas; find inverse of simple functions; compute recursively defined values.
- Diagrams: draw mapping diagrams showing composition or inverse; label sets, arrows, and particular elements.
- Derivations: demonstrate (g∘f)^{-1} = f^{-1}∘g^{-1} with step-by-step reasoning. What a full-marks answer contains:
- Precise definitions using quantifiers or words equivalent to quantifiers.
- Clear domain/codomain statements and any restrictions (e.g., domain restriction for invertibility).
- Step-by-step proofs with statements and reasons (e.g., assume f(x1)=f(x2), apply left-inverse to conclude x1=x2).
- For recursive problems show base case(s), recursive step, and a finite trace to base cases or a proof by induction for general claims.
- Correct diagrams labeled exactly as requested.
Quick check
- If f: A→B is injective and g: B→C is injective, is g∘f injective? (Yes/No)
- Suppose f: R→R is f(x)=x^2. Is f invertible as a function R→R? If not, how can you change domain to make it invertible?
- Give base cases and recursive step for the factorial function. Answers: 1. Yes — composition of injective functions is injective. 2. No; x^2 is not injective on R (x and −x map to same value); restrict domain to [0,∞) and codomain to [0,∞) (so f: [0,∞)→[0,∞)) to make it bijective; the inverse is sqrt(x). 3. Base case 0!=1; recursive step n!=n·(n-1)! for n≥1.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?