This paper presents a generalization of Fine’s completeness theorem for transitive logics of finite width, and proves the Kripke completeness of transitive logics of finite “suc-eq-width”. The frame condition for each finite suc-eq-width axiom requires, in rooted transitive frames, a finite upper bound of cardinality for antichains of points with different proper successors. The paper also presents a generalization of Rybakov’s completeness theorem for transitive logics of prefinite width, and proves the Kripke completeness of transitive logics of prefinite “suc-eq-width”. The (...) frame condition for each prefinite suc-eq-width axiom requires, in rooted transitive frames, a finite upper bound of cardinality for antichains of points that have a finite lower bound of depth and have different proper successors. We will construct continuums of transitive logics of finite suc-eq-width but not of finite width, and continuums of those of prefinite suc-eq-width but not of prefinite width. This shows that our new completeness results cover uncountably many more logics than Fine’s theorem and Rybakov’s theorem respectively. (shrink)

Say that two sentences are factually equivalent when they describe the same facts or situations, understood as worldly items, i.e. as bits of reality rather than as representations of reality. The notion of factual equivalence is certainly of central interest to philosophical semantics, but it plays a role in a much wider range of philosophical areas. What is the logic of factual equivalence? This paper attempts to give a partial answer to this question, by providing an answer (...) the following, more specific question: Given a standard propositional language with negation, conjunction and disjunction as primitive operators, which sentences of the language should be taken to be factually equivalent by virtue of their logical form? The system for factual equivalence advocated in this paper is a proper fragment of the first-degree system for the logic of analytic equivalence put forward in the late seventies by R. B. Angell. I provide the system with two semantics, both formulated in terms of the notion of a situation’s being fittingly described by a linguistic item. In the final part of the paper I argue, contra a view I defended in my “Grounding and Truth-Functions”, that the logic for factual equivalence I advocate here should be preferred to Angell’s logic if one wishes to follow the general conception of the relationships between factual equivalence and the notion of grounding put forward in the 2010 paper. (shrink)

Working under large cardinal assumptions such as supercompactness, we study the Borel reducibility between equivalence relations modulo restrictions of the nonstationary ideal on some fixed cardinal κ. We show the consistency of Eλ-clubλ++,λ++, the relation of equivalence modulo the nonstationary ideal restricted to Sλλ++ in the space λ++, being continuously reducible to Eλ+-club2,λ++, the relation of equivalence modulo the nonstationary ideal restricted to Sλ+λ++ in the space 2λ++. Then we show that for κ ineffable Ereg2,κ, the relation (...) of equivalence modulo the nonstationary ideal restricted to regular cardinals in the space 2κ is Σ11-complete. We finish by showing that, for Π21-indescribable κ, the isomorphism relation between dense linear orders of cardinality κ is Σ11-complete. (shrink)

The four-valued semantics of Belnap–Dunn logic, consisting of the truth values True, False, Neither, and Both, gives rise to several nonclassical logics depending on which feature of propositions we wish to preserve: truth, nonfalsity, or exact truth. Interpreting equality of truth values in this semantics as material equivalence of propositions, we can moreover see the equational consequence relation of this four-element algebra as a logic of material equivalence. In this paper, we axiomatize all combinations of these (...) four-valued logics, for example, the logic of truth and exact truth or the logic of truth and material equivalence. These combined systems are consequence relations which allow us to express implications involving more than one of these features of propositions. (shrink)

This paper presents the main assumptions of Andrzej Grzegorczyk’s last research project concerning the logic of synonymity. It shows that the basis of logic of analytic equivalence, presented in the first part of the work, fully corresponds with these assumptions.

This paper proves the finite axiomatizability of transitive modal logics of finite depth and finite width w.r.t. proper-successor-equivalence. The frame condition of the latter requires, in a rooted transitive frame, a finite upper bound of cardinality for antichains of points with different sets of proper successors. The result generalizes Rybakov’s result of the finite axiomatizability of extensions of $\mathbf {S4}$ of finite depth and finite width.

