We give a new proof of a theorem of Shelah which states that for every family of labeled trees, if the cardinality κ of the family is much larger (in the sense of large cardinals) than the cardinality λ of the set of labels, more precisely if the partition relation holds, then there is a homomorphism from one labeled tree in the family to another. Our proof uses a characterization of such homomorphisms in terms of games.

We introduce the appropriate iterated version of the system of ordinal notations from [G1] whose order type is the familiar Howard ordinal. As in [G1], our ordinal notations are partly inspired by the ideas from [P] where certain crucial properties of the traditional Munich' ordinal notations are isolated and used in the cut-elimination proofs. As compared to the corresponding “impredicative” Munich' ordinal notations (see e.g. [B1, B2, J, Sch1, Sch2, BSch]), our ordinal notations arearbitrary terms in the appropriate simple term (...) algebra based on the notion of collapsing functions (which we would rather identify as projective functions). In Sect. 1 below we define the systems of ordinal notationsPRJ( ), for any primitive recursive limit wellordering . In Sect. 2 we prove the crucial well-foundness property by using the appropriate well-quasi-ordering property of the corresponding binary labeled trees [G3]. In Sect. 3 we interprete inPRJ( ) the familiar Veblen-Bachmann hierarchy of ordinal functions, and in Sect. 4 we show that the corresponding Buchholz's system of ordinal notationsOT( ) is a proper subsystem ofPRJ( ), although it has the same order type according to [G3] together with the interpretation from Sect. 2 in the terms of labeled trees. In Sect. 5 we use Friedman's approach in order to obtain an appropriate purely combinatorial statement which is not provable in the theory of iterated inductive definitions ID< λ, for arbitrarily large limit ordinalλ. Formal theories, axioms, etc. used below are familiar in the proof theory of subsystems of analysis (see [BFPS, T, BSch]). (shrink)

We shall give a direct proof of the independence result of a Buchholz style-Hydra Game on labeled finite trees. We shall show that Takeuti-Arai's cut-elimination procedure of $(\Pi^{1}_{1}-CA) + BI$ and of the iterated inductive definition systems can be directly expressed by the reduction rules of Buchholz's Hydra Game. As a direct corollary the independence result of the Hydra Game follows.

This paper studies the relation between some extensions of the non-associative Lambek Calculus NL and their interpretation in tree models (free groupoids). We give various examples of sequents that are valid in tree models, but not derivable in NL. We argue why tree models may not be axiomatizable if we add finitely many derivation rules to NL, and proceed to consider labeled calculi instead.We define two labeled categorial calculi, and prove soundness and completeness for interpretations (...) that are almost the intended one, namely for tree models where some branches of some trees may be resp. all branches of all trees must be infinitely extending. Extrapolating from the experiences in our quite simple systems, we briefly discuss some problems involved with the introduction of labels in categorial grammar, and argue that many of the basic questions are not yet understood. (shrink)

The paper settles an open question concerning Negri-style labeled sequent calculi for modal logics and also, indirectly, other proof systems which make (more or less) explicit use of semantic parameters in the syntax and are thus subsumed by labeled calculi, like Brünnler’s deep sequent calculi, Poggiolesi’s tree-hypersequent calculi and Fitting’s prefixed tableau systems. Specifically, the main result we prove (through a semantic argument) is that labeled calculi for the modal logics K and D remain complete w.r.t. (...) valid sequents whose relational part encodes a tree-like structure, when the unique rule which contains an harmful implicit contraction—by which the condition that the premises be less complex than the conclusion is violated—is modified into a contraction-free one respecting the latter condition, thus making the proof-search space finite. (shrink)

We prove that for any k≥3 each element of the h-quasiorder of finite k-labeled forests is definable in the ordinary first order language and, respectively, each element of the h-quasiorder of countable k-labeled forests is definable in the language Lω1ω, in both cases provided that the minimal non-smallest elements are allowed as parameters. As corollaries, we characterize the automorphism groups of both structures and show that the structure of finite k-forests is atomic. Similar results hold true for two (...) other relevant structures: the h-quasiorder of finite k-labeled trees and of finite k-labeled trees with a fixed label of the root element. (shrink)

