16
$\begingroup$

While it is easy to understand what a function is intuitively, I've been trying to wrap my head around how to precisely define what a function is using only mathematical notation. My attempt at this is below, but here is my preliminary understanding:

  1. A function can have multiple inputs or parameters, but it generates a single output
  2. Each output is unique for the input values provided.

Here is my attempt at a definition:

A relation $R \subset (D \times C)$ is a function if: $$ (\forall (d_1, c_1) \in R)(\forall (d_2, c_2) \in R)(d_1 = d_2 \rightarrow c_1 = c_2)$$

This definition should cover all functions, not just functions with one input, as $d_1$ and $d_2$ could be n-tuples that define the n inputs of a function, as every element of $R$ is actually an ordered pair $((x_1, x_2, ..., x_n),c)$

Does this look like a correct and precise definition? Or could it be written better? I couldn't find any formal definition of a function on the web, even on Wikipedia.

Finally, is it correct to say that all functions with n inputs are (n+1)-ary relations? Since $((x_1, x_2, ..., x_n),c)$ is the same as $(x_1, x_2, ..., x_n,c)$.

Thanks.

$\endgroup$
3
  • $\begingroup$ Try to Google what it Means for a map to be "well defined". I think this will be something along the line you are looking for. $\endgroup$
    – An.Ditlev
    Sep 7, 2016 at 7:08
  • 1
    $\begingroup$ Wikipedia does give a definition that should be sufficient. en.wikipedia.org/wiki/Function_(mathematics)#Definition $\endgroup$
    – Thanassis
    Sep 7, 2016 at 7:10
  • $\begingroup$ @Thanassis while it may be descriptively sufficient, I'm only interested in a symbolic definition using set theory and logic $\endgroup$ Sep 7, 2016 at 10:22

2 Answers 2

14
$\begingroup$

The usual way to define a function, you are correct, is by relations. However, your definition is not ok, because for example, an empty relation fits your definition.

The correct definition must say something like:

A relation $R\subset A\times B$ is a function if each element $a$ of $A$ is contained in exactly one relation $(a,b)\in R$

In pure terms, you can write this as

$$\forall a\in A\exists! b\in B: (a,b)\in R$$

Where the $\exists!$ quantifier means "exists precisely one". A longer version (with only $\exists$ and $\forall$) would be

$$\forall a\in A \exists b\in B:((a,b)\in R\land \forall b'\in B:(a,b')\in R\implies b=b').$$


Answer to your other question about functions on multiple inputs:

No, functions are always binary relations. A function of "multiple (say, $n$ inputs)" is actuall a function whose domain is a cartesian product. So, for example, a function of $n$ real numbers is in fact a function whose domain is equal to $\mathbb R^3$.

This means that technically, we shouldn't write $f(x,y)=xy$, for example. We should write $f((x,y))=xy$, because $f$ takes only one input, and that input is a tuple of two numbers.

$\endgroup$
8
  • 4
    $\begingroup$ Now that you mention it, is there any reason why you cant have a function $f:\emptyset \to A$? Other than that it would be useless? $\endgroup$
    – pancini
    Sep 7, 2016 at 7:12
  • 2
    $\begingroup$ @ElliotG No, there is no reason. In fact, $\emptyset$ is a function between $\emptyset$ and $A$ (since $\emptyset\subseteq \emptyset\times A$ is clearly true, and $\forall a\in \emptyset:(...)$ is also true no matter what the brackets hold. But if $X$ is non-empty, then $\emptyset$ cannot be a function between $X$ and any other set. $\endgroup$
    – 5xum
    Sep 7, 2016 at 7:16
  • 1
    $\begingroup$ Actually, to define a function you need at least the pair $(B,R)$ (and usually, it's defined using the tuple $(A,B,R)$, for simplicity I guess), so that the definition of a surjective function can make sense. Otherwise, you always let $B=Im(f)$ and all functions are surjective. $\endgroup$ Sep 7, 2016 at 7:44
  • $\begingroup$ @Jean-ClaudeArbaut Well, $R$ is a subset of $A\times B$, so you don't need to then once more define what $B$ is. Using the definition I described above, a surjective function can be simply defined. $\endgroup$
    – 5xum
    Sep 7, 2016 at 7:45
  • $\begingroup$ @5xum Given a subset of $A\times B$, you don't know for sure what $B$ is. For instance, $\Bbb N\times \Bbb N$ is a subset of $\Bbb N\times \Bbb Z$, but also of $\Bbb N\times \Bbb Q$, $\Bbb N\times \Bbb R$, and of course of itself, and many, many other sets. However, given the condition to be a function, you know what $A$ is. $\endgroup$ Sep 7, 2016 at 7:47
14
$\begingroup$

5xum is right -- your definition is not sufficient. However, you may be interested to know that your definition,

A relation $R \subset (D \times C)$ is a function if: $$ (\forall (d_1, c_1) \in R)(\forall (d_2, c_2) \in R)(d_1 = d_2 \rightarrow c_1 = c_2)$$

is something we care about in some branches of math! This is called a partial function from $D$ to $C$ (sometimes denoted $f: D \rightharpoonup C$).

Partial functions are especially used in the theory of recursive functions (or computable functions from $\mathbb{N}$ to $\mathbb{N}$).

$\endgroup$
1
  • $\begingroup$ @esotechnica You're welcome :) $\endgroup$ Sep 7, 2016 at 10:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .