Prove the relation as an equivalence relation

Question

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.

Answer 1

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

4. $B=C$;
5. $(b1 \mathrel{R} c1) \land (b2 \mathrel{R} c2)$;
6. $(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.