We consider the structure of all labeled trees, called also infinite terms, in the first order language with function symbols in a recursive signature of cardinality at least two and at least a symbol of arity two, with equality and a binary relation symbol which is interpreted to be the subtree relation. The existential theory over of this structure is decidable (see Tulipani [9]), but more complex fragments of the theory are undecidable. We prove that the theory of the (...) structure is in , where formulas are those in prenex form consisting of a string of unbounded existential quantifiers followed by a string of arbitrary quantifiers all bounded with respect to . Since the fragment of the theory was already known to be -hard (see Marongiu and Tulipani [5]), it is now established to be -complete. (shrink)

Aristotelian causal theories incorporate some philosophically important features of the concept of cause, including necessity and essential character. The proposed formalization is restricted to one-place predicates and a finite domain of attributes (without individuals). Semantics is based on a labeled tree structure, with truth defined by means of tree paths. A relatively simple causal prefixing mechanism is defined, by means of which causes of propositions and reasoning with causes are made explicit. The distinction of causal and factual (...) explanation are elaborated, and examples of cyclic and convergent causation are given. Soundness and completeness proofs are sketched. (shrink)

A method is described for inducing a type-logical grammar from a sample of bare sentence trees which are annotated by lambda terms, called term-labelled trees . Any type logic from a permitted class of multimodal logics may be specified for use with the procedure, which induces the lexicon of the grammar including the grammatical categories. A first stage of semantic bootstrapping is performed, which induces a general form lexicon from the sample of term-labelled trees using Fulop’s (J Log Lang Inf (...) 14(1):49–86, 2005) procedure. Next we present a two-stage procedure for performing distributional learning by unifying the lexical types that are initially discovered. The first structural unification algorithm in essence unifies the initial family of sets of types so that the resulting grammar will generate all term-labelled trees that follow the usage patterns evident from the learning sample. Further altering the lexical categories to generate a recursively extended language can be accomplished by a second unification. The combined unification algorithm is shown to yield a new type-logical lexicon that extends the learning sample to a possibly infinite (and possibly context-sensitive) language in a principled fashion. Finally, the complete learning strategy is analyzed from the perspective of algorithmic learning theory; the range of the procedure is shown to be a class of term-labelled tree languages which is finitely learnable from good examples (Lange et al in Algorithmic learning theory, Vol 872 of lecture notes in artificial intelligence, Springer, Berlin, pp 423–437), and so is identifiable in the limit as a corollary. (shrink)

We introduce a new convolution kernel for labeled ordered trees with arbitrary subgraph features, and an efficient algorithm for computing the kernel with the same time complexity as that of the parse tree kernel. The proposed kernel is extended to allow mutations of labels and structures without increasing the order of computation time. Moreover, as a limit of generalization of the tree kernels, we show a hardness result in computing kernels for unordered rooted labeled trees with (...) arbitrary subgraph features. (shrink)

We say that a linear ordering is extendible if every partial ordering that does not embed can be extended to a linear ordering which does not embed either. Jullien’s theorem is a complete classification of the countable extendible linear orderings. Fraïssé’s conjecture, which is actually a theorem, is the statement that says that the class of countable linear ordering, quasiordered by the relation of embeddability, contains no infinite descending chain and no infinite antichain. In this paper we study the strength (...) of these two theorems from the viewpoint of Reverse Mathematics and Effective Mathematics. As a result of our analysis we get that they are equivalent over the basic system of .We also prove that Fraïssé’s conjecture is equivalent, over , to two other interesting statements. One that says that the class of well founded labeled trees, with labels from {+,−}, and with a very natural order relation, is well quasiordered. The other statement says that every linear ordering which does not contain a copy of the rationals is equimorphic to a finite sum of indecomposable linear orderings.While studying the proof theoretic strength of Jullien’s theorem, we prove the extendibility of many linear orderings, including ω2 and η, using just . Moreover, for all these linear orderings, , we prove that any partial ordering, , which does not embed has a linearization, hyperarithmetic in , which does not embed. (shrink)

