Palindrome function proof one-to-one, onto

1.2k Views Asked by At

This is the question:

Let $X=\text{{a,b}}$. A palindrome over $X$ is a string $\alpha$ for which $\alpha = \alpha^R$ (the string that reads the same forward and backward). An example of a palindrome over $X$ is $bbaabb$. Define a function from $X^*$ to the set of palindromes over $X$ as $f(\alpha)= \alpha \alpha^R$. Is $f$ one-to-one? Is $f$ onto? Prove your answers.

For the first part I have:

Let $\beta,\gamma \in X^*$. A function $f:X^* \to X$ is one-to-one if it satisfies the condition:

$$\forall \beta, \gamma \in X(f(\beta)=f(\gamma) \Rightarrow \beta = \gamma) $$ Here: $$f(\beta)=\beta\beta^R, f(\gamma)=\gamma\gamma^R$$ then $$\beta\beta^R = \gamma\gamma^R \Rightarrow \beta = \gamma$$ is this sufficient to prove that it is one-to-one?

As for the proving whether or not it is onto I have no idea how to start.

1

There are 1 best solutions below

1
On BEST ANSWER

Note that $\alpha\alpha^R $ is always a string of even length, and so palindromes of odd length cannot be in the image of $f$. So for strings of even length to be palindrome things should repeat in the reversed way after the mid-point. Now you can see injectivity of $f$.