Categorical Abstract Algebraic Logic: Partially Ordered Algebraic Systems

An extension of parts of the theory of partially ordered varieties and quasivarieties, as presented by Pałasińska and Pigozzi in the framework of abstract algebraic logic, is developed in the more abstract framework of categorical abstract algebraic logic. Algebraic systems, as introduced in previous work by the author, play in this more abstract framework the role that universal algebras play in the more traditional treatment. The aim here is to build the generalized framework and to formulate and prove abstract versions of the ordered homomorphism theorems in this framework. To Don Pigozzi and Kate Pałasińska.     

Infinitary first-order categorical logic

We present a unified categorical treatment of completeness theorems for several classical and intuitionistic infinitary logics with a proposed axiomatization. This provides new completeness theorems and subsumes previous ones by Gödel, Kripke, Beth, Karp and Joyal. As an application we prove, using large cardinals assumptions, the disjunction and existence properties for infinitary intuitionistic first-order logics.     

Intuitionistic completeness of first-order logic

We constructively prove completeness for intuitionistic first-order logic, iFOL, showing that a formula is provable in iFOL if and only if it is uniformly valid in intuitionistic evidence semantics as defined in intuitionistic type theory extended with an intersection operator.     

Uncountably categorical local tame abstract elementary classes with disjoint amalgamation

We prove Baldwin-Lachlan theorem for local (LS(K)-)tame abstract elementary classes K with disjoint amalgamation property and with LS(K)=ω. Partially supported by the Academy of Finland, grant 40734.     

The modular commutator via the Gumm terms

We derive the basic properties of the congruence commutator in modular varieties using the characterization of congruence modularity due to H.-P. Gumm rather than that due to A. Day.This paper is dedicated to the memory of Alan Day, whose mathematical enthusiasm and insights were an inspiration to us all.Presented by R. Freese.     

Cut-free formulations for a quantified logic of here and there

A predicate extension SQHT⁼ of the logic of here-and-there was introduced by V. Lifschitz, D. Pearce, and A. Valverde to characterize strong equivalence of logic programs with variables and equality with respect to stable models. The semantics for this logic is determined by intuitionistic Kripke models with two worlds (here and there) with constant individual domain and decidable equality. Our sequent formulation has special rules for implication and for pushing negation inside formulas. The soundness proof allows us to establish that SQHT⁼ is a conservative extension of the logic of weak excluded middle with respect to sequents without positive occurrences of implication. The completeness proof uses a non-closed branch of a proof search tree. The interplay between rules for pushing negation inside and truth in the “there” (non-root) world of the resulting Kripke model can be of independent interest. We prove that existence is definable in terms of remaining connectives.     

The algebraic uniqueness of the addition of natural numbers

As is known, multiplication is aniteration of addition within the natural numbers. We show that addition is essentially theonly associative binary operation on natural numbers whose iteration is commutative or associative. This result, in which a set determines a structure, is in a sense a converse of the classical one due to Pontrjagin [3] and Kolmogorov [1], in which certain algebraic and topological structures determine the fields of real and complex numbers and of quaternions.     

Malliavin calculus in abstract Wiener space using infinitesimals

Using infinitesimals, we develop Malliavin calculus on spaces which result from the classical Wiener space by replacing with any abstract Wiener space .We start from a Brownian motion b on a Loeb probability space Ω with values in the Banach space is the standard part of a ∗finite-dimensional Brownian motion B. Then we define iterated Itô integrals as standard parts of internal iterated Itô integrals. The integrator of the internal integrals is B and the values of the integrands are multilinear forms on , where is a ∗finite-dimensional linear space over between the Hilbert space and its ∗-extension .In the first part we prove a chaos decomposition theorem for L²-functionals on Ω that are measurable with respect to the σ-algebra generated by b. This result yields a chaos decomposition of L²-functionals with respect to the Wiener measure on the standard space of -valued continuous functions on [0,1]. In the second part we define the Malliavin derivative and the Skorohod integral as standard parts of internal operators defined on ∗finite-dimensional spaces. In an application we use the transformation rule for finite-dimensional Euclidean spaces to study time anticipating and non-anticipating shifts of Brownian motion by Bochner integrals (Girsanov transformations).     

Bounded width problems and algebras

Let be finite relational structure of finite type, and let CSP denote the following decision problem: if is a given structure of the same type as , is there a homomorphism from to ? To each relational structure is associated naturally an algebra whose structure determines the complexity of the associated decision problem. We investigate those finite algebras arising from CSP’s of so-called bounded width, i.e., for which local consistency algorithms effectively decide the problem. We show that if a CSP has bounded width then the variety generated by the associated algebra omits the Hobby-McKenzie types 1 and 2. This provides a method to prove that certain CSP’s do not have bounded width. We give several applications, answering a question of Nešetřil and Zhu [26], by showing that various graph homomorphism problems do not have bounded width. Feder and Vardi [17] have shown that every CSP is polynomial-time equivalent to the retraction problem for a poset we call the Feder − Vardi poset of the structure. We show that, in the case where the structure has a single relation, if the retraction problem for the Feder-Vardi poset has bounded width then the CSP for the structure also has bounded width. This is used to exhibit a finite order-primal algebra whose variety admits type 2 but omits type 1 (provided P ≠ NP). Presented by M. Valeriote. Received January 8, 2005; accepted in final form April 3, 2006. The first author’s research is supported by a grant from NSERC and the Centre de Recherches Mathématiques. The second author’s research is supported by OTKA no. 034175 and 48809 and T 037877. Part of this research was conducted while the second author was visiting Concordia University in Montréal and also when the first author was visiting the Bolyai Institute in Szeged. The support of NSERC, OTKA and the Bolyai Institute is gratefully acknowledged.     

