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.
 A: 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)$:


*

*$A=B$;

*$(a1 \mathrel{R} b1) \land (a2 \mathrel{R} b2)$;

*$(a1 \mathrel{R} b2) \land (a2 \mathrel{R} b1)$.


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


*$B=C$;

*$(b1 \mathrel{R} c1) \land (b2 \mathrel{R} c2)$;

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