# Modularity in the Semilattice ofω-Words

Authors: Jānis Buls; Edmunds Cers
Journal: Journal of Discrete Mathematics
 (2014)

---

## Abstract

A partial ordering ofω-words can be introduced with regard to whether an ω-word can be transformed into another by a Mealy machine. It is known that the poset of ω-words that is introduced by this ordering is a join-semilattice. The width of this join-semilattice has the power of continuum while the depth is at least ℵ
0. We have created a technique for proving that power-characteristic ω-words are incomparable. We use this technique to show that this join-semilattice is not modular.


---

## Body

## 1. Introduction

Infinite words (ω-words) provide a fertile ground of research and many classes of ω-words are known. While closure properties of some classes of ω-words have been studied extensively (see, e.g., [1–3]), we are interested in the general algebraic structure of ω-words. Mealy machines are a simple model of a word transforming automaton with the beneficial property of always transforming an ω-word into an ω-word. A partial ordering is defined on ω-words by the existence of a Mealy machine transforming one word into another (we write x
⇁
y if such a machine exists). When both x
⇁
y and y
⇁
x are true, we say that x  and  y  are machine equivalent. A class 𝔎 of ω-words is called machine invariant if 𝔎 contains all possible transformations of its elements.Buls [4] has shown that machine invariant classes of ω-words form a completely distributive lattice. Belovs [5] showed that the poset of machine equivalent classes of ω-words is a join-semilattice and that the width of this join-semilattice has the power of continuum while the depth is at least ℵ
0. We show in this paper that this join-semilattice is not modular.


## 2. Preliminaries

