Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:(\Bbb Z/12\mathbb Z)^∗→(\Bbb Z/4\Bbb Z)^∗:[x]_{12}↦[x]_4 ,$$ but I'm more intrested in the general procedure.

share|improve this question
    
Mostly, the second part is preferable. –  Babak S. Feb 24 '13 at 18:28
2  
@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 '13 at 18:29
1  
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 '13 at 18:30
3  
@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 '13 at 18:33
1  
@BabakS. What do you mean with map? I make no distinction between map and function. –  Git Gud Feb 24 '13 at 18:34

8 Answers 8

up vote 16 down vote accepted

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$.

share|improve this answer
2  
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 '13 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 '13 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 '13 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 '13 at 20:15
1  
@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 '13 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$.

share|improve this answer
1  
Thanks, your counterexample really helps me understanding this. –  Kasper Feb 24 '13 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})^* $$

share|improve this answer
    
Thanks. Edited. –  Mohan Feb 24 '13 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)^*$.

share|improve this answer
1  
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 '13 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.

So, what is it that really defines when a given relation is a function?$\vphantom{Some commands added; A.K.}\newcommand{\img}{\operatorname{img}}\newcommand{\id}{\mathrm{id}}$

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$
share|improve this answer

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/

share|improve this answer

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$

share|improve this answer
    
^ ^. Nice job. ${}$ –  Git Gud Feb 24 '13 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} $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.