2
$\begingroup$

The theory of concatenation (TC) can be equivalently expressed as the following assumptions:

  1. Closure of strings under concatenation $+$.
  2. Existence of an empty string $e$, namely $e+x = x = x+e$ for any string $x$.
  3. Associativity of $+$ on strings, namely $(x+y)+z = x+(y+z)$ for any strings $x,y,z$.
  4. Existence of distinct symbols $p,q$, namely distinct strings $p,q$ such that
    $p \ne u+v$ and $q \ne u+v$ for any non-empty strings $u,v$.
  5. Given any strings $a,b,c,d$ such that $a+b = c+d$, there is a string $x$ such that
    either ( $a+x = c$ and $b = x+d$ ) or ( $a = c+x$ and $x+b = d$ ).

Formally in first-order logic, TC is axiomatized as the theory with a binary function-symbol $+$ and constant-symbol $e$ and the following axioms:

  1. $∃e ∀x ( x+e = x = e+x )$.
  2. $∀x,y,z ( (x+y)+z = x+(y+z) )$.
  3. $∃x,y ( x≠y ∧ ¬∃u,v ( u≠e ∧ v≠e ∧ ( x=u+v ∨ y=u+v ) ) )$.
  4. $∀a,b,c,d ( a+b = c+d ⇒ ∃x ( a+x=c ∧ b=x+d ∨ a=c+x ∧ x+b=d ) )$.

Someone asked me (essentially) whether TC proves the cancellation property. This can be split into left-cancellation (LC) and right-cancellation (RC):

  • (LC) $∀x,y,c ( c+x = c+y ⇒ x=y )$.
  • (RC) $∀x,y,c ( x+c = y+c ⇒ x=y )$.

Of course, finite strings (the intended model of TC) satisfy cancellation (both LC and RC). So the question can be understood as asking whether these are independent over TC. Incidentally, LC and TC can be proven by TC plus a suitable induction schema.

I came up with countable binary-labelled linear orders modulo isomorphism (with $+$ interpreted as concatenation modulo isomorphism) as a model of TC that fails to satisfy cancellation. I also realize that countable binary-labelled well-orders modulo isomorphism is a model of TC and LC but not RC, because for any well-ordering every prefix embeds uniquely into itself, but not suffixes. An explicit counter-example for RC is $(0)+(0,0,0,\cdots) = ()+(0,0,0,\cdots)$.

My questions are:

What are other simple models of TC+LC+¬RC?

Is there a more systematic way of finding a model? (Mine was ad-hoc.)

I think TC and PA$^-$ are bi-interpretable. If so, can we utilize that to find nice models?

$\endgroup$
  • $\begingroup$ By the way, do you have a nice name for the $\forall abcd$ axiom? It seems to be saying that every nontrivial equality $ab=cd$ "factors through" the associative law, either as $(cx)b=c(xb)$ or $a(xd)=(ax)d$, so it can be viewed as an (evidently not completely successful) attempt to demand that there are no identities other than those forced by associativity. $\endgroup$ – Henning Makholm Oct 30 '17 at 15:12
  • $\begingroup$ @HenningMakholm: I would like to gloss that axiom as "Any two prefixes of the same string have one being a prefix of the other, and the same for suffixes." but I'm afraid it might be weaker. Haven't really tried hard to confirm or refute this. Any idea? $\endgroup$ – user21820 Oct 30 '17 at 15:42
  • $\begingroup$ @HenningMakholm: I now believe that my gloss of axiom (4) is weaker. Let $S$ be finite binary strings with no adjacent 1s and for each $x,y \in S$ define $x+y$ to be concatenation of $x,y$ but with a "0" inserted between the newly joined symbols if it forms "11" (thus "01" + "1001" = "0101001"). Then $(S,+)$ satisfies axioms (1) to (3), and satisfies the weaker $∀a,b,c,d (a+b=c+d⇒∃x(a+x=c∨a=c+x)∧∃x(b=x+d∨x+b=d))$ but not the original axiom (4). Am I right? (I didn't check carefully.) $\endgroup$ – user21820 Nov 3 '17 at 17:46
  • $\begingroup$ hmm, what would be a counterexample $a, b, c, d$ in that model? $\endgroup$ – Henning Makholm Nov 3 '17 at 17:49
  • $\begingroup$ @HenningMakholm: For (4) to succeed, consider "1"+"1" = "10"+"1", so you need $x$ to be "0" because "10" is strictly longer than "1", but then $x$ plus anything will have a "0", and hence (4) fails. $\endgroup$ – user21820 Nov 3 '17 at 18:01
3
$\begingroup$

The downside to "countable binary-labelled well-orders modulo isomorphism" is of course that you cannot compute explicitly in it -- it has uncountably many elements.

We get something better behaved if we consider only those elements where (a) the well-order is shorter than $\omega^2$, and (b) only finitely many positions are labeled $1$.

This is isomorphic to

The monoid of finite strings over $\{0,1,\infty\}$, modulo the relation $0\infty=\infty$.

where $\infty$ intuitively represents a sequence of $\omega$ many $0$s.


More systematically, lack of right cancellation plus the $abcd$ axiom implies that there must be elements $a,x,d$ such that $$ ax \ne a \qquad\text{and}\qquad xd=d $$ If we simply make this into the presentation of a monoid, we get $$ \langle a, x, d \mid xd=d \rangle $$ which is isomorphic to the above -- so what we have is in a certain sense the "simplest" model in that every solution must contain a homomorphic image of this that distinguishes between $ax$ and $a$.

$\endgroup$
  • $\begingroup$ Nice substructure! I never realized I could cut it down so much. But can you come up with any model that does not use well-orderings? =) $\endgroup$ – user21820 Oct 30 '17 at 14:36
  • $\begingroup$ Hmm sorry when I posted my above comment, somehow my browser had not loaded your edit, so all I saw was the first version. I guess your edit shows that there's nothing 'simpler', so thanks! =) $\endgroup$ – user21820 Oct 30 '17 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.