The identity connective is usually interpreted in non-Fregean logic as an operator representing the identity of situations. This interpretation is related to the modal criterion of the identity of sentence correlates, characteristic of the WT system and some stronger systems. However, this connective can also be interpreted in a different way – as an operator representing the identity of propositions. The “propositional” interpretation is in turn associated with the modal-contents criterion of the identity of sentence correlates. This begs the (...) question of whether there is a system of non-Fregean logic, providing an adequate formalization of this criterion. The aim of the paper is to systematize the metalogical and philosophical context of the issue and to point to a system that provides its solution. (shrink)

One of the most expected properties of a logical system is that it can be algebraizable, in the sense that an algebraic counterpart of the deductive machinery could be found. Since the inception of da Costa's paraconsistent calculi, an algebraic equivalent for such systems have been searched. It is known that these systems are non self-extensional (i.e., they do not satisfy the replacement property). More than this, they are not algebraizable in the sense of Blok-Pigozzi. The same negative results hold (...) for several systems of the hierarchy of paraconsistent logics known as Logics of Formal Inconsistency (LFIs). Because of this, these logics are uniquely characterized by semantics of non-deterministic kind. This paper offers a solution for two open problems in the domain of paraconsistency, in particular connected to algebraization of LFIs, by obtaining several LFIs weaker than C1, each of one is algebraizable in the standard Lindenbaum-Tarski's sense by a suitable variety of Boolean algebras extended with operators. This means that such LFIs satisfy the replacement property. The weakest LFI satisfying replacement presented here is called RmbC, which is obtained from the basic LFI called mbC. Some axiomatic extensions of RmbC are also studied, and in addition a neighborhood semantics is defined for such systems. It is shown that RmbC can be defined within the minimal bimodal non-normal logic E+E defined by the fusion of the non-normal modal logic E with itself. Finally, the framework is extended to first-order languages. RQmbC, the quantified extension of RmbC, is shown to be sound and complete w.r.t. BALFI semantics. (shrink)

We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relationsR,S, a componentwise reducibility is defined byR≤S⇔ ∃f∀x, y[x R y↔fS f].Here,fis taken from a suitable class of effective functions. For us the relations will be on natural numbers, andfmust be computable. We show that there is a${\rm{\Pi }}_1^0$-complete equivalence relation, but no${\rm{\Pi }}_k^0$-complete fork≥ 2. We show that${\rm{\Sigma }}_k^0$preorders arising naturally in the above-mentioned areas are${\rm{\Sigma }}_k^0$-complete. This includes polynomial (...) timem-reducibility on exponential time sets, which is${\rm{\Sigma }}_2^0$, almost inclusion on r.e. sets, which is${\rm{\Sigma }}_3^0$, and Turing reducibility on r.e. sets, which is${\rm{\Sigma }}_4^0$. (shrink)

We consider the logics determined by the set of all natural implicative expansions of Kleene’s strong 3-valued matrix and select the class of all logics functionally equivalent to Łukasiewicz’s 3-valued logic Ł3. The concept of a “natural implicative matrix” is based upon the notion of a “natural conditional” defined in Tomova.

This paper examines and classifies the computational complexity of model checking and satisfiability for hybrid logics over frames with equivalence relations. The considered languages contain all possible combinations of the downarrow binder, the existential binder, the satisfaction operator, and the global modality, ranging from the minimal hybrid language to very expressive languages. For model checking, we separate polynomial-time solvable from PSPACE-complete cases, and for satisfiability, we exhibit cases complete for NP, PS pace , NE xp T ime , and (...) even N2E xp T ime . Our analysis includes the versions of all these languages without atomic propositions, and also complete frames. (shrink)

Three-valued (strong-Kleene) modal logic provides the foundation for a new approach to formalizing causal explanation as a relation between partial situations. The approach makes fine-grained distinctions between aspects of events, even between aspects that are equivalent in classical logic. The framework can accommodate a variety of ontologies concerning the relata of causal explanation. I argue, however, for a tripartite ontology of objects corresponding to sentential nominals: facts, tropes (or facta or states of affairs), and situations (or events). I (...) axiomatize the relations and use canonical models to demonstrate completeness. (shrink)

