bluuebunny/crossref_metadata_2025_split huggingface dataset:
An undecidable problem in correspondence theory
Authors: Chagrova L. A. 
Published: May 2006

In this paper we prove undecidability of first-order definability of propositional formulas. The main result is proved for intuitionistic formulas, but it remains valid for other kinds of propositional formulas by analogous arguments or with the help of various translations.For general background on correspondence theory the reader is referred to van Benthem [1], [2] (see [3] for a survey of recent results).The method for the proofs of undecidability in this paper will be to simulate calculations of a Minsky machine by intuitionistic formulas. §3 concerns this simulation. Effective procedures for the construction of simulating modal formulas can be found in the literature (cf. [4]).The principal results of the paper are in §4. §5 gives some further undecidability results, that will be proved in another paper by modification of the method of this paper.I am indebted to the referee for drawing my attention to some errors in an earlier version of this paper.
The proofs of α → α in P – W
Authors: Hirokawa Sachio 
Published: May 2006

AbstractThe syntactic structure of the system of pure implicational relevant logic P − W is investigated. This system is defined by the axioms B = (b → c) → (a → b) → a → c, B′ = (a → b) → (b → c)→ a → c, I = a → a, and the rules of substitution and modus ponens. A class of λ-terms, the closed hereditary right-maximal linearλ-terms, and a translation of such λ-terms M to BB′ I-combinators M+ is introduced. It is shown that a formula a is provable in P − W if and only if α is a type of some λ-term in this class. Hence these λ-terms represent proof figures in the Natural Deduction version of P − W.Errol Martin (1982) proved that no formula with form α → α is provable in P − W without using the axiom I. We show that a β-normal form λ-term M in the class is η reducible to λx.x if the translated BB′ I-combinator M+ contains I. Using this theorem and Martin's result, we prove that a λ-term in the class is βη-reducible to λx.x if the λ-term has a type α → α. Hence the structure of proofs of α → α in P − W is determined.
Subformula property in many-valued modal logics
Authors: Takano Mitio 
Published: May 2006

Fitting, in [1] and [2], investigated two families of many-valued modal logics. The first, which is somewhat familiar in the literature, is that of the logics characterized using a many-valued version of the Kripke model (binary modal modelin his terminology) with a two-valued accessibility relation. On the other hand, those logics which are characterized using another many-valued version of the Kripke model (implicational modal model), with a many-valued accessibility relation, form the second family. Although he gave a sequent calculus for each of these logics, it is far from having the cut-elimination property (CEP) or the subformula property. So we will give a substitute for his system enjoying the subformula property, though it is not of ordinary sequent calculus but of the many-valued version of sequent calculus initiated by Takahashi [7] and Rousseau [3].The author, unaware of the deduction systems with CEP, had given in [8] and [9], after Rousseau [4], the deduction systems for the intuitionistic many-valued logics which enjoy CEP only for a certain restricted class of proofs. Then in [10], he gave for three-valued modal logics the ones with CEP, but these systems have a rule of inference which is unnecessary if the Cut rule is present. Why are we particular about CEP? The author's answer is that a cut-free proof is easy to examine since it is composed solely of subformulas of the formulas which form its conclusion. In this direction, the author has given, for modal logics with the Brouwerian axiom [11], the ones without CEP which nevertheless enjoy the subformula property. This paper is a sequel to the study in [11].
Step by step – Building representations in algebraic logic
Authors: Hirsch Robin , Hodkinson Ian 
Published: May 2006

AbstractWe consider the problem of finding and classifying representations in algebraic logic. This is approached by letting two players build a representation using a game. Homogeneous and universal representations are characterized according to the outcome of certain games. The Lyndon conditions defining representable relation algebras (for the finite case) and a similar schema for cylindric algebras are derived. Finte relation algebras with homogeneous representations are characterized by first order formulas. Equivalence games are defined, and are used to establish whether an algebra is ω-categorical. We have a simple proof that the perfect extension of a representable relation algebra is completely representable.An important open problem from algebraic logic is addressed by devising another two-player game, and using it to derive equational axiomatisations for the classes of all representable relation algebras and representable cylindric algebras.Other instances of this approach are looked at, and include the step by step method.
Degree theoretic definitions of the low2 recursively enumerable sets
Authors: Downey Rod , Shore Richard A. 
Published: May 2006

