1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

Tags:
  1. Oct 20, 2014 #1
    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.
    Is f one-to-one? Is f onto? Prove your answers.

    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. jcsd
  3. Oct 20, 2014 #2
    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|##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



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