The Paradox of the Knower was originally presented by Kaplan and Montague [26] as a puzzle about the everyday notion of knowledge in the face of self-reference. The paradox shows that any theory extending Robinson arithmetic with a predicate K satisfying the factivity axiom K → A as well as a few other epistemically plausible principles is inconsistent. After surveying the background of the paradox, we will focus on a recent debate about the role of epistemic closure principles in the (...) Knower. We will suggest this debate sheds new light on the concept of knowledge which is at issue in the paradox – i.e. is it a “thin” notion divorced from concepts such as evidence or justification, or is it a “thick” notion more closely resembling mathematical provability? We will argue that a number of features of the paradox suggest that the latter option is more plausible. Along the way, we will provide a reconstruction of the paradox using a quantified extension of Artemovʼs [2] Logic of Proofs, as well as a series of results linking the original formulation of the paradox to reflection principles for formal arithmetic. On this basis, we will argue that while the Knower can be understood to motivate a distinction between levels of knowledge, it does not provide a rationale for recognizing a uniform hierarchy of knowledge predicates in the manner suggested by Anderson. (shrink)

We transform the proof of the second incompleteness theorem given in [3] to a proof-theoretic version, avoiding the use of the arithmetized completeness theorem. We give also new proofs of old results: The Arithmetical Hierarchy Theorem and Tarski's Theorem on undefinability of truth; the proofs in which the construction of a sentence by means of diagonalization lemma is not needed.

A variety of projects in proof theory of relevance to the philosophy of mathematics are surveyed, including Gödel's incompleteness theorems, conservation results, independence results, ordinal analysis, predicativity, reverse mathematics, speed-up results, and provability logics.

I had the pleasure of renewing my acquaintance with Per Lindström at the meeting of the Seventh Scandinavian Logic Symposium, held in Uppsala in August 1996. There at lunch one day, Per said he had long been curious about the development of some of the ideas in my paper [1960] on the arithmetization of metamathematics. In particular, I had used the construction of a non-standard definition !* of the set of axioms of P (Peano Arithmetic) to show that P + (...) {¬ Con!} is interpretable in P, where ! is a standard definition of the axioms of P and Con! expresses the consistency of P via that presentation. Per pointed out that there is a simple “two-line” proof of this interpretability result which does not require the use of such formulas as !*, and he wondered whether I had been aware of that. In fact, his proof had never occurred to me, and if it had at the time, it is possible I would never have been led to the use of non-natural definitions. Per regarded this as a happy accident, since subsequent work by him and others on interpretability made essential use of such definitions. In our conversation, I enlarged a bit on the background to my work on arithmetization, and when I was invited to contribute to this special issue of Theoria dedicated to Lindström, it seemed a natural choice to use the occasion to fill out the story. One caveat, though: the following is drawn largely from memory, not always reliable, supplemented by consultation of the 1960 paper and the 1957 dissertation from which it was drawn. (shrink)

Øystein Linnebo has recently shown that the existence of successors cannot be proven in predicative Frege arithmetic, using Frege’s definitions of arithmetical notions. By contrast, it is shown here that the existence of successor can be proven in ramified predicative Frege arithmetic.

Is a logicist bound to the claim that as a matter of analytic truth there is an actual infinity of objects? If Hume’s Principle is analytic then in the standard setting the answer appears to be yes. Hodes’s work pointed to a way out by offering a modal picture in which only a potential infinity was posited. However, this project was abandoned due to apparent failures of cross-world predication. We re-explore this idea and discover that in the setting of the (...) potential infinite one can interpret first-order Peano arithmetic, but not second-order Peano arithmetic. We conclude that in order for the logicist to weaken the metaphysically loaded claim of necessary actual infinities, they must also weaken the mathematics they recover. (shrink)

