# Equivalence of Right Infinite Words

Authors: Liga Kulesa
Journal: Journal of Discrete Mathematics
 (2013)

---

## Abstract

Closure properties of some classes of right infinite words have been studied extensively; we are interested in the general algebraic structure of right infinite words. We investigate preorder of morphism invariant classes and show that it is not a semilattice.


---

## Body

## 1. Introduction

Right infinite words are ubiquitous in mathematics and theoretical computer science, therefore closure properties of some classes of right infinite words have been studied extensively. We consider simple function called morphism, which transforms right infinite word into a right infinite word.There are several kinds of properties that are typically studied about a class of words (a language), being finite or infinite. These include categorization, the study of the relationships between different languages; representation, different ways of describing the words belonging to a language; closure properties, the invariance of the language when certain transformations are applied; for example, Cobham [1] proved that the class of automatic sequences is closed under uniform transductions, that is, under the transducers where every transition outputs a string of the same length. In 1994, Dekking presented proof that finite state transduction of morphic sequence is still morphic, even if the transducer is nonuniform [2].In [3] Belovs introduced partial ordering on right infinite words: x⩽y if and only if there exists a Mealy machine that transforms y to x. He proved that this ordering is an upper semilattice, but it is not a lower semilattice. Similarly we can introduce partial ordering or right infinite words by transducers.We consider a poset of morphism invariant classes, which is simpler structure, therefore from an algebraic point of view it is surprising that it is neither an upper semilattice, nor a lower semilattice. Recently, Muchnik et al. [4] proved that transducer can be expressed as a composition of morphism and Mealy machine. Thus the ordering introduced by transducers is not an upper semilattice, nor a lower semilattice. In this sense the ordering defined by Mealy machine crucially differs.


## 2. Preliminaries

LetA be a finite nonempty set, and let A* be a free monoid generated by A. The identity element of A* is called the empty word and is denoted by λ. A function μ:A*→B* is called morphism if μ(λ)=λ and μ(uv)=μ(u)μ(v). The morphism is uniquely defined by its values on the A elements.The morphismμ is called nonerasing if for all a∈A:μ(a)≠λ. It is called uniform if for all a,b∈A:|μ(a)|=|μ(b)|. It is called literal if for all a∈A:μ(a)=1. The morphism μ can also be applied to an infinite word as follows:
(1)μ(x)=limn→∞μ([0,n]).
It is possible to define morphism with more than one argument in the same way. Let xi∈Aiω and f be a function from A0×A1×A2×⋯×Ak to B*, then
(2)f(x0,x1,x2,…,xk)=∏i=0∞f(x0[i],x1[i],…,xk[i]).
A set L with defined binary relation ⩾ on it is called a partially ordered set (further in text—a poset) or just an order, if it fulfills the following three axioms:
(3)x⩾xreflexivity,x⩾y,y⩾z⇒x⩾ztransitivity,x⩾y,y⩾x⇒x=yantisymmetry.
If a relation fulfills only the reflexivity and transitivity axioms then such an algebraic structure is called a preorder.An elementa of L is called the largest element if and only if for all x∈L:a⩾x. An element is called maximal if and only if for all x∈L:x⩾a⇒x=a.For each two elementsx and y of L their upper bound is such an element z where z⩾x and z⩾y. The supremum is the smallest upper bound; that is, such element z=x∨y that not only z⩾x,y, but also for any other element t⩾x,y, the expression t⩾z holds. For each two elements x and y of L their lower bound is such an element z where z⩽x and z⩽y. The infimum is such element z=x∧y that not only z⩽x,y, but also for any other element t⩽x,y holds t⩽z.A poset whose every two elements have a supremum is called anupper semilattice. If every two elements have infimum, it is called a lower semilattice.For more in depth coverage of the previous topics see, for example, [5, 6].


## 3. Semilattice

