The problem is addressed of establishing the satisfiability of prenex formulas involving a single universal quantifier, in diversified axiomatic set theories. A rather general decision method for solving this problem is illustrated through the treatment of membership theories of increasing strength, ending with a subtheory of Zermelo-Fraenkel which is already complete with respect to the ∀*∀ class of sentences. NP-hardness and NP-completeness results concerning the problems under study are achieved and a technique for restricting the universal quantifier is presented.

Fluted logic is the restriction of pure predicate logic to formulas in which variables play no essential role. Although fluted logic is significantly weaker than pure predicate logic, it is of interest because it seems closely to parallel natural logic, the logic that is conducted in natural language. It has been known since 1969 that if conjunction in fluted formulas is restricted to subformulas of equal arity, satisfiability is decidable. However, the decidability of sublogics lying between this restricted (...) (homogeneous) fluted logic and full predicate logic remained unknown. In 1994 it was shown that the satisfiability of fluted formulas without restriction is decidable, thus reducing the unknown region significantly. This paper further reduces the unknown region. It shows that fluted logic with the logical identity is decidable. Since the reflection functor can be defined in fluted logic with identity, it follows that fluted logic with the reflection functor also lies within the region of decidability. Relevance to natural logic is increased since the identity permits definition of singular predicates, which can represent anaphoric pronouns. (shrink)

We present a logic which we call Hybrid Duration Calculus. HDC is obtained by adding the following hybrid logical machinery to the Restricted Duration Calculus : nominals, satisfaction operators, down-arrow binder, and the global modality. RDC is known to be decidable, and in this paper we show that decidability is retained when adding the hybrid logical machinery. Decidability of HDC is shown by reducing the satisfiability problem to satisfiability of Monadic Second-Order Theory of Order. We illustrate (...) the increased expressive power obtained in hybridizing RDC by showing that HDC, in contrast to RDC, can express all of the 13 possible relations between intervals. (shrink)

Inquisitive logic is an extension of classical logic which can express questions. To enable this expressiveness, a possible world semantics is used. So, it is natural to combine inquisitive and modal logic, thus obtaining the inquisitive modal logic $$\textrm{InqML}$$. This paper contributes to the model theory of $$\textrm{InqML}$$. We show that the filtration technique can be adapted to the inquisitive logic semantics. Using filtrations, we prove that $$\textrm{InqML}$$ has the finite model property, i.e., every satisfiable formula is satisfiable in a (...) finite model. As a consequence, we obtain that $$\textrm{InqML}$$ is decidable. Finally, we study filtrations over particular model classes and we prove that some extensions of $$\textrm{InqML}$$ are also decidable. (shrink)

In this paper we consider an independence-friendly modal logic, IFML. It follows from results in the literature that qua expressive power, IFML is a fragment of second-order existential logic, , that cannot be translated into first-order logic. It is also known that IFML lacks the tree structure property. We show that IFML has the , a weaker version of the tree structure property, and that its satisfiability problem is solvable in 2NEXP. This implies that this paper reveals a new (...) decidable fragment of . We also show that IFML becomes undecidable if we add the identity symbol to its vocabulary by means of a reduction from the tiling problem. (shrink)

Ethical beliefs may vary across cultures but there are things that must be valued as preconditions to any cultural practice. Physical and mental abilities vital to believing, valuing and practising a culture are such preconditions and it is always important to protect them. If one is to practise a distinct culture, she must at least have these basic abilities. Access to basic healthcare is one way to ensure that vital abilities are protected. John Rawls argued that access to all-purpose primary (...) goods must be ensured. Amartya Sen and Martha Nussbaum claim that universal capabilities are what resources are meant to enable. Len Doyal and Ian Gough identify physical health and autonomy as basic needs of every person in every culture. When we disagree on what to prioritize, when resources to satisfy competing demands are scarce, our common needs can provide a point of normative convergence. Need-based rationing, however, has been criticized for being too indeterminate to give guidance for deciding which healthcare services to prioritize and for tending to create a bottomless-pit problem. But there is a difference between needing something (first-order need) and needing to have the ability to need (second-order need). Even if we disagree about which first-order need to prioritize, we must accept the importance of satisfying our second-order need to have the ability to value things. We all have a second-order need for basic healthcare as a means to protect our vital abilities even if we differ in what our cultures consider to be particular first-order needs. (shrink)

ABSTRACT Ethical beliefs may vary across cultures but there are things that must be valued as preconditions to any cultural practice. Physical and mental abilities vital to believing, valuing and practising a culture are such preconditions and it is always important to protect them. If one is to practise a distinct culture, she must at least have these basic abilities. Access to basic healthcare is one way to ensure that vital abilities are protected. John Rawls argued that access to all‐purpose (...) primary goods must be ensured. Amartya Sen and Martha Nussbaum claim that universal capabilities are what resources are meant to enable. Len Doyal and Ian Gough identify physical health and autonomy as basic needs of every person in every culture. When we disagree on what to prioritize, when resources to satisfy competing demands are scarce, our common needs can provide a point of normative convergence. Need‐based rationing, however, has been criticized for being too indeterminate to give guidance for deciding which healthcare services to prioritize and for tending to create a bottomless‐pit problem. But there is a difference between needing something (first‐order need) and needing to have the ability to need (second‐order need). Even if we disagree about which first‐order need to prioritize, we must accept the importance of satisfying our second‐order need to have the ability to value things. We all have a second‐order need for basic healthcare as a means to protect our vital abilities even if we differ in what our cultures consider to be particular first‐order needs. (shrink)

In first order logic without equality, but with arbitrary relations and functions the ∃*∀∃* class is the unique maximal solvable prefix class. We show that the satisfiability problem for this class is decidable in deterministic exponential time The result is established by a structural analysis of a particular infinite subset of the Herbrand universe and by a polynomial space bounded alternating procedure.