Our purpose is to formulate a complete logic of propositions that takes into account the fact that propositions are both senses provided with truth values and contents of conceptual thoughts. In our formalization, propositions are more complex entities than simple functions from possible worlds into truth values. They have a structure of constituents (a content) in addition to truth conditions. The formalization is adequate for the purposes of the logic of speech acts. It imposes a stronger criterion of (...) propositional identity than strict equivalence. Two propositions P and Q are identical if and only if, for any illocutionary force F, it is not possible to perform with success a speech act of the form F(P) without also performing with success a speech act of the form F(Q). Unlike hyperintensional logic, our logic of propositions is compatible with the classical Boolean laws of propositional identity such as the symmetry and the associativity of conjunction and the reduction of double negation. (shrink)

I explore the logic of ground. I first develop a logic of weak ground. This logic strengthens the logic of weak ground presented by Fine in his ‘Guide to Ground.’ This logic, I argue, generates many plausible principles which Fine’s system leaves out. I then derive from this a logic of strict ground. I argue that there is a strong abductive case for adopting this logic. It’s elegant, parsimonious and explanatorily powerful. Yet, so (...) I suggest, adopting it has important consequences. First, it means we should think of ground as a type of identity. Second, it means we should reject much of Fine’s logic of strict ground. I also show how the logic I develop connects to other systems in the literature. It is definitionally equivalent both to Angell’s logic of analytic containment and to Correia’s system G. (shrink)

The paper is devoted to applications of algebraic logic to databases. In databases a query is represented by a formula of first order logic. The same query can be associated with different formulas. Thus, a query is a class of equivalent formulae: equivalence here being similar to that in the transition to the Lindenbaum-Tarski algebra. An algebra of queries is identified with the corresponding algebra of logic. An algebra of replies to the queries is also associated (...) with algebraic logic. These relations lie at the core of the applications.In this paper it is shown how the theory of Halmos (polyadic) algebras (a notion introduced by Halmos as a tool in the algebraization of the first order predicate calculus) is used to create the algebraic model of a relational data base. The model allows us, in particular, to solve the problem of databases equivalence as well as develop a formal algebraic definition of a database's state description. In this paper we use the term "state description" for the logical description of the model. This description is based on the notion of filters in Halmos algebras. When speaking of a state description, we mean the description of a function which realizes the symbols of relations as real relations in the given system of data. (shrink)

Belnap–Dunn’s relevance logic, $\textsf{BD}$, was designed seeking a suitable logical device for dealing with multiple information sources which sometimes may provide inconsistent and/or incomplete pieces of information. $\textsf{BD}$ is a four-valued logic which is both paraconsistent and paracomplete. On the other hand, De and Omori, while investigating what classical negation amounts to in a paracomplete and paraconsistent four-valued setting, proposed the expansion $\textsf{BD2}$ of the four valued Belnap–Dunn logic by a classical negation. In this paper, we introduce (...) a four-valued expansion of BD called ${\textsf{BD}^\copyright }$, obtained by adding an unary connective ${\copyright }\,\$ which is a consistency operator (in the sense of the Logics of Formal Inconsistency, _LFI_s). In addition, this operator is the unique one with the following features: it extends to $\textsf{BD}$ the consistency operator of LFI1, a well-known three-valued _LFI_, still satisfying axiom _ciw_ (which states that any sentence is either consistent or contradictory), and allowing to define an undeterminedness operator (in the sense of Logic of Formal Undeterminedness, _LFU_s). Moreover, ${\textsf{BD}^\copyright }$ is maximal w.r.t. LFI1, and it is proved to be equivalent to BD2, up to signature. After presenting a natural Hilbert-style characterization of ${\textsf{BD}^\copyright }$ obtained by means of twist-structures semantics, we propose a first-order version of ${\textsf{BD}^\copyright }$ called ${\textsf{QBD}^\copyright }$, with semantics based on an appropriate notion of four-valued Tarskian-like structures called $\textbf{4}$ -structures. We show that in ${\textsf{QBD}^\copyright }$, the existential and universal quantifiers are interdefinable in terms of the paracomplete and paraconsistent negation, and not by means of the classical negation. Finally, a Hilbert-style calculus for ${\textsf{QBD}^\copyright }$ is presented, proving the corresponding soundness and completeness theorems. (shrink)

