3
$\begingroup$

I'm confused as to wether substitution is a consequence of the properties about equivalence relations (transitivity, reflexivity, and symetry) or rather it is an independent property of equality. For example, in general $(x=y) \wedge (x<z) \Longrightarrow (y<z)$. But what if I have an equivalence relation , say $"\equiv$", instead of equality. Can I use substitution directly or do I need to prove it?

EDIT: I have to admit that I asked this question without being very clear and also without thinking much about it. So, my appologies for that. I'll do some aditional details and please if you consider that my question doesn't make sense, vote to close it.

Like I said, I'm confused because I don't know if "equality" ($=$) is a term more general than "equivalence relation" (~) or else they are the same. I was asking about the property of substitution because aparently when using "$=$" everything can be substituted whereas it is not the case when using "~".

Let's define, for example, "$\equiv_{n}$" such that $\forall a,b\in \mathbb{Z}(a\equiv_{n} b \iff n|b-a)$. Now, suppose that $a\equiv_{n} b$ and $b=6^{m}$ for some $m\in \mathbb{Z}$. Then $a\equiv_{n}6^{m}$ by substitution. Also if $m=k+7$ we can again make a substitution to get $a\equiv_{n}6^{k+7}$. But, this same process cannot always be done if we consider $b\equiv_{n}6^{m}$ and $m\equiv_{n}k+7$.

Since both "$=$" and "~" are transitive, reflexive and symmetric my guess was then that substitution is a property that belongs to $"="$ but no to "~", but I'm not sure and I'm totally confused.

$\endgroup$
8
  • $\begingroup$ what confuses you exactly? why do you suppose the identity relation would not allow substitution? do you have a counter-example that makes you suspect? $\endgroup$ Aug 25, 2013 at 18:07
  • $\begingroup$ @Daniela Almost surely that depends on what $\equiv$ and $<$ mean. $\endgroup$
    – Git Gud
    Aug 25, 2013 at 18:09
  • $\begingroup$ @al-Hwarizmi Intuitively I would think that substitution is always possible in terms of equality in general but I'm not sure about substitution in an equivalence relation. For example if "$\equiv$" and $"<"$ are defined in terms of equipotence. $\endgroup$ Aug 25, 2013 at 18:15
  • $\begingroup$ @DanielaDiaz Regarding to cardinalities you can indeed make the substituion, but that's because you'll not actually be comparing the sets, but rather their cardinalities and therefore you'll actually be dealing with an equality (between cardinalities). $\endgroup$
    – Git Gud
    Aug 25, 2013 at 18:17
  • 1
    $\begingroup$ @DanielaDiaz I read your edit. It seems to me that you're not confused and that you know what's going on. With regards to first sentence in your question, substituion is a consequece of $=$. Substitutions comming from an equivalence relation may be done, but only because of transitivity. In this case it is not a substituion per se, but rather a consequence of whatever you have. $\endgroup$
    – Git Gud
    Aug 27, 2013 at 17:42

1 Answer 1

2
$\begingroup$

You would need to prove the substitution property. Suppose we have some equivalence relation $\cong$, an operation $\circ$, and a relation $R$.

A lot of mathematics can be done by painstakingly using $\cong$ every time one normally uses $=$. We could define the following:

$\circ$ is a $\cong$-compatible operation iff for every $x,y,z$:

$$x \cong y \implies z \circ x \cong z \circ y\land x \circ z \cong y \circ z$$

$R$ is a $\cong$-compatible relation iff for every $x,y,z$:

$$x \cong y \implies (z R x \iff z R y \land x R z \iff y R z)$$

Effectively, then, $\circ$ and $R$ do not "distinguish" $\cong$-equivalence classes. The former of these usually is defined the other way around, and $\cong$ is called compatible with $\circ$ (see ProofWiki).

Similar definitions can be made for operations and relations of different arities. It is clear that these definitions amount to the substitution property.

They also provide us an insight into what equality is. For $x = y$ to be meaningful, it is obvious that all operations and relations should be $=$-compatible.

On the other hand, this property intuitively says everything there is to say about equality. For, if we cannot distinguish two things by any operation or relation, are they really different?

There is a philosophical aspect to this, but for the purposes of mathematics, it is perfectly viable to define $=$ by requiring it to universally satisfy the substitution property.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .