one-to-one function from onto function


Given an onto functionMathworldPlanetmath from a set A to a set B, there exists a one-to-one function from B to A.


Suppose f:AB is onto, and define ={f-1({b}):bB}; that is, is the set containing the pre-image of each singleton subset of B. Since f is onto, no element of is empty, and since f is a function, the elements of are mutually disjoint, for if af-1({b1}) and af-1({b2}), we have f(a)=b1 and f(a)=b2, whence b1=b2. Let 𝒞: be a choice function, noting that =A, and define g:BA by g(b)=𝒞(f-1({b})). To see that g is one-to-one, let b1,b2B, and suppose that g(b1)=g(b2). This gives 𝒞(f-1({b1}))=𝒞(f-1({b2})), but since the elements of are disjoint, this implies that f-1({b1})=f-1({b2}), and thus b1=b2. So g is a one-to-one function from B to A. ∎

Title one-to-one function from onto function
Canonical name OnetooneFunctionFromOntoFunction
Date of creation 2013-03-22 16:26:55
Last modified on 2013-03-22 16:26:55
Owner mathcam (2727)
Last modified by mathcam (2727)
Numerical id 8
Author mathcam (2727)
Entry type Definition
Classification msc 03E25
Related topic function
Related topic ChoiceFunction
Related topic AxiomOfChoice
Related topic set
Related topic onto
Related topic SchroederBernsteinTheorem
Related topic AnInjectionBetweenTwoFiniteSetsOfTheSameCardinalityIsBijective
Related topic ASurjectionBetweenTwoFiniteSetsOfTheSameCardinalityIsBijective
Related topic Set
Related topic SurjectivePlanetmathPlanetmath