# How do I prove that a function is well defined?

How do you in general prove that a function is well-defined?

$$f:X\to Y:x\mapsto f(x)$$

I learned that I need to prove that every point has exactly one image. Does that mean that I need to prove the following two things:

1. Every element in the domain maps to an element in the codomain:
$$x\in X \implies f(x)\in Y$$
2. The same element in the domain maps to the same element in the codomain: $$x=y\implies f(x)=f(y)$$

At the moment I try to prove this function is well-defined: $$f:(Z/12\mathbb Z)^∗→(Z/4\Bbb Z)^∗:[x]_{12}↦[x]_4 ,$$ but I'm more intrested in the general procedure.

-
Mostly, the second part is preferable. –  B.S. Feb 24 at 18:28
@BabakS. The second part is senseless if $f$ isn't a function and trivial if $f$ is alrady known to be a function. –  Git Gud Feb 24 at 18:29
At the moment I try to prove this function is well-defined: $f:(\Bbb{Z}/12\Bbb{Z})^*\to(\Bbb{Z}/4\Bbb{Z})^*:[x]_{12}\mapsto[x]_4$ , but I'm more intrested in the general procedure. –  Kasper Feb 24 at 18:30
@Kasper: your original question does not make sense. A function is always defined otherwise it is not a function. What you need in the example, is to prove that there exists a function $f$ satisfying some given property, and that such a function is uniquely determined. –  Emanuele Paolini Feb 24 at 18:33
@BabakS. What do you mean with map? I make no distinction between map and function. –  Git Gud Feb 24 at 18:34

When we write $f\colon X\to Y$ we say three things:

1. $f\subseteq X\times Y$.
2. The domain of $f$ is $X$.
3. Whenever $\langle x,y_1\rangle,\langle x,y_2\rangle\in f$ then $y_1=y_2$. In this case whenever $\langle x,y\rangle\in f$ we denote $y$ by $f(x)$.

So to say that something is well-defined is to say that all three things are true. If we know some of these we only need to verify the rest, for example if we know that $f$ has the third property (so it is a function) we need to verify its domain is $X$ and the range is a subset of $Y$. If we know those things we need to verify the third condition.

But, and that's important, if we do not know that $f$ satisfies the third condition we cannot write $f(x)$ because that term assumes that there is a unique definition for that element of $Y$.

