Convexity theories 0 fin. foundations
Abstract
Kleisli, Heinrich; Röhrl, Helmut
Full text
Publicacions Matem`atiques, Vol 40 (1996), 469–496. CONVEXITY THEORIES 0 FIN. FOUNDATIONS Heinrich Kleisli and Helmut R¨ ohrl* Abstract In this paper we study big convexity theories, that is convexity theories that are not necessarily bounded. As in the bounded case (see [4]) such a convexity theory Γ gives rise to the category ΓCof (left) Γ-convex modules. This is an equationally presentable category, and we prove that it is indeed an algebraic category over Set.We also introduce the category ΓAlg of Γ-convex algebras and show that the category Frm of frames is isomorphic to the category of associative, commutative, idempotent DU-convex algebras satisfying additional conditions, where Dis the two-element semiring that is not a ring. Finally a classification of the convexity theories over Dand a description of the categories of their convex modules is given. 0. Introduction The set theory used in this paper has as its basic concepts “sets”, “classes”, and “conglomerates” and is described in [1, p. 5–8]. The class Uof all sets is called the universe. Conglomerates that can be indexed by a class are said to be legitimate and may, and indeed will, be treated as a class. Since we will be dealing with classes that are equipped with some structure it is convenient to replace the term “class” by “big set” and consequently speak of, for instance, “big group” instead of “class equipped with a group structure”. In section 1 we present the necessary background definitions. The “small” versions of these definitions appeared in [4]. However, here we wish to deal with the universe Uand certain maps from Uto semirings and similar structures. The definitions presented in this section formalize the notion of absolutely convergent series —known from classical analysis— to include infinite series with huge numbers of summands *Partial support by the Swiss National Science Foundation under grant 20-42054.94 is acknowledged.
470 H. Kleisli, H. R¨ ohrl from a prenormed semimodule over a prenormed semiring. A prenormed semimodule possessing this type of structure is called a prenormed semimodule with U-summation. Section 2 contains several elementary results concerning prenormed semimodules with U-summation. They deal with rearranging summands, double sums, and similar issues. Big convexity theories are introduced in section 3. Their definition is identical with the definition of N-convexity theories in [4, (4.1)], —except for the size. As in [4] we define the notions of Γ-convex modules and their homomorphisms, leading to the category ΓCof (left) Γ-convex modules. In the case of N-convexity theories the free Γ-convex modules can be described without further preparation (cf. [4, proof of (4.7)]). This is not so for big convexity theories. Hence a number of computational rules for Γ-convex modules have to be proved directly, as was done in [5, (2.4)]. The section closes with the definition of commutative convexity theories and the notion of algebras over such convexity theories. The main result of section 4 is the algebraicity of the category ΓC.It is shown by involving a well known characterization theorem ([3, 3.1.13]) that, in our case, reduces the issue to the existence of free objects. If Ais an infinite set and Γ |Astands for the “restriction” of Γ to Athen the free Γ|A-convex module over Acarries a unique Γ-convex module structure that makes it the free Γ-convex module over A. As a consequence, ΓC is an algebraic category, and the same is true for the category ΓAlgcof associative, commutative, and unital Γ-convex algebras where Γ is any big commutative convexity theory. In section 5 we show that the category of frames (see [2, p. 39]) is isomorphic to the category of associative, commutative, idempotent DU-algebras satisfying additional conditions (see section 5); here Dis the two-element semiring that is not a ring. The last section brings an enumeration of the big convexity theories over Dand describes the category of convex modules over those convexity theories. 1. Prenormed semirings and prenormed semimodules with U-summation Let Rbe a semiring (in the sense of [7, section 1]) and denote by RU the big set of all maps U→Rthat vanish on the complement of some subset of U. Such maps will be denoted by lower case greek letters with a lower placeholder symbol, e.g. α∗or α. We shall use freely the other definitions and notions of [4, 1.] pertaining to RNand apply them to
Convexity Theories 0 fin. Foundations 471 RU. In particular, RUis a big hemiring (under pointwise composition) as well as a big left-R, right-Rsemimodule. If Mis a left-Rsemimodule we denote by MUthe big set of all maps U→Mthat vanish on the complement of some subset of U. The elements of MUwill be denoted by lower case greek letters with a lower placeholder symbol, e.g. µ∗or µ. Again the pertinent definitions and notions of [4, 1.] carry over to MU.MUis a big left-RUhemimodule (under pointwise composition) as well as a left-Rsemimodule. Since we are mostly dealing with left structures we will call left-R semimodules from now on R-semimodules. Next we repeat some of the definitions of [4, 1.] in our current setting. The notions of positive semiring, cone semiring, prenormed semiring, and prenormed semimodule can be found in [7]. 1.1. Definition. Let Cbe a positive semiring. By a U-summation for Cis meant a pair (SC,C) consisting of a big twosided C-subsemimodule SCof CUand a twosided C-homomorphism C:SC→Csuch that (i) C(U):= {α∗∈C U: supp α∗is finite}is contained in SCand for all α∗∈C(U)the relation C(α∗)={αu:u∈supp α∗}holds, where stands for the usual sum of the finitely many elements in {αu:u∈supp α∗}; (ii) for all α∗∈SCand β∗∈C Uwith β∗≤α∗,β∗is in SCand C(β∗)≤C(α∗); (iii) for every α∗∈SCand every map ϕ:U→U,αϕ−1(u) ∗is in SCfor all u∈U, and the map C(αϕ−1 ∗) given by Uu→ C(αϕ−1(u) ∗)∈Cis in SCand satisfies C(C(αϕ−1 ∗)) = C(α∗); (iv) if α∗is in CUand there exists a map ϕ:U→Usuch that αϕ−1(u) ∗ is in SCfor all u∈Uand that C(αϕ−1 ∗)isinSC, then α∗is in SC. Recall (see [4]) that, given a possibly big subset Tof U, we denote by αT ∗the map given by Uu→ αuif u∈T 0ifu∈ T. Two comments are in place concerning (1.1). Firstly, it follows from (i) and (iii), that for any α∗∈SCthe relation αu≤C(α∗) holds for
472 H. Kleisli, H. R¨ ohrl all u∈U. As a consequence of this one obtains SC·SC⊆SC, whence SCis a big hemiring. Secondly, one checks easily that supp C(αϕ−1 ∗)⊆ ϕ(supp α∗) holds, whence for any α∗∈C Uthe map C(αϕ−1 ∗) is also in CU. 1.2. Definition. Let Rbe a prenormed semiring with prenorm :R→Cwhere Cis a cone semiring with twosided U-summation (SC,C). By a U-summation for Ris meant a pair (SR,R) consisting of a big twosided R-subsemimodule SRof RUand a twosided R-homomorphism R:SR→Rsuch that (o) α∗∈RUis in SRif and only if α∗is in SC; (i) R(U):= {α∗∈RU: supp α∗is finite}is contained in SRand for all α∗∈R(U)the relation R(α∗)={αu:u∈supp α∗}holds, where stands for the usual sum of the finitely many elements in {αu:u∈supp α∗}; (ii) for all α∗∈SR,R(α∗)≤C(α∗); (iii) for every α∗∈SRand every map ϕ:U→U,αϕ−1(u) ∗is in SRfor all u∈U, and the map R(αϕ−1 ∗) given by Uu→ R(αϕ−1(u) ∗)∈Ris in SRand satisfies R(R(αϕ−1 ∗))=R(α∗). The comments following (1.1) apply also to (1.2). 1.3. Definition. Let Rand Rbe prenormed semirings with prenorms :R→C resp. :R→Cwhere Cis a cone semiring with twosided U-summation (SC,C). In addition, let (SR,R) resp. (S R, R)beU-summations for Rresp. R. Then a map f:R→Ris called a bounded homomorphism of prenormed semirings with U-summation if fis a homomorphism of semirings such that (i) fU(SR)⊆S Rand RfU(α∗)=f(R(α∗)), for all α∗∈SR; (ii) there is a c∈C(depending on f) with RfU(α∗)≤(C(α∗)) ·c, for all α∗∈SR. A bounded homomorphism of prenormed semirings with U-summation is said to be a contractive homomorphism (or contraction) of prenormed semirings with U-summation if (1.3), (ii), holds with c=1.
Convexity Theories 0 fin. Foundations 473 1.4. Definition. Let Mbe a prenormed R-semimodule with prenorm :M→Cover the prenormed semiring Rwith prenorm :R→Cand U-summation (SR,R). By a U-summation for Mis meant a pair (SM,M) consisting of a R-subsemimodule SMof MUand a R-homomorphism M:SM→Msuch that (o) µ∗∈MUis in SMif and only µ∗is in SC; (i) a) M(U):= {µ∗∈MU: supp µ∗is finite}is contained in SMand for all µ∗∈M(U)the relation M(µ∗)={µu:u∈supp µ∗} holds, where stands for the usual sum of the finitely many elements in {µu:u∈supp µ∗}; (i) b) for all α∗∈SRand m∈M,M(α∗m∗)=( R(α∗)) ·m; (ii) for all µ∗∈SM,M(µ∗)≤C(µ∗); (iii) for every µ∗∈SMand every map ϕ:U→U,µϕ−1(u) ∗is in SMfor all u∈U, and the map M(µϕ−1 ∗) given by Uu→ M(µϕ−1(u) ∗)∈Mis in SMand satisfies M(M(µϕ−1 ∗)) = M(µ∗). Again the comments following (1.1) apply here too. We close this section with 1.5. Definition. Let Mand Mbe prenormed R-semimodules with prenorms : M→Cresp. :M→Cwhere Cis a cone semiring with twosided U-summation (SC,C). In addition, let (SM,M) resp. (S M, M) be U-summations for Mresp. M. Then a map f:M→Mis called a bounded homomorphism of prenormed R-semimodules with U-summation if fis a homomorphism of R-semimodules such that (i) fU(SM)⊆S Mand MfU(µ∗)=f(M(µ∗)), for all µ∗∈SM; (ii) there is a c∈C(depending on f) with MfU(µ∗)≤(C(µ∗)) ·c, for all µ∗∈SM. A bounded homomorphism of prenormed R-semimodules with U-summation is said to be a contractive homomorphism (or contraction)of prenormed R-semimodules with U-summation if (1.5), (ii), holds with c=1. If Mis a prenormed R-semimodule with U-summation and m∈M, then the map fm:R→Mgiven by Rr→ rm ∈Mis a bounded homomorphism of prenormed R-semimodules with U-summation.
474 H. Kleisli, H. R¨ ohrl Let Rbe a fixed prenormed semiring with U-summation. Then we obtain a category RSmod1Nwhose objects are the prenormed R-semimodules with U-summation and whose morphisms are the contractions of prenormed R-semimodules with U-summation, the composition being the set-theoretical one. 2. Some elementary results 2.1. Lemma. Let Mbe a prenormed R-semimodule with U-summation (SM,M). Let furthermore µ∗∈SM.ForT⊆Ulet µT ∗be the element of MUgiven by Uu→ µuif u∈T 0if u∈ T. Then µT ∗is in SMand M(µT ∗)≤C(µ∗). In particular, if u∈U then µu≤C(µ∗). Proof: Define a map ϕ:U→Usuch that for some u∈U,ϕ−1(u)=T holds. Then µT ∗is in SMby (1.4), (iii), and the inequality follows from (1.4), (ii). 2.2. Lemma. Let Mbe a prenormed R-semimodule with U-summation (SM,M). Let furthermore µ∗∈SMand ν∗∈MUbe such that for some sets A⊇ supp µ∗and B⊇supp ν∗there is a bijection ϕ:A→Bwith µu=νϕ(u) for all u∈supp µ∗. Then ν∗is in SMand M(ν∗)=M(µ∗). Proof: Extend ϕto some map ϕ:U→U. One checks easily that ν∗=M(µϕ−1 ∗) holds. Hence (1.4), (iii), shows that M(ν∗)= M(M(µϕ−1 ∗)) = M(µ∗) holds. 2.3. Lemma. Let Cbe a positive semiring with U-summation (SC,C)and let α∗∈ SCsatisfy the relation supp α∗⊆N1×N2for two subsets N1and N2 of U. Let furthermore ϕi:U→Ube such that ϕi(n1,n 2)=niholds for all (n1,n 2)∈N1×N2and i=1,2. Suppose that αϕ−1 1(u) ∗is in SCfor all
Convexity Theories 0 fin. Foundations 475 u∈Uand that C(αϕ−1 1 ∗)is in SC. Then αϕ−1 2(u) ∗is in SCfor all u∈U, C(αϕ−1 2 ∗)is in SCand C(C(αϕ−1 2 ∗)) = C(C(αϕ−1 1 ∗)). Proof: It follows directly from (1.1), (iv), that α∗is in SC. Hence the conclusion is an immediate consequence of (1.1), (iii). Due to (2.2) we may, and will, adopt the following notation. If µ∗∈SMhas the property that supp µ∗⊆Athen we write a∈A (µa) instead of M(µ∗). Hence, in the situation of (2.3), we may write n2∈N2 (αn1,n2) instead of C(αϕ−1 1(u) ∗) and replace C(C(αϕ−1 1 ∗)) by n1∈N1 n2∈N2 (αn1,n2). Therefore (2.3) means that in SCdouble sums may be interchanged. 2.4. Lemma. Let Rbe a prenormed semiring with U-summation (SR,R).Let furthermore α∗∈SR,β ∗a map from Uto SR, and γ∗a map from U to Rsuch that γ∗and Cβ ∗ are bounded. Then Rα(Rβ ∗γ∗)=RR(αβ ∗)γ∗. Proof: Using the axiom of choice for big sets we can establish a bijection ψ:U→U×U. Denote ψ(u), u∈U,by(u1,u 2) and write the map Uu→ αu1βu1 u2γu2as θ∗. We claim that θ∗is in SR. In order to prove this, let ϕi:U→Ube maps such that ϕi◦ψ−1(u1,u 2)=ui,i=1,2, holds. Denoting by pri:U×U→Uthe ith projection, i=1,2, we have ϕi=pri◦ψ,i=1,2. Obviously, θ∗is in (U, C). Moreover, the union {supp βu ∗:u∈supp α∗}is a set Nand we have θu= 0 for all elements u∈ ψ−1(supp α∗×N). This means that θ∗is in RU, and (1.2), (o), implies θ∗∈CU. Obviously we have θ∗ϕ−1 i(u)=θϕ−1 1(u) ∗ for all u∈U. Hence, for every u∈U,θ∗ϕ−1 1(u)is the map Uv−→ αuβu v2γv2if ψ(v)=(u, v2), 0 otherwise.
476 H. Kleisli, H. R¨ ohrl If cis a bound for γ∗,weget αuβu v2γv2≤αu·βu v2·γv2≤(Cα∗)·βu v2·c. Since the U-summation for Cis twosided, the right side of the last inequality is in SC, and by (1.1), (ii), so is the left side. Hence Cαuβu ∗γ∗exists and we obtain by (1.1), (i) b) and (ii), Cαuβu ∗γ∗≤αu·(Cβu ∗)·c. Since there is a bound cfor the big set of elements Cβu ∗,u∈U,we get Cαuβu ∗γ∗≤αu·cc, whence θ∗ϕ−1 1, that is the map Uu→ Cαuβu ∗γ∗∈C, satisfies θ∗ϕ−1 1≤α∗·cc. Since the latter is in SCit follows from (1.1), (iv), that θ∗itself is in SC. Thus (1.2), (o), implies θ∗∈SRas was claimed. At this point we can continue as in the proof of (2.3) to arrive at our assertion. 3. Big convexity theories 3.1. Definition. Let Rbe a prenormed semiring with prenorm :R→Cand U-summation (SR,R). By a big convexity theory over Ris meant a big subset Γ of SRsuch that (o) C(α∗)≤1, for all α∗∈Γ; (i) the map δu ∗given by Uv→ δu v=1ifu=v 0ifu=vis in Γ, for all u∈U; (ii) for all α∗βu ∗in Γ, u∈U, the map α,β ∗given by Uu→ R{αvβv u:v∈U}∈Ris in Γ. A comment is in order concerning (3.1), (ii). Denote by αβ uthe map Uv→ αvβv u. Then supp αβ u⊆supp α∗. Hence αβ uis in RU. Moreover, αβ u≤α∗as βv u≤C(βv ∗)≤1. By (1.1), (ii), and (1.2), (o), αβ uis in SR, implying that α,β ∗is defined. In addition, since αuβu ∗is the map Uv→ αuβu vwe have αuβu ∗≤βu ∗by (2.1) and (3.1), (o). Due to (1.1), (ii), αuβu ∗is in SCand C(αuβu ∗)≤αuC(βu ∗)≤αu. Therefore the map Uu→ C(αuβu ∗)is≤α∗. Since α∗is in SC, this also holds
Convexity Theories 0 fin. Foundations 477 for the last map and uC(αuβu ∗)≤C(α∗)≤1. In terms of the notation following (2.3) this means that u ( v (αuβu v)) ≤1 holds. Hence (2.3) shows that v u (αuβu v)≤1 is satisfied. The latter, however, is C(α,β ∗)≤1. In other words, the map defined in (3.1), (ii), satisfies without additional hypotheses the condition (3.1), (o). Let Γ be a big convexity theory over Rsuch that for some set Tthe condition card(supp α∗)≤card(T) is satisfied for all α∗∈Γ. Then card(T) is called a bound for Γ and Γ is said to be bounded. 3.2. Lemma. Any big convexity theory is the union of bounded big convexity subtheories. Proof: Let Tbe any infinite set. If Γ is a big convexity theory, put ΓT:= {α∗∈Γ : card(supp α∗)≤card(T)}. Since card(T×T) = card(T), it is easy to check that ΓTis a big convexity theory with bound card(T). Clearly, Γ = {ΓT:T∈P inf (U)}where Pinf (U) is the totality of all infinite subsets of U. 3.3. Definition. Let Γ be a big convexity theory over the prenormed semiring R.By aleft Γ-convex module is meant a set X, non-empty whenever 0∗∈Γ, together with a map Γ×(U, X)(α∗,x ∗)−→ α∗,x ∗∈X such that (i) δu ∗,x ∗=xu, for all u∈U,x∗∈(U, X); (ii) α,β ∗,x ∗=α,β ∗,x ∗, for all α∗∈Γ,β ∗∈(U, Γ),x ∗∈(U, X). Here, (U, X) stands for the conglomerate of all maps U→Xand, similarly, (U, Γ) for the conglomerate of all maps U→Γ. Since we will only deal with left Γ-convex modules, we shall drop the epithet “left” from now on.
484 H. Kleisli, H. R¨ ohrl (3.6) implies that α∗,y∗is independent of the choice of ϕ. It follows from (2.2) that for α∗∈Γ and β ∗∈ΓNthe relation αϕ(),βϕ() ∗= α,β ∗holds, where ϕis any bijection from Uto U. Since Γ is bounded by card(N) and since Nis an infinite set, we have for A:= supp α∗∪ {supp βu ∗:u∈supp α∗}the relation card Acard(N). In order to get a better visual display we write in (3.17.1) αϕ|N(∗)instead of αϕ(∗)|N and xϕ|N(∗)instead of xϕ(∗)|N. Then we have α,β ∗,y∗=αψ(),βψ() ∗,y∗ =αψ(),βψ() ψ|N(∗),yψ|N(∗) =αψ|N(),βψ|N() ψ|N(∗),yψ|N(∗) =αψ|N(),βψ|N() ψ|N(∗),yψ|N(∗) =α,β ψ|N(∗),yψ|N(∗) =α,β ∗,y∗, which is (3.3), (ii). Since the verification of (3.3), (i), for the composition (3.17.1) is straight forward we obtain that Yequipped with the composition (3.17.1) is a Γ-convex module Y∼. One checks easily that for any Γ-convex module Xthe relation (X)∼=Xand for any Γ|Nconvex module Ythe relation (Y∼)=Yis satisfied. Hence the asserted isomorphy is satisfied. 4. The category ΓCis algebraic 4.1. Theorem. Let Γbe any big convexity theory. Then ΓCis an algebraic category. Proof: In [3, Chap. 3, (1.13)], algebraic categories are characterized as equationally presentable categories satisfying three conditions. The last two of these conditions are trivially satisfied by ΓCas ΓChas separators (formed as in Set) and the underlying-set functor ΓC→Set creates quotients of congruences. Hence it remains to be shown that ΓChas arbitrary free objects. Let Abe any set and consider the set B:= {ξ∗∈Γ : supp ξ∗⊆A}.Ifα∗is in Γ and ξ ∗∈(U, B) then α,ξ ∗is in Γ and suppα,ξ ∗⊆Aholds, whence α,ξ ∗is an element of B. Evidently, this makes Ba Γ-convex module F(A). Let δ∗:A→F(A) be the map Aa→ δa ∗∈F(A). Now let ϕbe any map
Convexity Theories 0 fin. Foundations 485 from Ato some Γ-convex module Xand denote by ϕ∗∈(U, X) the map given by ϕ∗(u):=ϕ(u),if u∈A anything,if u∈ A. Define h:F(A)→Xby h(ξ∗):=ξ∗,ϕ ∗for all ξ∗∈F(A). Due to (3.5), his well defined. Obviously, h◦δ∗=ϕ. Moreover if α∗is in Γ and ξ ∗is in (U, F(A)) then h(α,ξ ∗)=α,ξ ∗,ϕ ∗=α,ξ ∗,ϕ ∗=α,h U(ξ ∗), showing that his a homomorphism of Γ-convex modules. The uniqueness of h(subject to h◦δ∗=ϕ) follows from the fact that δ∗(A) is a system of generators of the Γ-convex module F(A). Let Γ be any big convexity theory over the commutative prenormed semiring Rand let Xbe a Γ-convex module. Let furthermore Nbe a set and κ:XN→Xbe a map (equivalently: a composition of arity N). Then κis called a Γ-multi-homomorphism if for every ¯n∈Nand every y∗∈XN\{¯n}the map Xψy∗ −−→ XNκ −→ X is a homomorphism of Γ-convex modules, where ψy∗is given by ψy∗(x)(n):=x, if n=¯n yn,if n=¯n. Let Tbe an algebraic theory that is given by a set {κi:i∈I}of compositions and a set {ρj:j∈J}of relations. Denote the arity of κi by ki,i∈I. Then the category ΓTof Γ-convex T-algebras has as its objects the tuples {X,κ i,X :i∈I}where Xis any Γ-convex module and κi,X :Xki→X,i∈I, is a map such that (i) every κi,X ,i∈I, is a Γ-multi-homomorphism; (ii) every ρj,j∈J, is satisfied on X. Furthermore, ΓThas as its morphisms f:X→Yprecisely those maps that are homomorphisms of Γ-convex modules and are compatible with the compositions κi,X and κi,Y ,i∈I. In order to prove that ΓTis an algebraic category we need few preliminary statements.
486 H. Kleisli, H. R¨ ohrl 4.2. Lemma. Let Γbe any big convexity theory over the prenormed semiring R.Let furthermore α(1) ∗,... ,α (k) ∗be in Γand denote by β∗∈(U, R)the map βu:= α(1) u1·...·α(k) uk,if u=(u1,...,u k)∈supp α(1) ∗×···×supp α(k) ∗ 0,otherwise. Then β∗is in Γ. Proof: It suffices to consider the case k=2. Foru∈supp α(1) ∗define βu ∗by βu v:= α(2) w,if v=(u, w) and w∈U 0,otherwise. By (3.6) we have βu ∗∈Γ for all u∈supp α(1) ∗. Choose βu ∗∈Γ arbitrarily for all u∈ supp α(1) ∗. Then β∗=α,β ∗and hence β∗∈Γ. 4.3. Lemma. Let Γbe any big convexity theory over the prenormed semiring Rwith U-summation (SR,R). Let furthermore α∗∈Γand let ϕ:U→Ube any map. Then R(αϕ−1 ∗)is in Γ. Proof: Put βu ∗:= δϕ(u) ∗,u∈U. Then R(αϕ−1 ∗)=α,β ∗. 4.4. Theorem. Let Γbe any big convexity theory over the commutative prenormed semiring R. Let furthermore Tbe any algebraic theory that is given by a set {κi:i∈I}of finitary compositions of arity ≥1and a set {ρj:j∈J}of relations. Then ΓTis an algebraic category. Proof: Let Abe any set and denote B:= FT(A) the free T-object on A, where Tis the algebraic theory with compositions {κi:i∈I}and no relations. Bcan be thought of as the free “T-multi-magma” on A. Let F(A) be the free Γ-convex module on the set Band denote by δ∗the canonical map from Bto F(A). If i∗ A∈(U, F(A)) is any map with i∗ A|B=δ∗then for every x∈F(A) there is a unique αx ∗∈Γ with (αx ∗)B=αx ∗and x=αx ∗,i ∗ A. Let kibe the (finite) arity of κi,
Convexity Theories 0 fin. Foundations 487 i∈I, and denote the corresponding composition Bki→Bby κ i. Given ¯x:= (x1,... ,x ki)∈F(A)ki,i∈I, denote by β¯x ∗the map Uu−→ R{αx1 b1·...·αxki bki:b1,... ,b ki∈Band κ i(b1,... ,b ki)=u}. Due to (4.2) and (4.3), β¯x ∗is well defined and belongs to Γ. Now put κ i(x1,... ,x ki):=β¯x ∗,i ∗ A,¯x∈F(A)ki. We claim that κ iis a Γ-multi-homomorphism. Let kibe ≥2. For simplicity we check this only for the first component. Put y:= (x2,... ,x ki). For γ∗∈Γ and x∗∈(U, F(A)) we have γ∗,x ∗=γ,αx ∗,i ∗ A=γ,α x ∗,i ∗ A and hence αγ,x ∗=γ,α x ∗. Therefore κ i(γ∗,x ∗,y)=¯ β∗,i ∗ A where ¯ βu=R{γ,α x b1·αx2 b2·...·αxki bki:b1,... ,b ki∈B and κ i(b1,... ,b ki)=u},u∈U. On the other hand, γ,κ i(x,y)=γ,β(x,y) ∗,i ∗ A=γ,β(x,y) ∗,i ∗ A and = β∗:= γ,β(x,y) ∗satisfies = βu=R{γv·αxv b1·αx2 b2·...·αxki bki:v∈U, b1,... ,b ki∈B, and κ i(b1,... ,b ki)=u},u∈U. Since ¯ βu== βudue to (4.2) and (4.3), it is clear that κ iis a Γ-multihomomorphism. In case ki= 1 a similar, but simpler, argument can be used to prove that κ iis a Γ-multi-homomorphism. Now let Xbe any ΓT-object and let ϕ:A→Xbe any map. Since Xis also a T-object there is a map, indeed a T-homomorphism, ϕ:B→Xwith ϕ=ϕ◦δ∗ where δ∗ :A→Bis the canonical map. Since F(A)is the free Γ-convex module on Bthere is a homomorphism of Γ-convex
488 H. Kleisli, H. R¨ ohrl modules f:F(A)→Xwith ϕ=f◦δ∗. Since f◦i∗ A|B=ϕand since ϕis a T-homomorphism we have for every (x1,... ,x ki)∈F(A)ki fκ i(x1,... ,x ki)=f(β¯x ∗,i ∗ A) =β¯x ∗,fU(i∗ A) =β¯x ∗,f ◦i∗ A =κX if(x1),... ,f(xki), where κX iis the composition in Xthat corresponds to κi. This means that fis a T-homomorphism. Since Xis a ΓT-object, ffactors through g:F(A)→F(A)/∼where gis the quotient map with respect to the smallest Γ-congruence relation ∼that is compatible with the set {ρj:j∈J}of relations of T.Iff=¯ f◦gis this factorization then ϕ=ϕ◦δ∗ =f◦δ∗◦δ∗ =¯ f◦g◦δ∗◦δ∗, and this factorization determines ¯ funiquely in terms of ϕ. Hence F(A)/∼is the free ΓT-object on Awith g◦δ∗◦δ∗ the canonical map A→F(A)/∼. Since ΓChas separators, which are formed as in Set and since the underlying-set functor ΓC→Set creates quotients of congruences, [3, Chap. 3, (1.13)], implies that ΓTis an algebraic category. Suppose that on each Γ-convex module Xa map λX:X→Xis given. Then λ:= {λX:X∈0bΓC} is called an 6-ary Γ-composition if for every homomorphism f:X→Yof Γ-convex modules f◦λX=λY◦f is satisfied. The primary example is obtained as follows. Let α∗be given and denote card(supp α∗)by6. For each ϕ∈Xchoose an x∗ ϕ∈(U, X) with x∗ ϕ|supp α∗=ϕand put λX(ϕ)=α∗,x ∗ ϕ,ϕ ∈X. Then (3.5) implies that λis an 6-ary Γ-composition. 4.5. Addendum. Let Γ be any big convexity theory over the commutative prenormed semiring R. Let furthermore Tbe any algebraic theory as specified in (4.4). Given any set {λk:k∈K}of finitary Γ-compositions, denote by T∗the set of compositions {κi:i∈I}together with the class of relations {ρj:j∈J}∪{σ:6∈L}, where each σinvolves the compositions {κi:i∈I}and the Γ-compositions {λk:k∈K}. Then ΓT∗is an algebraic category. Proof: Same as for (4.4), with the appropriate change in the congruence relation ∼.
Convexity Theories 0 fin. Foundations 489 5. A simple example: Frames Let Ddenote the semiring consisting of the two element 0 and 1, with 0 the neutral element for addition and 1 the neutral element for multiplication, satisfying 1 + 1 = 1. There is only one other semiring having precisely two elements, namely the field F2. The ring Dis a positive semiring (indeed a cone semiring) with U-summation (DU,), where (α∗):=max{αu:u∈U}. It is also a prenormed semiring with prenorm idD:D→Dand U-summation (DU,). Furthermore DUis a big hemiring as well as a big commutative convexity theory. Given a DU-convex module Xwe obtain, for any α∗∈DUand any x∗∈(U, X), the element α∗,x ∗∈X. Due to (3.5), α∗,x ∗depends only on the restriction x∗|supp α∗. Hence α∗,x ∗may be written as a formal sum {xu:u∈supp α∗}. Conversely, if ξ:I→Xis any family of elements of Xand α∗∈DUis given by αu:= 1ifu∈I 0 otherwise ,u∈U, while x∗is any extension of ξ, then the formal sum associated with α∗,x ∗is {xu:u∈supp α∗}={xi:i∈I}={ξ(i):i∈I}. In other words we have in Xthe (formal) sums of arbitrary set-indexed families of elements of X. These sums are associative and distributive by (3.3), (ii), and commutative due to (3.6). 5.1. Lemma. Every DU-convex module Xadmits the structure of a semimodule over the semiring D. Proof: Since DUis a convexity theory with zero, (3.10) shows that Xhas a distinguished element 0X:= 0∗,x ∗. Let x,x be in X. Given any two distinct elements uand vof Uand any x∗∈(U, X) with xu=xand xv=x,δu ∗+δv ∗,x ∗is independent of x∗|(U\{u, v}) by (3.5) and is independent of the choice of u, v by (3.6). Hence we define x+x := δu ∗+δv ∗,x ∗. (3.6) shows that x+x =x +xholds. It follows from (3.12) that x+0 X=xis satisfied for all x∈X. Next let u, v, w be mutually
490 H. Kleisli, H. R¨ ohrl distinct elements of Uand let x∗∈(U, X) satisfy xu=x,xv=x, xw=x. Furthermore let βt ∗:= δu ∗+δv ∗,for t=u δw ∗,for t=v anything,otherwise ,t∈U. Then β u=β v=δ uand β w=δ v. Hence δu +δv ,β ∗=δu ∗+δv ∗+δw ∗. Since βu ∗,x ∗=x+x and βv ∗,x ∗=x,wehave (x+x)+x =δu +δv ,β ∗,x ∗ =δu +δv ,β ∗,x ∗=δu ∗+δv ∗+δw ∗,x ∗. However, if γt ∗:= δu ∗,for t=u δv ∗+δw ∗,for t=v anything,otherwise ,t∈U, then γ u=δ uand γ v=γ w=δ v. Hence δu +δv ,γ ∗=δu ∗+δv ∗+δw ∗. Since γu ∗,x ∗=xand γv ∗,x ∗=x +x,wehave x+(x +x)=δu +δv ,γ ∗,x ∗=δu ∗+δv ∗+δw ∗,x ∗ and therefore (x+x)+x =x+(x +x). Finally, let x∗∈(U, X) satisfy xu=xv=xand define α ∗by αt ∗:= δu ∗,for t=uand t=v anything,otherwise ,t∈U. Then αt ∗,x ∗=x, for t=uand t=v. Hence x+x=δu +δv ,α ∗,x ∗. Since δu +δv ,α ∗=δu ∗, we obtain x+x=δu +δv ,α ∗,x ∗=δu +δv ,α ∗,x ∗=δu ∗,x ∗=x. This implies that Xis a unital semimodule over the semiring D. Lemma 5.1 allows us to define a full subcategory DUAlgFof the category DUAlg of DU-convex algebras and their homomorphisms which will be shown to be isomorphic to the category Frm of frames (see [2, p. 39]). The objects of DUAlgFare the associative, commutative and idempotent DU-convex algebras Xthat satisfy the Absorption Law xy +y=y, for all x, y ∈X. The category DUAlgFis a category of algebras in the sense of Addendum (4.5) and therefore an algebraic category.
Convexity Theories 0 fin. Foundations 491 5.2. Theorem. The categories Frm and DUAlgFare isomorphic as concrete categories (over Set). Proof: Let Xbe a frame, that is a partially ordered set (with order relation “≤”) that is complete and satisfies the infinite distributive law. The DU-convex module structure on Xis given by (∗)α∗,x ∗:= {xv:αv=1},for all α∗∈DUand x∗∈(U, X). We have δu ∗,x ∗={xv:δu v=1}=xu,for all u∈U, x∗∈(U, X), which is (3.3), (i). Moreover, for α∗∈DU,β ∗∈(U, DU) and x∗∈ (U, X), α,β ∗,x ∗={{xv:βu v=1}:αu=1} ={xv: max{αuβu v:u∈U}=1} =α,β ∗,x ∗, which is (3.3), (ii). Next we define a multiplication on Xby putting x·x := x∧x for all x,x ∈X. Then by the infinite distributive law x·α∗,x ∗=x∧{xv:αv=1}={x∧xv:αv=1}=α∗,x ·x∗, where x·x∗is the map Uu→ x·xu∈X. This shows that X equipped with this structure is an associative, commutative, idempotent DU-convex algebra A(X) satisfying the Absorption Law. Indeed it follows from (∗) that the sum x+x in the DU-convex module Xis given by the join x∨x. Moreover, a frame morphism f:X→Ybecomes a homomorphism of DU-convex algebras A(f):A(X)→A(Y). Conversely, let Abe an associative, commutative and idempotent DU-convex algebra that satisfies the Absorption Law. We define an order relation “ ≤ on Aby setting a≤bwhenever ab =a. The resulting partially ordered set is denoted by X(A). We claim that for all α∗∈DU and a∗∈(U, A) (5.2.1) α∗,a ∗={av:αv=1}
492 H. Kleisli, H. R¨ ohrl holds. First we want to show that for any vwith αv= 1 the equality av·α∗,a ∗=avis satisfied. For this purpose let u∈Ube such that u=v. Define βt ∗,t∈U,by βt ∗:= αU\{v} ∗,for t=u δv ∗,for t=v anything,otherwise. Then α∗=δu +δv ,β ∗. Hence by the Absorption Law av·α∗,a ∗=α∗,a v·a∗ =δu +δv ,β ∗,a v·a∗ =δu +δv ,β ∗,a v·a∗ =βu ∗,a v·a∗+βv ∗,a v·a∗ =av·βu ∗,a ∗+avδv ∗,a ∗ =βu ∗,a ∗·av+av=av. In other words, av≤α∗,a ∗for all vwith αv= 1. On the other hand, if av≤bfor all vwith αv= 1, i.e., av·b=av, then by (3.5) α∗,a ∗=α∗,b·a∗=bα∗,α ∗ and therefore α∗,a ∗≤b. This proves (5.2.1). In particular we obtain that X(A) is a complete join-semilattice and thus a complete lattice. Moreover we have a∧b=ab. Finally b∧{av:αv=1}=b·α∗,a ∗=α∗,b·a∗={b∧av;αv=1}, which is the infinite distributive law for X(A). Hence X(A) is a frame. If g:A→Bis a homomorphism of DU-convex algebras. Then by (3.4) g(α∗,a ∗)=α∗,gU(a∗),α ∗∈DUand a∗∈(U, A), which shows that gpreserves arbitrary joins. Since gpreserves products, it preserves finite meets. Hence gis a frame morphism X(g):X(A)→ X(B). It is routine to verify that the resulting functors A:Frm → DUAlgFand X:DUAlgF→Frm are inverses to each other. 5.3. Addendum. Let F(A) be the free DU-convex module on the set A. Then the corresponding partial order relation (see proof of (5.2)) satisfies the infinite distributive law. In particular, F(A) always carries an associative,
Convexity Theories 0 fin. Foundations 493 commutative, idempotent DU-algebra structure satisfying the Absorption Law. Moreover, if f:F(A)→Xis a surjective homomorphism of DU-convex modules then for any x,x ∈X (5.3.1) f({f−1(x)}∧{f−1(x)})=x∧x. Proof: The elements of F(A) (see proof of (4.1)) are certain maps ϕ:A→R. In addition, ϕ1+ϕ2, as defined above, is the map given by (ϕ1+ϕ2)(a):= ϕ1(a)+ϕ2(a),a∈A, that is ϕ1+ϕ2is the pointwise sum. Since DUis the set of all maps U→Dwhose support is a set, ϕ1≤ϕ2is equivalent to ϕ1(a)≤ϕ2(a). Hence arbitrary joins and meets are formed pointwise. This shows that the validity of the infinite distributive law needs to be checked only pointwise, which means in Ditself. D, however, satisfies the infinite distributive law. Now let Xbe any DU-convex module and let f: F(A)→Xbe a surjective homomorphism of DU-convex modules. Due to (5.2.1), fpreserves arbitrary joins. In particular, f({f−1(x)})=x for all x∈X. Hence, if ϕ∈F(A) satisfies ϕ≤{f−1(x)}∧{f−1(x)} then f(ϕ)≤f({f−1(x)}∧{f−1(x)}) ≤f({f−1(x)})∧f({f−1(x)})=x∧x. On the other hand if y≤xthen there is a ¯y∈Xwith y+¯y=x. Suppose ψ, ¯ ψ∈F(A) satisfy f(ψ)=yand f(¯ ψ)=¯y. Then f(ψ+¯ ψ)= f(ψ)+f(¯ ψ)=y+¯y=xand thus ψ≤{f−1(x)}. This means that f maps {ϕ:ϕ≤{f−1(x)}∧{f−1(x)}} onto {y:y≤x∧x}.Asa consequence we obtain formula (5.3.1). 6. Classification of convexity theories over D By a level we mean either the cardinal number of a set or the cardinal number of U. As usual we define for two levels λ1and λ2,λ1λ2 provided there are sets A1and A2with card(Ai)=λi,i=1,2, for which there is an injective map A1→A2; we write λ1≺λ2in case λ1λ2and λ1=λ2. 6.1. Proposition. Let Γbe a big convexity theory over D. Then there exists a unique level λ, which is either 1 or infinite, such that Γis one of the following: (λ1)={α∗∈DU: card(supp α∗)λ}and λ= card U; (λ2)={α∗∈DU:1card(supp α∗)λ}and λ= card U; (λ3)={α∗∈DU: card(supp α∗)≺λ}and λis infinite; (λ4)={α∗∈DU:1card(supp α∗)≺λ}and λis infinite.