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)

We study the quantifier complexity and the relative strength of some fragments of arithmetic axiomatized by induction and minimization schemes for Δn+1 formulas.

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)

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)

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)

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)

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)

By a theorem of R. Kaye, J. Paris and C. Dimitracopoulos, the class of the Πn+1-sentences true in the standard model is the only consistent Πn+1-theory which extends the scheme of induction for parameter free Πn+1-formulas. Motivated by this result, we present a systematic study of extensions of bounded quantifier complexity of fragments of first-order Peano Arithmetic. Here, we improve that result and show that this property describes a general phenomenon valid for parameter free schemes. As a consequence, we obtain (...) results on the quantifier complexity, finite axiomatizability and relative strength of schemes for Δn+1-formulas. (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)

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)

Model-theoretic 1-types overa given first-order theory T may be construed as natural metalogical miniatures of G. W. Leibniz' ``complete individual notions'', ``substances'' or ``substantial forms''. This analogy prompts this essay's modal semantics for an essentiallyundecidable first-order theory T, in which one quantifies over such ``substances'' in a boolean universe V(C), where C is the completion of the Lindenbaum-algebra of T.More precisely, one can define recursively a set-theoretic translate of formulae νNϕ of formulae ν of a normal modal theory Tm based (...) on T, such that the counterpart `ξi' of a the modal variable `xi' of L(Tm) in this translation-scheme ranges over elements of V(C) that are 1-types of T with value 1 (sometimes called `definite' C-valued 1-types of T).The article's basic completeness-result (2.13) then establishes that ϕvarphi; is a theorem of Tm iff [[νN(ϕ) is aconsequenceof νN(Tm) for each extension N of T which is a subtheory of the canonical generic theory (ultrafilter) u]] = 1 – or equivalently, that Tm is consistent iff[[there is anextension N of T such that N is a subtheory of the canonical generic theory u, and νN(ϕ) for all ϕ in Tm]] > 0.The proof of thiscompleteness-result also shows that an N which provides a countermodel for a modally unprovable ϕ – or equivalently, a closed set in the Stone space St(T) in the sense of V(C) – is intertranslatable with an `accessibility'-relation of a closely related Kripke-semantics whose `worlds' are generic extensions of an initial universe V via C.This interrelation providesa fairly precise rationale for the semantics' recourse to C-valued structures, and exhibits a sense in which the boolean-valued context is sharp. (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)

An MV-algebra A=(A,0,¬,⊕) is an abelian monoid (A,0,⊕) equipped with a unary operation ¬ such that ¬¬x=x,x⊕¬0=¬0, and y⊕¬(y⊕¬x)=x⊕¬(x⊕¬y). Chang proved that the equational class of MV-algebras is generated by the real unit interval [0,1] equipped with the operations ¬x=1−x and x⊕y=min(1,x+y). Therefore, the free n-generated MV-algebra Free n is the algebra of [0,1]-valued functions over the n-cube [0,1] n generated by the coordinate functions ξ i ,i=1, . . . ,n, with pointwise operations. Any such function f is a (...) McNaughton function, i.e., f is continuous, piecewise linear, and each piece has integer coefficients. Conversely, McNaughton proved that all McNaughton functions f: [0,1] n →[0,1] are in Free n . The elements of Free n are logical equivalence classes of n-variable formulas in the infinite-valued calculus of Łukasiewicz. The aim of this paper is to provide an alternative, representation-free, characterization of Free n. (shrink)

We carry out a study of definability issues in the standard models of Presburger and Skolem arithmetics (henceforth referred to simply as Presburger and Skolem arithmetics, for short, because we only deal with these models, not the theories, thus there is no risk of confusion) supplied with free unary predicates—which are strongly related to definability in the monadic SOA (second-order arithmetic) without × or + , respectively. As a consequence, we obtain a very direct proof for ${\Pi^1_1}$ -completeness of Presburger, (...) and also Skolem, arithmetic with a free unary predicate, generalize it to all ${\Pi^1_n}$ -levels, and give an alternative description of the analytical hierarchy without × or + . Here ‘direct’ means that one explicitly m-reduces the truth of ${\Pi^1_1}$ -formulae in SOA to the truth in the extended structures. Notice that for the case of Presburger arithmetic, the ${\Pi^1_1}$ -completeness was already known, but the proof was indirect and exploited some special ${\Pi^1_1}$ -completeness results on so-called recurrent nondeterministic Turing machines—for these reasons, it was hardly able to shed any light on definability issues or possible generalizations. (shrink)

A fragment with the same provably recursive functions as n iterated inductive definitions is obtained by restricting second order arithmetic in the following way. The underlying language allows only up to n + 1 nested second order quantifications and those are in such a way, that no second order variable occurs free in the scope of another second order quantifier. The amount of induction on arithmetical formulae only affects the arithmetical consequences of these theories, whereas adding induction for arbitrary formulae (...) increases the strength by one inductive definition. (shrink)

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}).

There has been a recent interest in hierarchical generalizations of classic incompleteness results. This paper provides evidence that such generalizations are readily obtainable from suitably formulated hierarchical versions of the principles used in the original proofs. By collecting such principles, we prove hierarchical versions of Mostowski’s theorem on independent formulae, Kripke’s theorem on flexible formulae, Woodin’s theorem on the universal algorithm, and a few related results. As a corollary, we obtain the expected result that the formula expressing “$\mathrm {T}$is$\Sigma _n$-ill” (...) is a canonical example of a$\Sigma _{n+1}$formula that is$\Pi _{n+1}$-conservative over$\mathrm {T}$. (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)

Apostoli and Brown have shown that the class of formulae valid with respect to the class of -ary relational frames is completely axiomatized by Kn: an n-place aggregative system which adjoins [RM], [RN], and a complete axiomatization of propositional logic, with [Kn]:□α1 ∧...∧□αn+1 → □2/ is the disjunction of all pairwise conjunctions αi∧αj )).Their proof exploits the chromatic indices of n-uncolourable hypergraphs, or n-traces. Here, we use the notion of the χ-product of a family of sets to formulate an alternative (...) definition of an n-trace, which in turn enables a new and simpler completeness proof. (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)

A well-known result states that, over basic Kalmar elementary arithmetic EA, the induction schema for ∑n formulas is equivalent to the uniform reflection principle for ∑n + 1 formulas . We show that fragments of arithmetic axiomatized by various forms of induction rules admit a precise axiomatization in terms of reflection principles as well. Thus, the closure of EA under the induction rule for ∑n formulas is equivalent to ω times iterated ∑n reflection principle. Moreover, for k < ω, k (...) times iterated ∑n reflection principle over EA precisely corresponds to the extension of EA by k nested applications of ∑n induction rule.The above relationship holds in greater generality than just stated. In fact, we give general formulas characterizing in terms of iterated reflection principles the extension of any given theory by k nested applications of ∑n or Πn induction rules. In particular, the closure of a theory T under just one application of ∑1 induction rule is equivalent to T together with ∑1 reflection principle for each finite Π2 axiomatized subtheory of T.These results have closely parallel ones in the theory of subrecursive function classes. The rules under study correspond, in a canonical way, to natural closure operators on the classes of provably recursive functions. Thus, ∑1 induction rule precisely corresponds to the primitive recursive closure operator, and ∑1 collection rule, introduced below, corresponds to the elementary closure operator. (shrink)

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)

We deal with the fragment of modal logic consisting of implications of formulas built up from the variables and the constant ‘true’ by conjunction and diamonds only. The weaker language allows one to interpret the diamonds as the uniform reflection schemata in arithmetic, possibly of unrestricted logical complexity. We formulate an arithmetically complete calculus with modalities labeled by natural numbers and ω, where ω corresponds to the full uniform reflection schema, whereas n<ω corresponds to its restriction to arithmetical Πn+1-formulas. This (...) calculus is shown to be complete w.r.t. a suitable class of finite Kripke models and to be decidable in polynomial time. (shrink)

By a result of Paris and Friedman, the collection axiom schema for $\Sigma_{n+1}$ formulas, $B\Sigma_{n+1}$ , is $\Pi_{n+2}$ conservative over $I\Sigma_n$ . We give a new proof-theoretic proof of this theorem, which is based on a reduction of $B\Sigma_n$ to a version of collection rule and a subsequent analysis of this rule via Herbrand's theorem. A generalization of this method allows us to improve known results on reflection principles for $B\Sigma_n$ and to answer some technical questions left open by Sieg (...) [23] and Hájek [9]. We also give a new proof of independence of $B\Sigma_{n+1}$ over $I\Sigma_n$ by a direct recursion-theoretic argument and answer an open problem formulated by Gaifman and Dimitracopoulos [8]. (shrink)

Model-theoretic 1-types overa given first-order theory T may be construed as natural metalogical miniatures of G. W. Leibniz' ``complete individual notions'', ``substances'' or ``substantial forms''. This analogy prompts this essay's modal semantics for an essentiallyundecidable first-order theory T, in which one quantifies over such ``substances'' in a boolean universe V(C), where C is the completion of the Lindenbaum-algebra of T.More precisely, one can define recursively a set-theoretic translate of formulae N of formulae of a normal modal theory Tm based on (...) T, such that the counterpart `i' of a the modal variable `xi' of L(Tm) in this translation-scheme ranges over elements of V(C) that are 1-types of T with value 1 (sometimes called `definite' C-valued 1-types of T). (shrink)

We study the quantifier complexity and the relative strength of some fragments of arithmetic axiomatized by induction and minimization schemes for Δn+1 formulas.

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.

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)

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)

A well known theorem proved by J. Paris and H. Friedman states that BΣn +1 is a Πn +2-conservative extension of IΣn . In this paper, as a continuation of our previous work on collection schemes for Δn +1-formulas , we study a general version of this theorem and characterize theories T such that T + BΣn +1 is a Πn +2-conservative extension of T . We prove that this conservativeness property is equivalent to a model-theoretic property relating Πn-envelopes and (...) Πn-indicators for T . The analysis of Σn +1-collection we develop here is also applied to Σn +1-induction using Parsons' conservativeness theorem instead of Friedman-Paris' theorem.As a corollary, our work provides new model-theoretic proofs of two theorems of R. Kaye, J. Paris and C. Dimitracopoulos : BΣn +1 and IΣn +1 are Σn +3-conservative extensions of their parameter free versions, BΣ–n +1 and IΣ–n +1. (shrink)

In the first part of this paper we investigate the intuitionistic version $iI\!\Sigma_1$ of $I\!\Sigma_1$ (in the language of $PRA$ ), using Kleene's recursive realizability techniques. Our treatment closely parallels the usual one for $HA$ and establishes a number of nice properties for $iI\!\Sigma_1$ , e.g. existence of primitive recursive choice functions (this is established by different means also in [D94]). We then sharpen an unpublished theorem of Visser's to the effect that quantifier alternation alone is much less powerful intuitionistically (...) than classically: $iI\!\Sigma_1$ together with induction over arbitrary prenex formulas is $\Pi_2$ -conservative over $iI\!\Pi_2$ . In the second part of the article we study the relation of $iI\!\Sigma_1$ to $iI\!\Pi_1$ (in the usual arithmetical language). The situation here is markedly different from the classical case in that $iI\!\Pi_1$ and $iI\!\Sigma_1$ are mutually incomparable, while $iI\!\Sigma_1$ is significantly stronger than $iI\!\Pi_1$ as far as provably recursive functions are concerned: All primitive recursive functions can be proved total in $iI\!\Sigma_1$ whereas the provably recursive functions of $iI\!\Pi_1$ are all majorized by polynomials over ${\Bbb N}$ . 0 $iI\!\Pi_1$ is unusual also in that it lacks closure under Markov's Rule $\mbox{MR}_{PR}$. (shrink)

The formulae advanced by Popper to calculate the degree of corroboration C of a scientific hypothesis are unsatisfactory in that the probability values required in the computation are often not available. An attempt is made to define a quantitative measure B* in the place of C in which only countable empirical values would be used. This condition is fulfilled in two basic formulae and eq. ), which could be applied to calculate the degree of corroboration. When m successful falsifications of (...) the hypothesis h appear after a sequence of n unsuccessful ones, the pragmatic degree of corroboration B* results from the difference between B and the analogue value of the falsification F* and eq. ). In the event that the hypothesis can be "rescued" through a correction, increased experimental effort must be made with the revision. This would be taken into account through the correction equation ). When the hypothesis cannot be corrected, however, it can no longer exceed the value of 1-F*, even after numerous verification experiments. In the process of deciding whether a hypothesis is "adequately" verified or falsified, a lower threshold ${\rm B}_{{\rm u}}$ und Bₒ must be selected. These values have to be chosen on an intuitive subjective basis. The same applies to the strength of unsuccessful falsifications . This evaluation is expressed by a multiplicative constant a̱ ) or an additive constant kₐ in eq. . Despite the subjectivity of the values a̱, kₐ necessary for the calculation of B*, and of the values ${\rm B}_{{\rm u}}$ , Bₒ for the decision to discontiue the examination of the hypothesis, I feel that amongst the scientists within a particular field of research, a consensus for these values should be possible. Through a quantitative determination of B* the procedure for testing a hypothesis, considered to be a closed loop process, becomes clearer. To estimate the values of B* could not only have an influence upon the decisions of the respective researchers or research groups examining a hypothesis, but also be of assistance in decisions regarding research grants when financial resources are limited. (shrink)

The present text discusses whether there is a tension between aphorisms 6.1-6.13 of the Tractatus and the Church-Turing theorem about the decidability of predicate logic. We attempt to establish the following points: (i) Aphorisms 6.1-6.13 are not consistent with the Church-Turing theorem. (ii) The logical symbolism of the Tractatus, built from the N-operator, can (and should) be interpreted as expressively complete with respect to first-order formulas. (iii) Wittgenstein’s reasons for believing that Logic is decidable were purely philosophical and the undecidability (...) result shows that there are aspects of his criticisms of Frege and Russell that become unjustified in light of these results. (shrink)

Fundamental Theory has been called an "unfinished symphony" and "a challenge to the musicians among natural philosophers of the future". This book, written in 1944 but left unfinished because Eddington died too soon, proved to be his final effort at a vision for harmonization of quantum physics and relativity. The work is less connected and internally integrated than 'Protons and Electrons' while representing a later point in the author's thought arc. The really interested student should read both books together.The physical (...) and mathematical reasoning are very deep, but it is possible to enjoy much of the flavor of the book even without following everything. The tidbits given below illustrate Eddington's beautiful and mellifluous English style. This edition contains a clickable table of contents and some interesting illustrations.WARNING: Due to the complexity of the mathematical typesetting, the only way to reproduce this book has been as a series of scanned page images. We believe this work is scientifically and culturally important, and despite a few imperfections and the inevitably small print, have brought it back into print as part of our continuing commitment to the preservation of Eddington's work. On a portable electronic reader the pages come out pretty small, but they are legible. On a desktop computer running the Amazon app, they are perfectly fine. We appreciate your understanding, and hope you enjoy this valuable book.TIDBITS:The number of protons and electrons in the universe would, in itself, be merely a matter of idle curiosity. But N has a more general significance as a fundamental constant which enters into many physical formulae. Its special interpretation as the number of particles in the universe arises in the following way. If we consider a distribution of hydrogen in equilibrium at zero temperature, the presence of the matter produces a curvature of space, and the curvature causes the space to close when the number of particles contained in it reaches a certain total; that number is N. The present investigation seeks to determine N directly from the principles of measurement. We have to show, not that there are N particles in the universe, but that anyone who accepts certain elementary principles of measurement must, if he is consistent, think there are. We have to express in mathematical symbolism what we think we are doing when we measure things; for if we had no conception of what we were doing, the results of the measurements would not persuade us to believe anything in particular. All our results are derived from the condition that the conceptual interpretation which we place on the results of measurement must be consistent with our conceptual interpretation of the process of measurement.If we play about with a pin and a meter standard, we do not become aware of any number in particular unless the standard has been graduated, or unless we use a process of displacement which we interpret as adding pin-extensions. The fact is that, although measurement is primarily a process involving four entities, the conceptual interpretation of measurement postulates in addition the existence (in the structure contemplated) as something referred to as Z. The existence of Z is the condition that makes graduation an exact concept. In the actual universe there exists a basis which is uniform to a very high approximation, and this serves for almost all purposes; but to the much higher approximation required in the calculation of N the ideal exact basis of uniformity does not exist. The finitude of N is, in fact, the cause of the failure of the approximation.It must be remembered that we are now working to what would ordinarily be considered a fantastically high approximation. For ordinary purposes a measurable has 16 eigenvalues; but under the super-magnification here employed (which is not content to overlook 1 part in 10E39) there is a fine structure which splits each of them into 16 components. (shrink)

This is the first, out of two papers, in which we identify all logics between C1 and S5 having the same theses without iterated modalities. All these logics canbe divided into certain groups. Each such group depends only on which of thefollowing formulas are theses of all logics from this group:,,, ⌜∨ ☐q⌝,and for any n > 0 a formula ⌜ ∨ ⌝, where has not the atom ‘q’, and and have no common atom. We generalize Pollack’s result from [12],where (...) he proved that all modal logics between S1 and S5 have the same theseswhich does not involve iterated modalities. (shrink)

Modal dependence logic was introduced recently by Väänänen. It enhances the basic modal language by an operator = (). For propositional variables p 1, . . . , p n , = (p 1, . . . , p n-1, p n ) intuitively states that the value of p n is determined by those of p 1, . . . , p n-1. Sevenster (J. Logic and Computation, 2009) showed that satisfiability for modal dependence logic is complete for nondeterministic (...) exponential time.In this paper we consider fragments of modal dependence logic obtained by restricting the set of allowed propositional connectives. We show that satisfiability for poor man’s dependence logic, the language consisting of formulas built from literals and dependence atoms using ${\wedge, \square, \lozenge}$ (i. e., disallowing disjunction), remains NEXPTIME-complete. If we only allow monotone formulas (without negation, but with disjunction), the complexity drops to PSPACE-completeness.We also extend Väänänen’s language by allowing classical disjunction besides dependence disjunction and show that the satisfiability problem remains NEXPTIME-complete. If we then disallow both negation and dependence disjunction, satisfiability is complete for the second level of the polynomial hierarchy. Additionally we consider the restriction of modal dependence logic where the length of each single dependence atom is bounded by a number that is fixed for the whole logic. We show that the satisfiability problem for this bounded arity dependence logic is PSPACE-complete and that the complexity drops to the third level of the polynomial hierarchy if we then disallow disjunction.In this way we completely classify the computational complexity of the satisfiability problem for all restrictions of propositional and dependence operators considered by Väänänen and Sevenster. (shrink)

Fundamental Theory has been called an "unfinished symphony" and "a challenge to the musicians among natural philosophers of the future". This book, written in 1944 but left unfinished because Eddington died too soon, proved to be his final effort at a vision for harmonization of quantum physics and relativity. The work is less connected and internally integrated than 'Protons and Electrons' while representing a later point in the author's thought arc. The really interested student should read both books together.The physical (...) and mathematical reasoning are very deep, but it is possible to enjoy much of the flavor of the book even without following everything. The tidbits given below illustrate Eddington's beautiful and mellifluous English style. This edition contains a clickable table of contents and some interesting illustrations.WARNING: Due to the complexity of the mathematical typesetting, the only way to reproduce this book has been as a series of scanned page images. We believe this work is scientifically and culturally important, and despite a few imperfections and the inevitably small print, have brought it back into print as part of our continuing commitment to the preservation of Eddington's work. On a portable electronic reader the pages come out pretty small, but they are legible. On a desktop computer running the Amazon app, they are perfectly fine. We appreciate your understanding, and hope you enjoy this valuable book.TIDBITS:The number of protons and electrons in the universe would, in itself, be merely a matter of idle curiosity. But N has a more general significance as a fundamental constant which enters into many physical formulae. Its special interpretation as the number of particles in the universe arises in the following way. If we consider a distribution of hydrogen in equilibrium at zero temperature, the presence of the matter produces a curvature of space, and the curvature causes the space to close when the number of particles contained in it reaches a certain total; that number is N. The present investigation seeks to determine N directly from the principles of measurement. We have to show, not that there are N particles in the universe, but that anyone who accepts certain elementary principles of measurement must, if he is consistent, think there are. We have to express in mathematical symbolism what we think we are doing when we measure things; for if we had no conception of what we were doing, the results of the measurements would not persuade us to believe anything in particular. All our results are derived from the condition that the conceptual interpretation which we place on the results of measurement must be consistent with our conceptual interpretation of the process of measurement.If we play about with a pin and a meter standard, we do not become aware of any number in particular unless the standard has been graduated, or unless we use a process of displacement which we interpret as adding pin-extensions. The fact is that, although measurement is primarily a process involving four entities, the conceptual interpretation of measurement postulates in addition the existence (in the structure contemplated) as something referred to as Z. The existence of Z is the condition that makes graduation an exact concept. In the actual universe there exists a basis which is uniform to a very high approximation, and this serves for almost all purposes; but to the much higher approximation required in the calculation of N the ideal exact basis of uniformity does not exist. The finitude of N is, in fact, the cause of the failure of the approximation.It must be remembered that we are now working to what would ordinarily be considered a fantastically high approximation. For ordinary purposes a measurable has 16 eigenvalues; but under the super-magnification here employed (which is not content to overlook 1 part in 10E39) there is a fine structure which splits each of them into 16 components. (shrink)

Given an intermediate prepositional logic L, denote by L –d its disjuctionless fragment. We introduce an infinite sequence {J n}n1 of propositional formulas, and prove:(1)For any L: L –d =I –d (I=intuitionistic logic) if and only if J n L for every n 1.

In [15], [16] G. Kreisel introduced the no-counterexample interpretation (n.c.i.) of Peano arithmetic. In particular he proved, using a complicated ε-substitution method (due to W. Ackermann), that for every theorem A (A prenex) of first-order Peano arithmetic PA one can find ordinal recursive functionals Φ A of order type 0 which realize the Herbrand normal form A H of A. Subsequently more perspicuous proofs of this fact via functional interpretation (combined with normalization) and cut-elimination were found. These proofs however do (...) not carry out the no-counterexample interpretation as a local proof interpretation and don't respect the modus ponens on the level of the no-counterexample interpretation of formulas A and A → B. Closely related to this phenomenon is the fact that both proofs do not establish the condition (δ) and--at least not constructively-- (γ) which are part of the definition of an 'interpretation of a formal system' as formulated in [15]. In this paper we determine the complexity of the no-counterexample interpretation of the modus ponens rule for (i) PA-provable sentences, (ii) for arbitrary sentences A, B ∈ L(PA) uniformly in functionals satisfying the no-counterexample interpretation of (prenex normal forms of) A and A → B, and (iii) for arbitrary A, B ∈ L(PA) pointwise in given α( 0 ) -recursive functionals satisfying the no-counterexample interpretation of A and A → B. This yields in particular perspicuous proofs of new uniform versions of the conditions (γ), (δ). Finally we discuss a variant of the concept of an interpretation presented in [17] and show that it is incomparable with the concept studied in [15], [16]. In particular we show that the no-counterexample interpretation of PA n by α( n (ω))-recursive functionals (n ≥ 1) is an interpretation in the sense of [17] but not in the sense of [15] since it violates the condition (δ). (shrink)

A definition is given for formulae $A_1,\ldots,A_n$ in some theory $T$ which is formalized in a propositional calculus $S$ to be (in)dependent with respect to $S$. It is shown that, for intuitionistic propositional logic $\mathbf{IPC}$, dependency (with respect to $\mathbf{IPC}$ itself) is decidable. This is an almost immediate consequence of Pitts' uniform interpolation theorem for $\mathbf{IPC}$. A reasonably simple infinite sequence of $\mathbf{IPC}$-formulae $F_n(p, q)$ is given such that $\mathbf{IPC}$-formulae $A$ and $B$ are dependent if and only if at least (...) on the $F_n(A, B)$ is provable. (shrink)

This paper presents an algebraic approach of some many-valued generalizations of modal logic. The starting point is the definition of the [0, 1]-valued Kripke models, where [0, 1] denotes the well known MV-algebra. Two types of structures are used to define validity of formulas: the class of frames and the class of Ł n -valued frames. The latter structures are frames in which we specify in each world u the set (a subalgebra of Ł n ) of the allowed truth (...) values of the formulas in u. We apply and develop algebraic tools (namely, canonical and strong canonical extensions) to generate complete modal n + 1-valued logics and we obtain many-valued counterparts of Shalqvist canonicity result. (shrink)

Computability theorists have introduced multiple hierarchies to measure the complexity of sets of natural numbers. The Kleene Hierarchy classifies sets according to the first-order complexity of their defining formulas. The Ershov Hierarchy classifies Δ20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varDelta ^0_2$$\end{document} sets with respect to the number of mistakes that are needed to approximate them. Biacino and Gerla extended the Kleene Hierarchy to the realm of fuzzy sets, whose membership functions range in a complete lattice L. In (...) this paper, we combine the Ershov Hierarchy and fuzzy set theory, by introducing and investigating the Fuzzy Ershov Hierarchy. In particular, we focus on the fuzzy n-c.e. sets which form the finite levels of this hierarchy. Intuitively, a fuzzy set is n-c.e. if its membership function can be approximated by changing monotonicity at most n-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n-1$$\end{document} times. We prove that the Fuzzy Ershov Hierarchy does not collapse; that, in analogy with the classical case, each fuzzy n-c.e. set can be represented as a Boolean combination of fuzzy c.e. sets; but that, contrary to the classical case, the Fuzzy Ershov Hierarchy does not exhaust the class of all Δ20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varDelta ^0_2$$\end{document} fuzzy sets. (shrink)

We consider fragments of uniform reflection for formulas in the analytic hierarchy over theories of second order arithmetic. The main result is that for any second order arithmetic theory $T_0$ extending $\mathsf {RCA}_0$ and axiomatizable by a $\Pi ^1_{k+2}$ sentence, and for any $n\geq k+1$, $$\begin{align*}T_0+ \mathrm{RFN}_{\varPi^1_{n+2}} \ = \ T_0 + \mathrm{TI}_{\varPi^1_n}, \end{align*}$$ $$\begin{align*}T_0+ \mathrm{RFN}_{\varSigma^1_{n+1}} \ = \ T_0+ \mathrm{TI}_{\varPi^1_n}^{-}, \end{align*}$$ where T is $T_0$ augmented with full induction, and $\mathrm {TI}_{\varPi ^1_n}^{-}$ denotes the schema of transfinite induction up (...) to $\varepsilon _0$ for $\varPi ^1_n$ formulas without set parameters. (shrink)

We prove, for each 4⩽ n ω , that S Ra CA n+1 cannot be defined, using only finitely many first-order axioms, relative to S Ra CA n . The construction also shows that for 5⩽n S Ra CA n is not finitely axiomatisable over RA n , and that for 3⩽m S Nr m CA n+1 is not finitely axiomatisable over S Nr m CA n . In consequence, for a certain standard n -variable first-order proof system ⊢ m (...) , n of m -variable formulas, there is no finite set of m -variable schemata whose m -variable instances, when added to ⊢ m , n as axioms, yield ⊢ m , n +1. (shrink)

In the first section of this paper we show that i Π1 ≡ W⌝⌝lΠ1 and that a Kripke model which decides bounded formulas forces iΠ1 if and only if the union of the worlds in any path in it satisflies IΠ1. In particular, the union of the worlds in any path of a Kripke model of HA models IΠ1. In the second section of the paper, we show that for equivalence of forcing and satisfaction of Πm-formulas in a linear Kripke (...) model deciding Δ0-formulas it is necessary and sufficient that the model be Σm-elementary. This implies that if a linear Kripke model forces PEMprenex, then it forces PEM. We also show that, for each n ≥ 1, iΦn does not prove ℋ(IΠn's are Burr's fragments of HA. (shrink)

We consider the well-known provability logic GLP. We prove that the GLP-provability problem for polymodal formulas without variables is PSPACE-complete. For a number n, let L0n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L^{n}_0}$$\end{document} denote the class of all polymodal variable-free formulas without modalities ⟨n⟩,⟨n+1⟩,...\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\langle n \rangle,\langle n+1\rangle,...}$$\end{document}. We show that, for every number n, the GLP-provability problem for formulas from L0n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L^{n}_0}$$\end{document} (...) is in PTIME. (shrink)

Let L ω ∞ω be the infinitary language obtained from the first-order language of graphs by closure under conjunctions and disjunctions of arbitrary sets of formulas, provided only finitely many distinct variables occur among the formulas. Let p(n) be the edge probability of the random graph on n vertices. It is shown that if p(n) ≪ n -1 satisfies certain simple conditions on its growth rate, then for every σ∈ L ω ∞ω , the probability that σ holds for the (...) random graph on n vertices converges. In fact, if $p(n) = n^{-\alpha}, \alpha > 1$ , then the probability is either smaller than 2 -n d for some $d > 0$ , or it is asymptotic to cn -d for some $c > 0, d \geq 0$ . Results on the difficulty of computing the asymptotic probability are given. (shrink)

IΣ n andBΣ n are well known fragments of first-order arithmetic with induction and collection forΣ n formulas respectively;IΣ n 0 andBΣ n 0 are their second-order counterparts. RCA0 is the well known fragment of second-order arithmetic with recursive comprehension;WKL 0 isRCA 0 plus weak König's lemma. We first strengthen Harrington's conservation result by showing thatWKL 0 +BΣ n 0 is Π 1 1 -conservative overRCA 0 +BΣ n 0 . Then we develop some model theory inWKL 0 and illustrate (...) the use of formalized model theory by giving a relatively simple proof of the fact thatIΣ 1 provesBΣ n+1 to be Π n+2-conservative overIΣ n . Finally, we present a proof-theoretic proof of the stronger fact that theΠ n+2 conservation result is provable already inIΔ 0 + superexp. ThusIΣ n+1 proves 1-Con (BΣ n+1) andIΔ 0 +superexp proves Con (IΣ n )↔Con(BΣ n+1). (shrink)

A pointwise version of the Howard-Bezem notion of hereditary majorization is introduced which has various advantages, and its relation to the usual notion of majorization is discussed. This pointwise majorization of primitive recursive functionals (in the sense of Gödel'sT as well as Kleene/Feferman's ) is applied to systems of intuitionistic and classical arithmetic (H andH c) in all finite types with full induction as well as to the corresponding systems with restricted inductionĤ↾ andĤ↾c.H and Ĥ↾ are closed under a generalized (...) fan-rule. For a restricted class of formulae this also holds forH c andĤ↾c.We give a new and very perspicuous proof that for each one can construct a functional such that $\tilde \Phi \alpha $ is a modulus of uniform continuity for Φ on {β1∣∧n(βn≦αn)}. Such a modulus can also be obtained by majorizing any modulus of pointwise continuity for Φ.The type structure ℳ of all pointwise majorizable set-theoretical functionals of finite type is used to give a short proof that quantifier-free “choice” with uniqueness (AC!)1,0-qf. is not provable within classical arithmetic in all finite types plus comprehension [given by the schema (C)ϱ:∨y 0ϱ∧x ϱ(yx=0⇔A(x)) for arbitraryA], dependent ω-choice and bounded choice. Furthermore ℳ separates several μ-operators. (shrink)