The aim of this paper is to give new kinds of modal logics suitable for reasoning about regions in discrete spaces. We call them dynamic logics of the region-based theory of discrete spaces. These modal logics are linguistic restrictions of propositional dynamic logic with the global diamond E. Their formulas are equivalent to Boolean combinations of modal formulas like E(A ∧ ⟨α⟩ B) where A and B are Boolean terms and α is a relational term. Examining what we can (...) say about dynamic models when we use formulas to describe them, we successively address the axiomatization/completeness issue and the decidability/complexity issue of our dynamic logics of the region-based theory of discrete spaces. (shrink)

In this paper we investigate several extensions of the first order-language with finitely many binary relations. The most interesting of the studied extensions appears to be the monadic second-order one. We show that the extended languages have the same expressive power as the first-order language over the class of all relational structures of equivalence relations in local agreement by providing appropriate translation of formulae. The decidability of the considered extensions over the above mentioned class of structures is also shown.

_Framing effects_ concern the having of different attitudes towards logically or necessarily equivalent contents. Framing is of crucial importance for cognitive science, behavioral economics, decision theory, and the social sciences at large. We model a typical kind of framing, grounded in (i) the structural distinction between beliefs activated in working memory and beliefs left inactive in long term memory, and (ii) the topic- or subject matter-sensitivity of belief: a feature of propositional attitudes which is attracting growing research attention. We introduce (...) a class of models featuring (i) and (ii) to represent, and reason about, agents whose belief states can be subject to framing effects. We axiomatize a logic which we prove to be sound and complete with respect to the class. (shrink)

We introduce a deductive system Bal which models the logic of balance of opposing forces or of balance between conflicting evidence or influences. ‘‘Truth values’’ are interpreted as deviations from a state of equilibrium, so in this sense, the theorems of Bal are to be interpreted as balanced statements, for which reason there is only one distinguished truth value, namely the one that represents equilibrium. The main results are that the system Bal is algebraizable in the sense of [5] (...) and its equivalent algebraic semantics BAL is definitionally equivalent to the variety of abelian lattice ordered groups, that is, the categories of the algebras in BAL and of ℓ–groups are isomorphic (see [10], Ch.4, 4). We also prove the deduction theorem for Bal and we study different kinds of semantic consequence associated to Bal. Finally, we prove the co-NP-completeness of the tautology problem of Bal. (shrink)

Based on the branching time theory proposed by Prior and Thomason, this thesis is devoted to characterizing the causal aspect of agency by considering a sentence "$\alpha$ sees to it that A" as asserting a causal relation between a choice made by the agent $\alpha$ and a fact described in the sentence A. The phrase "see to it that" is abbreviated as stit. This thesis provides conceptual analyses of stit and develops some modal logics of stit in accordance with these (...) analyses. Theories of stit discussed in this thesis include B. Chellas' theory, Von Kutschera and Horty's theory, and Belnap and Perloff's theory. ;Chapters I-II focus on a conceptual examination of stit theories. We start with branching time theory, and develop a notion of possibility based on reality. After a discussion of Chellas' theory of stit and the controversial issue about stit closure under consequence, we introduce a notion of factual consequences of actions to serve as a basic interpretation of stit sentences. In order to back up this notion, we present a theory of events, a theory of causation and a theory of alternatives for agents in branching time. Using these theories, we interpret the relation between actions and their factual consequences as a causal relation, i.e., factual consequences of actions are sentences describing facts that are caused by those actions. Finally we reach the same semantics for stit as those proposed by Von Kutschera and Horty, and Belnap and Perloff. In Chapters III-VI, we focus on the technical aspect of the stit theory proposed by Belnap and Perloff. We present an axiomatization of the basic logic ${\bf L}\sb0$ of stit with a single agent and prove its completeness, and present an axiomatization of the logic ${\bf L}\sb1$ of stit with a single agent and refref equivalence and prove its completeness and decidability. Finally we present a study of stit modalities which serves as a study of modes of actions/inactions as well as a preparation for further studies of logics between ${\bf L}\sb0$ and ${\bf L}\sb1.$. (shrink)