This paper investigates the “general” semantics for first-order logic introduced to Antonelli, 637–58, 2013): a sound and complete axiom system is given, and the satisfiability problem for the general semantics is reduced to the satisfiability of formulas in the Guarded Fragment of Andréka et al. :217–274, 1998), thereby showing the former decidable. A truth-tree method is presented in the Appendix.

In this paper, we introduce a new fragment of the first-order temporal language, called the monodic fragment, in which all formulas beginning with a temporal operator have at most one free variable. We show that the satisfiability problem for monodic formulas in various linear time structures can be reduced to the satisfiability problem for a certain fragment of classical first-order logic. This reduction is then used to single out a number of decidable fragments of first-order temporal logics and (...) of two-sorted first-order logics in which one sort is intended for temporal reasoning. Besides standard first-order time structures, we consider also those that have only finite first-order domains, and extend the results mentioned above to temporal logics of finite domains. We prove decidability in three different ways: using decidability of monadic second-order logic over the intended flows of time, by an explicit analysis of structures with natural numbers time, and by a composition method that builds a model from pieces in finitely many steps. (shrink)

The -logic of Terwijn is a variant of first-order logic with the same syntax in which the models are equipped with probability measures and the quantifier is interpreted as ‘there exists a set A of a measure such that for each,...’. Previously, Kuyper and Terwijn proved that the general satisfiability and validity problems for this logic are, i) for rational, respectively -complete and -hard, and ii) for, respectively decidable and -complete. The adjective ‘general’ here means ‘uniformly over all languages’. (...) We extend these results in the scenario of finite models. In particular, we show that the problems of satisfiability and validity with respect to finite models in E-logic are, i) for rational, respectively -complete and -complete, and ii) for, respectively decidable and -complete. Although partial results toward the countable case are also achieved, the computability of E-logic over countable models still remains largely unsolved. In addition, most o... (shrink)

We prove decidability of satisfiability of sentences of the monodic packed fragment of first-order temporal logic with equality and connectives Until and Since, in models with various flows of time and domains of arbitrary cardinality. We also prove decidability over models with finite domains, over flows of time including the real order.

For arbitrary finite group $G$ and countable Dedekind domain $R$ such that the residue field $R/P$ is finite for every maximal $R$ -ideal $P$ , we show that the localizations at every maximal ideal of two $RG$ -lattices are isomorphic if and only if the two lattices satisfy the same first order sentences. Then we investigate generalizations of the above results to arbitrary $R$ -torsion-free $RG$ -modules and we apply the previous results to show the decidability of the theory (...) of ${\vec Z}C(2)^2$ -lattices. Eventually, we show that ${\vec Z} [i] C(2)^2$ -lattices have undecidable theory. (shrink)

We develop a timeout extension of propositional linear temporal logic to specify timing properties of timeout-based models of real-time systems. A timeout is used to model the execution of an action marking the end of a delay. With a view to expressing such timeout constraints, ToLTL uses a dynamic variable to abstract the timeout behaviour in addition to a variable which captures the global clock and some static timing variables which record time instances when discrete events occur. We propose a (...) corresponding timeout tableau for satisfiability checking of the ToLTL formulas. Further we prove that the validity checking for such an extended logic remains PSPACE-complete. Under discrete time semantics, with bounded timeout increments, the model-checking problem which verifies if a ToLTL-formula holds in a timeout Kripke structure is also shown to be PSPACE complete. We further prove that ToLTL, when interpreted over discrete time, can be embedded in the monadic second-order logic with.. (shrink)

With every new recursive relation R on a recursive model , we consider the images of R under all isomorphisms from to other recursive models. We call the set of Turing degrees of these images the degree spectrum of R on , and say that R is intrinsically r.e. if all the images are r.e. C. Ash and A. Nerode introduce an extra decidability condition on , expressed in terms of R. Assuming this decidability condition, they prove that (...) R is intrinsically r.e. if and only if a natural recursive-syntactic condition is satisfied. We show that, while a recursive non-intrinsically r.e. relation may have a two element degree spectrum, a non-intrinsically r.e. relation which satisfies the Ash–Nerode decidability condition has an infinite degree spectrum. We also study several related decidability conditions and their effects on the degree spectra, including some conditions which are sufficient to obtain every r.e. degree in a spectrum. (shrink)

We study a propositional probabilistic temporal epistemic logic $\textbf {PTEL}$ with both future and past temporal operators, with non-rigid set of agents and the operators for agents’ knowledge and for common knowledge and with probabilities defined on the sets of runs and on the sets of possible worlds. A semantics is given by a class ${\scriptsize{\rm Mod}}$ of Kripke-like models with possible worlds. We prove decidability of $\textbf {PTEL}$ by showing that checking satisfiability of a formula in ${\scriptsize{\rm (...) Mod}}$ is equivalent to checking its satisfiability in a finite set of finitely representable structures. The same procedure can be applied to the class of all synchronous ${\scriptsize{\rm Mod}}$-models. We give an upper complexity bound for the satisfiability problem for ${\scriptsize{\rm Mod}}$. (shrink)

Satisfaction systems and reductions between them are presented as an appropriate context for analyzing the satisfiability and the validity problems. The notion of reduction is generalized in order to cope with the meet-combination of logics. Reductions between satisfaction systems induce reductions between the respective satisfiability problems and (under mild conditions) also between their validity problems. Sufficient conditions are provided for relating satisfiability problems to validity problems. Reflection results for decidability in the presence of reductions are established. (...) The validity problem in the meet-combination is proved to be decidable whenever the validity problem for the components are decidable. Several examples are discussed, namely, involving modal and intuitionistic logics, as well as the meet-combination of modal logic and intuitionistic logic. (shrink)

