Kinds of correspondences

A correspondence f between X and Y is a triple (X,Y,Γ) where Γ is a subset of the Cartesian product X×Y

Parts of a correspondence

The graph of a correspondence is not constrained in the number of edges into or out of each element:  the image of a domain element can be empty, a singleton, or larger,

as can the pre-image of a range element. 


A function f:XY is a correspondence (X,Y,Γ) that assigns at most one range element to each element of its domain. Equivalently, the image of every element in the domain of f is a singleton. 


A mapping is a function whose domain is its entire pre-domain.

A mapping f:XY is:

onto or surjective if each yY has at least one pre-image in f
one-to-one injective at most
one-to-one and onto bijective exactly

The analogous concepts for binary relations

The pre-domain and co-domain are not relevant for a relation,, since a relation is simply a set of tuples. 

A relation r that is a subset of X×Y is:

functional if each xX maps to at most one yY
injective if each yY is mapped to by xX
Valid XHTML 1.0 Strict
Valid CSS!
Thomas A. Alspaugh