The logic FBCI given by linearly ordered BCI-matrices is known not to be an axiomatic extension of the well-known BCI logic. In this paper we axiomatize FBCI by adding a recursively enumerable set of schemes of inference rules to BCI and show that there is no finite axiomatization for FBCI.

In abstract algebraic logic, the general study of propositional non-classical logics has been traditionally based on the abstraction of the Lindenbaum-Tarski process. In this process one considers the Leibniz relation of indiscernible formulae. Such approach has resulted in a classification of logics partly based on generalizations of equivalence connectives: the Leibniz hierarchy. This paper performs an analogous abstract study of non-classical logics based on the kind of generalized implication connectives they possess. It yields a new classification of logics expanding Leibniz (...) hierarchy: the hierarchy of implicational logics. In this framework the notion of implicational semilinear logic can be naturally introduced as a property of the implication, namely a logic L is an implicational semilinear logic iff it has an implication such that L is complete w.r.t. the matrices where the implication induces a linear order, a property which is typically satisfied by well-known systems of fuzzy logic. The hierarchy of implicational logics is then restricted to the semilinear case obtaining a classification of implicational semilinear logics that encompasses almost all the known examples of fuzzy logics and suggests new directions for research in the field. (shrink)

A wide family of many-valued logics—for instance, those based on the weak Kleene algebra—includes a non-classical truth-value that is ‘contaminating’ in the sense that whenever the value is assigned to a formula φ⁠, any complex formula in which φ appears is assigned that value as well. In such systems, the contaminating value enjoys a wide range of interpretations, suggesting scenarios in which more than one of these interpretations are called for. This calls for an evaluation of systems with multiple contaminating (...) values. In this paper, we consider the countably infinite family of multiple-conclusion consequence relations in which classical logic is enriched with one or more contaminating values whose behavior is determined by a linear ordering between them. We consider some motivations and applications for such systems and provide general characterizations for all consequence relations in this family. Finally, we provide sequent calculi for a pair of four-valued logics including two linearly ordered contaminating values before defining two-sided sequent calculi corresponding to each of the infinite family of many-valued logics studied in this paper. (shrink)

We introduce the logics GLP Λ, a generalization of Japaridze’s polymodal provability logic GLP ω where Λ is any linearly ordered set representing a hierarchy of provability operators of increasing strength. We shall provide a reduction of these logics to GLP ω yielding among other things a finitary proof of the normal form theorem for the variable-free fragment of GLP Λ and the decidability of GLP Λ for recursive orderings Λ. Further, we give a restricted axiomatization of the (...) variable-free fragment of GLP Λ. (shrink)

O-minimal structures have long been thought to occupy the base of a hierarchy of ordered structures, in analogy with the role that strongly minimal structures play with respect to stable theories. This is the first in an anticipated series of papers whose aim is the development of model theory for ordered structures of rank greater than one. A class of ordered structures to which a notion of finite rank can be assigned, the decomposable structures, is introduced here. (...) These include all ordered structures definable in o-minimal structures. The principal result in this paper, Theorem 5.1, asserts roughly that a decomposable structure [Formula: see text] can be partitioned into finitely many definable subsets such that on each set the restriction of < is a "twisted lexicographic" order. As a consequence, for all n and linear orders ≺ definable on a subset X ⊆ Mn in an o-minimal structure [Formula: see text], there is a definable partition of X such that the restriction of ≺ to each set in the partition is "lexicographic". (shrink)

When a linear order has an order preserving surjection onto each of its suborders, we say that it is strongly surjective. We prove that the set of countable strongly surjective linear orders is a [Formula: see text]-complete set. Using hypotheses beyond ZFC, we prove the existence of uncountable strongly surjective orders.