We provide a simple translation of the satisfiability problem for regular grammar logics with converse into GF2, which is the intersection of the guarded fragment and the 2-variable fragment of first-order logic. The translation is theoretically interesting because it translates modal logics with certain frame conditions into first-order logic, without explicitly expressing the frame conditions. It is practically relevant because it makes it possible to use a decision procedure for the guarded fragment in order to decide regular grammar logics (...) with converse. The class of regular grammar logics includes numerous logics from various application domains. A consequence of the translation is that the general satisfiability problem for every regular grammar logics with converse is in EXPTIME. This extends a previous result of the first author for grammar logics without converse. Other logics that can be translated into GF2 include nominal tense logics and intuitionistic logic. In our view, the results in this paper show that the natural first-order fragment corresponding to regular grammar logics is simply GF2 without extra machinery such as fixed-point operators. (shrink)

We provide a simple translation of the satisfiability problem for regular grammar logics with converse into GF2, which is the intersection of the guarded fragment and the 2-variable fragment of first-order logic. The translation is theoretically interesting because it translates modal logics with certain frame conditions into first-order logic, without explicitly expressing the frame conditions. It is practically relevant because it makes it possible to use a decision procedure for the guarded fragment in order to decide regular grammar logics (...) with converse. The class of regular grammar logics includes numerous logics from various application domains. A consequence of the translation is that the general satisfiability problem for every regular grammar logics with converse is in EXPTIME. This extends a previous result of the first author for grammar logics without converse. Other logics that can be translated into GF2 include nominal tense logics and intuitionistic logic. In our view, the results in this paper show that the natural first-order fragment corresponding to regular grammar logics is simply GF2 without extra machinery such as fixed-point operators. (shrink)

The most common way of proving decidability in propositional modal logic is to shew that the system in question has the finite model property. This is not however the only way. Gabbay in [4] proves the decidability of many modal systems using Rabin's result in [8] on the decidability of the second-order theory of successor functions. In particular [4, pp. 258-265] he is able to prove the decidability of a system which lacks the finite model property. (...) Gabbay's system is however complete, in the sense of being characterized by a class of frames, and the question arises whether there is a decidable modal logic which is not complete. Since no incomplete modal logic has the finite model property [9, p. 33], any proof of decidability must employ some such method as Gabbay's. In this paper I use the Gabbay/Rabin technique to prove the decidability of a finitely axiomatized normal modal propositional logic which is not characterized by any class of frames. I am grateful to the referee for suggesting improvements in substance and presentation.The terminology I am using is standard in modal logic. By aframeis understood a pair 〈W, R〉 in whichWis a class (of “possible worlds”) andR⊆W2. To avoid confusion in what follows, a frame will henceforth be referred to as aKripkeframe. By contrast, ageneral frameis a pair 〈,Π〉 in whichis a Kripke frame andΠis a collection of subsets ofWclosed under the Boolean operations and satisfying the condition that ifAis inΠthen so isR−1“A. A model on a frame (of either kind) is obtained by adding a functionVwhich assigns sets of worlds to propositional variables. In the case of a general frame we require thatV(p) ∈Π. (shrink)

A new deontic logic, Action Type Deontic Logic, is presented. To motivate this logic, a number of benchmark cases are shown, representing inferences a deontic logic should validate. Some of the benchmark cases are singled out for further comments and some formal approaches to deontic reasoning are evaluated with respect to the benchmark cases. After that follows an informal introduction to the ideas behind the formal semantics, focussing on the distinction between action types and action tokens. Then the syntax and (...) semantics of Action Type Deontic Logic is presented and it is shown to meet the benchmarks. Finally, possibilities for further research are indicated. In the appendix, decidability of the satisfiability of formulas is proved via a technique known from monadic First Order Logic. (shrink)

The main theorem says that a consequence operator is an effective part of the consequence operator for the classical prepositional calculus iff it is a consequence operator for a logic satisfying the compactness theorem, and in which every finitely axiomatizable theory is decidable.

In this paper we investigate the computational complexity of deciding if the variety generated by a given finite idempotent algebra satisfies a special type of Maltsev condition that can be specified using a certain kind of finite labelled path. This class of Maltsev conditions includes several well known conditions, such as congruence permutability and having a sequence of n Jónsson terms, for some given n. We show that for such “path defined” Maltsev conditions, the decision problem is polynomial-time solvable.

The paper deals with a temporal multi-agent logic TMAZ, which imitates taking of decisions based on agents' access to knowledge by their interaction. The interaction is modelled by possible communication channels between agents in special temporal Kripke/Hintikka-like models. The logic TMAZ distinguishes local and global decisions-making. TMAZ is based on temporal Kripke/Hintikka models with agents' accessibility relations defined on states of all possible time clusters C(i) (where indexes i range over all integer numbers Z). The main result provides a decision (...) algorithm for TMAZ (so, we prove that TMAZ is decidable). This algorithm also solves the satisfiability problem. In the final part of the paper, we consider the admissibility problem for inference rules in TMAZ, and show that this problem is decidable for TMAZ as well. (shrink)

This is a textbook in symbolic logic comprising sentential and quantificational theory only. The logic of the propositional calculus is developed in a natural-deduction form reminiscent of Fitch's technique; therefore, most of the theorems take the form of metamathematical assertions and possess corresponding meta-proofs. The classical propositional calculus SCc is then formulated in the Hilbert-style axiomatic way which naturally leads to consistency, completeness, and decidability theorems for the system. The theory of quantifiers is also first set up in natural (...) deduction form, and then reformulated classically. Leblanc spends considerable time in a careful treatment of satisfiability and validity in first-order logic, this leading naturally to the Löweheim-Skolem [[sic]] theorem and related completeness results. There is an appendix containing some relevant results from set theory. In general this is a most thorough and neat job which succeeds admirably in giving in semantical form a rigorous introduction to logic.—P. J. M. (shrink)