The primary relation studied in recursion theory is that of relative complexity: A set or function A (of natural numbers) is reducible to one B if, given access to information about B, we can compute A. The primary reducibility is that of Turing, A ≤TB, where arbitrary (Turing) machines, φe, can be used; access to information about (the oracle) B is unlimited and the lengths of computations are potentially unbounded. Many other interesting reducibilities result from restricitng one or more of these facets of the procedure. Thus, for example, the strongest notion considered is one-one reducibility on sets: A ≤1B iff there is a one-one recursive (= effective) function f such that x Є A ⇔ f(x) Є B. Many-one (≤m) reducibility simply allows f to be many-one. Other intermediate reducibilities include truth-table (≤tt) and weak truth-table (≤wtt). The latter imposes a recursive bound f(x) on the information about B that can be used to compute A(x). The former also bounds the length of computations by requiring that the computation of A(x) from B halt in at most f(x) many steps.Each such reducibility r defines a notion of degree, degr(A) = {B : A ≤rB ∧ B ≤rA}, and a corresponding structure of the r-degrees ordered by r-reducibility. (We typically denote the degree of A by a.) A major theme in recursion theory has been the investigation of the relation between a set's place in these orderings (the algebraic properties of its degree) and other algorithmic, set-theoretic or definability type notions of complexity. Important examples of such other notions include rates of growth of functions, the types of approximation procedures which converge to the given function or set and the (syntactic) complexity of defining the set (or function) in arithmetic or analysis.
Some characterization theorems for infinitary universal Horn logic without equality
Authors: Dellunde Pilar , Jansana Ramon 
Published: May 2006

In this paper we mainly study preservation theorems for two fragments of the infinitary languagesLκκ, withκregular, without the equality symbol: the universal Horn fragment and the universal strict Horn fragment. In particular, whenκisω, we obtain the corresponding theorems for the first-order case.The universal Horn fragment of first-order logic (with equality) has been extensively studied; for references see [10], [7] and [8]. But the universal Horn fragment without equality, used frequently in logic programming, has received much less attention from the model theoretic point of view. At least to our knowledge, the problem of obtaining preservation results for it has not been studied before by model theorists. In spite of this, in the field of abstract algebraic logic we find a theorem which, properly translated, is a preservation result for the strict universal Horn fragment of infinitary languages without equality which, apart from function symbols, have only a unary relation symbol. This theorem is due to J. Czelakowski; see [5], Theorem 6.1, and [6], Theorem 5.1. A. Torrens [12] also has an unpublished result dealing with matrices of sequent calculi which, properly translated, is a preservation result for the strict universal Horn fragment of a first-order language. And in [2] of W. J. Blok and D. Pigozzi we find Corollary 6.3 which properly translated corresponds to our Corollary 19, but for the case of a first-order language that apart from its function symbols has only oneκ-ary relation symbol, and for strict universal Horn sentences. The study of these results is the basis for the present work. In the last part of the paper, Section 4, we will make these connections clear and obtain some of these results from our theorems. In this way we hope to make clear two things: (1) The field of abstract algebraic logic can be seen, in part, as a disguised study of universal Horn logic without equality and so has an added interest. (2) A general study of universal Horn logic without equality from a model theoretic point of view can be of help in the field of abstract algebraic logic.
The thickness lemma from P− + IΣ1 + ¬BΣ2
Authors: Yang Yue 
Published: May 2006

