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.

  • $\begingroup$ 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. $\endgroup$ – JMoravitz Jun 9 '18 at 21:05
  • $\begingroup$ @JMoravitz can you explain more on "significance of the particular length you mentioned" and "what do you mean by string's blocks". $\endgroup$ – maverick Jun 9 '18 at 21:09
  • 1
    $\begingroup$ 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$ $\endgroup$ – JMoravitz Jun 9 '18 at 21:10
  • $\begingroup$ @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. $\endgroup$ – maverick Jun 9 '18 at 21:14
  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.