Prove using induction that $\forall x \in \Sigma^*$, $\operatorname{rev}(\operatorname{rev}(x)) = x$

Question

Let $\Sigma$ be an alphabet. Assume that $\forall x, y \in \Sigma^*$, $\operatorname{rev}(xy) = \operatorname{rev}(y)\operatorname{rev}(x)$

Prove using induction that $\forall x \in \Sigma^*$, $\operatorname{rev}(\operatorname{rev}(x)) = x$

Answer 1

(This is not a complete answer as I want to leave something for the OP, and because I see a problem)

The base step is showing that it's true for all strings of length 1. I actually don't see how to show that given only the information in the question (i.e. assuming nothing about what $\operatorname{rev}(x)$ means).

The inductive step is to show that if it's true for all strings of length $n-1$ is also true for strings of length $n$. A string $x$ of length $n>1$ ($>0$ actually) has a first symbol, let's call it $a$ and let's call the rest of the string $y$, such that $x=ay$. Then we have: $$ \operatorname{rev}(\operatorname{rev}(x))= \operatorname{rev}(\operatorname{rev}(ay))= \operatorname{rev}(\operatorname{rev}(y)\operatorname{rev}(a))= $$ Where we used $\operatorname{rev}(xy) = \operatorname{rev}(y)\operatorname{rev}(x)$ (as given) in the last step. It you use it again, you will be in a position where you can use the induction hypothesis (and the base case - you can avoid that using strong induction - at least for $n\geq 4$)