Let P− denote the Peano axioms minus the induction scheme. Let IΣn, (I∏n), BΣn (B∏n), LΣn (L∏n denote the induction scheme, the collection scheme, and the least number principle for Σn-(∏n-) formulas respectively. Paris and Kirby [3] studied the relative proof-theoretic strengths of those schemes. The general theorem states that IΣn, I∏n, LΣn, and L∏n are equivalent; IΣn implies BΣn implies IΣn–1; but not conversely.In recent years, people have been interested in doing recursion theory on fragments of arithmetic. One of the purposes of this study is to understand the priority methods. Much work has been done in this area. For example, M. Mytilinaios [5] showed that the Sacks splitting theorem can be proven in P− + IΣ1. Later, J. Mourad showed that the Sacks splitting theorem is indeed equivalent to IΣ1 [4]. M. Groszek and M. Mytilinaios [1] showed that P− + IΣ2 is sufficient to prove the existence of a high incomplete r.e. set. On the other hand, M. Mytilinaios and T. Slaman [6] showed that P− + IΣ1 is too weak to prove the existence of such a set. A natural question to ask is if the existence of such a set implies IΣ2. In this paper, we will show the answer is negative by constructing a model of P− + IΣ1 + ¬BΣ2 which has a high incomplete r.e. set. Notice that, as shown by M. Groszek and T. Slaman in [2], P− + IΣ1 is too weak to show the transitivity of weak Turing reducibility on Σ2-sets.
Some remarks on the partition calculus of ordinals
Authors: Komjáth Péter 
Published: May 2006

One of the early partition relation theorems which include ordinals was the observation of Erdös and Rado [7] that if κ = cf(κ) > ω then the Dushnik–Miller theorem can be sharpened to κ→(κ, ω + 1)2. The question on the possible further extension of this result was answered by Hajnal who in [8] proved that the continuum hypothesis implies ω1 ↛ (ω1, ω + 2)2. He actually proved the stronger result ω1 ↛ (ω: 2))2. The consistency of the relation κ↛(κ, (ω: 2))2 was later extensively studied. Baumgartner [1] proved it for every κ which is the successor of a regular cardinal. Laver [9] showed that if κ is Mahlo there is a forcing notion which adds a witness for κ↛ (κ, (ω: 2))2 and preserves Mahloness, ω-Mahloness of κ, etc. We notice in connection with these results that λ→(λ, (ω: 2))2 holds if λ is singular, in fact λ→(λ, (μ: n))2 for n < ω, μ < λ (Theorem 4).In [11] Todorčević proved that if cf(λ) > ω then a ccc forcing can add a counter-example to λ→(λ, ω + 2)2. We give an alternative proof of this (Theorem 5) and extend it to larger cardinals: if GCH holds, cf (λ) > κ = cf (κ) then < κ-closed, κ+-c.c. forcing adds a counter-example to λ→(λ, κ + 2)2 (Theorem 6).Erdös and Hajnal remarked in their problem paper [5] that Galvin had proved ω2→(ω1, ω + 2)2 and he had also asked if ω2→(ω1, ω + 3)2 is true. We show in Theorem 1 that the negative relation is consistent.
Universal classes of simple relation algebras
Authors: Givant Steven 
Published: May 2006

Tarski [19] proved the important theorem that the class of representable relation algebras is equationally axiomatizable. One of the key steps in his proof is showing that the class of (isomorphs of) simple set relation algebras—that is, algebras of binary relations with a unit of the formU×Ufor some non-empty setU—is universal, i.e., is axiomatizable by a set of universal sentences. In the same paper Tarski observed that the class of (isomorphs of) relation algebras constructed from groups (so-calledgroup relation algebras) is also universal.We shall abstract the essential ingredients of Tarski's method (in Corollary 2.4), and then combine them with some observations about atom structures, to establish (in Theorem 2.6) a rather general method for showing that certain classes of simple relation algebras—and, more generally, certain classes of simple algebras in a discriminator variety V—are universal, and consequently that the collections of (isomorphs of) subdirect products of algebras in such classes form subvarieties of V. As applications of the method we show that two well-known classes of simple relation algebras, those constructed from projective geometries (sometimes calledLyndon algebras) and those constructed from modular lattices with a zero (sometimes calledMaddux algebras), are universal. In the process we prove that these two classes consist precisely of all (isomorphs of) complex algebras over the respective geometries and modular lattices, provided that we choose the primitive notions of the latter structures in an appropriate fashion. We also derive Tarski's theorems and a related theorem of the author as easy corollaries of Theorem 2.6.
A general formulation of simultaneous inductive-recursive definitions in type theory
Authors: Dybjer Peter 
Published: May 2006

