Proving Injectivity & Surjectivity of f: Palindromes over X

[cilla]

Homework Statement

[/B]
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.
Is f one-to-one? Is f onto? Prove your answers.

Homework Equations

[/B]
X* = set of all strings over X
α^R = α in reverse

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

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?

 

[gopher_p]

Two ideas that might help you organize your thoughts a little better;

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|##.