We show that both the $n$-density and the bounded $n$-width of Kripke frames can be modally defined not only with natural and well-known Sahlqvist formulae containing a linear number of different propositional variables but also with formulae of polynomial length with a logarithmic number of different propositional variables and then we prove that this exponential decrease in the number of variables leads us outside the class of Sahlqvist formulae.

The basis of the Periodic Table is discussed. Electronic configuration recurs in only 21 out of the 32 groups. A better basis is derived by considering the highest classical valency (v) exhibited by an element and a new measure, the highest valency in carbonyl compounds (v*). This leads to a table based on the number of outer electrons possessed by an atom (N) and the number of electrons required for it to achieve an inert (noble) gas configuration (N*). Periodicity of (...) these is nearly complete. The new basis helps to settle the question of the best form of table and related issues. (shrink)

It is and has been widely assumed, e.g., in Hintikka and Hintikka, that the logical theory available from Wittgenstein’s Tractatus Logico-Philosophicus affords a foundation for the conventional logic represented in standard formulations of classical propositional, first-order predicate, and perhaps higher-order formal systems. The present article is a detailed attempt at a mathematical demonstration, or as much demonstration as the sources will allow, that this assumption is false by contemporary lights and according to a preferred account of argument validity. When Wittgenstein’s (...) description of the forms of propositions or Sätze in the 5-numbered remarks and Remark 6 is given a close reconstruction, one sees that no Tractarian proposition is logically equivalent to a simple universally or existentially quantified formula of first-order predicate logic. Therefore, although Wittgenstein employs the sign ∀—or, in his notation—occasionally in explanations and illustrations, e.g., 4.0411 and 5.1311, when it comes to logic, the sign ∀ should receive in Tractatus a semantical treatment that is nonstandard. En route to that result, we show that the hierarchy of variables–and, hence, of propositions–defined at 5.501 incorporates the expressive power of finitary classical propositional logic. Also, when constructed over a first-order language for arithmetic, formulae corresponding to the specification of 5.501 pick out all and only arithmetic sets of numbers. Consequently, Wittgenstein’s hierarchy of iterated N-propositions–as described in vide Remark 6–does not collapse: at any level k, one finds propositions at k + 1 or above that are not logically equivalent to any proposition formed at k or below. (shrink)

We formalize various counting principles and compare their strengths over $$V^{0}$$ V 0. In particular, we conjecture the following mutual independence between: a uniform version of modular counting principles and the pigeonhole principle for injections, a version of the oddtown theorem and modular counting principles of modulus p, where p is any natural number which is not a power of 2, and a version of Fisher’s inequality and modular counting principles. Then, we give sufficient conditions to prove them. We give (...) a variation of the notion of PHP-tree and k-evaluation to show that any Frege proof of the pigeonhole principle for injections admitting the uniform counting principle as an axiom scheme cannot have o(n)-evaluations. As for the remaining two, we utilize well-known notions of p-tree and k-evaluation and reduce the problems to the existence of certain families of polynomials witnessing violations of the corresponding combinatorial principles with low-degree Nullstellensatz proofs from the violation of the modular counting principle in concern. (shrink)

We give alternative characterizations of exact, extendible and projective formulas in intuitionistic propositional calculus IPC in terms of n -universal models. From these characterizations we derive a new syntactic description of all extendible formulas of IPC in two variables. For the formulas in two variables we also give an alternative proof of Ghilardi’s theorem that every extendible formula is projective.

We study the theories I∇n, L∇n and overspill principles for ∇n formulas. We show that IEn ⇒ L∇n ⇒ I∇n, but we do not know if I∇n L∇n. We introduce a new scheme, the growth scheme Crγ, and we prove that L∇n ⇒ Cr∇n⇒ I∇n. Also, we analyse the utility of bounded collection axioms for the study of the above theories.

We give alternative characterizations of exact, extendible and projective formulas in intuitionistic propositional calculus IPC in terms of n-universal models. From these characterizations we derive a new syntactic description of all extendible formulas of IPC in two variables. For the formulas in two variables we also give an alternative proof of Ghilardi’s theorem that every extendible formula is projective.

