Covering in the lattice of equational theories and some properties of term finite theories

For countable languages, we completely describe those cardinals κ such that there is an equational theory which covers exactly κ other equational theories. For this task understanding term finite theories is helpful. A theoryT isterm finite provided {ψ:Tτϕ≈ψ} is finite for all terms ϕ. We develop here some fundamental properties of term finite theories and use them, together with Ramsey's Theorem, to prove that any finitely based term finite theory covers only finitely many others. We also show that every term finite theory possesses an independent base and that there are such theories whose pairwise joins are not term finite. The paper was written with the support of NSF Grant MCS-80-01778. Presented by B. Jónsson. Received July 22, 1980. Accepted for publication in final form March 19, 1981.     

Definable principal subcongruences

For varieties of algebras, we present the property of having "definable principal subcongruences" (DPSC), generalizing the concept of having definable principal congruences. It is shown that if a locally finite variety V of finite type has DPSC, then V has a finite equational basis if and only if its class of subdirectly irreducible members is finitely axiomatizable. As an application, we prove that if A is a finite algebra of finite type whose variety V(A) is congruence distributive, then V(A) has DPSC. Thus we obtain a new proof of the finite basis theorem for such varieties. In contrast, it is shown that the group variety V(S ₃ ) does not have DPSC. Received May 9 2000; accepted in final form April 26, 2001.     

Theories of linear order

LetT be a complete theory of linear order; the language ofT may contain a finite or a countable set of unary predicates. We prove the following results. (i) The number of nonisomorphic countable models ofT is either finite or 2^ω. (ii) If the language ofT is finite then the number of nonisomorphic countable models ofT is either 1 or 2^ω. (iii) IfS ₁(T) is countable then so isS _n(T) for everyn. (iv) In caseS ₁(T) is countable we find a relation between the Cantor Bendixon rank ofS ₁(T) and the Cantor Bendixon rank ofS _n(T). (v) We define a class of modelsL, and show thatS ₁(T) is finite iff the models ofT belong toL. We conclude that ifS ₁(T) is finite thenT is finitely axiomatizable. (vi) We prove some theorems concerning the existence and the structure of saturated models. Most of the results in this paper appeared in the author’s Master of Science thesis which was prepared at the Hebrew University under the supervision of Professor H. Gaifman.     

Definability in the lattice of equational theories of commutative semigroups

In this paper we study first-order definability in the lattice of equational theories of commutative semigroups. In a series of papers, J. Jezek, solving problems posed by A. Tarski and R. McKenzie, has proved, in particular, that each equational theory is first-order definable in the lattice of equational theories of a given type, up to automorphism, and that such lattices have no automorphisms besides the obvious syntactically defined ones (with exceptions for special unary types). He has proved also that the most important classes of theories of a given type are so definable. In a later paper, Jezek and McKenzie have ``almost proved" the same facts for the lattice of equational theories of semigroups. There were good reasons to believe that the same can be proved for the lattice of equational theories of commutative semigroups. In this paper, however, we show that the case of commutative semigroups is different.

     

Decidability of Equational Theories of Coverings of Semigroup Varieties

For every proper semigroup variety X, there exists a semigroup variety Y satisfying the following three conditions: (1) Y covers X, (2) if X is finitely based then so is Y, and (3) the equational theory of X is decidable if and only if so is the equational theory of Y. If X is an arbitrary semigroup variety defined by identities depending on finitely many variables and such that all periodic groups of X are locally finite, then one of the following two conditions holds: (1) all nilsemigroups of X are locally finite and (2) X includes a subvariety Y whose equational theory is undecidable and which has infinitely many covering varieties with undecidable equational theories.     

Definability in the Substructure Ordering of Simple Graphs

For simple graphs, we investigate and seek to characterize the properties first-order definable by the induced subgraph relation. Let \({\mathcal{P}\mathcal{G}}\) denote the set of finite isomorphism types of simple graphs ordered by the induced subgraph relation. We prove this poset has only one non-identity automorphism co, and for each finite isomorphism type G, the set {G, G ^co } is definable. Furthermore, we show first-order definability in \({\mathcal{P}\mathcal{G}}\) captures, up to isomorphism, full second-order satisfiability among finite simple graphs. These results can be utilized to explore first-order definability in the closely associated lattice of universal classes. We show that for simple graphs, the lattice of universal classes has only one non-trivial automorphism, the set of finitely generated and finitely axiomatizable universal classes are separately definable, and each such universal subclass is definable up to the unique non-trivial automorphism.     

Definability in substructure orderings, I: finite semilattices

We investigate definability in the set of isomorphism types of finite semilattices ordered by embeddability; we prove, among other things, that every finite semilattice is a definable element in this ordered set. Then we apply these results to investigate definability in the closely related lattice of universal classes of semilattices; we prove that the lattice has no non-identical automorphisms, the set of finitely generated and also the set of finitely axiomatizable universal classes are definable subsets and each element of the two subsets is a definable element in the lattice.     