Kruskal proved that finite trees are well-quasi-ordered by hom(e)omorphic embeddability. Friedman observed that this statement is not provable in predicative analysis. Friedman also proposed (see in [Simpson]) some stronger variants of the Kruskal theorem dealing with finite labeled trees under home(e)omorphic embeddability with a certain gap-condition, where labels are arbitrary finite ordinals from a fixed initial segment of ω. The corresponding limit statement, expressing that for all initial segments of ω these labeled trees are well-quasi-ordered, is provable in (...) Π 1 1 -CA, but not in the analogous theory Π 1 1 -CA 0 with induction restricted to sets. Schutte and Simpson proved that the one-dimensional case of Friedman's limit statement dealing with finite labeled intervals is not provable in Peano arithmetic. However, Friedman's gap-condition fails for finite trees labeled with transfinite ordinals. In [Gordeev 1] I proposed another gap-condition and proved the resulting one-dimensional modified statements for all (countable) transfinite ordinal-labels. The corresponding universal modified one-dimensional statement UM 1 is provable in (in fact, is equivalent to) the familiar theory ATR 0 whose proof-theoretic ordinal is Γ 0 . In [Gordeev 1] I also announced that, in the general case of arbitrarily-branching finite trees labeled with transfinite ordinals, in the proof-theoretic sense the hierarchy of the limit modified statements $\mathbf{M}_{ (which are denoted by LM λ in the present note) is as strong as the hierarchy of the familiar theories of iterated inductive definitions (more precisely, see [Gordeev 1, Concluding Remark 3]). In this note I present a "positive" proof of the full universal modified statement UM, together with a short proof of the crucial "reverse" results which is based on Okada's interpretation of the well-established ordinal notations of Buchholz corresponding to the theories of iterated inductive definitions. Formally the results are summarized in $\S5$ below. (shrink)

We show that under the proper forcing axiom the class of all Aronszajn lines behave like [Formula: see text]-scattered orders under the embeddability relation. In particular, we are able to show that the class of better-quasi-order labeled fragmented Aronszajn lines is itself a better-quasi-order. Moreover, we show that every better-quasi-order labeled Aronszajn line can be expressed as a finite sum of labeled types which are algebraically indecomposable. By encoding lines with finite labeled trees, we are also (...) able to deduce a decomposition result, that for every Aronszajn line [Formula: see text] there is an integer [Formula: see text] such that for any finite coloring of [Formula: see text] there is subset [Formula: see text] of [Formula: see text] isomorphic to [Formula: see text] which uses no more than [Formula: see text] colors. (shrink)

We prove that for any computable successor ordinal of the form α = δ + 2k there exists computable torsion-free abelian group that is relatively Δα0 -categorical and not Δα−10 -categorical. Equivalently, for any such α there exists a computable TFAG whose initial segments are uniformly described by Σαc infinitary computable formulae up to automorphism, and there is no syntactically simpler family of formulae that would capture these orbits. As far as we know, the problem of finding such optimal examples (...) of Δα0-categorical TFAGs for arbitrarily large α was first raised by Goncharov at least 10 years ago, but it has resisted solution 315–356]). As a byproduct of the proof, we introduce an effective functor that transforms a 0″-computable worthy labeled tree into a computable TFAG. We expect that this techni... (shrink)

In this paper we prove general exact unprovability results that show how a threshold between provability and unprovability of a finite well-quasi-orderedness assertion of a combinatorial class is transformed by the sequence-construction, multiset-construction, cycle-construction and labeled-tree-construction. Provability proofs use the asymptotic pigeonhole principle, unprovability proofs use Weiermann-style compression techniques and results from analytic combinatorics.

