surjection and axiom of choice


In this entry, we show the statement that

(*) every surjection has a right inverseMathworldPlanetmath

is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to the axiom of choiceMathworldPlanetmath (AC).

Proposition 1.

AC implies (*).

Proof.

Let f:AB be a surjection. Then the set C:={f-1(y)yB} partitions A. By the axiom of choice, there is a function g:CC such that g(f-1(y))f-1(y) for every yB. Since C=A, g is a function from C to A. Define h:BA by h(y)=g(f-1(y)). Then h(y)f-1(y), and therefore (fh)(y)=f(h(y))=y, implying that f has a right inverse. ∎

Remark. The function h is easily seen to be an injection: if h(y1)=h(y2), then y1=f(h(y1))=f(h(y2))=y2.

Proposition 2.

(*) implies AC.

Before proving this, let us remark that, in the collectionMathworldPlanetmath C of non-empty sets of the axiom of choice, there is no assumptionPlanetmathPlanetmath that the sets in C be pairwise disjoint. The statement

(**) given a set C of pairwise disjoint non-empty sets, there is a choice function f:CC

seemingly weaker than AC, turns out to be equivalent to AC, and we will prove this fact first.

Proof.

Obviously AC implies (**). Conversely, assume (**). Let C be a collection of non-empty sets. We assume C. For each aC, define a set Aa:={(x,a)xa}. Since a, Aa. In addition, AaAb= iff ab (true since elements of Aa and elements of Ab have distinct second coordinates). So the collection D:={AaaC} is a set consisting of pairwise disjoint non-empty sets. By (**), there is a function f:DD such that f(Aa)Aa for every aC. Now, define two functions g:CD and h:DC by g(a)=Aa and h(x,a)=x Then, for any aC, we have (hfg)(a)=h(f(Aa)). Since f(Aa)Aa, its first coordinate is an element of a. Therefore h(f(Aa))a, and hence hfg is the desired choice function. ∎

Proof of Propositon 2.

We show that (*) implies (**), and since (**) implies AC as shown above, the proof of PropositionPlanetmathPlanetmath 2 is then completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmath.

Let C be a collection of pairwise disjoint non-empty sets. Each element of C belongs to a unique set in C. Then the function g:CC taking each element of C to the set it belongs in C, is a well-defined function. It is clearly surjective. Hence, by assumption, there is a function f:CC such that gf=1C (a right inverse of g). For each xC, g(f(x))=x, which is the same as saying that f(x) is an element of x by the definition of g. ∎

Remark. In the category of sets, AC is equivalent to saying that every epimorophism is a split epimorphism. In general, a categoryMathworldPlanetmath is said to have the axiom of choice if every epimorphismMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath is a split epimorphism.

Title surjection and axiom of choice
Canonical name SurjectionAndAxiomOfChoice
Date of creation 2013-03-22 18:44:37
Last modified on 2013-03-22 18:44:37
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 9
Author CWoo (3771)
Entry type Derivation
Classification msc 03E25