Normative arrow update logic (NAUL) is a logic that combines normative temporal logic (NTL) and arrow update logic (AUL). In NAUL, norms are interpreted as arrow updates on labeled transition systems with a CTL-like logic. We show that the satisfiability problem of NAUL is decidable with a tableau method and it is in EXPSPACE.

The modal -calculus extends basic modal logic with second-order quantification in terms of arbitrarily nested fixpoint operators. Its satisfiability problem is EXPTIME-complete. Decision procedures for the modal -calculus are not easy to obtain though since the arbitrary nesting of fixpoint constructs requires some combinatorial arguments for showing the well-foundedness of least fixpoint unfoldings. The tableau-based decision procedures so far also make assumptions on the unfoldings of fixpoint formulas, e.g., explicitly require formulas to be in guarded normal form. In this (...) paper we present a tableau calculus for deciding satisfiability of arbitrary, i.e., not necessarily guarded -calculus formulas. It is based on a new unfolding rule for greatest fixpoint formulas which allows unguarded formulas to be handled without an explicit transformation into guarded form, thus avoiding a exponential blow-up in formula size. We prove soundness and completeness of the calculus, and compare it empirically to using guarded transformation instead. The new unfolding rule can also be used to handle nested star operators in PDL formulas correctly. (shrink)

In the predicate calculus, variables provide a flexible indexing service which selects the actual arguments to a predicate letter from among possible arguments that precede the predicate letter (in the parse of the formula). In the process of selection, the possible arguments can be permuted, repeated (used more than once), and skipped. If this service is withheld, so that arguments must be the immediately preceding ones, taken in the order in which they occur, the formula is said to be fluted. (...) Quine showed that if a fluted formula contains only homogeneous conjunction (conjoins only subformulas of equal arity), then the satisfiability of the formula is decidable. It remained an open question whether the satisfiability of a fluted formula without this restriction is decidable. This paper answers that question. (shrink)

We propose two alternatives to Xu’s axiomatization of Chellas’s STIT. The first one simplifies its presentation, and also provides an alternative axiomatization of the deliberative STIT. The second one starts from the idea that the historic necessity operator can be defined as an abbreviation of operators of agency, and can thus be eliminated from the logic of Chellas’s STIT. The second axiomatization also allows us to establish that the problem of deciding the satisfiability of a STIT formula without temporal (...) operators is NP-complete in the single-agent case, and is NEXPTIME-complete in the multiagent case, both for the deliberative and Chellas’s STIT. (shrink)

The author addresses the question of the necessity of logic courses in undergraduate education, particularly their use as a requirement in the humanities. This paper outlines why logic counts as a humanities subject and why certain virtues of logic are beneficial to a humanities education. The authors explores these two aspects of the question and invites the reader to decide whether the combination of these two aspects of a logic course jointly satisfy the educational needs of their particular institution’s curriculum.

We study first-order logic with two variables FO² and establish a small substructure property. Similar to the small model property for FO² we obtain an exponential size bound on embedded substructures, relative to a fixed surrounding structure that may be infinite. We apply this technique to analyse the satisfiability problem for FO² under constraints that require several binary relations to be interpreted as equivalence relations. With a single equivalence relation, FO² has the finite model property and is complete for (...) non-deterministic exponential time, just as for plain FO² With two equivalence relations, FO² does not have the finite model property, but is shown to be decidable via a construction of regular models that admit finite descriptions even though they may necessarily be infinite. For three or more equivalence relations, FO² is undecidable. (shrink)

We characterise explicitly the decidable predicates on integers of Infinite Time Turing machines, in terms of admissibility theory and the constructible hierarchy. We do this by pinning down ζ, the least ordinal not the length of any eventual output of an Infinite Time Turing machine (halting or otherwise); using this the Infinite Time Turing Degrees are considered, and it is shown how the jump operator coincides with the production of mastercodes for the constructible hierarchy; further that the natural ordinals associated (...) with the jump operator satisfy a Spector criterion, and correspond to the L ζ -stables. It also implies that the machines devised are "Σ 2 Complete" amongst all such other possible machines. It is shown that least upper bounds of an "eventual jump" hierarchy exist on an initial segment. (shrink)

The still unsettled decision problem for the restricted purely universal formulae 0-formulae) of the first order set-theoretic language based over =, ∈ is discussed in relation with the adoption or rejection of the axiom of foundation. Assuming the axiom of foundation, the related finite set-satisfiability problem for the very significant subclass of the 0-formulae consisting of the formulae involving only nested variables of level 1 is proved to be semidecidable on the ground of a reflection property over the hereditarily (...) finite sets, and various extensions of this result are obtained. When variables are restricted to range only over sets, in universes with infinitely many urelements the set-satisfiability problem is shown to be solvable provided the axiom of foundation is assumed; if it is not, then the decidability of a related derivability problem still holds. That, in turn, suggests the alternative adoption of an antifoundation axiom under which the set-satisfiability problem is also solvable . Turning to set theory without urelements, assuming a form of Boffa's antifoundation axiom, the complement of the set-satisfiability problem for the full class of Δ0-formulae is shown to be semidecidable; a result that is known not to hold, for the set-satisfiability problem itself, even for a very restricted subclass of the Δ0-formulae. (shrink)

The paper presents a family of propositional epistemic logics such that languages of these logics are extended by quantification over modal operators or over agents of knowledge and extended by predicate symbols that take modal operators as arguments. Denote this family by \}\). There exist epistemic logics whose languages have the above mentioned properties :311–350, 1995; Lomuscio and Colombetti in Proceedings of ATAL 1996. Lecture Notes in Computer Science, vol 1193, pp 71–85, 1996). But these logics are obtained from first-order (...) modal logics, while a logic of \}\) can be regarded as a propositional multi-modal logic whose language includes quantifiers over modal operators and predicate symbols that take modal operators as arguments. Among the logics of \}\) there are logics with a syntactical distinction between two readings of epistemic sentences: de dicto and de re. We show the decidability of logics of \}\) with the help of the loosely guarded fragment of first-order logic. Namely, we generalize LGF to a higher-order decidable loosely guarded fragment. The latter fragment allows us to construct various decidable propositional epistemic logics with quantification over modal operators. The family of this logics coincides with \}\). There are decidable propositional logics such that these logics implicitly contain quantification over agents of knowledge, but languages of these logics are usual propositional epistemic languages without quantifiers and predicate symbols :345–378, 1993). Some logics of \}\) can be regarded as counterparts of logics defined in Grove and Halpern :345–378, 1993). We prove that the satisfiability problem for these logics of \}\) is Pspace-complete using their counterparts in Grove and Halpern :345–378, 1993). (shrink)