In the Thirties, European personalism was an inspirational philosophical movement, with its birthplace in France, but with proponents and sympathizers in many other countries as well. Following the Second World War, Christian-Democratic politicians translated personalistic ideas into a political doctrine. Sometimes they still refer to personalism, but most often this reference is little more than a nostalgic salute. In the mainstream of Anglo-Saxon political philosophy, there are practically no references to personalistic philosophers. Is personalism exhausted as a philosophy or political (...) ideology? Yes and no. Paul Ricoeur, writing in Esprit , summed up the situation like this: “personalism is dead”, but he was careful to mention a “return of the person”. Indeed, no tradition or movement can simply perpetuate itself. It must, in order to continue making history, always abolish itself as a `system' so as to make room for the unsaid and the unthought in its tradition, an idea that Mounier also fervently believed in.To better situate the current discussion of personalism, however, it is necessary to look back to the original characteristics of personalism in the Thirties. As a response to the crisis provoked by the economic depression, failing democracy and existential uncertainty, there arose in France a number of `non-conformist movements' who labelled themselves personalistic. They did not constitute a unified movement with a commonly shared theory. It was rather a collection of `personalisms'. The article by the historian Christian Roy about the ecological personalism of Bernard Charbonneau and Jacques Ellul sheds interesting light on the multiple origins of French personalism, which is all too easily identified with the work of Maritain and Mounier alone. The work of Jacques Maritain, and the network of writers and artists surrounding him, undoubtedly remains a significant historical reference point when speaking of personalism.Another group was formed around Alexandre Marc who, along with Raymond Aron, Arnaud Dandieu, Daniel-Rops and Denis de Rougemont, kept the journal Ordre Nouveau alive for five years . They elaborated the idea of federalism as a way out of liberalism and totalitarianism. The most important and durable group, however, was formed by the movement and journal Esprit, founded in 1932 by Emmanuel Mounier and George Izard. In order to stress the historical importance of Esprit, we are including here a testimony from 1982, written by Paulette Mounier, the founder's wife, in which she looks back on 50 years of Esprit. After the war, some new and related groups formed, such as Economy and Humanism around Louis-Joseph Lebret. An historical survey of the dissemination of personalistic centres and movements, not only in France but over all of Europe, would be material for a stimulating historical research project. In this issue, there will also be mention of, among others, the Prague personalism of Jan Patocka and Vaclav Havel, the Leuven personalism of Louis Janssens, and the Polish personalism of Tadeusz Mazowiecki and others. But this list is far from exhaustive.What unites these various branches of the personalistic tree? It is a certain conception — or better perhaps: a certain attitude to the human person. Personalists were not seeking in the first instance a new academic theory about the person, but rather a practical philosophy of engagement. In the Thirties, quite a few personalists finished their university studies and chose not for an academic career but for non-conformist, demanding and vulnerable commitments with limited financial means. What motivated them? Primarily a strong sense that the time in which they were living was a turning point, one which was being ignored by the academic world. They interpreted the diverse economic, political and cultural crisis phenomena as symptoms of a more global crisis of civilization which demanded a response through radical change.Hence a certain rhetoric of a `new order', `spiritual revolution', `radical reform' and `rebirth'. But the rhetoric was supported by innovative ideas regarding political federalism, the third way economy and human alienation. The motivation for all this derived from a strong commitment to defend the concrete human person against the arrogance of systems, bureaucracies and ideologies, while at the same time avoiding the pitfalls of individualism — the reason why some personalists always qualified personalism as `communitarian'.In fact, much of what presents itself as communitarian philosophy today is a retrieval of personalistic themes from the Thirties applied to the current situation, a situation which is also interpreted by communitarians as a global cultural crisis. One should not forget, however, that alongside and sometimes opposed to the communitarian theme with its call to bring people back to their communitarian roots, personalists underscored the priority of metaphysics over politics, a theme that can likewise be found in the writings of personalistic dissidents in Eastern Europe. In the words of Mounier in Qu'est-ce que le personnalisme : “personalism combines faith in a certain human absolute with a progressive historical experience”.To what extent is personalistic thinking still relevant today? Its current relevance will be examined in three ways. In the first section, a number of articles are presented which illustrate the active presence of personalistic thought in the domains of politics and applied ethics. Vaclav Havel sent one of his recent addresses in which he links the theme of human rights with that of a world spirituality. His article is preceded by an introduction by Guido Van Heeswijck, situating Prague personalism.The need for an orientational philosophy of the person is not only manifest today in the political arena. Developments in economics, ecology, health care, the media, technology and in the world of the professions have had an extraordinarily large impact on the human person's lifeworld. The whole area of applied ethics requires a dynamic and orientational concept of the person. The contributions by Paul Schotsmans and Luk Bouckaert are seeking a personalistic point of departure for applied ethics. The more historical article by Christian Roy on ecological personalism has been included in the first section because it can be inspiring for an environmental ethics.The second section is more philosophical. To what extent does the `personalistic' conception of the person put forward in the Thirties still have any relevance today, following the waves of structuralism, post-structuralism and postmodernism? Paul Ricoeur's article, Approaching the Human Person — originally published in Esprit in 1990 and now translated for the first time — can be seen as a reference text. Ricoeur shows in what sense the concept of the person must be broadened in order to continue functioning. The person as `narrative identity' can only write history through the medium of language and institutions. Starting from very different assumptions, the articles by Louis Janssens & Joseph Selling and the analysis of Roland Breeur also explore the idea that a person is what he is only when his identity is opened up, touched by an exteriority or conceived as a focal point . It is this radical openness and vulnerability that gives the person its historical and transcendent dynamic, and prevents us from encapsulating it in existing systems, theories and power relations. The connection with Emmanuel Levinas and his hermeneutic of the idea of the infinite is an obvious one to draw.The third section contains a historical survey in which a number of active `personalistic' centres and journals are presented.Various European centres that appeal explicitly to some form of personalistic thinking were posed the following questions: What is the main historical reference to personalism at your centre? and How do you implement, today, a personalist credo in your work? John Dick organized the responses to these questions under a number of headings. This survey aims to provide not so much an exhaustive but a representative picture of the ways in which European personalism lives on as a mosaic of centres engaged in everyday history. (shrink)

