Algebraic geometry in first-order logic

In every variety of algebras Θ, we can consider its logic and its algebraic geometry. In previous papers, geometry in equational logic, i.e., equational geometry, has been studied. Here we describe an extension of this theory to first-order logic (FOL). The algebraic sets in this geometry are determined by arbitrary sets of FOL formulas. The principal motivation of such a generalization lies in the area of applications to knowledge science. In this paper, the FOL formulas are considered in the context of algebraic logic. For this purpose, we define special Halmos categories. These categories in algebraic geometry related to FOL play the same role as the category of free algebras Θ⁰ play in equational algebraic geometry. This paper consists of three parts. Section 1 is of introductory character. The first part (Secs. 2–4) contains background on algebraic logic in the given variety of algebras Θ. The second part is devoted to algebraic geometry related to FOL (Secs. 5–7). In the last part (Secs. 8–9), we consider applications of the previous material to knowledge science. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 22, Algebra and Geometry, 2004.     

Tableau method for residuated logic

Residuated logic is a generalization of intuitionistic logic, which does not assume the idempotence of the conjunction operator. Such generalized conjunction operators have proved important in expert systems (in the area of Approximate Reasoning) and in some areas of Theoretical Computer Science. Here we generalize the intuitionistic tableau procedure and prove that this generalized tableau method is sound for the semantics (the class of residuated algebras) of residuated propositional calculus (RPC). Since the axioms of RPC are complete for the semantics we may conclude that whenever a formula 0 is tableau provable, it is deducible in RPC. We present two different approaches for constructing residuated algebras which give us countermodels for some formulas φ which are not tableau provable. The first uses the fact that the theory of residuated algebras is equational, to construct quotients of free algebras. The second uses finite algebras. We end by discussing a number of open questions.     

Categories with families and first-order logic with dependent sorts

First-order logic with dependent sorts, such as Makkai's first-order logic with dependent sorts (FOLDS), or Aczel's and Belo's dependently typed (intuitionistic) first-order logic (DFOL), may be regarded as logic enriched dependent type theories. Categories with families (cwfs) is an established semantical structure for dependent type theories, such as Martin-Löf type theory. We introduce in this article a notion of hyperdoctrine over a cwf, and show how FOLDS and DFOL fit in this semantical framework. A soundness and completeness theorem is proved for DFOL. The semantics is functorial in the sense of Lawvere, and uses a dependent version of the Lindenbaum-Tarski algebra for a DFOL theory. Agreement with standard first-order semantics is established. Applications of DFOL to constructive mathematics and categorical foundations are given. A key feature is a local propositions-as-types principle.     

ŁΠ logic with fixed points

We study a system, μ?Π, obtained by an expansion of ?Π logic with fixed points connectives. The first main result of the paper is that μ?Π is standard complete, i.e., complete with regard to the unit interval of real numbers endowed with a suitable structure. We also prove that the class of algebras which forms algebraic semantics for this logic is generated, as a variety, by its linearly ordered members and that they are precisely the interval algebras of real closed fields. This correspondence is extended to a categorical equivalence between the whole category of those algebras and another category naturally arising from real closed fields. Finally, we show that this logic enjoys implicative interpolation.     

Gentzen-style axiomatizations in equational logic

The notion of a Gentzen-style axiomatization of equational theories is presented. In the standard deductive systems for equational logic axioms take the form of equations and the inference rules can be viewed as quasi-equations. In the deductive systems for quasi-equational logic the axioms, which are quasi-equations, can be viewed as sequents and the inference rules as Gentzen-style rules. It is conjectured that every finite algebra has a finite Gentzen-style axiomatization for its quasi-identities. We verify this conjecture for a class of algebras that includes all finite algebras without proper subalgebras and all finite simple algebras that are embeddable into the free algebra of their variety.Dedicated to the memory of Alan DayPresented by J. Sichler.Supported by an Iowa State University Research Assistantship.Supported by National Science Foundation Grant #DMS 8005870.     

On subtractive varieties,I

