What is the actual definition of a function?

287 Views Asked by At

I am learning precalculus and my book defines the following:

A function $f$ from a set $A$ to a set $B$ is a rule that assigns to every element $a$ in $A$ one and only one value in $B$.

Well, I am thinking, a rule isn't something that I've seen defined mathematically. So what is a function, really? Is it a subset of $A\times B$ or something?

3

There are 3 best solutions below

2
On

Indeed, a function is a subset of $A \times B$ with the following very important property: for every $x \in A$, there exist a unique $y \in B$ such that $(x,y) \in A \times B$. Intuitively, this tells you that a function cannot take an element $x$ into several distinct values $y$ - that wouldn't be a function anymore, but somehing called "binary relation" (that you need not worry about).

Nevertheless, for many practical purposes, thinking of a function as a rule, or a correspondence between $x$ values and $y$ values, will suffice. Still, keep the correct definition somewhere in the back of your mind, readily available if necessary.

8
On

Alex M. has given the standard definition of a function in "material set theory". In material set theory, everything is a set, and there is a single global relation $\in$. If you're working in material set theory, you must be able to boil down every possible statement into a statement involving $\in$ (and $=$, though it's even possible to get rid of $=$ if you try hard enough).

First, we prove that for all $a, b$, there is a unique $c$ such that for all $x$, $x \in c$ if and only if $x = a$ or $x = b$.

We then introduce the notation $\{a, b\}$ to represent this $c$. Note that if we have any statement involving the set $\{a, b\}$ (a statement $\phi(\{a, b\})$), we can always rewrite the statement to not use the notation $\{a, b\}$ by rewriting as "There is some $c$ such that for all $x$, $x \in c$ if and only if either $x = a$ or $x = b$, and furthermore $\phi(c)$".

Then, we introduce the notation $(a, b) = \{\{a\}, \{a, b\}\}$ (here, by $\{a\}$, we technically mean $\{a, a\}$). Note that $(a, b) = (c, d)$ if and only if $a = c$ and $b = d$. Once again, we can rewrite any statement involving the ordered pair $(a, b)$ to not involve this ordered pair - just substituting $\{\{a\}, \{a, b\}\}$. We can then take this statement and, using the above translation scheme, rewrite it to use only $\in$.

The statement "$f$ is a function from $A$ to $B$" can thus be written as

$$[\forall x . (x \in f \to \exists a . a \in A \land \exists b . b \in B \land (a, b) = x)] \land \forall x . x \in A \to \exists y . y \in B \land (x, y) \in f \land \forall y' . (x, y') \in f \to y = y'$$

though of course, this is only shorthand for a much longer and more complicated statement which doesn't use ordered pair notation.

In more convenient notation (involving more definitional extensions), we can write the definition of "$f$ is a function from $A$ to $B$" as

$$f \subseteq A \times B \land \forall x \in A . \exists! y \in B . (x, y) \in f$$

This requires extending the language to include the Cartesian product $\times$ and also the subset symbol $\subseteq$.

Note that when we make some statement about $f(x)$ in material set theory, we must be able to rewrite this statement to avoid using this notation. So $\phi(f(x))$ becomes the statement $\exists y . (x, y) \in f \land \phi(y)$.

However, in structural versions of set theory (such as ETCS), functions are actually primitive entities. Note I'm not considering SEAR here, only category-theoretic notions of set theory.

In structural set theory, there are two kinds of things. First, there are sets. Second, for any sets $A, B$, there are functions $f : A \to B$.

Instead of $\in$ being the primitive notion, the basic notion in structural is the notion of function composition. One starts with the notion of functions and function composition and then supposes the existence of a "one-element set" $1$ (where "one-element set" is defined purely in terms of functions, not elements). An element of a set $A$ is defined to be a function $a : 1 \to A$. If we have an element $a : 1 \to A$ and a function $f : A \to B$, then we see that $f \circ a : 1 \to B$. We define $f(a)$ to be $f \circ a$. This means that every function $f$ gives rise to a "rule" which takes an element of $A$ and outputs an element of $B$.

Note that function composition is, in practice, how almost all functions are defined. For example, consider the function $f(x, y) = \cos{\sin(x + y)}$. This is just $f = \cos \circ \sin \circ +$ - the definition is purely in terms of function compositions. Whenever we define functions using an explicit equation and other functions, we are using composition. So it makes sense to take function composition as the basic notion.

Conversely, we can specify $A \times B$ purely in terms of functions, and we can also define a notion of $\subseteq$ purely in terms of functions. We can then prove that for every $G \subseteq A \times B$, if for all $a \in A$, there is a unique $b \in B$ such that $(a, b) \in G$, then there is a unique function $f : A \to B$ such that for all $a \in A$, $(a, f(a)) \in G$. This means that every definable "rule" that, given an $a \in A$, specifies a unique $b \in B$ gives rise to a function which takes as an input the $a \in A$ and outputs the specified $b$.

So functions $A \to B$ are in bijective correspondence with their graphs $G \subseteq A \times B$, but the two are not definitionally the same thing. The notion of the graph of a function $f : A \to B$ - that is, $\{(a, f(a)) \mid a \in A\} \subseteq A \times B$ - is subsidiary to the notion of a function itself, which is the primitive and basic notion.

Let's return to the question of "what is a function?" In material set theory, because the defining notion is that of elementhood, we have to come up with an encoding for the intuitive idea that a function is a rule associating every possible input with exactly 1 output. We do this by defining a notion of "ordered pair" and then identifying a function $f : A \to B$ with its graph $\{(x, f(x)) \mid x \in A\}$.

By contrast, in structural set theory, we take functions themselves as a primitive notion. The only answer to the question "what is a function?" is an intuitive, informal answer. This is perfectly analogous to asking the question "what is a set?" in material set theory. We can't define a set in terms of the things which exist in material set theory, since the only things that exist in material set theory are sets.

0
On

Yes, it's a subset R of $A \times B$ such that for every $a \in A$ there is exactly one $b \in B$ such that $(a,b) \in R$. So, it's a special kind of binary relation, and since for every $a \in A$ there is one and only $b \in B$ that gets 'associated'/'paired' with this $a$, we can call that the 'function value' of $a$. This is what your textbook means by a function being a kind of a rule that 'assigns' a specific $b$ to any $a$ ... and as such we can say that $f(a) = b$

Interestingly, there are also things called 'partial functions', that assign at most one $b \in B$ to every $a \in A$ .. if there is no $b \in B$ that gets paired with some a in A, then we say that the function value $f(a)$ is undefined. So, strictly speaking, a partial function is not a function .. though it shares the important idea with a function that there cannot be more than two different elements $b_1 \in B$ and $b_2 \in B$ associated or assigned to any $a \in A$.