How is the notion of a function defined precicely?

Question

Often, when functions are defined, the description is something like "a 'rule' which assigns every element in one set to exactly one element of another set." Is there a precise definition of what a function is?

Answer 1

You can think first about a relation, for example, a relation from a set A to another set B, which are not empty. We also know that every relation between 2 sets, is a subset of the Cartesian product of the two sets: R $\subset$ A x B. Now you can notice this relation mathematically by (a, b) $\in$ R or just aRb. After that we can define the terms domain and image: the domain of the relation R, dom(R), is a set that is given as follows: dom(R) = { a $\in$ A | $\exists$ b $\in$ B : aRb) and the image of the relation R is given as Im(R) = { b $\in$ B | $\exists$ a $\in$ A : aRb}.

After this, we can specify "a function" as a special case of a relation. But now, besides domain and image, we also have to define a new term, namely codomain, because, as I said, a function is a special case of a relation. We use even other notation when we talk about function. Now consider again two sets, this time X and Y (not empty). We note the function from X to Y as f : X $\to$ Y. X is set (domain) whose elements are "projected" to others elements, namely to the elements of set Y (codomain). This doesn't mean that every element of Y belongs to this special case a relation (function). Now, the elements of Y that belongs effectivelly to the function are said to be in the image of the function. So we adjust our notations a little bit as follows:

Dom(f) = X = { x $\in$ X | $\exists$! y $\in$ Y: (x, y) $\in$ f} ; Codomain = Y ; Im(f) = { y $\in$ Y | $\exists$ x $\in$ X : y = f(x)}. As you can see, "R" became "f" and every x in X is in relation with at most ONE element y in Y. To be specific, we also notice f : X $\to$ Y : x $\mapsto$ y = f(x). Keep in mind that we notice y = f(x) because y is a function of x. To get a more intuitive feeling about functions, you can think about a set of people (X) and another set of positive integers (Y) to be the age of every person in X. Every person can have one age and that's why we call this relation from X to Y (the age of x is y) a function.

Answer 2

Yes. Suppose that $A$ and $B$ are sets, then we can define a function from $A$ to $B$ to be a subset $F \subseteq A \times B$ such that $(\forall a \in A)(\exists! b \in B)((a,b) \in F)$. This gives a notion of how to assign elements of $B$ to elements of $A$.

In proofs where you construct functions, this is helpful for thinking about the part of a proof where you show that a function is "well-defined." Take the proof of the first isomorphism theorem in group theory. If $\phi:G \to H$ is a group homomorphism, then to show that $G/\ker(\phi) \cong \phi(G)$, you construct a map $\bar \phi:\bar g \mapsto \phi(g)$ and attempt to show that this is an isomorphism by first showing that it is well defined. What you really did was construct a subset $\{(\bar g, \phi(g)): g \in G\} \subseteq G/\ker(\phi) \times \phi(G)$ and are then attempting to show that this subset defines a function.

Answer 3

There doesn't have to be a rule but there has to be a consistency.

Simple but incomplete and handwaving and with one essential undefined concept:

If $A$ is a set of elements (can be anything; could be $\mathbb R$; it could be a set of elephants; it could even be a set of functions) and $B$ is a set of elements (could be anything; could be the same thing as $A$ or something entirely different).

Then $f: A \to B$ is an assignment of the elements of $A$ to the elements of $B$ so that:

For each and every element $x \in A$ then $x$ consistently and unambiguous assigned to a specific value of $y\in B$. We write this as $f(x) = y$.

This means that for every $x \in A$ then $f(x)$ must mean something in $B$ and if $f(x)$ can't mean two different things or have different meaning under different circumstances.

However this doesn't mean that each different $x\in A$ get assigned to a different $y \in Y$. It's perfectly possible for two different $x$ and $z$ in $ A$ to both be assigned to the same value $y \in B$. i.e. $f(x)=f(z) = y \in B$. (Example: if $f:\mathbb R \to \mathbb R$ with $f(x) = (x-3)^2$ then $f(1) = f(4)=4$.)

This also doesn't mean that every value $y\in B$ has a value of $A$ assigned to it. It's quite possible for there to be be a $y\in B$ so that no $x \in A$ exist so that $f(x) = y$. (Example: if $f:\mathbb R \to \mathbb R$ with $f(x) = (x-3)^2$ then there is no $x \in \mathbb R$ so that $f(x) = -3$.)

But every $x \in A$ must be assign to specifically one $y \in B$.

And that's it.

....

except.... what is the definition of "assignment"?

So Hard and Abstract but worth understanding:

A set $A$ and a set $B$ are sets of elements. And an "ordered pair" is a pair of elements listed as "$(a,b)$" where $a \in A$ and $b \in B$.

And we say that $A \times B$ is the Cartesian Product of the two sets $A$ and $B$ and $A\times B$ is the set of all such ordered pairs. i.e. $A \times B = \{(a,b)|a \in A, b\in B\}$.

We refer to a subset $R \subset A\times B$ as a relation between $A$ and $B$. And we think of it (but don't define it) as a relationship between possible candidates for the first term of a pair and the second term of a pair.

So, for example, if we wanted to describe the "relationship" of two positive integers have factors in common, i.e. the relationship between $n$ and $m$ when $\gcd(n,m) \ne 1$, then the relationship is really the set $R = \{(n,m)|\gcd(n,m) \ne 1\} \subset \mathbb N \times \mathbb N = \{(a,b)|a\in \mathbb N; b\in \mathbb N\}$. So for example $(6,15) \in R$ and $(15, 45)\in R$ but $(3, 7) \not \in R$.

So a function is a relation $F \subset A \times B$ so that the following condition must occur:

For every $a \in A$ there is exactly one ordered pair in $F$ where the first term is $a$. i.e. for every $x \in A$ there is an $(a,y) \in F$. But $(a,y)$ is the only such pair in $F$. If $a \in A$ and $b \in B$ and $(a,b)\in F$. Then for any $c \in B$ where $c \ne b$ then $(a,c) \not \in F$.

And that is what a function is.

One subtle thing to notice. This idea of assignment is very subtle and wide spread. Consider the concept of a finite sequence $\{a_1, a_2, a_3, a_4...a_{27}\}$ where $a_i$ are terms in some set, say... $a_i \n \mathbb Q$. Notice that this is actually a function $f:\mathbb N_{27} \to \mathbb Q \subset \mathbb N_{27}\times \mathbb Q$ which is $\{(1,a_1), (2,a_2), .... ,(27, a_{27})\}$, or in terms of "rules" so that $f(n) = a_n$, which is nothing more or less than an "assignment" of indexes to corresponding values.