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?

  • $\begingroup$ By "property of substitution", do you mean, "For any well-formed formula $F(x)$, we have $a=b\implies F(a)=F(b)$, or do you mean something else? $\endgroup$ – G Tony Jacobs Sep 16 '17 at 17:48
  • 1
    $\begingroup$ Wikipedia does not say that one can prove the substitution property from the equivalence relations properties. This result looks completely false. There are many equivalence relations, and they don't have such drastic consequences. $\endgroup$ – Gribouillis Sep 16 '17 at 18:10
  • $\begingroup$ @GTonyJacobs: Yes, that's what I mean. $\endgroup$ – Daniel R. Collins Sep 16 '17 at 21:39
  • $\begingroup$ @Gribouillis: I think I've seen the claim made explicitly elsewhere, and I was taking the Wikipedia claim that equivalence properties are "seen as fundamental" to mean the same. If that's not the case, then seeing a counterexample would be helpful to me. $\endgroup$ – Daniel R. Collins Sep 16 '17 at 21:39
  • 2
    $\begingroup$ Well, we could define an equivalence relation on complex numbers where $z\sim w$ if and only if $\mathfrak{Re}(z)=\mathfrak{Re}(w)$. Then, taking the formula $F(z)=z^2$, we have $1\sim 1+i$, but $F(1)=1\not\sim 2i=F(1+i)$ $\endgroup$ – G Tony Jacobs Sep 16 '17 at 21:46

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


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.