AbstractThe first example of a simultaneous inductive-recursive definition in intuitionistic type theory is Martin-Löfs universe à la Tarski. A set U0of codes for small sets is generated inductively at the same time as a function T0, which maps a code to the corresponding small set, is defined by recursion on the way the elements of U0are generated.In this paper we argue that there is an underlyinggeneralnotion of simultaneous inductive-recursive definition which is implicit in Martin-Löf's intuitionistic type theory. We extend previously given schematic formulations of inductive definitions in type theory to encompass a general notion of simultaneous induction-recursion. This enables us to give a unified treatment of several interesting constructions including various universe constructions by Palmgren, Griffor, Rathjen, and Setzer and a constructive version of Aczel's Frege structures. Consistency of a restricted version of the extension is shown by constructing a realisability model in the style of Allen.
Subprevarieties versus extensions. Application to the logic of paradox
Authors: Pynko Alexej P. 
Published: May 2006

AbstractIn the present paper we prove that the poset of all extensions of the logic defined by a class of matrices whose sets of distinguished values are equationally definable by their algebra reducts is the retract, under a Galois connection, of the poset of all subprevarieties of the prevariety generated by the class of the algebra reducts of the matrices involved. We apply this general result to the problem of finding and studying all extensions of the logic of paradox (viz., the implication-free fragment of any non-classical normal extension of the relevance-mingle logic). In order to solve this problem, we first study the structure of prevarieties of Kleene lattices. Then, we show that the poset of extensions of the logic of paradox forms a four-element chain, all the extensions being finitely many-valued and finitely-axiomatizable logics. There are just two proper consistent extensions of the logic of paradox. The first is the classical logic that is relatively axiomatized by the Modus ponens rule for the material implication. The second extension, being intermediate between the logic of paradox and the classical logic, is the one relatively axiomatized by the Ex Contradictione Quodlibet rule.
On axiomatising products of Kripke frames
Authors: Kurucz Ágnes 
Published: May 2006

AbstractIt is shown that the many-dimensional modal logicKn, determined by products ofn-many Kripke frames, is not finitely axiomatisable in then-modal language, for anyn> 2. On the other hand,Knis determined by a class of frames satisfying a single first-order sentence.
Located sets and reverse mathematics
Authors: Giusto Mariagnese , Simpson Stephen G. 
Published: May 2006

AbstractLet X be a compact metric space. A closed set K ⊆ X is located if the distance function d(x, K) exists as a continuous real-valued function on X; weakly located if the predicate d(x, K) > r is allowing parameters. The purpose of this paper is to explore the concepts of located and weakly located subsets of a compact separable metric space in the context of subsystems of second order arithmetic such as RCA0, WKL0 and ACA0. We also give some applications of these concepts by discussing some versions of the Tietze extension theorem. In particular we prove an RCA0 version of this result for weakly located closed sets.
Non-distributive upper semilattice of Kleene degrees
Authors: Muraki Hisato 
Published: May 2006

AbstractK denotes the upper semilattice of all Kleene degrees. Under ZF + AD + DC. K is well-ordered and deg(XSJ) is the next Kleene degree above deg(X) for X ⊆ ωω (see [4] and [5, Chapter V]). While, without AD, properties of K are not always clear. In this note, we prove the non-distributivity of K under ZFC (§1), and that of Kleene degrees between deg(X) and deg(XSJ) for some X under ZFC + CH (§2.3).
The effective content of surreal algebra
Authors: Lurie Jacob 
Published: May 2006

