Cancellation

• Jun 18th 2010, 10:08 AM
mathman88
Cancellation
Let + denote the symbol for concatenation.

Given strings x,y,z show x+y=x+z implies y=z.
• Jun 18th 2010, 10:14 AM
undefined
Quote:

Originally Posted by mathman88
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.
• Jun 18th 2010, 10:15 AM
Ackbeet
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?
• Jun 18th 2010, 02:09 PM
mathman88
Quote:

Originally Posted by Ackbeet
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?
• Jun 18th 2010, 02:14 PM
Ackbeet
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.