Question from 'How to Prove It'

Question

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.

Answer 1

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.

Answer 2

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