Interdefinability of timelike, lightlike and spacelike relatedness of Minkowski spacetime is investigated in detail in the paper, with the aim of finding the simplest definitions. Based on ideas scattered in the literature, definitions are given between any two of these binary relations that use 4 variables, i.e., they use only 2 auxiliary variables. All these definitions work over arbitrary Euclidean fields in place of the field of reals, if the dimension n of spacetime is greater than two. If n=2, the definitions work over arbitrary ordered fields except the ones based on lightlike relatedness (where no definition can work by symmetry). None of these relations can be defined from another one using only one auxiliary variable. These definitions use only one universal and one existential quantifiers in a specific order. In some of the cases, we show that the order of these quantifiers can be reversed for the price of using twice as many quantifiers. Except in two cases, we provide existential/universal definitions using 3 auxiliary variables or show that no existential/universal definition exists. There are no existential/universal definitions between any two of these relations using only 2 auxiliary variables. It remains open whether there is an existential (universal) definition of timelike (lightlike) relatedness from spacelike relatedness if n>2. Finally, several other open problems related to the quantifier complexity of the simplest possible definitions are given.

Abstract We prove that the two-variable fragment of first-order logic has the weak Beth definability property. This makes the two-variable fragment a natural logic separating the weak and the strong Beth properties since it does not have the strong Beth definability property.

Abstract Givant [6] generalized the notion of an atomic pair-dense relation algebra from Maddux [13] by defining the notion of a measurable relation algebra, that is to say, a relation algebra in which the identity element is a sum of atoms that can be measured in the sense that the “size” of each such atom can be defined in an intuitive and reasonable way (within the framework of the first-order theory of relation algebras). In Andréka--Givant [2], a large class of examples of such algebras is constructed from systems of groups, coordinated systems of isomorphisms between quotients of the groups, and systems of cosets that are used to “shift” the operation of relative multiplication. In Givant--Andréka [8], it is shown that the class of these full coset relation algebras is adequate to the task of describing all measurable relation algebras in the sense that every atomic and complete measurable relation algebra is isomorphic to a full coset relation algebra. Call an algebra $\mathfrak{A}$ a coset relation algebra if $\mathfrak{A}$ is embeddable into some full coset relation algebra. In the present article, it is shown that the class of coset relation algebras is equationally axiomatizable (that is to say, it is a variety), but that no finite set of sentences suffices to axiomatize the class (that is to say, the class is not finitely axiomatizable).

Abstract It is shown that Tarski’s set of ten axioms for the calculus of relations is independent in the sense that no axiom can be derived from the remaining axioms. It is also shown that by modifying one of Tarski’s axioms slightly, and in fact by replacing the right-hand distributive law for relative multiplication with its left-hand version, we arrive at an equivalent set of axioms which is redundant in the sense that one of the axioms, namely the second involution law, is derivable from the other axioms. The set of remaining axioms is independent. Finally, it is shown that if both the left-hand and right-hand distributive laws for relative multiplication are included in the set of axioms, then two of Tarski’s other axioms become redundant, namely the second involution law and the distributive law for converse. The set of remaining axioms is independent and equivalent to Tarski’s axiom system.

Abstract We give a novel application of algebraic logic to first order logic. A new, flexible construction is presented for representable but not completely representable atomic relation and cylindric algebras of dimensionn(for finiten> 2) with the additional property that they are one-generated and the set of allnbynatomic matrices forms a cylindric basis. We use this construction to show that the classical Henkin-Orey omitting types theorem fails for the finite variable fragments of first order logic as long as the number of variables available is > 2 and we have a binary relation symbol in our language. We also prove a stronger result to the effect that there is no finite upper bound for the extra variables needed in the witness formulas. This result further emphasizes the ongoing interplay between algebraic logic and first order logic.

