Circle graphs and monadic second-order logic

This article is part of a project consisting in expressing, whenever possible, graph properties and graph transformations in monadic second-order logic or in its extensions using modulo p cardinality set predicates or auxiliary linear orders. A circle graph is the intersection graph of a set of chords of a circle. Such a set is called a chord diagram. It can also be described by a word with two occurrences of each letter, called a double occurrence word. If a circle graph is prime for the split (or join) decomposition defined by Cunnigham, it has a unique representation by a chord diagram, and this diagram can be defined by monadic second-order formulas with the even cardinality set predicate. By using the (canonical) split decomposition of a circle graph, we define in monadic second-order logic with auxiliary linear orders all its chord diagrams. This construction uses the fact that the canonical split decomposition of a graph can be constructed in monadic second-order logic with help of an arbitrary linear order. We prove that the order of first occurrences of the letters in a double occurrence word w that represents a connected circle graph determines this word in a unique way. The word w can be defined by a monadic second-order formula from the word of first occurrences of letters. We also prove that a set of circle graphs has bounded clique-width if and only if all the associated chord diagrams have bounded tree-width.     

A second-order relevance logic with modality

In this paper a system, RPF, of second-order relevance logic with S5 necessity is presented which contains a defined, notion of identity for propositions. A complete semantics is provided. It is shown that RPF allows for more than one necessary proposition. RPF contains primitive syntactic counterparts of the following semantic notions: (1) the reflexive, symmetrical, transitive binary alternativeness relation for S5 necessity, (2) the ternary Routley-Meyer alternativeness relation for implication, and (3) the Routley-Meyer notion of a prime intensional theory, as well as defined syntactic counterparts, of the semantic notions of a possible world and the Routley-Meyer ^* operator.     

Classical second-order intensional logic with maximal propositions

Conclusion By the standards presented in the Introduction, CMFC2 is deficient on at least one ontological ground: ‘∀’ is a syncategorematic expression and so CMFC2 is not an ideal language. To some there may be an additional difficulty: any two wffs provably equivalent in the classical sense are provably identical. We hope in sequel to present systems free of these difficulties, free either of one or the other, or perhaps both. This work was done with the aid of Canada Council Grant S74-0551-S1.     

The Ackermann approach for modal logic,correspondence theory and second-order reduction

The problem of eliminating second-order quantification over predicate symbols is in general undecidable. Since an application of second-order quantifier elimination is correspondence theory in modal logic, understanding when second-order quantifier elimination methods succeed is an important problem that sheds light on the kinds of axioms that are equivalent to first-order correspondence properties and can be used to obtain complete axiomatizations for modal logics. This paper introduces a substitution-rewrite approach based on Ackermann?s Lemma to second-order quantifier elimination in modal logic. Compared to related approaches, the approach includes a number of enhancements: The quantified symbols that need to be eliminated can be flexibly specified. The inference rules are restricted by orderings compatible with the elimination order, which provides more control and reduces non-determinism in derivations thereby increasing the efficiency and success rate. The approach is equipped with a powerful notion of redundancy, allowing for the flexible definition of practical simplification and optimization techniques. We present correctness, termination and canonicity results, and consider two applications: (i) computing first-order frame correspondence properties for modal axioms and rules, and (ii) rewriting second-order modal problems to equivalent simpler forms. The approach allows us to define and characterize two new classes of formulae, which are elementary and canonical, and subsume the class of Sahlqvist formulae and the class of monadic inductive formulae.     

Embeddings between the elementary ontology with an atom and the monadic second-order predicate logic

Let EOA be the elementary ontology augmented by an additional axiom S (S S), and let LS be the monadic second-order predicate logic. We show that the mapping which was introduced by V. A. Smirnov is an embedding of EOA into LS. We also give an embedding of LS into EOA.     

The monadic second-order logic of graphs XV: On a conjecture by D. Seese

A conjecture by D. Seese states that if a set of graphs has a decidable monadic second-order theory, then it is the image of a set of trees under a transformation of relational structures defined by monadic second-order formulas, or equivalently, has bounded clique-width. We prove that this conjecture is true if and only if it is true for the particular cases of bipartite undirected graphs, of directed graphs, of partial orders and of comparability graphs. We also prove that it is true for line graphs, for interval graphs and for partial orders of dimension 2. Our treatment of certain countably infinite graphs uses a representation of countable linear orders by binary trees that can be constructed by monadic second-order formulas. By using a counting argument, we show the intrinsic limits of the methods used here to handle this conjecture.     

Wittgenstein and logic

In his Tractatus Logico-Philosophicus Ludwig Wittgenstein (1889–1951) presents the concept of order in terms of a notational iteration that is completely logical but not part of logic. Logic for him is not the foundation of mathematical concepts but rather a purely formal way of reflecting the world that at the minimum adds absolutely no content. Order for him is not based on the concepts of logic but is instead revealed through an ideal notational series. He states that logic is “transcendental”. As such it requires an ideal that his philosophical method eventually forces him to reject. I argue that Wittgenstein’s philosophy is more dialectical than transcendental.     

Reasoning and logic

Gilbert Harman, in Logic and Reasoning (Synthese 60 (1984), 107–127) describes an unsuccessful attempt ... to develop a theory which would give logic a special role in reasoning. Here reasoning is psychological, a procedure for revising one's beliefs. In the present paper, I construe reasoning sociologically, as a process of linguistic interaction; and show how both reasoning in the psychologistic sense and logic are related to that process.     

Probability and logic

The paper is an attempt to show that the formalism of subjective probability has a logical interpretation of the sort proposed by Frank Ramsey: as a complete set of constraints for consistent distributions of partial belief. Though Ramsey proposed this view, he did not actually establish it in a way that showed an authentically logical character for the probability axioms (he started the current fashion for generating probabilities from suitably constrained preferences over uncertain options). Other people have also sought to provide the probability calculus with a logical character, though also unsuccessfully. The present paper gives a completeness and soundness theorem supporting a logical interpretation: the syntax is the probability axioms, and the semantics is that of fairness (for bets).