In this paper we define and study a generalized notion of a logical system that covers on an equal formal basis sentential, equational and sequential systems. We develop a general theory of equivalence between generalized logics that provides, first, a conception of algebraizable logic , second, a formal concept of equivalence between sequential systems and, third, a notion of equivalence between sentential and sequential systems. We also use our theory of equivalence for developing a general (...) algebraic approach to conjunctive non-pseudo-axiomatic self-extensional sentential logics. Finally, we consider within the framework of the mentioned approach various sequential formulations for some well-known sentential logics. (shrink)

We investigate synonymy in the strong sense of content identity. This notion is central in the philosophy of language and in applications of logic. We motivate, uniformly axiomatize, and characterize several “benchmark” notions of synonymy in the messy class of all possible notions of synonymy. This class is divided by two intuitive principles that are governed by a no-go result. We use the notion of a scenario to get a logic of synonymy which is the canonical representative of (...) one division. In the other division, the so-called conceptivist logics, we find, e.g., the well-known system of analytic containment. We axiomatize four logics of synonymy extending AC, relate them semantically and proof-theoretically to SF, and characterize them in terms of weak/strong subject matter preservation and weak/strong logical equivalence. This yields ways out of the no-go result and novel arguments—independent of a particular semantic framework—for each notion of synonymy discussed. This points to pluralism about meaning and a certain non-compositionality of truth in logic programs and neural networks. And it unveils an impossibility for synonymy: if it is to preserve subject matter, then either conjunction and disjunction lose an essential property or a very weak absorption law is violated. (shrink)

This paper considers the existence of finite equational axiomatisations of behavioural equivalences over a calculus of finite state processes. To express even simple properties such as μxE = μxE[E/x] some notation for substitutions is required. Accordingly, the calculus is embedded in a simply typed lambda calculus, allowing such schemas to be expressed as equations between terms containing first order variables. A notion of first order trace congruence over such terms is introduced and used to show that no finite set of (...) such equations is sound and complete for any reasonable equivalence finer than trace equivalence. The intermediate results are then applied to give two nonaxiomatisability results over calculi of regular expressions. (shrink)

For Tarski logics, there are simple criteria that enable one to conclude that two premise sets are equivalent. We shall show that the very same criteria hold for adaptive logics, which is a major advantage in comparison to other approaches to defeasible reasoning forms. A related property of Tarski logics is that the extensions of equivalent premise sets with the same set of formulas are equivalent premise sets. This does not hold for adaptive logics. However a very similar criterion does. (...) We also shall show that every monotonic logic weaker than an adaptive logic is weaker than the lower limit logic of the adaptive logic or identical to it. This highlights the role of the lower limit for settling the adaptive equivalence of extensions of equivalent premise sets. (shrink)

We investigate effective categoricity of computable equivalence structures . We show that is computably categorical if and only if has only finitely many finite equivalence classes, or has only finitely many infinite classes, bounded character, and at most one finite k such that there are infinitely many classes of size k. We also prove that all computably categorical structures are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. Since all computable equivalence structures (...) are relatively categorical, we further investigate when they are categorical. We also obtain results on the index sets of computable equivalence structures. (shrink)

Labeled transition systems are key structures for modeling computation. In this paper, we show how they lend themselves to ordinary logical analysis (without any special new formalisms), by introducing their standard first-order theory. This perspective enables us to raise several basic model-theoretic questions of definability, axiomatization and preservation for various notions of process equivalence found in the computational literature, and answer them using well-known logical techniques (including the Compactness theorem, Saturation and Ehrenfeucht games). Moreover, we consider what happens to (...) this general theory when one restricts attention to special classes of transition systems (in particular, finite ones), as well as extended logical languages (in particular, infinitary first-order logic). We hope that this puts standard logical formalisms on the map as a serious option for a theory of computational processes. As a side benefit, our approach increases comparability with several other existing formalisms over labeled transition systems (such as Process Algebra or Modal Logic). We provide some pointers to this effect, too. (shrink)

