How to prove substitution from properties of equivalence relations?

Question

I keep reading that the property of substitution is equivalent to assuming the axiomatic properties of an equivalence relation (reflexivity, symmetry, and transitivity). E.g., Wikipedia: "Although the symmetric and transitive properties are often seen as fundamental, they can be proved if the substitution and reflexive properties are assumed instead."

However, it is opaque to me how to take the equivalence properties and prove the property of substitution, and I haven't succeeded in searching for it. How is that demonstrated?

Answer 1

As noted in the comments, though it may be possible to prove transitivity and symmetry, given reflexiveness and substitution, it is not possible to prove substitution, given the other three.

Indeed, there are many equivalence relations where the substitution property does not hold for arbitrary formulas $F$. For example, let $F(x)=x^2$.

If we let $\sim$ be the equivalence relation defined on $\mathbb{C}$ where $z\sim w$ precisely when $\mathfrak{Re}(z)=\mathfrak{Re}(w)$. This is certainly an equivalence relation, corresponding to a partition of the complex plane into vertical lines. However, we have $1\sim 1+i$ and $F(1)=1\not\sim 2i=F(1+i)$.

For another example using the same $F$, define $\approx$ on $\mathbb{R}$ by setting $x\approx y$ precisely when $x-y\in\mathbb{Z}$. This relation partitions $\mathbb{R}$ into translates of $\mathbb{Z}$, and again substitution into $F$ fails: $\frac13\approx\frac43$, but $F\left(\frac13\right)=\frac19\not\approx \frac{16}{9}=F\left(\frac43\right)$.

Showing that substitution of a particular relation into a function does work, in the cases where it does, is what we usually call showing that the function is "well-defined" on the equivalence classes of the relation. This can be non-trivial, and a common example is showing that addition and multiplication are well defined on the equivalence classes of $\mathbb{Z}$ given by congruence modulo $n$. Proving this gives us the ability to carry out substitution with polynomial functions and the equivalence relation of congruence modulo $n$.