On the Clark Ocone formula for the abstract Wiener space

Fix an abstract Wiener space where is a separable Hilbert space densely embedded into a Banach space . A pathwise construction of the Itô integral as a continuous square integrable martingale is given, where the integrands are -valued processes and the integrator is a -valued Brownian motion. We use this approach to the vector integral to prove that each Malliavin differentiable functional ? defined on the space of continuous -valued functions on [0,1], endowed with the Wiener measure, can be decomposed into the sum of the expected value of ? and the Itô integral of the conditional expectation of the Malliavin derivative of ? with respect to the Brownian filtration. The Malliavin derivative of ? is an -valued stochastic process. In a second application, it is shown that the iterated Itô integral, defined as a process on , is a continuous square integrable martingale.     

On divergence of the general terms of the double Fourier-Haar series

In the present article we prove that the sequence of the general terms corresponding to the rectangular and spherical partial sums of the double Fourier-Haar series of some integrable functions do not converge almost everywhere. Received: 7 May 2005; revised: 28 June 2005     

Some of our primal algebras are missing: the canonical primal theory

It has been proven elsewhere that every variety has associated with it a unique canonical theory, where idempotent morphisms split. This article exhibits models of the canonical theory associated with any primal variety, for example, Boolean algebras. One such variety of models is generated by the several-sorted algebra with carriers of all prime cardinalities and with a clone of all finitary operations ω on and between carriers. This primal algebra was unknown. There are more. Presented by R. McKenzie. Received December 20, 2005; accepted in final form May 2, 2006.     

An algebraic structure for Faber polynomials

Let Σ be the set of functions, convergent for all |z|>1, with a Laurent series of the form f(z)=z+∑_n?0a_nz^-n. In this paper, we prove that the set of Faber polynomial sequences over Σ and the set of their normalized kth derivative sequences form groups which are isomorphic to the hitting time subgroup and the Bell^(k) subgroup of the Riordan group, respectively. Further, a relationship between such Faber polynomial sequences and Lucas and Sheffer polynomial sequences is derived.     

Few subpowers, congruence distributivity and near-unanimity terms

We prove that for any variety , the existence of an edge-term (defined in [1]) and Jónsson terms is equivalent to the existence of a near-unanimity term. We also characterize the idempotent Maltsev conditions which are defined by a system of linear absorption equations and which imply congruence distributivity. The first author was supported by the grant no. 144011G of the Ministry of Science and Environment of Serbia. The work of the second author was supported by US NSF grant no. DMS 0245622.     

On the structure of varieties with equationally definable principal congruences IV

The notion of apseudo-interior algebra is introduced; it is a hybrid of a (topological) interior algebra and a residuated partially ordered monoid. The elementary arithmetic of pseudo-interior algebras is developed leading to a simple equational axiomatization. A notion ofopen filter analogous to the open filters of interior algebras is investigated. Pseudo-interior algebras represent, in algebraic form, the logic inherent in varieties with acommutative, regular ternary deductive (TD) term p(x, y, z), which is defined by the conditions: (1)p(x,y,z) z (mod(x, y)); (2) for fixed elementsa, b of an algebra A, {p(a, b, z):z A} is a transversal of the set of equivalence classes of (a, b); (3)p(a, b, z) andp(a,b,z) define the same transversal whenever(a,b)=(a,b); (4)(p(x, y, 1), 1)= (x, y) for some constant term 1. The TD term generalizes the (affine) ternary discriminator. Varieties with a commutative, regular TD term include most of the varieties of traditional algebraic logic as well as all double-pointed affine discriminator varieties andn-potent hoops (residuated commutative po-monoids in which the partial ordering is inverse divisibility). The main theorem:A variety has a commutative, regular TD term iff it is termwise definitionally equivalent to a pseudo-interior algebra with additional operations that are compatible with the open filters in a natural way.Presented by R. W. Quackenbush.The authors gratefully acknowledge the support of National Science Foundation Grants DMS-8703743 and DMS-8805870.     

The geometry of two-dimensional symbols

We give a complex-analytic construction of the two-dimensional symbol of Parshin and Kato. Our approach leads to a new analytic formula for the symbol together with a direct proof of the reciprocity law it satisfies.     

On the congruence modularity conjecture

A new condition of compatibility with projections, applicable to some Maltsev filters, is defined and shown to hold, among others, for the filter of congruence-modular varieties. As a consequence, it is shown that there exist no simple counterexamples (in a specified sense) to the modularity conjecture. This paper is dedicated to Walter Taylor. Received November 5, 2005; accepted in final form April 3, 2006.     

A categorical characterization of varieties

A simple, direct proof of the following characterization of varieties of (finitary) algebras is presented: a cocomplete category is equivalent to a variety iff it has an algebraic generator, i.e., a regular generator which is exactly projective and finitely generated. This improves somewhat a recent restatement, due to Pedicchio and Wood, of the classical characterization theorem of Lawvere. A bijective correspondence between algebraic theories and algebraic generators is established.     

Strong normalization results by translation

We prove the strong normalization of full classical natural deduction (i.e. with conjunction, disjunction and permutative conversions) by using a translation into the simply typed λμ-calculus. We also extend Mendler’s result on recursive equations to this system.