A topological characterization of consistency of logic theories in propositional logic

The main purpose of this note is to characterize consistency of logic theories in propositional logic by means of topological concept. Based on the concepts of truth degree of formulas and similarity degree between formulas the concept of logic metric space has been proposed by the first author. It is proved in this note that a closed logic theory Γ is consistent if and only if it contains no interior point in the logic metric space. Moreover the relationship between logic closedness and topological closedness of a logic theory Γ is discussed. Finally, the concept of full divergency is also characterized by means of the topological concept of density. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A note on Grzegorczyk's logic

Grzegorczyk's modal logic (Grz) corresponds to the class of upwards well‐founded partially ordered Kripke frames, however all known proofs of this fact utilize some form of the Axiom of Choice; G. Boolos asked in [1], whether it is provable in plain ZF. We answer his question negatively: Grz corresponds (in ZF) to a class of frames, which does not provably coincide with upwards well‐founded posets in ZF alone. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A two-dimensional metric temporal logic

We introduce a two-dimensional metric (interval) temporal logic whose internal and external time flows are dense linear orderings. We provide a suitable semantics and a sequent calculus with axioms for equality and extralogical axioms. Then we prove completeness and a semantic partial cut elimination theorem down to formulas of a certain type.     

A strongly graded ring that is

We construct a ring that is strongly graded by the integers such that it is not graded equivalent to a skew group ring. This is in contrast to the finite case and the results of Cohen and Montgomery, in which every strongly graded ring is graded equivalent to a skew group ring ^{2 2}1991 mathematics subject classification: 16D90, 16S35, 16S40, 16S50, 16W50      

A survey of predicate realizability logic

The paper contains a survey of the results and methods of studying interpretations of predicate formulas based on constructive semantics of the first-order language of arithmetic and its extensions.     

A probabilistic extension of intuitionistic logic

We introduce a probabilistic extension of propositional intuitionistic logic. The logic allows making statements such as P_≥sα, with the intended meaning “the probability of truthfulness of α is at least s”. We describe the corresponding class of models, which are Kripke models with a naturally arising notion of probability, and give a sound and complete infinitary axiomatic system. We prove that the logic is decidable.     

A radical for graded Lie algebras

For an arbitrary group?G and a G-graded Lie algebra L over a field of characteristic zero we show that the Kostrikin radical of?L is graded and coincides with the graded Kostrikin radical of?L. As an important tool for our proof we show that the graded Kostrikin radical is the intersection of all graded-strongly prime ideals of?L. In particular, graded-nondegenerate Lie algebras are subdirect products of graded-strongly prime Lie algebras.     

On graded Thierrin radicals of graded rings

In this paper, we study the graded Thierrin radical and the classical Thierrin radical of a graded ring, which is the direct sum of a family of its additive subgroups indexed by a nonempty set, under the assumption that the product of homogeneous elements is again homogeneous. There are two versions of this graded radical, the graded Thierrin and the large graded Thierrin radical. We establish several characterizations of the graded Thierrin radical and prove that the largest homogeneous ideal contained in the classical Thierrin radical of a graded ring coincides with the large graded Thierrin radical of that ring.     

Semigroup graded algebras and graded PI-exponent

Let S be a semigroup. We study the structure of graded-simple S-graded algebras A and the exponential rate PIexp ^S-gr(A):= lim_n→∞ \(\sqrt[n]{{c_n^{S - gr}\left( A \right)}}\) of growth of codimensions c _n ^S-gr (A) of their graded polynomial identities. This is of great interest since such algebras can have non-integer PIexp ^S-gr(A) despite being finite dimensional and associative. In addition, such algebras can have a non-trivial Jacobson radical J(A). All this is in strong contrast with the case when S is a group since in the group case J(A) is trivial, PIexp ^S-gr(A) is always integer and, if the base field is algebraically closed, then PIexp ^S-gr(A) equals dimA. Without any restrictions on the base field F, we classify graded-simple S-graded algebras A for a class of semigroups S which is complementary to the class of groups. We explicitly describe the structure of J(A) showing that J(A) is built up of pieces of a maximal S-graded semisimple subalgebra of A which turns out to be simple. When F is algebraically closed, we get an upper bound for \({\overline {\lim } _{n \to \infty }}\sqrt[n]{{c_n^{S - gr}\left( A \right)}}\). If A/J(A) ≈ M ₂(F) and S is a right zero band, we show that this upper bound is sharp and PIexp ^S-gr(A) indeed exists. In particular, we present an infinite family of graded-simple algebras A with arbitrarily large non-integer PIexp ^S-gr(A).     

A logic language for combinatorial optimization

CHIP (Constraint Handling In Prolog) is a new logic programming language combining the declarative aspect of logic programming for stating search problems with the efficiency of constraint handling techniques for solving them. CHIP has been applied to many real-life problems in Operations Research and hardware design with an efficiency comparable to specific programs written in procedural languages. The main advantage of CHIP is the short development time of the programs and their great modifiability and extensibility. In this paper, we discuss the application of the finite domain part of CHIP to the solving of discrete combinatorial problems occurring in Operations Research. The basic mechanisms underlying CHIP are explained through simple examples. Solutions in CHIP of several real-life problems (e.g., cutting stock, warehouses location problems) are presented and compared with usual approaches, showing the versatility and the interest of the approach.     

A note on extensions of infinitary logic

We show that a strong form of the so called Lindströms Theorem [4] fails to generalize to extensions of L and L : For weakly compact there is no strongest extension of L with the (,)-compactness property and the Löwenheim-Skolem theorem down to . With an additional set-theoretic assumption, there is no strongest extension of L with the (,)-compactness property and the Löwenheim-Skolem theorem down to <.We are indebted to Lauri Hella, Tapani Hyttinen and Kerkko Luosto for useful suggestions.Research partially supported by the United States-Israel Binational Science Foundation. Publication number [ShVa:726]Research partially supported by grant 40734 of the Academy of Finland.     

A semantic hierarchy for intuitionistic logic

Brouwer’s views on the foundations of mathematics have inspired the study of intuitionistic logic, including the study of the intuitionistic propositional calculus and its extensions. The theory of these systems has become an independent branch of logic with connections to lattice theory, topology, modal logic, and other areas. This paper aims to present a modern account of semantics for intuitionistic propositional systems. The guiding idea is that of a hierarchy of semantics, organized by increasing generality: from the least general Kripke semantics on through Beth semantics, topological semantics, Dragalin semantics, and finally to the most general algebraic semantics. While the Kripke, topological, and algebraic semantics have been extensively studied, the Beth and Dragalin semantics have received less attention. We bring Beth and Dragalin semantics to the fore, relating them to the concept of a nucleus from pointfree topology, which provides a unifying perspective on the semantic hierarchy.     

A complete many-valued logic with product-conjunction

A simple complete axiomatic system is presented for the many-valued propositional logic based on the conjunction interpreted as product, the coresponding implication (Goguen's implication) and the corresponding negation (Gödel's negation). Algebraic proof methods are used. The meaning for fuzzy logic (in the narrow sense) is shortly discussed.This article was processed by the author using the LATEX style filepljorlm from Springer-Verlag.     

A characterization theorem for geometric logic

We establish a criterion for deciding whether a class of structures is the class of models of a geometric theory inside Grothendieck toposes; then we specialize this result to obtain a characterization of the infinitary first-order theories which are geometric in terms of their models in Grothendieck toposes, solving a problem posed by Ieke Moerdijk in 1989.     

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.