Below is the question from the book mentioned above:

Suppose $f : A \rightarrow B$ and $R$ is an equivalence relation on $A$. We will say that $f$ is compatible with $R$ if $∀x \in A\forall y ∈ A(xRy \rightarrow f(x) = f(y))$. Suppose $f$ is compatible with $R$. Prove that there is a unique function $h : A/R \rightarrow B$ such that for all $x ∈ A, h\left([x]_R\right)=f(x)$.

Below is my attempt in solving this problem:

Proving the existence of the function: Let $h=\{(X,y)\in A/R\times B|\exists x\in X(f(x)=y)\}$. Let $X=([x]_R)$ be an arbitrary element of $A/R$ and $x'$ some element of $X$, so $x'Rx$. Since $f$ is compatible with $R$ $(f(x)=f(y))$,so $f(x')=f(x)\in B$. Thus $([x]_R,f(x))\in h$.

Proving the uniqueness of the function: Let j be a function such that $j([x]_R)=f(x)$. That means we can find some $[x]_R \in A/R$ such that $f(x)=y$. Since $[x]_R\in A/R$ and $y\in B$, $([x]_R,f(x))\in h$, so $j\subseteq h$. By similar reasoning, $h\subseteq j$. So $h$ is unique.

I want to ask that: 1)Is my proof about the existence of the function correct? 2)is my proof about the uniqueness correct? I basically have no idea what I am proving for the uniqueness of the function...

Please explain and give some hints if there are some mistakes in the proof above. Thanks in advance.

  • 1
    $\begingroup$ Great book you're studying. $\endgroup$ – Git Gud Jul 24 '13 at 14:09
  • $\begingroup$ Can't agree more! This book is very nice! $\endgroup$ – Dave Clifford Jul 24 '13 at 14:11

There are proofs that make a more or less obvious fact less believable. Yours is of this kind.

There can be at most one function $h:\ A/R\to B$ that satisfies $$h\bigl([x]_R\bigr)=f(x)\qquad\forall x\in A\ ,\tag{1}$$ since its value on any class $[x]_R$ would be given by $(1)$.

The real problem is whether $(1)$ actually defines a function on $A/R$. From dealing with equivalence classes we know the following: Given an element $X\in A/R$ there is a representant $x\in A$ of $X$, but this $x$ is not uniquely determined. When both $x$, $x'\in A$ represent $X$ then on the one hand $X=[x]_R=[x']_R$, and on the other hand $xRx'$. In this case by assumption on $f$ we have $f(x')=f(x)$, so that $(1)$ defines the same value for $h(X)$, whether we use $x$ or $x'$ to compute it.

  • $\begingroup$ Do you also mean that whatever [x]_R we use, the output of h(X) will always be the same, which implies that every input has exactly only one image, suggesting that h(X) satisfies the prerequisite of being a function? $\endgroup$ – Dave Clifford Jul 25 '13 at 6:21
  • $\begingroup$ @Dave Clifford: I mean, whatever $x\in A$ we use to represent the given $X\in A/R$ in the form $X=[x]_R$, the value $f(x)$ will always be the same. $\endgroup$ – Christian Blatter Jul 25 '13 at 8:19
  • $\begingroup$ Oh, do you mean that there will only one image for each [x]_R right? $\endgroup$ – Dave Clifford Jul 25 '13 at 9:14

In your definition of $h, X$ is a subset of $A/R$, so putting it as the first element of an ordered pair is strange. Then in the second sentence $X$ is an element of $A/R$. You have the right thought-that you need to prove that if you apply the function to two elements of an equivalence class you get the same result.

For the uniqueness proof, you could argue that since there weren't any choices made in the construction the function must be unique. Otherwise, suppose there is a $j([x]_R)$ that disagrees with $h$. There must be at least one $[x']_R$ where $h([x']_R) \neq j([x']_R)$. But that would mean $j([x']_R) \neq f(x')$ which contradicts the definition of $j$.

  • $\begingroup$ Did i mention that X is a subset of A/R? in the set h defined I already stated that X is an element of A/R, not a subset of A/R. The uniqueness proof is very clear and easy to understand, thanks. $\endgroup$ – Dave Clifford Jul 25 '13 at 6:23
  • $\begingroup$ When you define $h$ you say $(X,y) \in A/R \times B$, which implies $X \in A/R$ and $y \in B$ $\endgroup$ – Ross Millikan Jul 25 '13 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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