[edit: reformatting for ease of reading in the hopes of getting a response on whether my latest revision is correct]
Context: I'm a first-year undergraduate working my way through How to Prove It? by Velleman
My questions:
- Is my proof correct?
- Any comments about the style? Have I provided enough scaffolding (considering the level)? Or is it too verbose?
Velleman 5.1.18. Suppose $f: A \rightarrow B$ and $R$ is an equivalence relation on $A$. We will say that $f$ is compatible with $R$ if $\forall x \in A \forall y \in A (xRy \rightarrow f(x) = f(y))$.
(a) Suppose $f$ is compatible with $R$. Prove that there is a unique function $h: A/R \rightarrow B$ such that for all $x \in A$, $h([x]_R) = f(x)$.
[Hint: Let $h = \{ (X,y) \in A/R \times B \mid \exists x \in X (f(x) = y) \} $]
Proof. Let $h = \{ (X,y) \in A/R \times B \mid \exists x \in X (f(x) = y) \} $.
First we show that $h: A/R \rightarrow B$. Let $X \in A/R$. Then there is some $x \in A$ such that $X = [x]_R$. Since $x\in A$ and $f$ is a function from $A$ to $B$, we can choose some $y \in B$ such that $y=f(x)$. Then by the definition of $h$, it follows that $(X, y) \in h$. Now suppose $(X, y_1) \in h$ and $(X, y_2) \in h$. Then we can choose some $x_1 \in X$ such that $y_1 = f(x_1)$, and we can choose some $x_2 \in X$ such that $y_2 = f(x_2)$. Since $X \in A/R$, $x_1 \in X$, and $x_2 \in X$, we have $x_1 R x_2$. And since $x_1 R x_2$ and $f$ is compatible with $R$, we have $y_1=f(x_1)=f(x_2)=y_2$.
Next we show that for all $x \in A$, $h([x]_R)= f(x)$. Let $x$ be an arbitrary element of $A$. Since $x \in A$ and $R$ is an equivalence relation, $[x]_R \in A/R$. By the definition of $h$, it follows that $([x]_R, f(x)) \in h$.
Now to show that $h$ is unique, suppose $h': A/R \rightarrow B$ such that for all $x \in A$, $h'([x]_R) = f(x)$. Let $X$ be an arbitrary element of $A/R$. Then we can choose some $x \in A$ such that $X = [x]_R$. Then clearly, $h'(X) = f(x) = h(X)$. Since $X$ was an arbitrary element of $A/R$, it follows from Theorem 5.1.4 that $h'=h$. $\square$
Theorems and (possibly) non-trivial definitions used in the proof:
Theorem 5.1.4. Suppose $f$ and $g$ are functions from $A$ to $B$. If $\forall a \in A (f(a) = g(a))$, then $f$ = $g$.
Definition (Equivalence relation). Suppose $R$ is a relation on a set $A$. Then $R$ is called an equivalence relation on A if it is reflexive, symmetric, and transitive.
Definition (Equivalence class). Suppose $R$ is an equivalence relation on a set $A$, and $x \in A$. Then the equivalence class of $x$ with respect to $R$ is the set $$[x]_R = \{ y \in A \mid yRx \} $$ The set of all equivalence classes of elements of $A$ is called $A$ module $R$ and is denoted $A/R$. Thus
$$ A/R = \{ [x]_R \mid x \in A \} = \{ X \subseteq A \mid \exists x \in A (X = [x]_R) \}$$
