Skip to content
Axiomatic Wiki
Lemma·L02

Composition preserves function properties

Composites of functions, injections, surjections, bijections are again such.

Let and be functions. Then:(i) the composite is a function;(ii) if and are injective, so is ;(iii) if is surjective onto and is surjective onto , then is surjective onto ;(iv) if both are bijections, so is .
In words
Composing two functions gives a function; composing two injections gives an injection; composing two surjections gives a surjection; and composing two bijections gives a bijection.
Rests onF02F03F04F05F06F09F14A01A02
Never needed: F08 · F10 · F11 · F12 · F13 · A03 · A04 · A05 · A06 · A07 · A08 (computed from the citation graph, not asserted).

Proof

  1. 1
    (i) Let . Then is the unique value of at , and is the unique value of at , both by D013. So the pair lies in by D018, and it is the only pair of with first coordinate : any such pair is with by definition, and equality of pairs is coordinatewise by L01. Hence every has exactly one value, and .
  2. 2
    (ii) Suppose for , that is, . Injectivity of gives , and injectivity of then gives (D014 twice).
  3. 3
    (iii) Let . Surjectivity of (D015) provides with , and surjectivity of provides with . Then . So every is attained.
  4. 4
    (iv) Immediate from (ii) and (iii), since a bijection is by definition an injective surjection (conjunction of the two properties).
∎

Remarks

Together with the identity and inverses, this lemma is what makes the bijections of any set into a group under composition, and it drives the transitivity of equinumerosity.
Wikipedia ↗Function.Bijective.comp ↗

Used by

L22L23L25L33
Propose an edit2 published revisions