• Home
• Foundations
Thomas A. Alspaugh
Correspondences A correspondence correspondence correspondence correspondence f between X and Y is a triple (X,Y,Γ) where Γ is a subset of the Cartesian product X×Y.

• The pre-domain of f is X.
• The co-domain of f is Y.
• Γ is the graph of f. (Note that Γ is a binary relation.)
• The domain of f (written Dom(f)) is {xX|∃yY ( (x,y)Γ ) }.
• The range of f (written Im(f)) is { yY | ∃xX ( (x,y)Γ ) }.
• yY is an image of xX if (x,y)Γ.
• The image of WX is { yY | ∃xW ( (x,y)Γ ) }.
• xX is a pre-image of yY if (y,x)Γ.
• The pre-image of VY is { xX | ∃yV ( (x,y)Γ ) }.
• The converse of f, written f-1 is the correspondence whose graph is { (y,x) | (x,y)Γ } 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.

# Functions

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.

# Mappings

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

A mapping f:XY is:

 onto or surjective if each y∈Y 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 x∈X maps to at most one y∈Y injective if each y∈Y is mapped to by x∈X