-
It might be good to mention that the domain of a relation $f$ is the set $\{x : \exists y\,(x,y) \in f\}$, because many people are only familiar with the notion of domain of a function. –  Trevor Wilson Feb 24 at 18:40
Also technically "the codomain of $f$ is $Y$" does not make sense (not in set theory anyway, maybe in category theory...) –  Trevor Wilson Feb 24 at 18:41
I don't understand #2: if $f\subseteq X\times Y$ and every $x\in X$ has a $y$ such that $\langle x,y\rangle\in f$, doesn't that automatically mean that the domain of $f$ is $X$? (Could you give an example where properties #1 and #3 are met, but property #2 is not?) –  ruakh Feb 24 at 20:11
@ruakh: Yes. But $\varnothing\subseteq X\times Y$ and the domain of $\varnothing$ is $\varnothing$. Also $X\times Y$ has domain of all $X$, but it does not obey the third rule. I do agree that the second property is redundant, but note that from the third property the first one follows as well. However often we are presented with a case where two of these properties are obvious, or almost obvious, and we need to conclude the third one. I do agree that some fix up might be in order here. I'll put some changes in. –  Asaf Karagila Feb 24 at 20:15
@Kasper: But we cannot use $f(x)$ as a term before we know that it is uniquely defined. Think of the following property "$f(x)$ is the son of $x$". I have a brother, so my dad have two sons. Which one is $f(\text{Asaf Karagila's dad})$? This is not well-defined, and we cannot use $f(x)$ in that context. –  Asaf Karagila Feb 24 at 20:57

The issue here is that $[x]_{12}$ means an equivalence class of elements of $\def\Z{\mathbb Z}\Z$, specifically the class of all $y$ such that $x-y$ is a multiple of 12. You have some procedure that says you are given one of these equivalence classes, $[x]_{12}$, and you are calculating a value by selecting a representative element, say $y$, from $[x]_{12}$, and then doing something to that representative to get the answer, in this case the object $[y]_4$. But this does not make sense—it is not "well defined"—if the value you get for the given class $[x]_{12}$ depends on which representative $y$ you selected from $[x]_{12}$.

So your job here is to show that the result you get does not depend on which $y$ you pick as a representative of $[x]_{12}$.

As a counterexample, let's consider the "function" that says that $f\left(\frac ab\right) = a+ b$. So for example $f\left(\frac 12\right) = 3$, simple. But no, wait. $\frac12$ is actually an equivalence class; it is the class $\left[\frac12\right]_\mathbb Q$, which contains not only $\frac12$ but also $\frac24$, $\frac36$, and $\frac{576}{288}$. And with the definition given, the value of $f$ does depend on which representative of $\left[\frac12\right]_\mathbb Q$ you chose. $\frac12 = \frac 24$, but if you use $\frac24$ to calculate $f\left(\frac 12\right)$ you get 6 instead of 3. So this is not a well-defined function; it's not a function at all.

In your example you need to show that if you are given a class, say $[x]_{12}$, and you select an element $y$ from it (which could be any integer at all, as long as $y-x\equiv 0\pmod{12}$), and then you consider the equivalence class $[y]_4$, the class you get does not depend on which $y$ you chose from $[x]_{12}$. If it does, then this $f$ operation is an meaningless as the one in the previous paragraph that claimed to have $f\left(\frac ab\right) = a+b$.

-
Thanks, your counterexample really helps me understanding this. –  Kasper Feb 24 at 20:50

You're trying to prove $$f:(\Bbb{Z}/12\Bbb{Z})^*\to(\Bbb{Z}/4\Bbb{Z})^*:[x]_{12}\mapsto[x]_4$$

So, you have to prove that this rule of assignment doesn't depend on the representative of the equivalence class. That is $$[x]_{12}=[y]_{12} \implies [x]_{4}=[y]_{4}$$

For example $[16]_{12}=[4]_{12}$ then $[16]_{4}=[4]_{4}$.

You also need to prove that $$[x]_{12} \in (\Bbb{Z}/12\Bbb{Z})^* \implies [x]_{4} \in (\Bbb{Z}/4\Bbb{Z})^*$$

-
Thanks. Edited. –  Mohan Feb 24 at 18:46

That's exactly what you need to do. Step (1) is showing that each element in the domain is assigned at least one element in the codomain. Step (2) is showing that each element in the domain is assigned at most one element in the codomain.

The actual methods used in doing these things may vary, depending on $X,Y,$ and how the would-be function $f$ is described. I'm afraid that we can't really get more specific than that.

Edit: In your specific example, your would be function goes from $(\Bbb Z/12\Bbb Z)^*\to(\Bbb Z/4\Bbb Z)^*$ given by $[x]_{12}\mapsto[x]_4$. Recall that for $x,y\in Z$ and $n\geq 1$, we say that $[x]_n=[y]_n$ if and only if $n\mid(x-y)$. This fact will be very useful for Step (2). As for Step (1), we need only show that an integer $x$ that is coprime to $12$--meaning $[x]_{12}\in(\Bbb Z/12\Bbb Z)^*$--is also coprime to $4$--meaning $[x]_4\in(\Bbb Z/4\Bbb Z)^*$.

-
Your explanation and what the OP did do not say the same thing, as I said in a comment: the second part is senseless if $f$ isn't a function and trivial if $f$ is already known to be a function. –  Git Gud Feb 24 at 18:31

An option would be to resort to Relational Algebra, in a pointfree style.
A logic of relations was first proposed by Augustus de Morgan, in 1867.

Functions are just special cases of Relations (binary relations, for that matter).

Given types $A$ and $B$, we denote a relation $R$, from $A$ to $B$, as $B \xleftarrow{R} A$.
We write $b \, R \, a$, to denote $(b,a) \in R$.
In the particular case of functions, for a function $f$, writing $b \, f \, a$ simply means $b = f \, a$, since we expect $b$ to be unique.

Therefore, $b \, R \, a$ is a generalization of $b \, f \, a$.
This generalization applies in many ways. For instance, equality on functions, $f=g$, generalizes to inclusion on relations, $R \subseteq S$, meaning $R$ is (at most) $S$.

Besides inclusion, an important concept to have in mind is the converse of a relation.
The converse of $R$, $B \xleftarrow{R} A$, is $R^\circ$, $A \xleftarrow{R^\circ} B$ (just turn the arrows the other way around).

The converse of a function always exists, as a relation (sometimes, in special cases, as a function too).

Function composition, $f \cdot g$, also generalizes to relations, $R \cdot S$, in the same way.


Let's look at a special function, $\id$.
We have $b \, \id \, a \equiv b = a$. Not too hard.

Why does $id$ matter?

• $R$ is reflexive iff $\id \subseteq R$.
• $R$ is coreflexive iff $R \subseteq \id$.

We then define:

• Kernel of $R$ as $\ker R \doteq R^\circ \cdot R$.
• Image of $R$ as $\img R \doteq R \cdot R^\circ$.

Finally, we have the following facts:

• $\ker R$ is reflexive $\equiv$ $R$ is entire.
• $\ker R$ is coreflexive $\equiv$ $R$ is injective.
• $\img R$ is reflexive $\equiv$ $R$ is surjective.
• $\img R$ is coreflexive $\equiv$ $R$ is simple.

We say relation $f$ is a function iff $f$ is entire and $f$ is simple.
Put in another way, what you want to prove is:

• $\id \subseteq ker f$ (simplifies to $\id \subseteq f^\circ \cdot f$)
• $\img f \subseteq \id$ (simplifies to $f \cdot f^\circ \subseteq \id$)

Bonus facts:

• $\ker (R^\circ) = \img R$
• $\img (R^\circ) = \ker R$
-

For predictably wise words about this from Tim Gowers (that's Professor Sir Timothy Gowers to you ...), see http://gowers.wordpress.com/2009/06/08/why-arent-all-functions-well-defined/

-

Okay, I'm trying to answer my own question here. This is how a function is defined in "Reading, Writing, and Proving: A Closer Look at Mathematics".

Recall that a relation $f$ from $X$ to $Y$ is a subset of $X\times Y$, and therefore the elements of $f$ are ordered pairs $(x,y)$.

A function $f:X\to Y$ is a relation $f$ from $X$ to $Y$ satisfying:
i). $\forall x\in X ,\exists y\in Y :(x,y)\in f$
ii). $\forall x\in X,\forall y_1,y_2 \in Y : (x,y_1),(x,y_2)\in f\implies y_1=y_2$

An function is often called an map or a mapping. The set is $X$ is called the domain and denoted by $\text{dom}(f)$, and the set $Y$ is called the codomain and denoted by $\text{cod}(f)$. When we know what these two sets are and the two conditions are satisfied, we say that $f$ is a well defined function.

Condition i) makes sure that each element in $X$ is related to some element of $Y$, while condition ii) makes sure that no element in $X$ is related to more than one element of $Y$. Note that it may be the case that an element of $Y$ has no element in $X$ to which it is related; or an element of $Y$ could be related to more than one element of $X$.

