TANGLING IN DUALISABILITY OF UNARY ALGEBRAS
by
Joya Danyluk
B.Sc., University of Northern British Columbia, 2013
THESIS SUBMITTED IN PARTIAL FULFILLMENT OF
THE REQUIREMENTS FOR THE DEGREE OF
MASTER OF SCIENCE
IN
MATHEMATICS
UNIVERSITY OF NORTHERN BRITISH COLUMBIA
May 2016
© Joya Danyluk, 2016
Abstract
We look at non-dualisable {O, 1}-valued finite unary algebras with O where meet is defined on the
algebra and join is partially defined. More specifically, we look at Join Upper Bounded Algebras
with unique rows, as well as two types of Join Upper Bounded Algebras with non-unique rows:
non-one-doubled-algebras and one-doubled-algebras. We then determine what tangled functions
need to be included for an extension of the algebra to be dualisable. It turns out that just including
the tangled functions for non-one-doubled-algebras and one-doubled-algebras is not enough to
guarantee dualisability. We then define the additional functions needed for dualisability of the
extension.
TABLE OF CONTENTS
Abstract
Table of Contents
ii
List of Figures
iv
List of Tables
v
Dedication
vii
Acknowledgement
viii
1 The Context of this Work
2
1
Notation and Background
2.1 What is an Algebra? . . . . . .
2.1.1 A Brief Review . . . . .
2.1.2 Definition of an Algebra
2.1.3 Unary Algebras and the Product Algebra
2.1.4 A Lattice is a Type of Algebra . . . . . .
2.2 Dualisability . . . . . . . . . . . . . . . . . . . .
2.2.1 The Quasivariety and Topological Quasivariety
2.2.2 Rows of an Algebra . . . . . . .
2.2.3 Dualisability of a Finite Algebra .
2.2.4 Theorems about Dualisability
2.3 Dualisability and Tangling . . . . . . . .
3
3
3
4
7
8
10
10
12
16
19
20
3 Join Upper Bounded Algebras
3 .1 Introduction . . . . . . . . . . . . . . . . .
3.2 Join Upper Bounded Algebras . . . . . . .
3.3 Properties of Join Upper Bounded Algebras
3.4 The Join Upper Bounded Algebra Morphism Property.
3.5 The Operation ft Defined on {O, 1}-Valued Join Upper Bounded Algebras
23
23
24
25
30
41
4 Dualisability of Join Upper Bounded Algebras with Unique Rows
44
11
4.1
4.2
4.3
5
Join Upper Bounded Algebras with Repeated Rows
5.1
5.2
5.3
6
{O, 1}-valued Join Upper Bounded Algebras with Non-Unique Rows .
Dualisability of Non-One-Doubled-Algebras . . . . .
5.2.1 An Example of a Non-One-Doubled-Algebra
Dualisability of One-Doubled-Algebras . . . . .
5.3.1 An Example of a One-Doubled-Algebra .
An Example of a Non-One-Doubled-Algebra
6.1 M is Not Dualisable . . . . . . . . . . . .
6.2
6.3
7
Defining the Tangled Functions on {0, 1}-valued Join Upper Bounded Algebras
with Unique Rows . . . . . . . . . . . . . . . . . . . . . . . . . . .
The Tangled Operations Respect the Meet and Join Homomorphisms .
Dualisability of Tangled Unary Algebras with Unique Rows . . . . .
Unable to Determine if Mr ang is Dualisable
JM is Dualisable . . . . . . . . . . . . . . .
44
48
55
60
60
76
96
97
123
126
. 126
135
. 136
Conclusion
146
7.1
7 .2
146
. 147
Summary
Future Work .
Bibliography
149
lll
LIST OF FIGURES
2.1
2.2
2.3
2.4
An example the semilattice induced by an algebra .
The dual of A where A E IT§IP'(M). . .
The dual of X where X E IT§c]P'+ (MI) . . . . .
Dualisability of an algebra. . . . . . . . . .
5.1
5.2
5.3
5.4
An example of a non-one-doubled-algebra.
62
An example of a Join Upper Bounded Algebra that is not a non-one-doubled-algebra. 63
An example of a one-doubled-algebra. . .
63
63
A non-example of a one-doubled-algebra.
6.1
6.2
M = ({O, 1, 2, 3,4} , {fo,h , /3 ,f4} ).
(M \ {4} , F IM\ {4}) . . · · · · · · · ·
16
17
17
18
. 127
. 133
lV
LIST OF TABLES
2.1 M2.1.1 = ({O, 1,2,3},!1 ,h ,h ) . . . . .
2.2 M2.2.1 = ({O, 1,2,3,4} , {fo,J1 ,h ,h} ).
2.3 M2.2.2 = ({O, 1, 2, 3},Jo,!1 ,h ,h ) . . .
7
14
15
3.1
3.2
3.3
33
38
4.1
4.2
4.3
4.4
4.5
The Join Upper Bounded Algebra Morphism Property.
Homomorphisms of A and their behaviour on Ao. . . .
The Join Upper Bounded Algebra Morphism Property is depicted here showing
the existence of an a E Ao such that Vy E X1 y( a) E BJ. . . . . . . . .
M= ({0, 1, 2,3},J1 ,h ,h,fo) . . . . . . . . . . . . . . . . . . . . .
{!1 ,h ,hJo} tangles hoo1 ,h101 ,ho11 but does not tangle h110 nor ho10.
The algebra, M along with the tangled operations defined on M. . . .
The above compositions cannot be found in F UH. The set FUH is therefore not
closed under composition. . . . . . . . . . .
a is an evaluation at a E Ao (a= eA(hu(a))).
5.1
5.2
5.3
40
47
48
53
54
57
Tangled and non-tangled operations . . . . .
73
73
An algebra with no tangled operations of the form hu ,
An example of an extension of a non-one-doubled-algebra that is not closed under
composition. Here we list the operations FU H. . . . . . . . . . . . . . . . . . . . 84
5.4 An example of an extension of a non-one-doubled-algebra that is not closed under
composition. Here we state all operations in P, along with the operation, h4o Phj,
which is not found in F U H U P. . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.5 If JM is an extension of a non-one-doubled-algebra then a= eA(hu(a)) when
range (a) = I. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.6 If JM is an extension of a non-one-doubled-algebra then a= eA (Ph(a)) when
range (a) = I U {b 1, b2}. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.7 An example of a non-one-doubled-algebra where the row(3 ) = row(4). The operation h101 o Phioo is not in F UH UP but must be included in order for the algebra
to be closed. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
98
5.8 The non-one-doubled-algebra, M, is not a closed algebra. . . . . . . . . . .
99
5.9 The algebra, M , is a closed algebra when the operation h101 o Phioo is added.
5.10 a =eA(hu (a)) whenrange(a) =/for KM. . . . . . .
118
5.11 a =eA (qh (a) ) whenrange (a ) =I U{l} for KM . . . . . . . . . .
120
123
5.12 a= eA(Ph (a) ) when range(a) = / U {1 ,b} when KM. . . . . . .
5.13 An example of a one-doubled-algebra where the row(3) = row(l).
124
V
5 .14 The compositions of the operations in FU HU PU Q therefore showing this partic. . 125
ular one-doubled-algebra is closed. . . . . . . . . . . . . . . . . . . . . . .
6.1
6.2
6.3
6.4
6.5
6.6
6.7
6.8
6.9
M,ang = ( {O, 1, 2, 3,4 }, {fo ,h ,!3,f4} U { h100 , h101} ). . . ..... .....
JM = ( {O, 1, 2, 3,4} , {fo ,h ,!3,f4} U {h100 ,h101} U {PJ0 ,PJf ,Ph 100 ,Ph 101 } ) . •
range (a)= {O, 1}.
range ( a) = {O, 2}.
range ( a) = {O, 1, 2} .
range(a) = {0, 3,4}.
range(a) = {0, 2, 3,4}.
range(a) = {O, 1, 3,4}.
range(a) = {O, 1,2, 3,4} . . . . . . . . . . .
...........
VI
. 135
. 136
. 142
. 142
.. 143
.. 143
. 144
. 144
. 145
Dedication
For the one who spent countless hours perfecting the RCMP walk and turn test and yet was
clueless about the existence of Corrie Ten Boon and Hudson Taylor. For your love and dedication
to your grandparents, as well as your undesirable need to constantly juggle fruit. For your strong
work ethic and your stubbornness to push through and continue to play. To the one who never
says what you mean and yet we all understand you anyway. Thank you for faithfully walking
this concussion-masters journey with me. I appreciated the countless walks and discussions as I
worked through my thesis, the pain and the constant exhaustion. Thank you for your patience as
you repeatedly convinced me to finish this degree and figure out a way to live with a mTBI. It is
only a temporary injury anyway. I needed daily encouragement to persevere and not run away. I
don't know if a day went by where I didn't want to quit, but I made it. We made it:) Thanks again.
I truly hope you never have to see 167 distinct road kill in one day again or get mobbed by a group
of hungry kids. That probably brought up some bad memories. Sorry about that. Go enjoy a White
Chocolate Mocha or a London Fog. I'll pay this time. Its the least I can do for all you 've done for
me.
vu
Acknowledgement
Dr. David Casperson and Dr. Jennifer Hyndman, thank you for the countless hours you put into
editing my thesis and helping me with LaTeX. Although we may have disagreed on whether or not
a thesis should have an apologies section, I have always valued your input. I am truly grateful for
all the help you gave. To my committee Dr. Hyndman, Dr. Casperson, Dr. Edward Dobrowolski
and Dr. Liang Chen thank you for being a part of this journey with me. I know that each of you
lead busy lives and I sincerely appreciate all the help you gave. Dr. Andrea Gorrell, thank you for
all your help! And to the University of Northern British Columbia and the Natural Sciences and
Engineering Research Council of Canada, thank you for your financial support in my education.
It constantly amazes me that we actually got to the part of my degree where I get to do the
finishing touches on this document such as adding the dedication and the acknowledgements. Out
of the 986 days it took me to do my Masters, 937 were spent recovering from my concussion.
I do not necessarily remember how we got this far with classes completed and research done, all
while dealing with constant exhaustion, frustration and a painfully sore head. What I do remember,
however, is how well looked after I was, both at home and at school.
Dr. Hyndman, I could not have ask for or imagined a better supervisor. Not only did you walk
this mathematical journey with me, but you were always so understanding and continually gave
me the space and ability to recover from the invisible injury I daily pretended I did not have. My
memory and speech have been problematic these past few years and your patience with me, as you
explained and re-explained concepts did not go unnoticed. Thank you for helping me and giving
me the space I needed to learn how to live with an injury.
Dr. Casperson, thank you your willingness to step in and help me fini sh my degree. For
taking the time to meet with me, read my thesis, explain concepts and for helping me with my
presentation. I really appreciate all the extra help you gave! Thank you!
To Jean Bowen and Erin Beveridge: thank you for taking care of me each and every day these
past few years. You drove me to school and back when I could not; took over my labs and tutoring
times ; continually checked in on me while I was at school; and just looked out for me. Thank
you for not listening to me when I said, 'Tm good, I can keep going." Although I never wanted to
stop, I was always thankful when you forced me to take a break. I could not have stayed in school
without you two (and Jennifer) looking out for me while I was there.
To Brett Kelly, Tyler Poole, Conan Veitch and Bashet Ullah: thank you for helping me with my
marking, as well as covering my labs and tutoring times. You took away all stress associated with
my responsibilities at school and allowed me to concentrate on resting and getting better. I really
appreciate it! To Vivian Fayowski and Nico Turner: thank you for watching out for me at the ASC
and encouraging me while I was there. You were all so understanding, thank you!
To the Knapps, thanks for taking care of me while at home: keeping me entertained and making
me laugh. Aunty Carol thanks for walking this journey with me. You helped keep me positive.
Who knew concussions could be so much fun - especially if you tack on a thesis as well. :) Oh the
viii
jokes that were made at my expense. It is what made this injury, degree and journey so enjoyable.
:P
Mom and Dad, I could not have tackled both a thesis and a concussion without you both. Your
constant willingness to listen to my daily struggles of mixing school and concussions was greatly
appreciated. You always seemed to know what to say to convince me to persevere and not run away
... and I made it! Thank you for everything! Anna, Lena and Josiah thanks for being interested
in my work even though it did not make sense to you, and for being patient with me as I slowly
recovered from this never ending injury.
[ . . . I furthermore want to take this opportunity to sincerely apologize to my aunt, my dog,
Annie Bourque and my family. Each now knows more math terms then they could ever care to want
to . . .. J
A big thank you to Nicole Strachan, Andrea Schneider, Pauline Martin, Dr. Cirelle Rosenblatt
and Dr. Rose Martel. I cannot begin to describe how nice it was to have people in my life that knew
what this was like and understood my struggles without me trying to explain everything. You gave
me the tools and knowledge I needed to excel both in school and in my concussion recovery. I am
so glad I discovered you. Although it was rough when we decreased my caffeine intake; rougher
still that time while I was learning to take breaks; even worse yet when I had to learn to live on a
points system; and we can't forget that time when I almost came close to "almost drowning"; and
do people actually balance on thick foam mats with their eyes closed for fun? - doesn't matter.
I've pretty much mastered that. :P Each of you made a huge difference in my life/recovery. There
is no doubt in my mind that I would not have been able to stay in school without your help. Thank
you once again.
And Nicole - Thank you for always taking the time to listen - even when there were maybe exercises we should have done instead. You always went out of your way to hear me out and filled in
the blanks when I did not:) You continually went above and beyond for me. I really appreciate all
you 've done!
Aunty Donna and Uncle Jack thanks for letting me intrude on your lives every month as I made
my pilgrimages to the concussion clinic. Thank you for taking the time to listen to what life was
like.
And finally, to the two people that instilled/formed a love of math in me: Cam and Cindy-Anne
Spelay. Thanks for everything. If I ever become I teacher, I would consider it an accomplishment
if I can be half as good as you both are.
To the One who continually provides, cares, listens, loves unconditionally and calls me His daughter. I'm speechless. Grateful. Amazed. And humbled. You gave me hope, strength and the ability
to press on. I would have been lost without You. Thank you for continually walking beside me and
for the promise to do so for the rest of my life.
lX
Chapter 1
The Context of this Work
In this document we look specifically at {O, 1}-valued finite unary algebras with O where meet
is defined on the algebra and join is partially defined. Our algebras therefore form semilattices
with least element zero. When the order of the underlying set of the algebra is greater than 3 the
algebra is not dualisable [3]. Moreover, there are specific operations, called tangled functions,
that can be defined and need to be included for an extension of the algebra to be dualisable [3].
We look at these non-dualisable {O, 1}-valued finite unary algebras with 0, and determine which
tangled functions must be included in order to ensure dualisability. In some cases, specifically
when the rows of the algebra are not unique, there are additional operations that must be included.
We are not sure if these additional operations are tangled. When all the necessary operations are
included, we show that the extended algebra is dualised by a particular alter ego. We use the
Duality Compactness Theorem to prove that the alter ego yields a duality on our algebra. In this
document we did not look into whether the alter ego yielded a full or strong duality on the algebra.
Although this question has not been addressed for our algebras, it has been looked into for various
other algebras [8, 11 , 12]. Furthermore, it is unknown if the alter ego that dualises the algebra is
the smallest possible alter ego that will dualise the algebra.
We chose to work with algebras where the join operation is a partial homomorphism as it has
1
previously been shown that, when we have a finite algebra where meet and join are both total
homomorphisms, then not only does the algebra form a lattice, but it is also dualisable [5, 8].
Furthermore, the alter ego that dualises the algebra uses meet, join and relations of arity at most
twice the size of the algebra [5, 8]. When an algebra has a sernilattice operation as one of its
basic operations then it is called a semilattice based algebra. Some work has been done with
finite semilattice based algebras and it has been shown that when the operation meet is also a
homomorphism then the algebra is dualised by M = (M , /\,&e1Ml+ l , !Y) [7]. This differs from the
work done in this document as our algebras are unary and are therefore not semilattice based.
In other literature, the kernel of an algebra has been used to categorize the dualisability of
all unary algebras of the form M = ({0, 1, 2} , F ) where F forms a monoid [6, 8]. It was shown
that algebras of this type could have zero, one, two or three kernels [6, 8]. When the algebra has
zero or one kernel then it is dualisable; however when the algebra has three kernels then it is not
dualisable [6, 8]. If the algebra has two kernels then conditions exist to determine if the algebra
is dualisable [6, 8]. Other theorems useful for showing specific algebras are dualisable include
the Strong Idempotents theorem, the GST theorem, Term retracts theorem and the Interpolation
Condition [7, 8].
Work has been done to show that if two finite algebras M and D generate the same quasivariety
and we know an alter ego, ID>, that dualises D then we can describe the alter ego that dualises
M [ 1O]. Furthermore, if the algebra D is actually a subalgebra of M and we have M E JI§IP'(D) then
by knowing the alter ego that dualises D we can build the alter ego that dualises M [10]. Moreover,
the author of [18] showed that "if we have a finite algebra M and 8e is a finite set of algebraic
relations then 8e yields a duality on M if and only if every relation in 8e is made using diagonal
relations, direct product of two relations, intersection of two relations and bijective projection to
some variable of a relation."
2
Chapter 2
Notation and Background
2.1
What is an Algebra?
In this section we begin with a review of some of the notation used in this document. We then
define the term algebra which will lead us to the definitions of unary algebras, product algebras
and lattices. These terms will be used and referred to throughout the entire document. The basic
definitions used in the section, What is an Algebra?, came from Burris and Sankappanavar [1].
2.1.1
A Brief Review
We give a brief review of the definitions of the product of sets, projection maps and n-ary operations. We also define the identity map, as well as the constant maps.
n
Let Mk, for 1 ~ k ~ n, be a collection of nonempty sets. We define the product, fl Mk, to be
k= l
3
the set
n
IJ Mk= { (m1, m2 , ... ,mn) : for every i with 1 ::; i::; n we have mi E Mi} k=I
n
We refer to the elements of TI Mk as n-tuples and we sometimes write m 1m2 · · · mn instead of
k=I
(m1,m2, ... ,mn)- For every i with 1 ::; i::; n we define the projection map
n
n;: fIMk-+Mi
k=I
to be
n
where (m1 , m2 , ... ,mn) is in the set TI Mk . If for every i with 1 ::; i::; n we have Mi= M then we
k=I
n
write Mn instead of TI Mk. We let M 0 denote the canonical one element set. A map f : Mn -+ M
k=I
(n 2: 0), is called an n-ary operation defined on M. We define the arity off to be n. If the arity
of an operation is zero, then we call the operation a nullary operation. A unary operation is an
operation whose arity is one. Given a unary operation f defined on the set M and if for every x in
M we have f(x) = x, then we refer to fas the identity map. A constant function is any function
that maps every element in the domain to one particular element in the range. For example, given
the unary operation f: M-+ M if for every x EM we have f(x) = 0 then f would be the constant
zero operation. And finally given a unary map h : M -+ M and an element b in MI , for some set/,
we define h(b) to be the element in MI such that for every i with i EI we have
h(b)(i) = h(b(i)).
2.1.2
Definition of an Algebra
We begin this section by defining an algebra, and then move on to the definitions of subalgebras
and subuniverses of algebras.
4
A collection of function symbols, ff, is called a language of type ff if for every symbol f
in ff there is a finite, non-negative number associated with it. This number is called the arity of
f. An algebra, M, of type ff is an ordered pair (M, ff) where Mis a nonempty set (called the
universe of M), and ff is a collection of function symbols with finite arity. Moreover, for each
f E ff of arity n there must be an associated n-ary operation JM defined on M. We sometimes use
F to denote the set of all functions defined on M whose corresponding operation symbols are in
ff . It is not uncommon to write
M = (M ,F )
instead of
M= (M,ff).
The notation JM is used to make it clear to the reader that the operation f is defined on the algebra
M . When the situation is clear we will drop the Mand write f. If the language of an algebra is fi-
nite, i.e. ff = {Jo ,!1 , ... , f v}, then we say the algebra has finite type. Furthermore, we sometimes
write (M,{fo,!1 , ... ,Jv }) instead of (M, {J6'1,JJ'1, ... ,f~} ). Given an algebraJ= (J,F ) and a
collection, H, of operations defined on J we define the extension of J to be the algebra
J' = (J,F UH ).
Furthermore, we sometimes refer to the algebra J as a reduct of the algebra J'.
Two algebras M1 = (M1 , ff1) and M2 = (M2, ff2) are said to be of the same type if ff1 and
ff2 are the same. Sometimes we refer to a class of algebras all of the same type, ff and we define
identities that the symbols in ff satisfy.
For example, consider the class of all groups of type ff = {*, -,, e} where * is a binary operation, -, is a unary operation and e is a nullary operation. A group can be defined as the algebra
G = (G, *, -, ,e) where the symbols *,-,, and e satisfy the following for all {x,y,z } ~ G:
5
2. x * e = x = e * x, and
3. X* •X = e = •X *X.
In this class we would find the group under addition, G + = (c+, +,- ,0) satisfying the following
for x ,y,z E G+ :
1. x+ (y+z) = (x+y) + z,
2. x + 0 = x = 0 + X, and
3. x+(-x)=O=(-x)+x.
We would also find the group under multiplication G· = (G" , ·, - l , 1) in the class. We note here that
each of G+ and G· are of type § = { *, , , e} with one binary, one unary and one nullary operation.
However the operation sets defined on each type of group are different as the operation set on G+
is pG+ = { +, - ,0}, while the operation set on G· is pG = { ·, - l , 1}. This therefore points out
the difference between the language, §, defined on an algebra (collection of symbols) and the
operation set, F, defined on the algebra (collection of operations on the algebra with the same arity
as the symbols in the language).
Suppose the algebras M 1 and M2 are of the same type. For each i E { 1, 2} let JM; represent an
operation in F;.. If M 1 is contained in M 2 and for every JM 1 E F1 we have JM 1 = JM 2 IM then we
1
say that M 1 is a subalgebra of M2 and write M1 ::; Mz. A subalgebra is a subset with restricted
operations. By convention, subalgebras are non-empty. Any subset N of M 1 that is closed under
every operation in F 1 is called a subuniverse of M1. If M1 is a subalgebra of M2 then M 1 is a
subuniverse of M 2 . So, the subuniverse is the carrier set of a subalgebra. In this document, our
6
algebras all have the constant zero operation a part of their operation set. Therefore, {0} is not a
subuniverse.
2.1.3
Unary Algebras and the Product Algebra
In this section we define two types of algebras: unary algebras and the product algebra. Both
algebras will be referred to throughout the document.
Let M = (M, F ) be an algebra. If for all fin F we have f is a unary operation, then M is called
a unary algebra. If for every f E F, with f not the identity map, we have that the the range off is
contained in {O, 1}, then we refer to Mas a {O, 1}-valued algebra. An example of a {O, 1}-valued
finite unary algebra is given in Example 2.1.1 .
Example 2.1.1. Let M2.1.1 = ({O, 1, 2, 3},!1 ,h,h ) be the algebra defined in Table 2.1. As each
operation is unary, the algebra is a unary algebra. We further note that each operation takes every
element in {O, 1, 2, 3} to either O or 1 and therefore our algebra is {O, 1}-valued. Hence, M 2.1. 1 is
a {O, 1}-valued unary algebra.
f1
h
h
0
0
0
0
1
0
1
0
2
0
0
1
3
1
0
1
Table 2.1: M2.1.1 = ({O, 1, 2, 3},!1 , h ,!J)
Let {Ai}iEJ, for i in some set/, be a collection of algebras of the same type. We define the
7
product algebra,
to be the algebra with universe TI Ai and whose fundamental operations satisfy
iEI
for every n-ary operation fin F and for a1 , ... ,an in TIA.
iEI
2.1.4
A Lattice is a Type of Algebra
In this section we introduce the concept of a lattice which is used in some dualising structures.
In order to talk about lattices we will need the definition of a poset and a /\-semilattice. Both are
defined below. This section is based on material from [ 1, 9].
A binary relation ::; defined on a set A is said to be a partial order if for every a , b and c in A
we have
1. a::; a (reflexive)
2. a::; band b::; a imply a= b (antisymmetric)
3. a ::; band b ::; c imply a ::; c (transitive).
A set with a partial order defined on it is called a partially ordered set or poset. Given a poset, P
with ::; defined and a, b E P we say a is covered by b, written a -< b, if a < band if there is a c E P
with a ::; c ::; b then either a = c or c = b. We will use this term throughout this document.
A set K , together with a binary operation I\ : K 2 -+ K is called a /\-semilattice, written (K, /\),
if I\ satisfies the following:
8
1. Vx E K we have x I\ x = x (idempotent);
2. V{x ,y} ~ K we have x /\y = y /\x (commutative); and
3. V{x,y,z} ~Kwehave (x/\y)/\z=x/\(y/\z) (associative).
The /\-semilattice is an example of an algebra.
With the definition of a /\-semilattice we can now define the term lattice. An algebra (L, /\, V),
with two binary operations, I\ and V, defined on M , is a lattice if
1. (L, /\) is a /\-semilattice;
2. the binary operation, V : L 2 -+ L, satisfies
(a) Vx E L we have x V x = x;
(b) V{x, y} ~ L we have x Vy = y V x; and
(c) V{x,y,z} ~ L we have (xvy) V z = xv (yv z) .
(Note that (L, v) is an example of an algebra); and,
3. for all { a, b} ~ L we have a I\ ( a V b) = a, a V ( a I\ b) = a (absorption laws).
A lattice is also an example of an algebra. When :::; is defined on L by a :::; b whenever a = a I\ b
then (L, :::;) is a poset. In this document we look specifically at semi lattices that are not lattices. A
formal definition of this is given in Section 2.2.2 on page 15. In the next section we look into what
it means for an algebra to be dualisable. It has been shown that all lattices are dualisable.
For a lattice (semilattice) we refer to the operations, I\ and V, as meet and join respectively.
9
2.2
Dualisability
The entire document looks at non-dualisable algebras and determines how to extend the algebras
so the extensions are dualisable. Before we can talk about this, we must first look into what it
means for an algebra to be dualisable. We do this by first introducing quasivarieties, alter egos
and topological quasivarieties (Section 2.2.1). We then define a particular relation known as the
Rows(M) (Section 2.2.2) and then move into the definition of dualisability (Section 2.2.3) . We end
the section by stating a few theorems about dualisability (Section 2.2.4). The following definitions
and concepts are from [1,4, 8, 13].
2.2.1
The Quasivariety and Topological Quasivariety
In this section we introduce the quasivariety generated by an algebra along with the topological
quasivariety generated by an alter ego. Both concepts are needed to define and understand dualities.
We first begin with the notion of homomorphisms and isomorphisms defined on algebras.
Given two algebras, M 1 and M2 of the same type § , if there is a map g: M 1 -+ M2 such that
for all n-ary fin § and a1 , a2 , .. . , an in M1 we have
then we call g a homomorphism from M 1 to M 2. Here, JM 1 and JM 2 are the n-ary functions,
in pM, and pMz respectively, corresponding to the n-ary function symbol fin .ff. We say M 1 is
isomorphic to M2 if there is a bijective map h: M 1 -+ M 2 that is also a homomorphism. This is
denoted as M1 ~ M 2 and we refer to the map has an isomorphism. An embedding is a one-to-one
homomorphism.
Let M = (M, F ) be a finite algebra. The quasivariety, .!21, generated by Mis the class of all
10
isomorphic copies of subalgebras of products of M. We denote the quasivariety by TI§IP(M). Note
that the one-element algebra TI© is always included in a quasivariety. We define the algebraic operations on M to be the homomorphisms from Mn to M, with finite non-negative n. We sometimes
refer to algebraic operations as total operations. The partial algebraic operations on M are the
homomorphisms from B to M where B ~ Mn and n is finite and non-negative. We sometimes refer
to these operations as partial operations. Every algebraic operation is a partial algebraic operation.
A subset R of M'1- (with n non-zero) that forms a subuniverse of Mn is called an algebraic relation
on M. A relation, R, with R ~ Mn is said to have an arity of n. Moreover, we use !!lk to denote all
relations of arity up to and including k, where k is a positive, finite number. Furthermore, if r is a
1
k-ary relation defined on an algebra M then we define the corresponding k-ary relation, ,M , as
{(b1 , . .. ,bk): b1 , ... ,bk E M1 and \/i EI we have (b1 , ... ,bk)(i) = (b1 (i) , ... ,bk(i)) Er} .
Given a relation R ~ M 1 and the tuples YI , .... ,YI EMA we say that (y1 , ... ,YL) are R-related when
(y 1 (a) , .. . ,y 1 (a)) E R for each a E A. Finally, recall that a topology, !Y, on a set A is a collection
of subsets of A where
1. the empty set and the set A are in the !Y;
2. for any P
c !Y we have ( LJ
CE~
c)
E §; and,
3. for any 9 C !Y with 9 is finite; we have (
n c) E § .
CE~
The discrete topology is one where every set is open.
Using this knowledge we now define the alter ego of an algebra and then finish with the definition of the topological quasivariety generated by the alter ego.
Let M be an algebra and let
11
• C§ be a set of algebraic operations on M ,
• .Yt' be a set of partial algebraic operations on M,
• !% be a set of algebraic relations on M, and
• § be the discrete topology on M .
Then given the algebra M together with the following sets, C§, £,!%,and § we define the topological structure, M = (M; C§, .Yt',!% , §), as an alter ego of M. Note that both the alter ego, M,
and the algebra, M, have the same underlying set M. Using the alter ego we can now define the
topological quasivariety. The topological quasivariety, !£, consists of all isomorphic copies of
closed substructures of non-zero powers of the alter ego, M. The topological quasivariety is denoted by JI§clfll+ (M). When we say non-zero powers of M, we mean Mn with n > 0. Furthermore,
the term closed is used to mean closed with respect to the topology and the term substructure refers
to being closed with respect to both C§ and£. A morphism a : (C -t Il)), where C, lI)) E lI§clfll+ (M),
is a continuous map that preserves the total operations, partial operations and relations on M.
2.2.2
Rows of an Algebra
In [2, 3] the authors introduce the concept of the row of an algebra. The rows of an algebra is
needed to divide the algebras in this document into two categories: algebras with unique rows and
algebras with non-unique rows. Furthermore, the rows of an algebra is used to draw the semilattice
induced by an algebra.
Suppose M = (M , F) is a finite unary algebra. Let F' = {!1, h, ... , fv} be a fixed enumeration
of the non-constant, non-identity operations in F. For all a EM define the row at a, written row(a),
12
to be
row (a) = (f1 (a) , h (a) , ... Jv (a)) .
When
(f1 (a) , h (a) , .. . , f v (a) )
is a specific tuple of small integers, we sometimes drop the parenthesis and commas. For example,
we would write 020 instead of (0, 2, 0). We further define the v-ary relation, Rows(M), as
Rows(M) = {row(a)
I a EM}
= {(!1 (a) , h (a) , .. . Jv (a)) I a E M}.
We demonstrate how to find the row(a) for some a EM as well as the Rows(M), for the algebra
M2.2.1 defined in Example 2.2.1 .
Example 2.2.1. Let M2 .2.1 = ({O, 1, 2, 3,4} , {fo,!1 ,h ,h} ) be as defined in Table 2.2. When evaluating row(a) we exclude Jo in the calculation as it is the constant zero operation. Then the row(O)
and row(3) will be as follows :
row(O) = (!1 (O) ,h(0) ,13(0))
= (0,0, 0)
or row(O) = 000,
and row(3) = (!1 (3) ,h(3),f3(3))
= (0 , 1, 1)
or row(3) = 011.
13
Jo !1
0
0
0
0
0
1
0
0
0
1
2
0
1
0
0
3
0
0
1
1
4
0
0
1
1
Table 2.2: M2.2. 1 = ({O, 1,2,3,4} ,{fo,!1 ,h ,h} ).
Furthermore, the Rows(M2.2. 1) will be
Rows(M2.2. 1) = {row(a) I a E M2.2.1)}
= {row(O) , row(l ), row(2) , row(3) , row(4)}
= {(0,0,0) , (0,0, 1) , (1 ,0,0) , (0, 1, 1)}
= {000,001 , 100,011} .
An algebra M = (M, F ) is said to have a repeated row if there are elements a and b in M , with
a =f. b, such that the row( a) = row( b). We sometimes refer to an algebra with a repeated row as an
algebra with non-unique rows. If no such elements exist we say that M has unique rows. Referring
to Example 2.2.2 (found below) we see that the algebra M2.2.2 has unique rows. In Example 2.2.1
(found above), however, the algebra M2.2.1 has non-unique rows as row(3) = row(4). If an algebra
M has unique rows then we say the Rows(M) are uniquely witnessed, i.e. for all i and j in M, if
row(i) = row(j) then we have i = j.
A finite unary algebra M that has a row and a column of zeros such that {O} forms a subalgebra of M, is called an algebra with zero. An example of an algebra with zero is given in
Example 2.2.2.
14
Example 2.2.2. The algebra M2.2.2 = ({O, 1, 2, 3},fo,!1 ,h ,13), as defined in Table 2.3, is a {O, 1}valued finite unary algebra with zero. Moreover, M2.2.2 has unique rows.
Jo !1 h
13
0
0
0
0
0
1
0
0
1
0
2
0
0
0
1
3
0
1
0
1
Table 2.3: M2.2.2 = ({O, 1,2, 3},Jo,!1 ,h ,h )
When the authors of [3] refer to the Rows(M) forming a semilattice that is not a lattice they
mean, "Assume that Rows(M) ~ {O, 1Y forms a sub-meet semilattice of the lattice formed by
{0, 1Y with the order O < 1. We will use I\* to represent the semilattice operation. Furthermore,
assume that Rows(M) does not form a lattice. Let the partial join operation on Rows(M) obtained
from the lattice be denoted by V* . The semilattice operation I\ on Mis defined by a I\ b = c if and
only if row(a) I\* row(b) = row(c). The semilattice operation V on M by a Vb= c if and only if
row(a) v* row(b) = row(c) ."
If M is a finite unary algebra with unique rows we can use the Rows(M) to draw the lattice
or semilattice induced by M. We do this by drawing a Hasse diagram using the point-wise order
induced by the elements in Rows(M) by the order induced by O < 1. This is done by looking at
each row of the algebra and comparing them coordinate-wise. For example, the tuple (a 1, ... , an)
would be less than or equal to the tuple (b1 , ... , bn) if and only if for every i with 1 ::; i ::; n we have
ai ::; bi . If it is the case that (a 1, ... , an) ::; (b 1, ..• , bn) then we would use a dot to represent each of
(a1, ... , an) and (b1, ... ,bn)- We would place the dot for (b1, ... , bn) above the tuple (a1, ... , an)
15
M
!1 h h
0
0
0
0
1
0
0
1
2
0
1
1
3
1
0
1
3
YM
0
IOl~M
001
000
Figure 2.1: An example the semilattice induced by an algebra
and we would use a line to connect the dots. We would follow this process for each element in the
algebra. If two tuples are not comparable there would be no line connecting them. We generally
label the dot representing the row (a) by a. An example of a semilattice induced by an algebra is
given in Figure 2.1. Here we draw the semilattice induced by the algebra, M , defined in Figure 2.1.
2.2.3
Dualisability of a Finite Algebra
Using our knowledge of quasivarieties, alter egos and topological quasivarieties we now look into
what it means for an algebra to be dualisable.
Let M = (M, F) be a finite algebra. For any A E TI§IP(M), the dual of A, denoted D (A), is the
set of all homomorphisms from A to M. It turns out that D (A) is in TI§cIP+(M). This is pictured in
Figure 2.2.
For any :XE TI§cIP+(M), the dual of :X, denoted E(X), is the set of all morphisms from :X to
M. Recall that a morphism is a structure-preserving continuous map. It turns out that E (X) is in
TI§!P(M ) as pictured in Figure 2.3.
16
JI§lfD(M)
Figure 2.2: The dual of A where A E JI§lfD(M).
lI§lfD(M)
Figure 2.3: The dual of X where XE lI§clfD+ (M).
17
It is not obvious that the D(A) E TI§c!P'+ (:MI) (for any A in JI§IP'(M)) and that the E (X) E JI§IP'(M)
(for any X in lI§c!P'+ (:MI)). The proof of these two non-trivial facts can be found in Chapter 1 of [4].
Suppose we have an algebra M and an alter ego :MI. Given an algebra A in JI§IP'(M) there is
a natural embedding from A to ED(A) which we call the evaluation map. The evaluation map,
denoted eA, is defined by
eA(a)(x) = x(a)
for every a EA and x E D(A).
An alter ego, :Ml, is said to yield a duality on some A in JI§IP'(M), if A is isomorphic to ED(A)
via eA. If, for every A E lI§IP'(M) we have A~ ED(A) via eA then the alter ego, :Ml, is said to yield
a duality on the algebra M. An algebra M is dualisable, if there is an alter ego :MI such that for
every algebra A in lI§IP'(M) we have that A is isomorphic to ED(A) via eA (refer to Figure 2.4).
E@--l!J
JI§IP'(M)
lI§c!P'+ (:MI)
Figure 2.4: Dualisability of an algebra.
From this, we see that in order to determine if an alter ego dualises the algebra A we must show
that eA is surjective. Therefore, to determine if an alter ego dualises the algebra M we must show
that for every A E JI§IP'(M) the embedding eA : A-+ ED(A) is surjective.
One of the first classes of algebras studied in duality theory was bounded distributive lattices
which were shown to be dualisable by Priestley [15, 16]. The authors of [1] define a bounded
18
distributive lattice, (L,/\, V, O, 1), to be such that
• (L, /\, v) forms a lattice;
• for all x in L we have x I\ 0 = 0 and x V 1 = 1; and
• for all x, y and z in L we have
x /\ (y Vz ) = (z/\y ) V (x /\z )
x V (y /\ z) = (zVy) /\ (xvz).
Priestley's bounded distributive lattice and its alter ego are noted in Example 2.2.3.
Example 2.2.3. [ 15, 16] The bounded distributive lattice,
M= ({0, 1} ;/\,V, 0, 1)
is dualised by
M = ({0, 1}; :S,5)
where :S is the partial order defined on {O, 1} with O :S 1 and g is the discrete topology. Given
LE JI§IP(M) the D(L) is all bounded lattice homomorphisms, while ED(L) is all order preserving
maps.
2.2.4
Theorems about Dualisability
In this section we state two theorems, both of which are used to prove the results in this document.
Two additional theorems are needed for the material in this document and they are stated in the
next section.
19
Theorem 2.2.1 (Duality Compactness Theorem). [4, 8] Let M be a finite algebra and let M be an
alter ego ofM that is of.finite type. JfM yields a duality on each.finite algebra in JI§IP'(M), then M
yeilds a duality on JI§IP'(M).
Theorem 2.2.1 is needed to prove the main technical theorem in this document (Theorem 3.4.2).
Before we introduce the next theorem we need the definition of an order ideal. Given a set K
partially ordered by ::;, a non-empty subset B of K is said to form an order ideal if for every b EB
and for all k E K with k ::; b then we have k is in the set B [ 1, 9]. This next theorem essentially says
that the lattice structure is essential for dualisability.
Theorem 2.2.2. [17] Let M be a {O, 1}-valued unary algebra with zero such that Rows(M) is
uniquely witnessed and forms an order ideal under O ::; 1. Then M is dualisable if and only if
Rows(M) is a lattice order.
The last theorem about dualisability is a corollary to Theorem 2.2.2. We use this corollary
throughout this document as we are working with sernilattices induced by a non-dualisable algebra.
However, as we shall see in Chapters 4, 5 and 6 we are able to extend these non-dualsable algebras
by adding particular operations that guarantee that the extension algebra is dualisable.
Corollary 2.2.3. [3] Let M be a {O, 1}-valued unary algebra with Osuch that row(O) is uniquely
witnessed. Assume that Rows(M) C {O, 1t forms a semilattice that is not a lattice. Then, M is
not dualisable.
2.3 Dualisability and Tangling
In this section we introduce the idea of tangled functions which is a concept introduced by the
authors of [3]. Essentially a tangled function is an operation that is missing from the operation
20
set of the algebra and that is needed for the algebra to be dualisable. In order to define a tangled
function we must first understand what it means for an algebra to be balanced. The author of [14]
uses the definition of horn-minimal to define balanced, a subalgebra A of Mn, for some finite n, is
said to be horn-minimal if the only homomorphisms from A to M are restrictions of projections
(that is if h: A--+ M then his the restriction of 7ri: Mn--+ M to A for some 1 :::; i:::; n). The author
further states that, if the algebra A is horn-minimal and 1ri fA# 7rJ fAfor i # j then A is said to be
balanced. With this knowledge we can now introduce the concept of tangling.
An algebra M = (M, F ) is said to tangle a unary function, h : M --+ M, if
1. M is not dualisable;
2. There is an A in IT§JP>(M) satisfying
(a) A is balanced (every homomorphism to Mis a unique projection map);
(b) there exists a yin ED(A) that is not an evaluation map eA (a) for any a EA;
(c) h : M--+ Mis the unique function for which there is ab EA such that for every x in
D(A) we have y(x) = h(x(b)).
We say F tangles h and write F /. h. Furthermore, we note that
1. Every A E IT§JP>(M) is isomorphic to a balanced algebra.
2. To be more specific about the quantification, the uniqueness of h means that for all g E MM,
and for every b EA, if for all x E D(A) we have g(x(b)) = y(x), then g = h.
Next we define a relation eu on M 2 . Let u E { 0, 1} v. We define the relation eu on M 2 so that
aeub if and only if u A row(a) = b.
21
This relation is used in the next theorem and gives a means for determining what unary operations
on Mare tangled. We refer to Theorem 2.3.1 throughout this document.
Theorem 2.3.1. [3 J Let M = (M, F ) be a {O, 1}-valued unary algebra with Osuch that row(O) is
uniquely witnessed by 0. Assume that Rows(M) C {O, 1}n forms a semilattice that is not a lattice.
Let hu be a function from M to M such that
1. hu ~ F;
2. hu (a) = b implies afJub;
3. the rows corresponding to range(hu) are uniquely witnessed.
Then F tangles hu.
22
Chapter 3
Join Upper Bounded Algebras
3.1
Introduction
This entire chapter looks at a specific type of algebra, M, which we call a Join Upper Bounded
Algebra. We define Join Upper Bounded Algebras in Section 3.2 and then proceed in Section 3.3
to describe some properties of Join Upper Bounded Algebras, such as the partial distributive law.
In Section 3.4 we state and prove the main technical theorem of this document, which is Theorem
3.4.2. We begin by defining a morphism a and subsets h and Bi of M that are needed for the
property in Theorem 3.4.2 which we call the Join Upper Bounded Algebra Morphism Property.
The Join Upper Bounded Algebra Morphism Property gives the necessary framework to show that
the morphism a is actually an evaluation map. This property is used to show that the algebras
described in Chapters 4, 5 and 6 are dualisable.
23
3.2 Join Upper Bounded Algebras
A finite unary algebra, M = (M ,F ), with Osuch that row(O) is uniquely witnessed by O and Fis
closed under composition, is said to be a Join Upper Bounded Algebra if there exists a partial
order :S on M such that the corresponding I\ and V satisfy:
1. I\ : M 2 -+ M is a homomorphism and a semilattice operation on M with least element O;
2. V is a partial algebraic operation on M that is not total; and,
3. if u, v, w EM such that u :S wand v :S w then u V vis defined.
The assumption that F is closed under composition is nonstandard but a convenient assumption.
This will always hold for {O, 1}-valued algebras, but not otherwise. If IMI < 3 then we have a
lattice and Mis dualisable. We therefore assume that the IMI 2:: 3. Given a Join Upper Bounded
Algebra, M = (M ,F ), we further define the following algebra
M * = (M , {f E F: f is {O, 1}-valued})
to be a {O, 1}-valued reduct of M. Furthermore, a {O, 1}-valued Join Upper Bounded Algebra
is a Join Upper Bounded Algebra that is {O, 1}-valued.
As Join Upper Bounded Algebras are algebras with O (a row and a column of zeros) there exists
a unary operation Jo in F such that for all x in M
fo(x) = 0.
This is the only constant function in F. Let f;d denote the identity map on M. From now on we fix
v =IF \ {fo ,!id} I and set
F \ {fo ,hd} = {!1 , · · · ,f v}.
24
3.3
Properties of Join Upper Bounded Algebras
Our goal in this section is to show that the rows of Join Upper Bounded Algebras respect meet
and join. We need these properties to prove the Join Upper Bounded Algebra Morphism Property
holds in Section 3.4.
Claim 3.3.1. Let M = (M, F ) be a Join Upper Bounded Algebra. For all a and b in M we have
row(a /\ b) = row(a) /\ row(b).
Proof As M is a Join Upper Bounded Algebra we know that I\ is a homomorphism with least
element 0. We will show that
row(a I\ b) = row(a) I\ row(b)
by proving that
row(a I\ b )i = [row(a) I\ row(b )]i
holds for every i with 1 :s; i :s; v. Recall that for any din M the row( d) is defined as (!1 (d) , . .. , fv( d)).
Therefore, for every i with 1 :s; i :s; v we have row(d)i = fi(d). Hence,
row(a I\ b )i = fi(a I\ b)
as I\ is a homomorphism and Ji E F
= f;(a) /\ fi(b)
= row(a)i I\ row (b )i
= [row(a) I\ row(b)]i.
So
row(a I\ b )i = [row(a) I\ row(b )]i
as needed. As this holds for all i with 1 :s; i :s; v we must have
row(a /\ b) = row(a) /\ row(b).
25
D
Claim 3.3.2. Let M = (M ,F ) be a Join Upper Bounded Algebra. For all a and bin M if a V b is
defined then
row(a V b)= row(a) V row(b).
Proof Since, by hypothesis, a V b is defined in M and as V is a partial algebraic operation on M
we know that
That is,
row(a V b)i = row(a)i V row(b )i = [row(a) V row(b)]i.
But this holds for all i, hence
row(a V b)= row(a) V row(b)
D
and we are done.
We say that a Join Upper Bounded Algebra satisfies the partial distributive laws if
1. whenever a Vb and a V c are defined then
(a V b) I\ ( a V c) = a V (b I\ c); and
2. whenever b V c is defined then
(a /\ b) V (a /\ c) =a /\ (b v c).
We note that when a Vb and a V c are defined, then as both
b /\ c~a V b ,
a~ a Vb;
b /\ c ~ a V c ,
a~a v c
26
and
hold, therefore by part 3 of the definition of Join Upper Bounded Algebras we know a V (b I\ c) is
in M. Similarly, if b V c is defined, then both
a I\ b ~ b ~ b V c
and
a /\ c ~ c~b V c
hold and by part 3 of the definition of Join Upper Bounded Algebras we know that (a I\ b) V ( a I\ c)
is in M. The next lemma shows that every {O, 1}-valued Join Upper Bounded Algebra with unique
rows satisfies the partial distributive laws.
Lemma 3.3.3. Let M = (M , F ) be a {O, 1 }-valued Join Upper Bounded Algebra with unique rows.
Let H be a collection of operations mapping the set M to itself. Furthermore, assume the operations
in H respect the I\ homomorphism and the partial V homomorphism defined on M. Then the
extension algebra, M' = (M , FU H ), satisfies the partial distributive laws.
Proof We will begin by showing that the partial distributive laws hold for the algebra M then
proceed to show they hold for M'. Note that M' forms an extension of M.
Let M = (M,F ) be a {O, !}-valued Join Upper Bounded Algebra with unique rows. Set
IF \ {fo ,hd}I = v. Suppose for a , b and c in M that a V b and a V care defined. We know that
{row(a) , row(b ), row(c)} <:: {O, 1 y. Furthermore, as both (a Vb) I\ (a V c) and a V (b I\ c) are de-
fined we know row( (a Vb) I\ (a V c)) and row(a V (b I\ c)) are in {O, 1 y. If we can show that
J;((a v b) /\ (a v c)) =f;(a V (b /\ c))
and therefore,
row( (a Vb) I\ (a V c) )i = row(a V (b I\ c) )i
holds for every 1 ~ i ~ v, then the Lemma holds for {O, 1}-valued Join Upper Bounded Algebras. But this follows as V and I\ are homomorphisms that commute with Ji, and as V and I\ are
27
distributive on {O, 1} (with order O < 1). That is,
Ji ( (a V b) I\ ( a V c)) = (Ji (a) V Ji (b)) I\ (Ji (a) V Ji (c))
as I\ and V are homomorphisms
= Ji(a) V (fi(b) /\ fi(c))
by distributivity on {0, 1}
= Ji (a V (b I\ c))
as I\ and V are homomorphisms.
This holds for all i and therefore we have
row((a V b) I\ (a V c)) = row(a V (b I\ c)).
Hence, by unique rows,
(a v b) I\ (a v c) = a v (b /\ c)
as needed.
To show (a I\ b) V (a I\ c) = a I\ ( b V c) we now assume a, b and c are in M and that b V c is
defined. Again, we note that both the row( (a I\ b) V (a I\ c)) and row( a I\ ( b V c)) are in {O, 1Y. If
we can show that
. fi((a /\ b) V (a /\ c))) =fi(a /\ (b V c))
and therefore,
row( (a I\ b) V ( a I\ c) )i = row( a I\ ( b V c) )i
holds for every 1 ::; i ::; v, then we would be done. Consider,
Ji ( (a I\ b) V (a I\ c)) = (Ii (a) I\ Ji (b)) V (Ii (a) I\ Ji (c))
as I\ and V are homomorphisms
= Ji(a) I\ (fi(b) V fi(c))
by distributivity on {0, l}
= Ji (a I\ ( b V c))
as I\ and V are homomorphisms.
This holds for every i and therefore we have
row( (a I\ b) V ( a I\ c)) = row( a I\ ( b V c)).
28
By unique rows,
(al\b)v(al\c) =al\(bvc)
as needed. Hence the algebra M satisfies the partial distributive laws. Therefore, all {O, 1}-valued
Join Upper Bounded Algebras with unique rows satisfy the partial distributive laws.
Now consider the extension M' = (M ,F UH) of M where His a collection of total operations
on M that respect both the I\ homomorphism and the partial V homomorphism defined on the
algebra M. Note that since the algebra M has unique rows the extension, M' will also have unique
rows. As the underlying set Mand both the I\ and V operations have not changed, M' also satisfies
the partial distributive laws.
Hence all Join Upper Bounded Algebras whose {O, 1}-valued reducts have unique rows, satisfy
D
the partial distributive laws.
Corollary 3.3.4. Let x, y E FU H with x o y ff. FU H, then x o y respects both the I\ homomorphism
and the partial V homomorphism.
In the following proof, we use the notation l\(a,b) instead of a l\ b. Both notations are equivalent and we switch between the two in this document.
Proof There are x and y in F UH with x o y not in F U H. Let (a, b) E M 2 , and consider,
(xoy)(l\(a,b)) =x(y(l\(a,b))
= x(l\(y(a) ,y(b))
by Theorem 4.2.1
= l\(x(y(a)) ,x(y(b)))
by Theorem 4.2.1
= l\((xoy)(a), (xoy)(b)).
So, x o y respects the I\ homomorphism.
29
Now, let (a, b) E M 2 such that a Vb = V(a, b) is defined in M. Consider,
(x oy)( v (a ,b)) =x(y(V(a ,b))
=x(V(y(a) ,y(b))
by Theorem 4.2.1
= V(x(y(a)) ,x(y(b)))
by Theorem 4.2.1
= V((x oy)(a) , (xoy)(b)) .
Therefore, when a Vb is defined in M then x o y respects the partial V homomorphism.
Hence x o y respects both the I\ homomorphism and the partial V homomorphism.
3.4
D
The Join Upper Bounded Algebra Morphism Property
In this section we present and prove the main technical theorem in this document. We refer to this
result as the Join Upper Bounded Algebra Morphism Property. The Join Upper Bounded Algebra
Morphism Property is used to show that certain algebras are dualisable in Chapters 4, 5 and 6.
Let M = (M,F ) be a Join Upper Bounded Algebra. Set
where
1. I\ and V are the algebraic operations in the definition of Join Upper Bounded Algebras,
2. ~ IMl2+IMI is the set of all algebraic relations of arity less than or equal to IMl 2 + IMI, and
3. G is a collection of endomorphisms defined on M (homomorohisms from M to itself). G
may be empty.
30
Pick A ~ Mn for some fixed positive n. Let X be the set of all homomorphisms from A to M,
denoted X = hom(A, M), and let a be any morphism from X to the alter ego MI. As A is finite the
set X is also finite. Enumerate the range of a as
range (a) = {i 1, i2 , ... , ik} ~ M
so that Irange (a) I = k. For all i E range (a) define
and, as I\ is an algebraic operation of MI we may define
Xi= j\X;.
Because a is a morphism and I\ is idempotent, for all i E range ( a) we have a(xi) = i. For all i in
the range of a, we define the following subsets of M:
Ii = {b E M : b I\ i = i} = {b E M : b ~ i}
and
B; = {b E /;: Vj E range(a) j /\b = j /\i}.
In the next lemma we show that for all i =I- j in range (a) we have Bin B j = 0. This ensures
that elements in B; and Bj are not mapped by the morphism a to two different places. Note further
that we are not requiring unique rows for Lemma 3.4.1.
Lemma 3.4.1. For all distinct pairs i, j in range (a) we have Bi n B j = 0.
Proof Let b be in Bi n B j, where i and j are in range (a). Recall that,
Bi = { b E /i : \Iv E range (a) v I\ b = v I\ i} ,
31
and,
B j = { b E lj : \/v E range (a) v A b = v A j}.
Since b is in Bi and because j is in range (a), it must hold that j A b= j A i. Similarly, because b
is also in B j and as, i is in range (a) we have i A b = j A i. Hence,
i A b=j A b.
But since bis in /i and Ij, it must hold that b Ai= i and b A j = j. Thus,
i=i A b=j A b=j.
Hence, Bi nBj -:f. 0 implies i = j, that is i -:f. j implies Bi nBj = 0.
D
We now define the subset Ao of A to be
Ao = {a EA : Vi E range (a) Xi (a) = i}.
Next, we state the main technical theorem of this document. This theorem will be used in
Chapters 4, 5 and 6. Notice that this theorem implies that Ao is non-empty.
Theorem 3.4.2. Let M = (M, F ) be a Join Upper Bounded Algebra that satisfies the partial distributive laws. For A a subalgebra of Mn, for some fixed positive n, let X = ham(A, M) and let a
be any morphism from X to M where
Here, G is a collection of endomorphisms defined on M. For all i E range (a) we define the sets
Xi, Ii and Bi and the element Xi as follows:
Xi={hE'X:a(h)=i} ,
32
and
Bi = {b E /i : Vj E range (a) j I\ b = j I\ i}.
We further define the set Ao to be,
Ao = {a E A : Vi E range (a)
Xi (a)
= i}.
Then there is an a in Ao such that for all j in range (a) the following holds
Theorem 3.4.2 is ilustrated in Table 3.1. From now on, we will refer to (*) as the Join Upper
Bounded Algebra Morphism Property.
Vb EAo
=iaEAo
a
z
z(b)
z(a)
a(z)
x·J
x1(b) = j
Xj(a) = j
a(x1) = j
y(b) E IJ
y(a) E Bj
a(y) = j
Table 3.1: The Join Upper Bounded Algebra Morphism Property.
The remainder of this section develops the proof of Theorem 3.4.2.
Lemma 3.4.3. Let /3 = {¢1 , z , . .. , z , ... , 1 , 2 , .. . , a)( a)
= (1 (a) , 2 (a) , ... , a (a)) .
Thus, as g is applied coordinate wise in Mcr,
g(d) = g(1 (a) ,2 (a) , ... ,a (a))
= (1 g (a) , 2g (a) , ... , a g (a))
as each i is a homomorphism and g E F
which is in lJI because g (a) is in A. Therefore, we have shown that for every operation gin F and
for every element din l/f, it holds that g(d) is in l/f.
D
Lemma 3.4.4. Let l/f = {(1 , 2 , ... , a)(a) I a EA}, where a :::; IMl 2 + IMI. For g1 , .. . ,ga E X,
if(g1 ,g2 , .. . ,ga) are lJl-relatedthen (a(g1) , a(g2) , ... , a(ga)) E l/f.
Proof By Lemma 3.4.3 we know that l/f is a subalgebra ofMcr. As l/f is in &i'IMl2+ IMI the morphism
D
a respects l/f.
Corollary 3.4.5. The set Ao = {a EA : \/i E range (a) Xi (a) = i} is non-empty.
Proof Set S = {(xi (a))iErange(a ) I a EA}. Then Sis a subset of M irange(a )I. Since for every i in
range (a) we have that the element Xi is in X, it follows from Lemma 3 .4.3 that~ is a subalgebra of
· fi es (x 1· (a )) iErange(a ) 1s
· m
· Sfor eac h am
· A we h ave (x 1·) iErange(a )
M lrange(a)I. A s (x 1·) iErange(a ) satls
are S-related. Furthermore, by Lemma 3.4.4, since !range ( a) I :::; IMI :::; IMl 2 + IMI , we have a
respects S. As (xi)iErange(a) are S-related we have (a(xi))iErange(a ) is in S. Therefore, since
(a(xi) )iErange(a ) = (i) iErange(a )
is in S, there exists a EA such that for all i E range (a) we have Xi (a) = i, as needed.
34
D
Lemma 3.4.6. Let w, x and z be in the set D(A) where w :S x. Then, wV (xl\z) is a homomorphism,
and w V (x I\ z) :S x.
Proof Recall that D(A) is the set of all homomorphisms from A to M, denoted hom(A ,M). Let
w, x and z be in the set D(A) where w :S x. As D(A) is in lI§cJP>+ (M) we know it is closed under
the total operation I\ and the partial operation V. To show that w V (x I\ z) is defined and therefore
a homomorphism, we must show that (w, (x I\ z)) is in the domain of V . Note that for all a E A we
have
w(a) :S x(a) as w :S x, and,
(xl\z)(a) :Sx(a) asx l\z :Sx.
As M is a Join Upper Bounded Algebra, it must hold that (w( a) , (x I\ z) (a)) is in the domain of V
for every a EA (by property 3 of Join Upper Bounded Algebras). Therefore, w V (x I\ z) is in the
set D(A), and is a homomorphism.
D
The next corollary follows directly from the previous lemma (take w = x l\y).
Corollary 3.4.7. Let x,y, and z be in the set hom(A ,M). Then, (xl\y) V (xl\z) is a homomorphism.
From now on, we enumerate and refer to the elements in X1 as y{
,lz, ... ,Ysr Note that for
all j with 1 :S j :S k and for all l with 1 :S l :S s J we have y{ E X1. For all l, as y{ 2: x J we have
y{ (a) 2: x1(a) = j soy{ (a) E 11 whenever a E Ao.
We now define a family of maps. For all i, j in the range of a, define z{ : A-+ M by
There are k2 such maps as Jrange (a) I = k. Also note that if i = j then z{ = xi.
35
Lemma 3.4.8. Let i and j be in range ( a). Each z{ is a homomorphism. Moreover, a(z{) = i I\ j.
Proof Recall that each of Xi ,Y{ ,Y~, . ... ,y{j are in hom(A , M). Furthermore, as Mis a Join Upper
Bounded Algebra we have the total operation I\ and the partial operation V with the property that
if a :S c and b :S c then a Vb is defined. We recursively define wk : A -+ M fork = 2, ... , s j. Set
and,
By Lemma 3.4.6 we know w2 E hom(A ,M) . By induction we get wk is well defined and in
hom(A ,M). Since Xi l\ y{ :S Xi and Xi l\ y~ :S Xi and using distributivity we have
Thus,
w3 = (xi I\ w2) V (xi l\ yi)
= (xi i\ ((xi l\ y{) v (xi l\ y~))) V (xi l\ yi)
= (xi l\ y{) V (xi A/z) V (xi l\ yi)
An inductive argument shows that
Since
we are done as we have shown that z{ is a homomorphism.
Before we show that a(z{) = i l\ j recall that a
(Yt) = j as yt E Xj, and as a is a morphism, it
respects both the I\ homomorphism and the partial V homomorphism on D(A).
36
Now consider
a(z{) = a(xi A y{) V a(xi A y~) V · · · V a(xi Ayi)
= ( i A a (y{)) V ( i A a (y~)) V .. . ( i A a (Yi))
as a is a homomorphism and A, V are in the alter ego
= i A j.
So a(z{) = i A j as needed.
D
Lemma 3.4.9. Let i, j E range (a). For all a E Ao we have z{ (a) 2: i A j. Furthermore, if z{ (a) = i A j
then Xi (a) A y{ (a) = i A j for all [ with 1 ~ l ~ s j·
Proof Let i, j be in range ( a) and let a be an element in Ao. Note that for all/ with 1 ~ l ~ Sj we
have y{ is in Xj and therefore y{ (a) 2: j. As Xi (a) = i, it must hold that for all / with 1 ~ l ~ sj
Xi
(a) A y{ (a) 2: i A j.
Since this holds for all/, with 1 ~ l ~ Sj, we must have
2: i A j.
So, z{ (a) 2: i A j as needed.
Now suppose z{ (a)= i A j. We therefore have,
z{ (a)= [ (xi A y{) V (xi A y~) V .. · V (xi Ay{)] (a)
= (Xi (a) A y{ (a)) V ( Xi (a) A y~ (a)) V ... V ( Xi (a) A y{j (a))
= i A j.
37
Since for all/ with 1 :::; l :::; Sj
Xi
(a) A y{ (a) 2 i A j
it must hold that x; (a) Ay{ (a) = i A j for all / with 1 :::; l :::; sj.
D
Vb E Ao
a
z
z(b)
a(z)
x;,
x; 1 (b) = i1
a(x;,) = i1
Xi2
x;i(b) = i2
a(x;1 ) = i2
y(b) E /; 1
a(y) = i1
y(b) E/;2
a(y) = i2
a(y) = ik
z{ (b) 2 i1 A j
a(z{) = i1 A j
zfz (b) 2 i2 A j
a(z{2 ) = i2 A j
Table 3.2: Homomorphisms of A and their behaviour on A 0 .
We now complete the proof of Theorem 3.4.2.
For a fixed j E range (a) we want to use the homomorphisms
38
zfi, ... ,z{k (see bottom of Ta-
ble 3 .2) to force the existence of an element a in Ao where for all y in X1 we have y (a) is in BJ. To
do this, let
2
By Lemma 3.4.3, we have SA is a subalgebra of Mk +k as lrange(a) I = k:::; IMI.
In fact,
k2 +k:::; IMl 2 + IMI. By Lemma 3.4.4, SA is closed under a. Since
there is an a EA with
Note that a is actually in Ao since Xi (a) = i for all i E range (a). We have therefore found an a in
Ao such that for each j in range (a)
z{, (a)= i1 !\ j ,
z{2 (a)= i2!\},
By Lemma 3.4.9, this means that for all l with 1 :::; l :::; s1, we have
Xi,
(a) !\y{ (a)= i1 !\ j ,
Xi 2
(a) !\ y{ (a) = i2 !\ j ,
39
But then, as Xi(a) = i for all [ with 1 ~ l ~ sj it must hold that y{ (a) is in B j· Therefore, for all yj
in Xj it follows that yj (a) is in B j as needed. This holds for all j in range (a). We have therefore
found an a in Ao where for all j in range (a) the following holds
This is illustrated in Table 3.3 and we have proved Theorem 3.4.2.
VbEAo
:la E Ao
a
z
z(b)
z(a)
a(z)
Xi1
Xi 1(b) = i1
Xi 1(a)= i1
a(x1 1 )=i1
Xi2
Xi 2(b) = i2
Xi2(a)= i2
a(x1 2) = i2
Xik(b)=ik
xda) = ik
a(x1k) = ik
y(b) Eli 1
y(a) E Bi 1
a(y) = i1
y(b) E li 2
y(a) E Bi2
a(y) = i2
a(y) = ik
Table 3.3: The Join Upper Bounded Algebra Morphism Property is depicted here showing the
existence of an a E Ao such that Vy E Xj y( a) E B j.
40
3.5
The Operation f( Defined on {O, 1}-Valued Join Upper
Bounded Algebras
Before we move on to dualisability results, we need one more property of {O, 1}-valued Join Upper
Bounded Algebras. We already know that Jo E F. In this section we show that if we have a {O, 1}valued Join Upper Bounded Algebra satisfying specific conditions, then there is another function
that exists either in F or that is tangled by F.
Lemma 3.5.1. Let M = (M, F) be a {O, 1}-valued Join Upper Bounded Algebra. Assume further,
that the row( 1) is not a repeated row. Let ft be the unary operation where for all x E M we have
Jt(x) =x !d.
!JO-< 1 in M then ft E F. However, if there exists an x in M with O < x < 1 and for every y with
0 ~ y ~ 1 we have the row(y) is not a repeated row, then F ,,<.. f(
Proof As M is a {O, 1}-valued Join Upper Bounded Algebra we know that A : M2 -+ M is a
semilattice homomorphism (with least element 0) on M. Therefore Jt(x) = x A 1 is defined on M.
Set IF\ {fo,Jid}I = v. There are two cases, namely the case when O-< 1 and when there exists
a x with O < x < 1.
Case 1: Suppose that O -< 1. Since O ~ x A 1 ~ 1, for all x in M we have x A 1 E {O, 1}.
Furthermore, since this holds for all x in M it follows that ft is a {O, 1}-valued unary operation
defined on M. We now show that there is an i with 1 ~ i ~ v and J;, E F \ {fo ,J;,d} with J;, = J(.
Since for all x in M we have x A 1 E {O, 1} we can rewrite M as the disjoint union of the
following two sets,
Mo={xEM :xA l=O}
41
and,
M1 = {x EM : x /\ 1 = 1}.
So M = M 1UMo. Enumerate M1 as m1 ,m2 , .. .. ,mµ. Note the following:
m1 /\ l = l
m2 I\ m 1 I\ 1 = m2 I\ (m 1 I\ 1) = m2 I\ 1 = 1
mµ I\ ··· I\ m1 I\ 1 = mµ I\ (mµ-1 I\ ··· I\ m1 I\ 1) = ... = mµ I\ 1 = 1
Therefore, as
mµ I\· ·· I\ m1 I\ 1 = 1
we must have
row(mµ I\· · · /\ m1 I\ 1) = row(l).
Moreover, as O-< 1 and the row(O) is not repeated there is an i with 1 :S: i :S: v with row(l)i = 1.
Hence
row(mµ I\·· · /\ m1 I\ l); = row(l)i = 1
and therefore
row(mµ)i /\· · · /\ row(m1)i /\ row(l)i= 1
by Claim 3.3.1. Hence for all j with 1 :S: j :S: µ we have row(mj)i = 1 (recall that for all m EM
we have row(m) E {O, 1}v). Furthermore, for all x E Mo we have row(x)i = 0. To see this, consider
x EMo. As
x i\ 1 = 0
we have
row(x I\ 1) = row(O)
42
therefore,
row(x A l)i = row(O)i = 0
hence,
row(x)i A row(l)i = 0
but, as row(l)i = 1 we have
row(x)i A 1 = 0.
Y it therefore holds that row(x)i = 0. This holds for all x E Mo.
Once again, as row(x) E {O, 1
To summarize, for all m E M1 we have row(m)i A row(l)i = 1 and for all m E Mo we have
row(m) i A row(l)i = 0. So we have found an operation ki in F with ki(x) = x A 1. Let ki = J{' and
we are done. So, when O -< 1 we have J{' E F.
Case 2: Now suppose there is an x in M with O < x < 1 and for every y with O :S; y :S; 1 we have
the row(y) is not a repeated row. We want to show that F ,/. J{'. Recall that we are assuming that
row(l) is not a repeated row. As O< x < 1 we must have x A 1 = x (/: {O, 1} so range(!{') cf:_ {O, 1}
and hence J{' (/: F. As row( 1) is not a repeated row, it follows that J{' = hu with u = row( 1) and
therefore by Theorem 2.3 .1 we have F ,/. J{' as needed.
From now on J{' will denote this particular function.
43
D
Chapter 4
Dualisability of Join Upper Bounded
Algebras with Unique Rows
In this chapter we define the tangled functions that are needed to ensure the dualisability of the
extensions of {O, 1}-valued Join Upper Bounded Algebras with unique rows. We end the chapter
with the proof that the extension is dualisable. This is done with the use of the Join Upper Bounded
Algebra Morphism Property.
4.1
Defining the Tangled Functions on {O, 1}-valued Join Upper Bounded Algebras with Unique Rows
We begin this section by finding the tangled functions on {O, 1}-valued Join Upper Bounded Algebras with unique rows. This knowledge is used in Theorem 4.3.2 to prove that a tangled extension
of a {O, 1}-valued Join Upper Bounded Algebra with unique rows is dualised by the alter ego M
44
where,
Recall the definition of tangling from Section 2.3 on page 21. Furthermore, when (M , F )
tangles a function h then we write F /.. h.
LetM be the underlying set of M . Given the tuple u E {O, 1}v, assume that for all x EM if there
is a b in M such that row(x) I\ u = row( b) then b is unique. We define the the unary function, hu,
by
hu (x) = the unique b EM, such that row(x) I\ u = row(b ).
Note that hu may be a partial operation. The next theorem is a restatement of Theorem 2.3.1 for
Join Upper Bounded Algebras.
Theorem 4.1.1. Let M = (M,F ) be a {O, I}-valued Join Upper Bounded Algebra with unique
rows. Let u E {O, 1? and assume hu is a total operation. Then if hu ~ F we have F /.. hu.
D
Proof Follows from Theorem 2.3.1.
For the tangled operation, hu, we always write hu in place of eu and hu(x) =bin place of x eu b
as we saw in Section 2.3 on page 22.
Throughout this section we assume that M is a {O, 1}-valued Join Upper Bounded Algebra
with unique rows. Set F \ {Jo ,hd} = {!1 , ... , f v}. Given u E {0, 1} v where u is the join of the rows
of elements in a subset N of M , we know that hu is tangled as long as hu is a total operation on M
and hu ~ F. We now show that hu is defined (Claim 4.1.3) and therefore tangled or in F. To show
this, we require Lemma 4.1.2 (found below) and recall Lemma 3.3.3 which shows that M satisfies
the partial distributive laws. That is, for x,y and z in M if xv (y /\z) and (x Vy ) I\ (x v z) are defined
then they are equal and, if x I\ (y V z) and (x /\ y) V (x I\ z) are defined then they are equal.
45
Y be such that hu is a total operation on M, and let a EM. If
Lemma 4.1.2. Let uo E {O, 1
0
u = uo V row(a) then hu is a total operation on M.
Proof Let uo E {O, 1Y such that hu0 is a total operation on M, and let a EM. Suppose that
u = uo V row(a). Let x EM. Since we are working in {O, 1}v, we have
row(x) I\ u = row(x) I\ (uo V row(a))
= (row(x) I\ uo) V (row(x) I\ row(a))
as row(x),u 0 ,row(a) E {O, IY
= (row(x) I\ uo) V row(x I\ a)
= row(b) V row(x /\a)
where hu0 (x) = b.
Since both band x I\ a are less than or equal to x (as row(b) = row(x) I\ uo ~ row(x), sob~ x), by
definition of a Join Upper Bounded Algebra there is a c in M such that c = b V (x I\ a). As M has
unique rows there is exactly one choice for c. Hence,
row(c) = row(b V (x/\a))
as V is a homomorphism on its domain.
= row(b) V row(x /\ a)
= row(x) /\ u
by the above
so, row(x) I\ u = row( c) and hence, hu (x) = c. Therefore, if u = uo V row( a) where a E M and hu0
is a total operation on M, then hu(x) is defined for all x EM.
D
We can now prove the following claim.
Claim 4.1.3. Let u = row (0) V row (x1) V · · · V row (xi) E {O, 1Y for some {x1 , ... ,xi} ~ M. Then
hu is a total operation on M.
Proof If i = 0 then u = row(O) and we have hu = Jo. Otherwise, let
u' = row (0) V row (x1) V · · · V row (x;_i) E {O, 1y.
46
By induction hu' is a total operation, and as u = u' V row(xi) by the preceding lemma we have that
D
hu is a total operation.
Example 4.1.1. Consider the algebra M = ({O, 1, 2, 3},!1 ,h ,!3,fo) where !1 ,h ,!3, and Jo are
all defined in Table 4.1. Note that hoo1 (where row(2) = 001), h101 (where row(3) = 101), and ho11
!1
h
!3
Jo
0
0
0
0
0
1
0
1
0
0
2
0
0
1
0
0
1
0
3
Table4.l: M= ({O, l , 2, 3},J1,h ,h,fo )
(where row(l) V row(2) = 011) are defined by Claim 4.1.3 and are therefore tangled functions
by Theorem 4.1.1. However, ifu = 110 (which is not the join of any of the Rows(M)) then hu is
undefined, as there is no b E M satisfying
u !\ row(3) = 110 /\ 101 = 100 = row(b).
This is illustrated in Table 4.2.
We also point out that how is not a tangled operation as horn = h E F. Furthermore, h
is actually the operation f t which we showed existed in Section 3.5. This is also depicted in
Table 4.2.
47
!1
h
h
Jo
ho01
h101
ho11
h110
horn= h
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
1
1
2
0
0
1
0
2
2
2
0
0
3
1
0
1
0
2
3
2
not defined
0
= ft
Table 4.2: {!1 ,h ,h,!o} tangles hoo1 , h101 , ho11 but does not tangle h110 nor horn-
4.2
The Tangled Operations Respect the Meet and Join Homomorphisms
In this section we show that the tangled operations, hu , respect both meet and join. This is important
as we would like extensions of {O, 1}-valued Join Upper Bounded Algebras with unique rows
where all the tangled operations are included, to still be Join Upper Bounded Algebras. If this
holds, then we can use the Join Upper Bounded Algebra Morphism Property.
Theorem 4.2.1. Let (M,F ) be a {O, 1}-valued Join Upper Bounded Algebra with unique rows. Let
u = V row( c) for some C ~ M. For all x, y E M the following holds:
cEC
1. hu(x l\y) =hu(x) l\ hu(y);
2.
if both x Vy is defined then hu(x Vy ) = hu(x) V hu(y).
Proof Let C ~ Mand letx,y be in M. To show hu(x l\y) = hu(x) l\ hu(Y) , let hu(x) = d1, hu(Y) = d2
48
and hu(x /\y) = d3. Then
row(d3) = row(x /\y) I\ u
= row(x) I\ row(y) I\ u
by Claim 3.3.1
= (row(x) I\ u) I\ (row(y) I\ u)
= row(di) I\ row(d2)
by Claim 3.3.1.
= row(d1 /\ d2)
Hence
implies d3 = di I\ d2 by unique rows. Therefore,
as needed.
To show hu(x Vy) = hu(x) V hu(Y) when both xVy and hu(x) V hu(Y) are defined, let hu(x) =di,
hu(Y) = d2 and hu(x Vy) = d3. Then
row(d3) = row(x Vy) /\ u
= (row(x)Vrow(y))/\u
by Claim 3.3.2
= (row(x) I\ u) V (row(y) I\ u)
= row(d1) V row(d2)
= row(di V d2)
by Claim 3.3.2.
Again using unique rows we have d3 = di V d2. Therefore,
as needed.
49
Thus, both the I\ homomorphism and the partial V homomorphism commute with the tangled
operation hu.
D
Let M = (M , F) be a {O, 1}-valued Join Upper Bounded Algebra and let
H = {hu: M-+
M: = V
u
row(a) for some M1 s;;;
M}.
a EM1
For h E H we note that either h E F or F ,,<., h. We make this distinction as hrow(O) E H but
hrow(O) = Jo E F. Furthermore, if O -< 1 then hrow( 1) E H but h = hrow( 1) = f t E F.
Given an algebra, M = (M ,F ) we would like the extension algebra, M' = (M ,FUH) to still be
a Join Upper Bounded Algebra. For this to be true, we need the operation set FU H to be closed
under composition. Unfortunately, this is not always the case. In Theorem 4.2.2 we see that when
0 -< 1 then F UH is closed under composition. However, in Example 4.2.1 we see that when there
is an x in M with O < x < 1, then F UH is not guaranteed to be closed under composition.
Theorem 4.2.2. Let M = (M ,F ) be a {O, 1}-valued Join Upper Bounded Algebra with unique
rows such that O-< 1. The operation set F UH where,
H = {hu: M-+M: u =
V row(a)forsome M1 s;;; M}
a EM1
is closed under composition.
Proof To show FU H is closed under composition, there are three cases to consider:
1. both Ji and Jj are in F;
2. both hu and hv are in HU {fo , f ( };
3. hu E HU {foJt } and Ji E F.
50
If both ft and Jj are in F then ft o Jj E F as M is a Join Upper Bounded Algebra and hence F
is closed. Suppose hu and hv are in HU {Jo,!(}. Then
u=
Vrow(a)
a EA
and
v=
V row(b)
b EB
for some A ,B ~ M. Consider,
u l\ v =
Vrow(a) I\ Vrow(b)
a EA
b EB
= V V(row(a) l\ row(b))
a EAb EB
= V Vrow(a l\ b)
a EAb EB
= Vrow(c)
cE C
where C = {a I\ b : a EA , b E B}. As C ~ M we have hu/\v E H. All that is left to show is
that hu ohv = hu/\v· Let x EM and consider hu(hv(x)). Suppose hv(x) = c and hu(c) = b. Then
hu(hv(x)) = b. We have
row(x) I\ v = row(c)
and
row(c) I\ u = row(b).
So
row(x) I\ v I\ u = row(b);
but that means that for all x we have hu/\v (x) = b = hu(hv(x)). Therefore, hu o hv EH as needed.
Finally, suppose hu E HU {Jo,!( } and J; E F. We must show that both ft o hu and hu o J; are in
F UH. For the v-tuple, k E {O, 1}v we will use the notation k; to denote the ith coordinate of k. To
51
show Ji o hu E FU H let hu (x) = b, and consider,
f;(hu(x)) = f;(b)
= row(b)i
= row(x)i I\ Ui
= J;(x) I\ u; .
If Ui = 0 then f;(hu(x)) = 0 (for every x) and hence Ji ohu = Jo E F. If ui = 1 then Ji(hu(x)) = J;(x)
(for every x) and hence f; o hu = f; E F . Therefore, f; o hu E F UH. To show hu o Ji E F UH recall
that Ji is a {O, 1}-valued function. As O-< 1 there are two choices for hu(l), namely hh(l) = 1
or hu(l) = 0. If not, then there is ab~ {O, 1} with hu(l) =band therefore u I\ row(l) = row(b).
But this implies row( b) < row( 1) which is a contradiction as O -< 1. Therefore, hu ( 1) E { 0 , 1}. If
hu(l) = 0 then as hu(O) = 0 we have hu(fi(x)) = 0 for every x. Therefore, hu o Ji= Jo E F. If
hu(l) = 1 then as hu(O) = 0 we have
and
hu(f;(x)) = 1 if f;(x) = 1.
So hu(f;(x)) = J;(x) for every x, and hence hu o Ji= f; E F. In any case hu o f; E F, and we have
that FU H is closed under composition.
Therefore, when O -< 1, the set F U H is closed under composition.
D
If O is not covered by 1, then the set FU H may not be closed under composition as seen in the
next example. The problem that arises is that hu ( 1) is not guaranteed to be in {0, 1}. This problem
affects the composition hu of;.
52
Example4.2.1. Consider the Join Upper Bounded Algebra, M= (M ,F ) = ({0, 1, 2, 3,4} ,
{fo,!1 ,h,!4} ) as defined in Table 4.3. The tangled operations defined on Mare
H = { hrow(2), hrow(4), hrow(3), hrow(l), hrow(2)Vrow(4), hrow(2)Vrow(3)} ·
The operations in H can be found in Table 4.3. We note that for all i, j E {1 , 2, 3,4} neither
Jo !1 h !3 f4
hrow(2) hrow(4) hrow(3) hrow( J) hrow(2)Vrow(4) hrow(2)Vrow(3)
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
1
2
0
3
1
2
3
2
0
0
1
0
0
2
0
2
2
2
2
3
0
0
1
1
0
2
0
3
3
2
3
4
0
1
1
0
0
0
4
0
0
4
4
Table 4.3: The algebra, M along with the tangled operations defined on M.
hrow(3) o Ji nor hrow(2) o fJ are in FU H. These operations can be found in Table 4.4. To simplify
the notation, we use h~ to represent hrow(a) and h~b to represent hrow(a)vrow(b)
From now on we will assume that the operations of the algebra M' are closed under composition. By Corollary 3.3.4 if we assume FU H is closed under composition, it still holds that the
operations in FU H respect both the I\ homomorphism and the partial V homomorphism.
In the next theorem we show that the extension algebra, M' = (M , FU H) is still a Join Upper
Bounded Algebra.
Theorem 4.2.3. Given a {O, 1}-valued Join Upper Bounded Algebra with unique rows, M = (M, F) ,
let the extension algebra be M' = (M ,FUH), where
H = {hu: M --t
M: = V
u
row(a)for some M1 S:
a EM1
53
M}.
h 3 of4
h2 of3
h2 of4
h2 of1
h3of1
h23 °h
h3 0!3
h23 0 f3
h23 ° f4
hi.40!3
h24 ° f4
h24 0 Ji
h23 ° !1
h2 oh
hi.4 °12
0
0
0
0
0
0
0
0
0
1
3
3
3
2
2
0
0
2
2
3
0
0
0
0
0
0
2
3
3
3
0
2
0
0
0
2
4
3
0
0
0
0
2
3
2
h3oh
Table 4.4: The above compositions cannot be found in F UH. The set F UH is therefore not closed
under composition.
We assume FU H is closed under composition. Then M' is a Join Upper Bounded Algebra with
unique rows.
Proof Let M = (M , F ) be a a {O, 1}-valued Join Upper Bounded Algebra with unique rows. Recall
the existence of the operation Jo along with the fact that row(O) is uniquely witnessed by 0. This
holds as Join Upper Bounded Algebras have a row and a column of zeros. Consider the algebra,
M' = (M, FU H) where,
H=
{hu:
M --"7
M: = V
u
row(a) for some Mi
~ M}
a EM1
and recall that hu(x) = b if and only if
row(x) /\ u = row(b).
But this means that hu(O) = 0 for every hu EH. Therefore, the row(O) still exists in the Rows(M'),
moreover, as rowM(O) is uniquely witnessed by Owe have rowM' (0) will be uniquely witnessed by
0. So M' is an algebra with zero. By Theorem 4.2.1 we know that
I\: M 2 --"7 M
54
is a total algebraic operation on M' and
2
V :M -+M
is a partial algebraic operation on M'. As, every tangled function in H respects both the total
operation I\ and the partial V operation, the extension algebra M' will inherit the following property
of the algebra M: if a, b ::; c in M then a Vb is in M.
Finally, in order for M' to be a Join Upper Bounded Algebra, F UH must be closed under
composition. But, we assume this. Thus M' is a Join Upper Bounded Algebra; but as M has
unique rows, so does M' and therefore M' is a Join Upper Bounded Algebra with unique rows.
4.3
D
Dualisability of Tangled Unary Algebras with Unique Rows
In this section the {O, 1}-valued Join Upper Bounded Algebras with unique rows are denoted M.
The notation NM denotes an algebra obtained by extending M to NM to include all tangled functions. In this section we show that when all tangled functions are included, the algebra NM is
dualisable.
As Join Upper Bounded Algebras form semilattices that are not lattices, we know by Theorem 2.2.2 that the algebra will not be dualisable and we can therefore have tangled functions.
Theorem 4.3.1. Let M = (M, F) be a {O, 1}-valued Join Upper Bounded Algebra such that M has
unique rows. If IMI 2 3 then M is not dualisable. Moreover there exists an i EM with F A hrow(i) ·
Proof Suppose the IMI 2 3. As Rows(M) of a Join Upper Bounded Algebra form a sernilattice
but not a lattice, by Theorem 2.2.2 the algebra M is not dualisable. By assumption IMI 2 3, and
55
therefore there exists some i in M with i =I= 0 and i =I= 1. As M is a {0, 1}-valued unary algebra with
zero we have F A hrow(i) and range(hrow(i)) 7= {O, 1}.
D
Let M = (M , F) be a {O, 1}-valued Join Upper Bounded Algebra with unique rows. In the next
theorem we show that if you extend M to NM by including all the tangled functions of the form hu
where
Y
u = row (x1) V · · · V row (xi) E {O, 1
for some {x 1 , ... , Xi} ~ M , then NM is dualised by :Ml = (M , I\, V, 0, ~ IMlz+IMI, !Y).
Theorem 4.3.2. Suppose M = (M,F ) is a {O, 1}-valued Join Upper Bounded Algebra with unique
rows. Let
H = {hu: M----+
M:
u=
V row(a)for some M1 ~ M}.
a EM1
Assume that the operations set F UH is closed under composition. Then NM = (M , FU H ) is
dualised by :MI = (M,/\, v, o,~IMl2+1MI, !Y).
Recall that for every h in H we have either h E F or F ,< h. To prove Theorem 4.3 .2 we will
use the Join Upper Bounded Algebra Morphism Property with G = 0 in the alter ego,
Proof Assume that the operations set F U H is closed under composition. Set
Since NM is finite, by the duality compactness theorem [4, 8], it is sufficient to show A~ ED (A)
for every finite A E li§lJJ> (NM )- Pick A ~ (NM )n, and let X = hom(A, NM). We want to show that
each morphism a : X----+ :MI is an evaluation at some a E A. We do this by considering each possible
range ( a).
56
Suppose range ( a) = {i 1, ••• , ik} . Set X; = a-l (i) for i in range ( a). Let Xi= /\Xi. Define
Ao= {a EA: Vi E range(a) Xi(a) = i}. We want to find an a E Ao with a= eA (a). As NM is
a Join Upper Bounded Algebra with unique rows (by Theomem 4.2.3 and the assumption that
FU H is closed under composition) and as the algebra also satisfies the partial distributive laws
(Lemma 3.3.3) we know that NM satisfies the Join Upper Bounded Algebra Morphism Property of
Theorem 3.4.2. There is therefore an a in Ao where for every j in range ( a) the following holds:
Recall that B j = {b E /i : Vj E range (a) j I\ b = j I\ i} and Ii = {b E M : b 2: i}. Now, let
Vb EAo
:la E Ao
a
hu(a)
z(b)
z(a)
a(z)
z(hu(a))
i2
i2
i2
i2
y E Xi,
y(b) E Ii,
y(a) E B; 1
i1
i1
yEX; 2
y(b) E/i2
y(a) EBi2
i2
i2
z
Table 4.5: a is an evaluation at a E Ao (a= eA(hu(a))).
k
u=
V row(iv ), that is, u =
V=I
V
row(j). We shall see that a= eA (hu(a) ). This is illustrated
j Erange(a )
in the Table 4.5.
To show that a= eA(hu(a)), pick i in range (a) and z in X;. Then z(a) is in Bi (by Join Upper
57
Bounded Algebra Morphism Property) and z(a) tj. Bj for j =/- i. Let b = z(a). We know a(z) = i.
We have
(hu(a))(z) = z(hu(a)) = hu(z(a)) = hu(b)
and
a(z) = i ,
so to show that a is an evaluation, it suffices to show hu (b) = i; or equivalently,
As b E B; we have j I\ b = j I\ i for all j E range ( a). Therefore, as u E {O, 1} IF\ {fo,J;d} I and
rowM(i) E {O, l} IF\ {fo,J;d} I for all i in range(a) we have,
u/\rowM(b) = [
V
rowM(j)] /\ rowM(b)
j Erange(a )
V (rowM(j) I\ rowM(b)) by distributivity in {O, 1} IF\ {fo,J;d} I
j Erange(a )
V rowM(j /\ b)
by Claim 3.3.1
j Erange(a )
V
rowM(j I\ i)
as j I\ b = j I\ i
(rowM(j) I\ rowM(i))
by Claim 3.3.1
rowM(j)] I\ rowM(i)
by distributivity in {O, 1} IF\ {fo,J;d} I
j Erange(a )
V
j Erange(a )
= [
V
j Erange( a )
= u I\ rowM(i)
as i E range(a) and u =
V rowM(j),
j Erange(a )
so rowM(i) ::; u. Hence, u /\ ro~(b) = rowM(i) and therefore hu(b) = i EM. This holds for all
b EB; and for all i in range ( a). Therefore, a(z) = i = hu(z(a)) for all i in range ( a) and z in X;.
58
k
Thus, a = eA ( hu (a)), where u =
V row( iv) and we can conclude that a is an evaluav= l
tion. This holds for every possible range (a). We have therefore shown that each morphism
a : X -+ MI is an evaluation at some a E A. Therefore, NM is dualisable and we have proved
D
Theorem 4.3.2.
59
Chapter 5
Join Upper Bounded Algebras with
Repeated Rows
In this chapter, we look at the dualisability of the extensions of two specific types of { 0, 1}-valued
Join Upper Bounded Algebras with repeated rows, namely non-one-doubled-algebras (Section 5.2)
and one-doubled-algebras (Section 5.3). An example of a dualisable non-one-doubled-algebra is
given in Chapter 6.
5.1
{O, 1}-valued Join Upper Bounded Algebras with
Non-Unique Rows
Here we define two different types of Join Upper Bounded Algebras with non unique rows which
we refer to as non-one-doubled-algebras and one-doubled-algebras. For both of these algebras we
make the assumption that O is not a repeated row so that we can invoke Thereom 2.3.1 when talking
60
about the tangled functions of the algebras.
Suppose M = (M, F) forms a { 0, 1}-valued Join Upper Bounded Algebra that satisfies the
following:
1. There exist b1, b2 in M with b1 =/= b2 such that
(a) row(b1) = row(b2),
(b) either 1 ff: {b1,b2} orb1 = 1,
(c) 0 < b1 -< b2, and
(d) row( c) =/= row(b1) for any c =/= { b1, b2} in M;
2. There does not exist an x E M with b2 < x; and,
3. M\ {b 2} forms a sub-sernilattice of M;
4. The restricted algebra, (M \ {b2} ,FIM\ {bz}), forms a Join Upper Bounded Algebra with
unique rows.
5. ForeveryX~M \ {b1 , b2}wehave V row(x)/row(b1).
x EX
We refer to such an algebra as a (b 1 , b2 , ::;) -Join Upper Bounded Algebra. Furthermore, a
(b1 ,b2 , :S:)-Join Upper Bounded Algebra where b1 =/= 1 and b2 =/= 1 is called a non-one-doubled-
algebra once b 1, b2 and :S: are fixed. If 1 is a repeated row and we have b1 = 1 (i.e. 0 -< 1 < b2)
then we call the (l , b2 , :S:)-Join Upper Bounded Algebra a one-doubled-algebra once b2 and :S:
are fixed. Since (b1 ,b2 , :S:)-Join Upper Bounded Algebras form sernilattices that are not lattices,
we know by Theorem 2.2.2 that the algebra will not be dualisable. We now look at some examples
and non-examples of both non-one-doubled-algebras and one-doubled-algebras.
Example 5.1.1. An example of a non-one-doubled-algebra is given in Figure 5.1.
61
M
!1
h h
f4
Jo
0
0
0
0
0
0
1
0
0
1
0
0
b1
0
0
0
1
0
b2
0
0
0
1
0
5
0
1
1
0
0
6
1
0
1
0
0
6
b2
1
b1
0
Figure 5.1: An example of a non-one-doubled-algebra.
Example 5.1.2. An example of a Join Upper Bounded Algebra that is not a non-one-doubledalgebra is given in Figure 5.2. The algebra fails to be a non-one-doubled-algebra as there exists
an element, 6, with 6 -=I= b2 and b2 < 6.
Example 5.1.3. An example of a one-doubled-algebra is given in Figure 5.3.
Example 5.1.4. An example of a Join Upper Bounded Algebra that is not a one-doubled-algebra
is given in Figure 5.4. The algebra fails to be a one-doubled-algebra as the element b was chosen
to be less than the element 1 in the semilattice induced by the algebra. For this algebra to be a
one-doubled-algebra we would need 1 < b.
Let M = (M, F ) be a (b1 , b2 , ::;)-Join Upper Bounded Algebra. Our goal is to show that extensions of (b1 ,b2 , ::;)-Join Upper Bounded Algebras satisfy the Join Upper Bounded Algebra
Morphism Property. Therefore, we begin by showing the extension algebra is still a Join Upper
Bounded Algebra and that it satisfies the partial distributive laws (Corollary 5.1 .3).
Lemma 5.1.1. Let M = (M, F) be a (b1 , b2 , ::;)-Join Upper Bounded Algebra. Let H be a collection
of unary operations that respect the A homomorphism and the partial V homomorphism defined
on M. Then for the extension algebra given by M' = (M , F UH ),for all a,b ,c EM whenever b V c
62
M
J1
h h
J4
Jo
0
0
0
0
0
0
1
0
1
0
0
0
2
1
0
0
0
0
b1
0
1
1
0
0
b2
0
1
1
0
0
5
1
1
0
0
0
6
0
1
1
1
0
6
b2
2
0
Figure 5.2: An example of a Join Upper Bounded Algebra that is not a non-one-doubled-algebra.
M
J4 h h
Jo
0
0
0
0
0
1
0
1
1
0
2
0
1
0
0
b
0
1
1
0
4
1
0
0
0
5
1
1
0
0
b
4
0
Figure 5.3: An example of a one-doubled-algebra.
M
J1 h h
Jo
0
0
0
0
0
1
1
0
0
0
2
0
1
0
0
b
1
0
0
0
4
0
1
1
0
1
4
b
0
Figure 5.4: A non-example of a one-doubled-algebra.
63
is defined, then
(a /\ b) V (a /\ c) =a /\ (b V c).
Proof Let a, b, c E M and assume b V c is defined. Note that when b V c is defined then a I\ ( b V c)
is defined. Since both a I\ b and a I\ c are below a I\ ( b V c) then (a I\ b) V (a I\ c) is defined by
property 3 of Join Upper Bounded Algebras. In order to show that
(a /\ b) v (a/\c) =a /\ (b V c)
there are three cases that we will need to look into:
1. b = b2,
2. c = b2, and
3. b, C Et { bz}.
In this proof the following properties of (b1 , b2 , :S)-Join Upper Bounded Algebras are frequently
used:
• we assume O < b1 -< b2;
• the rows of M \ { b2} are unique and form a sub-semilattice;
• for every X ~ M\ {b2} we have V rowM(x) "j rowM(b1) = rowM(b2).
xEX
Case 1: Assume b = bz. Then b V c = b2 V c is defined only if b2 V c = b2 and therefore we have
64
c ~ b 2. As c ~ b2 it follows that a I\ c ~ a I\ b2 and therefore,
(a I\ b) V ( a I\ c) = (a I\ b2) V ( a I\ c)
= a /\ b2
=a /\ (b2 V c)
=a /\ (b v c)
as needed.
Case 2: Assume c = b2. This is symmetric to Case 1.
Case 3: Assume b , c t/: {b2}.
(a /\ b) V (a /\ c) =a /\ (b v c)
follows from Lemma 3.3.3 and property 4 of (b1 , b2 , ~ )-Join Upper Bounded Algebras as M\ { b2}
is a Join Upper Bounded Algebra with unique rows.
If a E { b2} then we note the following:
a I\ b < a = b2 as b t/: {b2} and,
a I\ c < a as c ft. {b2}.
Therefore,
(a /\ b) V (a /\ c) < a
by property 5 of (b1 ,b2 , ~)-Join Upper Bounded Algebras. Also,
a /\ (b v c) < a
as b V c tJ: {b2} by property 5 of (b1 , b2 , ~)-Join Upper Bounded Algebras. Therefore the elements
(a I\ b) V (a I\ c) and a I\ ( b V c) are in M \ { b2}. Let d = a I\ ( b V c). And consider the following
65
calculations:
d /\ c= (a /\ (b v c)) /\ c
=a /\ (c /\ (b v c))
= a /\ c
as C :'.S b VC
and,
d /\ b= (a /\ (b V c)) /\ b
=a /\ (b /\ (b v c))
as b :'.S b V c.
= a /\ b
Therefore, d I\ c = a I\ c and d I\ b = a I\ b. Furthermore, consider
d /\ (b v c) = (a /\ (b Vc)) A (b v c)
=a /\ (b v c) /\ (b v c)
=a /\ (b V c)
=d.
Sod I\ (b V c) = d. As d ,c,b EM \ {b 2 }, which has unique rows, we know that
(d /\ b) V (d /\ c) =d /\ (b v c).
But we have
a /\ (b v c)=d
=d /\ (b v c)
= (d /\ b) V (d /\ c)
= (a /\ b) V (a /\ c).
66
So
(a/\b) V (a/\c) = a /\ (bvc)
when a E {b2} and c,b (/: {bz}.
In any case, we have
(a/\b)V(a/\c) =a /\(b Vc)
D
and we are done.
Lemma 5.1.2. Let M = (M, F ) be a (b 1 , b2 , s)-Join Upper Bounded Algebra. Let H be a collection
of operations that respect the /\ homomorphism and the V partial homomorphism defined on M.
Then for the extension algebra given by M' = (M, FU H ), for all a , b, c E M whenever a V b and
a V c are defined, then
(avb)/\(avc)=aV(b/\c).
We note here that when a V b and a V c are defined, then as a S a V b and b /\ c S b S a V b we
have by property 3 of Join Upper Bounded Algebras that a V (b /\ c) is in M.
Proof Let a, b , c EM and assume a V b and a V care all defined. In order to show that
(avh)/\(avc) =a V( b /\c)
there are two cases that we will need to look into:
1. a= b2, and
2. a(/: {b2}.
In this proof the following properties of (b 1, b2 , s)-Join Upper Bounded Algebras are frequently
used:
67
• the rows of M \ { b2} are unique and form a sub-semilattice; and,
• for every X ~ M \ {b2} we have V row(x) j:. row(b1) = row(b2).
xEX
Case 1: Assume a= b2. Then we have
as a Vb is defined and hence b :S b2; and,
as a V c is defined and therefore c :S b2 . Since both b and c are less than or equal to b2 we know
that b I\ c :S b2. Hence,
as a V (b I\ c) is defined and b I\ c :S b2. But then
=a V (b /\ c)
and we are done.
Case 2: Assume a~ {b2}. There are three cases.
Ifwe have band care also not in {b2} then as av (b /\ c) ,a v b ,a V care not in {b2} by property
5 of (b 1,b2 , :S)-Join Upper Bounded Algebras. Therefore, as M \ {b2} has unique rows, equality
will hold and we are done.
68
Suppose exactly one of b or c is in {b2}. Without loss of generality, assume b E {b2}. Note
that (a Vb) A (a V c) is not in {b2} as a V c is not in {b2}. Let
d= (a Vb) A (a Vc)
and consider the following:
d A a= (a v b) A (a v c) Aa
=(a v b) A a
as a V c is defined and a ::; a V c
=a
as a Vb is defined and a ::; a V b
and,
d A c= (a v b) A (a v c) Ac
as a V c is defined and a::; a V c
=(a v b) Ac
=b A c
as b E { b2} and therefore a Vb= b.
Note that the elements d ,a, c, (d A a) V (d A c) ,d A (a V c) are not in {b2}. Therefore, by unique
rows
(d Aa) V (d Ac) =d A (a Vc).
Hence,
a V (b Ac) = (d Aa) V (d Ac)
=d A (a v c)
= (a v b) A (a v c) A (a v c)
= (a v b) A (a v c)
and we are done.
69
Finally, suppose both band care in {b2}. Then b = b2 = c and we have
a V (b J\ C) = a V (b2 J\ b2)
=a V b2
= b2
as a V (b J\ c) is defined and therefore a V b2 is defined
= b2 J\ b2
= (a V b2) J\ (a V b2)
= (a v b) J\ (a v c)
as needed. Therefore, (a V b) J\ (a V c) = a V (b J\ c) when a~ { b2}.
In every case, we have
(a v b) J\ (a v c) =a V (b J\ c)
D
and we are done.
Corollary 5.1.3. All extensions of (b1 , b2 , ~ )-Join Upper Bounded Algebras, where the operations
de.fined on the algebra respect both the J\ homomorphism and the partial V homomorphism, satisfy
the partial distributive laws.
D
Proof Follows from Lemmas 5.1.1 and 5.1.2.
As both non-one-doubled-algebras and one-doubled-algebras are (b1 , b2 , ~)-Join Upper Bounded
Algebras, by Corollary 5.1.3 they also satisfy the partial distributive laws. Therefore, by Theorem 3.4.2 both non-one-doubled-algebras and one-doubled-algebras have the Join Upper Bounded
Algebra Morphism Property.
Recall that for a {O, 1}-valued finite unary algebra with zero, where row(O) is uniquely witnessed by 0, if u E {O, l} v where v =IF \ {fo,Jid} I, then the unary operation hu is defined as
70
hu(x) = b when row(x) I\ u = row(b).
Corollary 5.1.4. If M is a (b 1, b2, ':::)-Join Upper Bounded Algebra then eu is a total operation
when
u = row(xi) V · · · V row(xk)
for {xi ,x2 , ... ,xk} ~ M \ {bi , b2}. Moreover, bi , b2 ~ range(hu).
Proof Let M be a (b1 ,b2 , ':::)-Join Upper Bounded Algebra and let {x1 ,x2 , ... ,xk} ~ M \ {b1 ,bz}.
We want to show that hu is a total operation on M when u = row(x1) V · · · V row(xk). Let
N = M \ {b2} and set N = (N ,F rM\ {bz }) . Then by definition of (bi ,b2 , ':::)-Join Upper Bounded
Algebras we know that N is a {O, 1}-valued Join Upper Bounded Algebra with unique rows. For
x EM, define the sets Sx and Tx by
Sx = {a EN: u /\ row(x) = row(a)}
and,
Tx = {a EM: u /\ row(x) = row(a)}.
By Claim 4.1.3 we know that that hu rN is a total operation and therefore for each x EN the set Sx
is a singleton. Thus, for x EN the set Tx is either Sx or Sx U { b2}.
Let x EN \ {bi}.
By Property 5 of (b1 ,b2 , ':::)-Join Upper Bounded Algebras, for each
x EN\ { bi} the row(x) i row(b2) and therefore, b2 ~ Tx and we have Tx is a singleton.
For b = bi the equality u I\ row(bi) = row(b2) implies that u ~ row(b1) as row(b1) = row(b2).
But this contradicts Property 5 of (b1 , b2 , '::: )-Join Upper Bounded Algebras and thus, b2 ~ Tb 1 • So
nl is a singleton.
The last part to show is that Tb 2 is a singleton as well. Let c E Tb 1 then u I\ row( b I) = row( c) .
As row(b1) = row(b2) this means that u I\ row(b2) = row(c) and hence c E Tb 2 and we have Tb 2 is
71
non-empty. However, we note that for all a E M, we have
u A row(b1) = row(a)
if and only if
u A row(b2) = row(a).
But this implies that Tb 1 = Tb 2 • As Tb 1 is a singleton, it follows that
n is a singleton.
2
Therefore, as each Tx for x E M is a singleton, hu is a total operation on M.
D
Theorem 5.1.5. Let M = (M,F ) be a (b1 ,b2 , 5:)-Join Upper Bounded Algebra and define
H = { Vrow(v): C ~ M \ {b1 , b2}}.
vE C
Then for all v E H, if hv ~ F then F ,I.. hv.
Proof Follows from Corollary 5.1.4 and Theorem 2.3.1.
D
In the next example we use Corollary 5.1.4 and Theorem 5.1.5 to look at an operation that is
tangled by a non-one-doubled-algebra and an operation that is not tangled.
Example 5.1.5. For the algebra M = ({O, l , b1 , b2 , 5,6} , {fi ,h ,h,f4,fo} ) defined in Table 5.1
we have h1110 is a tangled operation while ho011 is not.
It is possible to have a Join Upper Bounded Algebra where no tangled functions of the form hu
are defined. This is portrayed in Example 5.1.6.
Example 5.1.6. For the algebra M = ({O, l ,b1 , b2} , {fi,h,Jo} ) defined in Table 5.2 there are no
tangled operations of the form hu.
We now show that the tangled functions defined on (b1, b2 , 5:)-Join Upper Bounded Algebras
respect the A homomorphism and the partial V homomorphism.
72
M
J1
h 13 J4
Jo
hrow(5)Vrow(6) = h1110
hrow(1)Vrow(b 1) = hoo11
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
1
b1
0
0
0
1
0
0
b1 or b2
b2
0
0
0
1
0
0
b1 or b2
5
0
1
1
0
0
5
1
6
1
0
1
0
0
6
1
Table 5.1: Tangled and non-tangled operations
M
Jo
J1
h
0
0
0
0
1
0
1
0
b1
0
0
1
b2
0
0
1
Table 5.2: An algebra with no tangled operations of the form hu.
73
Theorem 5.1.6. Let (M ,F ) be a (b1 ,b2 , "5:. )-Join Upper Bounded Algebra. Let u = V row(c) for
cEC
some C s:;; M \ {b 1, b2}. If hu is a total operation then for all x , y E M the following holds:
I. hu(x A y) = hu(x) A hu(y); and
2. ifx V y is defined, then hu(x V y) = hu(x) V hu(y).
Proof Note that hu(x) "5:. x "5:. x V y and hu(Y) "5:. y "5:. x V y. Therefore, hu(x) V hu(Y) is in M. As
(M,F ) is a (b 1 ,b2 , "5. )-Join Upper Bounded Algebra it satisfies the partial distributive Jaws by
Corollary 5.1.3 (taking the set Has empty). Let Cs:;; M \ {b1 , bz}. Letx,y be in M.
To show hu(x Ay) = hu(x) Ahu(Y), let hu(x) =di, hu(Y) = d2, and hu(x Ay) = d3. As u
i row(b1)
then every element q inM with row(q) "5:_ u has unique rows. In particular, d1 ,d2 and d3 have unique
rows and are not in {b1 , bz}. Thus,
row(d3) = row(x A y) A u
= row(x) A row(y) A u
by Claim 3.3.1
= (row(x) A u)A (row(y) A u)
= row(d1) A row(d2)
= row(d1 A d2)
by Claim 3.3.1.
As the rows are unique for d 1, d2, and d3 , we have d3 = d I A d2 and hence,
To show hu(x V y) = hu(x) V hu(Y) when x V y is defined, let hu(x) = d1, hu(Y) = d2, and
hu(x V y) = d3. Similar to the above, none of d1 ,d2 nor d3 are in {b1 , b2}. By property 5 of
74
(b1 , b2 , ::;)-Join Upper Bounded Algebras, the join d1 V d2 is not in {b1 , b2}. Therefore,
row(d3) = row(x Vy) /\ u
= (row(x) V row (y)) I\ u
by Claim 3.3.2
= (row(x)/\u) V (row(y)/\u)
by Corollary 5.1.3
= row(d1) V row(d2 )
= row(d1 V d2)
by Claim 3.3.2.
as needed.
Therefore, both the I\ homomorphism and the partial V homomorphism respect the tangled
D
operation hu.
The last theorem we need, before proving that extensions of non-one-doubled-algebras and
one-doubled-algebras are dualisable, states that there is an operation J; in F with
(:j:)
0
otherwise.
Theorem 5.1.7. Let M = (M ,F ) be a (bi ,b2 , ::;) -Join Upper Bounded Algebra. Then there is an
operation Ji E F that satisfies (:j:).
Proof We enumerate the set F \ {Jo , lid} as {J1 , ... , Jv}. We show that for some i E { 1, ... , v} we
have f;_ as defined above. Let I be the set I = {i : J; (b 1) = 1}. Suppose, for a contradiction that for
every i in I there is an a; EM \ {b1, b2} with f;_(ai) = 1. Set Ci= ai I\ b 1 so that
J;( c;) = f;_(a; I\ bi) = J;(a;) I\ f;_(b1) = 1.
75
Note that Ci < b 1 since ai ff: {b1 , b2}. Define c = V Ci. As the algebra Mis a Join Upper Bounded
iE/
Algebra and since Ci < b1 for every i, we know that c EM. Moreover, c is less than b1 by Property
5 of the definition of (b1 , b2 , :S)-Join Upper Bounded Algebras. For a contradiction, we show that
the row(c) = row(b1 ). For all j with !J(b1) = 0 we must have
!J(c) = fJ
(v Ci) V
=
iE/
Jj(ci) =
iE/
VJj(ai /\ b1) = V(!J(ai) /\ fJ(b1)) = 0.
iE/
iE/
Hence, for all j with !J(b 1) = 0 we have fJ(c) = 0.
Now consider all j with !J(b1) = 1. We must have
as there exists at least one Jj(ci) = 1. Namely, !J(cj) = 1 as j E /. As row(c) = row(b1) and c < b1.
But this contradicts Property Id of the definition of (b 1, b2 , :S)-Join Upper Bounded Algebras.
Therefore, there must be a coordinate i where for every a EM \ {b1 , b2} we have fi(a) = 0. Hence,
there is a Ji E F with
fi(x) =
0
otherwise
D
as needed.
5.2
Dualisability of Non-One-Doubled-Algebras
We begin this section by looking into what functions a non-one-doubled-algebra tangles . We let M
denote a non-one-doubled-algebra with the order :S and the repeated rows represented by b1 and
b2 . We then look at an extension of the algebra M where all the tangled operations are included,
along with a few additional operations. We refer to these additional operations as double functions.
76
We then proceed to prove Theorem 5.2.5 which states that the extension is dualisable. This is the
main result of this section.
By definition of a Join Upper Bounded Algebra, a non-one-doubled-algebra will form a semilattice that is not a lattice and thus, by Corollary2.2.3 we know non-one-doubled-algebras are not
dualisable. We can therefore, talk about the existence of tangled total operations on the algebra.
Suppose M = (M, F ) forms a non-one-doubled-algebra. Define the set fi to be
H = { V row(v): C ~ M \ {b1 ,b2}}.
vEC
Recall that for a {O, 1}-valued finite unary algebra with zero, where row(O) is uniquely witnessed
by 0, if u E {O, 1
t then the partial operation hu is defined by
hu(x) = b
if
{a EM: u !\ row(x) = row(a)} = {b}.
Note that when hu (x) = b we have u !\ row(x) = row( b) which is consistent with the definition
of hu in the unique rows case. Here, we are talking about the tangled operation as we did in
Section 5.1 on page 71. The next theorem describes a collection of tangled functions defined on
non-one-doubled-algebras.
Theorem 5.2.1. Let M = (M , F ) be a non-one-doubled-algebra and define
H = { V row(v): C ~ M \ {b1 ,b2}}.
vE C
Then for all v E H if hv (/: F then F A hv.
Proof Follows from Corollary 5.1.4 and Theorem 2.3.1.
D
We refer to the set of tangled operations defined on Mas H, where H = {hu : F ,.<,. hu and u E fi}.
It is currently unknown if (M , FU H ) is dualisable. Work has suggested that, unlike the situation
77
with unique rows, adding all the tangled functions of this form does not gaurentee that the extension algebra is dualisable. To deal with this we include some additional operations which we refer
to as double operations. In order to define double operations, we first recall the existence of the
constant operation Jo and the function J{' discussed in Section 3.5. Then for all y EH U {Jo , J{'}
we define the double operation
Pr:M-+M
by
y(x)
otherwise
for all x E M. Currently, it is unknown if Pr need to be tangled. We conjecture that it is not.
We use P to denote the set of all double operations on M , therefore
P = {Pr : r E Hu {Jo ,J{'}} .
In Theorem 5.2.5 we show that given a non-one-doubled-algebra, M = (M ,F ), the extension
JM = (M ,FUHUP)
is dualisable. To show this we use the Join Upper Bounded Algebra Morphism Property, found in
Section 3.4.2. In order to use this property we must show that:
1. every tangled operation in H , as well as every double function in P, respects both the I\
homomorphism and the partial V homomorphism;
2. the algebra JM is still a Join Upper Bounded Algebra; and,
3. the algebra JM satisfies the partial distributive laws.
78
This is done in the next two theorems.
Theorem 5.2.2. Assume that M is a non-one-doubled-algebra. Let h E H and let Pr E P with
y E HU {Jo, ft}. Both h and Pr respect the I\ homomorphism and the partial V homomorphism.
Note that M is a non-one-doubled-algebra and therefore is a Join Upper Bounded Algebra. We
can therefore invoke Claim 3.3.1.
Proof Let M be a non-one-doubled-algebra with row(b1) = row(b2) and::; fixed. We set b1 ::; b2.
Leth EH. Then by Theorem 5.1.6, h respects both the I\ homomorphism and the partial V
homomorphism.
Let Pr E P. Then y EH U {foJt }. In Section 3.5 we showed that the operation ft is either
in F or F A ft. Furthermore, both Jo and ft can be defined in terms of the rows of the algebra,
namely
fo = hrow(O)
and,
ft= hrow( I )·
Therefore, as y E HU {Jo ,f f } there exists a u E fl with Pr = Phu. We want to show that for all x
and y in M we have
Ph)x I\ Y) = Ph)x) I\ Ph)Y) ·
If x /\y E { b1 , b2} then both x and y must be in {b1 , b2}. Therefore,
as needed.
79
If x/\y (:/: {b1,b2} then without loss of generality, assume y (:/: {b1,b2}. Two cases exist:
X E { b I , b2} and X
tt {bI , b2}. If tt {b I , b2} then
X
Ph)x /\y) = hu(x /\y)
as x I\ y (:/: { b 1, b2}
= hu(x) /\ hu(Y)
by Theorem 5.1.6
= Ph)x) /\ ph)Y)
as x,y (:/: {b1 ,b2} .
If x E {b1 ,b2} then let hu(x /\y) = d and hu(Y) = e. Then
u /\row(x/\y) = row(d)
and,
u I\ row(y) = row(e)
respectively. But,
row(d) = u /\ row(x /\y)
= u I\ row(x) I\ row(y)
as x I\ y (:/: {b 1, b2} and is therefore a unique element
= row(x) I\ (u I\ row(y))
= row(x) I\ row(e)
= row(x I\ e)
by Claim 3.3 .1 and as x I\ e tJ. {b1 , b2}.
80
Therefore, x I\ e = d by unique rows (d , x I\ e E M \ { b 1, b2}). Consider,
Ph)x /\y) = hu(x /\y)
=d
=x /\e
= Ph)x) /\ hu(Y)
= Ph)x) I\ Ph)Y) ·
So in every case
Phu (x /\y) = Phu (x) I\ Phu(Y)
and we are done.
To show
Ph)x Vy) = Ph)x) V Ph)Y)
when xVy, hu(x) V hu(Y) and Ph)x) V Phu(Y) are all defined, first note that xVy will not be in
{b 1 ,b2} if and only if both x and y are not in {b1 , b2} .
First assume xVy (/:. {b1 ,b2} . Then x,y (/:. {b1, b2} and hence
Ph)x Vy) = hu(x Vy)
= hu(x) V hu(Y)
by Theorem 5.1.6
If x Vy E {b 1 , b2} then without loss of generality assume that y E {b 1 , b2}. There are two cases:
either x E {b 1, b2} or x (/:. {b 1, b2}. If x E {b 1 , b2} then
Ph)x Vy) = xVy = Ph)x) V Ph)y).
81
If x 1 {bi , b2} then let hu(x) = c. Then
u /\ row(x) = row(c)
and therefore,
row(c) :S row(x)
and hence,
as, x V y E {bi , bi} and x 1 {bi , b2} so x :Sy. Soc V y= y. Consider,
Ph)x v y) = x V y
=y
=c V y
= hu(x) V y
= Ph)x) V Ph)y).
Therefore, in every case we have
Hence, for every h E H and for every Pr E P with y E HU {Jo ,f t }, both hu and Pr respect the
I\ homomorphism and the partial V homomorphism.
D
We need the algebra JM to be closed under composition so that it forms a Join Upper Bounded
Algebra. Unfortunately, the set FU HU P may not always be closed under composition as seen in
Example 5.2.1.
82
Example 5.2.1. Let M = (M, FU HU P) be the algebra defined in Tables 5.3 and 5.4 where
F = {fo ,hJ( ,!3,f4,f5}
H = {hrow(2), hrow(3), hrow(4), hrow( I )Vrow(2), hrow(2)Vrow(3), hrow(2)Vrow(4)}
and,
p = {p Jo ' P J(' Phrow(2) ' Phrow(3) ' Phrow(4) ' Phrow( l )Vrow(2) l Phrow(2)Vrow(3) ' Phrow(2)Vrow(4) } ·
To simplify the notation in the table, we will use h'f to denote hrow(i) and h'fJ to denote hrow(i)vrow(j )·
We note that the operation set F UHUP is not closed under composition. Consider, h 4o Ph j defined
by
0
ifxE{0, 2}
1 if X= 1
3
if XE {3 ,4}
4
if X E {b J , b2}
and note that h4o Ph j ff. FU HU P. Hence, M is not closed under composition. The operation,
h4o Ph j is listed in Table 5.4.
From now on we will assume that the operations of the algebra JM are closed under composition. By Corollary 3.3.4 if we assume F U HU Pis closed under composition, it still holds that the
operations in F UH UP respect both the I\ homomorphism and the partial V homomorphism.
Theorem 5.2.3. Let M = (M, F) be a non-one-doubled-algebra. Let
be an algebra where FU HU P is closed under composition, with
H = { hu : F A hu and u E H}
83
Jo h
f(
!3 f4
fs
h*2 h*3
h*4
hi2
h23
h24
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
1
1
1
1
2
0
1
0
0
0
0
2
0
0
2
2
2
3
0
0
1
1
0
0
0
3
3
1
3
3
4
0
0
1
1
1
0
0
3
4
1
3
4
bi
0
0
1
1
1
1
0
3
4
1
3
4
b2
0
0
1
1
1
1
0
3
4
1
3
4
Table 5.3: An example of an extension of a non-one-doubled-algebra that is not closed under
composition. Here we list the operations F UH.
Pio
PJt
Phi
Ph 3 Ph4 Phiz
Phz3
Phi4
h4 ° Ph 3
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
1
1
1
1
1
2
0
0
2
0
0
2
2
2
0
3
0
1
0
3
3
1
3
3
3
4
0
1
0
3
4
1
3
4
3
bi
bi
bi
b1
bi
bi
bi
bi
bi
4
b2
b2
b2
b2
b2
b2
b2
b2
b2
4
Table 5.4: An example of an extension of a non-one-doubled-algebra that is not closed under
composition. Here we state all operations in P, along with the operation, h4o Phj, which is not
found in F UHUP.
84
and,
P = {py : Y E HU {Jo , ft}}
Then JM is a Join Upper Bounded Algebra that satisfies the partial distributive laws.
Proof Let M = (M , F ) be a (b1 , b2 , ::;)-Join Upper Bounded Algebra with row(b1) = row(b2) and
::; fixed. Set b1 ::; b2.
Recall the existence of the operation Jo, along with the fact that the row(O) is uniquely witnessed by 0. This holds as Join Upper Bounded Algebras have a row and a column of zeros. Now
consider the extension
JM = (M,FUHUP)
of M. Recall that hu(x) = b if and only if
{a EM: u !\ row(x) = row(a)} = {b}.
But this means that hu (0) = 0 for every hu E H. Moreover, as O f/. {b 1, b2} we have
Ph)O) = hv(O) = 0
for every Phv E P. Therefore, the rowfM(O) is the tuple of all O's in the set Rows(JM). Moreover,
as rowM(O) is uniquely witness by Owe have rowfM(O) will be uniquely witness by 0. So JM is an
algebra with zero. By Theorem 5.2.2 we know that
!\ :M2 -+M
is a total homomorphism and
V :M2 -+M
is a partial homomorphism. As JM has the same underlying set as M, the property
a , b::; c implies a V b is defined in M
85
also holds for our algebra JM. Finally, the last thing that must hold for JM to be a Join Upper
Bounded Algebra is that FU HU P must be closed under composition, which holds by assumption.
Hence, JM is a Join Upper Bounded Algebra. Moreover, since all the operations in the closed set
FU HU P respect both the I\ homomorphism and the partial V homomorphism (Theorem 5 .2.2 and
Corollary 3.3.4) we know that JM will also satisfy the partial distributive laws by Lemma 5.1.1.
Therefore, JM is a Join Upper Bounded Algebra that satisfies the partial distributive laws.
D
As JM is a Join Upper Bounded Algebra we can now use Claims 3.3.1 and 3.3.2 which state
that the rows of an algebra respect both the I\ homomorphism and the partial V homomorphism.
Furthermore, as the algebra JM is a Join Upper Bounded Algebra that satisfies the partial distributive laws (Theorem 5.2.3) we can now use Join Upper Bounded Algebra Morphism Property to
prove the main theorem in this section, Theorem 5.2.5. First we identify the maps, gb; : JM-+ JM
for i E {1 , 2} and j E {1 , 2} \ {i} defined by
x
otherwise.
For i E { 1, 2} and j E { 1, 2} \ { i} the maps gb; and gb j are homomorphisms on the extension of
non-one-doubled-algebras as seen in the following claim.
Claim 5.2.4. Let JM be an extension of a non-one-doubled-algebra, M = (M ,F ), with
JM = (M ,F UHUP) and FUHUP closed under composition. The maps gbpgb 2 : JM-+ JM are
homomorphisms on JM.
Proof Let M = (M, F ) be a non-one-doubled-algebra with row(b 1) = row(b 2 ) and :S fixed. Set
b1 :S b2. Furthermore, let algebraJM = (M ,FUHUP) be an extension ofM and assume F UHUP
is closed under composition.
86
Let i E { 1, 2} and j E { 1, 2} \ { i}.
We must show that for all µ E F U H U P we have
gb; (µ (x)) = µ (gb; (x)). Recall,
x
otherwise.
If i = 1 then gi = g1 and if i = 2 then gi = gz. We will show that gb;(µ(x)) = µ(gb;(x) ).
Let y E M. Notice that
and
Now suppose µ E F \ {foJid}. If y =I- bJ then gb;(Y) = y. Hence
µ(gb;(Y)) = µ(y).
Asµ is a {O, 1}-valued operation we have
gb;(µ(y)) = µ(y) as µ(y) =I- b1.
Therefore, µ (gb; (y)) = 8b; (µ (y)) when y =/- b J. If y = b J then,
µ(gb;(b1)) = µ(bi)
= µ(bj)
as row(bi) = row(b1) therefore µ(bi)= µ(b1) asµ E F \ {fo,f;d}
= gb;(µ(bJ))
as µ(x) E {O, 1} for every x and therefore gb;(µ(x)) = µ(x).
Thus, µ (gb; (y)) = gb; (µ (y)) when y = bJ and therefore µ (gb; (y)) = gb; (µ (y)) for all y E M as
needed.
87
Now considerµ EH. Then there is au E ii withµ= hu. That is, there exists a C ~ M \ {b1 ,b2}
with u =
V row(v). Note that for all c EM we have hu(c) ft. {b; ,b1}- Specifically, for c E {b1,b2}
vEC
we have
u !\ row(b;) = u !\ row(b1) =/. row(b1)
as u
i. row(b1) by property 5 of (b1, b2 , :S)-Join Upper Bounded Algebras. However, as hu is
defined there exists a d in M with
u !\ row(b;) = u !\ row(b1) = row(d) < row(b1)
or equivalently,
This d is neither b; nor b J. So, by the definition of a non-one-doubled-algebra there does not exist
a c EM with u !\ row(c) = row(b;). When y ft. {b; ,bJ} we have hu(Y) ft. {b; ,bJ} as, hu(Y) < y. If
y E { b;, bJ} then hu (b;) = d < b; from above. Therefore, for all y we have hu (y) ft. {b;, bJ} and
hence gb;(hu(Y)) = hu(Y) for ally. Now consider, hu(gb;(y) ),
hu(b;)
if y E {b; ,bJ}
hu(Y)
if y ft. {b; ,b1}
hu(b;)
ify E {bi}
hu(bj)
if y E {b1}
hu(Y)
if y ft. {b; ,b1}
hu(gb;(Y)) =
= hu(Y)
as hu(b;) = hu(b1)- Thus, hu(gb;(y)) = hu(y). So, gb;(hu(Y)) = hu(gb;(Y)) as needed.
Finally, suppose µ E P. Then there is some y E HU {Jo ,f(} with µ = Pr· In fact, there exists
a u such that y = hu. We will use the fact that gb;( y(y)) = gb; (hu (y)) = hu (y) = y(y) (established
88
above). Note that
gb;(Py(y)) =
gb;(bi)
if y = bi
gb;(b1)
if y = bi
gb;( y(y))
otherwise
bi
ify E {bi ,bj}
gb; ( y(y))
otherwise
bi
if y E {bi ,bJ}
y(y)
otherwise.
And,
Py(gb; (y)) =
Py(bi)
if y E {bi ,bj}
Pr(Y)
otherwise
bi
if y E {bi ,bJ}
y(y)
otherwise.
Hence, py(gb;(y)) = gb;(Py(y)) and therefore, for allµ E P we have µ(gb;(Y)) = gb;(µ(y)). Therefore, for all µ E FU HU P we have gb;(µ (x)) = µ (gb; (x)). So gb 1 and gb 2 are homomorphisms on
D
We are now ready to state and prove the main theorem in this section, Theorem 5.2.5.
Theorem 5.2.5. Let M = (M, F ) be a non-one-doubled-algebra. Let
JM = (M ,F UHUP)
be an algebra such that F U H U P is closed under composition, where
H = {hu : F /.. hu and u E fi}
89
and
p = {Pr : y E Hu {Jo ' J(}}.
The remainder of this section is the proof of Theorem 5.2.5. Furthermore, to prove Theorem 5.2.5 we will use the Join Upper Bounded Algebra Morphism Property with the set Gin the
alter ego,
Let M = (M , F) be a non-one-doubled-algebra with row(b1) = row(b2) and :S fixed. Set
b1 :S b2. Furthermore, let algebra JM = (M ,FUHUP) be an extension ofM and assume F UHUP
is closed under composition.
Set M= (M,/\,V,O,gb 1 ,gb2,&t°1Ml2+1Ml, 5'} Since JM is finite, to prove Theorem 5.2.5, by
the duality compactness theorem it is sufficient to show A ~ ED (A) via the evaluation maps
for every finite A E II§JP'(JM)- Pick A :S (JM?, and let X = hom(A, JM). We want to show
that each morphism a : X-+ M is an evaluation at some a EA. We do this by showing that
for each possible range ( a), the map a is an evaluation at some t(a) where a is in Ao with
Ao= {a EA: Vi E range (a) Xi (a)= i} and t E FUHUP. The form oft will depend on whether
b1 E range (a) or not.
We now fix a : X -+ M. Recall that for all i E range (a) we defined the sets Xi, Ii and Bi to
be Xi= {h EX: a(h) = i},li = {b EM: b ?_ i} and Bi= {b E Ii: Vj E range(a) j /\ b = j /\ i}.
As the algebra JM is a Join Upper Bounded Algebra that satisfies the partial distributive laws
(Theorem 5.2.3) we can use Join Upper Bounded Algebra Morphism Property. Therefore there is
90
an a in Ao where for all j in range (a) the following holds
We fix this particular element a in Ao for the remainder of this section.
Using the homomorphisms gb, and gb 2 defined on JM we note the following properties of
range ( a).
Lemma 5.2.6. For every range (a) note that the following holds:
1. 0 E range(a), and
2. b1 E range(a) ifandonlyb2 E range(a).
Proof To show that O E range (a), note the constant zero homomorphism, 0 which is in the alter
ego. Take any x EX. Then
a(O(x)) = O(a(x)) = 0
so O E range (a) as needed.
To show b1 E range ( a) if and only if b2 E range ( a) we need the homomorphisms gb, and gb 2
from Claim 5 .2.4. This homomorphisms are both in our alter ego. Suppose b2 E range (a). Then
there is an x E X with a(x) = b2. But then,
So b1 E range ( a). Now suppose b1 E range ( a). Then there is an x EX with a(x) = b 1. But then,
So b2 E range ( a). Therefore, b 2 E range ( a) if and only if b 1 E range ( a).
91
D
Recall that a is the particular element of A found by the Join Upper Bounded Algebra Morphism
Property. The element a satisfies Vy E Xj we have y(a) E Bj.
Let I~ M \ {b1 , b2} such that OE/. Using Lemma 5.2.6 we see that there are two possibilities
for range (a):
1. range (a) = I, or
2. range(a) =IU{b1 ,b2} .
For the first case, Claim 5.2.7 shows there is a function h in HU {Jo ,f t } such that a= eA(h (a)).
This uses the fact that the row( c) is unique for all c in I and therefore this proof similar to Section 4.3. For the second case, Claim 5.2.8 shows there is a pin P such that a= eA(P (a)).
Claim 5.2.7. Let I ~ M\ {b1 ,b2} with OE/. If range(a) = I then a= eA(h(a)) for some
h E HU {foJt }.
Proof To show this, suppose range ( a) = I. Now, let u = V row(i). Note that hu is either tangled
iEI
and in H , or is in {Jo,!( }. To show that a= eA(hu(a)), pick i in range(a) and z in X; . Then
z(a) is in B; (by Join Upper Bounded Algebra Morphism Property) and z(a) (/: Bj for j =/- i. Let
b = z(a). We know a(z) = i as z EX;. We have
(hu(a))( z) = z(hu(a)) = hu(z(a)) = hu(b)
and
a(z) = i,
so to show that a is an evaluation, it suffices to show hu (b) = i; or equivalently,
92
Let c be any element of Bi. We have for all j E range ( a) that j /\ c = j /\ i. Therefore as both u
and rowM(i) are in {O, l} IF\ {foJ;d} I (for all i in range(a)) we have,
u /\ rowM(c) = [
V
rowM(j)] /\ rowM(c)
} Erange (a )
V
(rowM(j) /\ rowM(c))
by distributivity in {O, 1} IF\ {!o,!;d} I
} Erange (a )
V rowM(j /\ c)
by Claim 3.3.1
j Erange (a )
V
rowM(j /\ i)
as j /\ c = j /\ i
(rowM(j) /\ rowM(i))
by Claim 3.3.1
rowM(j)] /\ rowM(i)
by distributivity in {O, 1} IF\ {!o,J;d} I
} Erange (a )
V
j Erange (a )
= [
V
} Erange (a )
= rowM(i).
So hu(c) = i EM. This holds for all c E Bi and for all j in range ( a) so hu(z(a)) = i as z(a) E Bi.
Therefore, a(z) = z(hu(a)) = hu(z(a)) = i for all i in range ( a) and all z in Xi.
k
Therefore, a= eA(hu (a)) where u =
V row(i) when range(a) = I. This is illustrated in TaiEJ
ble 5.5.
D
Claim 5.2.8. Let I~ M \ {b1 , b2} with OE/. If range (a)= /U {b1 , b2} then a= eA(Py(a)) for
some YE HU{fo ,Jt}.
Proof Recall that we have a particular element, a, that satisfies the following,
93
z
::la EAo
a
hu (a)
z(a)
a(z)
z(hu(a))
Vi EI Xi
Table 5.5: If JM 1s an extension of a non-one-doubled-algebra then a = eA(hu(a)) when
range (a)= I.
Let u =
V row(i) and set h = hu so that h EH U {foJt }. Take this particular h and recall the
iE/
function
Ph :M-+M
where
b2
if X = b2
h(x)
otherwise.
Note that, Ph E P. To show that a= eA(Ph(a) ), pick i in range ( a) and z in Xi. Then z(a) is in Bi
(by Join Upper Bounded Algebra Morphism Property) and z(a) (j. Bj for j =I= i. Let b = z(a) . As
z E Xi, we know a(z) = i. We have
(Ph(a))(z) = z(ph(a)) = Ph(z(a)) = Ph(b)
and
a(z) = i,
so to show that a is an evaluation, it suffices to show Ph (b) = i.
It is sufficient to show that for all j in I U { b1, b2} and for all c EB j that Ph (c) = j. There are
three cases.
94
Case 1: j = b 1 . Note that
lb, = {b EM: b I\ b1 = bi}
= {b1 ,bz}.
Therefore, as b2 E range (a) ,
Bb, = {b E lb 1 : Vj E range(a) j /\ b = j /\ bi}= {bi}.
Take c E Bb 1 = {b1}. Then Ph (b1) = b1 as needed.
Case 2: j = b2 . Note that
and therefore
Bb2 = {b E lb 2 : Vj E range(a) j /\ b = j /\ b2} = {b2}.
Take c E Bb 2 = {b2}. Then Ph(b2) = b2 as needed.
Case 3: j E /. Take c E B 1. Note that c is not in Bb, UBb 2 = {b1 , b2} as both B 1 nBb, and B 1 nBb2
are empty by Theorem 3.4.1. Hence,
Ph(c) = h(c) as c E B1 and therefore c =/- b1 ,bz .
We must therefore show that h(c) = j.
By definition of B1, as c E BJ we have for all i E range (a) that i I\ c = i I\ j. In particular, as
I~ range ( a) we have for all i EI that i I\ c = i I\ j. Both u and rowM (i) are in {O, 1} IF\ {foJ;d} I (for
95
all i in the set I) therefore we have,
u A rowM(c) =
[:J rowM(i)] rowM(c)
A
tEl
= V(rowM(i) A rowM(c))
by distributivity in {O, 1t \ Uoh}
iE/
= VrowM (i Ac)
by Claim 3.3.1
iE/
= VrowM(i A j)
as i Ac= i A j
iE/
= V(rowM(i) A rowM(j))
by Claim 3.3.1
iE/
=
[v
rowM(i)] A rowM(j)
by distributivity in {O, 1t \ Uoh}
1E/
= u i\ rowM(j)
as j E I implies rowM (j) ::; u.
Therefore h(c) = j and hence Ph(c) = h(c) = j when c E Bj and j E /. This is illustrated in
Table 5.6.
Therefore, in any case we have for all i in /U {b1 , b2} and for all c E Bi that Ph(c) = i. Set
a= Ph(b). Then a= eA (a) when range (a)= /U {b1 , b2}.
D
Therefore by Claims 5.2.7 and 5.2.8 and for any possible range(a) we get that there is an
c EA with a= eA(c). Hence, by Join Upper Bounded Algebra Morphism Property JM is dualised
5.2.1
An Example of a Non-One-Doubled-Algebra
The non-one-doubled-algebra, M = ({O , 1,2,3,4} ,{fo ,h ,!3,f4}), is defined in Table 5.7. Here,
row(3) = row( 4) and 3 ::; 4. We further note that it is not dualisable. If we include the tangled
96
=la E Ao
a
Ph (a)
z(a)
a(z)
z(ph(a))
Xb,
b1
b1
b1
Xb2
b2
b2
b2
Vj EI Vy EX1
y(a) E B 1
J
J
Vy E Xb,
y(a) E Bb, = {bi}
b1
b1
Vy E Xb 2
y(a) E Bb 2 = {b2}
b2
b2
z
Vi EI Xi
Table 5.6: If JM is an extension of a non-one-doubled-algebra then a = eA(Ph(a)) when
range(a) =lU{b1 ,b2}.
functions h100 and h101, as well as the additional functions PJo ,PJ(, Ph,oo and Ph,o, (all defined in
Table 5. 7) in the operation set of the algebra, then the algebra given by
is dualised by the alter ego M = (M,I\, V, O,g3 ,g4 ,~30 , !Y). Recall that extensions of non-onedoubled-algebras may not always be closed, as is the case with this algebra. The operation,
h101 o Ph,oo is not in F UH UP as seen in Table 5.8.
We go through the details of this example in Chapter 6.
5.3 Dualisability of One-Doubled-Algebras
Recall that a (b1 ,b2 , ~)-Join Upper Bounded Algebra where b 1= 1 is called a one-doubled-algebra
once b2 and ~ are fixed. We start by looking at what functions are tangled by one-doubled-
97
Jo h h J4 =J{'
h100
h101
PJo
Pf(
Ph100
Ph101 = id
h101
° Ph100
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
1
0
1
0
2
0
1
0
0
2
2
0
0
2
2
2
3
0
0
1
1
0
1
3
3
3
3
1
4
0
0
1
1
0
1
4
4
4
4
1
Table 5.7: An example of a non-one-doubled-algebra where the row(3) = row(4). The operation
h 101 o Phioo is not in FU HU P but must be included in order for the algebra to be closed.
Jo h h J{'
h100
h101
Pfo
Pf(
Ph100
Ph,o,
Jo
Jo Jo Jo Jo
Jo
Jo
Jo
Jo
Jo
Jo
h
Jo Jo Jo Jo
h
h
Jo
Jo
h
h
h
Jo Jo Jo Jo
Jo
Jo
h
h
h
h
J{'
Jo h h J{'
Jo
Ji
h
J{'
h
J{'
h100
Jo Jo Jo Jo
h100
h100
Jo
Jo
h100
h100
h101
Jo h h J{'
h100
h101
h
J{'
° Ph,oo
h101
Pio
Jo Jo Jo Jo
Jo
Jo
PJo
PJo
PJo
PJo
Pf(
Jo h h J{'
Jo
J{'
Pfo
PJ(
PJo
PJ(
Ph, 00
Jo Jo Jo Jo
h100
h100
PJo
PJo
Ph100
Ph100
Ph 10,
Jo h h J{'
h100
h101
PJo
Pf(
Ph,oo
Ph101
h101
Table 5.8: The non-one-doubled-algebra, M, is not a closed algebra.
98
k
II ko(h1010Ph100) I (h1010Ph1oo)ok
Jo
Jo
Jo
h
h
Jo
h
Jo
Jo
ft
h
Jo
h100
h100
h100
h101
h100
h100
Pio
Jo
h
Pf(
h
h
Ph100
h100
h101
° Ph1oo
° Ph100
h101
° Ph100
Ph101
h101
Table 5.9: The algebra, M, is a closed algebra when the operation h101 o Phioo is added.
99
algebras. By definition of a Join Upper Bounded Algebra, a one-doubled-algebra will form a
semilattice that is not a lattice and thus, by Corollary 2.2.3, we know one-doubled-algebras are not
dualisable. We can therefore talk about the existence of tangled total operations on the algebra.
Suppose M = (M,F ) is a one-doubled-algebra with row(l) = row(b) and :s; fixed. Let
ff = { Vrow( v) :
C~ M \ {b, 1}} .
vEC
Recall that for a {O, 1}-valued finite unary algebras with zero, where row(O) is uniquely witnessed
by 0, if u E {O, 1Y for v =IF \ {foJid}I, then the partial operation hu is defined by
hu(x) = d
if
{a EM: u l\ row(x) = row(a)} = {d}.
Note that when hu(x) = d we have u I\ row(x) = row(d) which is consistent with the definition of
hu in the unique rows case. Here, we are also talking about the tangled operation as we did in
Section 5.1 on page 71. The next theorem shows that if u E ff then F may tangle hu.
Theorem 5.3.1. Let M = (M, F ) be a one-doubled-algebra and define
ff= { V row(v):
C~ M \ {b , 1}} .
vE C
Then for all v E ff if hv i F then F A hv.
Proof Follows from Corollary 5.1.4 and Theorem 2.3.1.
D
Let H = {hu: F A hu and u E fl} . It is currently unknown if (M ,F UH) is dualisable when M
is a one-doubled-algebra. We conjecture it is not.
Let M be a one-doubled-algebra with row( 1) = row( b) and :s; fixed. For all y E HU {Jo} we
define the following two double operations:
py: M--+M
100
and
qr:M-+M
by
X
if XE {1 , b}
y(x)
otherwise
1
if XE {1 ,b}
r(x)
otherwise
Pr(x) =
and
qr(x) =
for all x EM. Currently, it is unknown if Pr and qr are tangled and we conjecture they are not. We
fix the following two sets, Q and P, defined by
P = {Pr :
r E Hu {Jo}}
and
Q = {qr : r E Hu {Jo}} .
In Theorem 5.3.5 we show that given a one-doubled-algebra, M = (M , F) the extension
KM= (M , FUHUPUQ)
is dualisable. To show this, we use the Join Upper Bounded Algebra Morphism Property, found in
Section 3.4.2. In order to use this property we must show that every tangled operation hu and every
double operation, Pr and qr, respect the I\ homomorphism and the partial V homomorphism. This
is done in the next theorem. We then proceed to show that KM is a Join Upper Bounded Algebra
that satisfies the partial distributive laws, therefore allowing us to use the Join Upper Bounded
Algebra Morphism Property.
Theorem 5.3.2. Assume that M is a one-doubled-algebra. Let h E H, Pr E P and qr E Q with
y EH U {Jo}. The operations h, Pr and qr respect both I\ homomorphism and the partial V
homomorphism.
101
Note that as Mis a one-doubled-algebra it is also a Join Upper Bounded Algebra, therefore,
we can invoke Claim 3.3.1.
Proof Assume that Mis a non-one-doubled-algebra with row( 1) = row( b) and :::; fixed. Leth EH.
Then by Theorem 5.1.6, the total operation h respects both the I\ homomorphism and the partial V
homomorphism.
Let Pr E P. Then y E HU {Jo}. Recall that the operation, Jo , can be defined as
Jo = hrow(O) ·
Therefore, as y EH U {Jo} there exists a u E fI with Pr= Phu and qr= qhu. We will first show that
Phu respects both meet and join, and then move on to qhu.
We want to show that for all x and y in M we have
If x /\ y E {1 ,b} then both x and y must be in {1, b }. Therefore,
Ph)x /\ y) = x /\ y
= Ph)x) /\ ph)Y)
as needed.
If x I\ y
i {1, b} then without loss of generality, assume y i {1, b}. Two cases exists: x E { 1, b}
and x i { 1, b}. If x i { 1, b} then
as x I\ y i { 1, b}
Ph)x /\ y) = hu(x /\ y)
= hu(x) /\ hu(Y)
by Theorem 5.1.6
= Ph)x) /\ ph)y).
102
If x E { 1, b} then let hu (x I\ y) = d and hu (y) = e. Then
u I\ row(x /\ y) = row(d)
and,
u /\ row(y) = row(e)
respectively. But,
row(d) = u I\ row(x l\ y)
= u I\ row(x) I\ row(y)
by Claim 3.3.1 and as x I\ y ~ { 1, b} and is therefore a unique element
= row(x) I\ (u /\ row(y))
= row(x) I\ row( e)
= row(x /\ e)
by Claim 3.3.1 and as x I\ e ~ {l ,b } .
Therefore, x I\ e = d by unique rows ( {d ,x I\ e} ~ M \ {1 , b} ). Consider,
Ph)x /\ y) = hu(x /\ y)
=d
=x /\ e
as hu(x) = x and hu(Y) = e
= hu(x) /\ hu(Y)
= Ph)x) /\ ph)y).
So in every case
and we are done.
103
To show
Ph,,(x V y) = Ph)x) V Ph,,(Y)
when x V y, hu (x) V hu (y) and Ph,, (x) V Ph" (y) are all defined, note that x V y will not be in { 1, b} if
and only if both x and y are not in { 1, b}. If x V y i { 1, b} then {x , y} c/:. { 1, b} and hence
Ph,,(x V y) = hu(x V y)
= hu(x) V hu(Y)
by Theorem 5.1.6
= Ph (x) V Ph,,(y).
11
If x V y E { 1, b} then without loss of generality assume that y E { 1, b}. There are two cases:
x E { 1, b} and x i { 1, b}. If x E { 1, b} then
Ph,,(x V y) = x V y
= Ph,, (x) V Ph,, (y).
If xi {1 , b} then let hu(x) = b. Then
u I\ row(x) = row(b)
and therefore,
row(b) :S: row(x)
and hence,
104
(x :Sy as x V y is define and in { 1, b} ). Sob V y= y. Consider,
Ph)x v y) = x V y
=y
=b V y
= hu(x) V y
= Ph)x) V Ph)Y) ·
Therefore, in every case we have
Hence, for all y E HU {Jo} the operation Pr respects both the I\ homomorphism and the partial V
homomorphism.
Next, we want to show that for all x and y in M we have
If x /\ y E {1 , b} then both x and y must be in {1 ,b }. Therefore,
qh)x /\ y) = 1
= 1 I\ 1
= qh)x) /\ qh)Y)
as needed. If x I\ y (/. { 1, b} then without loss of generality, assume y (/. { 1, b}. Two cases exist:
105
x E { 1, b} and x ~ { 1, b}. If x ~ { 1, b} then
qh.(x l\y) = hu(x l\y)
= hu(x) A hu(Y)
by Theorem 5.1.6
= qh.(x) A qh.(Y) ·
If x E {l,b} then let hu(x l\ y) = d and hu(Y) = e. Then
u I\ row(x l\ y) = row(d)
and,
u l\ row(y) = row(e)
respectively. But,
row(d) = u l\ row(x l\ y)
= u I\ row(x) I\ row(y)
by Claim 3 .3 .1 and as x I\ y ~ { 1, b} and therefore has a unique row
= row(x) I\ (u l\ row(y))
= row(x) I\ row( e)
=row(x l\ e)
by Claim 3.3.1.
Therefore, x I\ e = d by unique rows ( {d ,x I\ e} ~ M \ {1 , b} ). Consider,
qh.(x l\ y) = hu(x l\ y)
=d
=x l\ e
= 1 1\ e
106
as hu(x) = x and hu(Y) = e
= 1 A hu(Y)
= qh)x) J\ qh)y).
So in every case
and we are done.
To show
when x Vy, hu (x) V hu (y) and qhu (x) V qhu(y) are all defined, note that x Vy will not be in { 1, b} if
and only if both x and y are not in { 1, b}. If x Vy r/: { 1, b} then {x, y} 1;,. { 1, b} and hence
qh)x Vy) = hu(x Vy)
= hu(x) V hu(Y)
by Theorem 5.1.6
= qh)x) V qhu (y).
If x Vy E { 1, b} then without loss of generality assume that y E { 1, b}. There are two cases:
x E { 1, b} and x r/: { 1, b}. If x E { 1, b} then
qh)x Vy) = 1
=lVl
= qh)x) V qh)y).
If x r/: { 1, b} then let hu (x) = c. Then
uJ\row(x) = row(c)
107
and therefore,
row( c) :S: row(x)
and hence,
c:S:x:S:y
(x :S: y as x V y is defined and in {l , b}) . So c V y = hu(x) V y is defined and will be in {1 , b} as
y E { 1, b}. But this means that hu (x) V 1 is defined and is equal to 1. Therefore,
qh)x V y) = 1
=hu(x) V l
= qh)x) V qh)Y)
and we are done. Therefore, in every case we have
Thus, qhu respects both the I\ homomorphism and the partial V homomorphism.
Hence, for every hu E H and for every Pr E P and qr E Q with y E HU {Jo}, each of hu, Pr and
qr respect both the I\ homomorphism and the partial V homomorphism.
D
It is possible that the operation set F UH UP U Q is not closed under composition. Since
we need the algebra KM to be closed under composition so that it forms a Join Upper Bounded
Algebra, from now on we will assume that FU HU PU Q is closed under composition. By Corollary 3 .3 .4 if we assume FU HU PU Q is closed under composition, it still holds that the operations
in FU HU PU Q respect both the I\ homomorphism and the partial V homomorphism.
Theorem 5.3.3. Let M = (M, F) be a one-doubled-algebra. Let KM be the extension algebra,
KM= (M ,FUHUQUP)
108
where
H={hv:vEH},
Q = {qy: YE HU{Jo}}
and
r
P = {Pr : E Hu {Jo}}.
Assume that FU HU Q UP is closed under composition. Then KJ is a Join Upper Bounded Algebra
that satisfies the partial distributive laws.
Proof Let M = (M ,F ) be a one-doubled-algebra with row(l) = row(b) and::; fixed. Recall the
existence of the operation Jo along with the row(O) being uniquely witnessed by 0. This holds as
Join Upper Bounded Algebras have a row and a column of zeros. Now consider the extension
KM= (M ,FUHUPUQ)
of M and recall that hu (x) = d if and only if
{a EM: u t\ row(x) = row(a)} = {d}.
But this means that hu(O) = 0 for every hu EH. Moreover, as O tf: {l , b} we have
Ph)O) = hv(O) = 0
for every Phv E P and
qh)O) = hw(O) = 0
for every qhw E Q. Therefore, the row(O) still exists in the Rows(KM), moreover, as rowM(O)
is uniquely witnessed by oM we have rowKM(O) will be uniquely witness by QKM . So KM is an
algebra with zero. By Theorem 5.3.2 we know that
A :M2 -+M
109
is a total homomorphism and
2
V :M -+M
is a partial homomorphism. Furthermore, since the operations in FU HU PU Q respect both the A
homomorphism and the partial V homomorphism, the property
a, b ~ c implies a V b is defined in M
of M extends to our algebra KM. Finally, for KM to be a Join Upper Bounded Algebra the set
FU HU PU Q must be closed under composition, which we assume. Therefore, FU HU PU Q
is closed under composition and we can conclude that KM is a Join Upper Bounded Algebra.
Furthermore, as all the operations in F UH UP U Q respect both the A homomorphism and the
partial V homomorphism (Theorem 5.3.2 and Corollary 3.3.4) we know from Lemma 5.1.1 satisfies
the partial distributive laws. Therefore, KM is a Join Upper Bounded Algebra that satisfies the
partial distributive laws.
D
Theorem 5.3.3 allows us to use Join Upper Bounded Algebra Morphism Property to prove the
main theorem in this section which is Theorem 5.3.5. Before we proceed, however, we need to
identify one more homomorphism that will be in the alter ego that dualises the algebra.
Suppose we have a non-dualisable one-doubled-algebra, M, with row( 1) = row( b) and ~ fixed.
From this we build the extension algebra KM which has underlying set M and the operation set
FUHUPUQ (we assume this set is closed under composition). We define the map, g: KM-+ KM,
by
1 if XE {1 ,b}
g(x) =
x
otherwise.
The next claim shows that g is a homomorphism on KM.
110
Claim 5.3.4. Let M = (M , F ) be a one-doubled-algebra and let KM = (M , FU HU PU Q) be an
extension of M such that FU HU PU Q is closed under composition. The map g : KM ~ KM is a
homomorphism on KM.
Proof Let M be a one-doubled-algebra with row( 1) = row( b) and ::; fixed. Furthermore, let
KM= (M ,FUHUPU Q) be an extension of M such that FUHUPU Q is closed under composi-
tion. We must show that for allµ E F UHUPU Q we have g(µ(x)) = µ(g(x)).
Let y E M . First suppose µ E F. If y =/- b then g(y ) = y. Hence
µ(g(y)) = µ(y) .
As µ is a {O, 1}-valued operation we have
g(µ(y)) = µ(y) as µ(y) =/- b.
Therefore, µ (g(y)) = g(µ (y)) when y =/- b. If y = b then,
µ(g(b)) = µ(1)
= µ(b)
as row(l) = row(b) therefore µ(1) = µ(b) asµ E F
= g(µ(b))
as µ(x) E {O, 1} and therefore g(µ(x)) = µ(x).
Thus, µ (g(y)) = g(µ (y)) when y = b and therefore µ (g(y)) = g(µ (y)) for ally E M as needed.
Suppose µ E H. Then there is a u E fi with µ = hu.
NotethatforallcEMwehavehu(c) (/. {1 ,b} as
u !\ row(l) = u !\ row(b) =/- row(l) or row(b).
However, there exists a d in M with
u !\ row(l) = u !\ row(b) = row(d)
111
or equivalently,
hu ( 1) = hu (b) = d ~ {1, b} .
Suppose hu (y) = d , if y =J. 1, b. Then,
d
if y E {l,b}
hu(Y)
otherwise
d
if y E {l ,b}
hu(Y)
otherwise
hu(l)
if y E {l,b}
hu(Y)
otherwise
d
if y E {l,b}
hu(Y)
otherwise
hu(Y) =
So,
g(hu(Y)) =
Now consider, hu(g(y)),
hu(g(y)) =
-
So, g(hu(Y)) = hu(g(y)) as needed.
Now supposeµ E Q. Then there is some y EH U {Jo} with µ = qy. Note that
g( l )
if y E {1,b}
g( y(y))
otherwise
g(qy(y)) =
1
if y E {l ,b}
y(y)
otherwise
=
112
as y E HU {Jo} and therefore y(y) ~ {1, b} so g( y(y)) = y(y). Furthermore,
qy(l)
if y E {l ,b}
qy(y)
otherwise
1
if y E {l,b}
y(y)
otherwise.
qy(g(y)) =
Hence, qy(g(y)) = g(qy(y)) and therefore, for allµ E Q we have µ(g(y)) = g(µ(y)).
Finally, suppose µ E P. Then there is some y E HU {Jo} with µ = Pr· Note that
g(y)
if y E { 1, b}
g( y(y))
otherwise
g(py(y)) =
1
if y E {l ,b}
y(y)
otherwise
as y E H U {Jo} and therefore y(y) ~ { 1, b} so g (y(y)) = y(y). Furthermore,
py(l) if y E {l,b}
Py(g(y)) =
Py(Y)
otherwise
1
if y E {l ,b}
y(y)
otherwise.
Hence, py(g(y)) = g(py(y)) and therefore, for allµ E P we have µ(g(y)) = g(µ(y)). Therefore,
for allµ E F UHU QUP we have g(µ(x)) = µ(g(x)).
So g is a homomorphism on KM.
D
113
Theorem 5.3.5. Let M = (M, F) be a one-doubled-algebra. Then the extension algebra
KM= (M, FUHUQUP)
where
H = {hv : V E H} ,
Q= {qy: yEHU{fo}}
and
p = {Py :
r E Hu {Jo}}
is dualised by M = (M, A, V, 0, g,&?IMl2+IMI, 3'"). We assume that FU HU Q UP is closed under
composition.
The remainder of this section develops the proof of Theorem 5.3.5. We will use the Join Upper
Bounded Algebra Morphism Property with the set G in the alter ego,
taken to be {g}.
Let M be a one-doubled-algebra with row( 1) = row( b) and :S fixed.
Furthermore, let
KM = (M, FU HU PU Q) be an extension of M such that F UH UP U Q is closed under com-
position. Set M = (M ,A, V, 0,g,&?1Ml2+IMI, 3'"). Since KM is finite, to prove Theorem 5.3.5, by
the duality compactness theorem it is sufficient to show A ~ ED (A) via the evaluation maps
for every finite A E I[§JP'(KM) - Pick A :S (KMt, and let X = hom(A, KM). We want to show
that each morphism a : X-+ M is an evaluation at some a EA. We do this by showing that
for each possible range (a), the map a is an evaluation at some t (a) where a is in Ao with
Ao= {a EA: Vi E range (a) Xi (a)= i} and t E F UHUP. The form oft will depend on whether
1 ~ range (a), 1 E range (a) or { 1, b} s;:; range (a).
114
By Theorem 5.3.3 the algebra KM is a Join Upper Bounded Algebra that satisfies the partial
distributive laws. Hence KM has the Join Upper Bounded Algebra Morphism Property and there
is an a in Ao where for all j in range (a) the following holds
Recall that for all i E range ( a) we defined the sets X;, B; and/; to be X; = {h E :X : a (h) = i} ,
B; = {b E /;: \/j E range (a) j l\ b = j I\ i} and I;= {b EM: b ~ i}. We will refer to and use this
specific a for the remainder of this section. Again, this a is specific to each range (a). We now
show that for every range (a) the map a is an evaluation at some a EA by looking at three different
possibilities for range ( a). Recall the homomorphism g (Claim 5.3.4) defined by
1 if XE {l , b}
g(x) =
x
otherwise.
We will use g to note the following properties of range (a).
Lemma 5.3.6. For every range (a) note that the following holds:
1. 0 E range(a) , and
2. lfb E range(a) then 1 E range(a).
Proof To show that O E range (a) take the constant zero homomorphism, 0, found in the alter ego
and take any x E range (a). Then
a(O(x)) = O(a(x)) = 0
so O E range (a) as needed.
115
To show if b E range (a) then 1 E range (a) we will need the homomorphism g, found in M
and as defined in Claim 5.3.4. Suppose b E range ( a). Then there is an x EX with a(x) = b. But
then,
a(g(x)) = g(a(x)) = g(b) = 1.
So 1 E range (a). Therefore, if b E range (a) then 1 E range (a).
D
Let I~ M \ { 1, b} such that O E /. Using Lemma 5.3.6 we see that there are three possibilities
for range (a). Either,
1. range ( a) = I or,
2. range (a) = I U { 1}, or
3. range (a) = I U { 1, b} .
We will look at each range(a) individually in Claims 5.3.7, 5.3.8, and 5.3.9 respectively.
Again, we note that as KM is a Join Upper Bounded Algebra that satisfies the partial distributive
laws, we can invoke Claim 3.3.1.
Claim 5.3.7. Let I~ M \ {l,b} with OE/. If range(a) = I then a= eA(hu(a)) for some
hu E HU {Jo}.
Proof To show this suppose range (a) = I. Recall that we have already found an a E Ao where for
all j in range ( a) the following holds:
Vy E X1 y(a) E B1.
We want to show that a= eA (a). Let u = V row(i) then a= eA(hu(a)). Note that hu may not be
iEI
tangled. For example, if u = row(O) then hu = Jo which is not a tangled function. To show that
116
a= eA(hu(a) ), pick i in range ( a) and z in Xi. Then z(a) is in Bi (by Join Upper Bounded Algebra
Morphism Property) and z(a) tJ. Bj for j-/= i. Let b = z(a). We know a(z) = i. We have
(hu(a))( z) = z(hu(a)) = hu(z(a)) = hu(b)
and
a(z) = i ,
so to show that
a is an evaluation, it suffices to show hu (b) = i; or equivalently,
u I\ rowM(b) = rowM(i). As b E Bi we have j I\ b = j I\ i for all j E range (a). Therefore as
both u and rowM(i) are in {O, I} IF\ {fo J;d} I for all i in range(a) and we have,
u /\ rowM(b) = [
V rowM(j)] /\ rowM(b)
j Erange(a )
V (rowM(j) I\ rowM(b))
by distributivity in {O, I } IF\ {foJ;d} I
j Erange(a )
V rowM(j /\ b)
by Claim 3.3.1
j Erange(a )
V
rowM(j I\ i)
as j I\ b = j I\ i
V (row(j) I\ rowM(i))
by Claim 3.3.1
j Erange(a )
j Erange(a )
= [
V
rowM(j)] !\ rowM(i)
by distributivity in {O, 1} [F\ {fo,J;d} [
j Erange (a )
= u I\ rowM(i )
Hence, u I\ rowM (b) = rowM (i) and therefore hu (b) = i E M . This holds for all b E Bi and for
all i in range (a). Therefore, a (z) = hu (z (a)) = i for all i in range (a) and z in Xi. Therefore,
a= eA (hu (a)) where u = Vrow(i) when range ( a) = I. This is illustrated in Table 5.10.
iE/
117
D
=la E Ao
a
hu(a)
z(a)
a(z)
z(ph(a))
z
Vi EI Xi
If KM is an extension of a one-doubled-algebra then a = eA(hu(a)) when
Table 5.10:
range ( a) = I.
Claim 5.3.8. Let I~ M \ {1 ,b} with OE/. If range (a)= /U {1} then a= eA(qy(a)) for some
YE HU{fo}.
Proof Assume that I ~ M \ { 1, b} with O E /. We have an a in A such that for all j in range (a)
the following holds
Vy E Xj y(a) E BJ,
We now show that a= eA(qhu (a)).
Let u = V row(i) and set h = hu so that h EH U {Jo}. Take this particular hand define,
iEl
by
qh(x) =
1
if X E { 1, b}
{ h(x)
otherwise
Note that, qh E Q. To show that a= eA(qh(a)) pick j E range(a) and z E x1. Then z(a) is in B1
by the Join Upper Bounded Algebra Morphism Property and z(a) (/: Bi for i =I- j. Set z(a) = b. We
know that a(z) = j as z E x1. We have
118
and
a(z) = j ,
so to show that a is an evaluation, it suffices to show qh(b) = j. Therefore we must show that for
all j in range (a)= /U {1} and for all c E BJ that qh(c) = j. There are two cases.
Case 1 j = 1. Note that
Ji ={kEM:k /\ 1 = l}={l , b}
therefore
B 1 = {k E Ii : \i j E range (a) j I\ k = j I\ 1} = { 1, b}.
Take c E B1 = {1 , b }. Then qh(c) = 1 as needed.
Case 2 j E /. Take c E B1. Note that c is not in B 1 as B1 nB1 = 0 by Theorem 3.4.1. Thus,
qh(c) = h(c) as j ~ {l , b}
We must therefore show that h(c) = j. For this calculation to be true, we would need
hu(c) = j and therefore, u I\ rowM(c) = rowM(j). As c E BJ we have i I\ c = i I\ j for all
i E range ( a). Therefore as both u and rowM(j) are in {O, l} IF\{foJ;d} I we have,
u I\ rowM (c) = [
V rowM (i)] I\ rowM (c)
iErange(a )
V
(rowM(i) I\ rowM(c))
by distributivity in {O, 1} IF\ {fo,Jid} I
iErange (a )
V rowM (i I\ c)
by Claim 3.3.1
iErange(a )
119
V
rowM(i !\ j)
as i !\ c = i !\ j
(rowM(i) !\ rowM(j))
byClaim3.3.1
iErange(a)
V
iErange(ct)
= [
V rowM(i)] !\ rowM(j)
by distributivity in {O, l} IF\ {Jo,J;d} I
iErange (a )
= rowM(j)
Hence, u !\ rowM(c) = rowM(j) and therefore hu(c) = j EM.
Therefore, in any case we have for all j in /U{l} and for all c E Bj that qh(c) = j. Set k = qh(c).
Then a= eA(k) when range (a)= /U {1} as seen in Table 5.11.
D
::la E Ao
a
qh (a)
z(a)
a(z)
z(ph(a))
XJ
1
1
1
Vj EI Vy EXj
y(a) E Bj
j
j
VyE X1
y(a) E B1 = {1 ,b}
1
1
z
Vi EI Xi
Table 5.11:
If KM is an extension of a one-doubled-algebra then a = eA(qh(a)) when
range (a) = I U { 1} .
Claim 5.3.9. Let I~ M\ {1,b} with OE/. If range (a)= /U {l ,b} then a= eA(Py(a))for some
YE HU{fo}.
Proof Suppose I ~ M \ { 1, b} with O E /. Recall that we have a particular element a in A that
120
satisfies the following: for all j in range (a) and
We now show that a= eA(Py(a)).
Let u = V row(i) and set h = hu so that h EH U {Jo}. Take this particular hand define,
iE/
Ph :M-+M
by
if XE {1,b}
Ph(x) = { x
h(x)
otherwise
Note that, Ph E P. To show that a= eA(Ph(a)) pick j E range ( a) and z E X1. Then z(a) is in B1
by the Join Upper Bounded Algebra Morphism Property and z(a) tj. Bi for ii= j. Set z(a) = b. We
know that a(z) = j. We have
(ph(a)) (z) = z(ph(a)) = Ph(z(a)) = Ph (b)
and
a(z) = j ,
so to show that a is an evaluation, it suffices to show Ph(b) = j. Therefore we must show that for
all j in range (a)= /U {1} and for all c E B1 that Ph(c) = j. There are three cases.
Case 1: j = 1. Note that
Ji ={kEM:k A l=l}={l , b}
therefore
B 1 = { k E /1 : Vj E range (a) j A k = j A 1} = { 1}.
Take c E B1 = {1}. Then Ph(c) = 1 as needed.
121
Case 2: j = b. Note that
h={kEM:k A b=b}={b}
therefore
Bb = { k E lb : \;/ j E range (a) j A k = j A b} = { b} .
Take c E Bb = {b}. Then Ph(c) =bas needed.
Case 3: j E /. Take c E B1. Note that c is not in Bi for 1 E {1 , 2} as Bi nB1 = 0 by Theorem 3.4.1.
Thus,
Ph (c) = h( c) as j '¢ {1, b}
We must therefore show that h(c) = j. For this calculation to be true, we would need hu(c) = j and
therefore, u A rowM (c) = rowM (i). As c E BJ we have i A c = i A j for all i E range (a). Therefore
as both u and rowM(j) are in {O, l} IF\ {/oh} I we have,
u A rowM (c) = [
V
i)]
rowM (
A rowM (c)
iErange(a )
V (rowM(i) A rowM(c))
by distributivity in {O, 1} IF\ {Jo,!;d} I
iErange(a )
V rowM(i A c)
by Claim 3.3.1
iErange(a )
V rowM(i A j)
as i A c = i A j
iErange(a )
V (rowM(i) A rowM(j))
by Claim 3.3.1
iErange(a )
= [
V rowM(i)] A rowM(j)
by distributivity in {O, 1} IF\ {Jo,!;d} I
iErange(a )
= u A rowM(j)
Hence, u A rowM(c) = rowM(j) and therefore hu(c) = j EM.
122
Therefore, in any case we have for all j in I U { 1, b} and for all c E BJ that Ph (c) = j. Set
k = Ph(c). Then a= eA (k) when range ( a) = JU { 1, b }. This is illustrated in Table 5.12.
:3a E Ao
a
Ph(a)
z(a)
a(z)
z(ph(a))
XI
1
1
1
Xb
b
b
b
Vj EI Vy EX1
y(a) E B1
J
j
VyEX1
y(a) E B1 = {1}
1
1
VyEXb
y(a) E Bb = {b}
b
b
z
D
Vi EI Xi
Table 5.12:
If KM is an extension of a one-doubled-algebra then a = eA(Ph(a)) when
range (a) = I U { 1, b}.
Using the element a in A that was found with the Join Upper Bounded Algebra Morphism
Property and for any range(a) we have by Claims 5.3.7, 5.3.8, and 5.3.9 that a= eA (a). Hence,
KM is dualisable and we have completed the proof of Theorem 5.3.5.
5.3.1
An Example of a One-Doubled-Algebra
The algebra,
M = ({O, 1,2, 3,4} , {!1 ,fz, !3,Jo})
is a one-doubled-algebra that is not dualisable. The operations !1 ,fz ,h and Jo are defined in
Table 5.13 . We note that row(I) = row(3). When the tangled operations how and h011 (defined in
123
Table 5.13) are added to the operation set, the algebra given by
({O, 1, 2, 3,4 }, {!1 , h,h,!o} U {horn, holl} )
is presumably not dualisable (currently unknown). However when the operations PJo ,Phow ,qhow
and qh011 (defined in Table 5.13) are also added, then the algebra given by,
({O, 1, 2, 3, 4}, {!1 ,!2,h,!o} U{ho10 ,ho11} U{PJ0 ,Ph010 , qh010 , qh01 J)
is dualised by
:Ml= (M, I\, V, 0, g, ge30, 5).
We do note that for this algebra, the operation set FU HU PU Q is closed under composition as
seen in Table 5.14.
f1 = qfo h h
Jo horn holl PJo
Pho10
Pho11
qho10
qho11
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
1
1
1
1
2
0
1
0
0
2
2
0
2
2
2
2
3
1
0
0
0
0
0
3
3
3
1
1
4
0
1
1
0
2
4
0
2
4
2
4
Table 5.13: An example of a one-doubled-algebra where the row(3) = row(l ).
124
J1
h
h
Jo how ho11
PJo
Pho10
Pho11
qho1 0
qho11
J1
J1
h
h
Jo
Jo
Jo
J1
J1
J1
J1
J1
h
Jo Jo Jo Jo
h
h
Jo
h
h
h
h
h
Jo Jo Jo Jo
Jo
h
Jo
Jo
h
Jo
h
Jo
Jo Jo Jo Jo
Jo
Jo
Jo
Jo
Jo
Jo
Jo
how
Jo Jo Jo Jo how how
Jo
horn
how
horn
horn
ho11
Jo Jo Jo Jo how how
Jo
horn
hall
horn
ho11
Pfo
J1
Jo Jo Jo
PJo
PJo
PJo
J1
J1
Pho10
J1
h
h
Jo how how PJo
Pho10
Pho10
qho10
qho10
Pho11
J1 h
h
Jo how hall PJo
Pho10
Pho11
qho10
qho11
qho10
Ji h
h
Jo ho JO how
J1
qhow
qho10
qhow
qho10
qho11
Ji h
h
Jo how hall
J1
qhow
qho11
qhow
qho11
Jo
Jo
Table 5.14: The compositions of the operations in F UH UP U Q therefore showing this particular
one-doubled-algebra is closed.
125
Chapter 6
An Example of a
Non-One-Doubled-Algebra
In this chapter we define a non-one-doubled-algebra, M, where the row(3) = row(4) and show it is
not dualisable. Currently, we have been unable to determine if including all the tangled functions
implies the algebra is dualisable. However, we do show that if we include all the tangled functions,
as well as three double functions, then the extension algebra is dualisable. It is unknown if the
double functions are tangled.
6.1
Mis Not Dualisable
Let M = ({O, 1, 2,3 ,4}, {fo,h,!3,!4}) where the functions are as defined in Figure 6.1. We begin
by showing that Mis a Join Upper Bounded Algebra (Lemma 6.1.1). In Lemma 6.1.6 we then
show that Mis a non-one-doubled-algebra where the row(3) = row(4) . Here, we fix 3, 4 and :'.S,
and set 3 :'.S 4. From now on we will use M to refer to the set {O, 1, 2, 3,4 }.
126
M
Jo h
h f4=Jt
0
0
0
0
0
1
0
0
0
1
2
0
1
0
0
3
0
0
1
1
4
0
0
1
1
4
2
0
Figure 6.1: M = ({O, 1,2,3,4} , {fo,!2 ,!J,J4} ).
Notice that the operations respect the order illustrated in Figure 6.1. This order induces a meet
operation. Because the operations respect this order, the meet operation is a homomorphism.
Lemma 6.1.1. The algebra, M = ({0, 1, 2,3,4} ,{fo,J2 ,h,!4} ), is a {O , I}-valued Join Upper
Bounded Algebra that satisfies the partial distributive laws.
To prove Lemma 6.1.1, we need to show that Mis a {O, !}-valued finite unary algebra with
zero, and that M also satisfies the following:
1. I\ : (M) 2 --+ M is a semilattice homomorphism on M with least element O;
2. V is a partial algebraic operation on M that is not total; and,
3. if u, v, w EM such that u ~ wand v ~ w then u V v EM.
To show this, we will need Claims 6.1.2, 6.1.3 and 6.1.4.
Claim 6.1.2. The map, I\ : (M) 2 --+ M, is a semilattice homomorphism on M with least element 0.
Proof We define
/\ (a ,b) = the intersection of the row(a) with column(b) in the matrix given by:
127
0 0 0 0 0
0 1 0 1 1
/\ =
0 0 2 0 0
0 1 0 3 3
0 1 0 3 4
The columns of the above matrix are ordered as column 0, 1, 2, 3, 4 and the rows are ordered
as row 0, 1, 2, 3, 4. For example, we have /\ (1 , 2) = 0 and /\ (3 ,4) = 3. Note that O is the least
element.
We must show that for every fin F and for every (a, b) in M 2 the following holds:
f( /\ (a ,b)) = /\ (f(a),f(b)).
We will show this for one particular element of M 2 , namely (2 ,4). The rest can be shown in a
similar manner.
fo (/\ (2,4)) = fo(O)
as /\ (2,4) = 0
=0
as /\ (0, 0) = 0
= /\ (0,0)
= A(fo(2),Jo( 4))
h (/\ (2,4)) = h (O)
=0
= /\ (1 ,0)
as I\ ( 1, 0) = 0
= /\ (h(2 ), h (4))
128
h( /\ (2,4)) = !J(O)
=0
as /\ (0, 1) = 0
= /\ (0, 1)
= !\ (h (2) ,h( 4))
f4( !\ (2 , 4)) = f4(0)
=0
as /\ (0, 1) = 0
= /\ (0, 1)
= /\ (!4(2),!4( 4))
Therefore, for all fin F we have f( /\ (2,4)) = /\ (!(2),!(4)). This holds for all (a ,b) in M. So !\
D
is indeed a homomorphism defined on M.
Claim 6.1.3. The map, V : N ---t M for N ~ M 2, is a partial algebraic operation on M.
Proof Let N ~ M 2 . We must show that for every (a , b) in N 2 where a Vb is defined in M that
f( V (a ,b)) = v (f(a),f(b))
for every f in F. We define
0
V=
1
2
3
4
1 1
-
3
4
2
-
2
3
3
-
3
4
4
4
-
3
4
where,
V (a ,b) = the intersection of the row(a) with column(b) in the matrix above.
129
Again, the columns of the above matrix are ordered as column 0, 1, 2, 3, 4 and the rows are ordered
as row 0, 1, 2, 3, 4.
As an example, we have V( l ,2) = undefined and V(3,4) = 4.
We will show this holds for the element (3, 1). The proof for the remaining elements in M 2 is
similar.
as V(3, 1) = 3
fo(V(3, 1)) = fo(3)
=0
= V(O,O)
as v(O,O) = 0
= V (Jo (3) ,Jo ( 1) )
h(V(3, 1)) = f2(3)
=0
= V(O,O)
as V(O,O) = 0
= V(f2(3) ,h( l))
f3(V(3, 1)) = !3(3)
=l
=V(l,O)
as v(l, O) = 1
= V(f3 (3),f3(1))
f4(V(3, 1)) = f4(3)
=l
as v( l , 1) = 1
= V( l , l)
= V(j4(3),f4( l))
130
Hence, for every fin F we have f( V(3 , 1)) = v (f(3),f(l)). But this will hold for all (a ,b) in M 2
when a Vb is defined. So V is a partial homomorphism defined on M.
0
Claim 6.1.4. If u, v, w E M such that u ::; w and v ::; w then u V v E M.
Proof We show this by looking at all possible cases.
1. For every b E {0,2}, ifO::; 2 and b::; 2 then OV b = b EM.
2. For every b ,c E {1 , 3, 4}, when O::; c and b::; c then OV b = b EM.
3. For every a , b , c E { 1, 3, 4 }, when a ::; c and b ::; c then a Vb E { 1, 3, 4} EM.
And therefore, whenever u, v, w E M with u ::; w and v ::; w it holds that u V v E M .
0
We now prove Lemma 6.1.1 which shows that the algebra Mis a {O, !}-valued Join Upper
Bounded Algebra.
Lemma 6.1.5. The algebra, M = ({0, 1, 2, 3,4} , {fo ,h ,!3,f4}), is a {0 , 1}-valued Join Upper
Bounded Algebra that satisfies the partial distributive laws.
Proof First note that Mis a {O, 1}-valued finite unary algebra with zero (a row and a column of
zeros). By Claims 6.1.2, 6.1.3 and 6.1.4 it follows that Mis a {O, 1}-valued Join Upper Bounded
N~~-
0
Recall that an algebra is a non-one-doubled-algebra if it is a { 0, 1}-valued Join Upper Bounded
Algebra (where b1 , b2 and ::; are fixed) that satisfies the following:
1. There exists b 1, b2 in M with b 1 -/- b2 such that
131
(a) row(b1) = row(b2),
(c) 0 < b1 -< b2, and
(d) row(c) # row(b1) for any c # { b1 , b2} in M;
2. There does not exist an x E M with b2 < x; and,
3. M \ {b 2 } forms a sub-sernilattice of M;
4. The restricted algebra, (M \ {b2},FIM\{bz}), forms a Join Upper Bounded Algebra with
unique rows.
5. For every X ~ M \ {b1 ,b2} we have V row(x) j row(b1).
xEX
We use this definition to show M is a non-one-doubled-algebra, in Lemma 6.1.6.
Lemma 6.1.6. The algebra M = ({O, 1, 2, 3,4} , {fo,h ,h,f4} ) is a non-one-doubled-algebra.
Proof By Lemma 6.1.1 we know that Mis a Join Upper Bounded Algebra. To show we actually
have a non-one-doubled-algebra we further note that
1. the elements 3 and 4 exist in M with 3 # 4 such that
(a) row(3) = row(4) ,
(b) 3 # 1 and 4 # 1,
(c) the order O < 3 -< 4 holds, and
(d) row(c) # row(3) ,row(4) for any c # 3,4 in M;
2. There does not exist an x E M with 4 < x;
132
3
Jo h h
f4 =Ji
0
0
0
0
0
1
0
0
0
1
2
0
1
0
0
3
0
0
1
1
2
0
Figure 6.2: (M \ {4} ,FIM\ {4} ).
3. Moreover, as seen in Figure 6.2 we have (M \ {4} ,FIM\ {4}) forms a Join Upper Bounded
Algebra where M \ {4} forms a sub-sernilattice of M;
4. The restricted algebra, (M \ { 4} ,FIM\ {4}), forms a Join Upper Bounded Algebra with unique
rows; and
5. For every X <;;;; M \ {3 ,4} = {O, 1, 2} we have either
X = {O} so row(O) = (0,0,0) j (0, 1, 1) = row(3);
X = {1} or {1,0} so row(l) = (0,0, 1) j row(3);
X = {2} or {2, 0} so row(2) = (1,0,0) j row(3);
X = {1,2} or {O, 1, 2} so row(l) V row(2) = (1,0, 1) j row(3) .
Therefore, for every X <;;;; M \ {3 ,4} we have V row(x) j row (3) = row(4).
xEX
So, M is a non-one-doubled-algebra.
And finally, we note that by Corollary 5.1.3 as every f in F respects both the I\ homomorphism and the partial V homomorphism we have for all a,b and c in M whenever (a V b),
(a V c) and a V (b I\ c) are all defined in M then (a Vb) I\ (a V c) = a V (b I\ c). Similarly, whenever
133
(a I\ b) V ( a I\ c) and b V c are all defined in M then ( a I\ b) V ( a I\ c) = a I\ ( b V c). So M satisfies
D
the partial distributive laws.
Now that we have shown that M is a non-one-doubled-algebra, we will refer to and use the
theorems in Section 5.2 to show that
is dualisable (this is done in Section 6.3). In order to do this we will need to define the tangled
operations on M. From now on we will use a1a2a3 to represent the tuple (a1 ,a2 ,a3) .
Recall the set
~
fl= { Vrow(v): C M \ {3 ,4}}
vEC
from Section 5.2 that is used to find the tangled operations. This set, defined on M will be,
fl= {000, 100,001 , 101} where 101 = row(l) V row(2).
Furthermore, the operations given by
hooo and hoo1 are respectively the operations Jo and f4 = ft found in F. Therefore, both hooo and
hoo1 are not tangled. However, the operations given by h100 and h101 are not found in F and are
given below. For all x E M define
h10o(x) = the unique b EM where, 100 /\ row(x) = row(b)
and
h101 (x) = the unique c EM where, 101 I\ row(x) = row(c).
The operations, h100 and h101 are defined in Table 6.1. By Theorem 5.1.5 we have F ,,< h100 and
F ./ h101.
134
6.2
Unable to Determine if Mtang is Dualisable
Let M1ang = ({O, 1, 2, 3,4} , {Jo ,h ,!3,f4} U {h100 , h1oi} ) be defined as in Table 6.1. Then M1ang
the extension algebra of M that has all the tangled operations included.
Jo h
h J4 = J{' hwo
h101
0
0
0
0
0
0
0
1
0
0
0
1
0
1
2
0
1
0
0
2
2
3
0
0
1
1
0
1
4
0
0
1
1
0
1
Table 6.1: M1ang = ({O, 1, 2, 3,4} , {Jo ,h, !3,f4} U {h100 , h10i} ).
At this point in time we are unable to determine if M1ang is dualisable or not. Upon building
a morphism a: X-+ M where A :S (Miangt and X = hom(A,M1ang), we were unable to find an
a EA such that a= eA (a) for the cases when range (a)= {O, 3,4} and range ( a) = {O, 1, 3,4}. It
would appear that we need the unary functions given by
if X = 3, 4
Pr(x) = { x
y(x)
otherwise
for
YE HU {Jo,!{' }= {h100, h10i} U {Jo,!{' },
to remedy this situation (refer to Table 6.2 for the Pr's). At this time, we are unable to show that
the Pr's are tangled.
135
JM is Dualisable
6.3
Let JM = ( {O, 1, 2, 3,4} , {fo ,h ,/3,f4} U {h100 , h10i} U{PJo, PJ(, Ph 100 ,Ph 101}U {h101 o Ph 100 } ) where
the functions are as defined in Table 6.2.
° Ph100
Jo h
h
f4 = Jt
h100
h101
Pio
PJ(
Ph100
Ph101 = id
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
1
0
1
0
2
0
1
0
0
2
2
0
0
2
2
2
3
0
0
1
1
0
1
3
3
3
3
1
4
0
0
1
1
0
4
4
4
4
1
h101
Table 6.2: JM = ({O, 1, 2, 3,4} , {fo ,h ,/3,f4} U {h100 , h1oi} U {PJ0,PJ(, Ph 100 ,Ph 101 } ).
Let M = {O, 1, 2, 3,4}, F = {fo,h ,!3,f4} , H = {h100 , h10i} , and P = {PJ0,PJ(, Ph 100 ,Ph 101 }.
We know from Table 5.8 and Table 5.9 found in Section 5.2.1 that FU HU P is not closed under composition. We therefore include the operation h101 o Phi oo in the extension algebra. Then
JM = (M ,F UHUPU {h101 o Ph 100 } ) is dualised by M = (M, /\, V, O, g3 , g4 ,8e52 + s , 5 ). The remainder of this section outlines the details of and follows the proof of Theorem 5.2.5 specific to
our non-one-doubled-algebra, JM.
To show our algebra is dualisable, we must first confirm that it is closed under composition. Again, this was shown in Table 5.8 and Table 5.9 found in Section 5.2.1. Therefore,
F UHUPU {h101 o Phi oo } is closed under composition. By Theorem 5.2.2 we know that the operations in HU P respect both the I\ homomorphism and the partial V homomorphism. Since both
h101 and Phioo respect both the I\ homomorphism and the partial V homomorphism their composi-
136
tion will as well (Corollary 3.3.4). Therefore by Theorem 5.2.3, JM satisfies the partial distributive
laws . We therefore know, by Theorem 5.2.5, that JM is dualisable. We go through the details
below. We start by defining the homomorphisms, g3 and g4.
First recall from Claim 5.2.4 that the two maps, g3 ,g4 : JM-+ JM defined by
3
if X = 4
x
otherwise;
4
if X = 3
x
otherwise.
and
are homomorphisms on JM.
Set M = (M ,/\, V, O,g3 , g4 ,a?52+s , !!/). Since JM is finite, by the duality compactness theorem it is sufficient to show A S:! ED (A) for every finite A E I[§JP (JM). Pick A ::; Mn, and let
X = hom(A, JM). We want to show that each morphism a : X -+ M is an evaluation at some a EA .
We do this by showing that for each possible range ( a), the map a is an evaluation at some a in
Ao.
As JM is a {O, 1}-valued finite unary algebra we have by Theorem 3.4.2 that there is an a in Ao
that satisfies the Join Upper Bounded Algebra Morphism Property. Hence, for all j in range (a)
the following holds:
\/y E Xj y(a) E Bj
where Bi = {b E Ii: \/j E range (a) j /\ b = j /\ i} and Ii = {b EM: b /\ i = i} = {b EM : b ?. i}.
We will apply this to the possible ranges of the morphism a , however we first evaluate Ix for every
x in M. Consider,
Io= {b EM : b /\ 0 = O} = {b EM: 0 ::; b} = {O, 1, 2, 3,4}
137
and
/i = {b EM: b A 1 = 1} = {1 , 3,4}
and
Ji= {bEM:b A2=2} = {2}
and
h = {b EM: b A 3 = 3} = {3 ,4}
and
/4 = { b E M : b A 4 = 4} = {4}.
To prove that a is an evaluation at some a in A for every possible range (a) we must first determine the different possibilities for range ( a). Using the two homomorphisms g3 and g 4, and
Lemma 5.2.6 we know that O is always in range (a) and 3 will be range (a) if and only if 4 is also
in range (a). Therefore, the possible cases for range (a) are:
1. range(a) = {O}
2. range(a) = {O, 1}
3. range(a) = {0, 2}
4. range(a) = {O, 1, 2}
5. range(a) = {0, 3,4}
6. range(a) = {0, 2,3 ,4}
7. range(a) = {O, 1, 3,4}
8. range(a) = {O, 1, 2, 3,4}.
138
We now look at each range ( a) individually and show that a is an evaluation at some a in A for each
range ( a). The case when range ( a) = {O, 1} is looked at in detail. The other cases are simplified.
Lemma 6.3.1. If range (a)= {O, 1} then a= eA(f4(a)) = eA(f((a)).
Proof We have range(a) = {O, 1}. Note that
Bo = { b E Io : Vj E range (a) j I\ b = j I\ 0}
= {b E {O, 1, 2, 3,4}: VJ E {O, 1} j /\ b = j /\ 0}
= {b E {O, 1, 2, 3,4} : 0 /\ b = 0 /\ 0 and 1 /\ b = 1 /\ 0}
= {b E {O, 1, 2,3,4}: 0/\b = 0 and 1 /\ b = O}
= {0, 2}
and
B 1 = {b E /i : Vj E range (a) j I\ b = j I\ 1}
={bE{l,3,4}:VjE{0,1} j /\ b=j /\ l}
= {b E { 1, 3, 4} : 0 I\ b = 0 I\ 0 and 1 I\ b = 1 I\ 1}
= {b E {1 , 3,4}: 0 /\ b = 0 and 1 /\ b = 1}
= {1 , 3,4}.
Then, for all y E Xo U X1 we have
eA(f4(a))(y) = y(f4(a))
= f4(y(a))
= a(y).
139
Therefore, a = eA (!4 (a)) and hence a is an evaluation for range (a) = { 0, 1}. This is illustrated
in Table 6.3 on page 142. We note that
f4 = ft = hrow( J) = h (
V
row(a)
) ·
aErangc(a )
D
Lemma 6.3.2. If range (a) = { 0} then a = eA (Jo (a)).
Proof Let a E A . Then a = eA (Jo (a)). Again, Jo was chosen as
Jo= hrow(O) = h(
V
row(a)
) .
a Erange(a )
D
Lemma 6.3.3. If range (a)= {0,2} then a= eA(h100 (a)).
Proof Here, Bo and B2 are found in Table 6.4 on page 142. Then, a= eA(h10o(a)) and hence a
is an evaluation for range (a) = {0, 2}. We note that
h JOO = h (row(O)Vrow(2)) = h (
V
row(a)
) ·
aE rangc(a)
D
Lemma 6.3.4. lfrange(a) = {O, 1, 2} then a= eA(h101 (a)).
Proof We have range(a) = {O, 1, 2}. Here, Bo, B1 and B2 are found in Table 6.5 on page 143.
Therefore, a= eA(h101 (a)) and hence a is an evaluation for range (a)= {O, 1, 2}. We note that
h101 = h (row(O)Vrow( l )Vrow(2)) = h(
V
) ·
row(a)
aE range(a)
D
140
Lemma 6.3.5. If range (a )= {0,3,4} then a= eA (PJo (a)).
Proof We have range(a ) = {0, 3,4} . Here, Bo, B3 and B4 are found in Table 6.6 on page 143.
Then, a = eA (pJo (a)) and hence a is an evaluation for range (a ) = {0, 3, 4}.
D
Lemma 6.3.6. If range (a)= {0, 2, 3,4} then a= eA (Ph,o, (a)) = eA(a).
Proof We have range(a ) = {0,2,3,4}. Here, Bo, B2, B3 and B4 are found in Table 6.7 on
page 144. Then, a = eA (a) and hence a is an evaluation for range (a ) = { 0, 2, 3, 4}.
D
Lemma 6.3.7. /frange(a ) = {0, 1, 3,4} then a= eA (Pft (a)).
Proof We have, range (a ) = {0, 1, 3,4} . Here, Bo , B1 , B3 and B4 are found in Table 6.8 on
page 144. Then, a = eA (p ft (a) and hence a is an evaluation for range (a) = {0, 1, 3, 4}.
D
Lemma 6.3.8. If range (a ) = {0, 1, 2,3,4} then a= eA (Ph,o, (a)) = eA (a).
Proof We have range(a) = {0, 1,2,3,4}. Here, Bo , B1 , B2, B3 and B4 are found in Table 6.9.
Then, a= eA (a) and hence a is an evaluation for range (a ) = {O, 1, 2, 3, 4}.
D
We have therefore shown (Lemmas 6.3.2, 6.3 .1, 6.3.3, 6.3.4, 6.3.5, 6.3.6, 6.3.7, 6.3.8) that
for any range(a ) we have a= eA (a ) and thus, A~ ED (A). Since this holds for every finite
A E lI§lP' (JM), by the duality compactness theorem, JM is dualised by :MI therefore completing the
proof.
141
Va' EAo
:la E Ao
a
f4(a)
z
z(a')
z(a)
a(z)
z(hu(a))
xo
0
0
0
0
XJ
1
1
1
1
0
0
1
1
yEXo
y(a)'Elo y(a) E Bo
yEX1
y(a) El1
1
y(a) E B1
Table 6.3: range(a) = {O, 1}.
Va' E Ao
:la E Ao
a
h1oo(a)
z
z(a')
z(a)
a(z)
z(hu(a))
xo
0
0
0
0
Xz
2
2
2
2
yEXo
y(a)' Elo y(a) E Bo= {O, 1, 3,4}
0
0
yEX2
y(a) 1 E]z
2
2
y(a) E B2 = {2}
Table 6.4: range(a) = {0,2}.
142
Va' EAo
3a EAo
a
h101 (a)
z
z(a')
z(a)
a(z)
z(hu(a))
xo
0
0
0
0
XJ
1
1
1
1
x2
2
2
2
2
y(a) E Bo= {O}
0
0
yEXo y(a)' Elo
yEX1
y(a)' E/i
y(a) E B1 = {1 ,3,4}
1
1
yEX2
y(a)'E/i
y(a) E B2 = {2}
2
2
Table 6.5: range(a) = {O, 1,2}.
Va' EAo
3a EAo
a
PJ0 (a)
z
z(a')
z(a)
a(z)
z(hu(a))
xo
0
0
0
0
X3
3
3
3
3
X4
4
4
4
4
yEXo y(a)'Elo y(a) E Bo= {0,2}
0
0
yEX3
y(a)'Eh
y(a) E B3 = {3}
3
3
yEX4
y(a) 1 El4
y(a) E B4 = {4}
4
4
Table 6.6: range(a) = {0,3,4}.
143
Va' EAo
:la E Ao
a
a= Ph101
z
z(a')
z(a)
a(z)
z(hu(a))
xo
0
0
0
0
x2
2
2
2
2
X3
3
3
3
3
X4
4
4
4
4
yEXo
y(a)' Elo y(a) E Bo= {O}
0
0
yEX2
y(a)'E/i y(a) E B2 = {2}
2
2
yEX3
y(a)'Eh
y(a) E B3 = {3}
3
3
yEX4
y(a) 1 El4 y(a) E B4 = {4}
4
4
Table 6.7: range(a) = {0,2,3,4}.
Va' EAo
:la E Ao
a
PJ((a)
z
z(a')
z(a)
a(z)
z(hu(a))
xo
0
0
0
0
XI
1
1
1
1
X3
3
3
3
3
X4
4
4
4
4
0
0
yEXo
y(a)'E lo y(a) E Bo= {0,2}
yEX1
y(a) E l1
1
y(a) E B1 = {1}
1
1
y EX3
y(a)'Eh
y(a) E B3 = {3}
3
3
yEX4
y(a) E l4
1
y(a) E B4 = {4}
4
4
Table 6.8: range(a) = {O, 1, 3,4}.
144
Va' E Ao
:3a E Ao
a
a= Ph101 (a)
z
z(a')
z(a)
a(z)
z(hu(a))
xo
0
0
0
0
XJ
1
1
1
1
Xz
2
2
2
2
X3
3
3
3
3
X4
4
4
4
4
0
0
yEXo y(a)'Elo y(a) E Bo= {O}
yEX1
y(a) 1 El1
y(a) E B1 = {1}
1
1
yEX2
y(a)'E/z y(a) E B2 = {2}
2
2
y EX3
y(a)'El)
y(a) E B3 = {3}
3
3
yEX4
y(a)'E/4
y(a) E B4 = {4}
4
4
Table 6.9: range(a) = {O, 1,2,3,4}.
145
Chapter 7
Conclusion
7.1
Summary
To summarize, we defined Join Upper Bounded Algebras and specifically looked into the dualisability of extensions of {O, 1}-valued Join Upper Bounded Algebras with unique rows, nonone-doubled-algebras and one-doubled-algebras. In Chapter 4, we saw that the extension of a
{O, 1}-valued Join Upper Bounded Algebra with unique rows needed to only include the tangled
operations defined on the algebra, in order for the algebra to be dualisable. In Chapter 5, however,
when looking into {O, 1}-valued Join Upper Bounded Algebras with non-unique rows, namely
non-one-doubled-algebras and one-doubled-algebras, we saw that the extensions needed to include
operations that we knew to be tangled, along with the double functions which are conjectured to
not be tangled. In every case, we used the Join Upper Bounded Algebra Morphism Property (found
in Chapter 3) to find the existence of an element that allowed the morphism a to be an evaluation
map, therefore proving that the extension algebras were dualisable. We used the duality compactness theorem in conjunction with the Join Upper Bounded Algebra Morphism Property to prove
146
the alter ego dualised each algebra.
7.2
Future Work
For Join Upper Bounded Algebras with unique rows we showed that the extension algebra that
included all the tangled operations was dualisable. However, when dealing with non-one-doubledalgebras and one-doubled-algebras, work suggested that including the tangled operations alone
was not enough to guarantee the algebras were dualisable. This is why we included the double
functions. Further work could be done to determine whether or not the extensions of non-onedoubled-algebras and one-doubled-algebras that include only tangled operations, are dualisable.
Are the double functions needed? Moreover, with the current definition of tangling, the double
functions are conjectured to not be tangled due to the repeated rows found in non-one-doubledalgebras and one-doubled-algebras. Work could be done to prove these double operations are in
fact not tangled.
One problem that arose, and therefore requires further attention, is the closure of the operation sets FU H, FU HU P and FU HU PU Q found in the extensions of {O, 1}-valued Join
Upper Bounded Algebras with unique rows, non-one-doubled-algebras and one-doubled-algebras,
respectively. We saw an example where the set was closed and an example where the set was not
closed. Is it possible to determine when these sets are guaranteed to be closed? Can we generalize
what operations must be added to make the sets closed?
And finally, we showed that for:
1. The extensions of {O, 1}-valued Join Upper Bounded Algebras with unique rows, where all
147
the tangled operations are included, is dualised by the alter ego
2. Extensions of non-one-doubled-algebras with all the tangled operations and all double operations included, is dualised by the alter ego
and,
3. Extensions of one-doubled-algebras with all the tangled operations and all double operations
included, is dualised by the alter ego
However, we did not look into whether the alter egos that were used, yielded full or strong dualities
on the algebra. Moreover, it is unknown if the alter ego is the smallest possible alter ego that
dualises the algebra. These are some areas that could receive further attention.
148
Bibliography
[1] S. Burris and H.P. Sankappanavar, A course in universal algebra, Springer-Verlag, New York,
USA, 1981.
[2] D. Casperson, J. Hyndman, J. Mason, J.B. Nation, and B. Schaan, Existence offinite bases for
quasi-equations of unary algebras with 0, International Journal of Algebra and Computation
25(2015),no.06, 927-950.
[3] D. Casperson, J. Hyndman, and B. Schaan, Tangling in unary algebras with meet semilattices,
In preparation, 2014.
[4] D.M. Clark and B.A. Davey, Natural dualities for the working algebraist, Cambridge University Press, New York, USA, 1998.
[5] D.M. Clark, B.A. Davey, and J. Pitkethly, Binary homomorphisms and natural dualities, J.
Pure Appl. Algebra 169 (2002), 1-28.
[6]
, The complexity of dualisability: three-element unary algebras, International Journal
of Algebra and Computation 13 (2003), no. 3, 361-391.
[7] B.A. Davey, M. Jackson, J.G. Pitkethly, and M.R. Taluker, Natural dualities for semilatticebased algebras, Algebra Universalis 57 (2007), 463-490.
149
[8] B.A. Davey and J. Pitkethly, Dualisability: Unary algebras and beyond, New York: Springer,
USA, 2005.
[9] B.A. Davey and H.A. Priestley, Introduction to lattices and order, second edition ed., Cam-
bridge University Press, New York, USA, 2002.
[10) B.A. Davey and R. Willard, The dualisability of a quasi-variety is independent of the gener-
ating algebra, Algebra Universalis 45 (2001), 103-106.
[11) J. Hyndman, Strong duality of finite algebras that generate the same quasi variety, Algebra
Universalis 51 (2004), 29-34.
[12) J. Hyndman and R. Willard, An algebra that is dualizable but not fully dualizable, J. of Pure
and Applied Algebra 151 (2000), 31-42.
[13) James R. Munkres, Topology, 2 ed. , Prentice Hall, Upper Saddle River, NJ, 2000.
[14) Todd Niven, Dualizable but not fully dualizable algebras, International Journal of Algebra
and Computation 17 (2007), no. 2, 347-367.
[15) H. A. Priestley, Representation of distributive lattices by means of ordered stone spaces, Bull.
London Math. Soc. 2 (1970), 371-377.
[16)
, Ordered topological spaces and the representation of distributive lattices, Proc.
London Math. soc. 24 (1972), no. 3, 507-530.
[17) Brian Schaan, On the dualisability of finite {O, 1}-valued unary algebras with zero, Master's
thesis, University of Northern British Columbia, Prince George, British Columbia, 2014.
[18) L. Zadori, Natural duality via a finite set of relations, Bull. Austral. Math. Soc. 51 (1995),
469-478 .
150