Jections

Properties of Surjections, Injections and Bijections



Some properties of surjections, injections and bijections are presented with proofs here.
Below f is a function from a set A to a set B, and g is a function from the set B to a set C.

Property 1:   If f and g are surjections, then fg is a surjection.

Proof of Property 1:
Let z an arbitrary element in C.
Then since f is a surjection, there is an element y in B such that z = f(y).
Then since g is a surjection, there is an element x in A such that y = g(x).
Hence by the definition of composite function, z = f(g(x)), that is z = fg(x).
Hence fg is a surjection.
QED



Property 2:   If f and g are injections, then fg is an injection.

Proof of Property 2:
Let x1 and x2 be arbitrary elements in A.
Suppose that f(g(x1)) = f(g(x2)).
Then since f is an injection, g(x1) = g(x2).
Then since g is an injection, x1 = x2.
That is for any pair of elements x1 and x2 in A if f(g(x1)) = f(g(x2)), then x1 = x2.
Hence fg is an injection.
QED



Property 3:   If f and g are bijections, then fg is a bijection.

Proof of Property 3:
Obviously this follows from Properties 1 and 2.


Property 4:   If fg is a surjection, then f is a surjection.

Proof of Property 4:
Let z an arbitrary element in C.
Then since fg is a surjection, there is an element x in A such that z = f(g(x)).
By the definition of fg, there is an element y in B such that y = g(x) and z = f(y).
Hence for an arbitrary element z in C, there is an element y in B such that z = f(y).
Hence f is a surjection.
QED



Property 5:   If fg is an injection, then g is an injection.

Proof of Property 5:
Proof is left as an exercise.



Property 6:   If fg is a bijection, then f is a surjection and g is an injection.

Proof of Property 6:
Obviously this follows from Properties 4 and 5.


Below f is a function from a set A to a set B, S ⊆ A, and T ⊆ B.

Property 7:   If f is a bijection, then f( S ∩ T ) = f(S) ∩ f(T)

Proof of Property 7:
Since f( S ∩ T ) ⊆ f(S) ∩ f(T) for a function f, we need to prove that f(S) ∩ f(T) ⊆ f( S ∩ T ) for a bijection f.

Let y be an arbitrary element of f(S) ∩ f(T).

Then there is an element x1 in S and an element x2 in T such that y = f(x1) = f(x2).

Since f is a bijection, it is an injection.
Hence if f(x1) = f(x2), then x1 = x2.
Hence x1 (= x2) ∈ S ∩ T.
Hence y (= f(x1) = f(x2)) ∈ f( S ∩ T ).
Hence f(S) ∩ f(T) ⊆ f( S ∩ T ) if f is a bijection.

QED





Back to Schedule
Back to Table of Contents