properties of bijections

Let A,B,C,D be sets. We write AB when there is a bijection from A to B. Below are some properties of bijections.

  1. 1.

    AA. The identity functionMathworldPlanetmath is the bijection from A to A.

  2. 2.

    If AB, then BA. If f:AB is a bijection, then its inverse functionMathworldPlanetmath f-1:BA is also a bijection.

  3. 3.

    If AB, BC, then AC. If f:AB and g:BC are bijections, so is the compositionMathworldPlanetmathPlanetmath gf:AC.

  4. 4.

    If AB, CD, and AC=BD=, then ABCD.


    If f:AB and g:CD are bijections, so is h:ACBD, defined by

    h(x)={f(x) if xA,g(x) if xC.

    Since AC=, h is a well-defined function. h is onto since both f and g are. Since f,g are one-to-one, and BD=, h is also one-to-one. ∎

  5. 5.

    If AB, CD, then A×CB×D. If f:AB and g:CD are bijections, so is h:A×CB×D, given by h(x,y)=(f(x),g(y)).

  6. 6.

    A×BB×A. The function f:A×BB×A given by f(x,y)=(y,x) is a bijection.

  7. 7.

    If AB and CD, then ACBD.


    Suppose ϕ:AB and σ:CD are bijections. Define F:ACBD as follows: for any function f:AC, let F(f)=σfϕ-1:BD. F is a well-defined function. It is one-to-one because σ and ϕ are bijections (hence are cancellable). For any g:BD, it is easy to see that F(σ-1gϕ)=g, so that F is onto. Therefore F is a bijection from AC to BD. ∎

  8. 8.

    Continuing from property 8, using the bijection F, we have Mono(A,B)Mono(C,D), Epi(A,B)Epi(C,D), and Iso(A,B)Iso(C,D), where Mono(A,B), Epi(A,B), and Iso(A,B) are the sets of injections, surjectionsMathworldPlanetmath, and bijections from A to B.

  9. 9.

    P(A)2A, where P(A) is the powerset of A, and 2A is the set of all functions from A to 2={0,1}.


    For every BA, define φB:A2 by

    φB(x)={1 if xB,0 otherwise.

    Then φ:P(A)2A, defined by φ(B)=φB is a well-defined function. It is one-to-one: if φB=φC for B,CA, then xB iff xC, so B=C. It is onto: suppose f:A2, then by setting B={xAf(x)=1}, we see that φB=f. As a result, φ is a bijection. ∎

Remark. As a result of property 9, we sometimes denote 2A the powerset of A.

Title properties of bijections
Canonical name PropertiesOfBijections
Date of creation 2013-03-22 18:50:41
Last modified on 2013-03-22 18:50:41
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 6
Author CWoo (3771)
Entry type Derivation
Classification msc 03-00