Onto (Surjective) Functions: Definition, Counting Formula and Properties

A mapping can use every domain element and still fail to be onto, because surjectivity is checked against the codomain, not the domain. Functions in Discrete Mathematics: Types, Counting and Worked Examples distinguishes injective, surjective and bijective maps and counts a three-input, two-output example. Surjection-specific work goes further: the 4 -> 3 count requires inclusion-exclusion, while fibres, boundary cases, composition and right inverses reveal the underlying structure.

Onto function definition: codomain coverage is the entire test

For a function f:A -> B, every x in A must have exactly one output in B. Its image is f(A)={f(x):x in A}. The function is onto, or surjective, when f(A)=B. Equivalently, for every y in B, there exists x in A such that f(x)=y.

Keep the three sets clear. Let A={1,2,3,4}, B={a,b,c} and define f(1)=a, f(2)=b, f(3)=a, f(4)=c. The domain is A, the declared codomain is B, and the image is {a,b,c}. Therefore, f is onto even though a has two preimages. If the notation feels unfamiliar, revise Definition of a Function: Domain, Codomain, Range and Counting Formula first.

Now define g:A -> B by g(1)=a, g(2)=b, g(3)=a, g(4)=b. It is a valid function, but it is not onto: g(A)={a,b} and g^{-1}({c}) is empty.

Check surjectivity step by step with fibres and missing outputs

Use the same three-step audit every time:

1. Write the declared codomain.

2. Compute or trace the complete image.

3. Compare the image with the codomain.

For f, the fibres are f^{-1}({a})={1,3}, f^{-1}({b})={2} and f^{-1}({c})={4}. Every fibre is non-empty, so f is onto. To disprove surjectivity, one missing codomain element is enough. For g, choose c as the witness: there is no x in A with g(x)=c. No further calculation is needed.

The rule is identical for equations. For h:R -> R, h(x)=2x-5 is onto because an arbitrary target y is reached by choosing x=(y+5)/2. Substitution gives h((y+5)/2)=y. In contrast, q:R -> R, q(x)=x^2 is not onto because the target -1 has no real preimage. Arrow diagrams and algebra are testing the same condition: does every declared output have at least one input?

Count onto functions with inclusion-exclusion: 4 -> 3 worked fully

Count the onto functions from A={1,2,3,4} to B={a,b,c}. First count all functions. Each of the four domain elements has three choices, so the total is 3^4=81.

Let E_a, E_b and E_c be the sets of functions that miss a, b and c, respectively. If a function misses one specified output, every input has only two choices. Thus each event contains 2^4=16 functions, and we initially subtract 3*16=48.

That subtraction removes some functions twice. A pairwise intersection such as E_a intersect E_b contains functions that miss both a and b. All four inputs must then go to the sole remaining output c, so the intersection has 1^4=1 function. There are C(3,2)=3 pairwise intersections, so add 3. No function from non-empty A can miss all three outputs, so the triple intersection contributes 0.

Therefore,

N_onto(4,3)=81-48+3-0=36.

For positive integers m=|A| and n=|B|, the general formula is

N_onto(m,n)=sum from i=0 to n of (-1)^i C(n,i)(n-i)^m.

The alternating signs subtract maps missing at least one output, add back maps subtracted twice, and continue correcting overlaps.

Counting formula boundary cases and the partition interpretation

Three boundary checks make finite, non-empty cases faster. If m<n, no function can cover every codomain value, so N_onto(2,3)=0. If m=n, every onto function is a bijection, so N_onto(3,3)=3!=6. If n=1, every input must map to the single output, so N_onto(5,1)=1.

An equivalent formula is N_onto(m,n)=n! S(m,n). Here, S(m,n) partitions the m labelled domain elements into n non-empty, unlabelled fibres. The factor n! assigns those fibres to the n labelled codomain values. In the central example, S(4,3)=6, so 3!*6=6*6=36.

Use inclusion-exclusion for a direct derivation from the condition that no codomain value may be empty. Use the Stirling-number form when S(m,n) is known or when the fibre structure matters.

Onto function properties: composition, right inverses and finite cardinality

If f:A -> B and r:B -> C are onto, then r o f:A -> C is onto. Every value in C has a preimage in B under r, and that value in B has a preimage in A under f.

Reuse the earlier f and set C={0,1} with r(a)=0, r(b)=1, r(c)=1. The composite sends 1,2,3,4 to 0,1,0,1, so it reaches both outputs.

A useful converse fragment is also true: if r o f is onto, then r must be onto. However, f need not be onto. Let U={p,q}, V={1,2,3,4} and W={red,blue}, with f(p)=1, f(q)=4 and r(1)=red, r(2)=red, r(3)=blue, r(4)=blue. The map f misses 2 and 3, but r o f sends p to red and q to blue, so the composite is onto W.

For finite sets, an onto function has a right inverse. For the first map, choose s:B -> A with s(a)=1, s(b)=2, s(c)=4. Then f o s=id_B. Finally, when |A|=|B|, onto, one-to-one and bijective are equivalent. When |A|<|B|, an onto function is impossible.

Common surjection traps and the exact repair for each

There is also an overlap trap. Subtracting 3*16 from 81 gives 33, not the answer, because the three constant functions were each subtracted twice. Add the three pairwise intersections to repair the count: 33+3=36.

For composition, r o f onto guarantees that the outer function r is onto, not the inner f. The U={p,q}, V={1,2,3,4}, W={red,blue} counterexample above proves it. Use Set Theory and Relations MCQs: 12 Solved for more prerequisite drills.

How exam-style questions test onto functions

Stable question forms ask you to identify whether an arrow map is onto, solve f(x)=y for an arbitrary target, count surjections between finite sets, or judge statements about composition, inverses and cardinality.

For a finite-set numerical, use a fixed order. Write m=|A| and n=|B|. Return 0 immediately if m<n. Otherwise, write the count of all functions as n^m, name the missing-output events, and apply inclusion-exclusion with every overlap. Where possible, check the result against the m=n or n=1 boundary case.

Once you can redo the counting steps unaided, the GATE Test Series gives mixed, timed practice across functions and relations.

Onto functions: the short version and next step

Remember four lines: onto means image=codomain; one missing output disproves it; the finite count is sum (-1)^i C(n,i)(n-i)^m; and the central example gives 3^4-3*2^4+3*1^4=36.

Redraw both finite maps, then recompute 36 without looking. If you need the wider mathematics sequence around this topic, continue with Engineering Mathematics for GATE.