We introduce the computable FS-jump, an analog of the classical Friedman–Stanley jump in the context of equivalence relations on the natural numbers. We prove that the computable FS-jump is proper with respect to computable reducibility. We then study the effect of the computable FS-jump on computably enumerable equivalence relations (ceers).

Anil Gupta's slightly revised 1977 Pittsburgh doctoral dissertation is not a linguistic investigation of common nouns. There is no thorough attempt to organize and explain data about common nouns in natural languages. Gupta's goal is to develop and to defend formal modal languages and logics useful for the representation and defense of metaphysical theses on topics such as the structure of individuals, sorts or kinds, substances, and essences. He does, however, develop the special features of his formal syntax and semantics (...) on the basis of two theses about common nouns in our natural languages. Geach's work suggests the first thesis that properly expressed identity statements are of the form: b is the same K as c, where K is a common noun. Because the individual variables bound by quantifiers must be capable of being terms of an identity relation, this first thesis leads Gupta to require quantifiers to link individual variables with common noun expressions. Thus in his formal languages we can only express: "every K is _____" or "some K is _____" where K is syntactically part of the quantifier. We can call this "sortal quantification." Hence, "Every K is P" and "Some K is P" are not even expressible as "If anything is K then it is P" or "Something is K and P," let alone equivalent to such ill-formed expressions in his languages. Gupta's book is a useful introduction to the syntax and semantics for languages with this non-standard sortal quantification for those already familiar with the syntax and formal semantics of first order extensional and modal languages with standard quantifiers. Those unfamiliar with standard formal languages and model structure semantics will find Gupta's provocative metaphysical theories and conjectures inaccessible. (shrink)

The logics of formal inconsistency (LFIs, for short) are paraconsistent logics (that is, logics containing contradictory but non-trivial theories) having a consistency connective which allows to recover the ex falso quodlibet principle in a controlled way. The aim of this paper is considering a novel semantical approach to first-order LFIs based on Tarskian structures defined over swap structures, a special class of multialgebras. The proposed semantical framework generalizes previous aproaches to quantified LFIs presented in the literature. The case of QmbC, (...) the simpler quantified LFI expanding classical logic, will be analyzed in detail. An axiomatic extension of QmbC called QLFI1o is also studied, which is equivalent to the quantified version of da Costa and D'Ottaviano 3-valued logic J3. The semantical structures for this logic turn out to be Tarkian structures based on twist structures. The expansion of QmbC and QLFI1o with a standard equality predicate is also considered. (shrink)

Bilattices, introduced by Ginsberg as a uniform framework for inference in artificial intelligence, are algebraic structures that proved useful in many fields. In recent years, Arieli and Avron developed a logical system based on a class of bilattice-based matrices, called logical bilattices, and provided a Gentzen-style calculus for it. This logic is essentially an expansion of the well-known Belnap–Dunn four-valued logic to the standard language of bilattices. Our aim is to study Arieli and Avron’s logic from the (...) perspective of abstract algebraic logic . We introduce a Hilbert-style axiomatization in order to investigate the properties of the algebraic models of this logic, proving that every formula can be reduced to an equivalent normal form and that our axiomatization is complete w.r.t. Arieli and Avron’s semantics. In this way, we are able to classify this logic according to the criteria of AAL. We show, for instance, that it is non-protoalgebraic and non-self-extensional. We also characterize its Tarski congruence and the class of algebraic reducts of its reduced generalized models, which in the general theory of AAL is usually taken to be the algebraic counterpart of a sentential logic. This class turns out to be the variety generated by the smallest non-trivial bilattice, which is strictly contained in the class of algebraic reducts of logical bilattices. On the other hand, we prove that the class of algebraic reducts of reduced models of our logic is strictly included in the class of algebraic reducts of its reduced generalized models. Another interesting result obtained is that, as happens with some implicationless fragments of well-known logics, we can associate with our logic a Gentzen calculus which is algebraizable in the sense of Rebagliato and Verdú . We also prove some purely algebraic results concerning bilattices, for instance that the variety of distributive bilattices is generated by the smallest non-trivial bilattice. This result is based on an improvement of a theorem by Avron stating that every bounded interlaced bilattice is isomorphic to a certain product of two bounded lattices. We generalize it to the case of unbounded interlaced bilattices. (shrink)

