# I How to prove that a function is well-defined

1. Jul 19, 2017

### Mr Davis 97

For example, it's intuitively clear that $f(\frac{a}{b}) = (\frac{a}{b})^2$ is well-defined, since for any fraction in the domain we get one and only one fraction in the image. However, what is the formal way to prove this? In other words, is there a general way to show that a function is well-defined (or not), just as there is a general way to show that a function is injective or surjective?

2. Jul 19, 2017

### Staff: Mentor

It means you can't have two images of one element. This usually refers to functions defined on equivalence classes or otherwise defined sets, where the function is given by its action on representatives. So you can have two representatives, e.g. $[2]_6$ and $[-4]_6$ as remainders of the division by six, and you need to make sure that $f(2)$ and $f(-4)$ doesn't lead to different results. So how to prove it, depends a little bit on the function considered. If it's equal in the domain, than it has to be equal in the codomain.

3. Jul 19, 2017

### Math_QED

An approach that generally works is the following:

To be a function, for any element in the domain, there must be one, and only one, element associated in the codomain (or image). The problems arise when we we can associate two values in the codomain with the domain value. An example of such a non-function would be the non-function:

$f: \mathbb{Q} \to \mathbb{Z} \times \mathbb{Z_0}: q = \frac{a}{b} \to (a,b)$

Then, for example, the relation $f$ maps $2/3$ to $(2,3)$, but $2/3 = 4/6$, so this element gets also mapped to $(4,6)$. Meaning that $f$ is not a function

(We can make this function well-defined by demanding that $(a,b)=1$, since we can prove then that the fraction $a/b$ is uniquely determined. If needed I can provide a proof, using Bezout's theorem).

In general, if you want to show that a certain relation $R \subset A \times B$ is a function, you must look at the definition of the function to see what is required:

Recall the definition of a function:

$F: A \to B$ is a function
iff

1) $F \subset A \times B$
2) $\forall a \in A, \exists ! b \in B: (a,b) \in B$

So, you must take an $a \in A$, and then determine whether there is a unique $b \in B$ that satisfies the relation $F$.

To show uniqueness, a common strategy is to assume that if there are two elements that satisfy a certain property, then they are equal. In this case. Take $a \in A$ and assume $(a,b) \in F$ and $(a,b') \in F$. Then, show that $b = b'$. From this, you can see that it suffices to show that if $a = a'$ for $a = a ' \in A$, then also $b = b'$ and this is exactly how most proofs handle well-definedness!

An example:

Suppose we want to verify that the 'function' (we cannot say function yet, in case of possible ambiguity)

$f: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}: [x]_n \mapsto [kx]_n$ is well defined (here we mean with $\mathbb{Z}/n\mathbb{Z}$ the division ring, with multiplication as we are used it)

So, assume $[x]_n = [x']_n$. Then obviously $[kx]_n = [k]_n[x]_n = [k]_n[x']_n = [kx']_n$ and $f$ is well-defined.

Assume $a/b = a'/b'$. Then it is easy to see that $(a/b)^2 = (a'/b')^2$ so your function is well defined. What you actually did, was writing the function $f: \mathbb{Q} \to \mathbb{Q}: x \mapsto x^2$ in a misleading way. It should not need a proof that this function is well defined.

Important remark: A common mistake is to think that well-definedness means that if $a = a'$, then $f(a) = f(a')$ but this is abuse of notation! We cannot write f(something) until we have proven that $f$ is a function!

4. Jul 19, 2017

### Staff: Mentor

If you can check every element in the domain: sure.
In general you cannot. A made-up example:

$f: \{0\} \to \mathbb{N}$, $f(0)$ is the largest twin prime.
This function is well-defined if there is a largest twin prime, it is not well-defined otherwise. If there would be a general algorithm to determine if this function is well-defined, you could prove the twin prime hypothesis (or disprove it).
You can construct similar functions for all other open problems in mathematics.