# Prove whether f(α) = αα^R; X = {a,b}; f:X*→(palindromes over X) -- is injective and/or surjective?

Tags:
1. Oct 20, 2014

### cilla

1. The problem statement, all variables and given/known data

Let X = {a,b}.

A palindrome over X is a string α for which α = αR (i.e., a 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(α) = ααR.

2. Relevant equations

X* = set of all strings over X
αR = α in reverse

so if α = abb, αR = bba, and ααR = abbbba

3. The attempt at a solution

Injection:
Let f(α) = f(β).
Then ααR = ββR.
Show α = β.
We can reverse each side and get αRα = βRβ.
The cardinality of some string is equal to that of itself in reverse: |γ| = |γR|.
Therefore the cardinality of either side of the equation must be equal...

I don't quite know where I'm going with that. I know it is injective because
if [( f(α) = αR ) ∧ ( f(α) = f(β) )] → [ αR = βR ];
reverse both sides, α = β. The above seems to be a logically equivalent extension of that. But how to prove it?

Surjection:
Suppose that β ∈ the set of palindromes over X.
Then the string is a palindrome composed only with characters in {a,b}.
Any substring will therefore rightfully belong to the domain X as well, as the codomain of ƒ is a subset of the domain X... for every β, there is an α... therefore the codomain and the range are equal and the function maps onto the set of palindromes over X... I think it is.
Let ααR = β and solve for α? But if so how?

Last edited: Oct 20, 2014
2. Oct 20, 2014

### gopher_p

Given two strings $\alpha=\alpha_1\alpha_2\ldots \alpha_n$ and $\beta=\beta_1\beta_2\ldots \beta_m$ over $X$, $\alpha=\beta$ if and only if $n=m$ (i.e. $|\alpha|=|\beta|$) and $\alpha_i=\beta_i$ for all $i=1,\ldots,n$.
Given strings $\alpha$ and $\beta$ over $X$, $|\alpha\beta|=|\alpha|+|\beta|$.