A varietyV is subtractive if it obeys the laws s(x, x)=0, s(x, 0)=x for some binary terms and constant 0. This means thatV has 0-permutable congruences (namely [0]R ºS=[0]S ºR for any congruencesR, S of any algebra inV). We present the basic features of such varieties, mainly from the viewpoint of ideal theory. Subtractivity does not imply congruence modularity, yet the commutator theory for ideals works fine. We characterize i-Abelian algebras, (i.e. those in which the commutator is identically 0). In the appendix we consider the case of a classical ideal theory (comprising: groups, loops, rings, Heyting and Boolean algebras, even with multioperators and virtually all algebras coming from logic) and we characterize the corresponding class of subtractive varieties.Presented by A. F. Pixley.     

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.     

An arithmetical view to first-order logic

A value space is a topological algebra B equipped with a non-empty family of continuous quantifiers :B^∗→B. We will describe first-order logic on the basis of B. Operations of B are used as connectives and its relations are used to define statements. We prove under some normality conditions on the value space that any theory in the new setting can be represented by a classical first-order theory.     

Coalgebraic logic

We present a generalization of modal logic to logics which are interpreted on coalgebras of functors on sets. The leading idea is that infinitary modal logic contains characterizing formulas. That is, every model-world pair is characterized up to bisimulation by an infinitary formula. The point of our generalization is to understand this on a deeper level. We do this by studying a fragment of infinitary modal logic which contains the characterizing formulas and is closed under infinitary conjunction and an operation called Δ. This fragment generalizes to a wide range of coalgebraic logics. Each coalgebraic logic is determined by a functor on sets satisfying a few properties, and the formulas of each logic are interpreted on coalgebras of that functor. Among the logics obtained are the fragment of infinitary modal logic mentioned above as well as versions of natural logics associated with various classes of transition systems, including probabilistic transition systems. For most of the interesting cases, there is a characterization result for the coalgebraic logic determined by a given functor. We then apply the characterization result to get representation theorems for final coalgebras in terms of maximal elements of ordered algebras. The end result is that the formulas of coalgebraic logics can be viewed as approximations to the elements of a final coalgebra.     

Completeness of two systems of illative combinatory logic for first-order propositional and predicate calculus

Illative combinatory logic consists of the theory of combinators or lambda calculus extended by extra constants (and corresponding axioms and rules) intended to capture inference. The paper considers 4 systems of illative combinatory logic that are sound for first-order propositional and predicate calculus. The interpretation from ordinary logic into the illative systems can be done in two ways: following the propositions-as-types paradigm, in which derivations become combinators, or in a more direct way, in which derivations are not translated. Both translations are closely related in a canonical way. In a preceding paper, Barendregt, Bunder and Dekkers, 1993, we proved completeness of the two direct translations. In the present paper we prove completeness of the two indirect translations by showing that the corresponding illative systems are conservative over the two systems for the direct translations. In another version, DBB (1997), we shall give a more direct completeness proof. These papers fulfill the program of Church and Curry to base logic on a consistent system of -terms or combinators. Hitherto this program had failed because systems of ICL were either too weak (to provide a sound interpretation) or too strong (sometimes even inconsistent). Received: February 15, 1996     

On some developments in the representation theory of cylindric-like algebras

In this survey paper we recall the representation problem of certain classes of algebras of relations. Two specific recent research directions in algebraic logic are surveyed: the one is connected with the representation theory of cylindric relativized set algebras including Resek’s representation theorem and merry-go-round axioms, the other discusses the representation problem in some non-well-founded set theories where the axiom of foundation is replaced by Boffa’s weak anti-foundation axiom. This paper is dedicated to Walter Taylor. Received September 8, 2005; accepted in final form January 12, 2006. The first author was supported by Hungarian National Foundation for Scientific Research grants T43242 and T035192. The second author was supported by Hungarian National Foundation for Scientific Research grants D042177, T43242 and T035192.     

Reduction of Hilbert-type proof systems to the if-then-else equational logic

We present a construction of the linear reduction of Hilbert type proof systems for propositional logic to if-then-else equational logic. This construction is an improvement over the same result found in [4] in the sense that the technique used in the construction can be extended to the linear reduction of first-order logic to if-then-else equational logic.     

Clifford geometric parameterization of inequivalent vacua