A sentence of first-order logic is satisfiable if it is true in some structure, and finitely satisfiable if it is true in some finite structure. The question arises as to whether there exists an algorithm for determining whether a given formula of first-order logic is satisfiable, or indeed finitely satisfiable. This question was answered negatively in 1936 by Church and Turing (for satisfiability) and in 1950 by Trakhtenbrot (for finite satisfiability).In contrast, the satisfiability and finite satisfiability (...) problems are algorithmically solvable for restricted subsets---or, as we say, fragments---of first-order logic, a fact which is today of considerable interest in Computer Science. This book provides an up-to-date survey of the principal axes of research, charting the limits of decision in first-order logic and exploring the trade-off between expressive power and complexity of reasoning. Divided into three parts, the book considers for which fragments of first-order logic there is an effective method for determining satisfiability or finite satisfiability. Furthermore, if these problems are decidable for some fragment, what is their computational complexity? Part I focusses on fragments defined by restricting the set of available formulas. Topics covered include the Aristotelian syllogistic and its relatives, the two-variable fragment, the guarded fragment, the quantifier-prefix fragments and the fluted fragment. Part II investigates logics with counting quantifiers. Starting with De Morgan's numerical generalization of the Aristotelian syllogistic, we proceed to the two-variable fragment with counting quantifiers and its guarded subfragment, explaining the applications of the latter to the problem of query answering in structured data. Part III concerns logics characterized by semantic constraints, limiting the available interpretations of certain predicates. Taking propositional modal logic and graded modal logic as our cue, we return to the satisfiability problem for two-variable first-order logic and its relatives, but this time with certain distinguished binary predicates constrained to be interpreted as equivalence relations or transitive relations. The work finishes, slightly breaching the bounds of first-order logic proper, with a chapter on logics interpreted over trees. (shrink)

The question of age as a factor in ethical decision-making takes two forms. The first form considers age as a factor at the societal, or policy, level, and the second as a factor in determining the capacity of the individual patient to make decisions regarding their own care. This article satisfies itself with a consideration of only the latter question. The issue of whether age is contributing factor in medical decision-making is frequently posited when one considers ethically charged instances of (...) medical decision making at the end of life. Few would argue that the person who has the capacity for decision-making should be denied the ability to exercise that facility and so, it is when a person has lost their ability for making those choices that the question of age as a contributing factor in ethical decision making is raised. The question therefore becomes one of capacity more then age, with age as a useful, but inexact, gauge of that capacity. The inexactitude of age as a surrogate of capacity is a contributing factor to the problem posed in this series of articles. Therefore, to define the relative contribution of age to the capacity for ethical decision-making this article will focus not on the loss of that ability, but rather on the factors that define the realization of that faculty. To do this it will be necessary to define how that faculty is to be to be measured and what are the characteristics of an ethical decision that define it apart from other decisions. Since at the beginning of life, if age is the only variable (adjusting for other co-morbid states) then the issue of surrogacy is a temporary one and is unlike the adult where the presumption is that the person is unlikely to regain decision-making capacity as they slip further into their morbid state. (shrink)

The idea of rejection of some sentences on the basis of others comes from Aristotle, as Jan Łukasiewicz states in his studies on Aristotle's syllogistic [1939, 1951], concerning rejection of the false syllogistic form and those on certain calculus of propositions. Short historical remarks on the origin and development of the notion of a rejected sentence, introduced into logic by Jan Łukasiewicz, are contained in the Introduction of this paper. This paper is to a considerable extent a summary of papers (...) which are not easily available, even to the Polish reader: (1) J. Słupecki, Funkcja Łukasiewicza (Łukasiewicz’s function), Zeszyty Naukowe Uniwersytetu Wrocławskiego, Seria B, nr 3 (1959), 33-40; (2) U. Wybraniec-Skardowska, Teoria zdań odrzuconych (Theory of Rejected Sentences), (doctoral dissertation under the supervision of Jerzy Słupecki, published as a monograph), Zeszyty Naukowe Wyższej Szkoły Pedagogicznej w Opolu, Studia i Monografie, Nr 22 (1969), 5-131; (3) G. Bryll, Kilka uzupełnień teorii zdań odrzuconych (Some supplements to the theory of rejcted sentences), Zeszyty Naukowe Wyższej Szkoły Pedagogicznej w Opolu, Studia i Mnografie, Nr 22 (1969), 153-154. The paper also contains a good number of results which have not been published yet. Chapter I contains results presented in the papers (1)-(3). It provides an extension of Alfred Tarski’s theory of deductive systems presented by him in the papers [1930]: Fundamentale Begriffe der Methodologie der deduktiven Wssenschaften, I and Über einige fundamentale Begriffe der Metamathematik. The enriched theory is marked with T. The most essential new concept in T is the function Cn-1, whose definition was given by Słupecki in (1) on the basis of the so-called Tarski’s general theory of deductive systems. It has the form: y e Cn-1X iff Ex e X (x e Cn {y}), where Cn is Tarski’s consequence operation. In accordance with the definition: A sentence y is rejected on the basis of the sentences of the set X iff at least one of sentences of X is a consequence of y (is deducible from y). The intuitive meaning of the rejection function Cn-1: on the basis of false sentences we can reject false sentences only (while by means of the consequence operation Cn on the basis of true sentences we can deduce true sentences only). The function Cn-1 is a generalization of the notion of rejected sentences which was introduced into logic by Łukasiewicz. The essential property of the rejection function Cn-1 is that it satisfies the axioms of general Tarski’s consequence Cn, so it is a consequence operation, called the rejection consequence. In addition, it is an additive and normal operation. In Chapter I, there are given notions analogous to those of the theory of deductive systems, but they are written down by means of the symbol ‘Cn-1’ and not ‘Cn’. There are established the properties of introduced notions and differences and analogies taking place between them and properties of respective notions of the theory T. There are also given generalizations of the notions of ‘decidable system’ and ‘consistent system’ used by Łukasiewicz. The short Chapter II contains axioms of the system T’ which is equivalent to the system T. The only difference between sets of primitive notions of these systems consists in the appearance of the function Cn-1 in the system T’ instead of the function Cn. This chapter reproduces the results given in (2), but they are partially simplified. (shrink)