On generators and relations for unions of semigroups

Finite generation and presentability of general unions of semigroups, as well as of bands of semigroups, bands of monoids, semilattices of semigroups and strong semilattices of semigroups, are investigated. For instance, it is proved that a band Y of monoids S _α (α∈ Y ) is finitely generated/presented if and only if Y is finite and all S _α are finitely generated/presented. By way of contrast, an example is exhibited of a finitely generated semigroup which is not finitely presented, but which is a disjoint union of two finitely presented subsemigroups. January 21, 2000     

Para primal varieties: A study of finite axiomatizability and definable principal congruences in locally finite varieties

We introduce new sufficient conditions for a finite algebraU to possess a finite basis of identities. The conditions are that the variety generated byU possess essentially only finitely many subdirectly irreducible algebras, and have definable principal congruences. Both conditions are satisfied if this variety is directly representable by a finite set of finite algebras. One task of the paper is to show that virtually no lattice varieties possess definable principal congruences. However, the main purpose of the paper is to apply the new criterion in proving that every para primal variety (congruence permutable variety generated by finitely many para primal algebras) is finitely axiomatizable. The paper also contains a completely new approach to the structure theory of para primal varieties which complements and extends somewhat the recent work of Clark and Krauss.     

Definability in substructure orderings, III: Finite distributive lattices

Let ${{\mathcal D}}$ be the ordered set of isomorphism types of finite distributive lattices, where the ordering is by embeddability. We study first-order definability in this ordered set. We prove among other things that for every finite distributive lattice D, the set {d, d ^opp} is definable, where d and d ^opp are the isomorphism types of D and its opposite (D turned upside down). We prove that the only non-identity automorphism of ${{\mathcal D}}$ is the opposite map. Then we apply these results to investigate definability in the closely related lattice of universal classes of distributive lattices. We prove that this lattice has only one non-identity automorphism, the opposite map; that the set of finitely generated and also the set of finitely axiomatizable universal classes are definable subsets of the lattice; and that for each element K of the two subsets, {K, K ^opp} is a definable subset of the lattice.     