The paper is a theoretical study of a generalization of the lexicographic rule for combining ordering relations. We define the concept of priority operator: a priority operator maps a family of relations to a single relation which represents their lexicographic combination according to a certain priority on the family of relations. We present four kinds of results. • We show that the lexicographic rule is the only way of combining preference relations which satisfies natural conditions (similar to those proposed by Arrow). • We show in what circumstances the lexicographic rule propagates various conditions on preference relations, thus extending Grosof's results. • We give necessary and sufficient conditions on the priority relation to determine various relationships between combinations of preferences. • We give an algebraic treatment of this form of generalized prioritization. Two operators, called but and on the other hand, are sufficient to express any prioritization. We present a complete equational axiomatization of these two operators. These results can be applied in the theory of social choice (a branch of economics), in non‐monotonic reasoning (a branch of artificial intelligence), and more generally wherever relations have to be combined.

Abstract Using a combinatorial theorem of Herwig on extending partial isomorphisms of relational structures, we give a simple proof that certain classes of algebras, including Crs, polyadic Crs, and WA, have the ‘finite base property’ and have decidable universal theories, and that any finite algebra in each class is representable on a finite set.

This paper explores algebraic aspects of two modifications of the usual account of first-order quantifiers. Standard first-order quantificational logic is modelled algebraically by cylindric algebras. Prime examples of these are algebras whose members are sets of sequences: given a first-order model U for a language that is based on the set {υκ: κ < α} of variables, each formula φ is represented by the set of all those α-length sequences x = 〈xκ: κ < α〉 that satisfy φ in U. Such a sequence provides a value-assignment to the variables (υκ is assigned value xκ), but it may also be viewed geometrically as a point in the α-dimensional Cartesian spaceαU of all α-length sequences whose terms come from the underlying set U of U. Then existential quantification is represented by the operation of cylindrification. To explain this, define a binary relation Tκ on sequences by putting xTκy if and only if x and y differ at most at their κth coordinate, i.e., Then for any set X ⊆ αU, the set is the “cylinder” generated by translation of X parallel to the κth coordinate axis in αU. Given the standard semantics for the existential quantifier ∃υκ as it is evident that

Abstract We investigate in an algebraic setting the question of which logical languages can express the properties integral, permutational, and rigid for algebras of relations.

Jónsson and Tarski [1951] introduced the notion of a Boolean algebra with (additive) operators (for short, a Bo). They showed that every Bo can be extended to a complete and atomic Bo satisfying certain additional conditions, and that any two complete, atomic extensions of satisfying these conditions are isomorphic over . Henkin [1970] extended these results to Boolean algebras with generalized (i.e., weakly additive) operators. The particular complete, atomic extension of studied by Jónsson and Tarski is called the perfect extension of , and is denoted by +. It is very useful in algebraic investigations of classes of algebras that are associated with logics. Interesting examples of Bos abound in algebraic logic, and include relation algebras, cylindric algebras, and polyadic and quasi-polyadic algebras (with or without equality). Moreover, there are several important constructions that, when applied to certain Bos, lead to other, derived Bos. Obvious examples include the formation of subalgebras, homomorphic images, relativizations, and direct products. Other examples include the Boolean algebra of ideal elements of a Bo, the neat β;-reduct of an α-dimensional cylindric algebra (β; < α), and the relation algebraic reduct of a cylindric algebra (of dimension at least 3). It is natural to ask about the relationship between the perfect extension of a Bo and the perfect extension of one of its derived algebras ′: Is the perfect extension of the derived algebra just the derived algebra of the perfect extension? In symbols, is ( ′)+ = ( +)′? For example, is the perfect extension of a subalgebra, homomorphic image, relativization, or direct product, just the corresponding subalgebra, homomorphic image, relativization, or direct product of the perfect extension (up to isomorphisms)? Is the perfect extension of the Boolean algebra of ideal elements, or the neat reduct of a cylindric algebra, or the relation algebraic reduct of a cylindric algebra just the Boolean algebra of ideal elements, or the neat β;-reduct, or the relation algebraic reduct, of the perfect extension? We shall prove a general result in this direction; namely, if the derived algebra is constructed as the range of a relatively multiplicative operator, then the answer to our question is “yes”. We shall also give examples to show that in “infinitary” constructions, our question can have a spectacularly negative answer.

Abstract We shall show that certain natural and interesting intervals in the lattice of varieties of representable relation algebras embed the lattice of all subsets of the natural numbers, and therefore must have a very complicated lattice-theoretic structure.

