% Functions and Relations
\newcommand\fun{\mathop{\lambda}}
### Functions ###
A **function** is a rule or mapping from one or more arguments to a "result" or "value" or "output". If the function is defined only on members of a set $\Delta$, we can say it's (at least) a **partial function** on the **domain** $\Delta$. If it's defined on *all* the members of $\Delta$, then it's a **total function** on the domain $\Delta$. When we say just "function" without qualification, we're normally talking about total functions.
There's another use of the term "domain" in the literature we'll be discussing, when we talk about the "domain" of a quantifier. These uses are related, but they aren't obviously and straightforwardly derivable from each other.
There is a lot of variation in how the term "range" is used. Some authors use it to mean what I'm calling the function's codomain. And some authors talk not only about the "image of $d$ under $f$", but also about "the image of $f$" itself, by which they mean what I'm calling $f$'s range.
If $\Theta\se\Gamma$ is a subset of $f$'s codomain, then the **preimage** of $\Theta$ is the largest subset of $f$'s domain such that $f$ maps every member of that set into $\Theta$. For example, if $f\colon \Z\to\N$ maps each $z$ to $z^2$, then the preimage of $\set{4,9}$ will be $\set{-2,2,-3,3}$.
I don't think we'll need to make use of this notion. I'm only mentioning it here for reference, in case you come across it and wonder what it means.
When $f$ takes more than one argument, we'll say that its domain is a set of tuples, like $\Delta_1 \times \Delta_2$, and we'll write that $f\colon \Delta_1 \times \Delta_2 \to \Gamma$. This is not the only way to handle multiple arguments, but it is the style of handling them that you'll find in the literature we'll be reading.
Finally, the **graph** of a function $f$ with domain $\Delta$ and codomain $\Gamma$ is the set $\set{(d,c) \where d\in\Delta\latin{ and }c\in\Gamma\latin{ and }f(d)=c}$. Sometimes I slip and call this the function's "extension", but in fact the standard terminology is to call this the function's "graph" and to reserve the term "extension" for *predicates*. (The graph of a unary function $f$ *may* be the same set of pairs as the extension of some dyadic predicate "F".)
Some authors identify functions with their graphs. This raises two sets of issues. One is similar to the kind of issue raised by the identifications of $(a,b)$ with $\set{\set{a},\set{a,b}}$ and of $(a,b,c)$ with $(a,(b,c))$. There could be an intelligible argument about whether these objects should be identified, or rather whether they should instead be thought of as having some intimate (perhaps unique) corresondence.
A second kind of issue is different: this is that some authors, in certain contexts, want to distinguish between functions whose codomains differ, even if the functions have the same graph. (Similar things could be said about the domains, if the functions are partial.) That is, they may want to distinguish the function that maps every $z\in\Z$ to $z^2$ and whose codomain is the set of natural numbers $\N$, and the corresponding function whose codomain is the set of all integers $\Z$, even though none of the members of $\Z-\N$ are the value of this function for any argument.
I don't expect the merits of saying this to be obvious at this point in our studies. Like a number of other debates, I'm just flagging this so that you're aware that there are choices being made, about which arguments can be had. I think we can avoid taking a stand on the question whether there can be distinct functions with the same graph.
Functions cannot be "one-to-many." For a single argument (or tuple of arguments), the function must have only a single value. (Or if it's a partial function, the function must only have a single value if it's defined for that argument.) Of course, the single value could be a set. So if you found yourself in a situation where you wanted something like a one-$\Delta$-to-many-$\Gamma$s function, you might scratch your itch by instead working with a function whose values are sets of $\Gamma$s.
Functions can however be "many-to-one." For instance, consider the height function. Perhaps Sam is taller than me, but Vera and I are the same height. Then the "height-in-centimeters" function would map Sam and me to distinct numbers, but would map me and Vera to the same number. That is, it sometimes maps distinct arguments (me and Vera) to the same value (whatever our common height in centimeters happens to be).
Some functions are not many-to-one. These functions always map distinct arguments to distinct values. For instance, let $\Mu$ be the set of males who have children, and $\Rho$ the set of people, and let $f\colon \Mu\to\Rho$ be the function that maps a member of $\Mu$ to his firstborn child. Assuming no genetic engineering or special fertilization techniques, no two males have the same firstborn child. Functions of this sort, that always map distinct arguments to distinct values, are known as **one-to-one**. Another term sometimes used for this is that the functions are "injective" or "an injection."
Whether a function is one-to-one may depend on what you take its domain to be. For example, if we considered the function "firstborn child" to be defined not on the set of male parents, but on the set of male or female parents, then it would no longer be one-to-one, because some distinct parents have the same firstborn child.
Notice that the range of the "firstborn child" relation is smaller than what I designated as its codomain. Some members of $\Rho$ are not anyone's firstborn child. When this is *not* the case---when every member of the codomain is the value of *some* argument to that function---then we say that the function is (not merely into but) **onto** that codomain. Another term sometimes used for this is that the function is "surjective."
Functions can be one-to-one without being onto, and they can be onto without being one-to-one. But they can also be both. Functions that do have both of these properties are called **one-to-one correspondences**. Another term used for this is that the functon is "bijective" or "a bijection."
The terms "injective" and "surjective" can be applied to partial functions as well as to total functions. Generally, though, the term "bijection" is restricted to *total* functions.
As we'll discuss later, when a function is bijective, then its domain and codomain have to have the same size.
[Wikipedia](https://en.wikipedia.org/wiki/Bijection,_injection_and_surjection) has some diagrams of functions having and lacking some of these features. So too does a Partee reading I assigned.
Here's another HOMEWORK EXERCISE:
(13) Consider the functions described below, where $x\in \Chi\latin{ and }y\in\Psi$. Is the function injective? is it surjective?
a. $f(x,y) = x$
b. $f(x,y) = (y,x)$
c. $f(x) = (x,y_0)\latin{, for some fixed }y_0\in\Psi$
A **permutation** is a bijective function from a set to itself. You can think of it as a way to shuffle the members of the set around. The members of the set don't need to be *ordered* in any way, to be permutable in this sense.
HOMEWORK EXERCISES:
(14) Let $\Alpha$ be a finite set, and $f$ be a function from $\Alpha$ into $\Alpha$. (a) Explain why $f$'s being injective implies it is also surjective. (b) Explain why $f$'s being surjective implies it is also injective.
(15) Are (14a) and (14b) true when $\Alpha$ is infinite? If not, give counterexamples.
One special kind of permutation maps every member of its domain to that very same member. This is known as the **identity function** on that domain.
Suppose we have two functions $f\colon \Delta \to \Gamma$ and $g\colon \Gamma \to \Rho$. For example, $f$ might be the function that maps me to my height in centimeters and $g$ be the function that maps each number $n$ to $n^2$. Then there is a function with the domain $\Delta$ and codomain $\Rho$ which takes an argument $d\in\Delta$, first applies $f$ to it, and then applies $g$ to the result. In our example, this would be the function that maps me to (my height in centimeters)$^2$. This function is called **the composition of f and g** and is written as $g\circ f$. That is:
> $(g\circ f)(d) = g(f(d))$
Some more HOMEWORK EXERCISES:
(16) If $\operatorname{wife}$ is the function that maps a married individual to his (or her) wife, and $\operatorname{father}$ is the function that maps a married woman to her father, what is another name in English for the function $\operatorname{father}\circ\operatorname{wife}$?
(17) When we're talking about the composition of more than two functions, sometimes we'll leave off the parentheses. Should $h \circ g \circ f$ be understood as $h \circ (g \circ f)$ or as $(h \circ g) \circ f$? Justify your answer.
If $f$'s codomain is the same set as its domain, then the values of $f$ for some argument will also themselves be suitable arguments for $f$. So we can talk about $f\circ f$. And we can talk about $f \circ f \circ f$ and so on. Sometimes we use this shorthand notation:
> $\dots$
> $f^3(d) = (f\circ f\circ f)(d) = f(f(f(d)))$
> $f^2(d) = (f\circ f)(d) = f(f(d))$
> $f^1(d) = f(d)$
> $f^0(d) = I_\Delta(d) = d$, where $I_\Delta$ is the identity function for $f$'s domain $\Delta$
Note that this is very different from a convention you may have learned when doing trigonometry: $\sin^2 x = (\sin x)^2$, not $\sin(\sin x)$.
Suppose a function $f\colon \Delta \to \Gamma$ is a bijection. Then because the function is one-to-one, every value in $\Gamma$ *in $f$'s range* is such that there is a unique member of $\Delta$ that $f$ maps to it. And because the function is onto $\Gamma$, every value in $\Gamma$ *is* in $f$'s range. So we can talk about the **inverse** of function $f$, written as $f^{-1}\colon \Gamma \to \Delta$, and defined such that:
> $\forall c\in \Gamma (\forall d\in\Delta (f^{-1}(c) = d\latin{ iff }f(d)=c))$
We've just said that all bijections have inverses; in fact, they have unique inverses. The converse is also true: any function with an inverse is a bijection.
HOMEWORK EXERCISES:
(18) If $f\colon \Delta \to \Gamma$ is a bijection, (a) what is $f^{-1}\circ f$? (b) What is $f\circ f^{-1}$? It should be clear what the domain and codomain of your answers are.
(19) If $f$ and $g$ are both bijective, must $g\circ f$ be bijective? Defend your answer.
(20) \(a) If $g \circ f$ is bijective, must $f$ be injective? (b) must $g$ be injective? (c) must $f$ be surjective? (d) must $g$ be surjective? Defend your answers.
If we have a function $f\colon \Z\to\N$, such that $f(z) = z^2$, some other ways to specify which particular function $f$ is are:
> $f\colon z\mapsto z^2$
> $f = \fun z (z^2)$
We'll aim to discuss this $\fun$ notation some more at the end of the term. If we have a function that instead takes two arguments, such as $g(y,z) = y + z$, then we might write:
> $g = \fun (y,z) (y+z)$
You may also encounter this kind of notation:
> $\fun y z (y+z)$
That is shorthand for:
> $\fun y(\fun z (y+z))$
and it not quite the same as $\fun (y,z) (y+z)$. It's a different style for defining an operation on multiple arguments. (It's called the "curried" style, after the logician [Haskell Curry](https://en.wikipedia.org/wiki/Haskell_Curry).) The function $\fun (y,z) (y+z)$ is defined only on pairs of numbers. It is not defined for single numbers. The function $\fun y(\fun z (y+z))$ on the other hand is defined for single numbers. The result of applying this function to the argument $2$ is a function $\fun z (2+z)$ that maps arguments $z$ to $2+z$. These are somewhat different ideas, and in some contexts that difference is very important.
For the most part, however, we will just work with functions that take multiple arguments in the style of $\fun (y,z) (y+z)$; and we will avoid the $\fun$ notation for this until we return to the topic of "$\fun$-abstraction" later in the semester (if we get that far). We'll instead describe that function in the manner I began with: $g(y,z) = y + z$.
One last bit of vocabulary about functions: when a function takes a single argument, we call it a "unary" function. When it takes two arguments, "binary." When it takes three arguments, "ternary." And so on. The general property is called the function's "arity." Sometimes I may slip and talk of "monadic" and "dyadic" functions, and the function's "adicity." But in fact the dominant usage is that we talk about functions as having "arity"s and it's instead *predicates* that are monadic and dyadic and have adicities.
HOMEWORK EXERCISE:
(21) Which of the following mathematical symbols express unary functions? Which express binary functions? Which don't express functions at all?
a. $+$
b. $\lt$
c. $\union$
d. $\se$
e. $\sin$
### Relations ###
Whereas we talk of functions' *having a value* for a given argument (or for given argument*s*, which we're thinking of as a single tuple), a relation is instead something we talk about as *holding* (or not holding) between certain arguments. The most familiar kinds of relations are binary relations, like the relation that holds between $x$ and $z$ when $x$ is a parent of $z$. But there are also ternary relations, like the relation that holds between $x$ and $y$ and $z$ when $y$ is intermediate in size between $x$ and $z$. And quaternary relations, and so on.
Notice that unlike functions, relations *are* permitted to be one-to-many. One $x$ can stand in the $\operatorname{parent}$ relation to many $z$s. But some binary relations are such that whenever they hold between an $x$ and $z$, they don't also hold between $x$ and a distinct $z'$. These relations are called "functional." This generalizes to the ternary case like this: if the relation holds between $x$ and $y$ and $z$, it doesn't also hold between $x$ and $y$ and a $z'$ distinct from $z$.
There is a close affinity between functions and functional relations. If you have a $(n+1)$-ary functional relation $r$, you can define the $n$-ary function which maps an $n$-tuple $(x_1,x_2,\dots,x_n)$ to a value $z$ iff $r$ holds between $x1,x2,\dots,x_n$ and $z$. (Though in general, you cannot rely on this being a *total* function; since $r$ may not hold between every $x$ in the domain you're considering and another object.) And vice versa: given the function, you can define the corresponding functional relation.
The notion of a relation is more general though, since we can have $(n+1)$-ary relations to which no $n$-ary function correponds, like the $\operatorname{parent}$ relation. In general, there is no function that returns, for any $x$, *the* $z$ that $x$ is a parent of, since there may be several such $z$s. (Restricted to certain domains of $x$s, there *may* be such a function; but in general there won't be.)
Another way an $(n+1)$-ary relation could be associated with a function is with the $(n+1)$-ary (rather than $n$-ary) function that maps a tuple $(x_1,x_2,\dots,x_n,z)$ to the truth-value $\True$ if $r$ holds between $x1,x2,\dots,x_n$ and $z$, and to the truth-value $\False$ otherwise.
Vocabulary like "domain", "injective", "composition", and so on is applied to relations in a way analagous to the way it's applied to functions. $x$ stands in the composition of relation $r_1$ and relation $r_2$ to $z$ iff there's some $y$ such that $x$ stands in $r_1$ to $y$ and $y$ stands in $r_2$ to $z$.
The **inverse** of a relation $r$ is defined to be the relation that holds between $z$ and $x$ iff $r$ holds between $x$ and $z$. Unlike functions, every relation has an inverse.
Sometimes this is instead called the "converse" of the relation. The "inverse" terminology better parallels the use of "inverse" when we talk about functions. The "converse" terminology better parallels our talk about conditionals: $C\horseshoe A$ is the converse, not the inverse, of $A\horseshoe C$.