The modal logic of the countable random frame

 We study the modal logic M L ^r of the countable random frame, which is contained in and `approximates' the modal logic of almost sure frame validity, i.e. the logic of those modal principles which are valid with asymptotic probability 1 in a randomly chosen finite frame. We give a sound and complete axiomatization of M L ^r and show that it is not finitely axiomatizable. Then we describe the finite frames of that logic and show that it has the finite frame property and its satisfiability problem is in EXPTIME. All these results easily extend to temporal and other multi-modal logics. Finally, we show that there are modal formulas which are almost surely valid in the finite, yet fail in the countable random frame, and hence do not follow from the extension axioms. Therefore the analog of Fagin's transfer theorem for almost sure validity in first-order logic fails for modal logic. Received: 1 May 2000 / Revised version: 29 July 2001 / Published online: 2 September 2002 Mathematics Subject Classification (2000): 03B45, 03B70, 03C99 Key words or phrases: Modal logic – Random frames – Almost sure frame validity – Countable random frame – Axiomatization – Completeness     

Oligomorphic clones

A permutation group on a countably infinite domain is called oligomorphic if it has finitely many orbits of finitary tuples. We define a clone on a countable domain to be oligomorphic if its set of permutations forms an oligomorphic permutation group. There is a close relationship to ω-categorical structures, i.e., countably infinite structures with a first-order theory that has only one countable model, up to isomorphism. Every locally closed oligomorphic permutation group is the automorphism group of an ω-categorical structure, and conversely, the canonical structure of an oligomorphic permutation group is an ω-categorical structure that contains all first-order definable relations. There is a similar Galois connection between locally closed oligomorphic clones and ω-categorical structures containing all primitive positive definable relations. In this article we generalise some fundamental theorems of universal algebra from clones over a finite domain to oligomorphic clones. First, we define minimal oligomorphic clones, and present equivalent characterisations of minimality, and then generalise Rosenberg’s five types classification to minimal oligomorphic clones. We also present a generalisation of the theorem of Baker and Pixley to oligomorphic clones. Presented by A. Szendrei. Received July 12, 2005; accepted in final form August 29, 2006.     

Fields interpretable in rosy theories

We are working in a monster model ℭ of a rosy theory T. We prove the following theorems, generalizing the appropriate results from the finite Morley rank case and o-minimal structures. If R is a ⋁-definable integral domain of positive, finite U^t-rank, then its field of fractions is interpretable in ℭ. If A and M are infinite, definable, abelian groups such that A acts definably and faithfully on M as a group of automorphisms, M is A-minimal and U^t(M) is finite, then there is an infinite field interpretable in ℭ. If G is an infinite, solvable but non nilpotent-by-finite, definable group of finite U^t-rank and T has NIP, then there is an infinite field interpretable in 〈G, ·〉.     

Triviality of the peripheral point spectrum

If T_t = e^Zt is a positive one-parameter contraction semigroup acting on l^p(X) where X is a countable set and 1 ≤ p < ∞, then the peripheral point spectrum P of Z cannot contain any non-zero elements. The same holds for Feller semigroups acting on L^p(X) if X is locally compact.     

Definability for equational theories of commutative groupoids

We find several large classes of equations with the property that every automorphism of the lattice of equational theories of commutative groupoids fixes any equational theory generated by such equations, and every equational theory generated by finitely many such equations is a definable element of the lattice. We conjecture that the lattice has no non-identical automorphisms.     

Gradings and Derived Categories

Let G{{\mathcal G}} be a group, Λ a G{{\mathcal G}}-graded Artin algebra and gr(Λ) denote the category of finitely generated G{{\mathcal G}}-graded Λ-modules. This paper provides a framework that allows an extension of tilting theory to D^b(gr(L)){{\mathcal D}}^b(\rm gr(\Lambda)) and to study connections between the tilting theories of D^b(L){{\mathcal D}}^b(\Lambda) and D^b(gr(L)){{\mathcal D}}^b(\rm gr(\Lambda)). In particular, using that if T is a gradable Λ-module, then a grading of T induces a G{{\mathcal G}}-grading on End_Λ(T), we obtain conditions under which a derived equivalence induced by a gradable Λ-tilting module T can be lifted to a derived equivalence between the derived categories D^b(gr(L)){{\mathcal D}}^b(\rm gr(\Lambda)) and D^b(gr(End_L(T))){{\mathcal D}}^b(\rm gr(\rm End_{\Lambda}(\textit T))).     

On notions of representability for cylindric‐polyadic algebras,and a solution to the finitizability problem for quantifier logics with equality

We consider countable so‐called rich subsemigroups of ; each such semigroup T gives a variety CPEA_T that is axiomatizable by a finite schema of equations taken in a countable subsignature of that of ω‐dimensional cylindric‐polyadic algebras with equality where substitutions are restricted to maps in T. It is shown that for any such T, if and only if is representable as a concrete set algebra of ω‐ary relations. The operations in the signature are set‐theoretically interpreted like in polyadic equality set algebras, but such operations are relativized to a union of cartesian spaces that are not necessarily disjoint. This is a form of guarding semantics. We show that CPEA_T is canonical and atom‐canonical. Imposing an extra condition on T, we prove that atomic algebras in CPEA_T are completely representable and that CPEA_T has the super amalgamation property. If T is rich and finitely represented, it is shown that CPEA_T is term definitionally equivalent to a finitely axiomatizable Sahlqvist variety. Such semigroups exist. This can be regarded as a solution to the central finitizability problem in algebraic logic for first order logic with equality if we do not insist on full fledged commutativity of quantifiers. The finite dimensional case is approached from the view point of guarded and clique guarded (relativized) semantics of fragments of first order logic using finitely many variables. Both positive and negative results are presented.     

Finite axiomatizability in ?ukasiewicz logic

We classify every finitely axiomatizable theory in infinite-valued propositional ?ukasiewicz logic by an abstract simplicial complex (V,Σ) equipped with a weight function ω:V→{1,2,…}. Using the W?odarczyk–Morelli solution of the weak Oda conjecture for toric varieties, we then construct a Turing computable one–one correspondence between (Alexander) equivalence classes of weighted abstract simplicial complexes, and equivalence classes of finitely axiomatizable theories, two theories being equivalent if their Lindenbaum algebras are isomorphic. We discuss the relationship between our classification and Markov’s undecidability theorem for PL-homeomorphism of rational polyhedra.     

On equational theories of varieties of anticommutative rings

The existence of a finitely based variety of anticommutative rings (in the sense of the identityx ²=0) with unsolvable equational theory is proved. Translated fromMatematicheskie Zametki, Vol. 65, No. 2, pp. 230–245, February, 1999.     

On Vaught’s Conjecture and finitely valued MV algebras

We show that the complete first order theory of an MV algebra has $2^{\aleph _0}$ countable models unless the MV algebra is finitely valued. So, Vaught's Conjecture holds for all MV algebras except, possibly, for finitely valued ones. Additionally, we show that the complete theories of finitely valued MV algebras are $2^{\aleph _0}$ and that all ω‐categorical complete theories of MV algebras are finitely axiomatizable and decidable. As a final result we prove that the free algebra on countably many generators of any locally finite variety of MV algebras is ω‐categorical.