We study a new formal logic LD introduced by Prof. Grzegorczyk. The logic is based on so-called descriptive equivalence, corresponding to the idea of shared meaning rather than shared truth value. We construct a semantics for LD based on a new type of algebras and prove its soundness and completeness. We further show several examples of classical laws that hold for LD as well as laws that fail. Finally, we list a number of open problems. -/- .

Preferential model is one of the important semantical structures in nonmonotonic logic. This paper aims to establish an isomorphism theorem for preferential models, which gives us a purely algebraic characterization of the equivalence of preferential models. To this end, we present the notions of local similarity and local simulation. Based on these notions, two operators Δ(·) and μ(·) over preferential models are introduced and explored respectively. Together with other two existent operators ρ(·) and ΠD(·), we introduce an operator (...) ∂D(·). Then the isomorphism theorem is obtained in terms of ∂D(·), which asserts that for any two preferential models M₁ and M₂, they generate the same preferential inference if and only if ∂D(M₁) and ∂D(M₂) are isomorphic. Based on ∂D(·), we also get an alternative model-theoretical characterization of the well-known postulate "Weaken Disjunctive Rationality". Moreover, in the finite language framework, we show that Δ(μ(·)) is competent for the task of eliminating redundancy, and provide a representation result for k-relations. (shrink)

Two logics L1 and L2 are negatively equivalent if for any set of formulas X and any negated formula ¬, ¬ can be deduced from the set of hypotheses X in L1 if and only if it can be done in L2. This article is devoted to the investigation of negative equivalence relation in the class of extensions of minimal logic.

Labeled transition systems are key structures for modeling computation. In this paper, we show how they lend themselves to ordinary logical analysis (without any special new formalisms), by introducing their standard first-order theory. This perspective enables us to raise several basic model-theoretic questions of definability, axiomatization and preservation for various notions of process equivalence found in the computational literature, and answer them using well-known logical techniques (including the Compactness theorem, Saturation and Ehrenfeucht games). Moreover, we consider what happens to (...) this general theory when one restricts attention to special classes of transition systems (in particular, finite ones), as well as extended logical languages (in particular, infinitary first-order logic). We hope that this puts standard logical formalisms on the map as a serious option for a theory of computational processes. As a side benefit, our approach increases comparability with several other existing formalisms over labeled transition systems (such as Process Algebra or Modal Logic). We provide some pointers to this effect, too. (shrink)

We present a class of first-order modal logics, called transformational logics, which are designed for working with sentences that hold up to a certain type of transformation. An inference system is given, and com- pleteness for the basic transformational logic HOS is proved. In order to capture ‘up to isomorphism’, we express a very weak version of higher category theory in terms of first-order models, which makes tranforma- tional logics applicable to category theory. A category-theoretical concept of isomorphism is (...) used to arrive at a modal operator nisoφ expressing ‘up to isomorphism, φ’, which is such that category equivalence comes out as literally isomorphism up to isomorphism. In the final part of the paper, we explore the possibility of using trans- formational logics to define weak higher categories. We end with two informal comparisons: one between HOS and counterpart semantics, and one between isomorphism logic, as a transformational logic, and Homo- topy Type Theory. (shrink)