In this multi-disciplinary investigation we show how an evidence-based perspective of quantification---in terms of algorithmic verifiability and algorithmic computability---admits evidence-based definitions of well-definedness and effective computability, which yield two unarguably constructive interpretations of the first-order Peano Arithmetic PA---over the structure N of the natural numbers---that are complementary, not contradictory. The first yields the weak, standard, interpretation of PA over N, which is well-defined with respect to assignments of algorithmically verifiable Tarskian truth values to the formulas of PA under the interpretation. (...) The second yields a strong, finitary, interpretation of PA over N, which is well-defined with respect to assignments of algorithmically computable Tarskian truth values to the formulas of PA under the interpretation. We situate our investigation within a broad analysis of quantification vis a vis: * Hilbert's epsilon-calculus * Goedel's omega-consistency * The Law of the Excluded Middle * Hilbert's omega-Rule * An Algorithmic omega-Rule * Gentzen's Rule of Infinite Induction * Rosser's Rule C * Markov's Principle * The Church-Turing Thesis * Aristotle's particularisation * Wittgenstein's perspective of constructive mathematics * An evidence-based perspective of quantification. By showing how these are formally inter-related, we highlight the fragility of both the persisting, theistic, classical/Platonic interpretation of quantification grounded in Hilbert's epsilon-calculus; and the persisting, atheistic, constructive/Intuitionistic interpretation of quantification rooted in Brouwer's belief that the Law of the Excluded Middle is non-finitary. We then consider some consequences for mathematics, mathematics education, philosophy, and the natural sciences, of an agnostic, evidence-based, finitary interpretation of quantification that challenges classical paradigms in all these disciplines. (shrink)