Knowledge representation and reasoning (KRR) is a fundamental area in artificial intelligence (AI) research, focusing on encoding world knowledge as logical formulae in ontologies. This formalism enables logic-based AI systems to deduce new insights from existing knowledge. Within KRR, description logics (DLs) are a prominent family of languages to represent knowledge formally. They are decidable fragments of first-order logic, and their models can be visualized as edge- and vertex-labeled directed binary graphs. DLs facilitate various reasoning tasks, including checking the satisfiability (...) of statements and deciding entailment. However, a significant challenge arises in the computation of models of DL ontologies in the context of explaining reasoning results. Although existing algorithms efficiently compute models for reasoning tasks, they usually do not consider aspects of human cognition, leading to models that may be less effective for explanatory purposes. This paper tackles this challenge by proposing an approach to enhance the intelligibility of models of DL ontologies for users. By integrating insights from cognitive science and philosophy, we aim to identify key graph properties that make models more accessible and useful for explanation. (shrink)

For a theory T, we study relationships among IΔ n +1 (T), LΔ n+1 (T) and B * Δ n+1 (T). These theories are obtained restricting the schemes of induction, minimization and (a version of) collection to Δ n+1 (T) formulas. We obtain conditions on T (T is an extension of B * Δ n+1 (T) or Δ n+1 (T) is closed (in T) under bounded quantification) under which IΔ n+1 (T) and LΔ n+1 (T) are equivalent. These conditions (...) depend on Th Πn +2 (T), the Π n+2 –consequences of T. The first condition is connected with descriptions of Th Πn +2 (T) as IΣ n plus a class of nondecreasing total Π n –functions, and the second one is related with the equivalence between Δ n+1 (T)–formulas and bounded formulas (of a language extending the language of Arithmetic). This last property is closely tied to a general version of a well known theorem of R. Parikh. Using what we call Π n –envelopes we give uniform descriptions of the previous classes of nondecreasing total Π n –functions. Π n –envelopes are a generalization of envelopes (see [10]) and are closely related to indicators (see [12]). Finally, we study the hierarchy of theories IΔ n+1 (IΣ m ), m≥n, and prove a hierarchy theorem. (shrink)

This is a new edition, revised and expanded, of a seminal work in the logic and philosophy of time, originally published in 1968. Arthur N. Prior was the founding father of temporal logic. His work has attracted increased attention in the decades since his death: its influence stretches beyond philosophy and logic to computer science and formal linguistics. Prior's fundamental ideas about the logic of time are presented here along with his investigations into the formal properties of time and tense. (...) Already in 1969 Prior had been planning a new edition of Papers on Time and Tense, to incorporate his more recent work. Because of his untimely death this plan was never followed through--till now. Seven important papers have been added to the original selection, as well as a comprehensive bibliography of his work and an illuminating interview with his widow, Mary Prior, about his life and work. In addition, the Polish logic which made the original book difficult for many readers has been replaced by standard logical notation. This new edition will secure the classic status of the book. (shrink)

© 2016 Regents of the University of California.The Review summarizes much of particle physics and cosmology. Using data from previous editions, plus 3,062 new measurements from 721 papers, we list, evaluate, and average measured properties of gauge bosons and the recently discovered Higgs boson, leptons, quarks, mesons, and baryons. We summarize searches for hypothetical particles such as supersymmetric particles, heavy bosons, axions, dark photons, etc. All the particle properties and search limits are listed in Summary Tables. We also give numerous (...) tables, figures, formulae, and reviews of topics such as Higgs Boson Physics, Supersymmetry, Grand Unified Theories, Neutrino Mixing, Dark Energy, Dark Matter, Cosmology, Particle Detectors, Colliders, Probability and Statistics. Among the 117 reviews are many that are new or heavily revised, including those on Pentaquarks and Inflation. The complete Review is published online in a journal and on the website of the Particle Data Group. The printed PDG Book contains the Summary Tables and all review articles but no longer includes the detailed tables from the Particle Listings. A Booklet with the Summary Tables and abbreviated versions of some of the review articles is also available. (shrink)

We give necessary conditions for a set to be definable by a formula with a universal quantifier and an existential quantifier over algebraic integer rings or algebraic number fields. From these necessary conditions we obtain some undefinability results. For example, N is not definable by such a formula over Z. This extends a previous result of R. M. Robinson.