Organismal death is foundational to the evolution of life, and many biological concepts such as natural selection and life history strategy are so fashioned only because individuals are mortal. Organisms, irrespective of their organization, are composed of basic functional units—cells—and it is our understanding of cell death that lies at the heart of most general explanatory frameworks for organismal mortality. Cell death can be exogenous, arising from transmissible diseases, predation, or other misfortunes, but there are also endogenous forms of death (...) that are sometimes the result of adaptive evolution. These endogenous forms of death—often labeled programmed cell death, PCD—originated in the earliest cells and are maintained across the tree of life. Here, we consider two problematic issues related to PCD (and cell mortality generally). First, we trace the original discoveries of cell death from the nineteenth century and place current conceptions of PCD in their historical context. Revisions of our understanding of PCD demand a reassessment of its origin. Our second aim is thus to structure the proposed origin explanations of PCD into coherent arguments. In our analysis we argue for the evolutionary concept of PCD and the viral defense-immunity hypothesis for the origin of PCD. We suggest that this framework offers a plausible account of PCD early in the history of life, and also provides an epistemic basis for the future development of a general evolutionary account of mortality. (shrink)

We show that arbitrary tautologies of Johansson’s minimal propositional logic are provable by “small” polynomial-size dag-like natural deductions in Prawitz’s system for minimal propositional logic. These “small” deductions arise from standard “large” tree-like inputs by horizontal dag-like compression that is obtained by merging distinct nodes labeled with identical formulas occurring in horizontal sections of deductions involved. The underlying geometric idea: if the height, h(∂), and the total number of distinct formulas, ϕ(∂), of a given tree-like deduction ∂ (...) of a minimal tautology ρ are both polynomial in the length of ρ, |ρ|, then the size of the horizontal dag-like compression ∂ᶜ is at most h(∂)×ϕ(∂), and hence polynomial in |ρ|. That minimal tautologies ρ are provable by tree-like natural deductions ∂ with |ρ|-polynomial h(∂) and ϕ(∂) follows via embedding from Hudelmaier’s result that there are analogous sequent calculus deductions of sequent ⇒ρ. The notion of dag-like provability involved is more sophisticated than Prawitz’s tree-like one and its complexity is not clear yet. Our approach nevertheless provides a convergent sequence of NP lower approximations of PSPACE-complete validity of minimal logic. (shrink)