Therefore, like Asaf Karagila mentioned, if you want to prove that $f$ is a well defined funciton, and the domain $X$ and codomain $Y$ are given, then you need to show that:

1. $f$ is an relation from $X$ to $Y$
$f\subseteq X\times Y$

2. The domain of $f$ is $X$, every element in $X$ is related to some element of $Y$ $\forall x\in X ,\exists y\in Y :(x,y)\in f$

3. No element of $X$ is related to more than one element of $Y$ $\forall x\in X,\forall y_1,y_2 \in Y : (x,y_1),(x,y_2)\in f\implies y_1=y_2$

-
^ ^. Nice job. ${}$ –  Git Gud Feb 24 at 20:56

First, note that any function from $X$ to $Y$ defined by

$$x \mapsto E$$

or by

$$f(x) = E$$

is well-defined, where $x$ is an indeterminate variable that ranges over $X$ and $E$ is a (well-formed) Y-valued expression depending (only) on $x$. (to fix the edge cases, $1$ depends on $x$, albeit in a degenerate fashion)

However, this is not the only way we define functions. There are two ways of thinking about the common alternative:

The more set-theoretic viewpoint is that we can define $f$ by a relation. We might define a function on the rational numbers by thinking

$f$ relates $x/y$ with $(x+y)/y$

Of course, we would normally write it as $x/y \mapsto (x+y)/y$ or as $f(x/y) = (x+y)/y$. But we are thinking in terms of a relation.

To check that such a mapping is well-defined, we need to check that the relation passes the 'vertical line test': specifically, that set of values

$$\left\{ \left(\frac{x}{y}, \frac{x+y}{y} \right) \mid x,y \in \mathbb{Q}, y \neq 0 \right\}$$

contains exactly one pair $(q, \square)$ for each $q \in \mathbb{Q}$.

A more algebraic viewpoint is that we define our mapping in terms of preimages. If we define functions $g : Z \to Y$ and $p : Z \to X$, then we think of defining $f$ as a mapping

$$g(z) \mapsto p(z)$$

or by

$$f(g(z)) = p(z)$$

This is well-defined when we can prove

$$g(z) = g(z') \implies p(z) = p(z')$$

This can be thought of as the third isomorphism theorem as applied to sets. An extremely natural example in this viewpoint is anything to do modular arithmetic. e.g. we can define "multiplication by 5" on $\mathbb{Z} / 2 \mathbb{Z} \to \mathbb{Z} / 10 \mathbb{Z}$ by

$$[x]_2 \mapsto [5x]_{10}$$

In this case, the maps are

$$p(z) : \mathbb{Z} \to \mathbb{Z} / 2 \mathbb{Z} : x \mapsto [x]_2$$ $$g(z) : \mathbb{Z} \to \mathbb{Z} / 10 \mathbb{Z} : x \mapsto [5x]_{10}$$

-