# Prove the relation as an equivalence relation

Consider the infinite set of all English strings of all possible lengths.
Two strings $A$ an $B$ are said to be in a relation $\mathrel{R}$ iff:

• $A$ is equal to $B$ or
• Lets divide $A$ into two parts of equal lengths: $a1,a2$ and $B$ into parts $b1,b2$ likewise. Now one of the following must be true:
• $(a1 \mathrel{R} b1)$ and $(a2 \mathrel{R} b2)$
• $(a1 \mathrel{R} b2)$ and $(a2 \mathrel{R} b1)$

Eg: $(abaa \mathrel{R} aaba)$ since $(ab \mathrel{R} ba)$ and $(aa \mathrel{R} aa)$

Prove that the relation is equivalence relation.

What I did?
I was able to prove its reflexive and symmetric ofcourse. Transitivity is tricky though.
If the length is odd, then transitivity holds as the strings need to be identical.
I have the intuition that for even length, induction might help but I am not ready with formal proof.

• If I am interpreting the problem correctly and my intuition is correct, it sounds as though this could be reworded as the following: A string of length $2^n(2k+1)$ is considered related to another string of the same length iff the other string is formed via a permutation of the original string's "blocks." Seeing it in this light, the transitivity will become clear as the composition of permutations is again a permutation. It just remains for you to formalize my observation and prove that the definition of your relation coincides with the relation I describe here. – JMoravitz Jun 9 '18 at 21:05
• @JMoravitz can you explain more on "significance of the particular length you mentioned" and "what do you mean by string's blocks". – maverick Jun 9 '18 at 21:09
• In the above, a string of length $2^n(2k+1)$ will have $2^n$ blocks, each of size $(2k+1)$, for example how $\underline{bob}~\underline{car}~\underline{cat}~\underline{dog}$ is related to $\underline{dog}~\underline{cat}~\underline{bob}~\underline{car}$. I worry though in thinking about this longer that perhaps not all permutations of the blocks will be permitted, but only permutations of a certain type. It will remain then to show that the compositions of such permutations remain closed. E.g. I don't think $bob~car~dog~cat$ is related to $bob~dog~car~cat$ – JMoravitz Jun 9 '18 at 21:10
• @JMoravitz Nice, I understand your approach. But what about induction, if we assume all strings of length < i are transitive, we can then prove for length i also. – maverick Jun 9 '18 at 21:14
• If we were to use induction, I would do double-induction over the $n$ and $k$ that appear in $2^n(2k+1)$, i.e. simultaneous induction over the number of blocks and the size of the blocks. – JMoravitz Jun 9 '18 at 21:17

The problem is rather technical. You need to examine all possible nine combinations that validate the fact $(A \mathrel{R} B) \land (B \mathrel{R} C)$ and derive $(A \mathrel{R} C)$ from that. Simple induction over string's length $n$ could indeed help. Let $|A|$ denote the length of the string $A$.

Formally, you need to prove $(A \mathrel{R} B) \implies |A|=|B|$ first. This can be done via induction too. The counter would be $\max (|A|, |B|)$.

Coming back to transitivity, the base case $n=1$, as well as the proof for odd $n$, is easy: since there is no way to split a string into parts of equal lengths, $(A \mathrel{R} B)$ means $A=B$ in this case and $\mathrel{R}$ is therefore transitive. Now let $n$ be even. Assume $(A \mathrel{R} B) \land (B \mathrel{R} C)$, $|A|=|B|=|C|=n$, $A = a1 + a2$, $B = b1 + b2$, $C = c1 + c2$, where "$+$" means concatenation. There are three possible statements (not mutually exclusive though) which validate $(A \mathrel{R} B)$:

1. $A=B$;
2. $(a1 \mathrel{R} b1) \land (a2 \mathrel{R} b2)$;
3. $(a1 \mathrel{R} b2) \land (a2 \mathrel{R} b1)$.

Similarly, there are three possible statements which validate $(B \mathrel{R} C)$:

1. $B=C$;
2. $(b1 \mathrel{R} c1) \land (b2 \mathrel{R} c2)$;
3. $(b1 \mathrel{R} c2) \land (b2 \mathrel{R} c1)$.

As said above, there are nine possible pairs of these statements in total. Five of them containing either 1 or 4 are trivial. Here's how we can examine the remaining four:

• (2, 5). $(a1 \mathrel{R} b1) \land (b1 \mathrel{R} c1) \implies (a1 \mathrel{R} c1)$. Here we use the inductive assumption for $n' = |a1| = |b1| = |c1| =\frac n 2$. Similarly, $(a2 \mathrel{R} b2) \land (b2 \mathrel{R} c2) \implies (a2 \mathrel{R} c2)$ as $|a2| = |b2| = |c2| =\frac n 2$. By the definition of $\mathrel{R}$ (second case, first subcase), $(a1 \mathrel{R} c1) \land (a2 \mathrel{R} c2) \implies (A \mathrel{R} C)$.
• (2, 6). $(a1 \mathrel{R} b1) \land (b1 \mathrel{R} c2) \implies (a1 \mathrel{R} c2)$. $(a2 \mathrel{R} b2) \land (b2 \mathrel{R} c1) \implies (a2 \mathrel{R} c1)$. By the definition of $\mathrel{R}$ (second case, second subcase), $(a1 \mathrel{R} c2) \land (a2 \mathrel{R} c1) \implies (A \mathrel{R} C)$.
• (3, 5). $(a1 \mathrel{R} b2) \land (b2 \mathrel{R} c2) \implies (a1 \mathrel{R} c2)$. $(a2 \mathrel{R} b1) \land (b1 \mathrel{R} c1) \implies (a2 \mathrel{R} c1)$. By the definition of $\mathrel{R}$ (second case, second subcase), $(a1 \mathrel{R} c2) \land (a2 \mathrel{R} c1) \implies (A \mathrel{R} C)$.
• (3, 6). $(a1 \mathrel{R} b2) \land (b2 \mathrel{R} c1) \implies (a1 \mathrel{R} c1)$. $(a2 \mathrel{R} b1) \land (b1 \mathrel{R} c2) \implies (a2 \mathrel{R} c2)$. By the definition of $\mathrel{R}$ (second case, first subcase), $(a1 \mathrel{R} c1) \land (a2 \mathrel{R} c2) \implies (A \mathrel{R} C)$.

I wonder what was the reasoning in your proof of symmetry, because, technically speaking, you ought to use an induction similar to above (however only three cases 1-3 are to be considered and "reversed"). However, there may be some "intuitive" approach not seen to me. If so, then transitivity should be "intuitive" likewise.