Order-enriched categorical models of the classical sequent calculus

It is well-known that weakening and contraction cause naïve categorical models of the classical sequent calculus to collapse to Boolean lattices. Starting from a convenient formulation of the well-known categorical semantics of linear classical sequent proofs, we give models of weakening and contraction that do not collapse. Cut-reduction is interpreted by a partial order between morphisms. Our models make no commitment to any translation of classical logic into intuitionistic logic and distinguish non-deterministic choices of cut-elimination. We show soundness and completeness via initial models built from proof nets, and describe models built from sets and relations.     

Positive Sugihara monoids

It is proved that in the variety of positive Sugihara monoids, every finite subdirectly irreducible algebra is a retract of a free algebra. It follows that every quasivariety of positive Sugihara monoids is a variety, in contrast with the situation in several neighboring varieties. This result shows that when the logic R-mingle is formulated with the Ackermann constant t, then its full negation-free fragment is hereditarily structurally complete. Presented by R. W. Quackenbush. Received August 28, 2005; accepted in final form July 31, 2006.     

The Erdős-Mordell inequality is equivalent to non-positive curvature

We prove that, in plane absolute geometry, the Erdős-Mordell inequality is equivalent to the statement that the sum of the angles of a triangle is less than or equal to two right angles.      

Kripke models for classical logic

We introduce a notion of the Kripke model for classical logic for which we constructively prove the soundness and cut-free completeness. We discuss the novelty of the notion and its potential applications.     

Frolík decompositions for lattice-ordered groups

Frolík’s theorem says that a homeomorphism from a certain kind of topological space to itself decomposes the space into the clopen set of fixed points together with three clopen sets, each of whose images is disjoint from the original set. Stone’s theorem translates this result to a corresponding theorem about the Riesz space of continuous functions on the topological space. We prove a theorem analogous to that for Riesz spaces in the much more general setting of (possibly noncommutative) lattice-ordered groups and group-endomorphisms. The groups to which our result applies satisfy a weak condition, introduced by Abramovich and Kitover, on the polars; the images of our endomorphisms have a kind of order-density on their polars; the double polars of the images are cardinal summands; and the endomorphisms themselves are disjointness-preserving in both directions. We explain how to extend our result to larger groups to which it does not apply, and, to give additional insight, we provide many examples.     

Fibration of points and congruence modularity

Malcev varieties, or more generally Malcev categories, have been characterized by a property of the fibres of their fibration of points. In the same way, it is shown here that congruence modular varieties, and more generally Gumm categories, are also characterized by a property of these fibres.Received June 4, 2003; accepted in final form June 18, 2004.     

Logical structures and genus of proofs

Any arbitrarily complicated non-oriented graph, that is a graph of arbitrarily large genus, can be encoded in a cut-free proof. This unpublished result of Statman was shown in the early seventies. We provide a proof of it, and of a number of other related facts.     

Coherence for modalities

Positive modalities in S4, S5 and systems in their vicinity are investigated in terms of categorial proof theory. Coherence and maximality results are demonstrated, and connections with mixed distributive laws and Frobenius algebras are exhibited.     

The bounded proof property via step algebras and step frames

The paper introduces semantic and algorithmic methods for establishing a variant of the analytic subformula property (called ‘the bounded proof property’, bpp) for modal propositional logics. The bpp is much weaker property than full cut-elimination, but it is nevertheless sufficient for establishing decidability results. Our methodology originated from tools and techniques developed on one side within the algebraic/coalgebraic literature dealing with free algebra constructions and on the other side from classical correspondence theory in modal logic. As such, our approach is orthogonal to recent literature based on proof-theoretic methods and, in a way, complements it.     

An axiom system for Lingenberg’s metric-Euclidean planes

We show that Lingenbergs metric-Euclidean planes are the rectangular planes of Karzel and Stanik which satisfy the axiom If two of the perpendicular bisectors of a triangle exist, then so does the third.This paper was written while the author was at the Institute of Mathematics of University of Biaystok with a Fulbright grant. I thank the Polish-U.S. Fulbright Commission for the grant, Professor Krzysztof Pramowski for the hospitality, and Ewa Walecka for drawing the figures.     

Remarks, du côté de chez Tarski, on symmetric ternary relations

We point out that the results in [12] are the model-theoretic counterpart of results established syntactically in [3] and [10], and that Martin’s theorem for the Euclidean 3- or higher-dimensional case, established in [5], does not depend on the Beckman-Quarles theorem, and can be rephrased as a result about axiomatizability and definability.     

Injectives in residuated algebras

