A function collision is a pair of distinct inputs with . An injective function has no collisions. For a two-to-one function every nonempty fiber has two elements and hence one unordered collision pair. Finding such a pair through an oracle is the task of quantum collision finding.
In the finite example under image and preimage of a function, the pair is a function collision: both inputs give zero. The function retains their shared output but loses the distinction between them. If a finite set has more inputs than the number of available outputs, the pigeonhole principle forces a function collision. Equal source and target cardinalities alone do not prevent one.
For a finite function, let be the cardinality of its fiber of a function over . The number of unordered function collisions is , because each pair must lie in one common fiber. The example's nonempty fiber sizes are , giving exactly one collision pair.
New to topics? Read the docs here!