Let + denote the symbol for concatenation.

Given strings x,y,z show x+y=x+z implies y=z.

Printable View

- Jun 18th 2010, 10:08 AMmathman88Cancellation
Let + denote the symbol for concatenation.

Given strings x,y,z show x+y=x+z implies y=z. - Jun 18th 2010, 10:14 AMundefined
- Jun 18th 2010, 10:15 AMAckbeet
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 PMmathman88
- Jun 18th 2010, 02:14 PMAckbeet
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: is well-defined. is not. It's related to the problem of whether a function's inverse is 1-1.