Injectives in several classes of structures associated with logic are characterized. Among the classes considered are residuated lattices, MTL-algebras, IMTL-algebras, BL-algebras, NM-algebras and bounded hoops.     

Spreads of nonsingular pairs in symplectic vector spaces

Let V be a vector space of dimension 2n, n even, over a field F, equipped with a nonsingular symplectic form. We define a new algebraic/combinatorial structure, a spread of nonsingular pairs, or nsp-spread, on V and show that nsp-spreads exist in considerable generality. We further examine in detail some particular cases.     

Cutting planes,connectivity, and threshold logic

Originating from work in operations research the cutting plane refutation systemCP is an extension of resolution, where unsatisfiable propositional logic formulas in conjunctive normal form are recognized by showing the non-existence of boolean solutions to associated families of linear inequalities. Polynomial sizeCP proofs are given for the undirecteds-t connectivity principle. The subsystemsCP _q ofCP, forq2, are shown to be polynomially equivalent toCP, thus answering problem 19 from the list of open problems of [8]. We present a normal form theorem forCP ₂-proofs and thereby for arbitraryCP-proofs. As a corollary, we show that the coefficients and constant terms in arbitrary cutting plane proofs may be exponentially bounded by the number of steps in the proof, at the cost of an at most polynomial increase in the number of steps in the proof. The extensionCPLE ⁺, introduced in [9] and there shown top-simulate Frege systems, is proved to be polynomially equivalent to Frege systems. Lastly, since linear inequalities are related to threshold gates, we introduce a new threshold logic and prove a completeness theorem.Supported in part by NSF grant DMS-9205181 and by US-Czech Science and Technology Grant 93-205Partially supported by NSF grant CCR-9102896 and by US-Czech Science and Technology Grant 93-205     

Consistency,optimality, and incompleteness

Assume that the problem _P0$P_0$ is not solvable in polynomial time. Let T   be a first-order theory containing a sufficiently rich part of true arithmetic. We characterize T∪{_ConT}$T\cup \{{\mathit{Con}}_T\}$ as the minimal extension of T   proving for some algorithm that it decides _P0$P_0$ as fast as any algorithm B$\mathbb{B}$ with the property that T   proves that B$\mathbb{B}$ decides _P0$P_0$. Here, _ConT${\mathit{Con}}_T$ claims the consistency of T. As a byproduct, we obtain a version of Gödel?s Second Incompleteness Theorem. Moreover, we characterize problems with an optimal algorithm in terms of arithmetical theories.     

Some remarks on lengths of propositional proofs

We survey the best known lower bounds on symbols and lines in Frege and extended Frege proofs. We prove that in minimum length sequent calculus proofs, no formula is generated twice or used twice on any single branch of the proof. We prove that the number of distinct subformulas in a minimum length Frege proof is linearly bounded by the number of lines. Depthd Frege proofs ofm lines can be transformed into depthd proofs ofO(m ^d+1) symbols. We show that renaming Frege proof systems are p-equivalent to extended Frege systems. Some open problems in propositional proof length and in logical flow graphs are discussed. Supported in part by NSF grant DMS-9205181     

A relative interpolation theorem for infinitary universal Horn logic and its applications

In this paper we deal with infinitary universal Horn logic both with and without equality. First, we obtain a relative Lyndon-style interpolation theorem. Using this result, we prove a non-standard preservation theorem which contains, as a particular case, a Lyndon-style theorem on surjective homomorphisms in its Makkai-style formulation. Another consequence of the preservation theorem is a theorem on bimorphisms, which, in particular, provides a tool for immediate obtaining characterizations of infinitary universal Horn classes without equality from those with equality. From the theorem on surjective homomorphisms we also derive a non-standard Beth-style preservation theorem that yields a non-standard Beth-style definability theorem, according to which implicit definability of a relation symbol in an infinitary universal Horn theory implies its explicit definability by a conjunction of atomic formulas. We also apply our theorem on surjective homomorphisms, theorem on bimorphisms and definability theorem to algebraic logic for general propositional logic.     

Explicit constructions of graphs without short cycles and low density codes

We give an explicit construction of regular graphs of degree 2r withn vertices and girth ≧c logn/logr. We use Cayley graphs of factor groups of free subgroups of the modular group. An application to low density codes is given.     

A generalization of the formulas for intersection numbers of dual polar association schemes and their applications

Dual polar association schemes form an important family of association schemes, whose intersection numbers were computed in [Wan et al., Studies in Finite Geometry and the Construction of Incomplete Block Designs, Science Press, Beijing, 1966 (in Chinese)]. In this paper, we generalize the formulas for the intersection numbers, and introduce their applications to pooling designs, Cartesian authentication codes and vertex-transitive graphs.