LetA be a finite, nonempty set and A
* the free monoid generated by A. Call A analphabet, its elementsletters, and the elements of A
*  finite words. The identity element of A
* is called theempty word and is denoted by λ.Letw be a word over a finite and non-empty alphabet A. We denote the length of w by |
w
|. Similarly, the cardinality of A is denoted by |
A
|. The concatenation of the words u
,
v is denoted by u
#
v or simply u
v. Define w
0
=
λ and for all i  w
i
+
1
=
w
i
w. We say that u (resp., v) isa prefix (resp.,suffix) of u
v. Denote by Pref
(
w
) and Suff
(
w
) the respective sets of prefixes and suffixes of w. Let k
,
n
¯ denote the set of integers {
k
,
k
+
1
,
k
+
2
,
…
,
n
}:
(1)
ℕ
=
{
0,1
,
2
,
…
,
n
,
…
}
.
Call a total map x
:
ℕ
→
A an (indexed) ω
-word of the alphabet A. For any i
≥
0 define x
i
=
x
(
i
) and write
(2)
x
=
(
x
i
)
=
x
0
x
1
⋯
x
n
⋯
x
(
k
+
1
,
n
+
1
)
=
x
[
k
,
n
+
1
)
=
x
[
k
,
n
]
=
x
k
x
k
+
1
…
x
n
-
1
x
n
.
The set of all ω-words over A is denoted by A
ω. We say that y is aprefix of x, if there exists an integer k such that y
=
x
[
0
,
k
]. An ω-word x is calledultimately periodic if there exist integers p
≥
0 and T
>
0 such that x
i
=
x
i
+
T for all i
≥
p. In this case p is calledpreperiod and T aperiod of x. An ultimately periodic ω-word with a preperiod of zero is calledperiodic. We say a finite word w is(ultimately) periodic if it is a prefix of some (ultimately) periodic ω-word. We recall the important periodicity theorem due to Fine and Wilf [6].Theorem 1.
Letw be a word having periods p and q and denote by g
c
d
(
p
,
q
) the greatest common divisor of p and q. If |
w
|
≥
p
+
q
-
g
c
d
(
p
,
q
), then w has also the period g
c
d
(
p
,
q
).Corollary 2.
Letu
v and v
w be words having periods, respectively, p and q. If |
v
|
≥
p
+
q
-
g
c
d
(
p
,
q
), then u
v
w has the period g
c
d
(
p
,
q
).This is almost folklore in combinatorics on words. Nevertheless, for the sake of completeness, we will give the proof of this corollary.Proof.
Since|
v
|
≥
p
+
q
-
gcd
(
p
,
q
), then (Theorem 1) v has the period gcd
(
p
,
q
).
(i) At first we will prove by induction on|
u
| that u
v has the period gcd
(
p
,
q
). Let v
=
v
1
v
2
⋯
v
k. If |
u
|
=
1, then u
=
v
0 for some letter. Since the period of u
v is p then v
0
=
v
p.
Notice thatgcd
(
p
,
q
) divides p. Since the period of v is gcd
(
p
,
q
), then v
p
=
v
gcd
(
p
,
q
). Hence, v
0
=
v
gcd
(
p
,
q
).
(ii) If|
u
|
>
1, then u can be represented as concatenation a
u
′
=
u, where |
u
′
|
+
1
=
|
u
|. By assumption the period of u
′
v is gcd
(
p
,
q
). Now from (i) follows that the period of a
u
′
v is gcd
(
p
,
q
) too. We have completed the inductive step.
Now we shall prove by induction on|
w
| that v
w has the period gcd
(
p
,
q
).
(iii) If|
w
|
=
1, then w
=
v
k
+
1 for some letter. Since the period of v
w is q, then v
k
+
1
-
q
=
v
k
+
1. Notice
(3)
k
+
1
-
gcd
(
p
,
q
)
≡
k
+
1
-
q
,
(
mod
⁡
gcd
(
p
,
q
)
)
.
Hence, v
k
+
1
-
gcd
(
p
,
q
)
=
v
k
+
1
-
q
=
v
k
+
1.
(iv) If|
w
|
>
1, then w can be represented as concatenation w
′
b
=
w, where |
w
′
|
+
1
=
|
w
|. By assumption the period of v
w
′ is gcd
(
p
,
q
). Now from (iii) follows that the period of v
w
′
b is gcd
(
p
,
q
) too. We have completed the inductive step.A 3-sorted algebraV
=
〈
Q
,
A
,
B
;
q
0
,
∘
,
*
〉 is called aninitial Mealy machine if Q, A, B are finite, nonempty sets, called theset of states, theinput alphabet, and theoutput alphabet, respectively, q
0
∈
Q is called theinitial state, ∘
:
Q
×
A
→
Q is a total function called thetransition function, and *
:
Q
×
A
→
B is a total surjective function called theoutput function. We write 〈
Q
,
A
,
B
;
∘
,
*
〉 or even 〈
Q
,
A
,
B
;
q
0
〉 if there is no danger of confusion. The mappings ∘ and * are extended to Q
×
A
* by defining
(4)
q
∘
λ
=
q
,
q
∘
(
u
a
)
=
(
q
∘
u
)
∘
a
,
q
*
λ
=
λ
,
q
*
(
u
a
)
=
(
q
*
u
)
#
(
(
q
∘
u
)
*
a
)
,
for all q
∈
Q, (
u
,
a
)
∈
A
*
×
A. Henceforth, we shall omit parentheses if there is no danger of confusion. So, for example, we will write q
∘
u
*
a instead of (
q
∘
u
)
*
a. Let (
x
,
y
)
∈
A
ω
×
B
ω. If for some Mealy machine V: for all n  y
[
0
,
n
]
=
q
0
*
x
[
0
,
n
], we say that V
transforms
x
to
y and write y
=
q
0
*
x or x
⇁
V
y. We write x
⇁
y if there exists V such that x
⇁
V
y; otherwise, we write x
⇁
y. We write x
⇌
y if x
⇁
y and y
⇁
x and say that x and y are machine equivalent.Given the integersa
1
,
a
2
,
…
,
a
n, let lcm
(
a
1
,
a
2
,
…
,
a
n
) denote the least common multiple of a
1
,
a
2
,
…
,
a
n. Given a number x
∈
ℝ, denote by ⌊
x
⌋ the greatest integer less than or equal to x and by ⌈
x
⌉ the least integer greater than or equal to x.


## 3. Machine Transformations of Power-Characteristicω-Words

