A characterization of free generating sets in MV-algebras

MV-algebras are a generalization of Boolean algebras. As is well known, a free generating set for a Boolean algebra is characterized by the following simple algebraic condition: whenever A and B are finite disjoint subsets of X then . Our aim in this note is to give a similar characterization of free generating sets in MV-algebras. Received January 30, 2005; accepted in final form March 13, 2007.     

A theory of recursive dimension for ordered sets

The classical theorem of R. P. Dilworth asserts that a partially ordered set of width n can be partitioned into n chains. Dilworth's theorem plays a central role in the dimension theory of partially ordered sets since chain partitions can be used to provide embeddings of partially ordered sets in the Cartesian product of chains. In particular, the dimension of a partially-ordered set never exceeds its width. In this paper, we consider analogous problems in the setting of recursive combinatorics where it is required that the partially ordered set and any associated partition or embedding be described by recursive functions. We establish several theorems providing upper bounds on the recursive dimension of a partially ordered set in terms of its width. The proofs are highly combinatorial in nature and involve a detailed analysis of a 2-person game in which one person builds a partially ordered set one point at a time and the other builds the partition or embedding.This paper was prepared while the authors were supported, in part, by NSF grant ISP-80-11451. In addition, the second author received support under NSF grant MCS-80-01778 and the third author received support under NSF grant MCS-82-02172.     

Arithmetical complexity of fuzzy predicate logics — A survey II

Results on arithmetical complexity of important sets of formulas of several fuzzy predicate logics (tautologies, satisfiable formulas, …) are surveyed and some new results are proven.     

Topo-canonical completions of closure algebras and Heyting algebras

We introduce and investigate topo-canonical completions of closure algebras and Heyting algebras. We develop a duality theory that is an alternative to Esakia’s duality, describe duals of topo-canonical completions in terms of the Salbany and Banaschewski compactifications, and characterize topo-canonical varieties of closure algebras and Heyting algebras. Consequently, we show that ideal completions preserve no identities of Heyting algebras. We also characterize definable classes of topological spaces. Received January 20, 2006; accepted in final form September 12, 2006.     

Locally finite varieties of Heyting algebras

We show that for a variety of Heyting algebras the following conditions are equivalent: (1) is locally finite; (2) the -coproduct of any two finite -algebras is finite; (3) either coincides with the variety of Boolean algebras or finite -copowers of the three element chain are finite. We also show that a variety of Heyting algebras is generated by its finite members if, and only if, is generated by a locally finite -algebra. Finally, to the two existing criteria for varieties of Heyting algebras to be finitely generated we add the following one: is finitely generated if, and only if, is residually finite. Received November 11, 2001; accepted in final form July 25, 2005.     

On the topology of graph picture spaces

We study the space of pictures of a graph G in complex projective d-space. The main result is that the homology groups (with integer coefficients) of are completely determined by the Tutte polynomial of G. One application is a criterion in terms of the Tutte polynomial for independence in the d-parallel matroids studied in combinatorial rigidity theory. For certain special graphs called orchards, the picture space is smooth and has the structure of an iterated projective bundle. We give a Borel presentation of the cohomology ring of the picture space of an orchard, and use this presentation to develop an analogue of the classical Schubert calculus.     

Subreducts of MV-algebras with product and product residuation

Recently, MV-algebras with product have been investigated from different points of view. In particular, in [EGM01], a variety resulting from the combination of MV-algebras and product algebras (see [H98]) has been introduced. The elements of this variety are called ŁΠ-algebras. In this paper we treat subreducts of ŁΠ-algebras, with emphasis on quasivarieties of subreducts whose basic operations are continuous in the order topology. We give axiomatizations of the most interesting classes of subreducts, and we connect them with other algebraic classes of algebras, like f-rings and Wajsberg hoops, as well as to structures of co-infinitesimals of ŁΠ-algebras. In some cases, connections are given by means of equivalences of categories.Dedicated to the Memory of Wim BlokReceived June 19, 2002; accepted in final form November 29, 2004.This revised version was published online in August 2005 with a corrected cover date.     