If Y is normal with parameters μ and σ , the standard normal Z = ( Y - μ )/ σ has parameters and 1. Central Limit Theorem: For any sequence Y 1, Y 2, ... of IID random variables with expectation μ and variance σ , the cdf of Z is the limit, as n → ∞, of the cdf of ( Y 1 + Y 2 + … + Yn - nμ )/( σ √\x{D835}\x{DC5B}).

Considering a fixed language of propositional calculus and the class of formulas with n propositional indeterminates, the evaluation of these formulas with respect to a given truth-values assignment for these indeterminates and with respect to the usual worst-case analysis is proved to belong to the O-class.

For a subset K ⊆ [0, 1], the notion of K-satisfiability is a generalization of the usual satisfiability in first order fuzzy logics. A set Γ of closed formulas in a first order language τ is K-satisfiable, if there exists a τ-structure such that ∥ σ ∥ ∈ K, for any σ ∈ Γ. As a consequence, the usual compactness property can be replaced by the K-compactness property. In this paper, the K-compactness property for Łukasiewicz first order logic is (...) investigated. Using the ultraproduct construction, it is proved that for any closed subset K and set Γ of closed formulas, Γ is K-satisfiable if and only if it is finitely K-satisfiable. (shrink)

The purpose of this paper is to present some results instit theory, a theory of agency proposed by N. Belnap and M. Perloff. We will establish a correspondence between the numbers ofstit modalities and the complexity degrees ofbusy choice sequences in semantic structures, and consequently, a correspondence between the number of modes of actions/inactions instit theory and the complexity degrees ofbusy choice sequences in semantic structures.

In his book A History of the Culture of the Modern Period, the eminent scholar Egon Friedell wrote concerning Descartes's influence in seven-teenth-century France that all the efforts of the great philosopher's critics notwithstanding, "his school inexorably extended its influence not only through the ‘occasionalists,’ as his closest disciples and followers in philosophy were called, and through the remarkable logic of the Port-Royal school The Art of Thinking and Boileau's tone-setting work The Poetic Art: rather, all of France, headed by (...) the "Sun King," who at one time had banned Descartes's works, became his school. The state, economy, theater, architecture, religious affairs, strategy, and the art of gardening all became Cartesian. Descartes reigned unrestricted, as a sovereign, in all things: in tragedy, where the passions struggled with one another; in comedy, where algebraic formulas were devised for human characters; in the area around Versailles, dominated by the abstract symmetry of gardens; in the analytic methods for waging war and running the economy; and in the so to speak deductive ritual of hairstyles and manners, dances and genteel conversation. One can even say that to this day every Frenchman is a born Cartesian.". (shrink)

Gaifman's normal form theorem showed that every first-order sentence of quantifier rank n is equivalent to a Boolean combination of “scattered local sentences”, where the local neighborhoods have radius at most 7n−1. This bound was improved by Lifsches and Shelah to 3×4n−1. We use Ehrenfeucht–Fraïssé type games with a “shrinking horizon” to get a spectrum of normal form theorems of the Gaifman type, depending on the rate of shrinking. This spectrum includes the result of Lifsches and Shelah, with a more (...) easily understood proof and with the bound on the radius improved to 4n−1. We also obtain bounds for a normal form theorem of Schwentick and Barthelmann. (shrink)

Justification Logic provides an axiomatic description of justifications and delegates the question of their nature to semantics. In this note, we address the conceptual issue of the logical type of justifications: we argue that justifications in the logical setting are naturally interpreted as sets of formulas which leads to a class of epistemic models that we call modular models . We show that Fitting models for Justification Logic naturally encode modular models and can be regarded as convenient pre-models of (...) the former. (shrink)

A probability distribution can be given to the set of isomorphism classes of models with universe {1, ..., n} of a sentence in first-order logic. We study the entropy of this distribution and derive a result from the 0–1 law for first-order sentences.