We show how removing faith-based beliefs in current philosophies of classical and constructive mathematics admits formal, evidence-based, definitions of constructive mathematics; of a constructively well-defined logic of a formal mathematical language; and of a constructively well-defined model of such a language. -/- We argue that, from an evidence-based perspective, classical approaches which follow Hilbert's formal definitions of quantification can be labelled `theistic'; whilst constructive approaches based on Brouwer's philosophy of Intuitionism can be labelled `atheistic'. -/- We then adopt what may (...) be labelled a finitary, evidence-based, `agnostic' perspective and argue that Brouwerian atheism is merely a restricted perspective within the finitary agnostic perspective, whilst Hilbertian theism contradicts the finitary agnostic perspective. -/- We then consider the argument that Tarski's classic definitions permit an intelligence---whether human or mechanistic---to admit finitary, evidence-based, definitions of the satisfaction and truth of the atomic formulas of the first-order Peano Arithmetic PA over the domain N of the natural numbers in two, hitherto unsuspected and essentially different, ways. -/- We show that the two definitions correspond to two distinctly different---not necessarily evidence-based but complementary---assignments of satisfaction and truth to the compound formulas of PA over N. -/- We further show that the PA axioms are true over N, and that the PA rules of inference preserve truth over N, under both the complementary interpretations; and conclude some unsuspected constructive consequences of such complementarity for the foundations of mathematics, logic, philosophy, and the physical sciences. -/- . (shrink)

By a classical result of Kotlarski, Krajewski and Lachlan, pathological satisfaction classes can be constructed for countable, recursively saturated models of Peano arithmetic. In this paper we consider the question of whether the pathology can be eliminated; we ask in effect what generalities involving the notion of truth can be obtained in a deflationary truth theory (a theory of truth which is conservative over its base). It is shown that the answer depends on the notion of pathology we adopt. It (...) turns out in particular that a certain natural closure condition imposed on a satisfaction class—namely, closure of truth under sentential proofs—generates a nonconservative extension of a syntactic base theory (Peano arithmetic). (shrink)

Rudolf Carnap’s mature work on the logical reconstruction of scientific theories consists of two components. The first is the elimination of the theoretical vocabulary of a theory in terms of its Ramsification. The second is the reintroduction of the theoretical terms through explicit definitions in a language containing an epsilon operator. This paper investigates Carnap’s epsilon-reconstruction of theories in the context of pure mathematics. The main objective here is twofold: first, to specify the epsilon logic underlying his suggested definition of (...) theoretical terms and a suitable choice semantics for it. Second, to analyze whether Carnap’s approach is compatible with a structuralist conception of mathematics. (shrink)

In the paper we investigate typed axiomatizations of the truth predicate in which the axioms of truth come with a built-in, minimal and self-sufficient machinery to talk about syntactic aspects of an arbitrary base theory. Expanding previous works of the author and building on recent works of Albert Visser and Richard Heck, we give a precise characterization of these systems by investigating the strict relationships occurring between them, arithmetized model constructions in weak arithmetical systems and suitable set existence axioms. The (...) framework considered will give rise to some methodological remarks on the construction of truth theories and provide us with a privileged point of view to analyze the notion of truth arising from compositional principles in a typed setting. (shrink)

We define a property of substructures of models of arithmetic, that of being length-initial, and show that sharply bounded formulae are absolute between a model and its length-initial submodels. We use this to prove independence results for some weak fragments of bounded arithmetic by constructing appropriate models as length-initial submodels of some given model.

We show the non-arithmeticity of 1st order theories of lattices of Σ n sentences modulo provable equivalence in a formal theory, of diagonalizable algebras of a wider class of arithmetic theories than has been previously known, and of the lattice of degrees of interpretability over PA. The first two results are applications of Nies’ theorem on the non-arithmeticity of the 1st order theory of the lattice of r.e. ideals on any effectively dense r.e. Boolean algebra. The theorem on degrees of (...) interpretability relies on an adaptation of techniques leading to Nies’ theorem. (shrink)

In this paper we naturally define when a theory has bounded quantifier elimination, or is bounded model complete. We give several equivalent conditions for a theory to have each of these properties. These results provide simple proofs for some known results in the model theory of the bounded arithmetic theories like CPV and PV1. We use the mentioned results to obtain some independence results in the context of intuitionistic bounded arithmetic. We show that, if the intuitionistic theory of polynomial induction (...) on strict $\Pi_2^{b}$ formulas proves decidability of $\Sigma_1^b$ formulas, then P=NP. We also prove that, if the mentioned intuitionistic theory proves ${\rm LMIN}(\Sigma_{1}^{b})$ , then P=NP. (shrink)

Conservative subtheories of $${{R}^{1}_{2}}$$ and $${{S}^{1}_{2}}$$ are presented. For $${{S}^{1}_{2}}$$, a slight tightening of Jeřábek’s result (Math Logic Q 52(6):613–624, 2006) that $${T^{0}_{2} \preceq_{\forall \Sigma^{b}_{1}}S^{1}_{2}}$$ is presented: It is shown that $${T^{0}_{2}}$$ can be axiomatised as BASIC together with induction on sharply bounded formulas of one alternation. Within this $${\forall\Sigma^{b}_{1}}$$ -theory, we define a $${\forall\Sigma^{b}_{0}}$$ -theory, $${T^{-1}_{2}}$$, for the $${\forall\Sigma^{b}_{0}}$$ -consequences of $${S^{1}_{2}}$$. We show $${T^{-1}_{2}}$$ is weak by showing it cannot $${\Sigma^{b}_{0}}$$ -define division by 3. We then consider what (...) would be the analogous $${\forall\hat\Sigma^{b}_{1}}$$ -conservative subtheory of $${R^{1}_{2}}$$ based on Pollett (Ann Pure Appl Logic 100:189–245, 1999. It is shown that this theory, $${{T}^{0,\left\{2^{(||\dot{id}||)}\right\}}_{2}}$$, also cannot $${\Sigma^{b}_{0}}$$ -define division by 3. On the other hand, we show that $${{S}^{0}_{2}+open_{\{||id||\}}}$$ -COMP is a $${\forall\hat\Sigma^{b}_{1}}$$ -conservative subtheory of $${R^{1}_{2}}$$. Finally, we give a refinement of Johannsen and Pollett (Logic Colloquium’ 98, 262–279, 2000) and show that $${\hat{C}^{0}_{2}}$$ is $${\forall\hat\Sigma^{b}_{1}}$$ -conservative over a theory based on open cl-comprehension. (shrink)

We investigate what happens when ‘truth’ is replaced with ‘provability’ in Yablo’s paradox. By diagonalization, appropriate sequences of sentences can be constructed. Such sequences contain no sentence decided by the background consistent and sufficiently strong arithmetical theory. If the provability predicate satisfies the derivability conditions, each such sentence is provably equivalent to the consistency statement and to the Gödel sentence. Thus each two such sentences are provably equivalent to each other. The same holds for the arithmetization of the existential Yablo (...) paradox. We also look at a formulation which employs Rosser’s provability predicate. (shrink)

In this article, I examine the ramified-type theory set out in the first edition of Russell and Whitehead's Principia Mathematica. My starting point is the ‘no loss of generality’ problem: Russell, in the Introduction (Russell, B. and Whitehead, A. N. 1910. Principia Mathematica, Volume I, 1st ed., Cambridge: Cambridge University Press, pp. 53–54), says that one can account for all propositional functions using predicative variables only, that is, dismissing non-predicative variables. That claim is not self-evident at all, hence a problem. (...) The purpose of this article is to clarify Russell's claim and to solve the ‘no loss of generality’ problem. I first remark that the hierarchy of propositional functions calls for a fine-grained conception of ramified types as propositional forms (‘ramif-types’). Then, comparing different important interpretations of Principia’s theory of types, I consider the question as to whether Principia allows for non-predicative propositional functions and variables thereof. I explain how the distinction between the formal system of the theory, on the one hand, and its realizations in different epistemic universes, on the other hand, makes it possible to give us a more satisfactory answer to that question than those given by previous commentators, and, as a consequence, to solve the ‘no loss of generality’ problem. The solution consists in a substitutional semantics for non-predicative variables and non-predicative complex terms, based on an epistemic understanding of the order component of ramified types. The rest of the article then develops that epistemic understanding, adding an original epistemic model theory to the formal system of types. This shows that the universality sought by Russell for logic does not preclude semantical considerations, contrary to what van Heijenoort and Hintikka have claimed. (shrink)

Hilbert developed his famous finitist point of view in several essays in the 1920s. In this paper, we discuss various extensions of it, with particular emphasis on those suggested by Hilbert and Bernays in Grundlagen der Mathematik (vol. I 1934, vol. II 1939). The paper is in three sections. The first deals with Hilbert's introduction of a restricted ? -rule in his 1931 paper ?Die Grundlegung der elementaren Zahlenlehre?. The main question we discuss here is whether the finitist (meta-)mathematician would (...) be entitled to accept this rule as a finitary rule of inference. In the second section, we assess the strength of finitist metamathematics in Hilbert and Bernays 1934. The third and final section is devoted to the second volume of Grundlagen der Mathematik. For preparatory reasons, we first discuss Gentzen's proposal of expanding the range of what can be admitted as finitary in his esssay ?Die Widerspruchsfreiheit der reinen Zahlentheorie? (1936). As to Hilbert and Bernays 1939, we end on a ?critical? note: however considerable the impact of this work may have been on subsequent developments in metamathematics, there can be no doubt that in it the ideals of Hilbert's original finitism have fallen victim to sheer proof-theoretic pragmatism. (shrink)

This is a critical analysis of the first part of Go¨del’s 1951 Gibbs lecture on certain philosophical consequences of the incompleteness theorems. Go¨del’s discussion is framed in terms of a distinction between objective mathematics and subjective mathematics, according to which the former consists of the truths of mathematics in an absolute sense, and the latter consists of all humanly demonstrable truths. The question is whether these coincide; if they do, no formal axiomatic system (or Turing machine) can comprehend the mathematizing (...) potentialities of human thought, and, if not, there are absolutely unsolvable mathematical problems of diophantine form. (shrink)

The existence of a close connection between results on axiomatic truth and the analysis of truth-theoretic deflationism is nowadays widely recognized. The first attempt to make such link precise can be traced back to the so-called conservativeness argument due to Leon Horsten, Stewart Shapiro and Jeffrey Ketland: by employing standard Gödelian phenomena, they concluded that deflationism is untenable as any adequate theory of truth leads to consequences that were not achievable by the base theory alone. In the paper I highlight, (...) as Shapiro and Ketland, the irreducible nature of truth axioms with respect to their base theories. But, I argue, this does not immediately delineate a notion of truth playing a substantial role in philosophical or scientific explanations. I first offer a refinement of Hartry Field’s reaction to the conservativeness argument by distinguishing between metatheoretic and object-theoretic consequences of the theory of truth and address some possible rejoinders. In the resulting picture, truth is an irreducible tool for metatheoretic ascent. How robust is this characterizaton? I test it by considering: a recent example, due to Leon Horsten, of the alleged explanatory role played by the truth predicate in the derivation of Fitch’s paradox; an essential weakening of theories of truth analyzed in the first part of the paper. (shrink)

Ajtai’s completeness theorem roughly states that a countable structure A coded in a model of arithmetic can be end-extended and expanded to a model of a given theory G if and only if a contradiction cannot be derived by a proof from G plus the diagram of A, provided that the proof is definable in A and contains only formulas of a standard length. The existence of such model extensions is closely related to questions in complexity theory. In this paper (...) we give a new proof of Ajtai’s theorem using basic techniques of model theory. (shrink)

A theory T is trustworthy iff, whenever a theory U is interpretable in T, then it is faithfully interpretable. In this paper we give a characterization of trustworthiness. We provide a simple proof of Friedman’s Theorem that finitely axiomatized, sequential, consistent theories are trustworthy. We provide an example of a theory whose schematic predicate logic is complete Π20.

We present a decision procedure for the ∀∃ theory of the lattice of Σ1 sentences of Peano Arithmetic.

This paper engages the question ‘Does the consistency of a set of axioms entail the existence of a model in which they are satisfied?’ within the frame of the Frege-Hilbert controversy. The question is related historically to the formulation, proof and reception of Gödel’s Completeness Theorem. Tools from mathematical logic are then used to argue that there are precise senses in which Frege was correct to maintain that demonstrating consistency is as difficult as it can be, but also in which (...) Hilbert was correct to maintain that demonstrating existence given consistency is as easy as it can be. (shrink)

A common objection to hierarchical approaches to truth is that they fragment the concept of truth. This paper defends hierarchical approaches in general against the objection of fragmentation. It argues that the fragmentation required is familiar and unprob-lematic, via a comparison with mathematical proof. Furthermore, it offers an explanation of the source and nature of the fragmentation of truth. Fragmentation arises because the concept exhibits a kind of failure of closure under reflection. This paper offers a more precise characterization of (...) the reflection involved, first in the setting of formal theories of truth, and then in a more general setting. (shrink)

It is well known that Tarski proved a result which can be stated roughly as: no sufficiently rich, consistent, classical language can contain its own truth definition. Tarski's way around this problem is to deal with two languages at a time, an object language for which we are defining truth and a metalanguage in which the definition occurs. An obvious question then is: under what conditions can we construct a definition of truth for a given object language. Tarski claims that (...) it is necessary and sufficient that the metalanguage be "essentially richer". Our contention, put bluntly, is that this claim deserves more scrutiny from philosophers than it usually gets and in fact is false unless "essentially richer" means nothing else than "sufficient to contain a truth definition for the object language.". (shrink)

This paper develops a classical model for our ordinary use of the truth predicate (1) that is able to address the liar's paradox and (2) that satisfies a very strong version of deflationism. Since the model is a classical in the sense that it has no truth value gaps, the model is able to address Tarski's indictment of our ordinary use of the predicate as inconsistent. Moreover, since it is able to address the liar's paradox, it responds to arguments against (...) deflationism based upon that paradox alone. The model is based upon a notion of the complexity of propositions that a fixed set of speakers might express. A context-sensitive definition of the truth predicate is then provided based upon a class of possible worlds defined in terms of these speakers. Reasonable constraints on the memories and lifetimes of ordinary speakers are used to limit the set of propositions that they might express so that deflationist requirements are satisfied. (shrink)

This paper investigates the status of the fragments of Peano Arithmetic obtained by restricting induction, collection and least number axiom schemes to formulas which are $${\Delta_1}$$ provably in an arithmetic theory T. In particular, we determine the provably total computable functions of this kind of theories. As an application, we obtain a reduction of the problem whether $${I\Delta_0 + \neg \mathit{exp}}$$ implies $${B\Sigma_1}$$ to a purely recursion-theoretic question.

In this paper, we characterize the strength of the predicative Frege hierarchy, , introduced by John Burgess in his book [J. Burgess, Fixing frege, in: Princeton Monographs in Philosophy, Princeton University Press, Princeton, 2005]. We show that and are mutually interpretable. It follows that is mutually interpretable with Q. This fact was proved earlier by Mihai Ganea in [M. Ganea, Burgess’ PV is Robinson’s Q, The Journal of Symbolic Logic 72 619–624] using a different proof. Another consequence of the our (...) main result is that is mutually interpretable with Kalmar Arithmetic . The fact that interprets EA was proved earlier by Burgess. We provide a different proof. Each of the theories is finitely axiomatizable. Our main result implies that the whole hierarchy taken together, , is not finitely axiomatizable. What is more: no theory that is mutually locally interpretable with is finitely axiomatizable. (shrink)

This paper presents a new method - which does not rely on the cut-elimination theorem - for characterizing the provably total functions of certain intuitionistic subsystems of arithmetic. The new method hinges on a realizability argument within an infinitary language. We illustrate the method for the intuitionistic counterpart of Buss's theory Smath image, and we briefly sketch it for the other levels of bounded arithmetic and for the theory IΣ1.

We study problems of Clote and Paris, concerning the existence of end extensions of models of Σ n -collection. We continue the study of the notion of ‘Γ-fullness’, begun by Wilkie and Paris (Logic, Methodology and Philosophy of Science VIII (Moscow, 1987). Stud. Logic Found. Math., vol. 126, pp. 143–161. North- Holland, Amsterdam, 1989) and introduce and study a generalization of it, to be used in connection with the existence of Σ n -elementary end extensions (instead of plain end extensions). (...) We obtain (a) alternative proofs of results (Adamowicz in Fund. Math. 136, 133–145, 1990) and (Wilkie and Paris in Logic, Methodology and Philosophy of Science VIII (Moscow, 1987). Stud. Logic Found. Math., vol. 126, pp. 143–161. North-Holland, Amsterdam, 1989) related to the problem of Paris and (b) a partial solution to the problem of Clote. (shrink)

In this paper we will investigate different axiomatic theories of truth that are minimal in some sense. One criterion for minimality will be conservativity over Peano Arithmetic. We will then give a more fine-grained characterization by investigating some interpretability relations. We will show that disquotational theories of truth, as well as compositional theories of truth with restricted induction are relatively interpretable in Peano Arithmetic. Furthermore, we will give an example of a theory of truth that is a conservative extension of (...) Peano Arithmetic but not interpretable in it. We will then use stricter versions of interpretations to compare weak theories of truth to subsystems of second-order arithmetic. (shrink)

ABSTRACT We use Gödel’s incompleteness theorems as a case study for investigating mathematical depth. We examine the philosophical question of what the depth of Gödel’s incompleteness theorems consists in. We focus on the methodological study of the depth of Gödel’s incompleteness theorems, and propose three criteria to account for the depth of the incompleteness theorems: influence, fruitfulness, and unity. Finally, we give some explanations for our account of the depth of Gödel’s incompleteness theorems.

Truth is often considered to be a logico-linguistic tool for expressing indirect endorsements and infinite conjunctions. In this article, I will point out another logico-linguistic function of truth: to enable and validate what I call a blind argument, namely, an argument that involves indirectly endorsed statements. Admitting this function among the logico-linguistic functions of truth has some interesting consequences. In particular, it yields a new type of so-called conservativeness argument, which poses a new type of threat to deflationism about truth.

Let Iπ2 denote the fragment of Peano Arithmetic obtained by restricting the induction scheme to parameter free Π2Π2 formulas. Answering a question of R. Kaye, L. Beklemishev showed that the provably total computable functions of Iπ2 are, precisely, the primitive recursive ones. In this work we give a new proof of this fact through an analysis of certain local variants of induction principles closely related to Iπ2. In this way, we obtain a more direct answer to Kaye's question, avoiding the (...) metamathematical machinery needed for Beklemishev's original proof.Our methods are model-theoretic and allow for a general study of Iπn+1 for all n≥0n≥0. In particular, we derive a new conservation result for these theories, namely that Iπn+1 is πn+2 -conservative over IΣn for each n≥1n≥1. (shrink)

We show that versions of the prime number theorem as well as equivalent statements hold in an arbitrary model ofIΔ 0+exp.

The ‘Turing barrier’ is an evocative image for 0′, the degree of the unsolvability of the halting problem for Turing machines—equivalently, of the undecidability of Peano Arithmetic. The ‘barrier’ metaphor conveys the idea that effective computability is impaired by restrictions that could be removed by infinite methods. Assuming that the undecidability of PA is essentially depending on the finite nature of its computational means, decidability would be restored by the ω-rule. Hypercomputation, the hypothetical realization of infinitary machines through relativistic and (...) quantium models, would thus be capable of breaking the Turing barrier. The speculation is unfounded in principle, apart from issues of physical realizability: The point is that the ω-rule does not cope with all objects entailing the undecidability of PA. As long as the system is consistent, the computational boundary can be established by paradox-like constructions, such as Gödel-Rosser’s and Yablo’s, which are refractory to infinite induction, and do stand as the barrier’s buttresses. (shrink)

The paper presents a particular example of a formula which is a standard tautology of Łukasiewicz but not its general tautology; an example of a model in which the formula is not true is explicitly constructed. Analogous example of a formula and its model is given for product logic.

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.

It is demonstrated that we can represent Euler's φ-function by means of a Δ0-formula in such a way that the theory IΔ 0 proves the recursion equations that are characteristic for this function.

We show that that every countable model of PA has a conservative extension M with a subset Y such that a certain Σ1(Y)-formula defines in M a subset which is not r. e. relative to Y.

In this paper we deal with some new axiom schemes for Peano's Arithmetic that can substitute the classical induction, least-element, collection and strong collection schemes in the description of PA.

Continuing the earlier research from [T. Bigorajska, H. Kotlarski, Partitioning α-large sets: some lower bounds, Trans. Amer. Math. Soc. 358 4981–5001] we show that for the price of multiplying the number of parts by 3 we may construct partitions all of whose homogeneous sets are much smaller than in [T. Bigorajska, H. Kotlarski, Partitioning α-large sets: some lower bounds, Trans. Amer. Math. Soc. 358 4981–5001]. We also show that the Paris–Harrington independent statement remains unprovable if the number of colors is (...) restricted to 2, in fact, the statement is unprovable in IΣb. Other results concern some lower bounds for partitions of pairs. (shrink)