In this section we will prove that algebraic structure〈𝔑/≡m,⇁m〉is not a semilattice, where(1)
𝔑=⋃k=0∞‍{0,1,2,…,k}ω;(2)
⇁m is a relation, which holds if and only if there exists a morphism μ such that μ(x)=y;(3)
x≡my if and only if x⇁my∧y⇁mxOne can check that〈𝔑/≡m,⇁m〉 is a poset. By the semilattice definition every two elements must have a supremum and an infimum. We show that there are two elements in 〈𝔑/≡m,⇁m〉, which do not have a supremum, and that there are two elements in 〈𝔑/≡m,⇁m〉, which do not have an infimum, therefore, 〈𝔑/≡m,⇁m〉 is not a semilattice.Letx denote a word, such that
(4)xi={1,if∃ki=k2,0,otherwise,x=11001000010000001⋯.
Let morphisms μ and φ be defined {0,1}*→{0,1}*:
(5)μ(1)=11,φ(1)=111,μ(0)=00,φ(0)=000.
Morphism μ maps the word x as follows:
(6)μ(x)=d=11110000110000000011⋯.
Morphism φ maps the word x as follows:
(7)φ(x)=t=111111000000111000000000000⋯.
Now we will define new word from d=μ(x) and t=φ(x):
(8)(d,t)=(d0,t0)(d1,t1)⋯(dn,tn)⋯,fff55222222222(d,t)=(1,1)(1,1)(1,1)(1,1)(0,1)×(0,1)(0,0)(0,0)(1,0)(1,0)(0,0)(0,0)⋯.
Mappings ψ:(di,ti)→di;ξ:(di,ti)→ti define morphisms
(9){(0,0),(0,1),(1,0),(1,1)}*⟶{0,1}*.
From these definitions we obtain
(10)(d,t)ψ=d,(d,t)ξ=t.
For technical reasons we will write (x)f instead of f(x).Lemma 1.
For allk⩾1 factor 10k1 appears in words x, d,  and t once at most.Proof.
Obvious.Next we consider following diagram:(11)Lemma 2.
If(x)μ1μ2=d, then μ1μ2=μ.Proof.
Let us consider the first position in wordx; suppose that (1)μ1μ2=u, then(1)
ifu=λ and (0)μ1μ2=u1(12)then(x)μ1μ2=u1ω≠d, thus (1)μ1μ2≠λ;(2)
u≠0v, since word d begins with 14;(3)
ifu=1, then
(13)
(3.1)
(0)μ1μ2≠λ. Indeed, otherwise (x)μ1μ2 will generate 1ω≠d;(3.2)
(0)μ1μ2≠1n. Indeed, otherwise (x)μ1μ2 will generate 1ω≠d;(3.3)
(0)μ1μ2≠1n0k, because (x)[2,3]μ1μ2 and (x)[5,6]μ1μ2 will generate 10k1, a contradiction with Lemma 1;(3.4)
(0)μ1μ2≠0v, since word d begins with 14;(4)
ifu=11, then
(14)
(4.1)
(0)μ1μ2≠λ. Indeed, otherwise (x)μ1μ2 will generate 1ω≠d;(4.2)
(0)μ1μ2≠0, since (x)[0,5]μ1μ2=140212≠d;(4.3)
(0)μ1μ2=00;(4.4)
(0)μ1μ2≠0n, where n>2, since (x)[0,5]μ1μ2=1402n≠d;(5)
u≠1n, where n>2, since (x)[0,1]μ1μ2=12n≠d;(6)
u≠1n0k, since (x)[0,1]μ1μ2=1n0k1n0k≠d.From (4.3) it follows that μ1μ2=μ.Lemma 3.
If(x)μ1ξ2=t, then μ1ξ2=φ.Proof.
Let us consider the first position in wordx; suppose that (1)μ1ξ2=u, then(1)
ifu=λ and (0)μ1ξ2=u1(15)then(x)μ1ξ2=u1ω≠t, thus (1)μ1ξ2≠λ;(2)
u≠0v, since word t begins with 16;(3)
ifu=1, then
(16)
(3.1)
(0)μ1ξ2≠λ. Indeed, otherwise (x)μ1ξ2 will generate 1ω≠t;(3.2)
(0)μ1ξ2≠1n. Indeed, otherwise (x)μ1ξ2 will generate 1ω≠t;(3.3)
(0)μ1ξ2≠1n0k, because then (x)[2,3]μ1ξ2 and (x)[5,6]μ1ξ2 will generate 10k1, a contradiction with Lemma 1;(3.4)
(0)μ1ξ2≠0v, since word t begins with 16;(4)
ifu=11, then
(17)
(4.1)
(0)μ1μ2≠λ. Indeed, otherwise (x)μ1ξ2 will generate 1ω≠t;(4.2)
(0)μ1ξ2≠1. Indeed, otherwise (x)μ1ξ2 will generate 1ω≠t;(4.3)
(0)μ1ξ2≠1n0k, because (x)[2,3]μ1ξ2 and (x)[5,6]μ1ξ2 will generate 10k1, a contradiction with Lemma 1;(4.4)
(0)μ1ξ2≠0v, since word t begins with 16;(5)
ifu=111, then
(18)
(5.1)
(0)μ1ξ2≠λ. Indeed, otherwise (x)μ1ξ2 will generate 1ω≠t;(5.2)
(0)μ1ξ2≠0, since (x)[0,5]μ1μ2=160213≠t;(5.3)
(0)μ1ξ2≠00, since (x)[0,5]μ1μ2=160413≠t;(5.4)
(0)μ1ξ2=000;(5.5)
(0)μ1ξ2≠0n, where n>3, since (x)[0,5]μ1ξ2=111102n≠t;(6)
u≠1n, where n>3, since (x)[0,1]μ1μ2=12n≠t;(7)
u≠1n0k, since (x)[0,1]μ1μ2=1n0k1n0k≠t.From (5.4) it follows that μ1ξ2=φ.Lemma 4.
If(d,t)ξ1ξ2=t, then ξ1ξ2=ξ.Proof.
Let us consider the first position in word(d,t); suppose that (1,1)ξ1ξ2=u, then
(1) ifu=λ and (0,1)ξ1ξ2=u1, then(1.1)
ifu1=λ, then
(19)
Next we consider position(0,0) in word (d,t); suppose that (0,0)ξ1ξ2=u2, then(1.1.1)
u2≠λ, otherwise we obtain periodic word, but word t is not periodic;(1.1.2)
u2≠0v, since word t begins with 16;(1.1.3)
u2≠1n, otherwise we obtain (d,t)[20,26]ξ1ξ2=17n>16, but it is a contradiction with t construction;(1.1.4)
u2≠1n0k, since, for example, (d,t)[6,7]ξ1ξ2 and (d,t)[10,11]ξ1ξ2 will generate 10k1, but it is a contradiction with Lemma 1;(1.2)
u1≠0v, since word t begins with 16;(1.3)
ifu1=1, then
(20)
Next we consider position(0,0) in word (d,t); suppose that (0,0)ξ1ξ2=u2, then(1.3.1)
ifu2=λ, then
(21)
Next we consider position(1,0) in word (d,t); suppose that (1,0)ξ1ξ2=u3, then(1.3.1.1)
u3≠λ, otherwise we obtain periodic word 1ω≠t;(1.3.1.2)
u3≠0v, since word t begins with 16;(1.3.1.3)
u3≠1n, otherwise we obtain periodic word 1ω≠t;(1.3.1.4)
u3≠1n0k, since, for example, (d,t)[8,9]ξ1ξ2 and (d,t)[18,19]ξ1ξ2 will generate 10k1, but it is a contradiction with Lemma 1;(1.3.2)
u2≠0v, since word t begins with 16;(1.3.3)
u2≠1n, otherwise we obtain (d,t)[20,26]ξ1ξ2=17n>16, but it is a contradiction with t construction;(1.3.4)
u2≠1n0k, since, for example, (d,t)[6,7]ξ1ξ2 and (d,t)[10,11]ξ1ξ2 will generate 10k1, but it is a contradiction with Lemma 1;(1.4)
u1≠1n, where n>1, since (d,t)[4,5]ξ1ξ2 and (d,t)[12,13]ξ1ξ2 will generate 12n>14, but from t construction such situation occurs only in beginning of the word;(1.5)
u1≠1n0k, since, for example, (d,t)[4,5]ξ1ξ2 and (d,t)[12,13]ξ1ξ2 will generate 10k1, but it is a contradiction with Lemma 1;
(2)u≠0v, since word t begins with 16;
(3) ifu=1 and (0,1)ξ1ξ2=u1, then(3.1)
ifu1=λ, then
(22)
Next we consider position(0,0) in word (d,t); suppose that (0,0)ξ1ξ2=u2, then(3.1.1)
ifu2=λ, then
(23)
Next we consider position(1,0) in word (d,t); suppose that (1,0)ξ1ξ2=u3, then(3.1.1.1)
u3≠λ, otherwise we obtain periodic word 1ω≠t;(3.1.1.2)
u3≠0v, since word t begins with 16;(3.1.1.3)
u3≠1n, otherwise we obtain periodic word 1ω≠t;(3.1.1.4)
u3≠1n0k, since, for example, (d,t)[8,9]ξ1ξ2 and (d,t)[18,19]ξ1ξ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.1.2)
u2≠0v, since word t begins with 16;(3.1.3)
u2≠1n, otherwise we obtain (d,t)[20,26]ξ1ξ2=17n>16, but it is a contradiction with t construction;(3.1.4)
u2≠1n0k, since, for example, (d,t)[6,7]ξ1ξ2 and (d,t)[10,11]ξ1ξ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.2)
u1≠0v, since word t begins with 16;(3.3)
ifu1=1, then
(24)
Next we consider position(0,0) in word (d,t); suppose that (0,0)ξ1ξ2=u2, then(3.3.1)
ifu2=λ, then
(25)
Next we consider position(1,0) in word (d,t); suppose that (1,0)ξ1ξ2=u3, then(3.3.1.1)
u3≠λ, otherwise we obtain periodic word 1ω, but word t is not periodic;(3.3.1.2)
u3≠0n, since, for example, (d,t)[7,10]ξ1ξ2 and (d,t)[17,20]ξ1ξ2 will generate 102n1, but it is a contradiction with Lemma 1;(3.3.1.3)
u3≠0n1k, since, for example, (d,t)[8,9]ξ1ξ2 and (d,t)[18,19]ξ1ξ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.3.1.4)
u3≠1n, otherwise we obtain periodic word 1ω, but word t is not periodic;(3.3.1.5)
u3≠1n0k, since, for example, (d,t)[8,9]ξ1ξ2 and (d,t)[18,19]ξ1ξ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.3.2)
ifu2=0, then
(26)
Next we consider position(1,0) in word (d,t); suppose that (1,0)ξ1ξ2=u3, then(3.3.2.1)
u3≠λ, otherwise we obtain word (d,t)[0,14]ξ1ξ2=160413≠t;(3.3.2.2)
u3=0;(3.3.2.3)
u3≠0n, since, for example, (d,t)[7,10]ξ1ξ2 and (d,t)[17,20]ξ1ξ2 will generate 102n1, but it is a contradiction with Lemma 1;(3.3.2.4)
u3≠0n1k, since, for example, (d,t)[8,9]ξ1ξ2 and (d,t)[18,19]ξ1ξ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.3.2.5)
u3≠1n, otherwise we obtain word (d,t)[0,8]ξ1ξ2=160211≠t;(3.3.2.6)
u3≠1n0k, since, for example, (d,t)[8,9]ξ1ξ2 and (d,t)[18,19]ξ1ξ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.3.3)
ifu2=00, then
(27)
Next we consider position(1,0) in word (d,t); suppose that (1,0)ξ1ξ2=u3, then(3.3.3.1)
u3≠λ, otherwise we obtain word (d,t)[0,12]ξ1ξ2=16081≠t;(3.3.3.2)
u3≠0n, otherwise we obtain word (d,t)[0,12]ξ1ξ2=1604+2n+41≠t;(3.3.3.3)
u3≠0n1k, since, for example, (d,t)[8,9]ξ1ξ2 and (d,t)[18,19]ξ1ξ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.3.3.4)
u3≠1n, otherwise we obtain word (d,t)[0,8]ξ1ξ2=16041n≠t;(3.3.3.5)
u3≠1n0k, since, for example, (d,t)[8,9]ξ1ξ2 and (d,t)[18,19]ξ1ξ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.3.4)
ifu2=000, then
(28)
Next we consider position(1,0) in word (d,t); suppose that (1,0)ξ1ξ2=u3, then(3.3.4.1)
u3≠λ, otherwise we obtain word (d,t)[0,12]ξ1ξ2=160121≠t;(3.3.4.2)
u3≠0n, otherwise we obtain word (d,t)[0,12]ξ1ξ2=1606+2n+61≠t;(3.3.4.3)
u3≠0n1k, since, for example, (d,t)[8,9]ξ1ξ2 and (d,t)[18,19]ξ1ξ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.3.4.4)
u3≠1, otherwise we obtain word (d,t)[0,10]ξ1ξ2=16061203≠t;(3.3.4.5)
u3≠1n, where n>1, otherwise we obtain word (d,t)[0,10]ξ1ξ2=160612n03≠t;(3.3.4.6)
u3≠1n0k, since, for example, (d,t)[8,9]ξ1ξ2 and (d,t)[18,19]ξ1ξ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.3.5)
u2≠0n, where n>3, otherwise we obtain word (d,t)[0,7]ξ1ξ2=1602n≠t;(3.3.6)
u3≠0n1k, since, for example, (d,t)[6,7]ξ1ξ2 and (d,t)[10,11]ξ1ξ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.3.7)
u3≠1v, since word t begins with 1606;(3.4)
u1≠1n, where n>1 since word t begins with 16;(3.5)
u1≠1n0k, since, for example, (d,t)[4,5]ξ1ξ2 and (d,t)[12,13]ξ1ξ2 will generate 10k1, but it is a contradiction with Lemma 1.
(4)u≠1n, where n>1 since word t begins with 16.
(5)u≠1n0k, since, for example, (d,t)[0,1]ξ1ξ2 and (d,t)[2,3]ξ1ξ2 will generate 10k1, but it is a contradiction with Lemma 1.
From (3.3.2.2) it follows thatξ1ξ2=ξ.Lemma 5.
If(d,t)ξ1μ2=d, then ξ1μ2=ψ.Proof.
Let us consider the first position in word(d,t); suppose that (1,1)ξ1μ2=u, then
(1) ifu=λ and (0,1)ξ1μ2=u1, then(1.1)
ifu1=λ, then
(29)
Next we consider position(0,0) in word (d,t); suppose that (0,0)ξ1μ2=u2, then(1.1.1)
u2≠λ, otherwise we obtain periodic word, but word d is not periodic;(1.1.2)
u2≠0v, since word d begins with 14;(1.1.3)
u2≠1n, otherwise we obtain (d,t)[20,24]ξ1ξ2=15n>14, but it is a contradiction with d construction;(1.1.4)
u2≠1n0k, since, for example, (d,t)[6,7]ξ1μ2 and (d,t)[10,11]ξ1μ2 will generate 10k1, but it is a contradiction with Lemma 1;(1.2)
u1≠0v, since word d begins with 14;(1.3)
u1≠1n, otherwise we obtain (d,t)[12,14]ξ1μ2=13n, but it is a contradiction with d construction;(1.4)
u1≠1n0k, since, for example, (d,t)[4,5]ξ1μ2 and (d,t)[12,13]ξ1μ2 will generate 10k1, but it is a contradiction with Lemma 1;
(2)u≠0v, since word d begins with 14;
(3) ifu=1, then(3.1)
ifu1=λ, then
(30)
Next we consider position(0,0) in word (d,t); suppose that (0,0)ξ1μ2=u2, then(3.1.1)
ifu2=λ, then
(31)
Next we consider position(1,0) in word (d,t); suppose that (1,0)ξ1μ2=u3, then(3.1.1.1)
u3≠λ, otherwise we obtain periodic word, but word d is not periodic;(3.1.1.2)
u3≠0n, otherwise we obtain word (d,t)[0,33]ξ1ξ2=1406n≠d;(3.1.1.3)
u3≠1v, since word d begins with 140;(3.1.2)
ifu2=0, then
(32)
Next we consider position(1,0) in word (d,t); suppose that (1,0)ξ1μ2=u3, then(3.1.2.1)
u3≠λ, otherwise we obtain word (d,t)[0,15]ξ1ξ2=1405≠d;(3.1.2.2)
u3≠0n, otherwise we obtain word (d,t)[0,10]ξ1ξ2=140202n0≠d;(3.1.2.3)
u3≠0n1k, since, for example, (d,t)[8,9]ξ1μ2 and (d,t)[18,19]ξ1μ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.1.2.4)
u3≠1v, since word d begins with 140;(3.1.3)
ifu2=00, then
(33)
Next we consider position(1,0) in word (d,t); suppose that (1,0)ξ1μ2=u3, then(3.1.3.1)
u3≠λ, otherwise we obtain word (d,t)[0,10]ξ1ξ2=1406≠d;(3.1.3.2)
u3≠0n, otherwise we obtain word (d,t)[0,8]ξ1ξ2=140402n≠d;(3.1.3.3)
u3≠0n1k, since, for example, (d,t)[8,9]ξ1μ2 and (d,t)[18,19]ξ1μ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.1.3.4)
u3≠1v, since word d begins with 140;(3.1.4)
u2≠0n, where n>2, since word d begins with 14041;(3.1.5)
u2≠1v, since word d begins with 140;(3.2)
ifu1=0, then
(34)
Next we consider position(0,0) in word (d,t); suppose that (0,0)ξ1μ2=u2, then(3.2.1)
ifu2=λ, then
(35)
Next we consider position(1,0) in word (d,t); suppose that (1,0)ξ1μ2=u3, then(3.2.1.1)
u3≠λ, otherwise we obtain word (d,t)[0,14]ξ1ξ2=1405≠d;(3.2.1.2)
u3≠0n, otherwise we obtain word (d,t)[0,12]ξ1ξ2=1402n0≠d;(3.2.1.3)
u3≠0n1k, since, for example, (d,t)[8,9]ξ1μ2 and (d,t)[18,19]ξ1μ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.2.1.4)
u3≠1v, since word d begins with 140;(3.2.2)
ifu2=0, then
(36)
Next we consider position(1,0) in word (d,t); suppose that (1,0)ξ1μ2=u3, then(3.2.2.1)
u3≠λ, otherwise we obtain word (d,t)[0,10]ξ1ξ2=1405≠d;(3.2.2.2)
u3≠0v, since word d begins with 14041.(3.2.2.3)
u3=1;(3.2.2.4)
u3≠1n, where n>1, otherwise we obtain word (d,t)[0,9]ξ1ξ2=140412n≠d;(3.2.2.5)
u3≠0n1k, since, for example, (d,t)[8,9]ξ1μ2 and (d,t)[18,19]ξ1μ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.2.3)
u2≠0n, where n>1, otherwise we obtain word (d,t)[0,7]ξ1ξ2=1402+2n≠d;(3.2.4)
u2≠0n1k, since, for example, (d,t)[6,7]ξ1μ2 and (d,t)[10,11]ξ1μ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.2.5)
u2≠1v, since word d begins with 1404;(3.3)
ifu1=00, then
(37)
Next we consider position(0,0) in word (d,t); suppose that (0,0)ξ1μ2=u2, then(3.3.1)
ifu2=λ, then
(38)
Next we consider position(1,0) in word (d,t); suppose that (1,0)ξ1μ2=u3, then(3.3.1.1)
u3≠λ, otherwise we obtain word (d,t)[0,12]ξ1ξ2=1406≠d;(3.3.1.2)
u3≠0v, since word d begins with 14041;(3.3.1.3)
u3≠1n, otherwise we obtain word (d,t)[0,18]ξ1ξ2=140412n061n≠d;(3.3.1.4)
u3≠1n0k, since, for example, (d,t)[8,9]ξ1μ2 and (d,t)[18,19]ξ1μ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.3.2)
u2≠0v, since word d begins with 14041;(3.3.3)
u2≠1n, otherwise we obtain (d,t)[15,17]ξ1μ2=12n, but it is a contradiction with d construction;(3.3.4)
u2≠1n0k, since, for example, (d,t)[6,7]ξ1μ2 and (d,t)[10,11]ξ1μ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.4)
u1≠0n1k, since, for example, (d,t)[4,5]ξ1μ2 and (d,t)[12,13]ξ1μ2 will generate 10k1, but it is a contradiction with Lemma 1;(3.5)
u1≠1v, since word d begins with 140;
(4)u≠1n, where n>1, otherwise we obtain word (d,t)[0,3]ξ1ξ2=12n≠d;
(5)u≠1n0k, since, for example, (d,t)[0,1]ξ1μ2 and (d,t)[2,3]ξ1μ2 will generate 10k1, but it is a contradiction with Lemma 1;
From (3.2.2.3) it follows thatξ1μ2=ψ.Theorem 6.
Ifμ1, μ2, ξ1, and ξ2 are morphisms, then the diagram is not commutative. 							(39)Proof.
We have shown that the compositions of morphismsμ1μ2=μ, μ1ξ2=φ, ξ1ξ2=ξ, and ξ1μ2=ψ coincide, thus, for example, if μ maps word x letter by letter, then μ1μ2 does the same.
Next, we consider morphismsμ1, μ2, ξ1, and ξ2.
Denote that(40)0μ1=v0,(0,0)ξ1=v00,1μ1=v1,(0,1)ξ1=v01,(1,0)ξ1=v10,(1,1)ξ1=v11.
We denote by v the word which is obtained by mapping first 8 letters of word (d,t) with morphism ξ1 as follows:
(41)(d,t)[0,7]ξ1=v=v11v11v11v11v01v01v00v00.
Since ψ and ξ map (d,t) letter by letter, then ξ1μ2 and ξ1ξ2 will map the word (d,t) letter by letter from Lemmas 4 and 5 as follows:
(42)|(v)μ2|=8=|(v)ξ2|.
Next, we denote x[0,2]μ1=v1v1v0. Since μ maps x letter by letter, then by Lemma 2  μ1μ2 will map the word x letter by letter, thus
(43)|(v1v1v0)μ2|=6
therefore
(44)|v1v1v0|<|v|.
Since φ maps word x letter by letter, then μ1ξ2 will map word x letter by letter from Lemma 3 as follows:
(45)|(v1v1v0)ξ2|=9
then
(46)|v1v1v0|>|v|
which leads to a contradiction, and the diagram is not commutative. Hence two elements in such an algebraic structure do not have a supremum, since x⩾d,t, but there does not exist d∨t such that d∨t⩾d,t and x⩾d∨t. Also two elements in such an algebraic structure do not have an infimum, since t⩽x and t⩽(d,t), but there does not exist d∨t such that d∨t⩽x,  d∨t⩽(d,t) and t⩽d∨t. Thus algebraic structure 〈𝔑/≡m,⇁m〉 is not a semilattice.



---

*Source: 219291-2013-04-15.xml*