We propose a geometric method to parameterize inequivalent vacua by dynamical data. Introducing quantum Clifford algebras with arbitrary bilinear forms we distinguish isomorphic algebras—as Clifford algebras—by different filtrations (resp. induced gradings). The idea of a vacuum is introduced as the unique algebraic projection on the base field embedded in the Clifford algebra, which is however equivalent to the term vacuum in axiomatic quantum field theory and the GNS construction in C^*‐algebras. This approach is shown to be equivalent to the usual picture which fixes one product but employs a variety of GNS states. The most striking novelty of the geometric approach is the fact that dynamical data fix uniquely the vacuum and that positivity is not required. The usual concept of a statistical quantum state can be generalized to geometric meaningful but non‐statistical, non‐definite, situations. Furthermore, an algebraization of states takes place. An application to physics is provided by an U (2)‐symmetry producing a gap equation which governs a phase transition. The parameterization of all vacua is explicitly calculated from propagator matrix elements. A discussion of the relation to BCS theory and Bogoliubov–Valatin transformations is given. Copyright © 2001 John Wiley & Sons, Ltd.     

A non-axiomatizability result in algebraic logic

In this paper we prove that the class of all relation algebras which are isomorphic to relation algebras of the form (L) for some semigroupL (so called semigroup relation algebras) is not first-order axiomatizable.Presented by E. Fried.     

Fibered universal algebra for first-order logics

We extend Lawvere-Pitts prop-categories (aka. hyperdoctrines) to develop a general framework for providing fibered algebraic semantics for general first-order logics. This framework includes a natural notion of substitution, which allows first-order logics to be considered as structural closure operators just as propositional logics are in abstract algebraic logic. We then establish an extension of the homomorphism theorem from universal algebra for generalized prop-categories and characterize two natural closure operators on the prop-categorical semantics. The first closes a class of structures (which are interpreted as morphisms of prop-categories) under the satisfaction of their common first-order theory and the second closes a class of prop-categories under their associated first-order consequence. It turns out that these closure operators have characterizations that closely mirror Birkhoff's characterization of the closure of a class of algebras under the satisfaction of their common equational theory and Blok and Jónsson's characterization of closure under equational consequence, respectively. These algebraic characterizations of the first-order closure operators are unique to the prop-categorical semantics. They do not have analogues, for example, in the Tarskian semantics for classical first-order logic. The prop-categories we consider are much more general than traditional intuitionistic prop-categories or triposes (i.e., topos representing indexed partially ordered sets). Nonetheless, to the best of our knowledge, our results are new, even when restricted to these special classes of prop-categories.     

Very true on CBA fuzzy logic

CBA logic was introduced as a non-associative generalization of the Łukasiewicz many-valued propositional logic. Its algebraic semantic is just the variety of commutative basic algebras. Petr Hájek introduced vt-operators as models for the “very true” connective on fuzzy logics. The aim of the paper is to show possibilities of using vt-operators on commutative basic algebras, especially we show that CBA logic endowed with very true connective is still fuzzy.     

A semantic study of the first-order predicate logic with uncertainty involved

In this paper, we provide a semantic study of the first-order predicate logic for situations involving uncertainty. We introduce the concepts of uncertain predicate proposition, uncertain predicate formula, uncertain interpretation and degree of truth in the framework of uncertainty theory. Compared with classical predicate formula taking true value in \(\{0,1\}\) , the degree of truth of uncertain predicate formula may take any value in the unit interval \([0,1]\) . We also show that the uncertain first-order predicate logic is consistent with the classical first-order predicate logic on some laws of the degree of truth.     

Natural dualities for semilattice-based algebras

While every finite lattice-based algebra is dualisable, the same is not true of semilattice-based algebras. We show that a finite semilattice-based algebra is dualisable if all its operations are compatible with the semilattice operation. We also give examples of infinite semilattice-based algebras that are dualisable. In contrast, we present a general condition that guarantees the inherent non-dualisability of a finite semilattice-based algebra. We combine our results to characterise dualisability amongst the finite algebras in the classes of flat extensions of partial algebras and closure semilattices. Throughout, we emphasise the connection between the dualisability of an algebra and the residual character of the variety it generates. Presented by R. Willard.     

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.