==Formal definition==
Formally a function ''f'' from a
Set ''X'' to a set ''Y'', written ''f'' : ''X'' → ''Y'', is an
ordered triple (''X'', ''Y'', ''G''(''f'')), where ''G''(''f'') is a
Subset of the
Cartesian_product ''X'' × ''Y'', such that for each ''x'' in ''X'', there is a unique ''y'' in ''Y'' such that the
Ordered_pair (''x'', ''y'') is in ''G''(''f''). ''X'' is called the
domain of ''f'', ''Y'' is called the
Codomain of F, and ''G''(''f'') is called the
graph of ''f''. For each "input value" ''x'' in the domain, the corresponding unique "output value" ''y'' in the codomain is denoted by ''f''(''x'').
Equivalently a function f can be defined as a
relation between ''X'' and ''Y'' which satisfies:
# ''f'' is ''total'', or ''entire'': for all ''x'' in ''X'', there exists a ''y'' in ''Y'' such that ''x f y'' (''x'' is ''f''-related to ''y''), i.e. for each input value, there is at least one output value in ''Y''.
# ''f'' is ''many-to-one'', or ''functional'': if ''x f y'' and ''x f z'', then ''y'' = ''z''. i.e., many input values can be related to one output value, but one input value cannot be related to many output values.
A relation between ''X'' and ''Y'' that satisfies condition (1) is a '''
Multivalued_function'''. Every function is a multivalued function, but not every multivalued function is a function. A relation between ''X'' and ''Y'' that satisfies condition (2) is a '''
Partial_function'''. Every function is a partial function, but not every partial function is a function. In this encyclopedia, the term "function" will mean a relation satisfying both conditions (1) and (2), unless otherwise stated.
Consider the following three examples:
Image:notMap1.png | This relation is total but not many-to-one; the element 3 in ''X'' is related to two elements ''b'' and ''c'' in ''Y''. Therefore, this is a multivalued function, but ''not'' a function. |
Image:notMap2.png | This relation is many-to-one but not total; the element 1 in ''X'' is not related to any element of ''Y''. Therefore, this is a partial function, but ''not'' a function. | |
Image:mathmap2.png | This relation is both total and many-to-one, and so it is a function from ''X'' to ''Y''. Note that the emphasis is on "-to-one" as "many" may actually mean "one". The function can be given explicitly by specifing its graph ''G''(''f'') = {(1, d), (2, d), (3, c)} or as
: |
It is common practice to identify a function with its graph, however, the distinction becomes important when considering
surjectivity,
restrictions and
compositions of functions.
The set of all functions ''f'' : ''X'' → ''Y'' is denoted by ''Y
X''. Note that ''|Y
X| = |Y|
|X|'' (refer to
Cardinal numbers).