Abstract. One of the basic theorems in universal algebra is Birkhoff's variety theorem: the smallest equationally axiomatizable class containing a classKof algebras coincides with the class obtained by taking homomorphic images of subalgebras of direct products of elements ofK. G. Grätzer asked whether the variety theorem is equivalent to the Axiom of Choice. In 1980, two of the present authors proved that Birkhoff's theorem can already be derived inZF. Surprisingly, the Axiom of Foundation plays a crucial role here: we show that Birkhoff's theorem cannot be derived inZF+AC\{Foundation}, even if we add Foundation for Finite Sets. We also prove that the variety theorem is equivalent to a purely set-theoretical statement, the Collection Principle. This principle is independent ofZF\{Foundation}. The second part of the paper deals with further connections between axioms ofZF-set theory and theorems of universal algebra.

Abstract In this note we prove that the abstract property “weakly subdirectly indecomposable” does not characterize the class IWsα of weak cylindric set algebras. However, we give another (similar) abstract property characterizing IWsα. The original property does characterize the directed unions of members of IWsα iff α is countable. Free algebras will be shown to satisfy the original property.

Ordinary equational logic is a connective-free fragment of first-order logic which is concerned with total functions under the relation of ordinary equality. In [AN] (see also [AN1]) and in [Cr] it has been extended in two equivalent ways into a near-equational system of logic for partial functions. The extension given in [Cr] deals with partial functions under two relationships: a relationship of existence-dependent existence and one of existence-dependent Kleene equality. For the language that involves both relationships a set of rules was given that is complete. Those rules in the set that involve only existence-dependent existence turned out to be complete for the sublanguage that involves this relationship only. In the present paper we give a set of rules that is complete for the other sublanguage, namely the language of partial functions under existence-dependent Kleene equality. This language lacks a certain, often needed, power of expressing existence and fails, in particular, to be an extension of the language that underlies ordinary equational logic. That it possesses a fairly simple complete set of rules is therefore perhaps more of theoretical than of practical interest. The present paper is thus intended to serve as a supplement to [Cr] and, less directly, to [AN]. The subject is further rounded out, and some contrast is provided, by [Rob]. The systems of logic treated there are based on the weaker language in which partial functions are considered under the more basic relation of Kleene equality.

The theory of cylindric algebras (CA's) is the algebraic theory of first order logics. Several ideas about logic are easier to formulate in the frame of CA-theory. Such are e.g. some concepts of abstract model theory (cf. [1] and [10]–[12]) as well as ideas about relationships between several axiomatic theories of different similarity types (cf. [4] and [10]). In contrast with the relationship between Boolean algebras and classical propositional logic, CA's correspond not only to classical first order logic but also to several other ones. Hence CA-theoretic results contain more information than their counterparts in first order logic. For more about this see [1], [3], [5], [9], [10] and [12]. Here we shall use the notation and concepts of the monographs Henkin-Monk-Tarski [7] and [8]. ω denotes the set of natural numbers. CAα denotes the class of all cylindric algebras of dimension α; by “a CAα” we shall understand an element of the class CAα. The class Dcα ⊆ CAα was defined in [7]. Note that Dcα = 0 for α ∈ ω. The classes Wsα, and Csα were defined in 1.1.1 of [8], p. 4. They are called the classes of all weak cylindric set algebras, regular cylindric set algebras and cylindric set algebras respectively. It is proved in [8] (I.7.13, I.1.9) that ⊆ CAα. (These inclusions are proper by 7.3.7, 1.4.3 and 1.5.3 of [8].) It was proved in 2.3.22 and 2.3.23 of [7] that every simple, finitely generated Dcα is generated by a single element. This is the algebraic counterpart of a property of first order logics (cf. 2.3.23 of [7]). The question arose: for which simple CAα's does “finitely generated” imply “generated by a single element” (see p. 291 and Problem 2.3 in [7]). In terms of abstract model theory this amounts to asking the question: For which logics does the property described in 2.3.23 of [7] hold? This property is roughly the following. In any maximal theory any finite set of concepts is definable in terms of a single concept. The connection with CA-theory is that maximal theories correspond to simple CA's (the elements of which are the concepts of the original logic) and definability corresponds to generation.