# Definition of Substitution (Equality vs Equivalence relations)

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.

• 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? Aug 25 '13 at 18:07
• @Daniela Almost surely that depends on what $\equiv$ and $<$ mean. Aug 25 '13 at 18:09
• @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. Aug 25 '13 at 18:15
• @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). Aug 25 '13 at 18:17
• @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. Aug 27 '13 at 17:42

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.

What I believe you call substitution, isn't always possible in ordinary mathematics. You can easily end up with nonsense if you aren't careful. For instance, no one around here (well there does exist one exception, but I think he's on holiday at the moment), will deny that 5-3=2. Nor will anyone deny 4-1=3. Given that you can substitute arbitrarily, it follows that 5-4-1=2. Except, 5-4-1=1-1=0 makes sense under our assumptions, and who would ever dare deny one of our assumptions? No wise person would do that, right?

The fool currently on holiday has told me on more than one occasion that the problem is not hard to resolve at all. Substitutions for equals can happen in mathematics easily if one starts doing things differently. The fool on holiday has also told me that no one around here much cares to take up any sort of method which can resolve such a problem. The fool on holiday has also told me he has personally concluded that either mathematicians don't usually believe in substitutions for equals, or there have to exist a massive number of contradictions derivable from the principles employed by many mathematical texts. And yes, the fool is a he.

The fool left me with some notes which indicate how to resolve the problem in several different ways, which I can share if you have not happened upon a solution yourself so far.

You can have "substitution for equals" in a fairly mechanical fashion which requires no insight. There exist at least 4 ways to do this. You can't use all 4 ways simultaneously. The 4 ways the fool indicated to me for binary functions are

1. Write all functions before numerical symbols, variables, and other constants. Instead writing x+y-x*y write - + x y * x y.
2. Put brackets or other parenthetical symbols around the expressions. Instead of writing x+y-x*y, write [[x+y]-[x*y]].
3. Put brackets or other parentheses around the variables, numerical symbols, and other constants. Instead of writing x+y-x*y write [[x]+[y]]-[[x]*[y]].
4. Write all function after the numerical symbols, variables, and other constants. Instead writing x+y-x*y write x y + x y * - .

The fool kindly left me with notes which encapsulate rules which enable us to determine when an expression can get "substituted for an equal" mechanically, as somehow the fool managed to convince me that things would work out better if more texts did that thoroughly.

Let U stand for any unary function, and B the class of binary functions. For the first way of writing things, the rules go:

1. If x is a variable or constant, then Fx equals a variable or constant.
2. If x and y are variables or constant, then Bxy equals a variable or constant.

For the second way:

1. If x is a variable or constant, then Fx equals a variable or constant.
2. If x and y are variables or constants, then [xBy] equals a variable or constant.

For the third way:

1. If x is a variable or constant, then Fx equals a variable or constant.
2. If x and y are variables or constants, then [x]B[y] equals a variable or constant.

For the fourth way:

1. If x is a variable or constant, then Fx equals a variable or constant.
2. If x and y are variables or constants, then xyB equals a variable or constant.

The fool informed me you can freely space things out in any of the 4 ways as well as adding more parenthetical symbols in the first and fourth way if you like. And that all four ways allow you to "substitute for equals" just by manipulating symbols, so to speak.

• I guess the fool voted me down without telling me why. He never did much care for getting referred to in the third person... I think. Aug 27 '13 at 1:53
• The downvote comes form me, here is why: I don't like your example. Subtraction is a function $s:\mathbb{Z}\times\mathbb{Z}\rightarrow\mathbb{Z}$ where $\mathbb{Z}$ is the set of integers. Now 5 - 3 = 2 is short for s(5,3) = 2 and 4 - 1 = 3 is short for s(4,1) = 3. Now substituting in s(5,3) = 2 gives s(5,s(4,1)) = 2, which does not lead to any contradiction. Additionally needing to call anyone a fool seems hostile and unnecessary to me. Aug 27 '13 at 1:58
• @VincentPfenninger I don't believe you understood how I used the term "fool" here. Oh come on now... you've got to be kidding me!!! You can't ever write a mathematical text using a notation like s(5,s(4,1)) consistently from start to finish. So, you can't be serious about your notation at all!!! Aug 27 '13 at 2:22
• Of course I'm serious. I don't see what's wrong with my notation. We use short hands to make things less clumsy, but form time to time we need to remind ourselves what the notation really means in order not to abuse the notation. In your example you implicitly use s(5,s(4,1)) = s(s(5,4),1) which is not true, you are abusing the notation! Aug 27 '13 at 9:15
• If you are assuming the more general case you are also assuming the special case... Your repeated stating that there is anything wrong with my notation doesn't make it so. It seems to me that you like to state your opinion as fact without giving any arguments for why we should take you seriously. Also if I haven't realised what you're trying to do, why don't you tell me? Aug 29 '13 at 10:34