In a 1969 paper, Quine coined the term 'limits of decision'. This term evidently refers to limits on the logical vocabulary of a logic, beyond which satisfiability is no longer decidable. In the same paper. Quine showed that not only monadic formulas, but homogeneous k-adic formulas for arbitrary k lie on the decidable side of the limits of decision. But the precise location of the limits of decision has remained an open question. The present paper answers that question. It (...) addresses the question of decidability of those sublogics of first-order logic that are defined in terms of their logical vocabularies. A complete answer is obtained, thus locating exactly Quine's limits of decision. (shrink)

In this paper we present two types of logics and \ ) where certain p-adic functions are associated to propositional formulas. Logics of the former type are p-adic valued probability logics. In each of these logics we use probability formulas K r,ρ α and D ρ α,β which enable us to make sentences of the form “the probability of α belongs to the p-adic ball with the center r and the radius ρ”, and “the p-adic distance between the probabilities of (...) α and β is less than or equal to ρ”, respectively. Logics of the later type formalize processes of thinking where information are coded by p-adic numbers. We use the same operators as above, but in this formalism K r,ρ α means “the p-adic code of the information α belongs to the p-adic ball with the center r and the radius ρ”, while D ρ α,β means “the p-adic distance between codes of α and β are less than or equal to ρ”. The corresponding strongly complete axiom systems are presented and decidability of the satisfiability problem for each logic is proved. (shrink)

i) We show for each context-free language L that by considering each word of L as a structure in a natural way, one turns L into a finite union of classes which satisfy a finitary analog of the characteristic properties of complete universal first order classes of structures equipped with elementary embeddings. We show this to hold for a much larger class of languages which we call free local languages. ii) We define local languages, a class of languages between free (...) local and context-sensitive languages. Each local language L has a natural extension L ∞ to infinite words, and we prove a series of "pumping lemmas", analogs for each local language L of the "uvxyz theorem" of context free languages: they relate the existence of large words in L or L ∞ to the existence of infinite "progressions" of words included in L, and they imply the decidability of various questions about L or L ∞ . iii) We show that the pumping lemmas of ii) are independent from strong axioms, ranging from Peano arithmetic to ZF + Mahlo cardinals. We hope that these results are useful for a model-theoretic approach to the theory of formal languages. (shrink)

As proved recently, the satisfaction problem for all prenex formulae in the set-theoretic Bernays-Shönfinkel-Ramsey class is semi-decidable over von Neumann's cumulative hierarchy. Here that semi-decidability result is strengthened into a decidability result for the same collection of formulae.

