数理解析研究所講究録 1222 巻 2001 年 90-97

90

On Some Trices
Kiyomitsu Horiuchi(堀内 清光)Faculty of Science, Konan University(甲南大学理学部)
Okamoto, Higashinada, Kobe 658-8501, Japan1

Motivation and Introduction

Asemilattice (S,$*)$ is aset S with asingle binary, idempotent, commutative and. Under the relation defined byassociative$\mathrm{o}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}*$$a\leq_{*}b\Leftrightarrow a*b=b$,(1)

any semilattice $(S, *)$ is apartially ordered set. Let be alattice with two
operationsand. Then, $(L, \vee)$ andare semilattices. From(1), we can construct two ordered sets
, respectively
and$a\vee b=b$ and). The dual ofis. That is, the order
is nothing but the reverse of the order
The reason why
the reverse order is that lattices satisfy the absorption laws:$L$$(S, \leq_{\mathrm{s}})$$\vee(\mathrm{j}\mathrm{o}\mathrm{i}\mathrm{n})$$(L, \wedge)$$\wedge(\mathrm{m}\mathrm{e}\mathrm{e}\mathrm{t})$$(L, \leq_{\wedge})$$(L, \leq_{\mathrm{v}})$$a\leq_{\wedge}b\Leftrightarrow a\wedge b=b$$(L, \leq_{\mathrm{v}})$$(L, \leq_{\wedge})$$\vee \mathrm{a}\mathrm{n}\mathrm{d}$$\leq\wedge\cdot$$\leq_{\mathrm{v}}$$a\vee(a\wedge b)=a$,$a\wedge(a\vee b)=a$$(a\leq_{\mathrm{v}}b\Leftrightarrow$(absorption).

$\wedge \mathrm{i}\mathrm{n}\mathrm{t}\mathrm{r}\mathrm{o}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{e}$(2)Suppose that there is an object with arope on aline, and that we are able to pull
the rope from the right (see Figure 1). Then, we can move the object to the right
direction, but not to the left direction. This situation is considered to be irreversible.

Figure 1: one dimensional irreversible
Next, see Figure 2. By pullng the rope from either right or left directions, we canmove the object to any point on the Hue. This situation is considered to be reversible.
Asemlattice is aset having one order, i.e. one direction, like in Figure 1. Alattice

91

Figure 2: one dimensional reversible
is aset having two orders, i.e. two directions, like in Figure 2. Any object on theline can be moved to another arbitrary point on the line by pulling the object to thepositive or negative directions.

Figure 3: two dimensional reversible
Suppose that there is an object not on aHue but in aplane (two dimensional
Euclidian space). If we want to move the object to an arbitrary point in the plane,
it is sufficient to have three “suitable” directions to
the object, as shown in
Figure 3.
If the three directions are not “suitabl\"e, we cannot move the original object toan arbitrarily chosen target point. Movements in three directions are not necessarily
restricted to the two dimensional plane. Consider that alattice corresponds to theone dimensional reversible case (Figure 2). What systems with three binary operations (semilattice) correspond to the two dimensional reversible cases (Figure 3)?
$\mathrm{p}\mathrm{u}\mathrm{U}$For anonempty set and apositive integer, letbe an algebrawith binary operations, and $(A, *:)$ be asemilattice for every $i\in\{1,2, \ldots, n\}$ .
Then,is called a -semilattice. We will deal mainly with triple
semilattice, (that is, $n=3$ ). We denote each order on by $a\leq_{:}b\Leftrightarrow a*:b=b$ , respectively. Let
be the symmetric group on. An algebra
has the -roundabout absorption laws if it satisfies the following $n!$ identities:$A$$(A, *_{1}, *_{2}, \ldots, *_{n})$

$n$

$n$

$(A, *_{1}, *_{2}, \ldots, *_{n})$$\mathrm{n}$$A$$S_{n}$$(A, *_{1}, *_{2}, \ldots, *_{n})$$\{1, 2, \ldots n\}$$\mathrm{n}$.

(3)$((((a*_{\sigma(1)}b)*_{\sigma(2)}b)*_{\sigma(3)}b)\ldots*_{\sigma(n)}b)=b$

for all , $b\in A$ and for all. Of cause, the 2-roundabout absorption laws is theabsorption laws. An algebra
which satisfies the 2-roundabout absorption
laws is alattice. The operations
and are denoted by.
An algebra
which satisfies the -roundabout absorption laws is said to
be atrice. To simplify explanation, we often omit “3” of “3-roundabout absorption$\sigma\in S_{n}$$a$$(A, *_{1}, *_{2})$$*_{1}$$(A, *_{1}, *_{2}, *_{3})$$\vee \mathrm{a}\mathrm{n}\mathrm{d}$$*_{2}$$\theta$$\wedge$92
laws.” The operations , ’2 and $3 will be denoted
can easily check that alattice L has folowing properties:$\mathrm{b}\mathrm{y}/\ovalbox{\tt\small REJECT}_{1,\mathrm{a}_{2}}$$1_{\mathrm{t}}$$\forall a$, b $\in L\exists c\in L$ such that ab $\in L\exists c\in L$ such that a$\forall a,$

Proposition 1Let an algebralaws. For every $a,b\in A$ and for evry

$a\leq_{\sigma(1)}c_{1}\leq_{\sigma(2)}c_{2}\leq_{\sigma(3)}$...

$\mathrm{t}_{3}$. Now, we$\leq {}_{}\mathrm{C}\leq_{\wedge}b$$\leq {}_{\wedge}\mathrm{C}\leq_{\mathrm{v}}b$.

have the -roundabout absorption, there exists , , $c_{n-1}\in A$ such that$(A, *_{1}, *_{2}, \ldots, *_{n})$$\sigma\in S\mathrm{n}$and$\mathrm{n}$$c_{1}$$\ldots$$\leq_{\sigma(n-1)}c_{n-1}\leq_{\sigma(n)}b$(4).

is attainable if (4) is true for every , $b\in A$ . The
We say that“attainable” of lattice corresponds to the notion of reversiblity in the case of one
dimension (Figure 2). We can consider that the “attainablity” of trice corresponds
to the case of Figure 3, that is, the two dimensional reversible cases. The “trice” isanotion to correspond to “lattice.”$a$$(A, *_{1}, *_{2}, \ldots, *_{n})$2Construction of trice
If we introduce three orders into aset under the condition that aU two elements on
it have aleast upper bound for each order, then we can construct triple-semilattice.
However it is difficult to examine whether it is trice. Next question is naturally.
be a -semilattice. By adding any operations,
Question 1Let (A,is it possible to materialize the roundabout absorption laws?
$*_{1},*_{2},$\ldots , $*_{n})$$\mathrm{n}$We consider about some fundamental cases of the above question.

From lattice to trice

2,1

Question 2Let (L,is atrice, exists?

$\vee, \wedge)$

be lattice. What kind$\mathrm{o}\mathrm{f}\mathrm{o}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}*$, so that (L,$\vee, \wedge, *)$is atrice. This
, then the algebra
equal toIf thetype -semilattice is called stammered semilattice. It is being studied well (see [4]).
is atrice.
Let $(L,*)$ be any lnearly orderd set, then the algebra
And we can always make atrice by adding another type operation to alattice.
$\vee \mathrm{o}\mathrm{r}$$\mathrm{o}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}*\mathrm{i}\mathrm{s}$$\wedge$$(L, \vee, \wedge, *)$$\mathrm{n}$$(L, \vee, \wedge, *)$has five elements: , , , 0, 1 and $a\wedge b=$
Example 1The lattice$a\wedge c=b\wedge c=0$ ,) be asemilattice which$a\vee b=a\vee c=b\vee c=1$ .
Let (Abe asemilattice which diagram is Figure 4-(b).
diagram is Figure 4-(a), let
be asemilattice which diagram is Figure 4-(c). Then, the algebra
And letare trice.
) and, (M3,$(M_{3},\vee,\wedge)$$a$$*_{1}$$,$$(M_{3},*_{2})$$(M_{3}, *_{2})$$(M_{3},\vee,\wedge, *_{1})$$\mathrm{V},$$\wedge,$$*_{2}$$(M_{3},\vee, \wedge, 3)$

$b$

$c$

93

$c$

Figure 4: trice on

2.2$M_{3}$

From 2-semilattice to trice

Definition 1Letan algebra
Every lattice (L,cable 2-semilattice.

$\vee, \wedge)$

be a2-semilattice. The
is tricable whenis atrice for some semilattice operation $3 on .

$(S, *_{1}, *_{2})$$(S, *_{1}, *_{2}, *_{3})$$(S, *_{1}, *_{2})$$S$is tricable 2-semilattice. We will show another interested tri-

The two delegates on linearly ordered set
Suppose that $X$ is alinearly ordered set and } $X|\geq 2$ . Let $X(2)$ be the set of all two
points subset of $X$ , that is,$X(2)=\{\{x_{1},x_{2}\}|x_{1},x_{2}\in X\mathrm{s}.\mathrm{t}.

Suppose thatof

, $\{b_{1},b_{2}\}\in X(2)$ . Let. And take$\{a_{1}, a_{2}\}$$\{a_{1}, a_{2}, b_{1}, b_{2}\}$$c_{2}$$\mathrm{a}_{2}\vee b_{1}$$c_{1}=\{$$a_{1}\vee b_{2}$$a_{1}\vee b_{1}$Thenis the second largest member ofoperation on $X(2)$ by$c_{1}$

be

if
if
if

x_{1}<x_{2}\}$

V62. This$c_{2}$.

is the largest member$a_{2}<b_{2}$$b_{2}<a_{2}$$a_{2}=b_{2}$$\{a_{1}, a_{2}, b_{1}, b_{2}\}$.

We define the binary$\mathrm{u}$$\{a_{1}, a_{2}\}\square$$\{b_{1}, b_{2}\}=\{c_{1}, c_{2}\}$.

Clearly, $(X(2), \square )$ is asemilattice. For example, let $X$ be aset of students, andwe want to select two students as deledats to attend aconvention. Some membersof committee recommend
and . The other members of committee recommend
and . Then, we may selectandFrom , a2,andaccording to thismethod. Hence, we called this operation two delegates.
Next, we define the dual operation of U. Let
be the. Thisbe thesmallest member of. And take$a_{1}$$b_{1}$$b_{2}$$a_{2}$$c_{1}$$a_{1}$$c_{2}$$d_{1}$$\{a_{1}, a_{2}, b_{1}, b_{2}\}$$a_{2}\wedge b_{1}$$ifa_{1}<b_{1}$$d_{2}=\{$ $a_{1}\wedge b_{2}ifb_{1}<a_{1}$$a_{2}\Lambda b_{2}$if$a_{1}=b_{1}$$b_{1}$$b_{2}$$a_{1}\wedge b_{1}$$d_{1}$

94
Then,be the second smallest member ofoperation n on $X(2)$ by$d_{2}$$\{a_{1_{\rangle}}a_{2_{\rangle}}b_{1_{\rangle}}/_{2}\ovalbox{\tt\small REJECT}\}$$\{a_{1},a_{2}\}\cap\{b_{1},b_{2}\}=\{d_{1},d_{2}\}$This $(X(2), \cap)$ is also asemilattice. The
2-semilattice. Now we define another$(X(2), \mathrm{U}, \cap)$. We define the binary.

is not alattice. But it is tricableby$\mathrm{o}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}*\mathrm{o}\mathrm{n}X(2)$$\{a_{1},a_{2}\}*\{b_{1},b_{2}\}=\{d_{1}, c_{2}\}$This$*\mathrm{i}\mathrm{s}$amongis atrice.

.

the operation which chose the smallest member and the largest member. Clearly, $(X(2), *)$ is asemilattice. The algebra$(X(2), \mathrm{u}, \cap, *)$$\{a_{1},a_{2}, b_{1}, b_{2}\}$

Example 2Let $X$ be the four points linearly ordered set {1, 2, 3, 4}. We denotethe two points subset {1,2}, {1, 3}, {1, 4}, {2, 3}, {2, 4} and {3, 4} by , , , ,is aand $f$ . Then, the set $X(2)$ is $\{a,b, c,d,e, f\}$ (see Figure 5). This
trice.
$b$

$a$

$c$

$d$

$e$

$(X(2),\mathrm{u}, \mathrm{n}, *)$the order from u

the order from$\cap$

the order ffom

$*$

$c$

Figure 5: Example 2
The three delegates on linearly ordered set
We consider replacing “two delegates” with “three delegates”. Suppose that $X$ isalnearly ordered set and $|X|\geq 3$ . Define $X(3)=\{\{x_{1},x_{2},x_{3}\}|$ Xi, ,x3 $\in X$. $x_{1}<x_{2}<x_{3}$ }. For { , , a3} $\{b_{1},b_{2},b_{3}\}\in X(3)$ , suppose that is the largest. Let be the second largest member and let be themember inthird largest member. That is, we select three different points from top in descendingorder. We define the binary operations on $X(3)$ by$x_{2}$$\mathrm{s}.\mathrm{t}$$a_{1}$$c_{3}$$a_{2}$$\{a_{1},a_{2}, a_{3}, b_{1}, b_{2},b_{3}\}$$c_{1}$$c_{2}$$\mathrm{u}$$\{a_{1},a_{2}, a_{3}\}\mathrm{U}$$\{b_{1},b_{2},h\}=\{c_{1},c_{2},c_{3}\}$.

}, let be the second smallest
be the smallest member of { a2,Letmember and let be the third smaUaet member. That is, we select three different$X(3)$
points from bottom in ascending order. We define the binary operationsby$d_{1}$$a_{1}$$a_{3},b_{1},b_{2},b_{3}$$d_{2}$$d_{3}$$\cap \mathrm{o}\mathrm{n}$$\{a_{1},a_{2},a_{3}\}\cap\{b_{1},b_{2},b_{3}\}=\{d_{1},d_{2},d_{3}\}$.

95
Then, the algebra $(X(3),$L, 1) is not tricable 2-semilattice(see Example 3). However,define the two operations V and 6by{$a_{1}$a2,$a_{3}$}$\nabla\{b_{1},b_{2},b_{3}\}=\{d_{1},c_{2},c_{3}\}$$\{a_{1},a_{2},a_{3}\}\triangle\{b_{1},b_{2},b_{3}\}=\{c_{1},d_{2},d_{3}\}$Then,$\mathrm{u},$$\cap$,$\nabla$and$\triangle$.

have the 4-roundabout absorption laws.

Figure 6: Example 3
Example 3Let $X$ be the four points linearly ordered set {1, 2, 3, 4}. We denotethe three points subset {1, 2, 3}, {1, 2, 4}, {1, 3, 4} and {2, 3, 4} by 4, 3, 2and 1.
. (see Figure 6).
asemilattice on $X(3)$ . If
Then, the set $X(3)$ is
$2*3$
$2*3$
, then,. If. If $2*3$, then$2*3=\check{4}$, then. In any case, the
. If
then
algebra $(X(3), \square , \cap, *)$ is not atrice.
$\mathrm{L}\mathrm{e}\mathrm{t}*\mathrm{b}\mathrm{e}$$\{\check{1},\check{2},\check{3},\check{4}\}$$=\check{1}$$=\check{2}$$((\check{2}*\check{3})\mathrm{u}\check{3})\cap\check{3}=\check{4}$$((\check{2}*\check{3})\mathrm{u}\check{3})\cap\check{3}=\check{4}$$=\check{3}$$((\check{2}*\check{3})\mathrm{U}\check{3})\cap\check{3}=\check{4}$$((\check{3}*\check{2})\square \check{2})\Pi\check{2}=\check{4}$As the generalities, we have next question.
Question 3How many operations is it necessary to add to a -semilattice tosatisfy the roundabout absorption laws?
$\mathrm{n}$2.3From semilattice to trice

is not always one of the operations of alatWhen $(A, *_{1})$ is asemilattice, thetice. That is, it is not sufficient to add one operation to semilattice to satisfy theroundabout absorption laws.
$*_{1}$

Question 4By adding two operations, does any semilattice become atrice? Is
there aconcrete way of composing it? Then, can we make interested trice which it
should pay attention to?

96
Definition 2Let (A,when an algebra (A,A.

is tricablebe asemilattice. The semilattice (A,is atrice for some semilattice operations $2 and $3 on$*_{1})$$*\cdot)$$*_{1}, *_{2}, *_{\mathrm{S}})$,is trice, thenOf course, if it knows that an algebra
are tricable.
is alattice, then $(L, \vee)$ andare tricable. If
andis tricable in the meaning of the definition 1, $(S, *_{1})$ andIf the 2-semilattice$(S, *_{2})$ are tricable.
is not tricable even if $(A, *_{1})$But, the 2-semilattice
and the $(X(3), \cap)$ are tricable,
and $(A, *_{2})$ are tricable. For example, theis not tricable.
however the$(T, \nearrow_{1})$$(T, \nearrow_{1},\nwarrow 2, \downarrow 3)$$(L, \wedge)$$(L, \vee, \wedge)$$(T, \downarrow 3)$$(T, \nwarrow_{2})$$(S, *_{1}, *_{2})$$(A, *_{1}, *_{2})$$(X(3), \mathrm{U})$$(X(3), \mathrm{u}, \cap)$

Example 4The seven points semilattice which diagram is Figure 7-left is nottricable. But the eight points semilattice which diagram is Figure 7-right is tricable.

Figure 7: Example 4
Then, the suk emilattice of (A,$*)$ is not tricable even if (A,$*)$ is tricable.

We gained the next propositions about the concrete way of composing atricablesemilattice.
of pairwise disjoint tricable semilatSuppose we are given afamily
tice, i.e., thatfor $s\neq s’$ .
$\{(A_{t}, *_{\mathrm{g}})\}_{\epsilon\in S}$$A_{*}\cap A_{\epsilon’}$

Proposition 2Let
And let the operation$S$$\nearrow 1$

be alnearly ordered set. Cosider the set
on defined by$x\nearrow_{1}y=\{$

$x$

$y$

$\nearrow_{1})$.

if $x,y\in A_{t}$$x*_{\epsilon}y$The algebra (A,$A= \bigcup_{s\in S}A_{s}$

$A$

if
if

$x\in A_{\delta}$$x\in A_{s}$, $y\in A_{s’}$ axsd $s>s’$, $y\in A_{s’}$ and $s<s’$ .

is atricable semilattice.

and the semilattice
Proposition 3Letthat is, $e*_{0}x=x$ for all $x\in A_{0}$ . Cosider the set$\mathrm{O}\in S$$(A_{0}, *_{0})$have aminimum element ,. And let the operation$A= \bigcup_{s\in S}A_{s}$

$e$

97

$\nearrow 1$

on

$A$

defined byif$x*_{s}y$$x$$x\nearrow_{1}y=\{$$y$$e$

The algebra (A,$\nearrow_{1})$if
if$x,y\in A_{t}$,and $s\neq 0$$y\in A_{0}$ , $x\in A_{s}$ and $s\neq 0$
if $x\in A_{s}$ , $y\in A_{s’}$ and $0\neq s\neq s’\neq 0$ .
$x\in A_{0}$$y\in A_{s}$is atricable semilattice.

Proposition 4Suppose that the diagram of asemilattice is atree structure, thenit is made atrice by adding two operations which induced linearly ordered.
Example 5Suppose that
Figure 8-left. Let
andis atrice.
algebra$(S, \nearrow_{1})$$(S, \nwarrow_{2})$is asemilattice which diagram is the tree ofbe next linearly ordered sets. Then, the$(S, \downarrow 3)$$(S, \nearrow_{1}, \nwarrow 2, \downarrow 3)$

Figure 8: Example 5
Question 5wiu not there be another good method which composes atrice of asemilattice?
Question 6Will not there be agood way ofjudging that asemilattice is tricable?

References[1] G. Birkhoff. Lattice Theory (third ed.) Amer. Math. Soc. Colloq. Publ., 1967.

[2] S. Burris, H.P. Sankappanavar, A Course in Universal Algebra Springer-Verlag,
New York, 1981.
[3] G. Gratzer. General Lattice Theory (Second ed.) Birkhauser, 1998.

[4] A. Knoebel and A. Romanowska, Distributive multisemilattices.
Mathematicae (Rozprawy Matematyczne), Polska Akademia Nauk Instytut
Matematyczny. 309 (1991), 42 pp.
$\mathrm{D}\mathrm{i}\mathrm{a}\mathrm{e}\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\varpi$[5] A. Mitschke, Near unanimity identities and congruence distributivity in equational classes. Algebra Universalis 8(1978) 29-32