AbstractThis paper defines and explores the properties of several effectivizations of the structure of surreal numbers. The construction of one of previously investigated systems, the metadyadics, is shown to be effectively equivalent to the construction of the surreals in . This equivalence is used to answer several open questions concerning the metadyadics. Results obtained seem to indicate that the metadyadics best capture the notion of a recursive surreal number.
Definability and descent
Authors: Ballard David , Boshuck William 
Published: May 2006

The present note offers a short argument for the descent theorems of Zawadowski [10] (originally [9]) and Makkai [6], which were conjectured by Pitts after the descent theorem of Joyal and Tierney [3] for open geometric morphisms of (Grothendieck) toposes. The original proofs, which involve variants of Makkai's [5] duality for first order logic, are rather involved and there has been considerable interest in locating simpler proofs. Viewed categorically, the descent theorems establish a bicategorical exactness property (conservative morphisms are effective descent) for pretop (the 2-category of small pretoposes, pretopos functors, and natural transformations), for exact (exact categories, exact functors, and natural transformations), and for bpretop* (Boolean pretoposes, pretopos functors, and natural isomorphisms). Viewed logically, they fragment into a familiar Beth/Tarski-type definability theorem and a covering theorem for certain functors on PCΔ-categories (groupoids, in the Boolean case); the latter (as the former) is a arithmetical statement about the syntax of first order logic ([6, §3])).The argument here involves special models and, independently, a continuity lemma of Makkai. The use of special models is axiomatic in that only a few properties (listed below) are needed. The continuity lemma, 9.1 of [6], is established via forcing and can be read independently of the rest of that paper. Because of its interest to both the model theorist and the category theorist, the argument is first given as straight model theory and afterwards it is briefly indicated how the descent theorems follow.
Cohen-stable families of subsets of integers
Authors: Kurilić Miloš S. 
Published: May 2006

AbstractA maximal almost disjoint (mad) family ⊆ [ω]ω is Cohen-stable if and only if it remains maximal in any Cohen generic extension. Otherwise it is Cohen-unstable. It is shown that a mad family. .is Cohen-unstable if and only if there is a bijection G from ω to the rationals such that the sets G[A]. A ∈ are nowhere dense. An ℵ0-mad family, . is a mad family with the property that given any countable family ℬ ⊂ [ω]ω such that each element of ℬ meets infinitely many elements of in an infinite set there is an element of meeting each element of ℬ in an infinite set. It is shown that Cohen-stable mad families exist if and only if there exist ℵ0-mad families. Either of the conditions b = c or a < cov() implies that there exist Cohen-stable mad families. Similar results are obtained for splitting families. For example, a splitting family. . is Cohen-unstable if and only if there is a bijection G from ω to the rationals such that the boundaries of the sets G[S], S ∈ are nowhere dense. Also. Cohen-stable splitting families of cardinality ≤ κ exist if and only if ℵ0-splitting families of cardinality ≤ κ exist.
An algebraic approach to intuitionistic connectives
Authors: Caicedo Xavier , Cignoli Roberto 
Published: May 2006

Abstract.It is shown that axiomatic extensions of intuitionistic propositional calculus defining univocally new connectives, including those proposed by Gabbay, are strongly complete with respect to valuations in Heyting algebras with additional operations. In all cases, the double negation of such a connective is equivalent to a formula of intuitionistic calculus. Thus, under the excluded third law it collapses to a classical formula, showing that this condition in Gabbay's definition is redundant. Moreover, such connectives can not be interpreted in all Heyting algebras, unless they are already equivalent to a formula of intuitionistic calculus. These facts relativize to connectives over intermediate logics. In particular, the intermediate logic with values in the chain of lengthnmay be “completed” conservatively by adding a single unary connective, so that the expandedsystemdoes not allow further axiomatic extensions by new connectives.