Proposal Information: In this paper it is argued that although Spinoza, unlike other great philosophers of the Enlightenment era, never actually wrote a philosophy of education as such, he did – in his Ethics – write a philosophy of self-improvement that is deeply educational at heart. When looked at against the background of his overall metaphysical system, the educational account that emerges is one that is highly curious and may even, to some extent at least, come across as counter-intuitive in (...) a contemporary setting. This is so because it grounds the greater social and political endeavors of humanity in the individual’s striving for an ever-increasing power of acting. Hence, education, for Spinoza, is a decidedly individualistic affair, but then again, so is the making of society. Since, for Spinoza, every instance of knowledge bears the unique mark of the individual body that expresses it, one might conclude that at the foundation of every social structure is an encounter between concrete bodies; each expressing a particular perspective from where to grasp the world. I would argue, based on this, that one of Spinoza’s main contributions to educational theory is his grounding of larger social endeavors in the striving of the individual. Hinged on the striving to be more rational, as dictated by the doctrine of the conatus, education appears to offer a way of grounding the structure of the human social world in the same principles as those guiding the individual. Spinoza’s doctrine of the imitation of affects thereby offers a way of linking the egoistic striving for power on behalf of the individual with the educational goal of building a sustainable society. It does so as it conditions self-improvement by the human characteristic to imitate what others desire. By being surrounded with people who desire to be more rational, one can utilize this desire for the good and become strengthened in one’s own striving for increasing one’s degree of existence. Consequently, the teaching situation is geared for guiding students towards a more rational life, at the same time as it is geared for the self-improvement of the teacher. This aspect of self-improvement is, ultimately, what will motivate the teacher in striving to enhance the lives of his or her students in the first place. Being unable to self-improve in isolation, the doctrine of the imitation of affects dictates that the rational person will be moved toward a life of generosity, not primarily for altruistic reasons, but out of a desire to become more rational and thus to gain in his or her own power of acting. The question that follows from this, of course, is how does one go about when inculcating a desire to be more rational in one’s students?Education, from a Spinozistic point of view, is ultimately about the cultivation of the potential that lies dormant in each individual, so that a person may live a happier life as a result of understanding, more adequately, their place in the natural world. The challenge, then, becomes one of overcoming the many obstacles that prevent a person from developing their potential. Pedagogy, from this point of view, may be understood in terms of the art of offering the right amount of resistance. This notion is based on the assumption that if a student encounters no resistance – or too much resistance – his or her potential remains just that – a potential. In order to develop this potential the student needs to overcome certain barriers. With regards to this, the role of the teacher may be conceived in terms of the one balancing the amount of resistance so that the student is properly challenged but at the same time not overwhelmed. Methodology or Methods/ Research Instruments or Sources Used: The paper makes for an attempt to outline a Spinozistic philosophy of education based on readings of Spinoza’s texts – primarily the Ethics – and some of the relevant secondary literature such as Della Rocca’s influential reading of Spinoza. As such it is a philosophical inquiry seeking to interconnect some key aspects of Spinoza’s philosophy with some of the major issues of education. Methodologically, this paper argues, in line with Melamed, that rather than turning to the history of philosophy in order to identify ‘precursors to [our] own views’, so as to validate what we already believe we know, it is more fruitful to turn to past philosophers in order to ‘challenge our most basic beliefs and intuitions by studying texts that are both well-argued and strongly opposed to our commonsense’. Accordingly, turning to Spinoza marks an attempt to revisit and reconceptualize some key aspects of educational thought. Conclusions, Expected Outcomes or Findings: A conclusion of this paper is that a Spinozistic philosophy of education would need to focus on resolving the tension between Spinoza’s egoism and education as a social project. To this end it identifies Spinoza’s doctrine of the imitation of affects as a possible link between the individual’s striving for power and the collective agenda of improving human well-being at large. It is also suggested that, in aspiring to inculcate a desire to be more rational in his or her students, the challenge for the Spinozistic teacher is to prompt the students to aspire to reach beyond the temporary satisfactions of the passions so as to acquire a more enduring sense of satisfaction and so that their well-being is more fully under their own command rather than under the command of various external influences. This, in turn, is connected with the notion of resistance in the sense that in experiencing the volatility of fortune – and thereby understanding the instability of relying on one’s passions – a person would appear to be more inclined to strive for a more enduring sense of happiness, even if this would mean giving up on some of the temporary pleasures that one has grown accustomed to. The resistance, then, may be conceived in terms of the overcoming of temporary pleasures that stand in the way of the developing of one’s potential. In this scenario the role of the teacher may be understood in terms of someone offering a well-balanced amount of resistance. This means that to accommodate one’s students – in the sense that one approaches them in terms of prospective customers, aspiring to satisfy their demands – is inimical to education insofar as the wants and desires of students are, generally speaking, caused by passive affects rather than their rational wills. References: Aloni, N.. Spinoza as Educator: From Eudaimonistic Ethics to an Empowering and Liberating Pedagogy. Educational Philosophy and Theory 40, pp. 531–544.Della Rocca, M.. Spinoza. New York: Routledge.Della Rocca, M.. Rationalism, Idealism, Monism, and Beyond. In: E. Förster & Y. Y. Melamed Spinoza and German Idealism. Cambridge: Cambridge University Press, pp. 7–26.Derry, J.. The Unity of Intellect and Will: Vygotsky and Spinoza. Educational Review, 56, pp. 113–120.Lloyd, G.. Spinoza and Educating the Imagination. In: A. O. Rorty Philosophers on Education: Historical Perspectives. London: Routledge, pp. 157–172.Melamed, Y. Y.. Spinoza’s Metaphysics: Substance and Thought. Oxford: Oxford University Press.Nadler, S.. Eternity and Immortality in Spinoza’s Ethics. Midwest Studies in Philosophy 26, pp. 224–244.Poulimatka, T.. Spinoza’s Theory of Teaching and Indoctrination. Educational Philosophy and Theory 33, pp. 397–410.Spinoza, B.. The Ethics. In: E. Curley A Spinoza Reader: The Ethics and Other Works. Princeton: Princeton Unive. (shrink)

An important lesson that philosophy can learn from the Turing Test and computer science more generally concerns the careful use of the method of Levels of Abstraction (LoA). In this paper, the method is first briefly summarised. The constituents of the method are “observables”, collected together and moderated by predicates restraining their “behaviour”. The resulting collection of sets of observables is called a “gradient of abstractions” and it formalises the minimum consistency conditions that the chosen abstractions must satisfy. Two useful (...) kinds of gradient of abstraction – disjoint and nested – are identified. It is then argued that in any discrete (as distinct from analogue) domain of discourse, a complex phenomenon may be explicated in terms of simple approximations organised together in a gradient of abstractions. Thus, the method replaces, for discrete disciplines, the differential and integral calculus, which form the basis for understanding the complex analogue phenomena of science and engineering. The result formalises an approach that is rather common in computer science but has hitherto found little application in philosophy. So the philosophical value of the method is demonstrated by showing how making the LoA of discourse explicit can be fruitful for phenomenological and conceptual analysis. To this end, the method is applied to the Turing Test, the concept of agenthood, the definition of emergence, the notion of artificial life, quantum observation and decidable observation. It is hoped that this treatment will promote the use of the method in certain areas of the humanities and especially in philosophy. (shrink)

The objective of this article is to propose a precise characterization of the collective practice behind at least an important part of the phenomena named “decision by consensus”. First, I provide descriptions of the use of this rule, and give a definition of the non-opposition rule, both as a specific sequence of acts and as a stopping rule. Second, I challenge the usual way of understanding the non-opposition rule by contrast with voting, stating that the contrast between logic of approval (...) and logic of consent also has to be taken into account. Third, I examine the conditions of its use. The non-opposition rule satisfies groups whose concern is to decide without dividing. Finally, from the analytic benefit of opening up decision by consensus as the use of the non-opposition rule, I will examine, in a fourth part, whether consensus in decision-making is as democratic a procedure as is sometimes thought. (shrink)

