Functions should be familiar from algebra.
A function has two associated sets: the domain of the function and the codomain of the function.
For each member of the domain, the function produces exactly one member of the codomain. If f is a function and x is a member of its domain then f(x) is the member of f's codomain that is associated with x.
For example, suppose that the domain and codomain are both Z, the set of all integers. If f is defined by
f(x) = x^2 + 1then f(1) = 2 and f(2) = 5.
The domain of a function can be a cartesian product. For example, we can define
g(x,y) = x + 2ywhere the parameter is an ordered pair of numbers. That should be familiar from algebra. The codomain can also be a cartesian product; that is a little less familar. For example, you might define
t(x,y) = (y,x)so that t(2,3) = (3,2).
We will shortly think of functions as computational problems. It is important that we not limit functions to those that can be defined by rules of some simple kind. Each function must associated one member of its codomain with each member of its domain, but how that association is defined is a separate issue.
The functions that we have defined above are called total functions. A total function must have an answer for every argument.
But look at the division operator, /. It is conventionally written as a binary operator, but that is just a notational convention: / is really a function that takes a pair of numbers and yields a number. To avoid notational confusion, lets define
d(x,y) = x/y.So d(6,2) = 3 and d(5,2) = 2.5.
But what about d(1,0)? We all learn that you are not allowed to divide by 0, so d(1,0) is undefined. That means that d is not a total function.
Since the division function does not produce a value for every possible argument, division must not be a function, according to our definition. We say that division is a partial function.
Normally, do not allow an algorithm to loop forever. If a program loops forever, it does not qualify as an algorithm.
But sometimes we relax that and allow some infinite loops. If computation of f(1) goes into an infinite loop, what should we say the answer is? The best thing to do is to say that the answer is undefined.
Symbol ⊥ means undefined. Symbol ⊥ has a name, bottom.
Now we can define what a partial function is. A partial function from domain A to codomain B is a function from domain A to codomain B∪{⊥}.
Two total functions f and g are equal to one another if
they have the same domain and codomain
f(x) = g(x) for every x.
The same definition works for partial functions if you just think of ⊥ as a value. For example, if f = g and f(1) = ⊥ then g(1) = ⊥.