On their alethic reading, formulas,, and codify three of the most basic principles of possibility and its dual. This paper discusses these formulas on a broadly epistemic reading, and in particular as candidate principles about conceivability and its dual. As will be shown, the question whether and its classical dual equivalent, as well as and hold on this reading is not only a logical one but involves a distinctively metaphysical controversy between realist and antirealist views on the relation between truth (...) on the one hand and various cognitive conditions such as knowability, conceivability, and thinkability on the other. It will be argued that the stance we take with regard to the metaphysical dispute has consequences for our assessment of the plausibility not only of and its classical equivalent, but also of and—when that stance is combined with a structural account of propositions—potentially of as well; with all four taken in the above epistemic sense. A second upshot will be that the same sensitivity to metaphysical background commitment also applies to our view as to whether or not inconceivability of the opposite coincides with, or even entails, apriority. (shrink)

It has been claimed that counterpart theory cannot support a theory of actuality without rendering obviously invalid formulas valid or obviously valid formulas invalid. We argue that these claims are not based on logical flaws of counterpart theory itself, but point to the lack of appropriate devices in first-order logic for “remembering” the values of variables. We formulate a mildly dynamic version of first-order logic with appropriate memory devices and show how to base a version of counterpart theory (...) with actuality on this. This theory is, in special cases, equivalent to modal first-order logic with actuality, and apparently does not suffer from the logical flaws that have been mentioned in the literature. (shrink)

Assume [Formula: see text]. Let [Formula: see text] be a [Formula: see text] equivalence relation coded in [Formula: see text]. [Formula: see text] has an ordinal definable equivalence class without any ordinal definable elements if and only if [Formula: see text] is unpinned. [Formula: see text] proves [Formula: see text]-class section uniformization when [Formula: see text] is a [Formula: see text] equivalence relation on [Formula: see text] which is pinned in every transitive model of [Formula: see text] (...) containing the real which codes [Formula: see text]: Suppose [Formula: see text] is a relation on [Formula: see text] such that each section [Formula: see text] is an [Formula: see text]-class, then there is a function [Formula: see text] such that for all [Formula: see text], [Formula: see text]. [Formula: see text] proves that [Formula: see text] is Jónsson whenever [Formula: see text] is an ordinal: For every function [Formula: see text], there is an [Formula: see text] with [Formula: see text] in bijection with [Formula: see text] and [Formula: see text]. (shrink)

We study the degree structure of the ω-c.e., n-c.e., and Π10 equivalence relations under the computable many-one reducibility. In particular, we investigate for each of these classes of degrees the most basic questions about the structure of the partial order. We prove the existence of the greatest element for the ω-c.e. and n-computably enumerable equivalence relations. We provide computable enumerations of the degrees of ω-c.e., n-c.e., and Π10 equivalence relations. We prove that for all the degree classes (...) considered, upward density holds and downward density fails. (shrink)

Formulas of the propositional modal language with the unary modal operators □, Σ1, 1, Σ2, 2,… are considered as schemata of sentences of arithmetic , where □A is interpreted as “A is PA-provable”, ΣnA as “A is PA-equivalent to a Σn-sentence” and nA as “A is PA-equivalent to a Boolean combination of Σn-sentences”. We give an axiomatization and show decidability of the sets of the modal formulas which are schemata of: PA-provable, true arithmetical sentences.

In this paper, we give an alternative semantics to the non-normal logic of knowing how proposed by Fervari et al., based on a class of Kripke neighborhood models with both the epistemic relations and neighborhood structures. This alternative semantics is inspired by the same quantifier alternation pattern of ∃∀\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\exists \forall$$\end{document} in the semantics of the know-how modality and the neighborhood semantics for the standard modality. We show that this new (...) semantics is equivalent to the original Kripke semantics in terms of the validities. A key result is a representation theorem showing that the more abstract Kripke neighborhood models can be represented by the concrete Kripke models with action transitions modulo the valid formulas. We prove the completeness of the logic for the neighborhood semantics. The neighborhood semantics can be adapted to other variants of logics of knowing how. It provides us a powerful technical tool to study these logics while preserving the basic semantic intuition. (shrink)

An explication of preference and equivalence with regard to the evaluation of states of affairs. The logical system developed consists of the ordinary propositional calculus together with connectives standing for the notions above. In the course of this study a number of useful distinctions and definitions can be found. The author indicates that his logic of preference may be of use in connection with utility and decision theory, but does not develop this point.--R. H. T.