An exponential $\exp $ on an ordered field $$. The structure $$ is then called an ordered exponential field. A linearly ordered structure $$ is called o-minimal if every parametrically definable subset of M is a finite union of points and open intervals of M.The main subject of this thesis is the algebraic and model theoretic examination of o-minimal exponential fields $$ whose exponential satisfies the differential equation $\exp ' = \exp $ with initial condition $\exp = 1$. This study (...) is mainly motivated by the Transfer Conjecture, which states as follows:Any o-minimal exponential field $$ whose exponential satisfies the differential equation $\exp ' = \exp $ with initial condition $\exp =1$ is elementarily equivalent to $\mathbb {R}_{\exp }$.Here, $\mathbb {R}_{\exp }$ denotes the real exponential field $$, where $\exp $ denotes the standard exponential $x \mapsto \mathrm {e}^x$ on $\mathbb {R}$. Moreover, elementary equivalence means that any first-order sentence in the language $\mathcal {L}_{\exp } = \{+,-,\cdot,0,1, <,\exp \}$ holds for $$ if and only if it holds for $\mathbb {R}_{\exp }$.The Transfer Conjecture, and thus the study of o-minimal exponential fields, is of particular interest in the light of the decidability of $\mathbb {R}_{\exp }$. To the date, it is not known if $\mathbb {R}_{\exp }$ is decidable, i.e., whether there exists a procedure determining for a given first-order $\mathcal {L}_{\exp }$ -sentence whether it is true or false in $\mathbb {R}_{\exp }$. However, under the assumption of Schanuel’s Conjecture—a famous open conjecture from Transcendental Number Theory—a decision procedure for $\mathbb {R}_{\exp }$ exists. Also a positive answer to the Transfer Conjecture would result in the decidability of $\mathbb {R}_{\exp }$. Thus, we study o-minimal exponential fields with regard to the Transfer Conjecture, Schanuel’s Conjecture, and the decidability question of $\mathbb {R}_{\exp }$.Overall, we shed light on the valuation theoretic invariants of o-minimal exponential fields—the residue field and the value group—with additional induced structure. Moreover, we explore elementary substructures and extensions of o-minimal exponential fields to the maximal ends—the smallest elementary substructures being prime models and the maximal elementary extensions being contained in the surreal numbers. Further, we draw connections to models of Peano Arithmetic, integer parts, density in real closure, definable Henselian valuations, and strongly NIP ordered fields.Parts of this thesis were published in [2–5].Abstract prepared by Lothar Sebastian KrappE-mail: [email protected]: https://d-nb.info/1202012558/34. (shrink)

Vermaas and Houkes advance four desiderata for theories of artifact function, and classify such theories into non-intentionalist reproduction theories on the one hand and intentionalist non-reproduction theories on the other. They argue that non-intentionalist reproduction theories fail to satisfy their fourth desideratum. They maintain that only an intentionalist non-reproduction theory can satisfy all the desiderata, and they offer a version that they believe does satisfy all of them. I reply that intentionalist non-reproduction theories, including their version, fail to satisfy their (...) first desideratum. Thus neither type of function theory satisfies all the desiderata. This suggests that the list of desiderata may well be inconsistent, and that ultimately we may have to decide whether to give up the first desideratum or the fourth one. I recommend giving up the fourth one on the grounds that this choice preserves the phenomenologically salient social aspects of artifact function. Vermaas and Houkes attempt to satisfy their desiderata Why this attempt fails What is to be done? (shrink)

The teratogenicity of the Zika virus was considered established in 2016, and is an interesting case because three different sets of causal criteria were used to assess teratogenicity. This paper appeals to the thesis of Russo and Williamson (2007) to devise an epistemological framework that can be used to compare and evaluate sets of causal criteria. The framework can also be used to decide when enough criteria are satisfied to establish causality. Arguably, the three sets of causal criteria considered here (...) offer only a rudimentary assessment of mechanistic studies, and some suggestions are made as to alternative ways to establish causality. (shrink)

A Kripke model ? is a submodel of another Kripke model ℳ if ? is obtained by restricting the set of nodes of ℳ. In this paper we show that the class of formulas of Intuitionistic Predicate Logic that is preserved under taking submodels of Kripke models is precisely the class of semipositive formulas. This result is an analogue of the Łoś-Tarski theorem for the Classical Predicate Calculus.In Appendix A we prove that for theories with decidable identity we can take (...) as the embeddings between domains in Kripke models of the theory, the identical embeddings. This is a well known fact, but we know of no correct proof in the literature. In Appendix B we answer, negatively, a question posed by Sam Buss: whether there is a classical theory T, such that ℋT is HA. Here ℋT is the theory of all Kripke models ℳ such that the structures assigned to the nodes of ℳ all satisfy T in the sense of classical model theory. (shrink)

Let V be the cumulative set theoretic hierarchy, generated from the empty set by taking powers at successor stages and unions at limit stages and, following [2], let the primitive language of set theory be the first order language which contains binary symbols for equality and membership only. Despite the existence of ∀∀-formulae in the primitive language, with two free variables, which are satisfiable in V but not by finite sets ([5]), and therefore of ƎƎ∀∀ sentences of the same language, (...) which are undecidable in ZFC without the Axiom of Infinity, truth in V for Ǝ*∀∀-sentences of the primitive language, is decidable ([1]). Completeness of ZF with respect to such sentences follows. (shrink)

We consider a new fragment of first-order logic with two variables. This logic is defined over interval structures. It constitutes unary predicates, a binary predicate and a function symbol. Considering such a fragment of first-order logic is motivated by defining a general framework for event-based interval temporal logics. In this paper, we present a sound, complete and terminating decision procedure for this logic. We show that the logic is decidable, and provide a NEXPTIME complexity bound for satisfiability. This result (...) shows that even a simple decidable fragment of first-order logic has NEXPTIME complexity. (shrink)