A successivity in a linear order is a pair of elements with no other elements between them. A recursive linear order with recursive successivities U is recursively categorical if every recursive linear order with recursive successivities isomorphic to U is in fact recursively isomorphic to U . We characterize those recursive linear orders with recursive successivities that are recursively categorical as precisely those with order type k 1 + g 1 + k 2 + g 2 +…+ g n -1 (...) + k n where each k n is a finite order type, non-empty for i ϵ{2,…, n -1} and each g i is an order type from among {ω,ω * ,ω+ω * }∪{ k ·η: k. (shrink)

LetEbe a computably enumerable equivalence relation on the setωof natural numbers. We say that the quotient set$\omega /E$realizesa linearly ordered set${\cal L}$if there exists a c.e. relation ⊴ respectingEsuch that the induced structure is isomorphic to${\cal L}$. Thus, one can consider the class of all linearly ordered sets that are realized by$\omega /E$; formally,${\cal K}\left = \left\{ {{\cal L}\,|\,{\rm{the}}\,{\rm{order}}\, - \,{\rm{type}}\,{\cal L}\,{\rm{is}}\,{\rm{realized}}\,{\rm{by}}\,E} \right\}$. In this paper we study the relationship between computability-theoretic properties ofEand algebraic properties of (...) linearly ordered sets realized byE. One can also define the following pre-order$ \le _{lo} $on the class of all c.e. equivalence relations:$E_1 \le _{lo} E_2 $if every linear order realized byE1is also realized byE2. Following the tradition of computability theory, thelo-degrees are the classes of equivalence relations induced by the pre-order$ \le _{lo} $. We study the partially ordered set oflo-degrees. For instance, we construct various chains and anti-chains and show the existence of a maximal element among thelo-degrees. (shrink)

Let ⪯R be the preorder of embeddability between countable linear orders colored with elements of Rado's partial order . We show that ⪯R has fairly high complexity with respect to Borel reducibility , although its exact classification remains open.

We address the following question: Can we expand an NIP theory by adding a linear order such that the expansion is still NIP? Easily, if acl(A)= A for all A, then this is true. Otherwise, we give counterexamples. More precisely, there is a totally categorical theory for which every expansion by a linear order has IP. There is also an ω-stable NDOP theory for which every expansion by a linear order interprets pseudofinite arithmetic.

Numerous results about capturing complexity classes of queries by means of logical languages work for ordered structures only, and deal with non-generic, or order-dependent, queries. Recent attempts to improve the situation by characterizing wide classes of finite models where linear order is definable by certain simple means have not been very promising, as certain commonly believed conjectures were recently refuted (Dawar's Conjecture). We take on another approach that has to do with normalization of a given order (rather than (...) with defining a linear order from scratch). To this end, we show that normalizability of linear order is a strictly weaker condition than definability (say, in the least fixpoint logic), and still allows for extending Immerman-Vardi-style results to generic queries. It seems to be the weakest such condition. We then conjecture that linear order is normalizable in the least fixpoint logic for any finitely axiomatizable class of rigid structures. Truth of this conjecture, which is a strengthened version of Stolboushkin's conjecture, would have the same practical implications as Dawar's Conjecture. Finally, we suggest a series of reductions of the two conjectures to specialized classes of graphs, which we believe should simplify further work. (shrink)

A statement of hyperarithmetic analysis is a sentence of second order arithmetic S such that for every Y⊆ω, the minimum ω-model containing Y of RCA0 + S is HYP, the ω-model consisting of the sets hyperarithmetic in Y. We provide an example of a mathematical theorem which is a statement of hyperarithmetic analysis. This statement, that we call INDEC, is due to Jullien [13]. To the author's knowledge, no other already published, purely mathematical statement has been found with this property (...) until now. We also prove that, over RCA0, INDEC is implied by [Formula: see text] and implies ACA0, but of course, neither ACA0, nor ACA 0+ imply it. We introduce five other statements of hyperarithmetic analysis and study the relations among them. Four of them are related to finitely-terminating games. The fifth one, related to iterations of the Turing jump, is strictly weaker than all the other statements that we study in this paper, as we prove using Steel's method of forcing with tagged trees. (shrink)

We consider certain linear orders with a function on them, and discuss for which types of functions the resulting structure is or is not computably categorical. Particularly, we consider computable copies of the rationals with a fixed-point free automorphism, and also ω with a non-decreasing function.

We characterize the linear order types $\tau $ with the property that given any countable linear order $\mathcal {L}$, $\tau \cdot \mathcal {L}$ is a computable linear order iff $\mathcal {L}$ is a computable linear order, as exactly the finite nonempty order types.

The decision problem for positively quantified formulae in the theory of linearly ordered Heyting algebras is known, as a special case of work of Kreisel, to be solvable; a simple solution is here presented, inspired by related ideas in Gödel-Dummett logic.

In recent years large amounts of electronic texts have become available. While the first of these corpora had only a low level of annotation, the more recent ones are annotated with refined syntactic information. To make these rich annotations accessible for linguists, the development of query systems has become an important goal. One of the main difficulties in this task consists in the choice of the right query language, a language which at the same time should be powerful enough to (...) let users formulate the queries they want and which should be efficiently evaluable to keep query response times short. There is a widespread belief that such a query language does not exist. It is therefore the aim of this paper to show that there is indeed a powerful query language that can be efficiently evaluated. We propose the use of monadic second-order logic as a query language. We show that a query in this language can be evaluated in linear time in the size of a tree in the corpus. We also provide examples of complicated linguistic queries expressed in monadic second-order logic thereby demonstrating the high expressive power of the language. (shrink)

We re-express a previous general result in a way which seems easier to remember, using the terminology of infinite games. We show how this can be applied to construct recursive linear orderings, showing, for example, that if there is a ▵ 0 2β + 1 linear ordering of type τ, then there is a recursive ordering of type ω β · τ.

ABSTRACT A new type of calculi is proposed for a first order linear temporal logic. Instead of induction-type postulates the introduced calculi contain a similarity saturation principle, indicating some form of regularity in the derivations of the logic. In a finitary case we obtained the finite set of saturated sequents, showing that ?nothing new? can be obtained continuing the derivation process. Instead of the ?-type rule of inference, an infinitary saturated calculus has an infinite set of saturated sequents, showing that (...) only a ?similar? sequents can be obtained continuing the dérivation process. The saturation calculi have some resemblance with resolution-like calculi. (shrink)

Pursuing the proof-theoretic program of Friedman and Simpson, we begin the study of the metamathematics of countable linear orderings by proving two main results. Over the weak base system consisting of arithmetic comprehension, II 1 1 -CA0 is equivalent to Hausdorff's theorem concerning the canonical decomposition of countable linear orderings into a sum over a dense or singleton set of scattered linear orderings. Over the same base system, ATR0 is equivalent to a version of the Continuum Hypothesis for linear orderings, (...) which states that every countable linear ordering either has countably many or continuum many Dedekind cuts. (shrink)

We study the first-order theories of some natural and important classes of coloured trees, including the four classes of trees whose paths have the order type respectively of the natural numbers, the integers, the rationals, and the reals. We develop a technique for approximating a tree as a suitably coloured linear order. We then present the first-order theories of certain classes of coloured linear orders and use them, along with the approximating technique, to establish complete axiomatisations of the four classes (...) of trees mentioned above. (shrink)

Cohesive powersof computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let$\omega $,$\zeta $, and$\eta $denote the respective order-types of the natural numbers, the integers, and the rationals when thought of as linear orders. We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of$\omega $. If$\mathcal {L}$is a computable copy of$\omega $that is computably isomorphic to the usual presentation of$\omega $, then every cohesive power of$\mathcal {L}$has order-type$\omega + (...) \zeta \eta $. However, there are computable copies of$\omega $, necessarily not computably isomorphic to the usual presentation, having cohesive powers not elementarily equivalent to$\omega + \zeta \eta $. For example, we show that there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \eta $. Our most general result is that if$X \subseteq \mathbb {N} \setminus \{0\}$is a Boolean combination of$\Sigma _2$sets, thought of as a set of finite order-types, then there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$, where$\boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$denotes the shuffle of the order-types inXand the order-type$\omega + \zeta \eta + \omega ^*$. Furthermore, ifXis finite and non-empty, then there is a computable copy of$\omega $with a cohesive power of order-type$\omega + \boldsymbol {\sigma }(X)$. (shrink)

We carry out a systematic investigation of the definability of linear order on classes of finite rigid structures. We obtain upper and lower bounds for the expressibility of linear order in various logics that have been studied extensively in finite model theory, such as least fixpoint logic LFP, partial fixpoint logic PFP, infinitary logic Lω∞ω with a finite number of variables, as well as the closures of these logics under implicit definitions. Moreover, we show that the upper and lower bounds (...) established here cannot be made substantially tighter, unless outstanding conjectures in complexity theory are resolved at the same time. (shrink)

In this paper we define the notion of -linearity for and discuss interpretability (and noninterpretability) of -linear orders in structures and theories.

A low linear order with no computable copy constructed by C. Jockusch and R. Soare has Hausdorff rank equal to $2$. In this regard, the question arises, how simple can be a low linear order with no computable copy from the point of view of the linear order type? The main result of this work is an example of a low strong $\eta $ -representation with no computable copy that is the simplest possible example.

In this paper, we give a classification of ℵ0-categorical coloured linear orders, generalizing Rosenstein's characterization of ℵ0-categorical linear orderings. We show that they can all be built from coloured singletons by concatenation and ℚn-combinations . We give a method using coding trees to describe all structures in our list.

Slaman and Wehner have constructed structures which distinguish the computable Turing degree 0 from the noncomputable degrees, in the sense that the spectrum of each structure consists precisely of the noncomputable degrees. Downey has asked if this can be done for an ordinary type of structure such as a linear order. We show that there exists a linear order whose spectrum includes every noncomputable Δ 0 2 degree, but not 0. Since our argument requires the technique of permitting below a (...) Δ 0 2 set, we include a detailed explanation of the mechanics and intuition behind this type of permitting. (shrink)

The paper introduces a first-order theory in the language of predicate tense logic which contains a single simple axiom. It is shewn that this theory enables times to be referred to and sentences involving ‘now’ and ‘then’ to be formalised. The paper then compares this way of increasing the expressive capacity of predicate tense logic with other mechanisms, and indicates how to generalise the results to other modal and tense systems.

A linear order is -decidable if its universe is and the relations defined by formulas are uniformly computable. This means that there is a computable procedure which, when applied to a formula and a sequence of elements of the linear order, will determine whether or not is true in the structure. A linear order is decidable if the relations defined by all formulas are uniformly computable. These definitions suggest two questions. Are there, for each , -decidable linear orders that are (...) not -decidable? Are there linear orders that are -decidable for all but not decidable? The former was answered in the positive by Moses in 1993. Here we answer the latter, also positively. (shrink)

There is a Turing computable embedding $\Phi $ of directed graphs $\mathcal {A}$ in undirected graphs. Moreover, there is a fixed tuple of formulas that give a uniform effective interpretation; i.e., for all directed graphs $\mathcal {A}$, these formulas interpret $\mathcal {A}$ in $\Phi $. It follows that $\mathcal {A}$ is Medvedev reducible to $\Phi $ uniformly; i.e., $\mathcal {A}\leq _s\Phi $ with a fixed Turing operator that serves for all $\mathcal {A}$. We observe that there is a graph G (...) that is not Medvedev reducible to any linear ordering. Hence, G is not effectively interpreted in any linear ordering. Similarly, there is a graph that is not interpreted in any linear ordering using computable $\Sigma _2$ formulas. Any graph can be interpreted in a linear ordering using computable $\Sigma _3$ formulas. Friedman and Stanley [4] gave a Turing computable embedding L of directed graphs in linear orderings. We show that there is no fixed tuple of $L_{\omega _1\omega }$ -formulas that, for all G, interpret the input graph G in the output linear ordering $L$. Harrison-Trainor and Montalbán [7] have also shown this, by a quite different proof. (shrink)