A central concern of generative grammar is the relationship between hierarchy and word order, traditionally understood as two dimensions of a single syntactic representation. A related concern is directionality in the grammar. Traditional approaches posit process-neutral grammars, embodying knowledge of language, put to use with infinite facility both for production and comprehension. This has crystallized in the view of Merge as the central property of syntax, perhaps its only novel feature. A growing number of approaches explore grammars with different directionalities, (...) often with more direct connections to performance mechanisms. This paper describes a novel model of universal grammar as a one-directional, universal parser. Mismatch between word order and interpretation order is pervasive in comprehension; in the present model, word order is language-particular and interpretation order (i.e., hierarchy) is universal. These orders are not two dimensions of a unified abstract object (e.g., precedence and dominance in a single tree); rather, both are temporal sequences, and UG is an invariant real-time procedure (based on Knuth's stack-sorting algorithm) transforming word order into hierarchical order. This shift in perspective has several desirable consequences. It collapses linearization, displacement, and composition into a single performance process. The architecture provides a novel source of brackets (labeled unambiguously and without search), which are understood not as part-whole constituency relations, but as storage and retrieval routines in parsing. It also explains why neutral word order within single syntactic cycles avoids 213-like permutations. The model identifies cycles as extended projections of lexical heads, grounding the notion of phase. This is achieved with a universal processor, dispensing with parameters. The empirical focus is word order in noun phrases. This domain provides some of the clearest evidence for 213-avoidance as a cross-linguistic word order generalization. Importantly, recursive phrase structure “bottoms out” in noun phrases, which are typically a single cycle (though further cycles may be embedded, e.g., relative clauses). By contrast, a simple transitive clause plausibly involves two cycles (vP and CP), embedding further nominal cycles. In the present theory, recursion is fundamentally distinct from structure-building within a single cycle, and different word order restrictions might emerge in larger domains like clauses. (shrink)

We present an epistemic default logic, based on the metaphore of a meta-level architecture. Upward reflection is formalized by a nonmonotonic entailment relation, based on the objective facts that are either known or unknown at the object level. Then, the meta (monotonic) reasoning process generates a number of default-beliefs of object-level formulas. We extend this framework by proposing a mechanism to reflect these defaults down. Such a reflection is seen as essentially having a temporal flavour: defaults derived at the meta-level (...) are projected as facts in a next object level state. In this way, we obtain temporal models for default reasoning in meta-level formalisms which can be conceived as labeled branching trees. Thus, descending the tree corresponds to shifts in time that model downward reflection, whereas the branching of the tree corresponds to ways of combining possible defaults. All together, this yields an operational or procedural semantics of reasoning by default, which admits one to reason about it by means of branching-time temporal logic. Finally, we define sceptical and credulous entailment relations based on these temporal models and we characterize Reiter extensions in our semantics. (shrink)

This thesis introduces the "method of structural refinement", which serves as a means of transforming the relational semantics of a modal and/or constructive logic into an 'economical' proof system by connecting two proof-theoretic paradigms: labelled and nested sequent calculi. The formalism of labelled sequents has been successful in that cut-free calculi in possession of desirable proof-theoretic properties can be automatically generated for large classes of logics. Despite these qualities, labelled systems make use of a complicated syntax that explicitly incorporates the (...) semantics of the associated logic, and such systems typically violate the subformula property to a high degree. By contrast, nested sequent calculi employ a simpler syntax and adhere to a strict reading of the subformula property, making such systems useful in the design of automated reasoning algorithms. However, the downside of the nested sequent paradigm is that a general theory concerning the automated construction of such calculi (as in the labelled setting) is essentially absent, meaning that the construction of nested systems and the confirmation of their properties is usually done on a case-by-case basis. The refinement method connects both paradigms in a fruitful way, by transforming labelled systems into nested (or, refined labelled) systems with the properties of the former preserved throughout the transformation process. To demonstrate the method of refinement and some of its applications, we consider grammar logics, first-order intuitionistic logics, and deontic STIT logics. The introduced refined labelled calculi will be used to provide the first proof-search algorithms for deontic STIT logics. Furthermore, we employ our refined labelled calculi for grammar logics to show that every logic in the class possesses the effective Lyndon interpolation property. (shrink)

This important book provides a new unifying methodology for logic. It replaces the traditional view of logic as manipulating sets of formulas with the notion of structured families of labelled formulas with algebraic structures. This approach has far reaching consequences for the methodology of logics and their semantics, and the book studies the main features of such systems along with their applications. It will interest logicians, computer scientists, philosophers and linguists.

The subject of Labelled Non-Classical Logics is the development and investigation of a framework for the modular and uniform presentation and implementation of non-classical logics, in particular modal and relevance logics. Logics are presented as labelled deduction systems, which are proved to be sound and complete with respect to the corresponding Kripke-style semantics. We investigate the proof theory of our systems, and show them to possess structural properties such as normalization and the subformula property, which we exploit not only to (...) establish advantages and limitations of our approach with respect to related ones, but also to give, by means of a substructural analysis, a new proof-theoretic method for investigating decidability and complexity of (some of) the logics we consider. All of our deduction systems have been implemented in the generic theorem prover Isabelle, thus providing a simple and natural environment for interactive proof development. Labelled Non-Classical Logics is essential reading for researchers and practitioners interested in the theory and applications of non-classical logics. (shrink)

C. I. Lewis’ systems were the first axiomatisations of modal logics. However some of those systems are non-normal modal logics, since they do not admit a full rule of necessitation, but only a restricted version thereof. We provide G3-style labelled sequent calculi for Lewis’ non-normal propositional systems. The calculi enjoy good structural properties, namely admissibility of structural rules and admissibility of cut. Furthermore they allow for straightforward proofs of admissibility of the restricted versions of the necessitation rule. We establish completeness (...) of the calculi and we discuss also related systems. (shrink)

We present a labelled version of Lambek Calculus without unit, and we use it to prove a completeness theorem for Lambek Calculus with respect to some relational semantics.

Labelled tableau systems are developed for subintuitionistic logics \, \ and \. These subintuitionistic logics are embedded into corresponding normal modal logics. Hintikka’s model systems are applied to prove the completeness of labelled tableau systems. The finite model property, decidability and disjunction property are obtained by labelled tableau method.

We introduce an effective translation from proofs in the display calculus to proofs in the labelled calculus in the context of tense logics. We identify the labelled calculus proofs in the image of this translation as those built from labelled sequents whose underlying directed graph possesses certain properties. For the basic normal tense logic Kt, the image is shown to be the set of all proofs in the labelled calculus G3Kt.

The paper is devoted to the concise description of some Natural Deduction System (ND for short) for Linear Temporal Logic. The system's distinctive feature is that it is labelled and analytical. Labels convey necessary semantic information connected with the rules for temporal functors while the analytical character of the rules lets the system work as a decision procedure. It makes it more similar to Labelled Tableau Systems than to standard Natural Deduction. In fact, our solution of linearity representation is rather (...) independent of the underlying proof method, provided that some form of (analytic) cut is admissible. We will also discuss some generalisations of the system and compare it with other formalizations of linearity. (shrink)

We propose a family of Labelled Deductive Conditional Logic systems by defining a Labelled Deductive formalisation for the propositional conditional logics of normality proposed by Boutilier and Lamarre. By making use of the Compilation approach to Labelled Deductive Systems we define natural deduction rules for conditional logics and prove that our formalisation is a generalisation of the conditional logics of normality.

Resolution is an effective deduction procedure for classical logic. There is no similar "resolution" system for non-classical logics (though there are various automated deduction systems). The paper presents resolution systems for intuistionistic predicate logic as well as for modal and temporal logics within the framework of labelled deductive systems. Whereas in classical predicate logic resolution is applied to literals, in our system resolution is applied to L(abelled) R(epresentation) S(tructures). Proofs are discovered by a refutation procedure defined on LRSs, that imposes (...) a hierarchy on clause sets of such structures together with an inheritance discipline. This is a form of Theory Resolution. For intuitionistic logic these structures are called I(ntuitionistic) R(epresentation) S(tructures). Their hierarchical structure allows the restriction of unification of individual variables and/or constants without using Skolem functions. This structures must therefore be preserved when we consider other (non-modal) logics. Variations between different logics are captured by fine tuning of the inheritance properties of the hierarchy. For modal and temporal logics IRS's are extended to structures that represent worlds and/or times. This enables us to consider all kinds of combined logics. (shrink)

We propose to represent the syntax and semantics of natural languages with labelled proof nets in the implicative fragment of intuitionistic linear logic. Resource-sensitivity of linear logic is used to express all dependencies between the syntactic constituents of a sentence in the form of a proof net. Phonological and semantic labelling of the proof net from its inputs to the unique output are used to produce the well-formed phonological form and the semantic representation of a sentence from entries of a (...) lexicon. In this way we obtain a linguistic model of great flexibility because labelling is not completely determined logically: it is used to introduce linguistic constraints which go beyond the underlying logic. (shrink)

In this paper a uniform methodology to perform natural\ndeduction over the family of linear, relevance and intuitionistic\nlogics is proposed. The methodology follows the Labelled\nDeductive Systems (LDS) discipline, where the deductive process\nmanipulates {\em declarative units} -- formulas {\em labelled}\naccording to a {\em labelling algebra}. In the system described\nhere, labels are either ground terms or variables of a given {\em\nlabelling language} and inference rules manipulate formulas and\nlabels simultaneously, generating (whenever necessary)\nconstraints on the labels used in the rules. A set of natural\ndeduction style (...) inference rules is given, and the notion of a\n{\em derivation} is defined which associates a labelled natural\ndeduction style ``structural derivation'' with a set of generated\nconstraints. Algorithmic procedures, based on a technique called\n{\em resource abduction\/}, are defined to solve the constraints\ngenerated within a structural derivation, and their termination\nconditions discussed. A natural deduction derivation is then\ndefined to be {\em correct} with respect to a given substructural\nlogic, if, under the condition that the algorithmic procedures\nterminate, the associated set of constraints is satisfied with\nrespect to the underlying labelling algebra. Finally, soundness\nand completeness of the natural deduction system are proved with\nrespect to the LKE tableaux system \cite{daga:LAD}.\footnote{Full\nversion of a paper presented at the {\em 3rd Workshop on Logic,\nLanguage, Information and Computation\/} ({\em WoLLIC'96\/}), May\n8--10, Salvador (Bahia), Brazil, organised by Univ.\ Federal de\nPernambuco (UFPE) and Univ.\ Federal da Bahia (UFBA), and\nsponsored by IGPL, FoLLI, and ASL.}. (shrink)

In previous work we gave an approach, based on labelled natural deduction, for formalizing proof systems for a large class of propositional modal logics that includes K, D, T, B, S4, S4.2, KD45, and S5. Here we extend this approach to quantified modal logics, providing formalizations for logics with varying, increasing, decreasing, or constant domains. The result is modular with respect to both properties of the accessibility relation in the Kripke frame and the way domains of individuals change between worlds. (...) Our approach has a modular metatheory too; soundness, completeness and normalization are proved uniformly for every logic in our class. Finally, our work leads to a simple implementation of a modal logic theorem prover in a standard logical framework. (shrink)

Labelled sequent calculi are provided for a wide class of normal modal systems using truth values as labels. The rules for formula constructors are common to all modal systems. For each modal system, specific rules for truth values are provided that reflect the envisaged properties of the accessibility relation. Both local and global reasoning are supported. Strong completeness is proved for a natural two-sorted algebraic semantics. As a corollary, strong completeness is also obtained over general Kripke semantics. A duality result (...) is established between the category of sober algebras and the category of general Kripke structures. A simple enrichment of the proposed sequent calculi is proved to be complete over standard Kripke structures. The calculi are shown to be analytic in a useful sense. (shrink)

There exist two notions of equivalence of behavior between states of a Labelled Markov Process (LMP): state bisimilarity and event bisimilarity. The first one can be considered as an appropriate generalization to continuous spaces of Larsen and Skou’s probabilistic bisimilarity, whereas the second one is characterized by a natural logic. C. Zhou expressed state bisimilarity as the greatest fixed point of an operator that there is such a process with an uncountable Zhou ordinal.

Usually in logic, proof systems are defined having in mind proving properties like validity and semantic consequence. It seems worthwhile to address the problem of having proof systems where satisfiability is a primitive notion in the sense that a formal derivation means that a finite set of formulas is satisfiable. Moreover, it would be useful to cover within the same framework as many logics as possible. We consider Kripke semantics where the properties of the constructors are provided by valuation constraints (...) as the common ground of those logics. This includes for instance intuitionistic logic, paraconsistent Nelson’s logic ${\textsf{N4}}$, paraconsistent logic ${\textsf{imbC}}$ and modal logics among others. After specifying a logic by those valuation constraints, we show how to induce automatically and from scratch an existential proof system for that logic. The rules of the proof system are shown to be invertible. General results of soundness and completeness are proved and then applied to the logics at hand. (shrink)

This paper challenges the negative attitudes towards labelled proof systems, usually referred to as semantic pollution, by arguing that such critiques overlook the full potential of labelled calculi. The overarching objective is to develop a practice-based philosophical analysis of labelled calculi to provide insightful considerations regarding their proof-theoretic and philosophical value. To achieve this, successful applications of labelled calculi and related results will be showcased, and comparisons with other relevant works will be discussed. The paper ends by advocating for a (...) more practice-based approach towards the philosophical understanding of proof systems and their role in structural proof theory. (shrink)

Regarding the determination of vulnerability, the bioethics community has univocally jettisoned “labelled groups”, groups whose membership confers a context-invariant “vulnerable” status to their members. While the usual reasons against the sole use of labelled groups to determine the vulnerability of individuals are sound, labelled groups as exemplars of vulnerability can play indispensable roles in bioethical reasoning. In this article, I argue against the wholesale jettisoning of labelled groups by showing how they can be useful.

Pietraszewski contends that group representations that rely on a “containment metaphor” fail to adequately capture phenomena of group dynamics such as shifts in allegiances. We argue, in contrast, that social categories allow for computationally efficient, richly structured, and flexible group representations that explain some of the most intriguing aspects of social group behaviour.

This paper is about non-labelled proof-systems for hybrid logic, that is, proofsystems where arbitrary formulas can occur, not just satisfaction statements. We give an overview of such proof-systems, focusing on analytic systems: Natural deduction systems, Gentzen sequent systems and tableau systems. We point out major results and we discuss a couple of striking facts, in particular that nonlabelled hybrid-logical natural deduction systems are analytic, but this is not proved in the usual way via step-by-step normalization of derivations.