The finite embeddability property for residuated groupoids

A very simple proof of the finite embeddability property for residuated distributive-lattice-ordered groupoids and some related classes of structures is presented. In particular, this gives an answer to the question, posed by Blok and van Alten, whether the class of residuated ordered groupoids has the property. The presented construction improves the computational-complexity upper bound of the universal theory of residuated distributive-lattice-ordered groupoids given by Buszkowski and Farulewski; for chains in the class, a tight bound is obtained.     

The finite embeddability property for residuated lattices, pocrims and BCK-algebras

A class of algebras has the finite embeddability property (FEP) if every finite partial subalgebra of an algebra in the class can be embedded into a finite algebra in the class. We investigate the relationship of the FEP with the finite model property (FMP) and strong finite model property (SFMP).? For quasivarieties the FEP and the SFMP are equivalent, and for quasivarieties with equationally definable principal relative congruences the three notions FEP, FMP and SFMP are equivalent. The variety of intuitionistic linear algebras –which is known to have the FMP–fails to have the FEP, and hence the SFMP as well. The variety of integral intuitionistic linear algebras (also known as the variety of residuated lattices) does possess the FEP, and hence also the SFMP. Similarly contrasting statements hold for various subreduct classes. In particular, the quasivarieties of pocrims and of BCK-algebras possess the FEP. As a consequence, the universal theories of the classes of residuated lattices, pocrims and BCK-algebras are decidable. Received February 16, 2001; accepted in final form November 2, 2001. RID="h1" ID="h1"The second author was supported by a postdoctoral research fellowship of the National Research Foundation of South Africa, hosted by the University of Illinois at Chicago.     

Residuated Structures,Concentric Sums and Finiteness Conditions

This article is motivated by a concern with finiteness conditions on varieties of residuated structures—particularly residuated meet semilattice-ordered commutative monoids. A “concentric sum” construction is developed and is used to prove, among other results, a local finiteness theorem for a class that encompasses all n-potent hoops and all idempotent subdirect products of residuated chains. This in turn implies that a range of residuated lattice-based varieties have the finite embeddability property, whence their quasi-equational theories are decidable. Applications to substructural logics are discussed.     

The FEP for some varieties of fully distributive knotted residuated lattices

We prove the finite embeddability property for a wide range of varieties of fully distributive residuated lattices and FL-algebras. Part of the axiomatization is assumed to be a knotted inequality and some appropriate generalization of commutativity. The construction is based on distributive residuated frames and extends to subvarieties axiomatized by any division-free equation.     

On the finite embeddability property for residuated ordered groupoids

The finite embeddability property (FEP) for integral, commutative residuated ordered monoids was established by W. J. Blok and C. J. van Alten in 2002. Using Higman's finite basis theorem for divisibility orders we prove that the assumptions of commutativity and associativity are not required: the classes of integral residuated ordered monoids and integral residuated ordered groupoids have the FEP as well. The same holds for their respective subclasses of (bounded) (semi-)lattice ordered structures. The assumption of integrality cannot be dropped in general--the class of commutative, residuated, lattice ordered monoids does not have the FEP--but the class of -potent commutative residuated lattice ordered monoids does have the FEP, for any .

     

Constructing greedy linear extensions by interchanging chains

A natural way to prove that a particular linear extension of an ordered set is ‘optimal’ with respect to the ‘jump number’ is to transform this linear extension ‘canonically’ into one that is ‘optimal’. We treat a ‘greedy chain interchange’ transformation which has applications to ordered sets for which each ‘greedy’ linear extension is ‘optimal’.     

Distributive residuated frames and generalized bunched implication algebras

We show that all extensions of the (non-associative) Gentzen system for distributive full Lambek calculus by simple structural rules have the cut elimination property. Also, extensions by such rules that do not increase complexity have the finite model property, hence many subvarieties of the variety of distributive residuated lattices have decidable equational theories. For some other extensions, we prove the finite embeddability property, which implies the decidability of the universal theory, and we show that our results also apply to generalized bunched implication algebras. Our analysis is conducted in the general setting of residuated frames.     

LFI代数的性质及其与剩余格的关系

讨论LFI代数的性质．也讨论具有可嵌入性的LFI代数的性质；还给出了定义在完备格上的LFI代数成为剩余格的充要条件。     

Cayley’s and Holland’s Theorems for Idempotent Semirings and Their Applications to Residuated Lattices

We extend Cayley’s and Holland’s representation theorems to idempotent semirings and residuated lattices, and provide both functional and relational versions. Our analysis allows for extensions of the results to situations where conditions are imposed on the order relation of the representing structures. Moreover, we give a new proof of the finite embeddability property for the variety of integral residuated lattices and many of its subvarieties.     

Planar algebra of the subgroup-subfactor

We give an identification between the planar algebra of the subgroupsubfactor R ⋊ H ⊂ R ⋊ G and the G-invariant planar subalgebra of the planar algebra of the bipartite graph ★ _n , where n = [G: H]. The crucial step in this identification is an exhibition of a model for the basic construction tower, and thereafter of the standard invariant of R ⋊ H ⊂ R ⋊ G in terms of operator matrices. We also obtain an identification between the planar algebra of the fixed algebra subfactor R ^G ⊂ R ^H and the G-invariant planar subalgebra of the planar algebra of the ‘flip’ of ★ _n .     

Representation theoretic harmonic spinors for coherent families

Coherent continuation π ₂ of a representation π ₁ of a semisimple Lie algebra arises by tensoring π ₁ with a finite dimensional representation F and projecting it to the eigenspace of a particular infinitesimal character. Some relations exist between the spaces of harmonic spinors (involving Kostant’s cubic Dirac operator and the usual Dirac operator) with coefficients in the three modules. For the usual Dirac operator we illustrate with the example of cohomological representations by using their construction as generalized Enright-Varadarajan modules. In [9] we considered only discrete series, which arises as generalized Enright-Varadarajan modules in the particular case when the parabolic subalgebra is a Borel subalgebra.     

On strongly and weakly defined boolean terms

A problem of Gaifman about strongly and weakly defined Boolean terms is solved by finding a Boolean algebra ℱ with a complete subalgebra ℰ such that some element of ℱ not in ℰ can be obtained from elements of ℰ by meets and joins in the normal completion of ℱ.     

Completions for partially ordered semigroups

A standard completion γ assigns a closure system to each partially ordered set in such a way that the point closures are precisely the (order-theoretical) principal ideals. If S is a partially ordered semigroup such that all left and all right translations are γ-continuous (i.e., Y∈γS implies {x∈S:y·x∈Y}∈γS and {x∈S:x·y∈Y}∈γS for all y∈S), then S is called a γ-semigroup. If S is a γ-semigroup, then the completion γS is a complete residuated semigroup, and the canonical principal ideal embedding of S in γS is a semigroup homomorphism. We investigate the universal properties of γ-semigroup completions and find that under rather weak conditions on γ, the category of complete residuated semigroups is a reflective subcategory of the category of γ-semigroups. Our results apply, for example, to the Dedekind-MacNeille completion by cuts, but also to certain join-completions associated with so-called “subset systems”. Related facts are derived for conditional completions. A first draft of this paper by the second author, containing parts of Section 2, was received on August 9, 1985.     

Limits of rank 4 Azumaya algebras and applications to desingularization

It is shown that the schematic image of the scheme of Azumaya algebra structures on a vector bundle of rank 4 over any base scheme is separated, of finite type, smooth of relative dimension 13 and geometrically irreducible over that base and that this construction base-changes well. This fully generalizes Seshadri’s theorem in [16] that the variety of specializations of (2 x 2)-matrix algebras is smooth in characteristic ≠ 2. As an application, a construction of Seshadri in [16] is shown in a characteristic-free way to desingularize the moduli space of rank 2 even degree semi-stable vector bundles on a complete curve. As another application, a construction of Nori over ℤ (Appendix, [16]) is extended to the case of a normal domain which is a universally Japanese (Nagata) ring and is shown to desingularize the Artin moduli space [1] of invariants of several matrices in rank 2. This desingularization is shown to have a good specialization property if the Artin moduli space has geometrically reduced fibers — for example this happens over ℤ. Essential use is made of Kneser’s concept [8] of ‘semi-regular quadratic module’. For any free quadratic module of odd rank, a formula linking the half-discriminant and the values of the quadratic form on its radical is derived.     

An extension of Burnside’s Theorem to infinite-dimensional spaces

The classical Burnside’s Theorem guarantees in a finite dimensional space the existence of invariant subspaces for a proper subalgebra of the matrix algebra. In this paper we give an extension of Burnside’s Theorem for a general Banach space, which also gives new results on invariant subspaces. Partially supported by a grant from the National Science Foundation.     

Subalgebra extensions of partial monounary algebras

For a subalgebra B of a partial monounary algebra A we define the quotient partial monounary algebra A/B. Let B, B, C be partial monounary algebras. In this paper we give a construction of all partial monounary algebras A such that B is a subalgebra of A and C ≅ A/B.     

Join-semilattices whose sections are residuated PO-monoids

We generalize the concept of an integral residuated lattice to join-semilattices with an upper bound where every principal order-filter (section) is a residuated semilattice; such a structure is called a sectionally residuated semilattice. Natural examples come from propositional logic. For instance, implication algebras (also known as Tarski algebras), which are the algebraic models of the implication fragment of the classical logic, are sectionally residuated semilattices such that every section is even a Boolean algebra. A similar situation rises in case of the Lukasiewicz multiple-valued logic where sections are bounded commutative BCK-algebras, hence MV-algebras. Likewise, every integral residuated (semi)lattice is sectionally residuated in a natural way. We show that sectionally residuated semilattices can be axiomatized as algebras (A, r, →, ⇝, 1) of type 〈3, 2, 2, 0〉 where (A, →, ⇝, 1) is a {→, ⇝, 1}-subreduct of an integral residuated lattice. We prove that every sectionally residuated lattice can be isomorphically embedded into a residuated lattice in which the ternary operation r is given by r(x, y, z) = (x · y) ∨ z. Finally, we describe mutual connections between involutive sectionally residuated semilattices and certain biresiduation algebras. This work was supported by the Czech Government via the project MSM6198959214.     

Free Distributive Completions of Partial Complete Lattices

The free distributive completion of a partial complete lattice is the complete lattice that it is freely generated by the partial complete lattice in the most distributive way. This can be described as being a universal solution in the sense of universal algebra. Free distributive completions generalize the constructions of tensor products and of free completely distributive complete lattices over partially ordered sets.     

Roof duality,complementation and persistency in quadratic 0–1 optimization

The paper is concerned with the ‘primal’ problem of maximizing a given quadratic pseudo-boolean function. Four equivalent problems are discussed—the primal, the ‘complementation’, the ‘discrete Rhys LP’ and the ‘weighted stability problem of a SAM graph’. Each of them has a relaxation—the ‘roof dual’, the ‘quadratic complementation,’ the ‘continuous Rhys LP’ and the ‘fractional weighted stability problem of a SAM graph’. The main result is that the four gaps associated with the four relaxations are equal. Furthermore, a solution to any of these problems leads at once to solutions of the other three equivalent ones. The four relaxations can be solved in polynomial time by transforming them to a bipartite maximum flow problem. The optimal solutions of the ‘roof-dual’ define ‘best’ linear majorantsp(x) off, having the following persistency property: if theith coefficient inp is positive (negative) thenx _i=1 (0) in every optimum of the primal problem. Several characterizations are given for the case where these persistency results cannot be used to fix any variable of the primal. On the other hand, a class of gap-free functions (properly including the supermodular ones) is exhibited.