In this paper a new method, elimination of Skolem functions for monotone formulas, is developed which makes it possible to determine precisely the arithmetical strength of instances of various non-constructive function existence principles. This is achieved by reducing the use of such instances in a given proof to instances of certain arithmetical principles. Our framework are systems ${\cal T}^{\omega} :={\rm G}_n{\rm A}^{\omega} +{\rm AC}$ -qf $+\Delta$ , where (G $_n$ A $^{\omega})_{n \in {\Bbb N}}$ is a hierarchy of (weak) (...) subsystems of arithmetic in all finite types (introduced in [14]), AC-qf is the schema of quantifier-free choice in all types and $\Delta$ is a set of certain analytical principles which e.g. includes the binary König's lemma. We apply this method to show that the arithmetical closures of single instances of $\Pi^0_1$ -comprehension and -choice contribute to the growth of extractable bounds from proofs relative to ${\cal T}^\omega$ only by a primitive recursive functional in the sense of Kleene. In subsequent papers these results are widely generalized and the method is used to determine the arithmetical content of single sequences of instances of the Bolzano-Weierstraß principle for bounded sequences in ${\Bbb R}^d$ , the Ascoli-lemma and others. (shrink)

The paper deals with pp formulas in the language of reduced special groups, and the question of when the validity of a pp formula on each finite subspace of a space of orderings implies its global validity [18]. A large new class of pp formulas is introduced for which this is always the case, assuming the space of orderings in question has finite stability index. The paper also considers pp formulas of the special type $b\in \Pi _{i=1}^{n}\,D\langle (...) 1,a_{i}\rangle $. Formulas of this type with n = 3 are the simplest sort of pp formula not covered by the result, and are also the source of the recent counterexamples in [9] and [19]. (shrink)

Each closed (i.e. variable free) formula of interpretability logic is equivalent in ILF to a closed formula of the provability logic G, thus to a Boolean combination of formulas of the form n.

The main result proved in the paper is that on every recursive structure the intrinsically hyperarithmetical sets coincide with the relatively intrinsically hyperarithmetical sets. As a side effect of the proof an effective version of the Kueker's theorem on definability by means of infinitary formulas is obtained.

RésuméUn paradigme en vogue en informatique théorique exploite l'analogie entre les formules et les types et traite une deduction Al… An→ B comme une opération plurisortale. On propose ici d'étendre cette analogie aux déductions de la forme Al… An→, où la place à droite de la flèche est vide. D'un point de vue logique, une telle déduction constitue une réfutation de la conjonction desformules qui se trouvent à gauche de la flèche. On défend l'idée qu'ilfaut, selon ce paradigme étendu, interpréter (...) la flèche comme assignant à n'importe quelle séquence al… an, où aiest de type Ai, le type des valeurs de vérite correspondantes. Pour que cela fonctionne, cependant, il faut abandonner la règle structurale de l'affaiblissement à droite de la flèche. La négation de A est alors interprétée comme l'ensemble puissance de A et la complétude fonctionnelle habituelle s'identifie au schème de compréhension avec extensionnalitè. (shrink)

Friedman misunderstands postmodernism?or, as it could better be called, metamodernism. Metamodernism is the common sense beyond the lunatic formulas of the Vienna Circle and conventional statistics. It has little to do with the anxieties of Continental intellectuals. It therefore is necessary for serious empirical work on the role of the state.

We say that two arithmetical formulas A, B have the Σ1-interpolation property if they have an ‘interpolant’ σ, i.e., a Σ1 formula such that the formulas A→σ and σ→B are provable in Peano Arithmetic PA. The Σ1-interpolability predicate is just a formalization of this property in the language of arithmetic.Using a standard idea of Gödel, we can associate with this predicate its provability logic, which is the set of all formulas that express arithmetically valid principles in the (...) modal language with two modal operators, □ for provability in PA and for Σ1-interpolability. In this paper we determine this provability logic .It turns out that this problem appears to be quite similar to the problem of such modal description of relative interpretability, a problem, solved by Berarducci and Shavrukov. However, the present case is sometimes easier. In particular, we prove in this paper the fixed point property and the Craig interpolation property for our modal system ELH. (shrink)

The Tarski T-Schema has a propositional version. If we use ϕ as a metavariable for formulas and use terms of the form that-ϕ to denote propositions, then the propositional version of the T-Schema is: that-ϕ is true if and only if ϕ. For example, that Cameron is Prime Minister is true if and only if Cameron is Prime Minister. If that-ϕ is represented formally as [λ ϕ], then the T-Schema can be represented as the 0-place case of λ-Conversion. If (...) we interpret [λ…] as a truth-functional context, then using traditional logical techniques, one can prove that the propositional version of the T-Schema is a tautology, literally. Given how well-accepted these logical techniques are, we conclude that the T-Schema, in at least one of its forms, is a not just a logical truth but a tautology at that. (shrink)

