the same number of elements, then is surjective if and only if f is injective. Given two sets X and Y, the notation is used to say that either X is empty or that there is a surjection from Y onto X. Using the axiom of choice one can show that and together imply that |Y| = |X|, a variant of the Schröder–Bernstein theorem. Composition and decomposition The composition of surjective functions is always surjective: If f and g are both surjective, and the codomain of g is equal to the domain of f, then is surjective. Conversely, if is surjective, then f is surjective (but g, the function applied first, need not be). These properties generalize from surjections in the category of sets to any epimorphisms in any category. Any function can be decomposed into a surjection and an injection: For any function there exist a surjection and an injection such that h = g o f. To see this, define Y to be the set of preimages where z is in . These preimages are disjoint and partition X. Then f carries each x to the element of Y which contains it, and g carries each element of Y to the point in Z to which h sends its points. Then f is surjective since it is a projection map, and g is injective by definition. Induced surjection and induced bijection Any function induces a surjection by restricting its codomain to its range. Any surjective function induces a bijection defined on a quotient of its domain by collapsing all arguments mapping to a given fixed image. More precisely, every surjection can be factored as a projection followed by a bijection as follows. Let A/~ be the equivalence classes of A under the following equivalence relation: x ~ y if and only if f(x) = f(y). Equivalently, A/~ is the set of all preimages under f. Let P(~) : A → A/~ be the projection map which sends each x in A to its equivalence class [x]~, and let fP : A/~ → B be the well-defined function given by fP([x]~) = f(x). Then f = fP o P(~). Space of surjections Given fixed and , one can form the set of surjections . The cardinality of this set is one of the twelve aspects of Rota's Twelvefold way, and is given by , where denotes a Stirling number