Galois Connections and Applications
Galois Connections and Applications
Galois Connections and Applications
Managi ng Editor:
M. HAZEWINKEL
Centre for Mathematics and Computer Science, Amsterdam, The Netherlands
Volume 565
Galois Connections and
Applications
Edited by
K. Denecke
University of Potsdam,
Potsdam, Germany
M. Erne
University of Hannover,
Hannover, Germany
and
S. L. Wismath
University of Lethbridge,
Lethbridge, Canada
Preface . Vll
M. Erne
Adjunctions and Galois Connections: Origins, History and Devel-
opment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
G. Janelidze
Categorical Galois Theory: Revision and Some Recent Develop-
ments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
M. Erne
The Polarity between Approximation and Distribution . . . . . 173
K. Denecke, S. l. Wismath
Galois Connections and Complete Sublattices . . . . . . . . . . 211
R. Poschel
Galois Connections for Operations and Relations . . . . . . . . 231
K. Kaarli
Galois Connections and Polynomial Completeness . . . . . . . . 259
A. Szendrei
A Survey of Clones Closed Under Conjugation . . . . . . . . . . 297
P. Burmeister
Galois Connections for Partial Algebras . . . . . . . . . . . . . 345
K. Denecke, S. l. Wismath
Complexity of Terms and the Galois Connection Id-Mod . . . . 371
Vl Contents
J. lambek
Iterated Galois Connections in Arithmetic and Linguistics . . . 389
I. Chajda, R. Hala~
Deductive Systems and Galois Connections . . . . . . . . . . . 399
J. Slapal
A Galois Correspondence for Digital Topology . . . . . . . . . . 413
w. Gahler
Galois Connections in Category Theory, Topology and Logic . . 425
R. Wille
Dyadic Mathematics - Abstractions from Logical Thought . . . 453
Index . . . . . . . . . . . . .. .. . . . . . . . . . . . . . .. . 499
Preface
One or two decades later, the even more general notion of adjoint
functors was discovered by workers in category theory, and various
very useful types of categorical Galois correspondences were subse-
quently invented.
Concerning the position of Galois connections within mathematics, it
has to be admitted that deep theorems rarely are immediate conse-
quences of the general theory of Galois connections, but usually require
some extra tools and ideas stemming from the specific theory under
consideration. But the general framework, supporting the intuition
and suggesting the appropriate concepts, is established by the discov-
ery of the "right" underlying Galois connection, followed by a good
characterization of the "Galois-closed" (or "Galois-open") elements or
sets. And there is no doubt that many proofs become shorter, more
elegant and more transparent in the language of Galois connections.
The aim of this book is to present not only the main ideas of gen-
eral Galois theory, of concepts related to Galois connections, and of
their appearance in various classical and modern areas of mathemat-
ics, but also to show how they can be applied in other disciplines. The
book consist of 15 contributions, written by authors who are special-
ists in diverse fields of mathematics and who use Galois connections
in their work. Although the majority of the contributions are dealing
with themes of classical and universal algebra, the reader will also find
many logical, order-theoretical, topological and categorical aspects -
and, last but not least , several practical applications, sometimes even
in extra-mathematical fields like linguistics, digital representation of
graphics, or data analysis. In fact, the methods of modern formal
concept analysis, based on polarities arising from certain relations be-
tween objects and attributes, have applications in quite diverse non-
mathematical areas of sciences and arts. Readers interested in that
theory, its mathematical background and its applications, are referred
to the monograph Formal Concept Analysis - Mathematical Founda-
tions by B. Ganter and R. Wille (Springer-Verlag, 1999).
mal varieties to the k-th level and illustrate the limitations of such
extensions.
In the survey 11 Q-Independence and Weak Automorphisms as Galois
Connections", K. Glazek and S. Niwczyk present two further kinds of
Galois connections appearing in universal algebra. These are related
to general notions of independence and of weak automorphisms. In
the first case, the basic relation for the required polarity is defined
between subsets and partial maps of a fixed algebra: a subset X is
related to a partial map p if the latter extends to a homomorphism
on the subalgebra generated by X whenever X is the domain of p. In
the second case, the basic relation is defined between permutations of
a fixed set and clones over that set, and it holds iff the permutation
preserves the clone (in a natural way).
The last three papers are devoted to themes where categorical methods
help to generalize and to improve classical results of topology and
Galois theory.
W. Gahler shows in his survey Galois Connections in Category The-
ory, Topology and Logic how partially ordered monads (a categorical
notion very close to adjoint situations) provide the right framework
for a very general development of abstract categorical topology and
convergence theory. The basic idea here is to suitably generalize the
"classical" filter monad, which has proved basic for many questions
of convergence theory in the past. But, as recent developments have
shown, there is also a large overlap of such topological theories with
non-classical logics and computer sciences (see, for example, t he book
by St. Vickers: Topology via Logic (Cambridge Tracts in Th. Comp.
Sc. 5, Cambridge University Press, 1989). In the second part of this
paper, various types of fuzzy filters in locales and quantales are stud-
ied more thoroughly, and their interdependencies are illustrated by
several diagrams.
J. Slapal's note A Galois Correspondence for Digital Topology de-
scribes an adjoint situation between the category of (generalized) clo-
sure spaces in the sense of Cech (where only extensivity and preser-
XIV Preface
The plan for a book on Galois connections originated with the partici-
pants of a conference on that subject held at the University of Potsdam
Preface XV
in 2001. The editors hope that this volume, though certainly not com-
prehensive enough to cover all the important themes in this area, will
help to make an easy but beautiful concept more popular. Thus, if
the value of Galois connections as a unifying concept in quite diverse
branches of mathematics, but also its usefulness as a practical tool
both in mathematics and other areas, become more evident by the
contributions in this book, our main intention will have been fulfilled.
***
October 2003
Adjunctions and Galois Connections:
Origins, History and Development
M. Erne
Abstract
Galois connections build the abstract framework not only for classical and
modern Galois theory involving groups, fields and rings, but also for many
other algebraic, topological, order-theoretical, categorical and logical theo-
nes.
We sketch the development of Galois connections, both in their covariant
form (adjunct ions) and in the contravariant form (polarities) through the
last three centuries and illustrate their importance by many examples. The
main steps in the development are:
the theory of polynomial equations (Lagrange, Galois),
the modern Galois theory (Dedekind, Artin),
the origins of lattice theory (Dedekind, Schroder),
the polarities and lattice-theoretical aspects (Birkhoff),
the order-theoretical Galois connections (Ore),
the logical calculus (Boole, Peirce, Schroder),
and the residuation theory (Krull, Ward, Dilworth).
Besides sporadic occurrences of adjunctions and Galois connections in im-
portant mathematical theorems, we discuss diverse contributions to a sys-
tematical theory of adjunction and residuation, and we touch on various
applications to topology, logic, universal algebra and formal concept anal-
ysis.
Mathematics Subject Classification: 01-02, 06A15, 06D15, 12F10.
Key words: Adjoint map, Axiality, Closure operator, Complete lattice, Ga-
lois connection, Polynomial equation, Field, Group, (Partially} Ordered set,
Polarity.
Contents
1 The Idea of Adjunction and Galois Connections
4 Residuation Theory
A Galois Adjunction
A Galois Connection
(Duel Adjunction)
4 M . Erne
Galois connections are the main theme of this book. So, readers not
familiar with that topic might wish to know: where do they come
from, where are they used , and who were the prominent pioneers of the
theory? I hope I will be able to answer at least in part these questions.
Certainly it cannot be the intention of a historical introduction to
cover all relevant instances of Galois connections, and one or the other
expert will miss his own favorite theme. What I have tried to do is to
collect together a series of situations where Galois connections enter
(or may be introduced into) the picture of an interesting classical
theory or problem. A comprehensive historical discussion of the roots
of order and lattice theory can be found in the book by Mehrtens
[92]. For historically oriented treatments of classical Galois theory,
two comprehensive sources are Edwards [39] and Tignol [138].
In the 19th century, the concept of Galois theory was not yet born,
though we shall have occasion to encounter it implicitly in the work of
the prominent pioneers of Galois theory: Lagrange, Abel , Galois and
Dedekind.
In the 20th century, milestones on the way to the modern view of Ga-
lois connections are Birkhoff's "polarities", Ore's "Galois connexions",
and Schmidt's "Galois correspondences of mixed type", nowadays bet-
ter known as "adjunctions" . Particular mention should be made of the
residuation theory initiated by Krull, Dilworth and Ward , continued
by Blyth and Janowitz, and leading to the modern theory of "quan-
tales". We also briefly touch on the practice-oriented interpretation
of relations and polarities as "contexts" in the sense of formal concept
analysis (see R. Wille's contribution "Dyadic Mathematics - Abstrac-
tions from Logical Thought" in this volume). However, reasons of
limited space forbid us to have a closer look at the immense field of
categorical Galois connections and functorial adjunctions.
A number of examples from order theory, universal algebra and topol-
ogy, showing how the tool of adjoint maps may facilitate or clarify con-
siderably mathematical problems, will accompany our journey through
the world of Galois connections. The examples chosen are sometimes
rather elementary, but nevertheless some of them have caused break-
throughs not only in the development of mathematical theories, but
also in their applications.
Adjunctions and Galois Connections 5
P~Q
T
between (quasi-)ordered sets, subject to the defining condition
U=r) P::; Q(q) {::} A(p) ::; q,
which turns out to be equivalent to the requirement that A and 12 be
isotone (i.e. order-preserving) maps satisfying the inequalities
p :S Q(A(p)) and A(g(q)) :Sq.
As usual, we mean by a quasi-ordered set one with a reflexive and
transitive relation, called the order relation. If the relations involved
in an adjunction are partial orders (i.e. antisymmetric), then the left
or lower adjoint A is uniquely determined by its right or upper adjoint
Q, and conversely. Notice that rotating the above little diagram by
180° leads to an adjoint pair (g, A) between the dual posets Qd and
pd_ In the introductory example, A could stand for the addition of
a constant, and Q for the subtraction of the same constant. More
generally, in any (additively written) partially ordered group G with
isotone translations
Ta : X f--+ X +a
the "subtractions"
aa : y f--+ y- a
are both left and right adjoint to Ta , being inverse to Ta· Generally, a
poset with a binary operation * is said to be residuated iff each of the
translations x f--+ x *a and x f--+ a* x has a right adjoint (see Chapter
4).
Notice that one always may take, as a special instance of a partial
order, the equality relation =. In that specific case, an adjoint pair of
maps is just a pair of mutually inverse bijections, and the usual treat-
ment of equations by shifting parts of one side to the other appears
as a special case of the general handling of inequalities.
A similar, perhaps somewhat unexpected type of adjunction arises
when the first quasi-order is an equivalence relation and the second is
the identity relation. For example, the "world of congruences modulo
Adjunctions and Galois Connections 7
a prime number p" is translated into the "world of the Galois field
Fp = 'lljp'll" (consisting of the residue classes modulo p) , by means of
the quotient map
A : 'll---t Fp, n f---t n + p'll .
Any left inverse (! : Fp ---t 7l of A, picking one representative from each
residue class, is both left and right adjoint to A, since
A(n) = q -R n Q(q) mod p.
Thus, all statements, problems and solutions in Gauss' theory of con-
gruences modulo a prime number [61] may be translated into the the-
ory of Galois fields Fp , and vice versa.
An obvious question in the present context is this: which maps be-
tween ordered sets do have a left or a right adjoint? Although the
answer is very simple, it seems not to have been stated explicitly be-
fore the middle of the 20th century (see e.g. Pickert [114], Schmidt
[123]). Calling sets of the form
(p] = {x E p: X~ p}
principal (order) ideals and sets of the form
[p) = {X E p : p ~ X}
principal dual ideals or principal filters, one has the following
Characterization Theorem for Adjoint Maps
(1) A map A : P ---t Q between quasi-ordered sets has a right adjoint
if and only if it is residuated, i.e. inverse images of principal ideals
under A are again principal ideals. If P is a poset, the right adjoint
(! : Q ---t P is then given by
(4) Conversely, any join (meet) preserving map between complete lat-
tices is residuated (residual).
Indeed, if a map A : P---+ Q between complete lattices preserves joins
then
(! : Q ---+ P, q H V{p E P : A(p) ::; q}
is the right adjoint of A; and dually, if(! : Q---+ P preserves meets then
Qe
,\
Combining that result with its dual (exchanging left and right), one
obtains the
Theorem on Perfect Galois Connections
For an adjunction or Galois connection (.X , (2) between quasi-ordered
sets P and Q, the following conditions are equivalent:
(a) A and g aTe mutually inverse bijections.
(b) Ao g and (lOA are injective.
(c) Ao g and go.X are surjective.
(d) A and (2 aTe injective.
(e) A and g are suTjective. (f) There are maps J.L: P----+ N , fl : Q ----+ N
such that flo A and f-LOg aTe scales.
(g) There aTe scales J.L :P----+ N, fl :Q ----+ N with J.L = flo.X, fl = J.LO&J.
If P and Q aTe paTtially ordeTed, (g) may be replaced with
Adjunctions and Galois Connections 13
(h) There are isotone scales p,: P-+ N, jl: Q--+ N with
and jl ::; p,o (].
closure system, and the two systems are isomorphic via restriction
and corestriction of these maps.
Conversely, any adjunction between power sets and, consequently, any
isomorphism 1> between a closure system and a kernel system comes
from a unique relation R between the underlying sets in that manner,
where xRy means that y belongs to the image of the closure of {x}
under 1>.
Polarities and axialities are related via the complement operator c by
the equations
R c
K L
Dn_ _ _ __ _ Dn
n N n
18 M . Erne
.C(Dn } + - - -- --
.C(D~ ...-------R(D~)
These isomorphisms are the starting point in John von Neumann's in-
genious coordinatization theory for complete, complemented modular
lattices [145] .
But Wille also views formal concept analysis as an important tool for
the purpose of "restructuring lattice theory". In the introduction to
his inspiring article [153], he writes:
Sk = Bk,n = L:l~}l < ... <jk~n fl~=l Xjm = L:Y~X, #Y=k f]y EY Y'
are, up to signs, the coefficients of the polynomial
(*) TI7=(x- Xj ) =
1 L: ~=o Bk,n(-x)n-k,
a result probably due to Albert Girard (1629) in its full generality
(see [64]), while specific cases for small degrees were already known to
Frangois Viete (Francesco Vieta; see [143]).
Historians attribute the first major results on symmetric polynomials
to Isaac Newton (see, for example, [39]). About 1666, Newton listed in
his papers a whole sequence of formulas relating symmetric functions
of the roots of a cubic polynomial with its coefficients. In these notes,
one also finds the case n = 8 of the famous formula
L:f=l(-1 )j aj,n Bk- j,n + ksk ,n = 0
connecting t he power sums
aj,n L...-i=l x.;,J.
= ""n
with the elementary symmetric functions Sk,n· This formula occurs, in
a slightly different form and without proof, in Newton's Arithmetica
Universalis from 1707. It enables one to compute recursively t he
power sums from the elementary symmetric functions, and vice versa,
by the earlier mentioned process of shifting parts of the equation from
one side to the other. At least for n :::; 4, t he formula was already
24 M. Erne
~~/>
wn U { -oo}
For the proof, observe first that (2) for Rn = Rs[Xn] together with
(4) gives
Rs[Xn-1] [xn] = Rs[Xn] [xn]·
The general formula is then obtained by induction.
Finally, substituting for the indeterminates t he (pairwise distinct)
roots of a polynomial, one arrives at the useful
The last two formulas say that any symmetric polynomial (or rational)
expression in the roots of a given polynomial must already belong to
the ground ring (or field , respectively) , and that a polynomial (or
rational function) that is symmetric in all but one root is actually
a polynomial (or rational function) in that root . This is the form
in which Galois and his predecessor Lagrange used the Fundamental
Theorem on Symmetric Functions.
These are the essential tools not only in Lagrange's own considera-
tions on the solvability of polynomial equations, but also in the later
expansion of the theory by Abel, Galois and Dedekind.
30 M. Erne
and calls two rational functions similar if they are equivalent with re-
spect to that quasi-order, meaning that they have the same stabilizer.
One of the similarity classes is that of all symmetric functions.
Another useful ingredient in Lagrange's theory of polynomial equa-
tions is what nowadays is termed
Lagrange's Subgroup Theorem
The order (size) of any subgroup of a finite group G divides the order
of G.
But what Lagrange really stated in Articles 97-99 of his memoir [86]
is, rephrased in modern terms, the following more concrete
Theorem on Minimum Polynomials for Rational Functions
For f E K(X), the minimum polynomial (the least monic polynomial
with root f ) over K (S) is given by
mj(X) = ngEfSm (x- g)
Adjunctions and Galois Connections 31
Lagrange did not carry through a general proof but considered a few
particular cases, among them two-, three- and four-element subgroups
of S(X) and the case I(!) = S(X) , which amounts to the Fundamen-
tal Theorem on Symmetric Functions. Conversely, that theorem is the
base for a rigorous proof of the general statement. How the general
theorem extends to algebraic elements instead of rational functions,
and how it provides a perfect adjunction between subgroups and min-
imum polynomials will be discussed in Sections 2.3 and 2.4, dealing
with the later progrees made by Galois and Dedekind.
The essence of Article 104 in Lagrange's memoir [86] is the following
remarkable statement (in English translation):
If t and y are any two [rational} functions ... fin the roots
of a polynomial equation} and if these functions are such
that every permutation of the roots which changes y also
changes t, one can, generally speaking, express y rationally
in terms oft and ... [the coefficients of the equation].
Proof. The equivalence (a) ¢::? (b) and the implications (a)::::} (c)::::} (d)
=}(e) are straightforward: if G is cyclic of order n, say G = G(h),
34 M . Erne
then for each d E D(n), the unique subgroup of G having order dis
G(hnfd).
(e):::}(a). Ford= o(h) , we have G(h)r:;_pc(d), and# pc(d)s_d forces
pc(d)=G(h). Now, put ca(d) = #{hEG: o(h)=d}. From (a){:} (b)
ford instead of n we infer that pc(d) =G(h) ::::::= 'lld ::::::= Zn(n/d). Thus
ca(d) = c12 a(d)(d) = Czn(n/d)(d) s_ Czn (d) ,
and so there is an injection i from G into 'lln with o(h) = o(i(h)).
Since both groups have the same order, i must be onto, and as 'lln
does have an element of order n , so does G . D
The implication (e):::} (a) applies to any finite subgroup G of the mul-
tiplicative group of a field K , because the polynomial xn - 1 has at
most n roots in K. This gives a short proof of the famous
Theorem on Multiplicative Subgroups of Fields
All finite subgroups of the multiplicative group of a field K are cyclic.
In particular, if K is finite then K \ { 0} is a cyclic group under mul-
tiplication.
Perhaps the most famous and controversial paper in the history of alge-
bra is Galois' Memoire sur les conditions de resolubilites des equations
par radicaux, dated January 1831 but not published until1846 by Liou-
ville in the Journal de Mathematiques (see [56], or [57] for a later com-
mented edition, or Edwards [39] for an English translation). Hundreds
of elaborations, supplements, comments, refinements, and historical
remarks have been written by later authors about that memoir (see,
Adjunctions and Galois Connections 35
From the fact that j), inverts the divisibility relation (by the degree
formula for fields) and (} is anti tone, it follows that J.L = j), o A is an
isotone scale. Thus, the degree of a strong divisor of a polynomial h
in M (a, K) is not only smaller than but a divisor of the degree of h
(cf. Lagrange's Theorem on Minimum Polynomials!)
An immediate consequence of the above theorem is the "only if" part
in the
Theorem on Primitive Elements
A field extension E : K is simple and algebraic (i .e. E = K (a) for
an algebraic element a over K) if and only if the interval :F(E : K)
is finite. For characteristic 0, these two conditions are equivalent to
finiteness of [E: K] .
For the "if" part (cf. [90, 98]), one first observes that the degree
[E : K] must be finite (otherwise, one would obtain an infinite chain
of intermediate fields). Then, one distinguishes the following cases:
Adjunctions and Galois Connections 41
ductive accuracy put him far ahead of most , if not all of his contem-
poraries. Indeed, if some antiquated idioms and long-winded verbal
formulations in the text would be replaced by modern terms and for-
malisms, an almost up-to-date exposition of group and field theory
and other parts of algebra would arise. Unlike Lagrange, Dedekind
always endeavored to giving concise and elegant proofs, and on the
other hand, unlike Galois, he did not omit important arguments or
constructions. The reader of the present survey will already have
remarked that when one tries to make certain statements of those
forerunners precise, one has to refer to Dedekind's work again and
again.
In the preparatory Chapter I on groups, Dedekind deals not only
with permutations, but also with (finite) abstract groups, normal sub-
groups, and even with factor groups. Following Galois, he speaks of
substitutions rather than permutations and defines their product ac-
cording to the (rather modern) convention that the substitution ()()'
first applies () and then ()'. Then he proves the associative law and the
cancellation laws and remarks that these two "Fundamental Laws"
are the base for all further conclusions, so that they may be used for
an abstract definition of finite groups, occurring also in many other
mathematical contexts. (Dedekind is well avvare of the fact that the
finiteness hypothesis is essential for the desired conclusions.)
As a first highlight, he derives Lagrange's Subgroup Theorem and
some of its prominent consequences from the partition
G = H() + HO' + HO" + ...
of a group G into cosets of a subgroup H , mentioned already in Ga-
lois' letter to his friend Auguste Chevalier [57). Since all cosets have
the same cardinality asH, their number (the index of the subgroup)
multiplied by the order of H must give the order of the entire group
G. But Dedekind goes further , analyzes decompositions into two-sided
cosets () H ()' and shows, for example, that the intersection of all conju-
gates e- 1 H () is a normal subgroup ( "eigentlicher Divisor"). Perhaps
his most modern achievement in the area of group theory is the ob-
servation that the cosets of a normal subgroup again form a group
under the "complex product" - a conclusion that requires a degree of
abstraction entirely alien to other mathematicians of his time.
In Chapter II, Dedekind develops in a concise and rigorous way the
Adjunctions and Galois Connections 43
e(f)(xl, ... , Xm) = JB(xl , ... , Xm) = f(B( x!), ... , e(xm)) for() E S(X) .
are pairwise distinct (because t (}i = t (}j implies G (}i = G (}j , hence
i = j).
On account of the inclusion I(t) ~ I(y) , the elements Yj = (}j(y) =
y(}j E K(X) satisfy the implication 8(ti) = lj :::;. 8(yi) = Yj for each
() E S(X). Indeed,
t()i()=t()j {::} ()i(J(Jj- 1 E I(t) :::;. ()i()()j- 1 E I(y) {::} y()i() = y()j·
Now, the interpolation polynomial q E K(X)[x] with q(tj) = Yj has
the required property q(t) = q(t 1 ) = y 1 = y. From the construction
it is rather plausible that q is symmetric, but an exact proof requires
some care. First, one observes that p(x) = f1~ 1 (x - ti) is symmetric,
because application of any () E S(X) merely permutes the elements ti
(cf. Lagrange's Theorem on Minimum Polynomials). Hence, ()(p) = p
and ()(p') = p'. As ()(ti) = lj implies ()(yi) = yj , one obtains 8(q)(x) =
""'m O(w)O(p)(x) _
L.Jj = l (x-O(f:i))p'(O(fj)) -
( )
q X .
0
DEDEKIND LAGRANGE
"finite". And even bolder was his decision to declare finiteness of a set
S by the postulate that there be no injective self-map from S onto a
proper subset:
and so on. There exist some hints in the literature that in later years,
Dedekind himself was not satisfied with that sort of argumentation.
An interesting question in that context is this: can finiteness of a set
S also be defined equivalently by the postulate that every surjective
self-map of S be injective?
That the answer is in the affirmative is well-known, but probably not
the following simple proof using a suitable adjunction. It requires,
however, the hypothesis that the power set PS of a finite set is still
finite (which is easily verified by induction if the second definition
of finiteness is accepted). The argument is then as follows . A map
52 M. Erne
his priority in some of the relevant discoveries; but he also makes clear
that his own emphasis is on the applications to ideal and number the-
ory rather than logic and set theory ( "Systemlehre "), and that his
method provides considerable simplification of Schroder's results and
proofs. Indeed, Dedekind's definitions and deductions are of striking
elegance and precision, though he rarely used order-theoretical argu-
ments and completely avoided representations by diagrams (perhaps
a "forbidden tool" at that time).
We adapt Dedekind's terminology to the modern common use of lattice-
theoretical symbols and write V instead of+ for the join and 1\ instead
of - for the meet. Dedekind's "Fundamental Laws" are (1) the two
commutative laws, (2) the two associative laws, and (3) the absorption
laws
(3') a V (a 1\ b) = a and (3") a 1\ (a V b) = a.
Thus, Dedekind's "Dualgruppen" are just what later have been bap-
tized "lattices" by Birkhoff (Ore called them "structures"). At the
end of the 19th century, the later meaning of "groups" was not yet
standard, and some mathematicians used that term for every (or at
least every finite) semigroup. At that time, the name "Dualgruppen"
was chosen quite reasonably, pointing to the two commutative semi-
group structures and their duality (in the sense that every true lattice
identity entails its dual, obtained by exchanging the two fundamental
operations). Unlike many other authors, Dedekind does not include
(as stated by Birkhoff) the idempotency laws
(4') a V a = a and (4") a 1\ a = a
in the list of axioms, but he derives them as a first step from the
absorption laws in the shortest possible way. Then he emphasizes
that the distributive laws
(5') (a 1\ b) V (a 1\ c) =a 1\ (b V c)
(5") (a V b) 1\ (a V c) = a V (b 1\ c)
(characterizing his "Dualgruppen vom I dealtypus ") imply each other
and the modular laws (characterizing his aDualgruppen vom Modulty-
pus")
(6') (a 1\ b) V (a 1\ c) = a 1\ (b V (a 1\ c))
(6") (a V b) 1\ (a V c)= a V (b 1\ (a V c)).
54 M. Erne
a c
Adjunctions and Galois Connections 55
For finite modular lattices, Dedekind concludes that all maximal chains
have the same length, and that the degree ( "Stufe ") or height func-
tion a, associating with any element a the length of a maximal chain
between the least element and a, satisfies the identity
a( a)+ a(b) =a( a A b)+ a( a V b).
Of course, if a and bare related and a( a) = a(b) then a= b, so that a
is in fact a scale in the sense of Section 1.3. Conversely, the existence
of a function with these two properties forces modularity (cf. Birkhoff
[3] and von Neumann [145]). Indeed, in a pentagon with atoms a, b
and a coatom c above a,
a( a)+ a( b) = a(a A b)+ a( a V b) = a(cA b)+ a(c V b) =a(c)+ a( b),
hence a(a) = a(c), while a < c.
A further adjunction, not contained explicitly in Dedekind's work but
closely related to the above one, concerns
Distributivity and Product Representation of Lattices
For any two elements a, b of a bounded lattice L, the maps
A: (0, a] X (0, b]---+ L, (u, v) r---t u Vv and Q: L ---+[0, a] X (0, b], X r---t
(aAx,bAx)
form an adjoint pair. Furthermore, (-X, Q) is a perfect adjunction iff
(a, b) is a bi-modular, complementary and distributive pair, i.e.
aMbMa, aAb=O and x=(aAx)v(bAx) forall xEL.
Every direct product representation L c:= £ 1 x L 2 is, up to isomorphism,
of the above form. In particular, any complementary distributive pair
of elements in a modular lattice gives rise to a direct product repre-
sentation, and conversely.
This result is of importance, for example, in the famous decomposition
and coordinatization theory for complemented modular lattices due to
Garrett Birkhoff and John von Neumann (see [3] and [145] for details) .
Adjunctions and Galois Connections 57
G. T. Kneebone
Ernst Schroder probably was not only the inventor of the first semi-
formal system of lattice theory (perhaps even before Dedekind), but
also the first mathematician to investigate the interplay between logic
and (a restricted form of) universal algebra, involving certain Galois
connections. Although he did not use that terminology nor the precise
mathematical definition of such connections, they occur implicitly in
at least three problem areas discussed extensively by Schroder in his
monographs, articles and lectures [127] - [131]:
(1) The role of the distributive law and its (non-)provability in his
''logical calculus", the first axiomatic approach to lattice theory.
(2) The foundation of (parts of) universal algebra and its links to
lattice theory, exemplified by the equational theory of quasi-
groups.
square
D
rectrglf/ ~bus
trapezoid [ ~llelogt.m I kite
r\,"'~jJ
t>
quadrangle
However, Voigt and Schroder did not consider that whole lattice, but
argued that the symmetry group of the square, which is the concep-
tual synthesis of the rectangle and the rhombus, contains not only the
axial symmetries of these two "constituents" , but further symmetries
(obtained by rotation). Hence, the symmetry groups of the square, the
rectangle, the rhombus and the parallelogram together with the group
of rotations form a non-distributive (but modular) lattice. This "di-
amond" lattice may be regarded as a sublattice of the closure system
of all subgroups of the dihedral group D 4 of order 4 x 2 = 8 (which are
represented by the incidence-preserving permutations of the vertices of
a square). Notice that the cyclic group generated by the permutation
(1234) cannot be represented as a symmetry group of quadrangles,
because a quadrangle fixed by that permutation must alredy be a
square and has therefore the full symmetry group D 4 . But the whole
subgroup lattice contains a lot of further 5-element non-distributive
sublattices, among them also non-modular ones.
Adjunctions and Galois Connections 61
The other example is due to Korselt [79] . The elements are the points,
lines and planes of 3-dimensional euclidean space, together with the
empty set and the whole space - in other words, the affine subspaces of
IR3 . Since these objects are closed under arbitrary intersections, they
form a complete lattice, ordered by containment. This closure system
consists of all Galois-closed sets with respect to the incidence relation
between points and planes. Of course, the join of two affine subspaces
is the least affine subspace containing both, and this is almost never
their union. A plane, two parallel lines contained in it, a point on
one of the lines, and the empty space form a pentagon sublattice, so
that the whole lattice cannot even be modular (though being upper
semimodular). Later, Korselt modified his example to a projective
geometry [80, 81]. Thus, he made a first step towards the lattice-
theoretical development of (projective) geometry.
Let us conclude this section with a quotation (in free English trans-
lation) from Schroder's "Operationskreis". It concerns the "concept
of concept", fundamental for the philosophical foundation of formal
concept analysis (see Section 1.5):
Since the passage from extents to intents turns the whole concept
lattice "up-side down", this approach to lattice theory makes the du-
ality principle particularly evident. And it is the merit of Schroder
to have pointed out that duality, which was missing in Boole's earlier
development (Section 4.1).
(<I>, '11) associated with the above zero relation l_ send any subset Y
of the space S to the ideal <I>(Y) = Y1_ of all continuous functions
vanishing on Y, and in the opposite direction to each set F of functions
in C(S) its zero set
'li(F) = p.l = {z E S: f( z ) = 0 for all f E F}.
By continuity of the maps, each zero set is closed; but when are all
closed subsets of the space S Galois closed, i.e. zero sets? Necessary
and sufficient for that coincidence is that for any closed set Y and any
point z outside Y, there be a continuous real function vanishing on Y
but not at z. In other words, the space must be completely regular.
Thus, the aspect of Galois connections makes it evident why com-
pletely regular spaces play a central role in the theory of continuous
real functions.
Algebraic versions are obtained by considering endomorphism rings or
polynomial rings instead of rings of continuous functions . A rather ele-
mentary but useful tool of linear and geometric algebra is the following
result, obtained from the Dual Isomorphism Theorem for Submodules
(see Section 1.4) by passing from endomorphism rings to matrix rings
via the selection of bases:
Galois Connection Between Ideals and Subspaces
Let A denote the endomorphism ring of a finitely generated vector
space B. The polarity associated with the vanishing relation between A
and B induces a dual isomorphism between the lattice of all (principal)
left ideals of A and the lattice of all subspaces of B.
Now, let us turn to the central theme of this section and consider an
algebraic closure C of a field K. For the ring K[x] of polynomials
in one variable over K, the situation is easy to describe. For each
subset Y of C, the polynomials having all elements of Y as roots form
a (principal) ideal. Hence, there is a unique monic fy E K[x] dividing
precisely those polynomials which vanish on Y. If Y is finite then fy
is the product of the distinct minimum polynomials of elements in Y;
otherwise, fy is the zero polynomial. Denoting by Z 1 the zero set of
any f E K[x], we have the equivalences
fy divides f {::} f(y) = 0 for all y E Y {::} Y ~ ZJ ,
showing that the maps
64 M. Erne
(a) For each n, the Galois connection associated with the zero rela-
tion between Rn and eninduces a dual isomorphism between the
closure system of K -varieties in en
and that of radical ideals of
Rn .
(b) For each n and F ~ Rn, the zero set V(F) is nonempty if (and
only if) F generates a proper ideal.
(c) For each n , the Galois closure of any ideal I of Rn is its radical
Vi.
(d) For each n and all ideals I , J ~ Rn, V(I) ~ V(J) implies VJ ~
Vi.
(e) For each n and F, G ~ Rn
with V(F) ~ V(G) there is an r such
that each product of r factors in G belongs to the ideal generated
by F.
Proof. (a) :::} (b). Let I= (F) denote the ideal generated by F . If
V(F) = V(I) = V( Vi) = 0 then by the dual isomorphism, Vi= Rn ,
i.e. 1 E I = fln .
(b) :::} (c). Let I be any ideal of Rn. If fm E I then clearly f van-
ishes on V(I), which means that f belongs to the Galo~s closure of I.
Conversely, if the latter is the case, consider the ideal I generated by
I[x] U {1 - xf} in the polynomial ring R = Rn[x]. If 1 rf. i then by
(b) , there would exist a (y , z) E en X e ~ en-t-1 with g(y , z) = 0 for all
g E i , in particular g(y) = 0 for all g E I and 1- z f (y) = 0, contradict-
ing the hypothesis that f belongs to the Galois closure of I (and there-
fore f(y) = 0) . Hence, 1 E i, say 1 = g+ (1- xf)h for some g E I[x]
and h E Rn[x]. Iff is not the zero polynomial, it is invertible in the
quotient field of fln. Substituting 1/ f for x, one obtains 1 = g(1/ f) ,
and for the degree m of g, it follows that fm E I. (This idea is due to
Rabinovich [117]) .
(c):::} (e). Since V( G) = V( (G)) and (G) is finitely generated by
Hilbert 's Basis Theorem (see [72], [90] or [142]), one may assume that
G is finite, say #G = k. Now, V(F) ~ V(G) implies G ~ y'(F) by (c).
Hence, by finiteness of G, there is an exponent s such that g 8 E (F)
for all g E G, and for r = sk it follows that g1 •.• gr E (F) whenever
g1 , .. . , 9r E G (because one factor must occur at least s times).
The implications (e):::} (d) and (d):::} (a) are straightforward. D
66 M. Erne
The radical ideals are precisely the intersections of prime ideals, and
the latter correspond to the (union-)irreducible K -varieties via the
dual isomorphism induced by the zero relation.
That the situation described above frequently occurs in practice (for
example, when Cis the field of complex numbers) is assured by
Hilbert's Nullstellensatz (Zero Set Theorem)
The equivalent conditions in the previous theorem are fulfilled if C is
algebraically closed.
Various rather short proofs of that theorem are to be found in the
modern standard literature on algebra and algebraic geometry (see,
for example, [84] or [90]) . Historically, it has to be noted that in his
famous 1893 paper "Uber die vollen Invariantensysteme" [73], Hilbert
formulated the Nullstellensatz in a slighly different form, namely as
condition (e) (which often is lost in modern presentations) for ho-
mogeneous polynomials and the complex number field C. Actually,
Hilbert's primary purpose was the application to the theory of invari-
ants. Some of his concepts come close to the idea of Galois closure,
when he considers for a given set of (homogeneous) polynomials the
collection of all polynomials vanishing on the common zero set of the
given ones. However, the notion of Galois connections does not arise
explicitly in that context.
For finite fields, the situation becomes particularly simple.
Theorem on the Polynomial Completeness of Finite Fields
For a field K, the following conditions are equivalent:
(a) K is finite (a Galois field).
(b) For any a E Kn ther·e is a polynomial fa E K[x 1 , ... , Xn ] with
fa(a) = 1 and fa(b) = 0 forb E Kn \{a}.
(c) Any function g : Kn --+ K is a polynomial function.
(d) Each subset of Kn is the zero set of a polynomial.
Hence, for any .finite field K , the Galois connection associated with the
zero r·elation between K[x 1 , .. . , Xn ] and Kn is right perfect. In other
words, there is a dual isomoTphism between the poweT set of Kn and
the closure system of all radical ideals of K[x 1 , . .. , xn], under which
the singletons correspond to the prime ideals (by associating with any
point a E Kn the ideal of all polynomials vanishing at a).
Adjunctions and Galois Connections 67
and they are in fact the Galois-closed subsets of S(R) with respect to
the membership relation E between elements and prime ideals of R .
On the other hand, the Galois-closed subsets of Rare the intersections
of prime ideals, and these are known to be precisely the radical ideals.
(For the latter conclusion, one needs Krull's Separation Lemma, see
Section 4.2). Thus, we have the
Isomorphism Theorem for Radical Ideals
The polarity associated with the membership relation between elements
and prime ideals of a commutative ring R gives rise to an isomorphism
between the closure system of radical ideals and the hull-kernel topology
on the spectrum. Under that isomorphism, the prime ideals correspond
to the irreducible closed sets.
The similarity between the last theorem and that on algebraic varieties
is not casual, but there is an explicit link via continuous functions . For
any element z of en' the polynomials in Rn = K[xl , ..., Xn] vanishing
at z form a prime ideal Pz, and the function z H Pz is continuous
as a map from en with the Zariski topology to S(Rn) with the hull-
kernel topology. Indeed, in modern terminology, the latter space is the
sobrification or sober reflection of the former. Here, a space is sober
iff each irreducible closed set is the closure of a unique point (see e.g.
Johnstone [78]). Any topology is lattice-isomorphic to that of the
sobrification. In the present situation, both topologies are isomorphic
to the system of all radical ideals in Rn.
68 M . Erne
only does every relation between two sets (which may be identical) give
rise to a Galois connection between the corresponding power sets, but
also conversely, every Galois connection between power sets arises in
that fashion from a unique relation: indeed, if <I> : P(A) --t P(B) and
W : P(B) --t P(A) are two maps satisfying
X ~ w(Y) {:} Y ~ <I>(X) (X ~ A, Y ~ B)
then there is a unique relation R ~ Ax B with <I> = R-+ and W = +--R,
VlZ.
cuts; Birkhoff also speaks of "closed ideals ", reminding of the fact
that they are closed sets with respect to the involved Galois connec-
tion . By definition , they are just the intersections of principal ideals.
It is evident (and follows from the general remarks on polarities) that
the lower cuts form a closure system and therefore a complete lattice,
dually isomorphic to the closure system of upper cuts (intersections of
principal filters) . As Birkhoff points out, a poset is complete if and
only if every cut is already a principal ideal, while in general, any
poset P is embedded in the closure system N P of all cuts by sending
each element to the principal ideal generated by that element:
TJ : p -+ N p' X H -!-X = {p E p : p ::; X} .
This completion by cuts, alias Dedekind-MacNeille completion or nor-
mal completion, may be characterized abstractly by various universal
properties (see [2, 10, 15, 40, 10, 45, 46, 124] for details) .
Characterizations of the Completion by Cuts
For an embedding c of a poset P in a complete lattice C , the following
conditions are equivalent:
(a) There is an isomorphism t : NP-+ C with c =to 'rf ·
(d) For every order embedding c1 of Pin a complete lattice C' , there
is an order embedding t : C -+ C' with c' = t o c.
(f) For every cut continuous map c' from P into a complete lattice
C' , there is a unique join-preserving map t : C -+ C' with c 1 =
t 0 c.
(g) For every cut stable map c' from P into a complete lattice C',
there is a unique join- and meet-preserving map t : C -+ C' with
c' = t 0 c.
Any such map is lower and upper cut continuous, but not conversely.
Precisely speaking, Dedekind's completion of the rationals gives a con-
ditionally complete lattice (in which all nonempty bounded subsets
have join and meet); in the general setting of posets, that construc-
tion may be imitated by taking the nonempty proper cuts only. Here,
Birkhoff proves the following general result:
Conditional Completion of Bidirected Posets
If P is an up- and down-directed poset (all finite subsets have upper
and lower bounds) then the nonempty proper cuts form "the'' condi-
tional completion, that is, a conditionally complete lattice in which P
is join- and meet-densely embedded (which forces uniqueness of the
conditional completion up to isomorphism).
In order to understand that sentence, one must know that Ore means
by a topological space a set S equipped with a closure operator ( "clo-
sure relation" ) making the empty set closed, while finite unions of
closed sets need not be closed for him. Of course, such a "topological
representation" of a complet e lattice P is easily achieved, by endowing
the underlying set Po= P\ {0} (where 0 = 1\ P = V 0 is the least el-
ement) with the closure operator X H ] 0, V X], so t hat the "deleted"
principal ideals ] 0, p] = {x E P : 0 < x ::; p} form a closure system
isomorphic toP, and the empty set is closed. Now, Ore claims that
Adjunctions and Galois Connections 83
TJp
R+--
p (P)~===R==-->===:::::; p (Q)
Adjunctions and Galois Connections 85
type}}).
Clearly, the isomorphism sends a to ii, and its inverse sends any open
set U to 1\ (L \ U). If L happens to be a closure system on a set A (as
in the case of the filter lattice F(X)), then this perfect adjunction is
induced by the axiality corresponding to the relation
R = {(x, P) E Ax Sp(L): x tj_ P}
(cf. the analogous construction of spectral topologies in Section 2.8).
4 Residuation Theory
example "men and woman"), but also by the exclusive "or" (applied
to adjectives, as in 11beings that are men or women"). At first glance,
this simultaneous use of the words "and, or" seems to conflict with
our interpretation of the meet (intersection) described by the particle
11
and", while join (union) is described by the particle 11or". The in-
tuition that 11and" is in some sense dual to "or" was made precise by
Schroder, who distinguished between extent and intent of a concept
(see Sections 1.5 and 2.6); here, the conjunction of attributes (form-
ing the intent) corresponds to the intersection of the classes of objects
having these attributes (the extent). As indicated in Section 1.5, this
is a central aspect of formal concept analysis [59].
For the basic two operations, Boole explicitly postulates the law of
commutativity, while the law of associativity is not mentioned at all
(perhaps because juxtaposition and conjunction of more than two
members usually are written or phrased without parentheses) . As
a fundamental law of logic, Boole emphasizes the law of idempotency
xx = x, written as x 2 = x (and referred to as the "Law of Duality" by
Boole himself ; however, that terminology is not very suggestive and
was criticized by Schroder [129]). Thus, the Boolean multiplication
(juxtaposition) obeys the identities valid in what nowadays is called
a semilattice. For BooZe's addition, however, the dual law x + x = x
plays no role, in view of his hypothesis that the classes occurring in an
"interpretable" sum have to be disjoint. The next fundamental axiom
is the distributive law
z(x + y) = zx + zy,
which Boole motivates by examples. Then he introduces a third (par-
tial) operation he denotes by the subtraction symbol "-" . From the
point of adjunctions, this operation is of particular interest. Boole's
own comment:
an equation from one side to the other! One should remark that the
equivalence
( ~) X - Z = y {::} X = y+Z
holds only under the assumption that "z is subsumed under x ", which
may be described by any of the equivalent identities
z = zx, z - zx = 0, z(l - x) = 0,
using Boole's symbols 0 for "Nothing" and 1 for "the Universe", sub-
ject to the rules
Ox = 0 and lx = x.
But Boole prefers to choose an "indetermined class variable" v and
expresses the above situation by the equation
z = vx.
Dealing with equalities exclusively, Boole does not mention the so
defined order of subsumption, all the less the symbolic notation z :S
x. Nevertheless, the equivalence (~) may be regarded as a special
instance of an adjunction, viz. for the equality relation as order. A bit
problematic is the domain of definition for the operations involved in
that adjunction. If one wishes to avoid partial operations, one has to
consider, for fixed z, the mutually inverse isomorphisms
X H X - Z and y H y+Z
between the intervals
[z, l] = {x: z :S x} and [0,1 - z] = {y: y :S 1 - z}.
Of course, this is not only a (perfect) adjunction with respect to the
identity relation = , but also with respect to the order relation :S.
An alternate (but not Boole's) point of view is to regard y + z as the
join and x - z as the relative complement x z' in a Boolean algebra B.
Then the equivalence
x-z:Sy {::} x:Sy+z
shows that we have an adjoint pair of maps x H x- z and y H y + z,
defined on the whole of B, whose surjective restrictions yield the above
mutually inverse isomorphisms. A third (and perhaps the most con-
vincing) alternative would be to take for + the addition and for - the
subtraction in a Boolean ring, in which case addition and subtraction
Adjunctions and Galois Connections 99
ing for exact proofs and conclusions. In the preface to his early 1877
treatise "Der Operationskreis des Logikkalkuls" [129] he writes (free
English translation):
w =A+ OB + §C + ~D ,
that solution may be resolved into the following equations,
vzz.
Adjunctions and Galois Connections 101
w = A + vC, D = 0.
from the distribution law and the rules for the universal bound 1:
a(a +b) = aa + ab =a+ ab = al + ab = a(l +b) = al = a;
and now he concludes that the dual distribution law must hold, too:
(a + b) (a + e) = aa + ab + ae + be = a + ae + be = a + be.
After having proved and applied de Morgan's laws
(a V b)' = a' 1\ b' and (a 1\ b)' = a' V b'
he states in conclusion that (in contrast to Boole's original system)
the whole calculus obeys the rule of dualization: every true formula
remains valid when sum and product are exchanged at all occurrences
in the formula.
For the historical origins of residuation theory, the fourth section of
t he "Operationskreis" is of major relevance. Schroder points out that
in the logical calculus with distribution and complements, the dual
equations
x +b= a and xb = a
if solvable, do possess certain extremal solut ions. Namely, x + b = a
is solvable if and only if a'b = 0, in which case the largest solut ion
is x = a, while the smallest solution is the "minimal difference" x =
a - b = ab'. Dually, the equation xb = a is solvable iff ab' = 0, and
then the smallest solution is x = a, while the largest solution is here
the "maximal quotient" x = ~ =a + b'.
Schroder derives a whole series of rules for these two "principal values
of subtraction and division"; but he does not proceed explicitly to
the final idea of residuation theory, namely to search for t he extremal
solutions of the inequalities x + b 2: a (which could be written as an
equation, e.g. (x + b)a = a) and xb S a (equivalently, x b +a = a)
which always exist and are given by x = ab', respectively, x = a + b'.
In his later work, Schroder singled out the absorption laws as "partic-
ularly characteristic for the logical calculus" and included them into
the list of axioms but dropped the distribution and complement laws
from the axiomatic framework of his "logical calculus". He was familiar
with the early (and fragmentary) set- and lattice-theoretical ideas of
the Grassmann brothers [66, 67], who already used t he symbols U and
n and emphasized their dual behavior, in particular the equivalence
Adjunctions and Galois Connections 103
of the equations
an b =a and aU b = b,
both expressing that a be "included" in or "subsumed" under b. In
his extensive Lectures on the Algebra of Logic [131], Schroder often
returned to that su bsum ption relation as a basic concept for logic (or,
interpreted as set inclusion, for the theory of classes). Curiously, as
a forerunner of the inclusion symbol ~ ' he chose the Euro symbol =€
for subsumption. Comparing the two pioneers of lattice theory with
each other, one might say that Dedekind preferred the operational ap-
proach, while Schroder later emphasized the relational (hence order-
theoretical) tools. His basic principles for the subsumption are reflex-
ivity and transitivity; instead of demanding the law of antisymmetry,
he defines equality by the equivalence
a = b : {::} a =€ b and b =€ a
(later a common use in set theory). The existence of a least element 0
and a greatest element 1 are postulated verbally (rather than by the
formulas 0 =€ a and a =€ 1) . The definitions of (binary) join and meet
are again divided into a formal part:
if c =€ a and c =€ b then c =€ ab ,
if a =€ c and b =€ c then a + b =€ c,
and a verbal part, describing ab and a + b in the usual naive set-
theoretical sense of intersection and union by means of the word "Ge-
biet" (domain, field, area) . The "logical calculus" defined in that
semi-axiomatic way apparently is what later would become the order-
theoretical definition of (bounded) lattices. In order to obtain the full
"identical calculus" (of Boolean algebra), Schroder adds a weak form
of the "distribution law ":
if be = 0 then a (b + c) =€ ab + ac
and the defining condition for complements
aa' =€ 0 and 1 =€ a+ a'
together with the postulate that for each a at least one such a' exists,
"obtainable as remainder by omitting a from 1".
Schroder knew and appreciated Peirce's attempts to formalize logi-
cal thinking [110]. A purified list of order-theoretical postulates for
104 M. Erne
Although the name "lattice-ordered groups" or "l-groups " was not used
by Dedekind , he invented that important modern concept and discov-
ered its basic properties. Of t he many interest ing aspects of the later
extensively elaborated theory of l-groups (see e.g. Birkhoff [3] for a
small excerpt), we shall touch on t hose only which occur in Dedekind's
106 M . Erne
work and provide the origin of the theory of residuated lattices. Al-
ready in the first (1897) paper on his "Dualgruppen" (see [30] and
Section 2.4), Dedekind defines abelian groups exactly the same way
we do, but writes them always multiplicatively. Moreover, he consid-
ers such groups endowed with an extra semilattice operation, denoted
by + , and postulates the distributive law
a (b + c) = ab + ac.
In order to give a succinct version of Dedekind's basic theorem on
such structures, let us (historically) anticipate the notion of a partially
ordered group, that is, a group G with a partial order such that left
and right translations are order isomorphisms, hence left and right
adjoint to the inverse translations:
ax ~ y {::} x ~ a- 1 y and xa ~ y {::} x ~ ya- 1 .
As in Section 2.5, we write V instead of+ in order to avoid confusion
with other possible additions. Dedekind's crucial observation is that
a 1\ b = ab / (a V b)
defines a second operation such that (G , V, 1\) becomes a lattice ( "Du-
algruppe"). His proof is entirely algebraic, but of course, one may
also invoke the fact that inversion is a dual automorphism. Hence,
x H ax- 1 b is a dual automorphism, too, and consequently a( a V b) - 1 b
must be the meet of aa- 1 b = b and ab- 1 b = a. Thus, in the non-
commutative case, the above equation has to be replaced with
a 1\ b =a( a V b) - 1 b
(see Birkhoff [3]). Now , the non-commutative version of Dedekind's
theorem and an extension to infinite joins and meets reads as follows:
Charcterization Theorem for Lattice-Ordered Groups
For any partially ordered group G, the following statements and their
duals are all equivalent:
(a) The join a V e exists for the neutral element e and each a E G.
(b) G is a semilattice with (a V b)c = ac V be.
(c) G is a semilattice such that c= 1\B implies
av c= 1\{av b: b EB}.
(d) G is a distributive lattice (with the underlying order).
Adjunctions and Galois Connections 107
Proof. (a) :::} (b). Being order isomorphisms, the translations pre-
serve joins. Thus, ((ab- 1 ) Ve)b = abb- 1 V eb = aV b exists, and (av
b)c = ac V be.
(b) :::} (c). If c = 1\ B and x ~a V b for all bE B, then c ~ b entails
a V b =a V b V c and c ~(a V c) 1\ b =(a V c)(a V b) - 1 b ~(a V c)x - 1 b,
hence x(a V c)- 1 c ~ b for all bE B. Consequently x(a V c) - 1 c ~ c, and
finally x ~a V c. This proves the equation aV c=f\{aV b: b EB}.
(c) :::} (d) :::} (a) and the self-duality of the statements are clear, be-
cause inversion is a dual automorphism. D
The implication (b) :::} (d) for commutative groups and the follow-
ing aesthetic proof is due to Dedekind. Iterated application of the
lattice identities and the commutative and distributive laws for the
multiplication yields
(a V b V c) ( ab V be V ca) = (a V b) (b V c) ( c V a),
an identity Dedekind uses at some places in his general ideal theory.
Now,
a 1\ (b V c) = a(b V c) = a(ab V be V ca) = __!l;Q_ ac _
aVbVc (avb)(avc) aVb v ave -
(a 1\ b) V (a 1\ c).
In view of the preservation of all existing joins and meets by the unary
lattice operations x H a V x and x H a 1\ x, one might guess that they
could possess adjoints (as the multiplicative translations do). But
that is not the case, by lack of universal bounds for any non-trivial
lattice-ordered group. Again, it was already Dedekind who observed
that such a group cannot possess any elements of finite order (see E.
Noether's comment in the 1931 edition of Dedekind's Collected Works
[31]).
The commutative case is treated by Krull in his 1924 paper [82] , and
the non-commutative case in his 1928 paper [83]. We shall discuss only
a few basic definitions and facts from the first two chapters of the lat-
ter, which extends much of the material contained in the former. The
later chapters, being of minor relevance for the idea of residuation ,
will not be commented on here. Krull 's principal idea is the abstrac-
tion from concrete ring- and ideal-theoretical situations to a structure
whose "individuals" are not the elements of a ring, but the "ideals"
(in a generalized sense) themselves. So he writes in the introduction:
For the general quantalic version (which covers the above and many
other separation lemmas, see [51]), one needs the notion of open m-
filters; these are subsets S of a quantale Q such that
112 M . Erne
a contradiction.
It should be mentioned that the local distributive law for residuated
lattices cannot be extended to infinite subsets A, as a straightforward
inspection of the cofinite topology on an infinite set shows. Although
this is a complete distributive lattice with ascending chain condition in
which every element is a meet of coatoms, it is certainly not Boolean,
and the infinite distributive law a V 1\ X = 1\(a V X) fails.
While even a finite distributive lattice may possess several residu-
ations, Ward and Dilworth showed that a complemented residuated
lattice must already be Boolean, and the multiplication must be the
meet operation. Since their computations are rather complicated, we
add here a short proof for a slightly stronger result , providing one of
dozens of possible axiomatizations for Boolean algebras (cf. Hunting-
ton [76]).
Characterization Theorem for Boolean Algebras
If a join-semilattice S with least element 0 and greatest element i car-
ries a commutative binary operation · and a unary operation ' such
that
a·i =a, a·a' = 0, a V a'= i , and a· (b V c) = (a· b) V (a· c)
then a· b is the binary meet, hence (S, V , ·, 0, i,') is a Boolean algebra.
Indeed, a V a' V b = i implies
a A b::; a A (a' V b) =a· (a' V b) =a· a' V a·b = a·b.
Clearly, every ring ideal is a join of principal ideals, and these are
closed under the formation of powers and even of products (if the ring
is commutative). Thus, the above theorem actually applies to classical
ring theory. Modifying the notion of principal elements, Dilworth later
found still more powerful results (see his own comment and [37]) .
Adjunctions and Galois Connections 121
In the last part, Ward and Dilworth deal with conditions under which
a residuated lattice is distributive. They show that the postulates
(a: b) V (b: a) = i
a: (b 1\ c) = (a : b) V (a: c)
(b V c) : a= (b: a) V (c : a)
are mutually equivalent and entail distributivity. Another sufficient
condition for distributivity is provided by the following
Distributive Law for Principal Elements
In a residuated lattice, the unary meet operations x H a 1\ x preserve
all principal joins: if c = V B is a principal element then a 1\ c =
V(ai\B).
Indeed, if d ~ a 1\ b for all b E B then
d:c = 1\{d:b I bE B} ~ 1\{(al\b) :b I bE B} = 1\{a:b I bE B}
= a:c,
are dually isomorphic bounded lattices. The Galois connection (Lk, Rk)
induces mutually inverse dual isomorphisms between these lattices.
Proof. By definition of Baer semigroups, .Ck and Rk are the ranges of
the Galois connection (Lk, Rk) between .CPT(S) and RPT(S). Clearly,
kS = Sk = Lk(l) = Rk(l) is the least and S = Lk(k) = Rk(k) is the
greatest element of .Ck and of Rk. The only detail that remains to
be shown is that the intersection of two members eS, fS E nk (with
idempotent e, f) is again in Rk· This and the corresponding state-
ment for Lk together with the dual isomorphism between those posets
then give the desired lattice properties. First, note that eS, fS E Rk
imply Rk(ke) = Rk(Lk(eS)) = eS and Rk(k!) = fS. Next, put
h =kef and g = fhk. Idempotency off yields hg = hhk E kS and
g = hkg = fg = gg. Now, if y E gS then y = gy = fhky E fS, hence
key = hhky E kS, and so y E Rk(ke) n fS = eS n fS. Conversely,
y E Rk(ke) n fS implies key E kS andy= fy, hence hy =key E kS
and so y = fy E hkS, i.e. y E fhkS = gS. Thus, we have
gS = eSnfS = Rk(ke)nRk(kJ) and therefore gS = Rk(Lk(gS)) E Rk·
0
a 1\ VB = V {a 1\ b: bE B}.
There exists an immense literature on that topic, of which we only
mention Johnstone's excellent book Stone Spaces [78]. Perhaps some-
what unexpectedly, in the last few decades logic and topology amalga-
mated to a quite powerful synthesis, profiting from both theories (and,
of course, from lattice theory and the theory of adjoint maps). The
theories that arose from that fruitful interplay are pointfree topology
and the more recent formal topology.
Let us conclude our journey through the world of adjunctions and Ga-
lois connections by the remark that meanwhile there exist extremely
powerful categorical extensions of the modest order-theoretical notion
of adjunctions, like categorical Galois connections and adjoint functors
(see, for example, the early paper by Lawvere [87] on adjunctions, the
nice article by Herrlich and Husek [70] on four types of categorical Ga-
lois connections of increasing generality, and the inexhaustible source
Abstract and Concrete Categories by Adamek, Herrlich and Strecker
[3]). Another very modern theory in that context is the theory of
Chu spaces [115], which combines categorical methods with the idea
of multivalued contexts, known from formal concept analysis. For
quite recent material on the role of (classical and categorical) Galois
connections in pointfree topology and its links to classical topology,
we refer to the paper General Stone Duality (52] and to the article The
polarity between approximation and distribution in this volume.
S. Mac Lane in
Categories for the Working Mathematician
130 M. Erne
References
[1] Abel, N.-H.: (Euvres Completes. (L. Sylow and S. Lie, eds.) , Gr0endahl
& S0n, Christiania, 1881.
[2] Abian, A. : On definitions of cuts and completion of partially ordered
sets. Z. Math. Logik Grundl. der Math. 14 (1968), 299-309.
[3] Adamek, J., Herrlich, H. , Strecker, G.: Abstract and Concrete Cate-
gories. John Wiley& Sons, Inc., New York, 1990.
[4] Alexandroff, P.: Diskrete Raume. Mat. Sb. (N.S.) 2 (1937) , 501-518.
[5] Artin, E.: Galoissche Theorie . Teubner, Leipzig. 1959.
[6] Baer, R.: Linear Algebra and Projective Geometry. Academic Press, New
York, 1952.
[7] Baer, R.: On closure operators. Arch. Math. 10 (1959) , 261- 266.
[8] Banaschewski, B.: Prime elements from prime ideals. Order 2 (1985) ,
211- 213.
[9] Banaschewski, B., Erne, M.: On Krull's separation lemma. Order 10
(1993), 253- 260.
[10] Banaschewski, B., Bruns, G.: Categorical characterization of the Mac-
Neille completion. Arch. Math. (Basel) 43 (1967) , 369- 377.
[11] Benado, M.: Nouveaux theoremes de decomposition et d'intercalation a
la normalite a. C. R. Acad. Sci., Paris 228 (1949) , 529-531.
[12] Birkhoff, G.: Combinatorial relations in projective geometries. Ann.
Math. 36 (1935), 743-748.
[13] Birkhoff, G.: Lattice Theory, Amer. Math. Soc. Coll. Publ. 25, Provi-
dence, R. I.; 1st ed. 1940, 2nd ed . 1948, 3d ed. 1973.
[14] Birkhoff, G.: Ordered sets in geometry. In: I. Rival (ed.) , Ordered Sets. ,
Proceedings NATO ASI Ser. C, Math. and Phys., No. 83 (1982), D.
Reidel Publ. Co. , Dordrecht- Boston- London, 1981, 407- 443.
[15] Bishop, A.: A universal mapping characterization of the completion by
cuts. Algebra Universalis 8 (1978) , 349- 353.
[16] Blyth, T., Janowitz, M.: Residuation Theory. Pergamon Press, Oxford,
1972.
[17] Boole, G.: A general method in analysis. Phil. Trans. of the Royal Soc.
London 134 (1844), 225- 282.
[18] Boole, G.: The Mathematical Analysis of Logic. Cambridge, 1847. Repr.
Oxford, 1951.
[19] Boole, G.: An Investigation of The Laws of Thought, Dover Publ., Lon-
don, 1854. Repr. New York, 1958.
[20] Bvelohlavek, R.: Fuzzy Galois connections. Math. Logic Q. 45 (1999) ,
497- 504.
Adjunctions and Galois Connections 131
[21] Bvelohlavek, R.: Fuzzy Galois connections and fuzzy concept lattices:
from binary relations to conceptual structures. Discovering the world
with fuzzy logic, 462-494, Stud. Fuzziness Soft Comput. 57, Physica,
Heidelberg, 2000.
[22] Choquet, G.: Convergences. Ann. Univ. Grenoble Sect. Sci. Math. Phys.
(N.S.) 23 (1948) , 57-112.
[23] Codd, E.F.: A relational model for large shared data banks. Comm.
ACM 13.6 (1970), 377- 387.
[24] Crawley, P.: Decomposition theory for nonsemimodular lattices. Trans .
Amer. Math. Soc. 99 (1961) , 246- 254.
[25] Crawley, P., Dilworth, R.P.: Algebraic Theory of Lattices. Prentice-Hall
Inc., Englewood Cliffs, New Jersey, 1973.
[26] Dedekind, R.: Vorlesungen iiber Algebra. Manuscript (1858-1868).
Printed in [121]
[27] Dedekind, R.: Uber die Theorie der ganzen algebraischen Zahlen. Sup-
plement XI to: Dirichlet, P.G.L.: Vorlesungen iiber Zahlentheorie. pt
ed. Braunschweig, 1863; 2nd ed. 1871, 3d ed. 1879, 4th ed. 1894.
[28] Dedekind, R.: Stetigkeit und Irrationale Zahlen. Vieweg, Braunschweig,
1st ed. 1872, lOth ed. 1969.
[29] Dedekind, R.: Was sind und was sollen die Zahlen? Vieweg, Braun-
schweig, 1st ed. 1887, lOth ed. 1969.
[30] Dedekind, R.: Uber Zerlegung von Zahlen durch ihre gr613ten gemein-
samen Teiler. Festschrift der Technischen Hochschule zu Braunschweig
bei Gelegenheit der 69. Versammlung Deutscher Naturforscher und
Arzte, 1-40 (1897). Reprint with concluding comment by E. Noether in:
R. Fricke (ed.), Richard Dedekind, Gesammelte Mathematische Werke,
2nd vol., Vieweg, Braunschweig, 1931 , pp. 103- 147.
[31] Dedekind, R.: Uber die von drei Moduln erzeugte Dualgruppe. Math.
Annalen 53 (1900) , 371-403. Reprint with concluding comment by E.
Noether in: R. Fricke (ed.) , Richard Dedekind, Gesammelte Mathema-
tische Werke, 2nd vol., Vieweg, Braunschweig, 1931, pp. 236- 271.
[32] Dedekind, R.: Uber die Permutationen des Korpers aller algebraischen
Zahlen. Festschrift zur Feier des hundertfiinfzigjiihrigen Bestehens der
Koniglichen Gesellschaft der Wissenschaften zu Gottingen. Abh. der
Math.-phys. Klasse (1901) , 1-17.
[33] Deiters, K., and Erne, M: Negations and contrapositions of complete
lattices. Discrete Math. 181 (1998) , 91-111.
[34] Diercks, V., Erne, M., Reinhold , J.: Complements in lattices of varieties
and equational theories. Algebra Universalis 31 (1994) , 506- 515.
[35] Dilworth, R.P.: Abstract residuation over lattices. Bull. Amer. Math .
Soc. 44 (1938), 262- 268.
132 M. Erne
[54] Everett, C.J.: Closure operators and Galois theory in lattices. Trans.
Amer. Math. Soc. 55 (1944) , 514- 525.
[55] Frink, 0.: Pseudo-complements in lattices. Duke Math. J. 29 (1962) ,
505- 514.
[56] Galois, E.: Memoire sur les conditions de resolubilites des equations
par radicaux (1831). Published by J. Liouville in the Journal de
Mathematiques 1846.
[57] Galois, E.: CEuvres Mathematiques. With an introduction by E. Picard.
Gauthier-Villars, Paris 1897.
[58] Ganter, B., Wille, R., Wolff, K. E. (eds.) : Beitriige zur Begriffsanalyse.
B.I. Wissenschaftsverlag, Mannheim- Wien - Zurich, 1987.
[59] Ganter, B., Wille, R. : Formal Concept Analysis - Mathematical Founda-
tion. Springer-Verlag, Berlin - Heidelberg - New York, 1999
[60] Gauss, C. F.: Demonstratio nova altera theorematis omnem functionem
algebraicam rationalem integram unius variabilis in factores primi vel
secundi gradus resolvi posse. Comm. soc. regiae scient. Gottingensis re-
centiores 3 (1816). Reprinted in: C. F. Gauss , Werke Bd. III, Georg
Olms, Hildesheim, 1981 , pp. 31-56.
[61] Gauss, C. F.: Disquisitiones Arithmeticae. Apud Gerh. Fleischer Iun.
Lipsia, 1801. Reprinted in: C. F . Gauss, Werke Bd. I, Herausg. Konig.
Ges. Wiss. Gottingen, 1870.
[62] Gierz, G., Hofmann, K.H. , Keimel , K ., Lawson, J.D., Mislove, M., and
Scott, D.S.: A Compendium of Continuous Lattices, Springer-Verlag,
Berlin - Heidelberg - New York, 1980.
[63] Gillman, L., Jerison, M.: Rings of Continuous Functions. Van Nostrand ,
Princeton. Reprint: Graduate Texts in Math. 43, Springer-Verlag, Berlin
- Heidelberg - New York, 1976.
[64] Girard, A.: Invention Nouvelle en l'Algebre (1629) , reimpression par D.
Bierens De Haan, Mure Freres, Leiden, 1884.
[65] Glivenko, V.: Sur quelques points de Ia logique de M. Brouwer. Bull.
Acad. Sci. Belgique 15 (1929), 183- 188.
[66] Grassmann, H.: Gesammelte Mathematische und Physikalische Werke .
ed. F. Engel. 3 Vol. , Leipzig, 1894- 1911.
[67] Grassmann, R.: Die Formenlehre oder Mathematik. Stettin , 1872.
Reprint Hildesheim, 1966.
[68] Gratzer, G.: General Lattice Theory. Bikhiiuser, Basel, 1978.
[69] Hailperin, T.: Boote 's Logic and Probability. Studies in Logic 85, North-
Holland, Amsterdam, 1976.
134 M. Erne
[70] Herrlich, H., Husek, M.: Galois connections categorically. J. Pure Appl.
Algebra 68 (1990), 165- 180.
[71] Heyting, A.: Die formalen Regeln der intuitionistischen Logik. Sitzungs-
ber. PreujJ. Akademie der Wiss., Phys.-Math. Klasse (1930) , 42-56.
[72] Hilbert, D.: Uber die Theorie der algebraischen Formen. Math. Annalen
36 (1890), 473- 534.
[73] Hilbert, D.: Uber die vollen Invariantensysteme. Math. Annalen 42
(1893), 313- 373.
[74] Hilbert, D.: Grundlagen der Geometrie. 7th ed., Teubner, Stuttgart,
1930.
[75] Hoffmann, R.-E.: Topological spaces admitting a "dual", in: Cate-
gorical Topology, Lecture Notes in Math. 719, Springer-Verlag, Berlin-
Heidelberg-New York, 1979, pp. 157- 166.
[76] Huntington, E. V.: Sets of independent postulates for the algebra of logic.
Trans. Amer. Math. Soc. 5 (1904), 288-309.
[77] Johnson, Jr., A.: A lattice whose residuated maps do not form a lattice.
J. Nat. Sci. and Math. 9 (2) (1969), 283-284.
[78] Johnstone, P. T.: Stone Spaces, Cambridge University Press, Cambridge,
1982.
[79] Korselt , A.R. : Bemerkungen zur Algebra der Logik. Math. Ann. 44
(1894), 156-157.
[80] Korselt, A.R.: Uber die Grundlagen der Geometrie. Jahresber. DMV 12
(1903), 402- 407.
[81] Korselt, A.R.: Uber die Logik der Geometrie. Jahresber. DMV17 (1908) ,
98- 124.
[82] Krull, W.: Axiomatische Begriindung der allgemeinen Idealtheorie.
Sitzungsberichte der physikalisch-medizinischen Sozietiit zu Erlangen 56
(1924), 47-63.
[83] Krull , W.: Zur Theorie der zweiseitigen !deale in nichtkommutativen
Bereichen. Math. Z. 28 (1928), 481- 503.
[84] Kunz, E.: Introduction to Commutative Algebra and Algebraic Geometry.
Birkhauser, Basel, 1985.
[85] Lagrange, J.-L.: CEvres Complf~ tes. Ed. J.A. Serret; G. Darboux. 14
volumes, Gauthier-Villars, Paris, 1867- 1892.
[86] Lagrange, J.-L.: Reflexions sur la resolution algebrique des equations.
Nouveaux Memoires de l'Academie Royale des Sciences et Belles-Lettres
de Berlin, 1770-1771. See also [85], vol. 3, pp. 205-421.
[87] Lawvere, F.W.: Adjointness in foundations. Dialectica 23 (1969), 281-
296.
[88] Levine, N.: Strongly connected sets in topology, Amer. Math. Monthly
72 (1965)' 1098- 1101.
Adjunctions and Galois Connections 135
[89] Lisa, J.: Cardinal sums and direct products in Galois connections. Com-
ment. Math. Univ. Carolinae 14 (1973) , 325- 338.
[90] Lorenz, F.: Einfuhrung in die Algebra. B.l. Wissenschaftsverlag, Mann-
heim, 1992.
[91] MacNeille, H.M.: Partially ordered sets. Transactions Amer. Math. Soc.
42 (1937), 90-96.
[92] Mehrtens, H.: Die Entstehung der Verbandstheorie. Gerstenberg, Hildes-
heim, 1979.
[93] Melton, A., Schmidt, D. A., Strecker, G. E.: Galois connections and com-
puter science applications. In: D. Pitt et al. (eds.) : Category Theory
and Computer Programming (Guilford 1985), Lecture Notes in Computer
Science 240 (1986) , 299- 312.
[94] Menger, K.: Bemerkungen zu Grundlagenfragen IV. Jahresber. DMV 37
(1928), 309- 325.
[95] Menger, K.: New foundations of projective and affine geometry. Ann.
Math . 37 (1936) , 456- 482.
[96] Menger, K.: Non-euclidean geometry of joining and intersecting. Bull
Amer. Math. Soc. 44 (1938) , 821-824.
[97] Menger, K.: Topology without points. The Rice Institute Pamphlet 27
(1940), 80- 107.
[98] Meyberg, K: Algebra, Teil 2. C. Hanser Verlag, Miinchen - Wien, 1976.
[99] Nelson, E.: Galois connections as left adjoint maps. Comm. Math. Univ.
Carolinae 17 (1976) , 523- 541.
[100] Nobeling, G.: Topologie der Vereine und Verbande. Arch. Math. (Basel)
1 (1948) ,154- 159.
[101] Nobeling, G.: Grundlagen der Analytischen Topologie. Springer-Verlag,
Heidelberg, 1954.
[102] Noether, E.: Abstrakter Aufbau der Idealtheorie. Math. Annalen 96
(1926)' 36-61.
[103] Ore, 0.: On the foundations of abstract algebra, II, Annals of Math. 37
(1936), 265- 292.
[104] Ore, 0.: Structures and group theory II. Duke Math. J. 4 (1938) , 247-
269.
[105] Ore, 0.: Theory of equivalence relations. Duke Math. J. 9 (1942) , 573-
627.
[106] Ore, 0.: Theory of monomial groups. Trans . A mer. Mat. Soc. 51 (1942) ,
15-64.
[107] Ore, 0.: Combinations of closure relations. Ann. of Math. (2) 44 (1943),
514- 533.
[108] Ore, 0.: Some studies on closure relations. Duke Math. J. 10 (1943) ,
573- 627.
136 M. Erne
[109) Ore, 0.: Galois connexions. Trans. Amer. Math. Soc. 55 (1944), 493-
513.
[110] Peirce, C. S.: Collected papers, Vol. III. Exact Logic, Vol. IV. The Sim-
plest Mathematics. 2nd printing, Cambridge, Mass., 1960.
[111) Pawlak, Z.: Rough concept analysis. Bull. Polish Acad. Sci.: Technical
Sciences 33 (1985), 495- 498.
[112) Pawlak, Z.: Rough sets. Kluwer, Dordrecht- Boston 1991.
[113) Picado, J.: The quantale of Galois connections. Preprint, University of
Coimbra, 2001.
[114) Pickert, G.: Bemerkungen iiber Galois-Verbindungen.
Ar·ch. Math. (Basel) 3 (1952) , 285- 289.
[115) Pratt, V.: Chu spaces. Notes for the School on Category Theory and
Applications, University of Coimbra, 1999.
[116) Purkert, W.: Ein Manuskript Dedekinds iiber Galois-Theorie. NTM-
Schriftenr. Geschichte Naturw. Technik Med. 13, Heft 2 (1977), 1- 16.
[128] Schroder, E.: Uber die formalen Elemente der absoluten Algebra. Stutt-
gart, 1874.
Adjunctions and Galois Connections 137
[129] Schroder, E.: Der Operationskr·eis des Logikkalkuls. Leipzig, 1877; repr.
Darmstadt, 1966.
[130] Schroder, E.: Uber Algorithmen und Calculn. Archiv der Math. und
Physik (2nd series) 5, (1887), 225-278.
[131] Schroder, E.: Vorlesungen uber die Algebra der Logik. (Exakte Logik). 3
Vol., Leipzig, 1890-1905; repr. New York, 1966.
[132] Schroder, E.: Algebra und Logik der Relative. Erste Abteilung. Leipzig,
1895.
[133] Shmuely, Z.: The structure of Galois connections. Pacific J. Math. 54
(1974), 209- 225.
[134] Shmuely, Z.: The tensor product of distributive lattices. Algebra Univer-
salis 9 (1979), 281- 296.
[135] Sonner, H.: Die Polaritiit zwischen topologischen Riiumen und
Limesriiumen. Arch. Math. (Basel} 4 (1953) , 461- 469.
[136] Steinitz, E.: Algebraische Theorie der Korper. Journal fur Mathematik
137 (1910), 167- 309.
[137] Stone, M.H.: The theory of representation for Boolean algebras. Trans .
Amer. Math. Soc. 40 (1936), 37- 111.
[138] Tignol, J.-P.: Galois' Theory of Algebraic Equations. World Scientific,
Singapore 2001.
[139] Toti Rigatelli, L.: Evariste Galois (translated from the Italian by J.
Denton). Birkhiiuser, Basel, 1996.
[140] Umbreit, S.: Formale Begriffsanalyse mit unscharfen Begriffen. Ph.
Diss., University of Halle, 1994.
[141] Vandermonde, A. T .: Memoire sur Ia resolution des equations. Histoire
de l'Acad. Royale des Sciences (avec les memoires de Math. f3 de Phys.
pour la meme annee, tires des registres de cette Acad.} (1771), 365-416.
[142] Van der Waerden, B.: Algebra, Erster und Zweiter Teil. pt_7th ed.,
Springer-Verlag, Berlin - Heidelberg - New York, 1936-1966.
[143] Vieta, F.: The Analytic Art. Translated by T. R. Witmer, Kent State
Univ. Press, Kent, Ohio, 1983.
[144] Voigt, A.: Was is Logik? Vierteljahresschrift fur wissenschaftliche
Philosphie 16 (1892) , 189-332.
[145] Von Neumann, J.: Continuous Geometry. Reprint of Lectures from
1935/6. Princeton, 1960.
[146] Ward, M.: Residuation in structures over which a multiplication is de-
fined. Duke Math. J. 3 (1937) , 627- 636.
[147] Ward, M.: Some arithmetical applications of residuation. A mer. J. Math.
39 (1937), 921- 926.
[148] Ward, M.: Structure residuation. Ann. Math. 39 (1938) , 558- 568.
138 M . Erne
[149] Ward, M.: The closure operators of a lattice. Ann. of Math. (2) 43
(1942)' 191- 196.
[150] Ward, M., Dilworth, R.P.: Residuated lattices. Trans. Amer. Math. Soc.
45 (1939), 335- 354.
[151] Ward, M., Dilworth, R.P.: Evaluations over residuated structures. Ann.
Math. 40 (1939), 328- 338.
[152] Waring, E.: Meditationes Algebraicae. Translated by D. Weeks, Amer.
Math. Soc., Providence, RI, 1991.
[153] Wille, R.: Restructuring lattice theory: An approach based on hierar-
chies of concepts. In: I. Rival (ed.) , Ordered Sets (Banff 1981}, NATO
ASI Ser. C, Math. and Phys. , No. 83 (1982) . D. Reidel Pub!. Co. , Dor-
drecht- Boston- London, 1981, 445- 470.
Author's address:
Marcel Erne
Department of Mathematics
University of Hannover
D-30167 Hannover
Germany
e-mail: erne@math.uni-hannover.de
Categorical Galois Theory: Revision
and Some Recent Developments
G. Janelidze
Abstract
1 Introduction
nothing but the Galois group of the universal covering, i.e. the largest
Galois group.
Grothendieck's GFT has been extended to an elementary-topos-theo-
retic context in various ways by M. Barr, Diaconescu, J. Kennison , G.
Wright, A. Joyal and M. Tierney, I. Noerdijk, M. Bunge and others,
and there are many other non-topos-theoretical extensions, such as the
one proposed by Y. Diers (19]; A. R. Magid's theorem [55, Theorem
IV.31] seems to be especially important - since it is the final step in
the extension of (separable) Galois theory from fields to commutative
rings. Magid's theory is indeed beyond the topos-theoreticallevel since
it involves profinite groupoid actions on profinite topological spaces,
and those do not form a topos.
A purely categorical approach to Magid 's theory was first briefly de-
scribed in [27] and then in [28], where it was already transformed into
categorical Galois theory, with a new example of central extensions of
groups - which is very far from Grothendieck's Galois theory. These
results were reported to Saunders Mac Lane, and presented in his talk
[54] - and the next paper (30] was written according to his suggestion,
with an additional page written by him for the introduction. Various
further developments are briefly described in the book (4] , whose main
purpose is to show a precise chain of generalizations from the classical
level of finite field extensions to the purely categorical level.
This expository paper presents a short review of categorical Galois
theory (with special attention to the connection with A. R. Magid 's
Galois theory of commutative rings and most recent developments in
the theory of generalized central extensions) , where however I was try-
ing to exclude the material that would copy the corresponding parts
of [4], for example the categorical approach to covering spaces de-
scribed in Chapter 6 of [4] ; some " minimal" definitions from [4] are
replaced by more refined ones, especially useful for formulations of
open questions and for a few observations that did not exist when the
manuscript of [4] was submitted for publication.
The paper is organized as follows: Section 1 shows how the topological
notion of connectedness becomes categorical, and transforms it into
what is called Galois structure, which is an abstract adjunction be-
tween categories with specified classes of morphisms called fibrations.
Several examples of Galois structures are given. The term "fibration"
Recent Developments in Categorical Galois Theory 141
is used for the first time; in fact it is suggested by the example studied
in [8](see Example 2.12).
Since the role of Galois group( oid)s in general is played by internal pre-
categories, the internal precategories and their actions are described
in Section 3; a sufficient condition on a precategory action to become
a category/ groupoid action is also given.
The categorical GFT in Section 4 is formulated essentially as in [32],
and then some related notions are defined and some examples are
described in Section 5.
The links and applications to Galois theory of commutative rings are
briefly described in Section 6, and the theory of generalized central
extensions is considered in Section 7.
Several open questions are listed in Section 8.
I would like to thank Klaus Denecke and the other organizers of the In-
ternational Conference on Galois connections in Potsdam for inviting
me; this paper is an extended version of the talk I gave there.
H({i})
t
HI(A)
(2.5)
where 'TJA is the unit of the adjunction, and the right hand vertical
arrow is the image of the inclusion map {i} ----t I(A) under the functor
H.
Our next step is to make the notion of connectedness much more ab-
stract by replacing Sets with an arbitrary category X. The structure
which we obtain provides an appropriate level of generality for categor-
ical Galois theory and therefore it is called Galois structure, alt hough
the definition we are giving here is slightly different from the original
144 G. Janelidze
one given in [32]. Its absolute version (see Definition 2.4( e)) is closely
related to various other structures that occur in general connected-
ness/ radical/ torsion theories (see [57] and references there) .
(I , H, rJ , E) : C---+ X (2.6)
and two classes F and <I> of morphisms in C and X respectively, whose
elements are called fibrations ; the following conditions on fibrations
are required:
(a) all pullbacks along fibrations exist, and the classes of fibrations are
pullback stable;
(b) the classes of fibrations are closed under composition and contain
all isomorphisms;
(c) the functors I and H preserve fibrations .
Such a Galois structure is said to be finitely complete, absolute, ad-
missible, or closed, if it satisfies the following conditions respectively:
(d) the categories C and X have all finite limits (usually there are all
small limits, but we will never use them) ;
(e) all morphisms in C and in X are fi brations;
(f) for every object C in C and every fibration <p : X ---+ I (C) in
X, the composite of the canonical morphisms I(C x HI(C ) H(X)) ---+
IH(X)---+ X is an isomorphism;
(g) for every object A inC, the morphism 'TJA : A---+ H I(A) is a fibra-
tion, and for every object X in X , the morphism Ex : I H(X) ---+X is
an isomorphism.
Let us consider/ recall some examples:
3 Precategory actions
From now on we have to assume that the reader is familiar with some
basic notions of internal category theory, described for instance in [4] .
This should not create problems for "non-experts" since these notions
are as simple and natural as their well-known special cases, such as
• internal groups ( = group objects) used for example in topology
and analysis, where internal groups in the category of Hausdorff
spaces are called topological groups;
Recent Developments in Categorical Galois Theory 147
p d
(3.1)
P1 x (d,1r) Ao Ao
proj1 j jw (3.2)
pl Po
c
148 G. Janelidze
(3.3)
w
X z
E (3.7)
are isomorphisms.
JE
F(E) <I>(I(E))
p!
j 1J(p)! (4.1)
F(B) <I>(I(B))
JB
HE
F(E) <I>(I(E))
p* r l(p)· (4.2)
1
F(B) <I>(I(B))
HB
the horizontal arrows here are as in (2.7), and the vertical arrows
form the appropriate change-of base adjunctions. The diagram (4.1)
obviously commutes, and since the diagram (4.2) is obtained from
(4.1) by replacing all arrows with their right adjoints, it commutes
too, up to a canonical isomorphism.
Definition 4.1. A fibration (A, f) over B is said to be
(a) a trivial covering (of B) , if t he diagram
---HI(A)
!HI(!) (4.3)
------HI(B)
(4.4)
is an isomorphism.
152 G. Janelidze
Spl(E,p TrivCov(E)
F(B) F(E)
p*
(4.6)
that is, the functor H8 induces an equivalence
TrivCov(B) rv CJ!(I(B))
(4.7)
Therefore, under the admissibility condition, the pullback (4.5) can
be rewritten (up to an equivalence) as
Recent Developments in Categorical Galois Theory 153
Spl(E , p) <f!(I(E))
(4.8)
F(B) F(E)
p*
Since the diagram (4.2) commutes, the equivalence (4. 7) tells us that
the functor p* carries trivial coverings to trivial coverings, and that
TrivCov(B) is obviously contained in Spl(E , p) .
If we ask now, what information on F(B) can be obtained using the
category X, there is a trivial answer - namely the equivalence (4. 7)
that describes TrivCov(B) , but there is also a non-trivial one- namely
Theorem 4.3 below, which describes the larger category Spl(E , p)
whenever (E, p) is a monadic extension in the sense of
The first full proof of this theorem is given only in [32], but as was
already mentioned, the special case proved in [27] (in detail in [28])
is sufficient in order to show that the fundamental theorem of Galois
theory of commutative rings, whose most general version is due to A.
R. Magid [55], extends to a purely categorical context. The same is
shown in [4] on a more elementary level but with some long calculation
omitted.
The (internal) precategory I(Eq(p)) should be called the Galois pre-
category of the extension (E , p) and denoted by Gal(E , p) . It is a
154 G. Janelidze
groupoid if the conditions of Corollary 3.4 are satisfied, and if so, then
it is a group if and only if E is connected, i.e. I(E) is a terminal object
in X.
implications are not true in general. It can also be proved that the
existence of a weakly universal covering implies that every projective
covering is weakly universal, and that every connected projective cov-
ering is universal. These and some other links (see also Section 6)
between the notions listed in Definition 5.1 in some sense are visible
already in the following simple cases:
r as in r as in ras in ras in
Example 2.5 Example Examp le 2.9 Example 2.11
2.8
with C = G-Sets , with C as in the last w ith C = Groups and
where G is a sentence there; X = Abelian Groups;
groupj B = 1 B the g round field B any group ;
Trivia l Trivial G - sets All B-algebras that are the e xtensions of B
fibrations
coverings i.e. sets equipped fin ite products that are obtained as
with the trivial of copies of B pullbacks of
action of G abelian exte nsions
of abe lianizations of B
Monadic nonempty Monadic Nondegen e rat ed All extensions
exte nsions G -sets extensions B -algebras of B
Coverings All G -sets All Separa ble B -algebras , Central extensions
fibrations
i.e. finite products of of B
separable field
extensions o f B
Connected Tra n sitive G-sets Isomorph. Separable field Central extensions
coverings with exac t ly one extensions of B (E, p) of B , s u ch t h at
(non empty ) orbit the hom omorp hi s m
HI(p,O ) : HI(E ,D)
--+ Ht (B, D) is an
isomorphis m
Cartesian N onempty G -sets, All monad. Nonempty finite products A ll exte n sions
normal in whi ch e very ex tensions of those field extensions of B
extensions stabilizer of B in wh ich the s ubfield
is a normal of separable elements is a
subgroup Galois extension of B
Normal As above As above Nonempty finite Ce ntral extensions
extensions products of of B
Galo is extensions of B
W eakly Nonempty As above Nonempty finite products Weakl y unive rsal
universal si m pie ( = free) of c opies of the separable central extensions
cove ring s G-sets closure of B , provided that i. e . weak ly ini t ia l
clos ure is a finite o bjects in t h e
extension of B; otherwise category of ce n t ra l
t here are no weak ly extensions o f B
universa l coverings of B
Proj ective As above Projective As a bove As above
monadic
cove rings extensions
Projective As above As a bove Non e mpty finite produc t s Free extensions , i.e.
monadic of c opi es of t h e a lgebraic the extensions ( E, p)
ex tensions closu re of B prov ided t h at of B in which E is a
clos ure is a finite free g roup
extension of B; otherwise
there are no projective
m onadic extension s of B
Universal S imple Projective The se p a r a ble closure of The universal central
monadic
coverings transitive e xte nsion s B, provided that clos ure is exte ns ion of B
a ll w hose
G-sets e ndom. a finite extensio n of B i prov ided B is perfect ,
a re isom. otherwise there a re no i.e. B =[B , B ]
uni versa l co ve rings of B
If (E,p) and (E',p') are fibrations over B and p' factors through p,
then clearly Spl(E,p) <::; Spl(E',p'). Therefore whenever (E,p) is a
156 G. Janelidze
Lemma 7 .3. The fibration (E~, p~) above is a projective weakly uni-
versal covering.
object in the category Cov(B) , and that is what is usually called the
universal central extension. In the case of !1-groups the existence of
universal central extensions is a part of what A. Frohlich's school calls
theory of Baer invariants; we already mentioned the papers [20), [53),
[21), but much deeper links are to be established.
8.1 The classification theorem for covering spaces of a " good" space is
shown in detail in [4] to be a special case of what is presented here as
Corollary 5.3 of Theorem 4.3. Does it mean that the notion of Galois
structure is rich enough to be used for developing " abstract homo-
topy theory" = " higher dimensional Galois theory" to be applicable
to other examples of categorical Galois theory? If so, this approach
should be in the same relationship with D. Quillen's approach [60), as
the general adjunctions with the adjunctions formed by the functors
(2.2) and (2.4). One possible way of developing higher dimensional
Galois theory is indicated by a very special example of so-called dou-
ble central extensions of groups [31], further extended in [33].
8.2 A further generalization of Galois theory to so-called variable cate-
gories is proposed in [41] and then an intermediate case studied in [44].
After that A. Joyal- M. Tierney's theorem on presentations of geomet-
ric morphisms of toposes [52] and the Tannaka duality become parts
of (generalized) categorical Galois theory. However it seems that they
should even be special cases of the " straightforward" two-dimensional
version of the very special situation studied in [11] and in [38].
8.3 The universal-algebraic notion of commutator (of two congruences)
was invented by J.D.H. Smith [62] for Mal 'tsev varieties, and then
generalized in various directions by various authors, although all defi-
nitions agree in the congruence modular case; some relevant references
are given in [40), where the commutators are described via internal cat-
egorical structures ( "pseudogrupoids" - rather than " pregroupoids"
used in [58] in [58]). As explained in Section 6 above the notion of
commutator theory perfectly agrees with the categorical notion of cen-
tral extension, at least in the congruence nodular case. However this
comparison makes sense only in a very special case of X being the
category of abelian objects inC (see 7.1). Is it possible to define the
notion of commutator with respect to any subvariety/ " good" reflec-
Recent Developments in Categorical Galois Theory 165
References
[3] M. Barr, Abstract Galois theory II, Journal of Pure and Applied
Algebra 25, 1982, 227-247.
Author's address
A. Razmadze Mathematical Institute
Georgian Academy of Sciences
1 M. Alexidze Street
Tbilisi 0193
e-mail:george_janelidze@hotmail.com
The Polarity between Approximation
and Distribution
M. Erne
Abstract
173
K. Denecke eta/. (eds. ), Galois Connections and Applications, 173-210.
© 2004 Kluwer Academic Publishers.
174 M. Erne
0 Introduction
given by
x « y {:::} y :::; VW implies x :::; VF for some F ~w W
(where F ~w W means that F is a finite subset of W) , has the ap-
proximation and consequently the interpolation property [18]. In other
words, L is a continuous lattice in the sense of Scott [24]. Perhaps even
more interesting is the fact that a dcpo or domain (a poset in which all
directed subsets have joins) is continuous ( that is, for each element
there is a least directed downset whose join dominates that element)
iff the Scott topology (equivalently, the system of Scott-closed sets)
is completely distributive (see [18, 21]) . The Scott-open sets are then
precisely those of the form U«.
A similar characterization holds for lattices with completely distribu-
tive ideal lattices. Indeed, a much more general theory has been
developed for so-called Z-distributive and Z-continuous lattices and
posets (see, for example, [4, 5, 7, 12, 22, 25]) . Here, instead of arbi-
trary, directed or finite subsets, one considers a general system Z (in
[5, 7, 8, 14] denoted by M) of subsets of a poset P. The Z-join ideals,
i. e., those downsets that contain with any member of Z its join (pro-
vided it exists) form a closure system z v. On the other hand , passing
from Z to the system Z l\ of all Z-downsets
.}Z = {y: y:::; z for some z E Z}
where Z is a member of Z or a singleton {x}, one may assume that
Z is a standard extension, i. e. a collection of downsets including at
least all principal ideals
.}y = {x: x :S: y} (yEP) .
Moreover, there is no essential loss of generality in assuming t hat all
members of Z have joins - in other words, that the underlying poset
is Z-complete. Then, it turns out that z v is completely distributive
whenever Z is strongly approximating, meaning that the Z-below ideals
JJ-zy = n{z E ZA: y :S:V Z}
belong to ZA and, moreover, the Z-below relation, defined by
X <<z Y {:::} X E JJ-zy ,
has both the approximation and the interpolation property. Under
rather mild hypotheses, the converse implication is true as well. (Con-
176 M. Erne
sult the aforementioned references, in particular [5] and [12], for de-
tails.)
Often, one has to work with ordered structures possessing weaker local
approximation properties. For example, the ideal lattice of a join-
semilattice S is known to be distributive (and even a frame) iff for
all finite subsets Z and all x E S with x :=::; V Z, there is a finite
W ~-!-Z with x = VW (cf. [8, 19]). Or, the Scott topology of a dcpo
is a dual frame iff the corresponding condition is fulfilled for directed
instead of finite subsets (for complete lattices, this is equivalent to
meet-continuity; cf. [14, 18]). More generally, it was shown in [8] that
the Z-join ideals of a Z-complete poset P form a frame whenever Z
is locally approximating, that is,
ZEZ and x::;VZ imply x=VW for some WEZ with W~ -t-Z.
Again, under suitable weak assumptions on Z (for example, that Z 11
be closed under binary intersections), the converse also holds true.
A recent result established in [14] is that all T 0 closure systems that
are frames arise as Z-join ideal systems from locally approximating
standard extensions. Similarly, we shall demonstrate in the present
note that all completely distributive T0 closure systems come from
strongly approximating standard extensions in that manner.
An appropriate and elegant concept for these investigations is that of
Galois connections and, in particular, polarities in the sense of Birkhoff
[3]. For surveys on that topic, see [15] and the article Adjunctions and
Galois Connections: Origins, History and Development in this volume.
Recall that polarities are pairs ( <P, \J!) of anti tone (inclusion inverting)
maps between power sets such that the two possible compositions are
extensive. Any such Galois connection between power sets comes from
a unique relation (! between the underlying sets A and B such that
<P(Y)=Y 12 ={zEB:y(!z forall yEY} (Y~A) ,
\J!(Z) = Z 12 ={yEA: y (! z for all z E Z} (Z ~B).
In the present situation, the polarity results from a relation canonically
associated with a given closure operation. Often, this operation is the
cut operator ~ of a poset P = (X, :=::;), assigning to each subset Y of
X the intersection of all principal ideals containing Y. The crucial
relation is then defined by
The Polarity between Approximation and Distribution 177
x 1\ VY = V(x 1\ Y) (x E L, Y ~ L)
where x 1\ Y is a shorthand notation for {x 1\ y : y E Y} .
From the viewpoint of Galois connections, it is worthwile to note that
a complete lattice L is a frame iff for each x E L , the unary meet
operation z f-----7 x 1\ z has a right adjoint , sending y to the relative
pseudocomplement or residual
x....-.ty = y: x = V{ z E L :x 1\ z ~ y}.
A subframe of L is closed under arbitrary joins and finite meets,
whereas a sub locale Y of L is closed under arbitrary meets (/\-closed)
and under residuation, the latter meaning that y: x lies in Y for all x E
L and y E Y. For more background about frames , see, for example,
[20].
Henceforth, we are fixing
- a frame L with order relation ~ '
- a closure operation b on L , and
- a subset X of the range L 8 = b[L] that is join-dense in L.
Thus, each element of L is a join of elements from X. For later use,
we note the known fact that a join-dense subset X of L is /\-closed
in L (that is, for each subset of X , the meet formed in L belongs to
X) if and only if X is a complete lattice with respect to the induced
order. It is an experience in order and category theory that often
the reduction to join-dense subsets simplifies constructions and proofs.
This will be a guiding principle in the subsequent considerations. Most
of the definitions will involve the closure operation b, and some of
them also the join-dense subset X, although that dependence will not
be mentioned explicitly.
It will be convenient to write bx for b(x) etc. Recall the most succinct
characterization of closure operations by the equivalence
x ~ by {::} bx ~ by.
Every subset Y of L gives rise to a closure operation IV defined by
/YX = 1\ {y E Y : X ~ y },
and Y coincides with £ 1Y iffY is /\-closed in L. More generally, for
every preclosure operation, that is, for every map f3 : L --t L satisfy-
ing
The Polarity between Approximation and Distribution 179
nucleus
-0-
extensive /\-homomorphism
-0-
prenucleus
-0-
pseudonucleus
-0-
preclosure operation
locally /\-approximating
-ll-
locally approximating
-ll-
locally 8z -approximating
-ll-
locally 8Z -approximating
-ll-
locally 8-approximating
Proof. Only the last claim requires a verification. The set N of all
6-nuclear elements is /\-closed by Lemma 1. It is a sublocale by Propo-
sition 1, and by Proposition 4, its closure N 8 e is a Galois-dosed locally
approximating subset containing N . By maximality, N must coincide
with its Galois closure. o
Summarizing the previous results, we arrive at
are some situations where the global analogues fail at least partially
or are more complicated. For example, Lemma 3 has no exact coun-
terpart for maps that preserve arbitrary meets. To be more explicit: it
is not true in general that if a prenucleus (3 preserves arbitrary meets,
the associated nucleus 73 would also preserve arbitrary meets.
strongly approximating
-0-
( globally) approximating
-ll-
6z -approximating
-ll-
6Z -approximating
-0-
6 -approximating
and therefore 1\ W E Z. o
After these remarks about invariant and Galois-closed subsets, we are
now in a position to establish the global version of Proposition 4.
Proposition 8. A subset Y of L contains L 8 and is completely dis-
tributive (hence a sublocale) iff Z = ye is strongly approximating and
satisfies Y = Z 8 . In particular, L 8 is completely distributive iff L is
strongly approximating.
We conclude this section with the remark that many of the previous
results and their local counterparts admit a common generalization
to the situation of meets formed by fewer than K elements, where K
is a regular infinite cardinal. For example, call a subset Z of L K-
approximating if for each x E X and each subset W of Z with fewer
than K elements, x :::; /\ 6[W] implies x = 6z for some z E Z with
z :::; /\ w, and call a complete lattice K-distributive if vn
y = /\ V[Y]
for all systems Y of less than K downsets. Then, among other facts
generalizing those obtained before, one may show that if a /\-closed
subset Y of a K-distributive complete lattice with closure operation 6 ;::::
/Y is K-distributive, too, then the set Z = Yt? is K-approximating and
satisfies Y = Z 6 ; and the converse holds at least if 6z is idempotent.
Lemma 13. The relation <lz is idempotent (interpolating) iff the map
{!z is idempotent (h ence a dual closure operation). Sufficient for idem-
potency is the equation
c5zx = {!zbzx for all x E X,
and this is also necessary if the elements of X are V-prime.
Proof. Recall that r!zY = V{u: U<lzY} (y E L). Hence, if<lz IS
idempotent then
r!zr!zY = V{u: U<lz V{v: v <lzy}} =
V{u: U<lzV<lzY for some v} = V{u: U<lzY} = r!zY·
Conversely, suppose {!z is idempotent. Then, as {!z preserves joins,
u <1 zY {::} u <1 r!zY = V{ezv: v <1 r!zY}
{::} u <1 {!zV for some v <1 {!zY {::} u <1 zV <1 z Y for some v .
By definition of {!z, the equation c5zx = {!zbzx for all .T E X entails
Proof. (a)::::} (bn)· Put Xn = {2zn6zx. Then x = "(Xo , and the equations
"fXn+l = "( (}zXn = 'Y (V {6zx' : x' EX, x' <l Xn}) =
'Y(V {"(6zx' : x' E X, x' <l Xn}) =
(a1) =} (b1) {::} (cl) =} (d1) {::} (e1) =} (fl) {::} (g1) {::} (h1)
-U- 11 -0- -U- -0- -0- -U- -0-
(a2) {::} (b2) =} (c2) =} (d2) {::} (e2) =} (f2) =} (g2) {::} (h2)
which is the Z-core and also the Z-below part of the principal ideal
generated by x . Recall that a strongly approximating standard exten-
sion is one such that ~z is idempotent, i. e., the sets
~zy = U{~Z: ZEZ, Z~ .,j..Y}
following "standard" version (cf. [14] for the first part and [12] for the
second):
Theorem 4. Associating with each locally approximating standard ex-
tension Z of a poset P the collection zt:. of all Z-tl-ideals, one obtains
precisely all standard completions that are frames . Similarly, the com-
pletely distributive standard completions of P are precisely the systems
of Z-tl-ideals coming from strongly approximating standard extensions
Z, In both cases, restriction to Galois-closed extensions makes the re-
spective correspondences bijective.
Corollary 13. For any poset P = (X, ::;) , the following conditions
are equivalent:
(a) The lattice Ft:. of all Frink ideals is distributive (a frame) .
(b) Ft:. is a sub locale of£, the frame of all downsets.
(c) The cut operator 6 preserves finite intersections in Ft:..
(d) The ideal operator 6F preserves finite intersections in .C.
(e) 6F induces a (pre)nucleus on .C.
(f) For F ~wX and x E 6F, there is an E ~w.J-.F with x = VE .
(g) F is locally approximating.
A V-semilattice P with these properties is called distributive (see,
for example, [19]). In (8], an example of a V-semilattice has been
given whose ideal lattice fails to be distributive, although the sys-
tem of all downsets (not only the finitely generated ones) is locally
6-approximating. Of course, that failure cannot happen with 1\-
semilattices, because then the finitely generated downsets form a 1\-
semilattice, too, and Corollary 1 applies. For the "global" situation,
we get:
poset is "the" free V-semilattice over that poset. Our final exam-
ple shows that the standard extension :F of a V-semilattice may be
(strongly) approximating without being locally /\-approximating.
Example 4. The "double real square"
C = [0, 1] X [0, 1] X { 0, 1}
is completely distributive. For any number r with 0 < r < 1, the
subset
S = C \ (({r} X [0, 1] X {0}) U ([0, 1] X {r} X {0}))
is a V-subsemilattice whose elements are joins of finitely many V-prime
elements. For x = (1, 1, 0) , y = (r, 1, 1) , z = (1 , r, 1) and F ={.{y,z},
we obtain x ~ V F, but {.x n F is not finitely generated.
References
[1] Banaschewski, B., Another look at the localic Tychonoff theorem,
Comm . Math. Univ. Carolinae 29 (1988) , 647-656.
[3] Birkhoff, G., Lattice Theory. Amer. Math. Soc. Coll. Publ. 25 , 3rd ed.,
Providence, R.I., 1973
[4] Bandelt, H.-J. and Erne, M., The category of Z-continuous posets, J.
Pure Appl. Algebra 30 (1983) , 219-226.
[6] Erne, M., Scott convergence and Scott topologies on partially ordered
sets II, in: [2], pp. 61-96.
[9] Erne, M., Adjunctions and standard constructions for partially ordered
sets, in: Eigenthaler, G. et al. (eds.) , Contributions to General Algebra
2, Proc. Klagenfurt Conf. 1982, Holder-Pichler-Tempsky, Wien, 1983,
pp. 77-106.
[11] Erne, M., Algebraic ordered sets and their generalizations, in: Rosen-
berg, I. and Sabidussi, G. {eds.), Algebras and Orders, Proc. Montreal
1992, Kluwer, Amsterdam, 1994.
[12] Erne, M., Z-continuous posets and their topological manifestation,
Appl. Cat. Structures 7 (1999) , 31-70.
[13] Erne, M., Continuity properties and Scott frames. Preprint , University
of Hannover, 2000
[14] Erne, M., Pultr, A., Sichler, E. , Closure frames and web spaces.
Preprint, Hannover-Prag, 2000
[17] Frink, 0., Ideals in partially ordered sets. Amer. Math. Monthly 61
(1954), 223-234.
[19] Gratzer, G., General Lattice Theory, Birkhauser Verlag, Basel, 1978
[24] Scott, D. S., Continuous lattices. In: Toposes, Algebraic Geometry and
Logic, Lecture Notes in Math. 274, Springer-Verlag, Berlin - Heidel-
berg - New York, 1972.
[26] Wright, J. B., Wagner, E. G., and Thatcher, J. W., A uniform ap-
proach to inductive posets and inductive closure, Theor. Comp. Sci. 7
(1978), 57-77.
Author's address:
Marcel Erne
Department of Mathematics
University of Hannover
D-30167 Hannover
Germany
e-mail: erne@math.uni-hannover.de
Galois Connections and Complete
Sublattices
K. Denecke, 5. L. Wismath*
Abstract
Any Galois connection (between two sets) has associated with it two clo-
sure operators, and hence two complete lattices (dually isomorphic to each
other). Set-theoretical Galois connections are induced by relations, and
it is interesting to know which subrelations of an inducing relation will in
turn induce complete sublattices of the two lattices. Complete sublattices
of the Galois-lattices may also be obtained using conjugate pairs of closure
operators. It is also well known that the set of fixed points of a closure (or
a kernel) operator defined on a complete lattice forms a complete lattice,
and in this case too we can look for properties which ensure that this lattice
is a complete sublattice. This paper surveys the results known about such
subrelations, conjugate pairs of closure operators, and closure and kernel
operators. We also give an application of the closure and kernel opera-
tor method, which generalizes several well-known examples from universal
algebra using the Galois connection (Id,Mod) .
AMS Classification: 06B23, 06A15.
Key Words: Galois connection, Closure operator, Kernel operator, Com-
plete sublattice.
such that for all T, T' ~ A and all S , S' ~ B the following conditions
are satisfied:
by
i(T) : {s E E I VtET ((t,s) E R)},
p(S) : {tEA I VsES ((t, s)ER)} .
Then it is easy to verify that the pair (i, f.1) forms a Galois connec-
tion between A and B, called the Galois connection induced by R.
Conversely, any Galois connection between A and B determines a re-
lation R ~ A x B. Thus there is a one-to-one correspondence between
relations from A to B and Galois connections between A and B.
214 K. Denecke, S. L. Wismath
be a relation between A and B . Then 'Yl and ')'2 are called conjugate
with respect to R , and we say that the pair ('Yl , ')'2 ) is a conjugate pair
with respect toR, if for all tEA and all s E B, 'Y1 (t) x {s} ~Riff
{t} x 'Y2 (s) ~ R.
This property of conjugacy of two closure operators is defined in terms
of individual elements. When the two operators are also additive, we
can extend this to sets of elements. Thus when ('Yl, 'Y2 ) is a pair of
additive closure operators, 'Yl on A and ')'2 on B , and they are conju-
gate with respect to a relation R ~ Ax B , then for all T ~ A and all
S ~ B we have T x 'Y2 (S) ~ R if and only if 'Y1 (T) x S ~ R .
The two closure operators w and Lf..L , obtained from a Galois connec-
tion induced by a relation R , are always conjugate with respect toR.
But f..LL and Lf..L need not be additive in general.
Definition 2.3. {{DWB}) Let 'Y := {1'1 , 'Y2 ) be a conjugate pair of ad-
ditive closure operators, with respect to a relation R ~ A x B . Let Ry
be the following relation between A and B:
Theorem 2.4. ([DWB}) Let 'Y = {1'1 , 'Y2 ) be a conjugate pair of addi-
tive closure operators with respect to R ~ A x B . Then for all T ~ A
and S ~ B , the following properties hold:
and dually,
The next theorem is the "Main Theorem for Conjugate Pairs of Clo-
sure Operators", from [Rei]. It shows that when we consider sets
which are closed under the original Galois connection from R, there
are four equivalent conditions for such sets to also be closed under the
new connection from R1 .
Proof: We prove the equivalence of (i) ,(ii) ,(iii) and (iv); the equiva-
lence of the four dual statements can be proved dually.
(i) ::::} (ii) We always have T ~ --y1 (T) , since --y1 is a closure opera-
tor. Since iJ..t is a closure operator we also have --y1 (T) ~ iJ..t( --y1 (T)) =
i-y(J..t-y(T)) = T, by 2.4 (v') and (i).
(ii) ::::} (iii) We have ~-t(T) = ~-tb1 (T)) = /-t-y (T) by (ii) and 2.4 (i) .
(iii) ::::} (iv) We have --y2 (~-t(T)) = --y2 (~-t-y (T)) = /-t-y (T), using 2.4 (iv)
and (iii).
(iv) ::::} (i) Since the i-y /-t-y-closed sets are exactly the sets of the form
i-y(S), we have to find a set S ~ B with T = i-y (S). But we have
i-y(~-t(T)) = i('"Y2 (~-t(T))) = t(~-t(T)) = T , by 2.4 (i') and our assumption
that T is ij..t-closed. •
Proof: We prove only (i') and (ii') ; the others are dual.
(i') Suppose that --y2( S) ~ ~-t( t( S)). Since J..tL is a closure operator
we have J..t(t(S)) = J..t(t(J..t(t(S)))) 2 J..t(i('"Y2(S))) = J..t -y (t-y (S)) , by our
assumption and by 2.4 (v). Also S ~ --y2(S) , and hence we have
J..t(i(S)) ~ J..t(i('"Y2(S))) = /-t-y (i-y (S)) , again by 2.4 (v). For the converse
218 K. Denecke, S. L. Wismath
we have 1'2(5) ~ J1(~,(!'2 (S))) = /1-y (~,-y (S)) = J1(~,(S)) , using the exten-
sivity of f1L,, 2.4 (v) and our assumption.
(ii') Let ')'2(5) ~ (!1(~,(5)). Then S ~ ')'2(S) implies that ')'2 (J1(~,(S)))
~ ')'2 (!1(~,(1'2 (5)))). We also have ')'2 (J1(~, (!'2(S)))) = /'2(J1(~,-y (S))) by
Theorem 2.4 (i'), and ')'2 (J1(~,(!'2 (S)))) = J1(~,-y (S)) by 2.4 (iv') . In ad-
dition, J1(~,-y(5)) = J1(~,(!'2 (S))) ~ J1(L,(J1(~,(S)))) = J1(~,(S)). Altogether
we obtain J'2 (J1(~,(5))) ~ 11(~,(5)). The opposite inclusion is always
true, since ')'2 is a closure operator. Conversely, 5 ~ J1(~,(5)) implies
')'2 (5) ~ ')' 2 (!1(~,(5))) = 11(~,(5)) , by the extensivity of f1L, , the mono-
a:::; {3 :{:} (VT ~ A)(V5 ~ B)[!'1 (T) ~ !'2 (T) and 1'~(5) ~ I'~(S)].
When a :::; {3, it can be shown that the lattice 1iJ.Lf3 Lf3 is a sublattice of
1iJ.La La , and dually that 1iLf3 Jl.f3 is a sublattice of 1iLa J.La. The following
additional properties may also be verified:
3 Galois-Closed Subrelations
In the previous section we used a pair of additive closure operators,
which is conjugate with respect to the relation R, to determine a new
relation R1 , which in turn induces a new Galois connection and closure
operators. We showed that the sets closed under these new operators
form complete sublattices of the original lattices of closed sets. Now
we want to focus on the relations such as R, which determine com-
plete sublattices of our original lattices. In general, we can look at
subrelations R' ~ R, and consider the complete lattices of closed sets
obtained from the Galois connection induced by R'. When are these
lattices complete sublattices of the lattices obtained via R? In this
section we describe a property of subrelations R' of R which is suf-
ficient to guarantee that the new complete lattices obtained from R'
will be complete sublattices of the original lattices, and show that any
complete sublattices of our original lattices arise in this way. The
property we need is called the Galois-closed subrelation property.
Definition 3.1. Let R and R' be relations between sets A and B,
and let (p,, i) and (p,' , i1 ) be the Galois connections between A and B
induced by R and R', respectively. The relation R' is called a Galois-
closed subrelation of R if:
1) R' ~ R, and
(ii) For any T ~A, if t'p/(T) = T then p,(T) = p,'(T) , and for any
S ~ B, if p,'t'(S) = S then t(S) = t'(S);
(iii) For all T ~ A and for all S ~ B the equations t' p,' (T) = L p,' (T)
and p,' t' ( S) = p, t' ( S) are satisfied.
Ru := U {T x p,(T) I T E U}
is a Galois-closed subr·elation of R.
Galois Connections and Complete Sublattices 221
(iii) For any Galois-closed subrelation R' of R and any complete sub-
lattice U of 1lq. , we have
(ii) Now let U be any complete sublattice of 1l~w We will prove that
the relation Ru is a Galois-closed subrelation of R o First, for each
non-empty T E U we have p,(T) = {s E B I Vt E T, (t , s) E R} and
then T x p,(T) ~ Ro Therefore Ru ~ R o To show that the second
condition of the definition of a Galois-closed subrelation is met, we
let (p,' , ~') be the Galois connection between sets A and B induced by
222 K . Denecke, S. L. Wismath
Ru, and assume that tl(T) = S and t'(S) = T for some T <;;;; A and
S <;;;; B. Our goal is to prove that
(iii) Now we must show that for any complete sublattice U of1lqj,, and
any Galois-closed subrelation R' of R , we have URu = U and Run, = R'.
We know that URu := 1£L, Jl/ , the lattice of subsets of A closed under
the closure operator t' p,' induced from the relation Ru. This means
that T E URu iff t' p,' (T) = T. First let T E URu, and let S be the
set p,'(T). Then we have t'(S) = T , and since Ru is a Galois-closed
subrelation of R we conclude that
This shows that T E 1£,,~ 11,, which is equal to URu. We now have the
required equality URu = U .
To show the opposite inclusion, letT E UR', and letS= p,(T). Then
from Facts 1 and 2 we have
of all fixed points of (/); and for any closure system S we have the
closure operator 'P defined by
t:
'P(T) = 'Ps(T) := 1\{T' E S IT' 2 T} forT E .C.
224 K. Denecke, S. L. Wismath
Moreover, for any closure system S and any closure operator cp, we
have 1icps = S and cp1i<p = cp.
There is also a dual 1-1-correspondence between kernel operators and
kernel systems on a complete lattice £. A kernel operator is a mapping
which is intensive, monotonic and idempotent, and a kernel system on
£ is a family S of subsets of£ which is closed under arbitrary joins.
Then for kernel operators 'ljJ : £ ---* £ on £ and kernel systems S on
£,we set
for every index set J, then the set of all fixed points under cp,
1icp = {T E £ I cp (T) = T}
is a closure operator on .C with cp1l(.C) = 1t, and <{)1£ satisfies the con-
dition (*). Moreover, 1tcp1i = 1t and <{)1£'{' = cp.
'l/J1l(T) := v
£
{T' E 1t IT' :s; T}
is a kernel operator on .C with 'l/J1i (.C) = 1t1/J, and 'ljJ satisfies the con-
dition (**). Moreover, 1t1/J1i = 1t and 'l/J1i..p = '1/J.
5 An Application
We saw in the previous section that any join-preserving closure opera-
tor on a complete lattice induces a complete sublattice of the lattice. In
this section we describe a technique to produce such a join-preserving
closure operator. Our technique is a relatively simple one, but when
applied to the Galois connection (I d, Mod) leads to some interesting
and new examples of complete sublattices of the lattice of all varieties.
As before, we assume that ( L, J.L) is a Galois connection between two
sets A and B. Let E ~ B be a subset of B which is closed under
the closure operator LJ.L, so that LJ.L(E) = E. We define the following
functions.
(ii) The operator cp~ is a closure operator on the lattice 1-lll-£ of the
subsets of A closed under the closure operator JU, and it preserves
non-empty joins.
Theorem 5.5. LetT E 1-l!l-£ be a set such that cp~ (T) =1- T. Assume
that the operator cp~ satisfies the inclusion
Galois Connections and Complete Sublattices 227
It is well known that these two maps form a Galois connection between
Alg(r) and W7 (X) 2, induced by the relation of satisfaction between
algebras and identities. The corresponding complete lattices are the
lattice .C(r ) of all varieties of type r, and the lattice £(r) of all equa-
tional theories of type T.
Now we take E = E(r) to be any property of identities which is an
equational theory, that is, any element E E £(r). The map cp~ with
~ H ~ n E is then a kernel operator which preserves meets. By Theo-
rem 5.3, the mapping cp~ = f-tip~ i = M odip~ldis a closure operator on
the lattice £(T), and preserves joins. Then the collection of cp~-closed
varieties forms a complete sublattice of .C(r) . This corresponds to the
Galois connection induced by the Galois-closed subrelation
Re = {(A, s ~ t) E Alg(r ) x E I A satisfies s ~ t}.
Corollary 5.6. Let E(r) be any property of identities which forms an
equational theory. Then the class of all ip~ - closed varieties of type T
228 K . Denecke, S. L. Wismath
References
[Mel] Mel'nik, I. 1., Nilpotent shifts of varieties (in Russian), Mat. Za-
metki 14, No. 5, 1973. English translation: Math. Notes 14, 1973,
962-966.
[Tar] Tarski, A., A lattice theoretical fix point theorem and its applica-
tion, Pacific. J. Math. 5 (1955), 285- 310.
Authors' addresses:
Klaus Denecke
University of Potsdam
Institute of Mathematics
Am Neuen Palais
14415 Potsdam
Germany
e-mail: kdenecke@rz.uni-potsdam.de
Shelly Wismath
Dept.of Mathematics and CS
University of Lethbridge
Lethbridge, Ab.
Canada T1K-3M4
e-mail: wismaths@cs.uleth.ca
Galois Connections for Operations
and Relations
R. Poschel
Abstract
This paper reports on various Galois connections between operations and
relations. Several specifications and generalizations are discussed.
AMS Mathematics Subject Classification: 08A55, 03B10.
Key words: Operations, Relations, Clones, Relational algebras.
Introduction
relations)
The (A) may be omitted if it is clear from the context. 0-ary functions
or relations are not considered (mainly for technical reasons).
An m-tuple r E Am sometimes will be regarded as a mapping r :
m ----t A with m := {1, ... , m }, and its components are given by r =
(r(1), ... , r(m)).
Note that the notation Pol stands for polymorphisms, not for polyno-
mials! The subscript A may be omitted if A is clear from the context.
The notion of weak automorphism applies here to relational systems
and differs from the weak automorphisms for algebras introduced by
A. Goetz ([Goe66]) and investigated in many papers of K. Glazek
(e.g. [Gla97]).
according to
cp : ~(A) ---+ ~(B), 1/J : ~(B) ---+ ~(A) induced by a binary relation
I~ Ax B via
2.2. With the above definitions in 2.1 , the (strong) invariance relation
[> ( cf. 1.2) gives rise to the following Galois connections:
In order to include results for infinite sets A we still need some more
notions and notations.
2.4. Relational clones and local closures. For b= (c1 , . .. , em) E
Em and a mapping f E A B let
LocF := n00
m =l
m-LocF ,
LOCF := n00
m=l
m-LOCF.
With these notions we can state the following theorem which ex-
tends 2.3 to infinite sets A.
We start with the approach (A) which was already described in [Pos80a,
15.1].
For finite A the local operators can be omitted and [.]Rc can be replaced
by [.]RA· ForE = Op(A) orR = Rel(A) one can choose R 0 = 0 or
Fo = 0.
Proof. The result immediately follows from Theorem 2.5 and E n
PolQ = PolQ 0 n PolQ = Pol(Q 0 u Q) , Rn Inv F = Inv F 0 n Inv F =
lnv(Fo U F). 0
(A, V denoting meet and join in the lattice LA) according to Theo-
rem 3.2 (where the local operators can be omitted since A in finite) ;
for infinite A one has to restrict to the lattice of locally closed clones.
Op(A)
GVH
•
'.: ·.
/ •G
Let E = AAk and let G be the clone of all term operations of an algebra
A = (A; (fi)iEI) from a class JC of algebras. The cls(E,a)-closed sets
H ~ AAk (monoids in case k = 1) can be equipped with the algebraic
structure inherited from A. They were investigated in [JakMP03] as
so-called operation JC-algebras (transformation JC-algebras for k = 1)
and generalize the concept of near-rings.
In particular cases the Galois closures may be characterized more
intrinsically. Note, e.g. , that the Galois connections End- Inv and
wAut- Inv coincide with EPol- Inv forE= Tr(A) and E = Sym(A),
respectively (and trivial R = Rel(A)).
As a further example we mention the following characterization theo-
rem where the arity of operations or relations will be restricted (E =
Op(m)(A) orR= Rel(m)(A)).
Thus, e.g., the so-called bicentralizer Pol Pol F ofF means Pol(Pol F•)•
(with p• := {r I f E F} for a set F of operations) . Note that e.g.
242 R. Poschel
c• = Sym(At n [Q]Rc
L = s,p(A) n [Q]Rc
C = Eq(A) n [Q]Rc
Now let us consider further Galois connections from the points of view
(B) and (C) mentioned at the end of Section 2.
Concerning (B) we mention here some generalizations of the opera-
tions under consideration while the other side of the Galois connection
246 R. Poschel
[
Galois connection
Nota- rela- dosed opera-
Closure closed
tion tiona} system tiona} system
I for fimte base set A:
slnv - Aut (cf. 2.3 and Tab. 1)
(1) Lop A (:3, /\, V, •, =) [Q]KA Krasner alge- group of per-
bra (cf. 1.5, mutations
1.6)
to be continued on next page
248 R. Peschel
Galois connection
Closure closed rela- closed opera-
tional system tional system
Table 2, continued from previous page
Inv- End (cf. 2.3 and Tab. 1)
(2) LopA(3, 1\, V, =) [Q]wKA weak Kras- monoid of
ner algebra unary func-
(cf. 1.5, 1.6) tions
Inv- Pol (cf. 2.3 and Tab. 1)
(3) LopA(3, 1\, =) [Q]RA relational alge- clone of fini-
bra (cf. 1.5, tary functions
1.6)
Inv- pPol
(4) LopA(/\,=) weak system down-closed
with identity clone of fini-
tary partial
functions
Inv- mPol
(5) Lop A(/\) weak system of down-closed
relations clone of
finitary multi-
functions
slnv- sEnd (sbmEnd, resp.)
(6) Special mo-
noid of unary
functions (cf.
LopA(::l,/\,V,---,) [Q]BSP BSP (cf. 4.2) [BorPS, 7.9])
(6') (down-closed
involuted mo-
noid of bitotal
multifunc-
tions, resp.)
to be continued on next page
Operations and Relations 249
Galois connection
Closure closed rela- closed opera-
tional system tional system
Table 2, continued from previous page
slnv - spmEnd
(7) LopA(A,V,--, , =) [Q)BSI BSI (cf. 4.2) down-closed
involuted
monoid of
pp-multifunc-
tions (partial
permutations)
slnv -smEnd
(8) LopA(A,V,•) [Q]ss BS (cf. 4.2) down-closed
involuted mo-
noid of unary
multifunctions
I for arbitrary base set A:
slnv- Aut (cf. 2.5 and Tab. 1)
(9) (KC) = [Q]Kc Krasner clone locally closed
(WKC)&( --,)&(sS) (cf. 2.4) group of per-
mutations
Inv- wAut (cf. 2.5 and Tab. 1)
(10) (PKC) = [Q)PKC Pre-Krasner locally closed
(WKC)&(v)&(sS) clone (cf. 2.4) monoid of per-
mutations
lnv- sur-End
(11) (WKC)&(sS) InvH for sets locally closed
H of surjec- monoid of sur-
tive unary jective unary
functions functions
Inv - inb-End
(12) (WKC)&( --,) InvH for lo- locally closed
cally invertible locally invert-
monoids H ible monoid
of unary
functions
to be continued on next page
250 R. Poschel
Galois connection
Closure closed rela- closed opera-
tional system tional system
Table 2, continued from previous page
Inv - inj-End
(13) (WKC)&(v) InvH for locally closed
monoids H monoid of
of injective injective unary
functions functions
Inv - End (cf. 2.5 and Tab. 1)
(14) (WKC) = [Q]wKc weak Krasner locally closed
(RC)&(1-LOC) clone (cf. 2.4) monoid of
unary func-
tions
Inv - Pol (cf. 2.5 and Tab. 1)
(15) (RC) = [Q] Rc relational locally closed
(S)&(LOC) clone (cf. 2.4) clone of fini-
tary functions
References
[G~a97] K. G~azek. A cert ain Galois connect ion and weak automor-
phisms. Acta Univ. Patacki. Olomouc, Fac. rer. nat. , Mathe-
matica, 36: 15- 26, 1997.
[Ros83] I.G. Rosenberg. The Galois theory for partial clones. In R.S.
Freese and O.C. Garcia, editors, Universal Algebra and Lattice
Theory, volume 1004 of Lecture Notes in Math ., pages 257-
272. Springer-Verlag, 1983. (Proceedings Puebla 1982) .
Author's address:
Reinhard Poschel
Institut fur Algebra
TU Dresden
D - 01062 Dresden
GERMANY
e-mail: poeschel@math.tu-dresden.de
Galois Connections and Polynomial
Completeness
K. Kaarli*
Abstract
The aim of this paper is to emphasize the importance of the Galois theo-
retic approach in the study of polynomial completeness problems. We show
that reasoning in terms of Galois connections can be used for describing
(local) polynomial functions , for classifying and introducing new types of
polynomial completeness properties, etc. Special attention is paid to al-
gebras with a majority term, in which case the local term functions of an
algebra A are determined by the subuniverses of A 2 .
AMS Math ematics Subject Classification: 08A40, 06A15.
Key words: Galois correspondence, Polynomial completeness, Primality,
Order functional completeness, Endoprimality.
1 Introduction
on A. We also use symbols Fn(A) and Rn(A) for denoting the sets
of all n-ary functions and relations, respectively, on A. Thus, every
f E Fn(A) is a function from An to A and every r E Rn(A) is a
subset of An. Note that we do not require that a function f E Fn(A)
be essentially n-ary. IfF is any subset of F(A) then its n-ary part is
Fn = F n Fn(A) . The n-ary part of R ~ R(A) is defined similarly.
Our Galois connection is generated by the fundamental binary relation
"preserves" between F(A) and R(A) which we describe now. Let
f E Fn(A) and r E Rm(A). We say that f preserves r if for every
m x n matrix (aij) with all its rows in r , we have:
Instead of saying "f preserves r" one often says: "r is !-invariant" or
"f respects r" or "r supports f" or (especially if r is an equivalence
relation) "f is r-compatible".
The context (F(A), R(A) , preserves) generates the Galois connection
between the ordered sets (p(F(A)) , ~)and (p(R(A)) , ~) in the usual
way (say, as in formal concept analysis) . This connection is established
by the mappings:
and
F(!cp = LocTerm A
Theorem 4.2. ([16], Theorem 2.10) Let A be a finite set. Assume that
a subset R ~ Rn(A) contains tl~ and An, and is closed with respect to
the operations n, Cn, Pa and pa- l for every mapping a. If R ep contains
an (n + 1)-ary near-unanimity function , then R ep(! n Rn(A) = R.
saying that the local polynomial functions of L are precisely its order
preserving functions.
In the finite case the necessity part of Theorem 5.2 can be easily
derived from Theorem 5.1 and Corollary 4.3. Suppose that L is a
finite order functionally complete lattice. Then {~} cp = PolL which
implies
Now Corollary 4.3 implies that the order relation ~ generates the
algebra S2 (L). However, it is easy to see that the subalgebra of R2 (L)
generated by ~ has the universe {~ , ;::::: , .6. 2 , L 2 }. In particular, L has
no nontrivial tolerance relation.
A similar way of reasoning works also in the case of order affine com-
pleteness defined by the equality (Con LU{ ~} )'P = PolL . If we assume
that L is finite and apply to this equality the mapping (! then Corol-
lary 4.3 implies that L is order affine complete iff the algebra 5 2 (L)
is generated by the congruences and the order relation of L. On the
other hand it follows from Theorem 5.1 that the algebra S2 (L) is gen-
erated by the tolerances and the order relation of L. Consequently we
have the following result.
Theorem 5.3. A finite lattice L is order affine complete iff all toler-
ances of L are contained in the subalgebra of S2 (L) generated by the
congruences and th e order relation of L .
G. Gratzer ([7]) proved that all Boolean algebras are affine complete
and then characterized affine complete bounded distributive lattices
([8]). He proved, in particular, that every bounded distributive lattice
L is order affine complete. This result was generalized to arbitrary
distributive lattices by D. Dorninger and D. Eigenthaler ([6]). In the
language of our Galois connection their result reads as follows.
x" ~ x, (x 1\ x 1 ) V y V y 1 ~ y V y 1 •
It is well known that the variety of Kleene algebras is generated by
the 3-element Kleene chain K 3 . (Obviously there is only one way to
define a unary operation 1 on the 3-element lattice so that the result is a
Kleene algebra.) Therefore every Kleene algebra is a subdirect product
of copies of K 3 and its 2-element subalgebra K 2 with universe {0, 1},
which in fact is the 2-element Boolean algebra B 2 . Trying to find
an analog of Theorem 6.1, we first studied the diagonal subuniverses
of K 3 2 . It turned out that the algebra S2 (K 3 ) is generated by the
so-called uncertainty order
It turned out that in the case of Stone algebras the role of ::; in (2)
and ~ in (3) is played by the relation
7 Endoprimal algebras
References
Author's address:
Institute of Pure Mathematics
University of Tartu
50090 Tartu
Estonia
e-mail: george_janelidze@hotmail.com
Q-lndependence and Weak
Automorphisms
K. Glazek, 5. Niwczyk
Abstract
The aim of this survey is a presentation of two kinds of Galois connections,
which appear in Universal Algebra but are not well known. They are related
to the notions of general independence and of weak automorphism. There
are still interesting open problems from these areas.
AMS Mathematics Subject Classification: 06A15, 08B20, 08A40, 08A35,
08A30, 03B50, 20B 25, 20B21.
Key words: General Galois connection, Formal context, Marczewski inde-
pendence, Independences with respect to a family of mappings, Weak endo-
morphism, Weak automorphism, G-clone.
1 Introduction
2 Preliminaries
Let A be nonempty set and ((}n) (A) , JR(n) (A) the set of all n-ary
operations and the set of all n-ary relations of A , respectively (for
00
any positive integer n) . Let us put O(A) = U ((}n) (A) and JR(A)
n=l
00
The first Galois connection we shall describe uses the concept of in-
dependence. Let 2l = (A ; JF) be an algebra with a carrier A and a
set lF of fundamental operations. A nonempty set I ~ A is called
M -independent (or independent in the sense of Marczewski; see [35],
[36] and [9]) if for any finite system a1, ... , an E I of different elements
and for any pair j, g E T(n) (2l) of n-ary term operations the equality
j(a1, ... ,an) = g(a 1, ... ,an) implies f =gin A. We also assume (unlike
the assumption in [35]) that the empty set is M-independent. This
notion is a special case of the notion of independence with respect to
a set of mappings, to be considered in Section 3.
Now we introduce the necessary background for the second Galois con-
nection we shall consider, using weak automorphisms. For an algebra
2l = (A; JF) letT be a mapping from A into A. Consider the following
two conditions:
(a) For every f E 'I'(2l) (say: n-ary) there exists g E 'I'(2l) such that
(*) (\fa1 , ... , an E A) (T (! (a1, ... , an)) = g (T (a1), ... , T (an))).
One can verify that if T is " onto" , then g is uniquely determined (see
[19]).
(b) For every g E 'I'(2l) (say: n-ary) there exists f E 'I'(2l) such that
the equality (*) holds.
a('I'(2t)) = 'I'(2t)
holds, then a is said to be a weak automorphism of the algebra 2t.
It is worth adding, that - in the definition of a weak automorphism
- it is not enough to assume the inclusion a('I'(2t)) ~ 'I'(2t) (in this
case a is a semi-weak endomorphism with injective ol We denote by
Aut (2t) and W Aut (2t) the groups of all automorphisms and all weak
automorphisms of the algebra 2t, respectively. One can verify that
Aut (2t) is a normal subgroup of the group W Aut (2t) (see [48], [39]).
('1/p E M) [0 e p].
282 K . Gtazek, St. Niwczyk
Now, the dually adjoint operators forming our Galois connection are
defined as follows:
M 2Q f-t I( Q) = {X ~ A I (Vp E Q) [X [J p]} '
2A 2 J f-t Q(J) = {p EM I (VX E J) [X [J p]}.
Let us define Galois closure operators by the equalities:
v(J) = i(Q(J)),
6(Q) = Q(i(Q)).
It is known (also from (9]) that the set D(2l) of all maximal sets
of mappings with set-theoretic join and meet operations, and with
complementation defined by
(a) Q' = (M \ Q) U H ,
is a complete atomic Boolean algebra.
In a context J these families (Q and J) are determined by the closure
operators 6 and v.
(6) ifthe set I(Q) is hereditary 1 , then the set i ((~(Q))') is of finite
character2 .
From statement (5), one can easily conclude that the converse of im-
plication (6) is not true.
The lattice J(2t) of all v-closed sets, with set-theoretic join and meet
operations and complementation defined by (/3), is dually isomorphic
to D(2t).
For any subset T ~ A, T tf. Ind(M), we have:
(8) the sets (M \AT) U Hand P \ {T} are co-atoms of the lattices
J(Qt) and Q(Qt) respectively.
One can construct (in a rather artificial way, see [9]) a set Q ~ M of
mappings such that
(!) t-Ind<J. = Ind<J.(Q) ,
for any algebra Qt. The following problem (see [10], Problem 7.5) seems
to be interesting and still open:
Note some simple properties of this mappings (see (17], (18]) , namely:
(v) if lB\i E F(G) (for i E J), then / U lB\i) E F(G) and more
\tEl
generally F( G) is a sublattice of the lattice of all clones over A,
Define the operators V : 25 A ---+ 25 A and 6. : 2.c ---+ 2.c in the following
way:
v(G) = G(F(G)),
6.(F) = F(G(F)).
286 K . Gtazek, St. Niwczyk
The set 11' = lF U lE is a clone and 'f E F( G) iff B is invariant under all
permutations from G:::; SA. Then one can observe that if the subgroup
G is maximal with respect to inclusion, having the set B as a union
oforbits, then v(G) =G.
Let E be the identity permutation on set A . Using this example for
A = {0, 1, 2} we can easily show that {c, (01)} , {c, (12)} and {c, (02)}
3 4 see "Added in proof" at the end of t his pa per.
Q-lndependence and Weak Automorphisms 287
((!(xu , ... , XIm) , J (x21, ... , X2m), ... , f (xnl, ... , Xnm)) E f!)] .
These operators Pol and Inv form the Galois connection mentioned
above (see [2], [42] and [46]); and for each lF ~ (())(A) , Pol (Inv (JF)) =
Lac ( (lF)) where
Loc(lF) = {f E (())(n) (A) I n 2: 1, ('If finiteB ~ An)(3 g E lF)[fls =
9ls]}
is the so-called local closure of the set IF (see [46]). If the set A is finite
then the Galois -closed sets of operations are exactly the clones.
For a permutation a E SA and a relation{! E JR(n) (A) let
a
It is known ([24]) that for§ ~ lR (A), (Pol(§)) = Pol (a(§)) . If the
permutation a maps the set §onto itself, then so does a. If the set of
288 K. Gtazek, St. Niwczyk
1r
1 2 ) ts
= ( 01 2 . a b"mary re1atwn
. m. wh"tch e1ements are wntten
. as
1
columns) onto itself, is the identity E. Indeed , let f be an operation of
one variable which preserves the relation 1r , and let f (0) = 1. Then we
must have f (1) = 2 and f (2) = 1. If a E S3, then let g =a(!) , i.e.
g (x ) =a(! (a- 1 (x ))). If a= (01) , then g (0) = 2 and g (1) = 0, and
thus g does not preserve the relation 1r. Analogously we can show that
the only permutation a E S3 , for which g preserves 1r , is the identity.
(c) T e B {::} T fulfills the condition (a) for the algebra (A; B) (see
Preliminaries) ;
fi (xu,.:... , XIm) )
I.e. ( E [!.
fn (xn1 , · · ·, Xnm)
E[! E[!
Then
(! ,g) E Q;, iffa(f(xl, ... ,xn)) =g(a(xi), ... ,a(xn)),
which means that (f) =g. a
Such a situation can be generalized in the following way.
290 K. Gtazek, St. Niwczyk
Added in proof:
The authors obtained an information from Agnes Szendrei that the
answer to question A (and for two its equivalent forms, namely ques-
tions B and C) is NO. T he answer is finally due to S. Marchenkov
([34]) and it is based on the papers [29], [30], [32], [33] (see also [51]
in this volume).
The authors would like to thank A. Szendrei for this important infor-
mation.
References
[1] G. Birkhoff, Lattice Th eory (2nd ed.). Arner. Math. Soc., New
York 1948 (cf. also the 1st ed. from 1940, and the 3rd ed., Provi-
dence, RI, 1967).
[2] V.G. Bodnarcuk, L.A. Kaluznin, V.N. Kotov, and B.A. Romov,
Q-lndependence and Weak Automorphisms 291
[3] P.M. Cohn, Universal Algebra (2nd ed.) . D. Reidel Publ. Co.,
Dordrecht 1981.
[10] K. Glazek, Some old and new problems in the independence the-
ory. Colloq. Math. 42 (1979), 127-189.
[24] V.V. Gorlov and R. Poschel, Clones closed with respect to permu-
tation groups or transformation semigroups. Beitriige zur Algebra
und Geometrie 39 (1998), 128-204.
Authors' addresses:
K. Glazek, St. Niwczyk ,
Institute of Mathematics,
Technical University of Zielona G6ra,
ul. Pog6rna 50 ,
65-246 Zielona G6ra, Poland,
e-mail: k.glazek@im.pz.zgora.pl
s.ni wczy k@im. pz.zgora.pl
A Survey of Clones Closed Under
Conjugation *
/
A. Szendrei
Abstract
1 Introduction
*This material is based upon work supported by the Hungarian National Foun-
dation for Scientific Research (OTKA) grants no. T 026243, T 034175, T 37877.
297
K. Denecke et at. (eds.), Galois Connections and Applications, 297-343.
© 2004 Kluwer Academic Publishers.
298 A. Szendrei
will denote the algebra that arises from A by adding all constants as
fundamental operations. The clone of A c , that is, the clone generated
by F and all constants, is called the clone of polynomial operations of
A , and is denoted by Pol(A). For n ~ 1, Clon(A) and Poln(A) will
denote the set of n-ary term operations, and the set of n-ary polyno-
mial operations of A , respectively. A finite algebra A is called primal
if Clo( A) is the clone of all operations on A , and functionally com-
plete if A c is primal. We will call A a projection algebra if Clo( A) is
the clone of projections. Two algebras are said to be term equivalent
if they have the same clones, and they are said to be polynomially
equivalent if they have the same clones of polynomial operations.
An operation f on A is idempotent if it satisfies the identity f(x, ... , x)
= x . An algebra A is idempotent if all fundamental operations (and
hence all term operations) of A are idempotent. A clone <t is idempo-
tent if all operations in <tare idempotent. A ternary operation f is a
Mal'tsev operation if it satisfies the identities f(x , y , y) = f(y , y, x) =
x; f is a minority operation if it satisfies the identities f(x , y , y) =
f(y , x , y) = f(y, y , x ) = x ; and f is a majority operation if it satisfies
the identities f(x , y , y) = f(y , x , y) = f(y , y , x ) = y.
We will use the notation 'TA. , CA , SA , and AA for the full transformation
monoid, its subsemigroup of all constants, the symmetric group, and
the alternating group on A , respectively. For IAI = 4, VA will denote
the Klein group on A.
Let --y E SA. For an n-ary operation f on A the conjugate of f by --y is
the operation
clone of
[A, v]
[0, 1]
clone of projections
From now on we will assume that A is a finite set with at least three
elements, and A is the underlying set of all algebras and clones consid-
302 A. Szendrei
The same argument that proves that clones on a finite set form an
atomic and dually atomic, algebraic and dually algebraic lattice, also
proves that G-closed clones form an atomic and dually atomic, alge-
braic and dually algebraic lattice for all G. In fact, the lattice of G-
closed clones is a complete sublattice of the lattice of H-closed clones
whenever H ~ G ~ SA, and in all these lattices the smallest element
is the clone of projections, and the largest element is the clone of all
operations. 3 One cannot expect that the lattice of G-closed clones is
much simpler than the lattice of all clones, unless the permutation
group G is fairly large.
Next we summarize the notions and basic facts about permutation
groups that we will need in this survey. A permutation group G ~ SA
is called primitive if the unary algebra (A; G) is simple, and IGI > 1
when IAI = 2. For 1 < k < IAI , G is said to be k-transitive if for
any two lists b1 , ... , bk and c1 , ... , ck of pairwise distinct elements of
A there exists "( E G such that ci = "f(bi) for all i; G is said to
be k-homogeneous if for any two k-element subsets B, C of A there
exists 'Y E G such that C = 1(B). A !-transitive (or equivalently,
!-homogeneous) group is briefly called transitive. Clearly, primitive
permutation groups are transitive, k-transitive permutation groups
are k-homogeneous, and k-homogeneous permutation groups are also
(IAI - k)-homogeneous. It is also easy to see that 2-homogeneous
permutation groups are primitive.
The two most well known infinite families of 2-transitive groups are
the affine linear groups and the projective linear groups. Let K A be
a finite vector space with underlying set A. The automorphism group
of K A is the general linear group G L(K A) , and its subgroup consisting
of all automorphisms with determinant 1 is the special linear group
SL(KA). The affine general linear group AGL(KA) is the subgroup of
SA generated by GL(KA) and by the group of translations TR(KA) =
{x+a: a E A}; AGL(KA) is a 2-transitive group on A for every vector
space KA. We note that the permutation group AGL(KA) determines
(i) U is SA -closed;
(ii) there is a filter F of kernel types on A such that the members of
U are exactly the transformations whose kernel types belong to
F.
2.8 Example. For 2 < m < IAI let 9\n denote the clone consisting
of the projections and all operations whose range has size at most m.
An important subclone of 9\2 is the following clone 113: it consists of
the projections and all operations of the form
(n 2: 1) (2.1)
where <p 1 , ... , 'Pn are mappings A ---7 {0, 1}, +is addition modulo 2,
and cp is any mapping {0, 1} ---7 A. If IAI is even, then the projections
and all operations of the form (2.1) where the kernel of each 'Pi (i =
1, ... , n) has two even size blocks form a proper subclone in 113; this
clone will be denoted by 113*. It is easy to check that all the clones
9\n, 113, and 113* are SA-closed.
It is well known [3, 22, 37) that the clones containing 74 form a chain
whose members are exactly the clones [74), 113 U [74), and 9\n U [74)
(m = 2, ... , IAI). The coatom 9\IAI-I U [74) of this chain is called
the Slupecki clone. The description of all clones containing 74 was ex-
tended in [12] to all clones containing SA. Since all clones that contain
SA are SA-closed, these results will be covered by the description of
SA-closed clones discussed in Section 4.
2.9 Example. Another rich class of SA-closed clones is the class con-
sisting of the clones Clo(A) where A is a homogeneous algebra, that
is, A has S A as its automorphism group. These clones were described
in [6] and (23). The description was extended in [25) to the case when
the automorphism group of A is AA (IAI > 3); interestingly, these
clones are also SA-closed.
Clones Closed Under Conjugation 307
z if x = y, X if X= y ,
t(x, y, z) = { x d(x, y , z) = { z
itx=/=y, if X =/= y,
s(x, y,z) = G if X= y,
if X= z,
otherwise,
and
3.1 Theorem. [38] Let A be a finite algebra with at least three ele-
ments. If the weak automorphism group of A is 2-homogeneous, then
one of the following conditions holds for A:
clone of projections
(a) A is quasiprimal;
(b) A is affine;
(c) A is isomorphic to an algebra term equivalent to U (m] for some
2-element unary algebra U and some integer m 2: 1;
ations only, and has a different meaning than in the definition of an idempotent
operation, as introduced at the beginning of Section 2.
Clones Closed Under Conjugation 315
4 SA -closed clones
In this section we give a complete description of the SA-closed clones
on a finite set A. The case IAI = 2 was discussed in Example 2.1,
so we will assume throughout this section that A has at least three
elements. The description of SA-closed clones for IAI = 3 was first
published in [13]. As regards the case IAI ~ 4, in [14] Hoa found the
maximal SA-closed clones and described all SA-closed clones that are
contained in the Slupecki clone; in [15] he announced the completion
of the description of all SA-closed clones. Later Marchenkov [27, 28]
used a purely relational approach to describe all SA-closed clones that
are not contained in the Slupecki clone. The description we present
318 A. Szendrei
4.1 Theorem. [14] Let A be a finite set with IAI :2: 3. The SA-closed
clones It on A that satisfy condition (S) are the following:
(2)* 113* U [T] if IAI is even, where T is as in (1) and the kernel type
of each nonsurjective member ofT consists of even numbers;
It is easy to see that for two SA-closed clones of type (S) which are
given in this unique form as XU (T] and X' U [T'] (X = 0, Q5 , Q5* , or
9\m) we have XU (T] ~X' U [T'] if and only if X~ X' and T ~ T'.
Sketch of proof of Theorem 4.1. ([20]) It is easy to see that all clones
listed in the theorem are SA-closed and satisfy condition (S). Con-
versely, let ~ be an SA-closed clone satisfying condition (S) , and let
A = (A;~). Since ct is SA-closed, so is the transformation monoid
T = ct(l). Therefore Corollary 2. 7 applies, and shows in particular
that T contains all constants. Hence ct = Pol(A) and T = Pol 1 (A).
If ct is an essentially unary clone, then there is nothing more to prove
to see that (1) holds.
From now on we will assume that ct is not essentially unary. Let r
denote the maximum of the cardinalities of ranges of operations p E ct
that depend on more than one variable. Since ct is contained in the
SJupecki clone and has an operation that depends on more than one
variable we have 2 < r < IAI. We know from condition (S) that A is
simple. Corollary 2. 7 implies that for some positive integers k1 and k2 ,
T = Poh (A) contains all transformations of kernel type ( k1 , k 2 ). Thus
the minimal idempotent polynomials of A have 2-element ranges, and
every 2-element subset of A is a trace. Remark 3.5 implies that A is
of type 1, 2, or 3.
Now let us fix a trace N of A , and following [19] let us call a set
of the form M = f(N, N, ... , N) with f E Pol(A) = ct a multitrace
of A. Furthermore, let m denote the size of the largest multitrace
in A . It is easy to see that m < r. Indeed, if m = 2 then this is
320 A. Szendrei
f(MI , M2 , ... , Mn) = f(JI(N , ... , N), ... , fn(N, ... , N))
(1) .71.1 = e (A) for some idempotent unary polynomial e E Pob (A),
and
An fin (Mk)n ~ M .
Applying properties (1) and (3) to ida E IT (B ~A) one can see that
(4.5) if A has a proper subalgebra B of size IBI = k, then every subset
of A of size < k supports a subalgebra of A .
324 A. Szendrei
Moreover,
4.7 Theorem. [20] (cf. [15, 28]) Let A be a finite set with IAI ;::: 3,
and let A = (A; It) where It is an SA -closed clone on A that satisfies
condition (I). Then one of the following conditions holds for A:
(Q) A is quasiprimal;
4.8 Lemma. Let A be a finite set with IAI 2 3 and let IT be a family
of bijections between subsets of A such that IT satisfies conditions (4.4)
(0)-(3). Then IT is one of the following families:
(i) ]k,l = U(Bij 8 (A) : 0 < S < k) U {idE : B ~ A, IBI < l} U {idA}
for some integers k, l with 1 < k < l < IAI;
(ii) (a) ]3,! U U(VB : B ~ A, IBI = 4) for some l with 3 < l < IAI,
(b) ]k,luU(AB: B ~A, IBI = k+1) for some k,l with 2 < k <
l < IAI,
(c) ]k,l U U(SB : B ~A, IBI = k + 1) for some k, l with 1 < k <
l < IAI;
(iii) ]IAI/2- l,l U BijfAI/ 2(A) for some l with IAI/2 < l < IAI, if IAI is
even;
326 A. Szendrei
(v) (a) .JTk,k UN for some k :::: 1 with IA I - 3 < k < IA I and f or
some nontrivial normal subgroup N of SA such that k :::: IAI- 2
if N =SA,
:::~
...
.. .. ..
The next theorem will show that for every family TI of bijections from
Lemma 4.8 there exists an SA-closed clone Q: that satisfies conditions
(I) and TI = Iso( (A; <r)). An explicit list of all such clones is also given
in the theorem. We will use the following notation. If TI = .Jf k,l U ... is
one of the families listed in Lemma 4.8, then we define D(TI) to be the
set of all operations on A that preserve all members of TI (as binary
relations). Clearly, D(TI) is the clone of an idempotent quasiprimal
algebra. Furthermore, let
1' 2 (TI) = {J E D(TI) : JIB E Clo( (B; 1\, v)) for all 2-element
subsets B of A}
= {J E D(TI) : J preserves all reflexive crosses on
2-element subsets of A},
1'r(TI) = {J E D(TI) : J preserves all r x 2 crosses} (3 < r < IAI),
~(TI) = {J E D(TI) : JIB E Clo( (B; x + y + z)) for all
2-element subsets B of A},
<Er(TI) = {J E D(TI): JIB is a projection for all r-element
subsets B of A} (2 < r < IAI).
4.9 Theorem. [15, 28, 20] Let A be a finite set with IAI 2': 3, and
let ll = ]k,l U ... be a family of bijections from Lemma 4 .8. The SA-
closed clones <t that satisfy condition (I) and have the property that
ll = Iso( (A; <!:)) are the following.
(1) If k 2': 2, then there are exactly k + l + 1 such clones <t, namely
O(ll), ~r(ll) (r = 2, . .. , l orr = IAI), ~(ll), and <Es(ll) (s =
2, ... ' k).
In Figures 3-5 the four cases for ll that are distinguished in Theo-
rem 4.9 are indicated as follows . The families ll with k 2': 2 are those
that appear in the triangular region. The families ll with l > k = 1
are inside the rectangular region, and the two subclasses distinguished
by the property "Ss ~ ll for all 2-element subsets B of A" and by the
complementary property "ll n Ss ={ids} for all 2-element subsets B
of A" are separated by a dashed line. The remaining families ll are
those with parameters k = l = 1. Figure 6 shows the clones listed in
Theorem 4.9 for four typical families ll = llj (j = 1, 2, 3, 4). For each j
the family ll = llj represents the case when ll satisfies the assumptions
of part (j) of Theorem 4.9, and the corresponding clones are ordered
by inclusion.
The fact that every SA-closed clone satisfying condition (I) is one
of the clones listed in Theorem 4.9 is immediate from Theorem 4.7.
What is new in Theorem 4.9 is the statement that the clones X(ll)
(X= 0, ~ ' ~n or <Es) appearing in the theorem are pairwise distinct,
and that for every such clone we have ll = Iso( (A; X(ll))). Both of
Clones Closed Under Conjugation 331
Fig. 6:
332 A. Szendrei
Therefore, from now on, we assume that A has a binary reduced com-
patible relation. Using the existence of such a relation {! and the
constructions described at the beginning of the proof along with some
of the properties of A established earlier, one can prove the following
preparatory claims on subalgebras, compatible crosses, and internal
isomorphisms of A.
(4.14) subA ~ 2.
(4.15) If B <:;;; A is not simple, then B is a projection algebra.
334 A. Szendrei
(4.16) croA 2: 2.
(4.17) If r;;[b, B; c, C] with B = {b, b'} and C = {c, c'} is a 2 x 2 com-
patible cross of A, then the bijection i: B ---+ C, b f-----t c', b' f-----t c
belongs to Iso( A).
(4.18) Every 2-element subset of A is a subalgebra, and either every
2-element subalgebra B of A is term equivalent to the unique
lattice on B, or every 2-element subalgebra B of A is term
equivalent to the unique majority algebra on B, or every 2-
element subalgebra B of A is a projection algebra (cf. Fig-
ure 1).
(4.19) If croA 2: 3, then Iso(A) is 2-complete.
(4.20) If Iso(A) is 2-complete and A has a compatible r x 2 cross,
then all r x 2 crosses are compatible relations of A.
For the proof of (4.22) let B = pr 1 {!, C = pr2 {!, and r = croA. We can
assume without loss of generality that IBI 2: ICI. For any compatible
r x 2 cross K;[d, D; v, V] (dE C, V = { v, v'}) of A, {! o K;[d, D ; v, V] is
a compatible relation of A of the form
(4.24) If croA > 2 and the 2-element subalgebras of A are not projec-
tion algebras, then (D) holds.
(4.25) If croA > 2 and the 2-element subalgebras of A are projection
algebras, then (E) holds.
(4.26) (D) or (E) holds also if croA = 2.
compatible relations of A.
If r ~ 3 and the 2-element subalgebras of A are projection algebras,
then Theorem 4.11 and (4.22) yield that every reduced compatible
relation of A has size < r. All such relations are preserved by every
operation f that satisfies the conditions described in (E). Thus it fol-
lows immediately from (4.10) that f is a term operation of A. Finally,
if r = 2, then we know from Theorem 4.11 and (4.22) that every re-
duced compatible relation a of A has size < 2. It is not hard to prove
by induction on the arity n of a, and using (4.17), that for any indices
1 < i < j < n there exist internal isomorphisms '"ij: pri a --t prj a.
Therefore a arises from a compatible relation a' of the 2-element sub-
algebra B of A on B = pr1 a by applying the internal isomorphisms
t 12 , ... , t 1n in the 2nd, ... , n-th coordinates. Thus every operation f
that satisfies the condit ions described in (D) or (E), respectively, for
r = 2 preserves a. This holds for every reduced compatible relation
a, so we get from (4.10) that f is a term operation of A. D
of this section shows that there are very few possible candidates for
such a G. This theorem determines all groups G for which the number
of G-closed clones that contain all constants is finite.
(i) The lattice of G-closed clones that contain all constants is finite.
(ii) G satisfies the following combinatorial condition:
(iii) G is one of the following groups: SA, AA, AGL(1 , 5) (IAI = 5),
PSL(2, 5) (lA I = 6), PGL(2, 5) (IAI = 6), PGL(2, 7) (IAI = 8),
PGL(2, 8) (IAI = 9), PfL(2, 8) (IAI = 9) .
Outline of proof. To prove the implication (i)::::}(ii) we assume that
(ii) fails, and construct infinitely many G-closed clones that contain
all constants. To witness the failure of (ii) we fix an integer k (2 <
k < lA I), a k-element subset C of A , and a (k + 1)-element subset B =
Cu{O} of A so that '!'(C) =J- C' for every 1' E G and for every k-element
subset C' of B that contains 0. For notational simplicity let us assume
that C = {1, 2, ... , k }. Using these sets we construct an infinite se-
quence f2n (n = 2, 3, .... ) of relations and an infinite sequence fn (n =
3, 4, ... ) of operations on A as follows : f2n is the (n + k- 1)-ary relation
consisting of all tuples (x 1 , ... ,xn, y1 , ... , yk-l) E An+k-l such that
l{xl, ... ,Xn,Yl,···,Yk- dl < k+1 and if{xl , . . . ,Xn, Yl , ···,Yk- d =
'!'(C) for some ')' E G then I{x 1 , .. . , Xn} I 2: 2; f n is the n-ary opera-
tion on A such that fn(1 , ... , 1, 0, 1, ... , 1) = 1 (with 0 occurring in
the j-th position) for every j (1 < j < n) , fn(c , . .. , c) = c for all
c = 2, ... , k, and fn(x 1 , ... ,xn) = 0 for all remaining arguments. It is
not hard to check that
• every f2n is reflexive and satisfies 'Yf2n = f2n for all')' E G; therefore
the clone lt(f2n) consisting of all operations that preserve the
relation f2n is G-closed and contains all constants;
Clones Closed Under Conjugation 339
References
[13] Nguen Van Khoa [Nguen Van Hoa], On the structure of self-dual
closed classes of three-valued logic P 3 (Russian), Diskret. Mat. 4
(1992), no. 4, 82- 95.
[14] Nguen Van Khoa, Families of closed classes of k-valued logic that
are pr·eserved by all automorphisms (Russian), Diskret. Mat. 5
(1993) , no. 4, 87- 108.
[15] Nguen Van Khoa, Description of closed classes that are preserved
by all inner automorphisms of k-valued logic (Russian) , Dokl.
Akad. Nauk Belarusi 38 (1994), no. 3, 16- 19, 122.
[16] Nguen Van Khoa, On closed classes of k- valued logic that are self-
dual with respect to transitive groups (Russian), Diskret. Mat.
8 (1996), no. 1, 129--159; translation in: Discrete Math. Appl.
Clones Closed Under Conjugation 341
Author's address:
Agnes Szendrei
Bolyai Institute
University of Szeged
Aradi vertanuk t ere 1
H-6720 Szeged, Hungary
email: A. Szendrei @math.u-szeged. hu
Galois Connections for Partial
Algebras
P. Burmeister
Abstract
In connection with partial algebras one has many more relevant polarities
(i.e. Galois connections induced by binary relations) than in the case of
total algebras. On one side there are many different subsets of the set of
first order formulas, which one wants to use as a concept of identity in
some special context, and where one is interested in the closure operators
induced by restricting the validity of first order formulas to this special sub-
set. On the other hand the polarity induced by the reflection of formulas
by mappings allows us to keep track many interesting properties of homo-
morphisms between partial algebras, while others can be related to these
via factorization systems - which can be considered as special pairs of cor-
responding closed classes (in Formal Concept Analysis one would call such
pairs "formal concepts") of the polarity induced by the (unique) diagonal-
fill-in property on the class of all homomorphisms. - Moreover, having
an interesting set of properties of homomorphisms, the relation "a homo-
morphism has a property" can be used to apply the method of attribute
exploration from Formal Concept Analysis in order to elaborate a basis for
all implications among these properties and on the other hand a small but
"complete" set of counterexamples against all non-valid implications.
In this note we want to describe some' of these polarities or correspond-
ing pairs of interest in them, and we shall present them in the context of
many-sorted partial algebras, since this context seems to be less known.
Moreover, we want to give an example of an attribute exploration as men-
tioned above.
AMS Mathematics Subject Classification: 08A55, 03B10.
Key words: Partial algebra, Polarity, Formal context.
345
K. Denecke et al. (eds.), Galois Connections and Applications, 345-370.
© 2004 Kluwer Academic Publishers.
346 P. Burmeister
1 Introduction
algebras needed in this note; for more details cf. [B86J , [B93J or in the internet
Galois Connections for Partial Algebras 349
[BOO].
One often considers the pair (ry(w), u(w)) as the value of one single function
7
~ then mostly also denoted by 17, and one omits t he arity function T, which is
implicit in our ry, but we think that the above notation is more convenient.
350 P. Burmeister
11 Observe that, fort = t' , A f= (X; t ~ t)[v] still has the nontrivial meaning that
"t E dom v8 " , i.e. that t is interpreted w.r.t. v (or, in other words, v interprets t).
12 Note that, for an arbitrary subset B of A one defines the rela-
tive subalgebra lB := B of A with carrier B to be the partial algebra
(B, (wAn (B''I(w) X B,.(w)))wErJ
Galois Connections for Partial Algebras 353
13 Observe that all elements in any such a sequence a have to be of the same
sort, and a and b should be of the same sort, too.
14 See [BiOI].
354 P. Burmeister
(1) For every w E n, (a1, ... , a7 (w)) E M'(}(w) , and a E Mo ,a(w) one
has:
If wMo (a 1 , ... , aT(w)) =a, then
(a) Ia ~ Ia 1 n . . . n Iar<wl,
(b) 1ri(a) = wA., (1ri(a1), ... , 7ri(a7 (w))) for every i E Ia.
The ordered set (~(IK) , ::::;) always forms a complete lattice. One
has two mappings 1-L : M --7 ~(IK) - with J-L(m) := ( { m}.!. , {m }H)
(mE M)- and 1: G--+ ~(IK)- with ! (g):= ({g}t+, {g}t) (g E G)
- assigning to the attributes and objects their "generated formal con-
cepts". In line diagrams of concept lattices the name of the attribute
m is usually written a little above the circle representing the formal
concept J-L(m), and the name of the object g is usually written a little
below the circle representing the formal concept ! (g) (cf. Figure 2).
15 Cf. [GW99].
Galois Connections for Partial Algebras 355
3 Properties of homomorphisms
(iii) S) = { ( { xl, ... 'XT(w), y }; •WXl ... XT(w) e y) I X-t E y1)(w)(i) (1 :S;
i :S; T(w)) , y E Yu(w), and wE r2 }+<l.
16 Observe that we write {x 1 , .. . ,Xr(w),;t/} as abbreviation for S-sets (Xs)sES
with Xs = { z I (z = Xi and rJ(w)(i) = s and 1 ~ i ~ T(w)) or (z = ;t1 and
a(w) = s)} (for s E S).
356 P. Burmeister
Table 1
°
2 Cf. e.g. [B86], Remark 10.2.11 -observe that there and in other books and
papers the operators have a different notation than we have used in this note in
order to have a homogeneous notation. Very often one writes A(£) instead of [ t0 ,
and A0 P(M) instead of M.!-0 .
21 Observe that, what one often ·- and we here, too - calls a "mono-factor",
need not consist only of monomorphisms. As an example take the class Closed~ of
all closed homomorphisms. However, the factorization systems considered origi-
nally usually consisted of a class of epimorphisms as extent and a class of monomor-
phisms as intent. - Observe, too, that we have in the theory of partial algebras an
interesting factorization system (all final homomorphisms, all bijective homomor-
phisms ) , where the final homomorphisms between partial algebras - which form
the dual concept to initial homomorphisms in the sense of Bourbaki [Bou57] -
are exactly those homomorphisms, which fully induce the structure on the image
algebra, but they need not be surjective and therefore not epimorphic. Moreover,
the bijective homomorphisms are not defined by t he reflection of formulas.
Galois Connections for Partial Algebras 359
"epi-factor" "mono-factor"
(class of all full and surjective homomorphisms, Menor; )
(class of all TAigr;-extendable epimorphisms, Closedr: )
(Epir;= class of all epimorphisms, Monor:,closed )
(class of all surjective homomorphisms, Monor:,full )
(class of all final homomorphisms, cl. of all
biject. horns).
Table 2
Definition 4 Let
n
t- := (X; f\ ti ~ t~ =} t ~ t')
i= l
And we obtain
Q ~ U ({P} x T~ (var(P)) 2 )
PEPrem
to be any set of set theoretically encoded elementary implications of
the corresponding type. For P E Prem we define
With the above notation one has the following description of closed
sets of elementary implications of one of the three kinds of Prem:
Theorem 5 25
Let Prem E {Preme, Premece, Premqe}, and let Q s;;;; UPEPrem({P} x
TI'.(var(P)f) be any set representing elementary implications connected
with Prem.
(i) Q = lmpPrem(Mod(Q)).
(ii) Q has the following properties (11) through (14) for any
P, P' E Prem:
(11) suppQ(P) is a var(P)-generated relative subalgebra of
'.II'I'.(var(P)) - in particular one has suppQ(P) =
-!- Q(P).
(12) Q(P) is a closed congruence relation on supp Q(P).
(13) P s;;;; Q(P).
(14) For every homomorphism f : -!-P ~ supp Q(P') satis-
fying(! x f)(P) s;;;; Q(P'), there exists a homomorphic
extension fPP' : supp Q(P) ~ supp Q(P'), which satis-
fies (JPP' X fPP')(Q(P)) s;;;; Q(P').
25 The proof of this theorem for the homogeneous case can be found first -
formulated for QE-equations - in [ABN81] (and in another form in [AN83]). Later
it appeared in [B86] and, without proof, in [B93]. Yet in all three cases (Il)
contained an error, since we there refer to "'Q(P) rather than to suppQ(P), and
±Q(P) is trivially generated by var(P), i.e.-then (Il) does not contain any non-
trivial condition. We think that in this set theoretical form, and formulated for
heterogeneous partial algebras the theorem is formulated here for the first time.
364 P. Burmeister
Homl X X X X X
Hom2 X X X X X
Hom3 X X X X X
Hom4 X X X X
Hom5 X X X X X
Hom6 X X X X
Hom7 X X X X
Hom4
References
Author's address:
Peter Burmeister
FB4, AG1, Darmstadt University of Technology
SchloBgartenstraBe 7
D-64289 Darmstadt, Germany
email: burmeister@mathematik. tu-darmstadt.de
Complexity of Terms and the Galois
Connection ld-Mod
K. Denecke, 5. L. Wismath*
Abstract
A non-trivial identity s ~ t is normal when neither of the terms s and t is
a variable. Using several common measures of the complexity of a term,
this requires exactly that both s and t have complexity ::::: 1. We generalize
this definition to any integer k ::::: 1, by saying that a non-trivial identity
s ~ t is k-normal when both s and t have complexity ::::: k. A variety will
be called k-normal when all its non-trivial identities are k-normal. Using
results from the theory of Galois connections and complete sublattices, we
show that the collection of all k-normal varieties of a fixed type forms a
complete sublattice of the lattice of all varieties of the type. We also gen-
eralize to the k-normal case the results of Graczynska ([Gra]) and Melnik
([Mel]) describing normal varieties and the mapping taking any variety to
the least normal variety containing it.
AMS Classification: 08B05, 08A55.
Key words: Complexity, Normalization, Galois connection, Complete sub-
lattice.
1 Introduction
It is well known that these two maps form a Galois connection between
Alg(T) and W7 (X) 2 , induced by the relation of satisfaction between
algebras and identities. The corresponding complete lattices are the
lattice £(T) of all varieties of type T, and the lattice E(T) of all equa-
tional theories of type T.
Now we take P(T) to be any property of identities which is an equa-
tional theory, that is, any element P(T) E E(T). It follows from [DW]
that the map <p~ with .Ef--t .En P(T) is a kernel operator which pre-
serves both unions and intersections, and the mapping <pj, = J.L<p~&
= M od<p~I d is a closure operator on the lattice £(T), and preserves
joins. Moreover the collection of <pj,-closed varieties forms a complete
sublattice of£(T). This corresponds to the Galois connection induced
by the Galois-closed subrelation
Nt : L:--+ L: n Pk(T),
N;(: V--+ Mod(IdV n Pk(T)) .
Theorem 1.2. The map N;( : .C(T) --+ .C(T) defined by N;((V)
Mod(IdV n Pk(T)) is a join-preserving closure operator on .C(T), and
the class of all N ;(-closed varieties forms a complete sub lattice of the
lattice of all varieties of type T.
sublattices
Example 1.3. The medial variety of type (2) is defined by one identity
f(j(x, y), f(z, w)) ~ f(j(x, z), f(y, w)). Using the depth function as
our complexity measure, this identity has complexity of 2 on each side.
This means that V = Nt(V) = Nt(V) C Nf(V). The type (2) variety
V = SL of semilattices has Nt(V) = V =1- Nt(V) =1- Nt(V) .
2 k-Normalizations
The lattice of all normal varieties of a fixed type T , and the mapping
Nt taking any variety V to the least normal variety Nt(V) to contain
V, have been studied by Mel'nik ([Mel]) and Graczynska ([Gra]) . In
this section we show that some of their results can be extended to our
k-normal varieties and mappings N;(, fork :2: 2.
Lemma 2.1. Let k :2: 0. For any variety V, the variety N;((V) is the
smallest k-normal variety to contain V.
Now we are ready to prove our main theorem. Recall that for any
variety V, we denote by £(V) the subvariety lattice of V.
Proof: We know from Theorem 1.2 that the map Nf always preserves
joins. We now show that on subvarieties of V it also preserves meets.
We have
Nf(Ul 1\ U2) ModNf(Id(Ul 1\ U2))
ModNf(Con(IdU1 u IdU2))
ModCon[Nf(Con(IdUI)) U Nf(Con(IdU2))],
by Corollary 2.6
ModCon[Nf(IdUI) U Nf(IdU2)],
since I dUi is an equational theory
ModCon(IdNf(U1 ) U IdNf(U2)) ,
since IdNf(Ui) = Nf(IdUi)
Modld(Nf(UI) 1\ Nf(U2))
Nf(UI) 1\ Nf(U2)·
Thus Nf is a lattice homomorphism on £(V). For the injectivity,
let U1 and U2 be any subvarieties of V, and let e be a non-normality
witness for V. Then
Example 2.9. Let V be the type (2) variety Mad( {f(x, f(y, z)) ~
f(f(x, y),
z ), x ~ f(f(x, x), f(f(x, x), f(x, x))), f(x , y) ~ f(y, x)} ), and let the
complexity function c be the depth function. Since V satisfies identities
of varying depths, we have V C Nf(V) C Nf(V) C Nf(V), and in
particular V is not normal. However, by Lemma . { 2 the map N f has
Proof: We will show that W must also satisfy the identity e. Then us-
ing Lemma 2.4 and the fact that W ~ N;((V) means that IdN;((V) ~
IdW, we have
IdV = Con(IdN;((V) u {e}) ~ Con(IdWU {e}) ~ IdW,
and hence W C V.
To show that W satisfies e, we will show that it can be deduced from
the set N{(IdV) of identities along with some non-normal identity f
of W. If e = f this is obvious, so we assume that e =/::- f. We can write
f as x ~ p(x, ... , x) for some term p with complexity r ~ 1, and by
inflating if necessary we may assume that r > k . Now consider the
sequence
x ~ p(x, ... , x) ~ p(t(x , ... , x), ... , t(x , . . . , x)) ~ t(x , ... x).
The first identity is just f itself; the second one is a consequence of
e E I dV and has complexity on each side ~ r > k , and the third
identity is a consequence of f . This shows that we can deduce e, or
x ~ t(x, ... , x), using only identities from Nf(I dV) U {f}. These
identities are all in IdW, and hence W satisfies e. •
not normal, and hence not k-normal for any k ~ 1. We will fix k = 2,
and consider the varieties V C Nt(V) C Nf(V). Since both terms in
the associative law f(x , f(y , z )) ~ f(f(x, y) , z ) have depth 2, the va-
riety Nf(V) is still a variety of semigroups. We will follow the usual
convention of writing semigroup terms as words (with the binary op-
eration denoted by juxtaposition and brackets omitted}.
Now let W be the subvariety of Nf(V) defined by the set of identities
N .f (I dV) plus the one additional identity xi ~ xf. This additional
identity is a normal identity of V, and the term xi has depth 1, so
we have Nt(V) ~ W C Nf(V), and W is a normal variety. But it
t
is also true that N (V) is properly contained in W , since the normal
identity x 1 x 2 ~ xix 2 holds in Nt(V) but cannot be deduced from the
identities of W.
This example shows that it is possible to have a non-normal variety V
and a normal variety W with W c Nt"(V) but W neither k-normal nor
a subvariety of Nt_1 (V). Again this highlights the special properties
of non-normal identities. For any variety W with W ~ Nt(V), either
all identities of W are normal, or adding any one non-normal identity
to the set of all normal ones gives all the identities of V. At higher
levels, this no longer happens: our example shows that we can add
one non-2-normal identity to the 2-normal identities of V , without
obtaining all such non-2-normal identities.
As we remarked above, our proofs only apply in the situation of a non-
normal variety V, where we can use a non-normal identity to "inflate"
other identities. Another consequence of this is that we cannot carry
out any of our work at a higher level, that is for varieties V which are
normal but not k-normal for some k ~ 2. A non-k-normal identity
s ~ t can only be used to inflate terms in which an instance of s or t
occurs, not arbitrary terms. Consider as an example a type (2) normal
variety which satisfies an identity of the form f(x , x ) ~ f(x , f(x , x )).
There is no way to use this to inflate the term on the left of the identity
f(x, y) ~ f(f(x, y), f( x, y)). In this respect normality is a very strong
property.
3 Structural Theorems
Our proofs so far have focussed on identities satisfied in V and Nt(V),
to generalize the results of Graczyri.ska. A different approach was taken
Complexity of Terms and the Galois Connection ld-Mod 383
Lemma 3.5. Let k 2: 1, and let V = Mod(x ~ u(x, ... , x)) with c(u)
2: k. Let E be the set of identities constructed above. Then Nt(V) =
ModE.
The identities in r then make 'Pu the identity mapping on rlk(B), since
any element of this set has the form t 8 ( b1 , ... , bm) for some term t and
elements b1, ... , bm. •
~w.,.(x) are equational theories. Therefore E(~ui ) = ~ui and this gives
E(E(~) U U E(~ui)) = Nff(E(~ U U{ x ~ uj(x, · · · , x)}) U ~W.,. (X) ·
j EJ j EJ
The left hand side can be replaced by E(~ U U ~ui) U ~w.,.(x) , and
j EJ
this finishes the proof. •
The following example shows that without the assumption of Theorem
3.6 we will not get a basis for the k-normalization.
Example 3.7. We use type (2) and complexity equal to depth, and
since our varieties will all satisfy associativity we write terms as words.
Using k = 1 and the non-normal identity x ~ x 2 , the set ~ above
consists of the 4 identities
References
[ADP] Arworn, S., K. Denecke and R. Poschel, Closure Operators on
Complete Lattices, Ordered Algebraic Structures: Nanjing; Algebra,
Logic and Applications Series Volume 16, Gordon and Breach Science
Publishers, 2001 , 1 - 22.
[Mel] Mel'nik, I. I., Nilpotent shifts of varieties (in Russian) , Mat. Za-
metki 14, No. 5, 1973. English translation: Math. Notes 14, 1973,
962-966.
Authors' addresses:
Klaus Denecke
University of Potsdam
Institute of Mathematics
Am Neuen Palais
14415 Potsdam
Germany
e-mail: kdenecke@rz. uni-potsdam.de
Shelly Wismath
Dept.of Mathematics and CS
University of Lethbridge
Lethbridge, Ab.
Canada T1K-3M3
e-mail: wismaths@cs.uleth.ca
Iterated Galois Connections in
Arithmetic and Linguistics
J. Lambek
Abstract
Galois connections may be viewed as pairs of adjoint functors, specialized
from categories to partially ordered sets. We study situations that permit
iterations of such adjoints. While their occurrence in elementary number
theory is a curiosity, they play a crucial role in a new algebraic approach
to sentence structure in natural languages.
AMS classification: 18A40, 06A15,03B65.
Key words: Adjoint functors , Iteration of adjoint functors, Sentence struc-
ture in natural languages.
389
K. Denecke et al. (eds.), Galois Connections and Applications, 389-397.
© 2004 Kluwer Academic Publishers.
390 J. Lambek
then
f(x) +x::; x+y {::} x+y::; g(y) +y
{::} g(y)+y+l>x+y.
It follows immediately that the sets
2. Iterated adjoints.
In this case, (a) holds trivially and (b) holds if and only if {y E Nix ::;
g(y)} =/=- 0 for each x in N, that is, provided g is unbounded.
We note that then f = l will also be unbounded, since f(x) ::; b
would imply x::; g(b). Therefore, ge also has a left adjoint gee, and so
on.
In summary, if g : N----+ N has a left adjoint gf-, then it also has iterated
left adjoints gfe, ge.ef etc.
One way to construct these is to look at the corresponding subsets of
N:
The functions
F, Fe - 1, (Fe - 1Y - 1, · · · .
Now
_r(o) = 0 iff 0 E Fe- 1, i.e. 1 E Fe, i.e. 1 (j_ F,
_rr(O) = 0 iff 0 E (Fe- 1Y- 1, i.e. 1 E (Fe- 1)e,
i.e. 1 (j_ Fe- 1, i.e. 2 (j_ Fe, i.e. 2 E F.
3. Adjunction in 2-categories.
E : fg ---t 1s
such that
(v)
4. Pregroups.
and expansions
Both contractions and expansions are needed to prove that the com-
pound types form a pregroup with adjoints
Without loss of generality, one may assume that all contractions pre-
cede all expansions.
It follows that to show A ::; /3, where f3 is a simple type, no expansions
are needed. In particular, to show that a string of words of compound
Iterated Galois Connections in Arithmetic and Linguistics 395
5. Linguistic applications.
English.
I see her
7fl (7rrsld') 0 ::; sl
L...____j L..__j
Note that q£q1 ::; q£q ::; 1. The dash here represents a Chomskyan
trace, which is put in for comparison only. In writing whom rather
396 J. Lambek
she is seen -
1r3 ( 1r3r s1 o££P2f.) (P2o£) < s1
'----...J I L.__j I
German.
du siehst ihn
1r2 (1r2s1o£) o ::::; s1
'----...J L...._j
siehst du ihn?
(q1o£7r~)(1r2 o) ::::; ql
I L...____j I
French.
j e veux dormir
7fl (7fr sl i~') i ::::; sl
L..______j L___j
je veux le voir
1f 1
L_____j
( nr sl ie) (ioeeie) (ioe)
L___j I L__j I
::::; sl
Note that the three languages considered here all require the simple
type oee, but German also requires orr. So far, I have not come across
a language that requires oeee or orrr.
References
Author's address:
J. Lambek, McGill University,
Montreal, Canada
Deductive Systems and Galois
Connections
I. Chajda, R. Halas
Abstract
1 Introduction
(H1) x · (y·x) = 1
(H2) (x · (y · z)) · ((x · y) · (x · z)) = 1
(H3) X· y = 1 andy· X= 1 imply X= y.
of the symbol "*", generally used for implication, we will here (for
the sake of brevity) use " ·" .
It was shown by A. Diego [2] that the operations of a Hilbert algebra
satisfy the following properties:
(1) X· X= 1, 1 = 1, 1 ·X=
X· X
(2) x · (y · z) = y · (x · z)
(3) x · (y · z) = (x · y) · (x · z).
Moreover, on the base set of a Hilbert algebra a binary relation :::; can
be introduced by setting
x ::::; y if and only if x · y = 1
and, due to (H3), (1) , (2) and (3) , it is a partial order on H with the
greatest element 1.
Now, deductive systems on a Hilbert algebra 1l = (H; ·, 1) are subsets
containing the constant 1 and closed under the inference rule Modus
Ponens; formally, a subset D ~ His a deductive system of 1l if
1 ED and
a E D and a · c E D give c E D.
This concept was generalized from Hilbert algebras to weakly regular
algebras by the first author in [1]. In what follows we get another
definition which is a generalization of the previous one for Hilbert
algebras but not so restrictive as that in [1] for investigations of Galois
connections.
2 b-deductive systems
From now on let A = (A , F) be an algebra and let T 2 (A) denote
the set of all binary term functions of A . We introduce the following
concept:
Definition 1. Let A= (A , F) and b E T 2 (A). By a b-translation is
meant every unary func tion
for every a E A.
We are ready to introduce our main concept:
Definition 2. Let A = (A , F) be an algebra with a constant 0 and
b E T 2 (A). A subset D <:;;; A is called a b-deductive system of A
whenever
(i) 0 ED
(ii) a E D and b(a, c) E D , b(c, a) E D imply c E D
(iii) a E D implies b(O , a) E D and b(a, 0) E D
(iv) if b(a, c) ED and b(c, a) ED then also b(T(a) , T(c)) ED for every
b-translation T .
Remark 1. If 1l = (H; ·, 1) is a Hilbert algebra and its constant
1 is considered as 0 in the previous definition, then the concept of
b-deductive system for b(x, y) = x · y coincides with the already men-
tioned one. It is an easy exercise to verify that the condition (iii) is
trivially satisfied with respect to (1) and, due to (2) and (3) , also (iv)
is evident. It is not too complicated to show that also (ii) is satisfied.
At first , we will study the interconnection between b-deductive systems
and congruence kernels. For this, we introduce the following concept:
3 Fichtner terms
One can immediately check that the variety of all Hilbert algebras
is weakly regular (where 1 is considered as our constant) due to the
condition (H3) . Moreover, we need only one term and n = 2 in the
Fichtner condition (**)since one can take b1 (x, y) = x·y and b2 (x, y) =
b1 (x, y) = y · x (It was shown by A. Diego [2] that the class of all
Hilbert algebras is a variety). This motivates us to introduce the
following concept:
Definition 4. A binary term b of a variety V with 0 is called a
Fichtner term if
holds in V.
Remark 3. Hence, every variety V having a Fichtner term is weakly
regular.
Let b be a binary term of a variety V and A E V. The term function
on A induced by b will be denoted by the symbol bA. Analogously for
oA.
Lemma 1. Let b be a Fichtner term of a variety V, let A E V and
8 E ConA. Th en
4 Galois connections
for every b-translation T. One can easily infer [bAI8 (T(a) , T(c))]e =
bAI8 (T([a] 8 ), T([c) 8 )) = [OA]e and hence bA(T(a), T(c)) E [OA]e =D.
0
In the remaining part of the paper, we are interested in lattice proper-
ties of Q(b) = DedA (b). For this, we can ask for some more restrictive
408 I. Chajda , R. Hala?5
8D 1 vD2 = 8D 1 V 8D 2
(where Von the right hand side is in ConA).
Suppose D, D"~ E DedA (bA) for "'( E f and a E D n V{D'Y; "'( E f} .
By Theorem 3, there are 8 , 8"~ E Con A such that D = [OA]e , D 1 =
[OA]e')' for"'( E f. Hence, (OA , a) E 8 and, due to the compactness of
con A, there exist "'/1' ... ' "'/k E r such that (oA ' a) E e'Yl v . . . v e 'Yk.
Hence, there exist Co, Ct, ... 'Ck E A with Co = oA , Ck =a and
D n D* = D n VP = V{D n C; C E P} = {oA}
by Theorem 7 thus D* is the pseudocomplement of D. D
thus also
Hence C n D = {OA} . D
References
Author's addresses:
Department of Algebra and Geometry
Palacky University Olomouc
Tomkova 40
779 00 Olomouc, Czech Republic
e-mails: chajda@risc. upol.cz
hals@risc. upol.cz
A Galois Correspondence for Digital
Topology
v
J. 5/apa/
Abstract
We investigate a Galois correspondence between the category of closure
spaces (where closures are considered to be only grounded, extensive and
monotone) and the category of relational systems of a given arity (where
arities are considered to be ordinals) . We show that objects of the obtained
coreflective subcategory of the category of closure spaces are suitable for
applications to digital topology because their connectedness is a certain
type of path connectedness.
AMS Mathematics Subject Classification: 18B30, 18A40, 06A15.
Key words: Closure spaces, Relational systems, Digital topology.
(II) Fa(Rela) is the full subcategory of Clo whose objects are pre-
cisely the closure spaces (X, u) having the following property:
a sequence with x = Xio for some i 0 , 0 < i 0 < a, there exists i 1 < i 0
such that Xi 1 E A.
Complete systems of neighbourhoods of points of (X, fa(R)) can be
determined by using the following statement (and Remark 2(b)):
Denote by Clau the full subcategory of Cla given by the closure spaces
whose closure is idempotent. Further, denote by TapA the full subcat-
egory of Clau whose objects are precisely the Alexandroff topological
spaces. TapA is a full subcategory of F2 (Rel2 ) and in [12] the following
statement is proved:
an element. Then the set {xi; i < i 0 } is connected in (X, fa(R)) for
each i 0 , 0 < i 0 ::::; a.
Proof. For i 0 = 1 the statement is trivial. Let i 0 > 1 and suppose that
{xi; i < i 1 } is connected for each i 1 , 0 < i 1 < i 0 . As {xi; i < i 1 } ~
{xi; i::::; i 1 } ~ !a(R){xi; i < i 1 }, the set {xi; i::::; i 1 } is connected for
each i1, 0 < i1 < io. Since no<il<io{xi; i::::; i1} #- 0, Uo<il <io {xi; i::::;
i 1 } is connected. But Uo<i 1 <io{xi; i ::::; ii} = {xi; i < i 0 } and the
statement follows from the principle of transfinite induction.
From now on, n will denote a natural number (i.e., a finite ordinal)
with n > 1.
with at least four points such that, for each point z E C, there are
exactly two points in C adjacent to z, then C separates Z x Z into
precisely two components. Now, there arises a problem to formulate
and prove an analogy of the Jordan curve theorem for the closure op-
erations fn(R). This problem seems to be quite difficult in its general
setting but, with respect to applications to digital topology, it would
be sufficient to solve it by finding a convenient n-ary relation R on
Z x Z for each natural number n > 1. For n = 2 the problem has
been solved because, in consequence of [6], such a convenient binary
relation R on Z x Z is that one mentioned above for which h(R) is
the Khalimsky topology.
References
Author's address:
Department of Mathematics
Technical University of Brno
616 69 Brno, Czech Republic
e-mail: slapal@um.fme.vutbr.cz
Galois Connections in Category
Theory, Topology and Logic
W. Gahler
Abstract
The notion of a Galois connection is important in different branches of
mathematics. It even is used for defining basic notions in several theories.
In this paper the role of Galois connections is demonstrated in reference to
known results and moreover in presenting new ones.
AMS Mathematics Subject Classification: 06D35,18B35,03E12.
Key words: Galois connection, Non-classical logic, MV-algebra, Partially
ordered monad, Fuzzy filter.
(Ml) For any set X and each pair of different elements x and y of X,
the infimum of rJx(x) and TJx(Y) does not exist.
(M2) For all mappings f, g: Y ------t rpX from f ~ g it follows J-Lx o rpf ~
J-Lx o rpg, where ~ is defined argumentwise with respect to the
partial ordering of rpX.
(M3) For each set X, J-Lx: (rprpX, ~) ------t (rpX , ~)preserves non-empty
suprema.
The partial orderings ~ of the sets rpX are considered as finer rela-
tions. For each set X, the elements of rpX are called rp- objects on X,
and the minimal elements of rpX also ultra objects.
For each non-empty subset A of rpX the supremum V M exists.
MEA
Hence, whenever for a subset A of rpX a lower bound in rpX exists,
the infimum A M of this subset exists.
MEA
For each non-empty set X we denote the supremum V TJx(x) by
xEX
TJx[X]. A rp-object M on X for which M ~ TJx[X] holds, is called
stratified.
A rp-object Mona set X for which M < TJx(x) holds for some x EX,
is called a microobject at x. Because of condition (Ml), x is uniquely
associated to M. Of course, microobjects are special stratified <p-
objects.
Microobjects are in some sense properly finer than points. They may
exist or may not. If there are no microobjects, then condition (Ml)
can be formulated as follows:
(Ml') For each set X, TJx : X ------t rpX is an injection and all values
TJx(x) are ultra objects on X.
filter functor-, which assigns to each set X the set FX of all (proper)
filters on X. ::; indicates that the sets FX are equipped with the finer
relations of filters, that is , the inversion of the inclusion. ry and p, are
natural transformations consisting of all mappings 'r/x : X --+ FX and
fJ,x: FFX--+ FX respectively, where for each x EX, 'r!x (x) = {M ~
X I X E M} and for each filter .c on FX , Mx(.C) = un
AE.CMEA
M. In
this classical case microobjects do not exist.
In the general case of a partially ordered monad <]) = (<p, ::; , ry , p,) there
are the following examples of Galois connections.
Example 1. Let f : X --+ <pY and e : Y --+X be mappings such that
foe= ryy. Then the sup-inverse of P,x o<p f : (<pX ,::; )--+ (<pY ,::; )
exists and is denoted by
<p;;: (<pY, ::;) --+ (<pX, ::;).
Example 2. For each surjection f : X --+ Y , the sup-inverse of the
acSLAT-morphism <pf : (<pX , ::;) --+ (<pY , ::;) exists, denoted by <p- f :
(<pY, ::;) --+ (<pX, ::;).
Partially ordered submonads. Let<]) = (<p, ::; , ry , p,) be a partially
ordered monad. By a partially ordered submonad of <]) we mean a
partially ordered monad W = (<p' , ::; , ry' , p,') such that
nb = J1x o rpp,
rpX X rpX
cp- t 2 of cpt 2 exists. We introduce the closure operator cl : cpX ---+ cpX
ofT ([3]) by means of the sup-inverse cp;t 1 defining
cl is a hull operator, that is, M ::::; elM holds for all M E cpX . If
M = elM, then M is called closed. Since cl is a hull operator, we
have that the infimum of any set of of closed cp-objects on X is closed,
as far as this infimum exists.
As neighbourhood operator nb : cpX ---+ cpX of the <I>-convergence
structure T we mean the neighbourhood operator of the associated <I>-
pretopology p ofT, which is defined by p(x) = V M for all x E X.
M--tx
nb is also a hull operator and can be introduced by means of the
sup-inverse cp- t 2 ([6]) by
(0) 0 is closed with respect to all non-empty suprema and all infima,
as far as these infima exist.
p(x) = M (1)
MEO,ryx(x):SM
i EI i EJ
a ----+ y = max { x E L I a 1\ x ~ y }
432 W . Gahler
iEI iEI
a ---+ y = max { x E L I a * x :S y }
and for the mappings fa : L ---+ L and ga : L ---+ L, given by fa (x) = a*X
and ga(Y) =a---+ y, we have fa(x) :S y +-+ x :S ga(Y) for all x , y E L.
Clearly, a frame is a commutative quantale with 1\ : L 2 ---+ L the
related binary operation.
Further examples of commutative quantales are given by means of the
continuous t-norms * : £ 2 ---+ L. They are defined as follows:
(T1) L is the unit interval [0, 1] equipped with the usual ordering.
(T3) * is order preserving, that is, a :::; band c :::; dimply a* c :::; b *d.
if a> 0
if a= 0.
Hence, for these t-norms the condition of double negation is not ful-
filled and they therefore do not define Girard monoids.
Case of MY-algebras. By a complete MV-algebra we mean a com-
plete Girard monoid (L , ::; , *) which is divisible, that is, for all a, b E L
from a ::; b it follows a = b * c for some c E L.
Examples of complete MY-algebras:
(1) The Lukasiewicz t-norm *defines a complete MY-algebra ([0, 1],::;
'* ).
(2) All complete Boolean algebras are complete MY-algebras. They
can be characterized as those complete MY-algebras (L, ::;, *)for which
* is idempotent, that is, a * a = a for all a E L. In this case, then *
equals 1\.
Related logics. In the following there are listed basic structures
together with related non-classical logics:
Frames intuitionistic logic
Commutative quantales monoidallogic
Complete Girard-monoids - linear logic
Complete MY-algebras Lukasiewicz logic
The following is well-known in first order logic:
For each mapping f : X --* Y, the mapping FLf : FLX --* FLY
assigns to each M E FLX the fuzzy filter FLf(M) on Y given by
FLf(M)(g) = M(g of) for all g E Lx .
For each set X, each x E X and f E Lx let 'TJx(x )(f) = f(x) , and
for each £ E FLFLX and f E Lx let J-tx(.C)(f) = .C(ef) , where ef :
FLX--* L is the mapping M r-+ M(f).
We distinguish some types of fuzzy filters. An L-filter M on a set X
is called
bounded if M(a) :::;; a holds for all a E L and
homogeneous if M(a) =a holds for all a E L.
As a specialization of the general property of being stratified, here we
have that an L-filter on a set X is
stratified if and only if M(a) :::=: a holds for all a E L.
Each fuzzy filter coarser than a bounded fuzzy filter is also bounded.
Each fuzzy filter finer than a stratified fuzzy filter is also stratified.
Galois Connections in Category Theory, Topology and Logic 435
(v
M EA
M)(f) = A M(f)
M EA
(2)
(A M)(f) =
MEA h 1\ ···1\ fnS!
Ml , ... ,MnEA
for all g E Lx, a bounded fuzzy filter [f, a] is defined, called a principal
fuzzy filter on X (first defined in [4]).
Since for each f E Lx the principal fuzzy filter [f, Uf] is bounded,
its homogenization [ f , Uf) 1\ TJx[X] exists. For any f E Lx and all
g E Lx we have [f](g) = V (Uf 1\a) vng . Clearly, [OJ= TJx[X].
f /\a5:c g
436 W. Gahler
M 1\
a ~M(f) 1\ Uf
[f, a].
M= 1\ [f].
Uf~M(f)
If* is the infimum 1\ in (L , ::;), then the notion of a fuzzy filter in both
the frame case and in the quantale case coincide. Hence, the quantale
case is more general than the frame case.
In the quantale case, the related partially ordered fuzzy filter monad
(.ri, ::;, ry, fJ), also called the L-filter monad, is defined in the same way
as in the frame case. In particular, the L-filters Tlx(x) : Lx ---* L are
the same mappings as in the frame case.
Moreover, the notions of bounded, homogeneous and stratified fuzzy
filter are defined in the same way as in the frame case. There exist the
partially ordered fuzzy filter submonads of (FL, ::;, ry, 11) defined by all
bounded, homogeneous and stratified L-filters, respectively.
For each set X the supremum of a non-empty subset A of FLX has
the same representation as in the frame case given in Proposition 7
by equation (2). It follows that for each non-empty set X , T]x [X] =
V Tfx(x) also is a fuzzy filter in the quantale case.
xEX
For the infima of fuzzy filters in the quantale case we have:
(A
MEA
M)(J) = v
h •··· • fn S:: f
M1 , ... ,MnEA
(A
MEA
M)(J) v
MEA
M(J) .
if X= Xo
f(x) = { :
if X -::j::. Xo
From the example in Section 12 we will obtain, that there are distin-
guished fuzzy filters which differ from their c-adjoints and also some
which do not.
If M and N are distinguished fuzzy filters and M = Ne , hence
also Me = N, then {M , N} will be called a c-adjoint pair. In case
M = Me, the fuzzy filter M will be called c-selfadjoint.
a E9 b = c(c(a) * c(b)).
If L is a Girard monoid, then as c we can take the negation -, : L -t L
holds for all f, g E Lx. Notice that in this definition only an inequality
appears, which is in accordance with the inequality in condition (Q3)
of the definition of a fuzzy filter in the quantale case.
Analogously as in the frame case, to each c-distinguished fuzzy filter
M can be associated a further fuzzy filter Me defined by M e(!) =
c(M(c of)) for all f E Lx. Me is called the c-adjoint of M. Propo-
sitions 18 and 19 hold analogously in the quantale case. The notions
c-adjoint pair and c-selfadjoint fuzzy filter are defined analogously as
in the frame case.
In the example which will be presented in Section 13 all c-distinguished
fuzzy filters M are c-selfadjoint.
442 W . Gahler
L J fs
0
There are 25 fuzzy filters in this example. They are shown in Fig. 3,
in which finer filters are situated more downwards. In particular there
are
9 bounded, non-homogeneous fuzzy filters , indicated by small circles,
11 homogeneous fuzzy filt ers, indicated by boldfaced dots, and
5 stratified, non-homogeneous fuzzy filt ers, indicated by small dots.
Whereas in this example all the principal fuzzy filters are the bounded,
non- homogeneous fuzzy filters , their homogenizations as well as H1s =
[!I] A [fs], H16 = [!I] A [!6], Hs2 = [is] A [!2], H52 = [!6]/\ [!2] are
the homogeneous fuzzy filters .
Moreover, Mo = [h] A [!6], M1 = [!4]/\ [is], Mo1 = [fs] 1\ [!6]
and 5 0 = [!I] A [fs]A [f6], S1 = [!2] A [fs] A [!6] are the stratified,
non-homogeneous fuzzy filters.
(3) In this example [h, 1], [!4 , 1], 7Jx(O), 7Jx(1), M0 and M1 are the
distinguished fuzzy filters, indicated in Fig. 3 additionally by overlines.
(4) {M 0 , [h, 1]} and {M 1 , [!4 , 1]} are adjoint pairs.
(5) Both fuzzy filter-s 1Jx(O) and 7Jx(1) are selfadjoint.
(0, 0]
TJx(
=[h]
defined by
1
0 1
* 2
0 0 0 0
1 1
2 0 0 2
1 0 21 1
By a fuzzy filter here we mean an L-filter with L the quantale (L, :::; , *).
There are 22 fuzzy filters in this example. They are shown in Figure
4, where the finer fuzzy filters are situated more downwards. In par-
ticular, there are
11 bounded, non-homogeneous fuzzy filters, indicated by small circles,
and
11 homogeneous fuzzy filters , indicated by bold faced dots.
Stratified fuzzy filters which are non-homogeneous, in particular micro-
fuzzy filters, do not exist.
From Proposition 14 it follows:
Proposition 21 The mappings [!5, 1], [!6, 1], [f5] and [f6] are ex-
cluded as fuzzy filters with respect to (L , :::; , *).
There are four bounded non-homogeneous fuzzy filters which are not
single principal fuzzy filters. They are:
Notice that for the principle fuzzy filters [!,a] appearing in this ex-
ample in some cases only the condition f :::; f * f (e.g. for [h, 1]) and
in some other cases only the condition a* a = 0 (e.g. for [h , ~]) is
fulfilled.
Galois Connections in Category Theory, Topology and Logic 445
[0,0]
'TJX (0)
=[h]
On the other hand, each mapping int : Lx ---+ Lx which fulfills these
conditions, is the interior operator of the fuzzy pretopology defined by
equation (3). The interior operator int characterizes a fuzzy topology
if and only if additionally into int = int.
In the frame case conditions (2) and (3) are equivalent to the condition
(0') T is closed with respect to all suprema and all finite products
!1 * · · · * fn of fuzzy sets.
Each <I>-topology p can be characterized as a subset T of Lx which ful-
fills condition (0') by taking intf = V g for all f E Lx.
g"S_ f,gET
Proposition 27 The sup-inverse 'P;t 1 : (/)X ---+ (/JT of J.Lx o'Pt 1 : (/JT ---+
'PX is given by
v (4)
for all M E 'PX and h E LT, wheTe joT each f E Lx, ef : 'PX ---+ L is
defined by ef (N) = N (f).
(elM)(!) = v
N(h)•···•NCJn) ~ f (x)
for all N -tx
(5)
(ciM)(.f) v
cl (JI ,.. ..Jn) :S; J
M(h*·· · *fn)· (7)
450 W. Gahler
The frame case. In the following we assume that * equals 1\. In this
case we have more results. Some are even more simple. For instance,
for all JI, ... , fn E Lx it follows that cl (JI , ... , j~) = cl (fi/\ .. .1\fn).
Hence, in the frame case, we only need the notion of fuzzy set closure
for single fuzzy sets. Thus instead of (6) we only need
Proposition 30 In the frame case the equations (4) , (5) and (7) can
be reduced, respectively, to
<p~t1(M)(h) v M(g) ,
t1 ::; h
v M(g),
e9 o
(ciM)(.f) (9)
N(g ) ~ f( x)
for all JV -4x
(ciM)(.f) V M(g).
clg :S: f
Proposition 31 In the cases (A) and (S) under the assumption that
(L, ~) fulfills the condition (Z) and in the cases (B') and (H') (in which
(L, ~ ) even is a complete chain) we have cl M V ciN = cl (M V N)
for all M,N E <pX .
by p(O) = [!I], q(O) = [h, ~] and p(l) = q(l) = 7Jx(l) are different
<I>-pretopologies which have one and the same closure operator.
References
[1] G. Birkhoff, Lattice theory, Amer. Math. Soc. Colloq. Publ. 25 , 1940.
[5] W. Gahler, The general fuzzy filter approach to fuzzy topology, II,
Fuzzy Sets and Systems 76 (1995) 225-246.
Author's address:
Werner Gahler,
Scheibenbergstr. 37,
12685 Berlin
Dyadic Mathematics -
Abstractions from Logical Thought
R. Wille
Abstract
Mathematics finally aims at supporting thought and action of human be-
ings. For fulfilling this aim, mathematical abstractions of logical thought
are essential. Because human logical reasoning is based on concepts as the
basic units of thought, the dyadic mathematization of concepts performed
in Formal Concept Analysis is such an abstraction. The dyadic nature of
concepts is grasped through the notion of a formal context with its object-
attribute-relation and its corresponding Galois connection. It is outlined
how this dyadic foundation may lead to dyadic conceptions and results in
order and lattice theory, contextual logic, algebra, and geometry, and how
that supports the development of a human-oriented mathematics.
AMS Mathematics Subject Classification: 06A15, 06B23, 03B, 08A, 051D
Key words: Dyadic Mathematics, Formal Concept Analysis, Ordered sets,
Lattices, Galois connection, Contextual logic, General Algebra, Geometric
measurement
Contents
1. Introduction
2. Galois Connections in Human Thought
3. Dyadic Order Theory and Logic
4. Dyadic Algebra and Geometry
5. Outlook
1 Introduction
Dyadic Mathematics is understood as a human-oriented development of
mathematics based on the conviction that the aim of mathematics finally
453
K. Denecke eta!. (eds. ), Galois Connections and Applications, 453-498.
© 2004 Kluwer Academic Publishers.
454 R. Wille
lies in the support of thought and action of human beings (cf. [Wi02a]).
For elaborating this view, we have to answer the basic question: How
can mathematics support human thinking? Following Peirce's philosoph-
ical pragmatism (see for instance [Pe92]), we obtain as a short answer that
mathematics is able to promote human reasoning. More explicitly, logical
thinking as expression of human reason grasps actual realities by the ba-
sic forms of thought: concepts, judgments, and conclusions; mathematical
thinking abstracts logical thinking for hypothetically developing a "cosmos
of forms" of potential realities. This close relationship between logical and
mathematical thinking allows mathematics to support humans in their rea-
soning about realities (cf. [WiOl b]).
This paper gives a survey about basic attempts to unfold the idea of dyadic
mathematics. Because of the lack of space, most explanations can only
sketch the different findings and will be far from being complete. But, for
all the different approaches, a unifying basis evolves out of the understand-
ing that human reasoning is based on concepts as the basic units of thought
(cf. [SeOl]). Since a concept is constituted by its extension and its inten-
sion, concepts are of dyadic nature and may even be viewed as the origin
of the notion of Galois connection. This is outlined in Section 2 in con-
nection with an introduction to Formal Concept Analysis, which has been
developed out of a mathematization of "context" and "concept". A general
dyadic method for mathematizing transformations from ideas to concepts is
presented and applied to mathematize linear continua order-theoretically.
Section 3 points out that orders in general yield basic patterns of thought
with which humans grasp realities. Prominent mathematizations of those
patterns are general ordinal and contraordinal scales which are discussed
in their central role for a dyadic order theory. These mathematical abstrac-
tions of logical thought are related to the dyadically developed Contextual
Logic for which a close connection between the mathematized concepts and
judgments is essential. Section 4 reports on basic theorems of a possible
dyadic algebra and on applications in elementary linear algebra. A possible
dyadic geometry is then discussed through geometric measurement with its
four mathematization levels from (1) empirical situations to (2) empirical
models, (3) synthetic models, and (4) numerical (algebraic) models. Fi-
nally, an outlook suggests, in particular, future work on an extension of
dyadic mathematics to triadic mathematics in the sense of Peirce's three
universal categories.
Dyadic Mathematics -Abstractions from Logical Thought 455
Obviously, the two derivation operators satisfy the following three condi-
tions:
( 1) z1 c- z2 ===} z11 :J
-
z2'1 (2) z c- ziT ' (3) ziii = z 1 ·'
this means that the two derivation operators form a Galois connection be-
tween the power sets of G and M ordered by set-inclusion. The general
definition of a Galois connection based on a binary relation was first pub-
lished by G. Birkhoff in [Bi40] where he even mentioned the interpretation
of the binary relation as object-attribute-relation (as G. Birkhoff has told
the author, he was inspired to his general definition by the presentation
456 R. Wille
The rich experiences in applications have shown that users of Formal Con-
cept Analysis could easily and successfully activate the Galois connection of
the object-attribute-relation in their logical thinking if they were familiar
with the content of the formalized context. But, in most cases, the users
were not able to mathematically understand Galois connections and For-
mal Concept Analysis; therefore it is important to establish enough bridges
between mathematical and logical thinking. The basic notion of a formal
context can be logically understood best via data tables. The example
shown in Fig.2 (see [PrOO]) represents a formal context with 21 objects
(types of sleeping bags) evaluated by 8 attributes (the crosses describe the
binary relation). Such data tables can also support the logical understand-
ing of the following mathematical definition of formal concepts and of the
subconcept-superconcept relation:
The set of all formal concepts of IK together with the defined order relation
is denoted by IB (IK).
0
A general method of constructing formal concepts uses the derivation oper-
ators to obtain, for X ~ G and Y ~ M , the formal concepts (X I I , X I) and
(YI,YII). For an object g E G , its object concept 19 := ({g}II , {gV) is
the smallest concept in IB(IK) whose extent contains g and, for an attribute
mE M, its attribute concept J-Lm := ({mV, {m}II) is the greatest concept
in IB(IK) whose intent contains m.
f\ (At, Bt)
t ET t ET l ET
V(At, Bt)
lET l ET l ET
Dyadic Mathematics -Abstractions from Logical Thought 457
Sund X X X
Kompakt Basic X X X X
Finmark Tour X X X
Interlight Lyx X X X
Kompakt X X X
Cat's Meow X X X X
Igloo Super X X X
Donna X X X
Tyin X X X
Travellers Dream X X X X
Yeti light X X X X
Climber X X X
Viking X X X X
Eiger X X X
Climber light X X X X
Cobra X X X X
Cobra Comfort X X X
Foxfire X X X X
Mont Blanc X X X X
content represented in the formal context; quite often, after a short glance
at the diagram, users even recognize mistakes in the underlying data con-
text (cf. [WiOOb]). This direct support of logical thinking indicates that the
contextual and holistic nature of concepts in human mind are remarkably
preserved by our mathematization of formal contexts and concepts.
Since concepts are the basic units of human thought, the mathematization
of concepts by formal concepts based on Galois connections can be used to
make mathematically explicit further ideas and conceptions. This shall be
demonstrated by establishing a general method for mathematizing transfor-
mations from ideas to concepts. Those transformations shall be understood
in the sense of the structure-genetic psychology of Jean Piaget [Pi59] (see
also [SeOl]) .
Now, let Fa be an !-maximal filter of C . Then 1Fo has the infimum !Fol\f.l.l
as its only lower neighbour in ~( JK.(C)) which yields 1Fo E J(~(JK.(C)))
and hence /~o(C) ~ J(~(JK.(C))). Conversely, let b be a V-irreducible
formal concept of ~(JK.(C)) . Then, by the Basic Theorem, b has to be an
object concept, i.e., there is an F E ~(C) with b = 1F. For the unique
lower neighbour c of b, by Zorn's Lemma, there exists a maximal formal
concept ~ with c ~ ~ and b <f ~- It follows that ~ is /\-irreducible in
~(JK.(C)) and therefore an attribute concept by the Basic Theorem, i.e.
there is an I E J( C) with ~ = f.J.l . Because of 1F 1\ f.J.l = c, F is !-maximal
and hence FE ~o(C). Thus, /~o(C) = J(~(JK.(C))) is proved. Dually, we
obtain M(~(JK.(C))) = f.J.Jo(C).
1 L(l)
Lemma 1.
F1 := C1 U {1} and F2 := C2 U {1} are the "extreme " !-maximal filters,
462 R. Wille
(4) each cut (c-1,cf-) yields that 1F1 V rFc-< = t-d(c-<J and
1F2 V r Fc't- = f.lJ(c 't-J, p,I(c-<J is a lower neighbour of
p,I(c""'] V rFc't- and an upper neighbour of p,I(c-<),
p,I(c't-] is a lower neighbour of p,I(c't-] V r Fc.., and an upper
neighbour of p,I(c't-) ,
(5) x = d-1 1\ cf- yields that t(x) := ({FE J(C) I x E F},
{IE J( C) IX E I}) = r Fc't- v rFd-1 = p,I(d-1] (\ f.lJ(c't-]·
durations, but not in time points). These hints shall suffice to demonstrate
the fruitfullness of concept-analytic methods and to support the Aristote-
lean conception of continua. Finally, the concept-analytic results shall be
even more concretized within the example of the real continuum-structure.
Example 2. The real continuum-structure CIR decribed in Example 1 is
embedded by the map L into the concept lattice of the formal context IK( C JR)
by Theorem 1, which can be illustrated by a linear ordered set (IR, :::;)
extending (JR., :::;). (IR, :::;) is defined by
i :=(JR. x {- 1,+1}) U{( - oo, +1),(+oo,-1)} and
(r, u) :::; (s, v) : {::} r < s or (r = s and u:::; v);
The linear ordered set (IR \ {(-oo, + 1), (+oo, -1)} , :::;) obviously arises out
of (JR., :::; ) by dividing each real number r into t he two elements (r, -1) <
(r, +1). i can be mapped bijectively onto the set of all atoms of ~(IK( C JR))
by the map a with a( - oo, +1) := 1F1, a(r, - 1) := !F}--oo,r[ • a(r, +1) :=
IF]r,+ oo[• and a( +oo, - 1) := 1F2 . To simplify we define - oo := 1F1,
r- := !F}--oo ,r[• r+ := IF]r,+oo[• and +oo := 1 F 2. By a(r, u) :::; a(s, v) :
{::} (r, u) :::; (s, v), the linear order of (IR, :::;) is transferred to the set of
atoms of ~(IK(C JR )) ; with respect to this order :::;, -oo is the smallest
atom, +oo is the largest atom, and r- < r+ < s - < s+ if r < s in JR.
The continua of the real continuum-structure QIR are represented in the
concept lattice by the formal concepts t(]r, s[). By Theorem 2(5), we have
t(]r, s[) = (r+) V (s- ), which indicates that the atoms a with r+ :::; a:::; s -
are exactly the atoms below t(]r, s [); thus, it is meaningful to say that the
point concepts r+ and s- are the boundaries of the continuum concept
t(]r, s [). The cuts of the real continuum-structure are represented in the
concept lattice by the pairs (r - , r+ ); in this conceptual frame, r - and r+
stand for the indecomposable partial subpoints of the decomposable real
point which is represented by the formal concept (r-) V (r+) .
[GW99], Section 1.4), in this paper we only concentrate on two types which
are basic for the mathematical theory of ordered sets: the general ordinal
scale ([])£ := (P, P, :S:) and the general contraordinal scale ([JPJ!. := (P, P, l).
Dyadic Mathematics -Abstractions from Logical Thought 467
.0_
cheap (P, :S. 250)
A
medium-priced (P, > . 2501\ :S. 400)
A
expens1ve - (P, >. 400)
.0_
downy feather (F, a. goose down)
.0_
synthetic fibre (F, -, a. goose down)
good
.0_
((T, >. 0 1\ :S. 7) 1\ (G, :S .1000)) v
((T, >. -7 A:S.O)I\(G,:S.1400)) v
((T, > . - 15 1\ :S. -7) 1\ (G, :S .1700)) v
(T, :S. -15) 1\ (G, :S. 2000))
.0_
acceptable ((T, > .01\ ::;.7)A(G,:S.1400)) V
( (T, > . - 7 1\ :S . 0) 1\ (G, :S . 1700)) v
((T, >. - 151\ :::;. -7) 1\ (G,:S.2000)) v
(T, :S. -15)
bad -A ((T, >.01\ :::;. 7) 1\ (G, > .1400)) v
( (T, > . - 7 1\ :S. 0) 1\ (G, >. 1700)) v
((T, > . -151\ :::;. -7) 1\ (G,>.2000))
Both, Theorem and Supplement, show that the concept lattice of the gen-
eral ordinal scale ([Jl.E is (up to isomorphism) the smallest complete lattice
into which the ordered set P := (P, ~) has an order embedding. This in
particular underlines the importance of the Galois connection given by the
derivation operators of ([Jl.E:
The formal context JK(P) := (J(P) , J(P) , .6.) defined in Section 2 can be
viewed as a modified version of the general ordinal scale ([Jl.E which, in the
finite case, is even isomorphic to ([Jl.E.
The dyadic view of mathematical theories does not only give closer links
to logical thinking, it may also substantially enrich their structure the-
ory. In the scope of mathematical order theory this may become clear
by considering, for each ordered set P, the corresponding standard context
IKo (P) := (Jo(P), Jo(P) , .6.) which can be understood as an analogue to the
spectrum of a commutative ring with 1. Since '13 (JK( P)) ~ '13 (!Ko (P)) by
Theorem 1, P can still be represented by its standard context. This has
been elaborated in the form of topological representation theorems for 0-1-
lattices P including the special cases of distributive and Boolean 0-1-lattices
[Ha92]; recently, this has been generalized to 0-1-lattices with operators by
M. Gehrke and J. Harding [GH01]. Here the usefulness of the standard
context shall only be demonstrated by results about the order dimension.
dim(P) = fdim(J(SB(fflp
-
)) , M(SB(fflp
-
)) , ~)
for each finite ordered set P. Theorem 1 indicates that this equation can
be obtained even for certain infinite ordered sets:
The order dimension results can be succesfully applied to the task of establi-
shing well readable line diagrams of concept lattices which are essential for
reaching valuable interpretations of empirical data represented by formal
contexts. In this paper such applications can only be explained through
an example, the data context (G, M,I) of which is presented in Fig.6. The
Ferrers dimension of that context is 3 which is indicated by the numbers 1,
2, and 3 filled into the empty cells to represent the complements of the three
corresponding Ferrers relations R1 , R2 , and R3 , respectively. The three cells
(2, c), (4, b), and (6, g) show that two Ferrers relations do not suffice. The
concept lattices Li := SB(G, M, Ri) (i = 1, 2, 3) which are chains of length 5,
3, and 2 are depicted in Fig.7. An order embedding of the concept lattice of
470 R. Wille
II a b c d e f g h
1 Leech X X 1 1 1 1 X 1 1
2 Bream X X 1 1 1 1 X X 1
3 Frog X X X 1 1 1 X X 1
4 Dog X 2 X 1 1 1 X X X
5 Spike- weed X X 3 X 3 X 3 3 3
6 Reed X X X X 3 X 3 3 3
7 Bean X 2 X X X 1 2 2 2
8 Maize X 2 X X 2 X 2 2 2
a,b,g
1
h
2
c a,c,d,f
3 8
4
e
7 a,b,d,:!:
d,e g,h,i
7 4
f b e,g,h ,i
5,6,8 1,2,3,5,6 1,2,3,4,7,8
Now, we consider the second basic type of ordinal scales: the general con-
traordinal scales !!Jfl'_ ·- (P, P, l) based on ordered sets P ·- (P, :::;) .
Dyadic Mathematics -Abstractions from Logical Thought 471
These scales yield the important Galois connection given by the derivation
operators of OE. :
Proof For (Sl, 23) E 23(JKcd(P)) we have InF = 0 for all IE Qt and FE 23,
hence U Qt n U 23 = 0. U mis, as a union of ideals, an order ideal and U 23
is, as a union of filters , an order filter. Furthermore, (U Sl) U (U 23) = P
because otherwise there would be an a E P with a rj_ U Sl and a rj_ U 23 ,
i.e. (a] rj_ Qt and (a]~cd B for all BE 23, which would contradict Qt = 23~cd.
Thus, (U m, U 23) is a formal concept of oct.
Conversely, for (A , B) E
23(0Ci_), m:={IE J(P) I I~ A} and 23 :=[FE ~(P) I F ~ B} form the
formal concept (Qt,23) of occd(P) with (USl, U23) = ~cd(Qt , 23) =(A, B).
This proves that ~cd is a bijection. Since ~cd and its inverse are obviously
order-preserving, ~ cd is an isomorphism from 23 (JKcd (P)) onto 23 (OCj_). D
case we consider, for any p E M, the set Jp of all minimal order ideals D of
(M, ~) with p ED and AnD =f. 0 for all A E 2t; let JM := UpEM Jp. Then
the finite formal context ((J)M := (J M , M, ;i) is called the (object reduced)
simply implicational standard scale derived from M. 0
Theorem 5. The intents of ((J)M are exactly the order filters of (M , ~)
equal to M or not containing any A E 2t. The set J(((J)M) \ {M} of all
proper intents is therefore an order ideal I of the distributive lattice of all
order filters of (M, ~) which satisfy -!F = 0 for all order filters F not in I.
Conversely, each such order ideal may be represented by the proper intents
of a simply implicational standard scale.
Proof For D E JM we have the object intent D;6 = M \D. Thus, the
intents of ((J)M are just the sets M \ UtET Dt with Dt E J M ( t E T) , which
are obviously order filters of (M, ~) equal to M or not containing any
A E 2t. Now, let F be any such order filter unequal M. Then M \ F is
an order ideal of (M, ~) with An (M \F) =f. 0 for all A E 2t. For each
p tf_ F we choose a minimal order ideal Dp in M \ F with p E Dp and
A n Dp =f. 0 for all A E 2t; then F = M \ Up EM\ F Dp. Thus, the intents
of ((J)M are exactly the order filters of (M, ~) equal to M or not containing
any A E 2t. Clearly, J(((J)M) \ {M} is an order ideal of the lattice F(M, ~)
of all order filters of the finite ordered set (M, ~) . Conversely, let I be an
order ideal of :F(M, ;S) satisfying ..1-F = 0 for all order filters F not in I,
and let 2li := {FE F(M, ~) \ {0} I F tf_ I} . Then M := (M , ~ ' 2li) is an
ordered set with inconsistent subsets and I= J(((J)M) \ {M}. D
1\
chain decomposition C1, ... , Cn of M(L) and extend each chain Ck to Ck:=
C k U { 1L} (k = 1, ... , n) . Then a 1--7 ( c1 (a) , . .. , Cn (a)) , where Ck (a) is the
1\
smallest upper bound of a in Ck (k = 1, ... , n) , yields an isomorphism L
1\ 1\
from L \ {OL} onto an order filter of C 1 x · · · x Cn- Now, t(L \ {OL}) can
be drawn as an upper part of a grid which represents the direct product
1\ 1\ 1\
C1 x · · · x Cn where the chains Ck are located on straight lines. Finally,
the node representing OL has to be added properly {cf. [LSW97]). Fig.9
shows a concept lattice drawn by the described method {cf. [GW99], p.23).
"Contextual Logic" (cf. [WiOOa]). In this paper, we shall only discuss the
dyadic nature of concepts graphs which arise from the contextual math-
ematization of Sowa's conceptual graphs [So84]:
Definition 8.
(1) A power context family is a sequence i. := (!Ko, JKI , lK2, . . . ) of formal
contexts~:= (Gk,Mk,h) with Gk c:;;; (Go)k fork= 1,2, .... The formal
concepts of~ with k = 1, 2, . . . are called relation concepts, because they
represent k-ary relations on the object set Go by their extents.
(2) A relational graph is a structure (V, E , z;) consisting of two sets V and
E and a mapping v: E-+ Uk=I ,2 , ... Vk; the elements of VandE are called
vertices and edges, respectively, and v( e) = (VI, .. . , vk) is read: VI, ... , Vk
are the adjacent vertices of the k-ary edge e (lei := k is the arity of e; the
arity of a vertex is defined to be 0). Let E (k) be t he set of all elements of
VUE of arity k (k = 0, 1, 2, .. . ).
(3) A concept graph of a power context family i. := (!Ko, JKI, lK2, .. . ) with
~ := (Gb Mk, Ik) for k = 0, 1, 2, ... is a structure Q5 := (V, E , v, /'\,'e) for
which
- /'\,:VUE-+ Uk= O,I,2 , ... 1B(~) is a mapping such that 1'\,(u) E IB(~)
for all u E E(k),
- e: V-+ s.}J(Go)\{0} is a mapping such that e(v) c:;;; Ext(/'\,(v)) for all
vE vand, furthermore, e(vl) X ... X e(vk) c:;;; Ext(/'\,( e)) for all e E E
with v( e) = (VI, ... , Vk); in general, E xt( c) denotes the extent of the
formal concept c.
D
2
1j
<J)
·en0
::&
I
Ill 0
(water,earth)
(water,air)
uwaier AIX IX (water,fire)
arth X X IX (earth,air)
r X XIX (earth,fire)
re XXIX (air,fire)
Fig. 12: Two concept graphs of the power context family in Fig.lO
Dyadic Mathematics -Abstractions from Logical Thought 477
Definition 9. For a power context family IK, the k-ary conceptual content
Ck(IB) (also called the lKA; -conceptual content) of a concept graph IB :=
(V, E , v, K, e) of IK is defined as the closure of {(g, K(u)) I u E E(k ) and g E
e(u)} with respect to the closure system C(lKA;) (k = 0, 1, 2, ... ). Then the
disjoint union
C( IB) := Co( ~B) u CI (~B) U C2( ~B ) U ...
is called the (IK-) conceptual content of the concept graph IB.
Definition 10. For a context lK. := {G, M, I), let §imP(JK.) := { (g, b) E G x
SB(JK.) I g E Ext{b)} and let scon(SB(JK.)) be the set of all convex subsets 6
ofSB{lK.)\ { (M 1 , M)} for which 6U{ (M 1 , M)} is a complete sublattice of the
interval
[(M 1 , M) , V 6] of IB{JK.). A conceptual information context corresponding
to lK. is defined by
JK:inf (K) := (§imP(JK.), 6 con {IB (JK.) ), ~)
Fig. 13: Line diagram of the concept lattice of the conceptual infor-
mation context Kinf (IKo) having as extents the conceptual
contents of the formal context IKo in Fig.lO
Theorem 6. (cf. [PK79]) Let A be a finite set. Then the extents of the
operation-relation-context oc0 R(A) are exactly the subalgebras of the opera-
tional algebra Op(A), which are called the operational clones on A, and the
intents of the operation-relation-context OC0 R (A) are exactly the subalgebras
of the relational algebra Rel(A) , which are called the relational clones on
A.
The two basic types of descriptions may become more apparent by consid-
ering the important algebraic notion of an equational class. Let <.!.:17 be the
class of all algebras of similarity type a and let E 17 (X) be the set of all a-
equations over the (countable) set X of variables. Then the dyadic nature
of the notion of an equational class can be explicated by the formal context
OC( <.!.:17 ; X) := ( <.!.:17 , E 17 (X) , f=) with A f= p ~ q : {::} the equation p ~ q is
Dyadic Mathematics -Abstractions from Logical Thought 481
Further pairs of antiisomorphisms have been studied via suitably chosen for-
mal contexts for or·dered vector spaces [Wl99], finite abelian groups [Vo95],
[Gr99], modules [KV96], and algebraic geometry [Be99]. General investiga-
tions of bialgebraic contexts in which both context sets carry an algebraic
structure are presented in [Vo94] . The here cited research has been inspired
by "Ideas of Algebraic Concept Analysis" as outlined in [VW94] (see also
[Wi76], [WiOla]).
Lemma 3. Let (cp,cpd) E 113(GI x G2,M2 x M1,"') and let cp: G1---+ G2
be a map. If cp(GI)l_w -::/- 0 then mw E M1 and cp(GI)_Lw = (cpd) - 1(mw);
dually, if cpd(M2)1_w -::/- 0 then 9w E G2 and cpd(M2) 1_w = cp- 1(gw)·
Proof The existence of an attribute min cp(GI)_iw yields w =<cp(g), m>
=< g, cpd(m) > for all g E G which is equivalent to cpd(m) = mw E M1
since the underlying W -context is clarified. This equivalence is formally
expressed by the identity cp(GI)l_w = (cpd) - 1(mw)· The dual claim can be
dually proved. 0
dual space V, and the ternary relationE with (v, <p, r) E E: {::} <p(v) = r.
As an example of such an application, a dyadic-algebraic proof is given for
the following well-known theorem:
Theorem 8. For each matrix over a field, its row rank zs equal to its
column rank.
coordinatization
geometrical models
synthetic level
representation
empirical models
formal level
formalization
empirical ituations
of reality
reality level
0
Theorem 10. (Coordinatization Theorem) A clarified ordinal con-
I\
text ][( ( inteTOrdinally derived context OC; 0 ) with the attribute set M =
{ mo, m1, ... , mn} satisfying (Ai) and (Pij) (i, j = 0, 1, ... , n with i =I= j)
is isomorphic to the ordinal context IK(L_) (interordinally derived context
0C; 0 (L)) of a suitable ordered n-loop L_.
Although the embeddings of ordinal contexts into bilinear contexts over the
reals are not finitely axiomatizable in first order logic [WlOO], the General
Representation Theorem can still be used for concrete data which shall fi-
nally be demonstrated by the example context presented in Fig.15. The
data context in this figure describes the amounts of absorption of four colour
stimuli by eleven receptors in a goldfish retina (cf. [SF68]). The data con-
text is viewed as an ordinal context IKcot whose integer values are ordered in
490 R. Wille
the natural way. For representing such an ordinal context in a real vector
space, by the General Representation Theorem, we have to determine the
antiordinal attribute dependencies of the ordinal context (cf. [WW96]). In
[GW86], it is shown that the ordinal dependencies of an ordinal context
lK. := ( G, M, (Wm, ~m)mE M , I) are exactly the attribute implications of the
formal context 0Ca := (G 2 , M,I0 ) with (g , h)I0 m : {::} m(g) ~m m(h).
Since an ordinal dependency m1 , ... , mn ~ m is defined by (mi (g) ~ mi
mi(h)for all i = 1, ... , n) =? m(g) ~m m(h) , for checking the conditions
(Ai), it helps to extent lK. to the ordinal context lK := (G , M(JMd , (Wn , ~n
)nEMl.JMd,llJJd) where Md := {md I mE M}, wmd := Wm , v ~md w:
{::} w ~m v, and Jd := {(g , md , w) I (g , m , w) E I}. Then we obtain
the dependencies described by the (Ai ) as implications of lKo which can
be read from the line diagram of the concept lattice of lKv . For our ex-
ample, this line diagram is depicted in Fig.l6 (cf. [WW96]). It shows
that the conditions (Ai) are satisfied by the ordinal contexts correspond-
ing to the attribute sets {Violet430, Blue458dual , Blue - Green498}
and {Violet430, Blue485dual , Blue- Green498}. Therefore, we have
two ordered-2-loop-representations which can even be simultanously repre-
sented in the Euclidean plane as shown in Fig.17 (cf. [Wi92]). An interesting
outcome is that the four colours are "ordered" in the figure according to
the colour circle.
Dyadic Mathematics -Abstractions from Logical Thought 491
Blue-Green 498
5 Outlook
As already pointed out in the introduction, the presented survey only gives
a first insight into what dyadic mathematics could be. This hopefully is
stimulating to elaborate further the sketched ideas concerning a human-
oriented mathematics. Of course, comprehensive efforts are desirable. In-
stead of discussing possibilities of further developments of dyadic mathe-
matics, it shall only be explained that there are even good reasons for ex-
tending dyadic mathematics to triadic mathematics. Inspired by Peirce's
triadic theory of signs understood as a basic theory of human thought, a
Triadic Concept Analysis has already been invented based on triadic con-
texts which code when an object has an attribute under a certain condition
(see [LW95],[Wi95],[WZOO]). This led to mathematical investigations of
triordered sets and trilattices [Bi98b] and even of triadic Galois connections
492 R. Wille
[Bi97]. It turned out that Triadic Concept Analysis is a useful basis for a
modal extension of Contextual Logic (see [Wi98],[SW03]) . But also a triadic
view of algebra and geometry becomes meaningful if the degrees of freedom
of mathematizing realities are mathematized themselves on a third level.
Already Klein's Erlanger Programm [K172] may be viewed as triadic in this
sense and even more the theory of invariance and meaningfullness for rep-
resentational measurement [KLST71]. All this indicates how inspiring and
fruitful further human-oriented developments of mathematics might be.
References
[Ar95] Aristoteles Werke in deutscher Ubersetzung. Bd. 11: Physikvor-
lesung. 5. Aufl. Akademie Verlag, Berlin 1995.
[SeOl] Th. B. Seiler: Begreifen und Verstehen. Ein Buch iiber Begriffe
und Bedeutungen. Verlag Allgemeine Wissenschaft, Miihltal
2001.
[Wi03c] R. Wille: Sind unsere Vorstellungen von Raum und Zeit richtig?
oder: Besteht ein Kontinuum a us Punk ten? In: L. Hefendehl-
Hebeker, S. HuBmann (Hrsg.): Mathematikdidaktik: Zwischen
Fachorientierung und Empirie. Franzbecker Verlag, Hildesheim-
Berlin 2003, 266~279.
[WW93] R. Wille, U. Wille: On the controversy over Huntington's equa-
tions. When are such equations meaningful? Mathematical So-
cial Sciences 25 {1993) , 173~180 .
[WW95] R. Wille, U. Wille: Uniqueness of coordinatizations of ordinal
structures. Contributions to General Algebra 9 (1995) , 321 ~324.
Q-independence, 277
radical ideals, 67
regular strong equation, 347
relational algebra, 234, 262
relational clone, 234, 262
relational system, 231 , 415
relative automorphism, vii
relative pseudocomplement, 404
right adjoint, 6
right pregroup, 393
Ring of symmetric polynomials,
25
t-independence, 284
terminal object, 142
topological category, 416
topology, 414
topos, 142
ultrafilter, 93
variety
congruence modular, 146