We show that every formula of L ω 1p is equivalent to one which is a propositional combination of formulas with only one quantifier. It follows that the complete theory of a probability model is determined by the distribution of a family of random variables induced by the model. We characterize the class of distribution which can arise in such a way. We use these results together with a form of de Finetti's theorem to prove an almost sure interpolation (...) theorem for L ω 1p. (shrink)

These lecture notes were composed while teaching a class at Stanford and studying the work of Brian Chellas (Modal Logic: An Introduction, Cambridge: Cambridge University Press, 1980), Robert Goldblatt (Logics of Time and Computation, Stanford: CSLI, 1987), George Hughes and Max Cresswell (An Introduction to Modal Logic, London: Methuen, 1968; A Companion to Modal Logic, London: Methuen, 1984), and E. J. Lemmon (An Introduction to Modal Logic, Oxford: Blackwell, 1977). The Chellas text influenced me the most, though the order of (...) presentation is inspired more by Goldblatt.2 My goal was to write a text for dedicated undergraduates with no previous experience in modal logic. The text had to meet the following desiderata: (1) the level of difficulty should depend on how much the student tries to prove on his or her own—it should be an easy text for those who look up all the proofs in the appendix, yet more difficult for those who try to prove everything themselves; (2) philosophers (i.e., colleagues) with a basic training in logic should be able to work through the text on their own; (3) graduate students should find it useful in preparing for a graduate course in modal logic; (4) the text should prepare people for reading advanced texts in modal logic, such as Goldblatt, Chellas, Hughes and Cresswell, and van Benthem, and in particular, it should help the student to see what motivated the choices in these texts; (5) it should link the two conceptions of logic, namely, the conception of a logic as an axiom system (in which the set of theorems is constructed from the bottom up through proof sequences) and the conception of a logic as a set containing initial ‘axioms’ and closed under ‘rules of inference’ (in which the set of theorems is constructed from the top down, by carving out the logic from the set of all formulas as the smallest set closed under the rules); finally, (6) the pace for the presentation of the completeness theorems should be moderate—the text should be intermediate between Goldblatt and Chellas in this regard (in Goldblatt, the completeness proofs come too quickly for the undergraduate, whereas in Chellas, too many unrelated.... (shrink)

Let HA be Heyting's arithmetic, and let CS denote the conjunction of Kreisel's axioms for the creative subject: \begin{eqnarray*} {\rm CS}_1.&&\quad \,\forall\, x (\qed_x A \vee \; \neg \qed_x A)\; ,\nn {\rm CS}_2. &&\quad \,\forall\, x (\qed_x A\to A)\; ,\nn {\rm CS}_3^{\rm S}. &&\quad A\to\,\exists\, x \qed_x A\; ,\nn {\rm CS}_4.&&\quad \,\forall\, x\,\forall\, y (\qed_x A & y \ge x\to\qed_y A)\; .\nn \end{eqnarray*} It is shown that the theory HA + CS with the induction schema restricted to arithmetical (i.e. not (...) containing $\qed$ ) formulas is conservative over HA. (shrink)

Arthur Norman Prior (1914-69) was a logician and philosopher from New Zealand who contributed crucially to the development of ‘non-standard’ logics, especially of the modal variety. His greatest achievement was the invention of modern temporal logic, worked out in close connection with modal logic. However, his work in logic had a much broader scope. He was also the founder of hybrid logic, and he made important contributions to deontic logic, modal logic, the theory of quantification, the nature of propositions and (...) the history of logic. In addition, he discussed questions of ethics, free will, and general theology. Prior’s philosophical works comprise about 200 titles. His earliest articles center on philosophical theology and historical studies of Scottish Reformed Theology. This led on to the publication of his first influential work on ethics: Logic and The Basis of Ethics (1949). With the invention of tense-logic in the early 1950s, his focus shifted to investigations into the syntax of tempo-modal logic leading to his seminal Time and Modality (1957), a volume derived from his John Locke Lectures in Oxford in 1956. Furthermore Prior, together with the Irish mathematician and logician C.A. Meredith (1904-76), made important early contributions to the semantics of possible worlds. Prior’s tense-logic provided a strong conceptual framework for problems pertaining to the philosophy of time. In Time and Modality, Prior discussed the philosophical implications of Ruth Barcan’s famous formulae for tense-logic, and in the 1960s he worked on the notion of the present. The most persistent problem running through Prior’s work is his study of the questions surrounding human freedom and divine foreknowledge, and more general philosophical problems emerging from this classical theological question. His thorough analysis of this problem, with the conceptual tools of tense-logic, received a crucial impetus from his correspondence with the young Saul Kripke, when the latter suggested the semantic tool of branching time to Prior. Prior’s development of two solutions based on branching time for the problem of future contingency, the Peircean and the Ockham solution, was most thoroughly developed in Past, Present and Future (1967), the most important work published by Prior. Characteristically for Prior’s methodological approach, the development of these two solutions were at the same time a development of two new systems of tense logic, and vice versa. One of Prior’s significant contributions to logic was his work on world propositions and instant propositions. In the course of developing these notions he also made one of the earliest formulations of hybrid logic. In Papers on Time and Tense (1968), he presented this idea in a more detailed manner in the context of his four grades of tense-logical involvement. (shrink)

In this paper, the authors discuss Frege's theory of "logical objects" and the recent attempts to rehabilitate it. We show that the 'eta' relation George Boolos deployed on Frege's behalf is similar, if not identical, to the encoding mode of predication that underlies the theory of abstract objects. Whereas Boolos accepted unrestricted Comprehension for Properties and used the 'eta' relation to assert the existence of logical objects under certain highly restricted conditions, the theory of abstract objects uses unrestricted Comprehension for (...) Logical Objects and banishes encoding formulas from Comprehension for Properties. The relative mathematical and philosophical strengths of the two theories are discussed. Along the way, new results in the theory of abstract objects are described, involving: the theory of extensions, the theory of directions and shapes, and the theory of truth values. (shrink)

We review studies of an evolution operator ℒ for a discrete Langevin equation with a strongly hyperbolic classical dynamics and a Gaussian noise. The leading eigenvalue of ℒ yields a physically measurable property of the dynamical system, the escape rate from the repeller. The spectrum of the evolution operator ℒ in the weak noise limit can be computed in several ways. A method using a local matrix representation of the operator allows to push the corrections to the escape rate up (...) to order eight in the noise expansion parameter. These corrections then appear to form a divergent series. Actually, via a cumulant expansion, they relate to analogous divergent series for other quantities, the traces of the evolution operators ℒn. Using an integral representation of the evolution operator ℒ, we then investigate the high order corrections to the latter traces. Their asymptotic behavior is found to be controlled by sub-dominant saddle points previously neglected in the perturbative expansion, and to be ultimately described by a kind of trace formula. (shrink)

We define classes Φnof formulae of first-order arithmetic with the following properties:(i) Everyφϵ Φnis classically equivalent to a Πn-formula (n≠ 1, Φ1:= Σ1).(ii)(iii)IΠnandiΦn(i.e., Heyting arithmetic with induction schema restricted to Φn-formulae) prove the same Π2-formulae.We further generalize a result by Visser and Wehmeier. namely that prenex induction within intuitionistic arithmetic is rather weak: After closing Φnboth under existential and universal quantification (we call these classes Θn) the corresponding theoriesiΘnstill prove the same Π2-formulae. In a second part we consideriΔ0plus collection-principles. We (...) show that both the provably recursive functions and the provably total functions ofare polynomially bounded. Furthermore we show that the contrapositive of the collection-schema gives rise to instances of the law of excluded middle and hence. (shrink)

Bayesians take “definite” or “single-case” probabilities to be basic. Definite probabilities attach to closed formulas or propositions. We write them here using small caps: PROB(P) and PROB(P/Q). Most objective probability theories begin instead with “indefinite” or “general” probabilities (sometimes called “statistical probabilities”). Indefinite probabilities attach to open formulas or propositions. We write indefinite probabilities using lower case “prob” and free variables: prob(Bx/Ax). The indefinite probability of an A being a B is not about any particular A, but rather (...) about the property of being an A. In this respect, its logical form is the same as that of relative frequencies. For instance, we might talk about the probability of a human baby being female. That probability is about human babies in general — not about individuals. If we examine a baby and determine conclusively that she is female, then the definite probability of her being female is 1, but that does not alter the indefinite probability of human babies in general being female. Most objective approaches to probability tie probabilities to relative frequencies in some way, and the resulting probabilities have the same logical form as the relative frequencies. That is, they are indefinite probabilities. The simplest theories identify indefinite probabilities with relative frequencies.3 It is often objected that such “finite frequency theories” are inadequate because our probability judgments often diverge from relative frequencies. For example, we can talk about a coin being fair (and so the indefinite probability of a flip landing heads is 0.5) even when it is flipped only once and then destroyed (in which case the relative frequency is either 1 or 0). For understanding such indefinite probabilities, it has been suggested that we need a notion of probability that talks about possible instances of properties as well as actual instances.. (shrink)

We study the complexity of proving the Pigeon Hole Principle in a monotone variant of the Gentzen Calculus, also known as Geometric Logic. We prove a size-depth trade-off upper bound for monotone proofs of the standard encoding of the PHP as a monotone sequent. At one extreme of the trade-off we get quasipolynomia -size monotone proofs, and at the other extreme we get subexponential-size bounded-depth monotone proofs. This result is a consequence of deriving the basic properties of certain monotone (...) class='Hi'>formulas computing the Boolean threshold functions. We also consider the monotone sequent expressing the Clique-Coclique Principle defined by Bonet, Pitassi and Raz [9]. We show that monotone proofs for this sequent can be easily reduced to monotone proofs of the one-to-one and onto PHP, and so CLIQUE also has quasipolynomia -size monotone proofs. As a consequence of our results, Resolution, Cutting Planes with polynomially bounded coefficients, and Bounded-Depth Frege are exponentially separated from the monotone Gentzen Calculus. Finally, a simple simulation argument implies that these results extend to the Intuitionistic Gentzen Calculus. Our results partially answer some questions left open by P. Pudlák. (shrink)

We define the logic FOTLT(n), to be a monadic monodic fragment of first-order linear temporal logic, with 2n propositions representing the read and write steps of n two-step concurrent database transactions and a time-dependent predicate representing queries giving the sets of data items accessed by those read and write steps at given points in time. The models of FOTLT(n) contain interleaved sequences of the steps of infinitely many occurrences of the n transactions accessing unlimited data over time. A property of (...) serializability is specified for FOTLT(n) formulae. We show that the serializability problem for FOTLT(n) formulae is decidable. (shrink)

This article investigates the prospect of giving de dicto- and de re-necessity a uniform treatment. The historical starting point is a puzzle raised by Aristotle's claim, advanced in one of the modal chapters of his Prior Analytics, that universally privative apodeictic premises simply convert. As regards the Prior and the Posterior Analytics, the data suggest a representation of propositions of the type in question by doubly modally qualified formulae of modal predicate logic that display a necessity operator in two distinct (...) positions. Can the N-operator occurring in these positions be given a unified semantical treatment (which would justify dispensing with a notational differentiation)? A positive answer, based on a suitably shaped truth condition for N-formulae, is given, and is supported in the final section with an alternative proof theoretically based conception of a property's essential belonging to an individual. (shrink)

For a non-zero natural number n, we work with finitary $$\Sigma ^0_n$$ -formulas $$\psi (x)$$ without parameters. We consider computable structures $${\mathcal {S}}$$ such that the domain of $${\mathcal {S}}$$ has infinitely many $$\Sigma ^0_n$$ -definable subsets. Following Goncharov and Kogabaev, we say that an infinite list of $$\Sigma ^0_n$$ -formulas is a $$\Sigma ^0_n$$ -classification for $${\mathcal {S}}$$ if the list enumerates all $$\Sigma ^0_n$$ -definable subsets of $${\mathcal {S}}$$ without repetitions. We show that an arbitrary computable (...) $${\mathcal {S}}$$ always has a $${{\mathbf {0}}}^{(n)}$$ -computable $$\Sigma ^0_n$$ -classification. On the other hand, we prove that this bound is sharp: we build a computable structure with no $${{\mathbf {0}}}^{(n-1)}$$ -computable $$\Sigma ^0_n$$ -classifications. (shrink)

Propositional canonical Gentzen-type systems, introduced in [2], are systems which in addition to the standard axioms and structural rules have only logical rules in which exactly one occurrence of a connective is introduced and no other connective is mentioned. [2] provides a constructive coherence criterion for the non-triviality of such systems and shows that a system of this kind admits cut-elimination iff it is coherent. The semantics of such systems is provided using two-valued non-deterministic matrices (2Nmatrices). [23] extends these results (...) to systems with unary quantifiers of a very restricted form. In this paper we substantially extend the characterization of canonical systems to (n, k)-ary quantifiers, which bind k distinct variables and connect n formulas, and show that the coherence criterion remains constructive for such systems. Then we focus on the case of k ∈ {0, 1} and show that the following statements concerning a canonical calculus G are equivalent: (i) G is coherent, (ii) G has a strongly characteristic 2Nmatrix, and (iii) G admits strong cut-elimination. We also show that coherence is not a necessary condition for standard cut-elimination, and then characterize a subclass of canonical systems for which this property does hold. (shrink)

'Wolterstorff (2009) provides an important explanation to the question: What caused the surprising resurgence in philosophical theology that has occurred over the last 50 years—a resurgence that rivals its zenith in the Middle Ages? This article supplements that with a more fine-grained answer to the question. Recent discoveries in Arthur Norman Prior’s correspondence with J.J.C Smart and Mary Prior, between November 1953 and August 1954 on the possibility of necessary existence, demonstrates the importance of Prior’s discussion of the Barcan formulae (...) in Time and Modality (1957) for the resurgence of analytic theology. The correspondence establishes that Prior’s discovery of tense-logic, and his discussion of quantified tense-logic constituted the perfect opportunity for him to challenge key anti-metaphysical assumptions in analytic philosophy, from which four important consequences can be drawn for the resurgence of philosophical theology. First, Prior’s discussion of time and existence challenged the idea of Russell (1945) and Findlay (1948) on the logical status of a necessary existing being. Second, the discussion challenged the Analytic school’s view of analysis and gave Prior the opportunity to introduce a different perspective on the relationship between logic and metaphysics. Third, it gave Prior a good opportunity to demonstrate that the then-prevailing attitude towards medieval logic was wrong. Fourth, it made it possible for Prior to demonstrate that the highly surprising metaphysical conclusions of quantified tense-logic brings modern logicians into a discussion with the theologically minded medieval logicians. (shrink)

Our aim is to show that translating the modal graphs of Moretti’s “n-opposition theory” (2004) into set theory by a suited device, through identifying logical modal formulas with appropriate subsets of a characteristic set, one can, in a constructive and exhaustive way, by means of a simple recurring combinatory, exhibit all so-called “logical bi-simplexes of dimension n” (or n-oppositional figures, that is the logical squares, logical hexagons, logical cubes, etc.) contained in the logic produced by any given modal graph (...) (an exhaustiveness which was not possible before). In this paper we shall handle explicitly the classical case of the so-called 3(3)-modal graph (which is, among others, the one of S5), getting to a very elegant tetraicosahedronal geometrisation of this logic. (shrink)

In this paper we continue the study of the theories IΔ n+1 (T), initiated in [7]. We focus on the quantifier complexity of these fragments and theirs (non)finite axiomatization. A characterization is obtained for the class of theories such that IΔ n+1 (T) is Π n+2 –axiomatizable. In particular, IΔ n+1 (IΔ n+1 ) gives an axiomatization of Th Π n+2 (IΔ n+1 ) and is not finitely axiomatizable. This fact relates the fragment IΔ n+1 (IΔ n+1 ) to induction (...) rule for Δ n+1 –formulas. Our arguments, involving a construction due to R. Kaye (see [9]), provide proofs of Parsons’ conservativeness theorem (see [16]) and (a weak version) of a result of L.D. Beklemishev on unnested applications of induction rules for Π n+2 and Δ n+1 formulas (see [2]). (shrink)

Let n be a positive integer. By a $\beta_{n}-model$ we mean an $\omega-model$ which is elementary with respect to $\sigma_{n}^{1}$ formulas. We prove the following $\beta_{n}-model$ version of $G\ddot{o}del's$ Second Incompleteness Theorem. For any recursively axiomatized theory S in the language of second order arithmetic, if there exists a $\beta_{n}-model$ of S, then there exists a $\beta_{n}-model$ of S + "there is no countable $\beta_{n}-model$ of S". We also prove a $\beta_{n}-model$ version of $L\ddot{o}b's$ Theorem. As a corollary, we (...) obtain a $\beta_{n}-model$ which is not a $\beta_{n+1}-model$. (shrink)