Definition 3.
We will call theω-word x
ζ
∈
{
0,1
}
ω the characteristic word of the power ζ if
(5)
x
ζ
(
n
)
=
{
1
,
if
∃
k
∈
ℕ
,
n
=
k
ζ
,
0
,
otherwise
.
For example, x
2
=
110010000100
… is the characteristic word of the squares.Convention. Henceforth, we assume that ζ
≥
2 and it is a natural number.More generally, letf
:
ℕ
→
ℕ be any total increasing function; then
(6)
x
f
(
n
)
=
{
1
,
if
∃
k
∈
ℕ
,
n
=
f
(
k
)
,
0
,
otherwise
.
Let V
=
〈
Q
,
{
0,1
}
,
{
0,1
}
;
∘
,
*
〉 be a Mealy machine, where
(7)
Q
=
{
q
1
′
,
q
2
′
,
…
,
q
b
′
}
.
Applying the pigeonhole principle, we can state that for every q
∈
Q there is a least integer i
≥
0 such that q
∘
0
i
=
q
∘
0
j for some i
<
j. The integer i is called theindex of q, and j
-
i is called theperiod of q. We can visualize this as the diagrams (see Figure 1).Figure 1
Indices and periods.Claim 1.
Ifa
s is the index and c
s is the period of q
s
′,
(8)
a
s
≤
m
1
<
m
2
,
m
1
≡
m
2
(
mod
⁡
c
s
)
,
then
(9)
q
s
′
∘
0
m
1
=
q
s
′
∘
0
m
2
.Claim 2.
Ifmax
⁡
(
a
1
,
a
2
,
…
,
a
b
)
≤
m
1
<
m
2 and m
1
≡
m
2
(
mod
⁡
m
), where
(10)
m
=
lcm
(
c
1
,
c
2
,
…
,
c
b
)
,
then
(11)
∀
q
∈
Q
,
q
∘
1
0
m
1
=
q
∘
1
0
m
2
.
Let α
(
X
) be an integer polynomial; that is, α
(
X
)
∈
ℤ
[
X
]. The following theorem is known from elementary number theory.Theorem 4.
Ifi
≡
j
(
mod
⁡
m
), then α
(
i
)
≡
α
(
j
)
(
mod
⁡
m
).If we takeα
k
=
(
k
+
1
)
ζ
-
k
ζ
-
1, then we can express
(12)
x
ζ
=
11
0
α
1
1
0
α
2
⋯
1
0
α
k
⋯
=
u
0
u
1
⋯
u
k
⋯
,
where u
k
=
1
0
α
k. Hence, x
ζ
[
0
,
k
ζ
)
=
u
0
u
1
⋯
u
k
-
1.Corollary 5.
Ifi
≡
j
(
mod
⁡
m
), then α
i
≡
α
j
(
mod
⁡
m
).Let(13)
w
0
=
u
0
,
w
k
+
1
=
w
k
u
k
+
1
.
Then
(14)
x
ζ
[
0
,
k
ζ
)
=
u
0
u
1
⋯
u
k
-
1
=
w
k
-
1
.
Let q
∈
Q. We define a sequence
(15)
q
0
,
q
1
,
…
,
q
k
,
…
,
where q
k
=
q
∘
w
k.Corollary 6.
The sequenceq
0
,
q
1
,
…
,
q
k
,
… is ultimately periodic.Proof.
Letm
=
lcm
(
c
1
,
c
2
,
…
,
c
b
). There exists n such that
(16)
|
u
m
n
|
>
max
⁡
(
a
1
,
a
2
,
…
,
a
b
)
.
Now consider the sequence q
m
n
,
q
m
(
n
+
1
)
,
…
,
q
m
(
n
+
b
). Since |
0
,
b
¯
|
=
b
+
1
>
|
Q
|, then—by the pigeonhole principle—there must exist two equal states
(17)
q
m
(
n
+
i
)
=
q
m
(
n
+
j
)
,
with
0
≤
i
<
j
≤
b
.
Hence
(18)
q
m
(
n
+
i
)
+
1
=
Claim
2
q
m
(
n
+
i
)
∘
u
m
(
n
+
i
)
+
1
=
q
m
(
n
+
j
)
∘
u
m
(
n
+
i
)
+
1
=
Claim
2
q
m
(
n
+
j
)
∘
u
m
(
n
+
j
)
+
1
=
q
m
(
n
+
j
)
+
1
.
The rest follows by induction.The following lemma is very easy, but it turns out to be useful.Lemma 7.
LetV
=
〈
Q
,
A
,
B
;
q
0
〉 be a Mealy machine. If |
Q
|
=
m and q
0
*
0
s
=
w, then there exists ϰ such that
(19)
w
=
u
v
ϰ
v
˙
,
where
|
u
|
+
|
v
|
≤
m
and
v
˙
∈
Pref
(
v
)
.Proof.
(i) Ifs
≤
m, then |
w
|
=
|
0
s
|
=
s
≤
m, and we can choose u
=
w, v
=
v
˙
=
λ.
(ii) Lets
>
m and q
0
,
q
1
,
…
,
q
m states, where
(20)
∀
i
∈
0
,
m
¯
q
i
=
q
0
∘
0
i
.
Since |
0
,
m
¯
|
=
m
+
1
>
|
Q
|, then—by the pigeonhole principle—there must exist two equal states; namely, there exist i and j, 0
≤
i
<
j
≤
m, such that
(21)
q
i
=
q
j
.
Putting
(22)
u
=
q
0
*
0
i
,
v
=
q
i
*
0
j
-
i
,
ϰ
=
⌊
s
-
i
j
-
i
⌋
,
v
˙
=
q
i
*
0
s
-
i
-
ϰ
(
j
-
i
)
,
then |
u
|
+
|
v
|
=
|
0
i
|
+
|
0
j
-
i
|
=
i
+
(
j
-
i
)
=
j
≤
m and w
=
u
v
ϰ
v
˙.Proposition 8.
Ifx
f
⇁
y, x
ζ
⇁
y and
(23)
∀
ϰ
∃
a
k
f
(
k
)
≤
a
ζ
<
(
a
+
ϰ
)
ζ
≤
f
(
k
+
1
)
,
then y is ultimately periodic.Proof .
Sincex
ζ
⇁
y and x
f
⇁
y, there exist Mealy machines
(24)
V
=
〈
Q
,
{
0,1
}
,
B
;
q
,
∘
,
*
〉
,
V
′
=
〈
Q
′
,
{
0,1
}
,
B
;
q
′
,
∘
′
,
*
′
〉
such that x
ζ
⇁
V
y and x
f
⇁
V
′
y.
(i) First, we expressx
ζ
=
u
0
u
1
⋯
u
n
⋯ with
(25)
u
n
=
1
0
α
n
,
α
n
=
(
n
+
1
)
ζ
-
n
ζ
-
1
,
and look at the sequence q
0
,
q
1
,
…
,
q
n
,
…, where
(26)
q
n
=
q
∘
(
u
0
u
1
⋯
u
n
)
.
We have shown (Corollary 6) that the sequence q
0
,
q
1
,
…
,
q
n
,
… is ultimately periodic. Assume its period is T and the preperiod p.
(ii) By assumption (see (23)) we can choose integers k and a such that
(27)
f
(
k
)
≤
a
ζ
<
(
a
+
T
+
1
)
ζ
≤
f
(
k
+
1
)
and, moreover, a
>
p
+
7 and (
a
+
1
)
ζ
-
a
ζ
>
3
·
max
⁡
(
|
Q
|
,
|
Q
′
|
)
+
7. Now, x
f
(
f
(
k
)
,
f
(
k
+
1
)
) is a word of the form 0
d, and thus (by Lemma 7)
(28)
y
(
f
(
k
)
,
f
(
k
+
1
)
)
must be ultimately periodic with both its period and preperiod not greater than |
Q
′
|. We denote this preperiod by p
′ and the least period by T
′. Since
(29)
p
′
≤
|
Q
′
|
<
(
a
+
1
)
ζ
-
a
ζ
-
7
,
then y
[
(
a
+
1
)
ζ
,
(
a
+
1
+
T
)
ζ
) is periodic with the period T
′. Notice that
(30)
y
[
(
a
+
i
)
ζ
,
(
a
+
i
+
1
)
ζ
)
=
q
a
+
i
-
1
*
x
ζ
[
(
a
+
i
)
ζ
,
(
a
+
i
+
1
)
ζ
)
=
q
a
+
i
-
1
*
1
0
α
a
+
i
and that the sequence of states q
a
,
q
a
+
1
,
q
a
+
2
,
…
,
q
a
+
T
,
… is also periodic. Therefore
(31)
y
[
(
a
+
i
+
T
)
ζ
,
(
a
+
i
+
1
+
T
)
ζ
)
=
q
a
+
i
-
1
+
T
*
x
ζ
[
(
a
+
i
+
T
)
ζ
,
(
a
+
i
+
1
+
T
)
ζ
)
=
q
a
+
i
-
1
+
T
*
1
0
α
a
+
i
+
T
=
q
a
+
i
-
1
*
1
0
α
a
+
i
+
T
=
u
˙
v
˙
w
˙
,
where |
u
˙
|
=
|
v
˙
|
=
max
⁡
(
|
Q
|
,
|
Q
′
|
). So we have two periodic words u
˙
v
˙ and v
˙
w
˙. Hence by Corollary 2
(32)
y
[
(
a
+
i
+
T
)
ζ
,
(
a
+
i
+
1
+
T
)
ζ
)
is periodic with period T
′. Therefore we can conclude that y
[
(
a
+
i
)
ζ
,
(
a
+
i
+
1
)
ζ
) is periodic with period T
′ for all i
>
0; besides, T
′ is the least period for all i
>
0.
(iii) LetX
>
a and μ
=
lcm
(
T
,
T
′
). Then
(33)
(
X
+
μ
)
ζ
-
X
ζ
=
∑
j
=
0
ζ
(
ζ
j
)
μ
j
X
ζ
-
j
-
X
ζ
=
μ
∑
j
=
1
ζ
(
ζ
j
)
μ
j
-
1
X
ζ
-
j
=
μ
P
(
X
)
,
where
(34)
P
(
X
)
=
∑
j
=
1
ζ
(
ζ
j
)
μ
j
-
1
X
ζ
-
j
.
We have shown in (ii) that y
[
X
ζ
,
(
X
+
1
)
ζ
) is periodic. Therefore there is a v such that
(35)
y
[
X
ζ
,
(
X
+
1
)
ζ
)
=
v
r
v
′
,
where |
v
|
=
T
′ and v
′
∈
Pref
(
v
). Since T divides μ, then q
X
-
1
=
q
X
-
1
+
μ. But then
(36)
y
[
(
X
+
μ
)
ζ
,
(
X
+
μ
+
1
)
ζ
)
=
q
X
+
μ
-
1
*
x
ζ
[
(
X
+
μ
)
ζ
,
(
X
+
μ
+
1
)
ζ
)
=
q
X
-
1
*
x
ζ
[
(
X
+
μ
)
ζ
,
(
X
+
μ
+
1
)
ζ
)
=
q
X
-
1
*
1
0
α
X
+
μ
=
v
r
′
v
′′
,
for some number r
′ and v
′′
∈
Pref
(
v
). It follows from (33) that
(37)
(
X
+
μ
+
1
)
ζ
-
(
X
+
μ
)
ζ
≡
(
X
+
1
)
ζ
-
X
ζ
(
mod
⁡
T
′
)
and therefore v
′
=
v
′′.
(iv) Finally, we can select integersk
˘, a
˘ such that k
<
k
˘ and
(38)
f
(
k
˘
)
≤
a
˘
ζ
<
(
a
˘
+
μ
+
1
)
ζ
≤
f
(
k
˘
+
1
)
.
Now we repeat the proof from (ii). So we can conclude that there is the least period T
′′
≤
|
Q
′
| of the word y
[
(
a
˘
+
1
)
ζ
,
(
a
˘
+
1
+
μ
)
ζ
). A period of
(39)
y
[
(
a
˘
+
1
)
ζ
,
(
a
˘
+
2
)
ζ
)
is T
′ too. Hence (Theorem 1) T
′′
=
T
′. Denote y
[
(
a
˘
+
1
)
ζ
,
(
a
˘
+
1
)
ζ
+
T
′
)
=
u. Since (from formula (33))
(40)
(
a
˘
+
1
+
μ
)
ζ
-
(
a
˘
+
1
)
ζ
≡
0
(
mod
⁡
T
′
)
,
there is an integer s such that y
[
(
a
˘
+
1
)
ζ
,
(
a
˘
+
1
+
μ
)
ζ
)
=
u
s. As it was shown in (iii) we can choose s
1
′
,
s
2
′ such that
(41)
y
[
(
a
˘
+
1
)
ζ
,
(
a
˘
+
2
)
ζ
)
=
u
s
1
′
u
′
,
y
[
(
a
˘
+
1
+
μ
)
ζ
,
(
a
˘
+
2
+
μ
)
ζ
)
=
u
s
2
′
u
′
.
But then y
[
(
a
˘
+
1
)
ζ
,
(
a
˘
+
2
+
μ
)
ζ
)
=
u
s
u
s
′
2
u
′, which means that
(42)
y
[
(
a
˘
+
1
)
ζ
,
(
a
˘
+
2
+
μ
)
ζ
)
is periodic with the period T
′. Now suppose that y
[
(
a
˘
+
1
)
ζ
,
(
a
˘
+
n
)
ζ
)
=
u
σ
u
˘, where n
>
μ
+
1 and u
˘
∈
Pref
(
u
). Then there exists such v
˘
∈
Suff
(
u
) that u
˘
v
˘
=
u. From (see formula (33)) (
a
˘
+
n
)
ζ
-
(
a
˘
+
n
-
μ
)
ζ
≡
0
(
mod
⁡
T
)
′, we can conclude that
(43)
v
˘
∈
Pref
(
y
[
(
a
˘
+
n
-
μ
)
ζ
,
(
a
˘
+
n
-
μ
+
1
)
ζ
)
)
.
It follows from what we have shown in (iii) that there are σ
1
,
σ
2 such that(44)
y
[
(
a
˘
+
n
-
μ
)
ζ
,
(
a
˘
+
n
-
μ
+
1
)
ζ
)
=
v
σ
1
v
′
,
y
[
(
a
˘
+
n
)
ζ
,
(
a
˘
+
n
+
1
)
ζ
)
=
v
σ
2
v
′
with |
v
|
=
T
′ and v
′
∈
Pref
(
v
). But then v
=
v
˘
u
˘ and
(45)
y
[
(
a
˘
+
1
)
ζ
,
(
a
˘
+
n
+
1
)
ζ
)
=
u
σ
u
˘
v
σ
2
v
′
=
u
σ
u
˘
(
v
˘
u
˘
)
σ
2
v
′
=
u
σ
(
u
˘
v
˘
)
σ
2
u
˘
v
′
=
u
σ
+
σ
2
u
˘
v
′
.
This means that y
[
(
a
˘
+
1
)
ζ
,
(
a
˘
+
n
+
1
)
ζ
) is periodic with period T
′. Now, by induction, we have y
[
(
a
˘
+
1
)
ζ
,
(
a
˘
+
i
)
ζ
] is periodic with the period T
′ for any i
>
1. Hence, y is ultimately periodic.


## 4. Modularity in the Semilattice ofω-Words

Our main object of investigation is the machine poset of infinite words. In order to avoid some set-theoretical problems, we make some assumptions. Let us take the set𝔑
=
⋃
k
=
0
∞
(
0
,
k
¯
)
ω. We shall assume that the states of the involved Mealy machines as well as their input and output alphabets all are from the set ℕ. If another input or output alphabet A is used, we assume that there exists a bijection β
:
A
→
0
,
|
A
|
-
1
¯ and that this bijection is applied to the input or output word, respectively.We suppose that the reader is familiar with the basic notions of ordered sets [7]. If ⇁ is used as an algebraic relation on 𝔑, then the algebraic structure 〈
𝔑
,
⇁
〉 defines a preorder [5], while the quotient set 𝔑
~
=
𝔑
/
⇌ becomes the ordered set 〈
𝔑
,
⇁
〉. It has been shown that this poset 𝔑
~ is a join-semilattice [5], where the join [
(
x
i
)
]
∨
[
(
y
i
)
]
=
[
(
x
i
,
y
i
)
].Definition 9.
A join-semilattice〈
D
,
≤
〉 is distributive when
(46)
∀
x
a
b
(
x
≤
a
∨
b
⟹
∃
a
′
b
′
(
a
′

≤
a
&
b
′

≤
b
&
x
=
a
′
∨
b
′
)
)
.
A join-semilattice 〈
D
,
≤
〉 is modular when
(47)
∀
x
a
b
(
a
≤
x
≤
a
∨
b
⟹
∃
b
′
≤
b
(
x
=
a
∨
b
′
)
)
.Theorem 10.
The join-semilattice〈
𝔑
~
,
⇁
〉 is not modular.Proof.
We start by showing thatx
2
∨
x
4
⇁
x
′, where
(48)
x
′
(
n
)
=
{
1
,
if
∃
k
∈
ℕ
,
n
=
k
4
,
1
,
if
∃
k
∈
ℕ
,
n
=
(
k
2
+
1
)
2
,
0
,
otherwise
.
By definition, (
x
2
∨
x
4
)
(
n
)
=
(
x
2
(
n
)
,
x
4
(
n
)
). Define the Mealy machine
(49)
V
=
〈
{
q
0
,
q
1
,
q
2
}
,
{
(
0
0
)
,
(
0
1
)
,
(
1
0
)
,
(
1
1
)
}
,
{
0,1
}
;
q
0
,
∘
,
*
〉
by
(50)
q
1
=
q
0
∘
(
0
0
)
=
q
0
∘
(
0
1
)
=
q
0
∘
(
1
0
)
=
q
0
∘
(
1
1
)
=
q
1
∘
(
0
0
)
=
q
1
∘
(
0
1
)
=
q
1
∘
(
1
0
)
=
q
2
∘
(
1
0
)
,
q
2
=
q
1
∘
(
1
1
)
=
q
2
∘
(
0
0
)
=
q
2
∘
(
0
1
)
=
q
2
∘
(
1
1
)
,
0
=
q
1
*
(
0
0
)
=
q
1
*
(
0
1
)
=
q
1
*
(
1
0
)
=
q
2
*
(
0
0
)
=
q
2
*
(
0
1
)
=
q
2
*
(
1
1
)
,
1
=
q
0
*
(
0
0
)
=
q
0
*
(
0
1
)
=
q
0
*
(
1
0
)
=
q
0
*
(
1
1
)
=
q
1
*
(
1
1
)
=
q
2
*
(
1
0
)
.
We illustrate this by the diagram in Figure 2. It follows straightforwardly from the construction that x
2
∨
x
4
⇁
V
x
′
⇁
x
4. Now suppose that there exists y such that x
2
⇁
y and x
′
⇌
x
4
∨
y. But then x
′
⇁
y too. Notice that x
′
=
x
g for
(51)
g
(
k
)
=
{
0
,
if
k
=
0
,
(
k
+
1
)
4
16
,
if
k
is
odd
,
(
k
2
4
+
1
)
2
,
if
k
is
even
.
Hence, by Proposition 8
y is ultimately periodic. But if so, then x
4
∨
y
⇌
x
4. However this is a contradiction because then x
′
⇌
x
4.Figure 2
x
2
∨
x
4
⇁
V
x
′.Corollary 11 (see [8]).
The join-semilattice〈
𝔑
~
,
⇁
〉 is not distributive.We recall that every distributive join-semilattice is modular.


## 5. Conclusion

We agree that it is not sufficient to state that𝔑
~ is very complicated as it was done in Wikipedia writing review about Turing degrees [9]. Nevertheless it is clear that 𝔑
~ is not modular and that there is no classical algebraic notion that describes such semilattice axiomatically at this moment. So we have challenge to extract axioms for semilattice 𝔑
~.



---

*Source: 891760-2014-05-15.xml*