Results 1 to 5 of 5

Math Help - Cancellation

  1. #1
    Junior Member
    Joined
    Dec 2008
    Posts
    62

    Cancellation

    Let + denote the symbol for concatenation.

    Given strings x,y,z show x+y=x+z implies y=z.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by mathman88 View Post
    Let + denote the symbol for concatenation.

    Given strings x,y,z show x+y=x+z implies y=z.
    I'm curious to see the formal notation other people will probably post, but it should be easy to see that if you just "chop off" the x from the left of strings x+y and x+z you will be left with y on the LHS and z on the RHS.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    You need to have some sort of symbol/procedure for deleting strings from strings, or taking just a subset. Moreover, as string concatenation is not commutative, it'll need to reflect that fact. Perhaps you could think of the size of string x as |x|, which equals the number of characters. Then, define the left delete function ld as follows:

    ld(x,n) = x with the first n characters deleted from the left, if n <= |x|
    = 0 if n > |x|.

    That function should, I think undo concatenation from the left, which is what you need. You'll probably need to show that the function is well-defined (that is, its output is identical for identical inputs). Then, you'll need to show that

    ld(x+y,|x|) = y for all strings x and y.

    Perhaps you can finish from there?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Dec 2008
    Posts
    62
    Quote Originally Posted by Ackbeet View Post
    You need to have some sort of symbol/procedure for deleting strings from strings, or taking just a subset. Moreover, as string concatenation is not commutative, it'll need to reflect that fact. Perhaps you could think of the size of string x as |x|, which equals the number of characters. Then, define the left delete function ld as follows:

    ld(x,n) = x with the first n characters deleted from the left, if n <= |x|
    = 0 if n > |x|.

    That function should, I think undo concatenation from the left, which is what you need. You'll probably need to show that the function is well-defined (that is, its output is identical for identical inputs). Then, you'll need to show that

    ld(x+y,|x|) = y for all strings x and y.

    Perhaps you can finish from there?
    How would one go about showing ld is well defined?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    A function being well-defined means that it is single-valued. So, a particular element of the domain can only get mapped to one element in the range, not more than one. To prove it, take two arbitrary strings that are equal but have different labels, and show that the function ld applied to those strings comes out to the same thing.

    As an example: f(x)=\sqrt{x} is well-defined. f(x)=\pm\sqrt{x} is not. It's related to the problem of whether a function's inverse is 1-1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Cancellation of sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 11th 2011, 03:15 PM
  2. cancellation
    Posted in the Algebra Forum
    Replies: 1
    Last Post: June 6th 2010, 11:50 PM
  3. cancellation & simplification
    Posted in the Algebra Forum
    Replies: 2
    Last Post: June 5th 2010, 03:59 PM
  4. cancellation
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: April 26th 2010, 01:17 AM
  5. Multiplication cancellation proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 4th 2007, 06:53 PM

Search Tags


/mathhelpforum @mathhelpforum