The normal subgroup lattice of 2-transitive automorphism groups of linearly ordered sets

Using combinatorial and model-theoretic means, we examine the structure of normal subgroup lattices N(A()) of 2-transitive automorphism groups A() of infinite linearly ordered sets (, ). Certain natural sublattices of N(A()) are shown to be Stone algebras, and several first order properties of their dense and dually dense elements are characterized within the Dedekind-completion of (, ). As a consequence, A() has either precisely 5 or at least 2²¹ (even maximal) normal subgroups, and various other group- and lattice-theoretic results follow.     

The Caporaso–Harris formula and plane relative Gromov-Witten invariants in tropical geometry

Some years ago Caporaso and Harris have found a nice way to compute the numbers N(d, g) of complex plane curves of degree d and genus g through 3d + g − 1 general points with the help of relative Gromov-Witten invariants. Recently, Mikhalkin has found a way to reinterpret the numbers N(d, g) in terms of tropical geometry and to compute them by counting certain lattice paths in integral polytopes. We relate these two results by defining an analogue of the relative Gromov-Witten invariants and rederiving the Caporaso–Harris formula in terms of both tropical geometry and lattice paths. H. Markwig has been funded by the DFG grant Ga 636/2.     

The Schwarz genus of the Stiefel manifold

In this paper we compute: the Schwarz genus of the Stiefel manifold _Vk(Rⁿ)$V_k({\mathbb{R}}^n)$ with respect to the action of the Weyl group _Wk:=(Z/2)^k?_Sk$W_k:={(\mathbb{Z}/2)}^k?{\mathfrak{S}}_k$, and the Lusternik–Schnirelmann category of the quotient space _Vk(Rⁿ)/_Wk$V_k({\mathbb{R}}^n)/W_k$. Furthermore, these results are used in estimating the number of critically outscribed parallelotopes around a strictly convex body, and Birkhoff–James orthogonal bases of a normed finite dimensional vector space.     

Irredundant self-dual bases for self-dual lattice varieties

For any finitely based self-dual variety of lattices, we determine the sizes of all equational bases that are both irredundant and self-dual. We make the same determination for {0, 1}-lattice varieties.Received July 11, 2002; accepted in final form August 27, 2004.     

Yet another single law for lattices

In this note we show that the equational theory of all lattices is defined by the single absorption law This identity of length 29 with 8 variables is shorter than previously known such equations defining lattices.     

Belousov equations on ternary quasigroups

Summary The study of Belousov equations in binary quasigroups was initiated by V. D. Belousov. Krape and Taylor showed that every finite set of Belousov equations was equivalent to a single Belousov equation which was in some sense no longer than any single member of the set. This led to the concept of an irreducible Belousov equation, that is one which is not equivalent to an equation with fewer variables. Krape and Taylor determined the structure of the irreducible equations by establishing a correspondence between them and specific polynomials overZ ₂.In this paper it is shown that the structure of the ternary equations is richer than the binary counterpart, although the main result is similar to the binary case in as far as a system of ternary Belousov equations is equivalent to a single Belousov equation which is no longer than any member of the system or the system is equivalent to a pair of equations each with three variables.     

Algorithmic correspondence and canonicity for distributive modal logic

We define the algorithm ALBA for the language of the same distributive modal logic (DML) for which a Sahlqvist theorem was proved by Gehrke, Nagahashi, and Venema. Successful executions of ALBA compute the local first-order correspondents of input DML inequalities, and also guarantee their canonicity. The class of inequalities on which ALBA is successful is strictly larger than the newly introduced class of inductive inequalities, which in its turn properly extends the Sahlqvist inequalities of Gehrke et al. Evidence is given to the effect that, as their name suggests, inductive inequalities are the distributive counterparts of the inductive formulas of Goranko and Vakarelov in the classical setting.