Showing that $(a,a')\in R\implies f(a)=f(a')$

95 Views Asked by At

From https://arxiv.org/pdf/1612.09375.pdf (p.130): enter image description here enter image description here

I'm confused by the proof given at the end. Namely, I don't understand why the statement "so these statements are equivalent" follows. And also I don't understand what for the author defines the third relation (I don't know how to type that symbol here).

Can one prove the original claim as follows?

Let $\sim$ be the equivalence relation generated by $R$. We need to show that $(a,a')\in R\implies f(a)=f(a')$, knowing that $(a,a')\in \sim \implies f(a)=f(a')$ [which is (5.19)]. So assume $(a,a')\in R$. Since $\sim$ is the equivalence relation generated by $R$, the relation $\sim$ contains $R$. Thus $(a,a')\in \sim$. Now by (5.19), $f(a)=f(a')$.

I don't see what's wrong with my proof, but it doesn't use that $\sim$ is the smallest equivalence relation generated by $R$.

1

There are 1 best solutions below

2
On BEST ANSWER

For the original proof you need to show that $R ⊆ \approx$ implies $\sim ⊆\approx$ (the other direction is obvious since $R ⊆ \sim$). Well, since $\sim$ is the smallest equivalence containing $R$, and $\approx$ contains $R$ by assumption, we must have that $\sim$ is smaller than $\approx$, ie. that $\sim ⊆ \approx$. (This is completely analogous (and formally the same) to how you'd argue that eg. the statements $A ⊆ F$ and $\operatorname{Cl} A ⊆ F$ are equivalent for a closed set $F$.)

In your proof you only show that 5.19 implies 5.20, and not the converse, which is the more important part.

Finally, for LaTeX, you can usually google the symbols you need (in this case "latex relation symbols" would suffice), and there are also tools like detexify that can help.