Bijection Sets

Question

Suppose A, B, C and D are sets and that f : A → B , g : B → C and h : C → D are functions. Prove that if g ◦ f and h ◦ g are bijective, then g is bijective.

Answer 1

A function requires that one particular input maps to one and only one output. An input cannot map to more than one output, nor can it not map at all.

Consider the cardinality for bijective, injective, surjective function mappings between two sets X and Y:

BIJ: |X|=|Y|, INJ: |X|<|Y|, SUR: |X|>|Y|.

Also let < imply a difference of 1.

Now consider all composite mappings X→Y→Z applying the above rules.

	BIJ	INJ	SUR
BIJ	|X|=|Y|=|Z|⇒|X|=|Z|	|X|=|Y|<|Z|⇒|X|<|Z|	|X|=|Y|>|Z|⇒|X|>|Z|
INJ	|X|<|Y|=|Z|⇒|X|<|Z|	|X|<|Y|<|Z|⇒|X|<|Z|	|X|<|Y|>|Z|⇒|X|=|Z|
SUR	|X|>|Y|=|Z|⇒|X|>|Z|	|X|>|Y|<|Z|⇒|X|=|Z|	|X|>|Y|>|Z|⇒|X|>|Z|

In three cases |X|=|Z| indicating a possible composite bijection: BIJ-BIJ, INJ-SUR, SUR-INJ. For bijective mappings (g o f)(x) = g(f(x)) and (h o g)(x)= h(g(x)), g(x) is either the first or second mapping. So clearly in BIJ-BIJ g(x) is bijective.

In the other two cases g(x) would have to be injective in one instance and surjective in the other. The only way this can happen is if g(x) is both, that is, it is bijective.