- #1
cilla
- 13
- 0
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?
Last edited: