Injective hulls are not natural

In a category with injective hulls and a cogenerator, the embeddings into injective hulls can never form a natural transformation, unless all objects are injective. In particular, assigning to a field its algebraic closure, to a poset or Boolean algebra its Mac-Neille completion, and to an R-module its injective envelope is not functorial, if one wants the respective embeddings to form a natural transformation. Received January 21, 2000; accepted in final form August 10, 2001. RID="h1" RID="h2" RID="h3" ID="h1"The hospitality of York University is gratefully acknowledged by the first author. ID="h2"Third author partially supported by the Grant Agency of the Czech Republic under Grant no. 201/99/0310, and the hospitality of York University is also acknowledged. ID="h3"Partial financial assistance by the Natural Sciences and Engineering Councel of Canada is acknowledged by the fourth author.     

Compact representations of BL-algebras

In this paper we define sheaf spaces of BL-algebras (or BL-sheaf spaces), we study completely regular and compact BL-sheaf spaces and compact representations of BL-algebras and, finally, we prove that the category of non-trivial BL-algebras is equivalent with the category of compact local BL-sheaf spaces. Mathematics Subject Classification (2000):08A72, 03G25, 54B40, 06F99, 06D05     

Hájek basic fuzzy logic and Łukasiewicz infinite-valued logic

 Using the theory of BL-algebras, it is shown that a propositional formula ϕ is derivable in Łukasiewicz infinite valued Logic if and only if its double negation ˜˜ϕ is derivable in Hájek Basic Fuzzy logic. If SBL is the extension of Basic Logic by the axiom (φ & (φ→˜φ)) → ψ, then ϕ is derivable in in classical logic if and only if ˜˜ ϕ is derivable in SBL. Axiomatic extensions of Basic Logic are in correspondence with subvarieties of the variety of BL-algebras. It is shown that the MV-algebra of regular elements of a free algebra in a subvariety of BL-algebras is free in the corresponding subvariety of MV-algebras, with the same number of free generators. Similar results are obtained for the generalized BL-algebras of dense elements of free BL-algebras. Received: 20 June 2001 / Published online: 2 September 2002 This paper was prepared while the first author was visiting the Universidad de Barcelona supported by INTERCAMPUS Program E.AL 2000. The second author was partially supported by Grants 2000SGR-0007 of D. G. R. of Generalitat de Catalunya and PB 97-0888 of D. G. I. C. Y. T. of Spain. Mathematics Subject classification (2000): 03B50, 03B52, 03G25, 06D35 Keywords or Phrases: Basic fuzzy logic – Łukasiewicz logic – BL-algebras – MV-algebras – Glivenko's theorem     

Combinatorial and Arithmetical Properties of Linear Numeration Systems

Dedicated to the memory of Paul Erdős We extend a result of J. Alexander and D. Zagier on the Garsia entropy of the Erdős measure. Our investigation heavily relies on methods from combinatorics on words. Furthermore, we introduce a new singular measure related to the Farey tree. Received October 7, 1999 RID="†" ID="†" This author is supported by the START-project Y96-MAT of the Austrian Science Fund RID="‡" ID="‡" This author is supported by the Austrian Science Fund (FWF) grant P14200-MAT RID="*" ID="*" This author is supported by the Austrian Science Fund (FWF) grant S8307-MAT     

Natural dualities for varieties of BL-algebras

BL-algebras are the Lindenbaum algebras for Hájek's Basic Logic, just as Boolean algebras correspond to the classical propositional calculus. The finite totally ordered BL-algebras are ordinal sums of MV-chains. We develop a natural duality, in the sense of Davey and Werner, for each subvariety generated by a finite BL-chain, and we use it to describe the injective and the weak injective members of these classes. The preliminary research for this paper was carried out while the second author was visiting Salerno University. The second author would like to thank the first author and Salerno University for their hospitality. The second author acknowledges partial supports from Salerno University and from the belgian Fonds National de la Recherche Scientifique.     

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.     

Projective semimodules

In this paper we represent a projective semimodule as a retract of a direct sum of its countably generated projective retracts with zero intersection. A characterization by means of congruences is also given. Received May 17, 1999; accepted in final form March 13, 2002. RID="h1" ID="h1"This research was supported by ESF grant 4912 and the Fulbright Fellow award.?The author would like to thank the referee for helpful remarks.     

Flat and weakly flat projection algebras

The notion of a projection algebra was first introduced in [4] by Ehrig et al. as an algebraic version of ultrametric spaces. Computer scientists use this notion as a convenient means of algebraic specification of process algebras. Some algebraic notions regarding these algebras have been studied in [1], [2], [5]. The flat projection algebras have been investigated by the authors in [1]. Here we completely characterize flat and weakly flat (m-separated and separated) projection algebras. Received November 19, 2001; accepted in final form December 1, 2002. RID="h1" ID="h1"     

Convergence analysis and error estimates for a parallel algorithm for solving the Navier-Stokes equations

Summary. This paper is concerned with the analysis of the convergence and the derivation of error estimates for a parallel algorithm which is used to solve the incompressible Navier-Stokes equations. As usual, the main idea is to split the main differential operator; this allows to consider independently the two main difficulties, namely nonlinearity and incompressibility. The results justify the observed accuracy of related numerical results. Received April 20, 2001 / Revised version received May 21, 2001 / Published online March 8, 2002 RID="*" ID="*" Partially supported by D.G.E.S. (Spain), Proyecto PB98–1134 RID="**" ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986 RID="**" ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986 RID="*" ID="*" Partially supported by D.G.E.S. (Spain), Proyecto PB98–1134 RID="**" ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986 RID="**" ID="**" Partially supported by D.G.E.S. (Spain) Proyecto PB96–0986     

The completeness of the isomorphism relation for countable Boolean algebras

We show that the isomorphism relation for countable Boolean algebras is Borel complete, i.e., the isomorphism relation for arbitrary countable structures is Borel reducible to that for countable Boolean algebras. This implies that Ketonen's classification of countable Boolean algebras is optimal in the sense that the kind of objects used for the complete invariants cannot be improved in an essential way. We also give a stronger form of the Vaught conjecture for Boolean algebras which states that, for any complete first-order theory of Boolean algebras that has more than one countable model up to isomorphism, the class of countable models for the theory is Borel complete. The results are applied to settle many other classification problems related to countable Boolean algebras and separable Boolean spaces. In particular, we will show that the following equivalence relations are Borel complete: the translation equivalence between closed subsets of the Cantor space, the isomorphism relation between ideals of the countable atomless Boolean algebra, the conjugacy equivalence of the autohomeomorphisms of the Cantor space, etc. Another corollary of our results is the Borel completeness of the commutative AF -algebras, which in turn gives rise to similar results for Bratteli diagrams and dimension groups.

     

On some types of radical classes

Let be an infinite cardinal. We denote by the collection of all -representable Boolean algebras. Further, let be the collection of all generalized Boolean algebras B such that for each b ∈ B, the interval [0, b] of B belongs to . In this paper we prove that is a radical class of generalized Boolean algebras. Further, we investigate some related questions concerning lattice ordered groups and generalized MV-algebras. This work was supported by Science and Technology Assistance Agency under the contract No. APVT-51-032002. This work has been partially supported by the Slovak Academy of Sciences via the project Center of Excellence-Physics of Information.     

Kites and pseudo BL-algebras

We investigate a construction of a pseudo BL-algebra out of an ?-group called a kite. We show that many well-known examples of algebras related to fuzzy logics can be obtained in that way. We describe subdirectly irreducible kites. As another application, we exhibit a new countably infinite family of varieties of pseudo BL-algebras covering the variety of Boolean algebras.     

Strongly meager and strong measure zero sets

 In this paper we present two consistency results concerning the existence of large strong measure zero and strongly meager sets. RID="ID=" <E5>Mathematics Subject Classification (2000):</E5>&ensp;03E35 RID="ID=" The first author was supported by Alexander von Humboldt Foundation and NSF grant DMS 95-05375. The second author was partially supported by Basic Research Fund, Israel Academy of Sciences, publication 658 Received: 6 January 1999 / Revised version: 20 July 1999 / Published online: 25 February 2002 RID=" ID=" <E5>Mathematics Subject Classification (2000):</E5>&ensp;03E35 RID=" ID=" The first author was supported by Alexander von Humboldt Foundation and NSF grant DMS 95-05375. The second author was partially supported by Basic Research Fund, Israel Academy of Sciences, publication 658     

Computable Homogeneous Boolean Algebras and a Metatheorem

We consider computable homogeneous Boolean algebras. Previously, countable homogeneous Boolean algebras have been described up to isomorphism and a simple criterion has been found for the existence of a strongly constructive (decidable) isomorphic copy for such. We propose a natural criterion for the existence of a constructive (computable) isomorphic copy. For this, a new hierarchy of -computable functions and sets is introduced, which is more delicate than Feiner's. Also, a metatheorem is proved connecting computable Boolean algebras and their hyperarithmetical quotient algebras.     

A coalgebraic approach to quasigroup permutation representations

The paper identifies the class of all permutation representations of a given finite quasigroup as a covariety of coalgebras. Each permutation representation decomposes as a sum of homomorphic images of homogeneous spaces. For a group, permutation representations in the present sense specialise to the classical concept. Burnside's Lemma, with a new proof, is extended from groups to quasigroups. Received March 13, 2002; accepted in final form September 18, 2002. RID="h1" ID="h1"This paper was written while the author was a guest of the Institute of Mathematics and Information Sciences at Warsaw University of Technology, on Faculty Professional Development Assignment from Iowa State University.     

Solid varieties of arbitrary type

A solid variety is an equational class in which every identity holds as a hyperidentity as well, meaning that it is satisfied not just by the fundamental operations but also by all terms of the appropriate arity. For type (2), an infinite number of solid varieties (of semigroups) are known, but for other types very few examples of solid varieties are known. In this paper we present several constructions which produce infinite chains of solid varieties. One construction generalizes the normalization of a variety, and gives a method to produce a chain of solid varieties from any given solid variety of type (n). The second construction generalizes the rectangular nilpotent varieties of type (2) to type (n). Finally, we use identities which are consequences of idempotency to construct an infinite chain of solid varieties of any fixed type. Received March 23, 2001; accepted in final form July 11, 2002. RID="h1" ID="h1"Research of the third author was supported by NSERC of Canada.     

Implicative twist-structures

The twist-structure construction is used to represent algebras related to non-classical logics (e.g., Nelson algebras, bilattices) as a special kind of power of better-known algebraic structures (distributive lattices, Heyting algebras). We study a specific type of twist-structure (called implicative twist-structure) obtained as a power of a generalized Boolean algebra, focusing on the implication-negation fragment of the usual algebraic language of twist-structures. We prove that implicative twist-structures form a variety which is semisimple, congruence-distributive, finitely generated, and has equationally definable principal congruences. We characterize the congruences of each algebra in the variety in terms of the congruences of the associated generalized Boolean algebra. We classify and axiomatize the subvarieties of implicative twist-structures. We define a corresponding logic and prove that it is algebraizable with respect to our variety.     

A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs

 The authors of this paper recently introduced a transformation [4] that converts a class of semidefinite programs (SDPs) into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods to handle efficiently. Based on the transformation, we proposed a globally convergent, first-order (i.e., gradient-based) log-barrier algorithm for solving a class of linear SDPs. In this paper, we discuss an efficient implementation of the proposed algorithm and report computational results on semidefinite relaxations of three types of combinatorial optimization problems. Our results demonstrate that the proposed algorithm is indeed capable of solving large-scale SDPs and is particularly effective for problems with a large number of constraints. Received: June 22, 2001 / Accepted: January 20, 2002 Published online: December 9, 2002 RID="†" ID="†"Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired in part with support from NSF Grant DMS-9872009. RID="⋆" ID="⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203426 RID="⋆⋆" ID="⋆⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203113 RID="⋆⋆⋆" ID="⋆⋆⋆"This author was supported in part by DOE Grant DE-FG03-97ER25331, DOE/LANL Contract 03891-99-23 and NSF Grant DMS-9973339. Key Words. semidefinite program – semidefinite relaxation – nonlinear programming – interior-point methods – limited memory quasi-Newton methods. Mathematics Subject Classification (1991): 90C06, 90C27, 90C30.