The goals of reduction andreductionism in the natural sciences are mainly explanatoryin character, while those inmathematics are primarily foundational.In contrast to global reductionistprograms which aim to reduce all ofmathematics to one supposedly ``universal'' system or foundational scheme, reductive proof theory pursues local reductions of one formal system to another which is more justified in some sense. In this direction, two specific rationales have been proposed as aims for reductive proof theory, the constructive consistency-proof rationale and the foundational reduction rationale. However, (...) recent advances in proof theory force one to consider the viability of these rationales. Despite the genuine problems of foundational significance raised by that work, the paper concludes with a defense of reductive proof theory at a minimum as one of the principal means to lay out what rests on what in mathematics. In an extensive appendix to the paper,various reduction relations betweensystems are explained and compared, and arguments against proof-theoretic reduction as a ``good'' reducibilityrelation are taken up and rebutted. (shrink)

Although the recent emphasis on models in philosophy of science has been an important development, the consequence has been a shift away from more traditional notions of theory. Because the semantic view defines theories as families of models and because much of the literature on “scientific” modeling has emphasized various degrees of independence from theory, little attention has been paid to the role that theory has in articulating scientific knowledge. This paper is the beginning of what I hope will be (...) a redress of the imbalance. I begin with a discussion of some of the difficulties faced by various formulations of the semantic view not only with respect to their account of models but also with their definition of a theory. From there I go on to articulate reasons why a notion of theory is necessary for capturing the structure of scientific knowledge and how one might go about formulating such a notion in terms of different levels of representation and explanation. The context for my discussion is the BCS account of superconductivity, a `theory' that was, and still is, sometimes referred to as a `model'. BCS provides a nice focus for the discussion because it illuminates various features of the theory/model relationship that seem to require a robust notion of theory that is not easily captured by the semantic account. (shrink)

Gurevich and Shelah have shown that Peano Arithmetic cannot be interpreted in the monadic second-order theory of short chains (hence, in the monadic second-order theory of the real line). We will show here that it is consistent that the monadic second-order theory of no chain interprets Peano Arithmetic.

Though my ultimate concern is with issues in epistemology and metaphysics, let me phrase the central question I will pursue in terms evocative of philosophy of religion: What are the implications of our logic-in particular, of Cantor and G6del-for the possibility of omniscience?

We shall be concerned with two natural expansions of the quantifier-free ‘polynomial’ probability logic of Fagin et al. (A logic for reasoning about probabilities, Inform Comput, 1990; 87:78–128). One of these, denoted by ${\textsf{QPL}}^{\textrm{e}}$, is obtained by adding quantifiers over arbitrary events, and the other, denoted by $\underline{{\textsf{QPL}}}^{\textrm{e}}$, uses quantifiers over propositional formulas—or equivalently, over events expressible by such formulas. The earlier proofs of the complexity lower bound results for ${\textsf{QPL}}^{\textrm{e}}$ and $\underline{{\textsf{QPL}}}^{\textrm{e}}$ relied heavily on multiplication, and therefore on the (...) polynomiality of the basic parts. We shall obtain the same lower bounds for natural fragments of ${\textsf{QPL}}^{\textrm{e}}$ and $\underline{{\textsf{QPL}}}^{\textrm{e}}$ in which only linear combinations of a very special form are allowed. Also, it will be studied what happens if we add quantifiers over reals. (shrink)

This paper is concerned with a two-sorted probabilistic language, denoted by $\textsf{QPL}$, which contains quantifiers over events and over reals, and can be viewed as an elementary language for reasoning about probability spaces. The fragment of $\textsf{QPL}$ containing only quantifiers over reals is a variant of the well-known ‘polynomial’ language from Fagin et al. (1990, Inform. Comput., 87, 78–128). We shall prove that the $\textsf{QPL}$-theory of the Lebesgue measure on $\left [ 0, 1 \right ]$ is decidable, and moreover, all (...) atomless spaces have the same $\textsf{QPL}$-theory. Also, we shall introduce the notion of elementary invariant for $\textsf{QPL}$ and use it to translate the semantics for $\textsf{QPL}$ into the setting of elementary analysis. This will allow us to obtain further decidability results as well as to provide exact complexity upper bounds for a range of interesting undecidable theories. (shrink)

In this paper we study essential hereditary undecidability. Theories with this property are a convenient tool to prove undecidability of other theories. The paper develops the basic facts concerning essentially hereditary undecidability and provides salient examples, like a construction of essentially hereditarily undecidable theories due to Hanf and an example of a rather natural essentially hereditarily undecidable theory strictly below. We discuss the (non-)interaction of essential hereditary undecidability with recursive boolean isomorphism. We develop a reduction relation essential tolerance, or, in (...) the converse direction, lax interpretability that interacts in a good way with essential hereditary undecidability. We introduce the class of $$\Sigma ^0_1$$ Σ 1 0 -friendly theories and show that $$\Sigma ^0_1$$ Σ 1 0 -friendliness is sufficient but not necessary for essential hereditary undecidability. Finally, we adapt an argument due to Pakhomov, Murwanashyaka and Visser to show that there is no interpretability minimal essentially hereditarily undecidable theory. (shrink)

In this paper we examine various requirements on the formalisation choices under which self-reference can be adequately formalised in arithmetic. In particular, we study self-referential numberings, which immediately provide a strong notion of self-reference even for expressively weak languages. The results of this paper suggest that the question whether truly self-referential reasoning can be formalised in arithmetic is more sensitive to the underlying coding apparatus than usually believed. As a case study, we show how this sensitivity affects the formal study (...) of certain principles of self-referential truth. (shrink)

This is a paper for a special issue of Semiotic Studies devoted to Stanislaw Krajewski’s paper. This paper gives some supplementary notes to Krajewski’s on the Anti-Mechanist Arguments based on Gödel’s incompleteness theorem. In Section 3, we give some additional explanations to Section 4–6 in Krajewski’s and classify some misunderstandings of Gödel’s incompleteness theorem related to AntiMechanist Arguments. In Section 4 and 5, we give a more detailed discussion of Gödel’s Disjunctive Thesis, Gödel’s Undemonstrability of Consistency Thesis and the definability (...) of natural numbers as in Section 7–8 in Krajewski’s, describing how recent advances bear on these issues. (shrink)

What is the source of logical and mathematical truth? This book revitalizes conventionalism as an answer to this question. Conventionalism takes logical and mathematical truth to have their source in linguistic conventions. This was an extremely popular view in the early 20th century, but it was never worked out in detail and is now almost universally rejected in mainstream philosophical circles. Shadows of Syntax is the first book-length treatment and defense of a combined conventionalist theory of logic and mathematics. It (...) argues that our conventions, in the form of syntactic rules of language use, are perfectly suited to explain the truth, necessity, and a priority of logical and mathematical claims, as well as our logical and mathematical knowledge. (shrink)

Often philosophers, logicians, and mathematicians employ a notion of intended structure when talking about a branch of mathematics. In addition, we know that there are foundational mathematical theories that can find representatives for the objects of informal mathematics. In this paper, we examine how faithfully foundational theories can represent intended structures, and show that this question is closely linked to the decidability of the theory of the intended structure. We argue that this sheds light on the trade-off between expressive power (...) and meta-theoretic properties when comparing first-order and second-order logic. (shrink)

This paper explores the relationship borne by the traditional paradoxes of set theory and semantics to formal incompleteness phenomena. A central tool is the application of the Arithmetized Completeness Theorem to systems of second-order arithmetic and set theory in which various “paradoxical notions” for first-order languages can be formalized. I will first discuss the setting in which this result was originally presented by Hilbert & Bernays (1939) and also how it was later adapted by Kreisel (1950) and Wang (1955) in (...) order to obtain formal undecidability results. A generalization of this method will then be presented whereby Russell’s paradox, a variant of Mirimanoff’s paradox, the Liar, and the Grelling–Nelson paradox may be uniformly transformed into incompleteness theorems. Some additional observations are then framed relating these results to the unification of the set theoretic and semantic paradoxes, the intensionality of arithmetization (in the sense of Feferman, 1960), and axiomatic theories of truth. (shrink)

Intertheoretic relations are an important topic in the philosophy of science. However, since their classical discussion by Ernest Nagel, such relations have mostly been restricted to relations between pairs of theories in the natural sciences. This paper presents a case study of a new type of intertheoretic relation that is inspired by Montague’s analysis of the linguistic syntax-semantics relation. The paper develops a simple model of this relation. To motivate the adoption of our new model, we show that this model (...) extends the scope of application of the Nagelian models and that it shares the epistemological advantages of the Nagelian model. The latter is achieved in a Bayesian framework. (shrink)

This book illustrates the program of Logical-Informational Dynamics. Rational agents exploit the information available in the world in delicate ways, adopt a wide range of epistemic attitudes, and in that process, constantly change the world itself. Logical-Informational Dynamics is about logical systems putting such activities at center stage, focusing on the events by which we acquire information and change attitudes. Its contributions show many current logics of information and change at work, often in multi-agent settings where social behavior is essential, (...) and often stressing Johan van Benthem's pioneering work in establishing this program. However, this is not a Festschrift, but a rich tapestry for a field with a wealth of strands of its own. The reader will see the state of the art in such topics as information update, belief change, preference, learning over time, and strategic interaction in games. Moreover, no tight boundary has been enforced, and some chapters add more general mathematical or philosophical foundations or links to current trends in computer science. The theme of this book lies at the interface of many disciplines. Logic is the main methodology, but the various chapters cross easily between mathematics, computer science, philosophy, linguistics, cognitive and social sciences, while also ranging from pure theory to empirical work. Accordingly, the authors of this book represent a wide variety of original thinkers from different research communities. And their interconnected themes challenge at the same time how we think of logic, philosophy and computation. Thus, very much in line with van Benthem's work over many decades, the volume shows how all these disciplines form a natural unity in the perspective of dynamic logicians (broadly conceived) exploring their new themes today. And at the same time, in doing so, it offers a broader conception of logic with a certain grandeur, moving its horizons beyond the traditional study of consequence relations. (shrink)

This essay clarifies quantifier variance and uses it to provide a theory of indefinite extensibility that I call the variance theory of indefinite extensibility. The indefinite extensibility response to the set-theoretic paradoxes sees each argument for paradox as a demonstration that we have come to a different and more expansive understanding of ‘all sets’. But indefinite extensibility is philosophically puzzling: extant accounts are either metasemantically suspect in requiring mysterious mechanisms of domain expansion, or metaphysically suspect in requiring nonstandard assumptions about (...) mathematical objects. Happily, the view of quantifier meanings that underwrites quantifier variance can be used to provide an account of indefinite extensibility that is both metasemantically and metaphysically satisfying. Section 1 introduces the puzzle of indefinite extensibility; section 2 develops and clarifies the metasemantics of quantifier variance; section 3 solves section 1's puzzle of indefinite extensibility by applying section 2's account of quantifier meanings; and section 4 compares the theory developed in section 3 to several other theories in the literature. (shrink)

This dissertation argues that we have no good reason to accept any one theory of properties as correct. To show this, I present three possible bases for theory-choice in the properties debate: coherence, explanatory adequacy, and explanatory value. Then I argue that none of these bases resolve the underdetermination of our choice between theories of properties. First, I argue considerations about coherence cannot resolve the underdetermination, because no traditional theory of properties is obviously incoherent. Second, I argue considerations of explanatory (...) adequacy cannot resolve the underdetermination, because every traditional theory of properties lacks the theoretical resources to adequately explain resemblance, causal powers, and predication. However, these inadequacies are easily remedied with theoretical modifications. But this results in an overabundance of modified, but adequate, theories of properties. Third, I argue explanatory virtues cannot resolve the underdetermination, because we have no reason to think explanatory virtues make theories of properties more likely to be true. I reject the common argument that explanatory virtues are truth-conducive in theories of properties because they are truth-conducive in scientific theories. Since none of the three bases for theory choice can resolve the underdetermination, I conclude that we have no good reason to accept any one theory of properties as correct. Finally, I consider the possibility of choosing one theory over the others on pragmatic grounds. But I argue that pragmatic grounds cannot resolve the underdetermination either. Instead, I suggest we accept the view I call 'instrumental pluralism,' which allows practitioners to use whatever theory of properties they find useful. Adviser: Jennifer McKitrick. (shrink)

Prior Analytics by the Greek philosopher Aristotle and Laws of Thought by the English mathematician George Boole are the two most important surviving original logical works from before the advent of modern logic. This article has a single goal: to compare Aristotle's system with the system that Boole constructed over twenty-two centuries later intending to extend and perfect what Aristotle had started. This comparison merits an article itself. Accordingly, this article does not discuss many other historically and philosophically important aspects (...) of Boole's book, e.g. his confused attempt to apply differential calculus to logic, his misguided effort to make his system of ‘class logic’ serve as a kind of ‘truth-functional logic’, his now almost forgotten foray into probability theory, or his blindness to the fact that a truth-functional combination of equations that follows from a given truth-functional combination of equations need not follow truth-functionally. One of the main conclusions is that Boole's contribution widened logic and changed its nature to such an extent that he fully deserves to share with Aristotle the status of being a founding figure in logic. By setting forth in clear and systematic fashion the basic methods for establishing validity and for establishing invalidity, Aristotle became the founder of logic as formal epistemology. By making the first unmistakable steps toward opening logic to the study of ‘laws of thought’—tautologies and laws such as excluded middle and non-contradiction—Boole became the founder of logic as formal ontology.… using mathematical methods … has led to more knowledge about logic in one century than had been obtained from the death of Aristotle up to … when Boole's masterpiece was published.Paul Rosenbloom 1950. (shrink)

The rather unrestrained use of second-order logic in the neo-logicist program is critically examined. It is argued in some detail that it brings with it genuine set-theoretical existence assumptions and that the mathematical power that Hume’s Principle seems to provide, in the derivation of Frege’s Theorem, comes largely from the ‘logic’ assumed rather than from Hume’s Principle. It is shown that Hume’s Principle is in reality not stronger than the very weak Robinson Arithmetic Q. Consequently, only a few rudimentary facts (...) of arithmetic are logically derivable from Hume’s Principle. And that hardly counts as a vindication of logicism. (shrink)

Recently a number of works in meta-ontology have used a variant of J.H. Harris's collapse argument in the philosophy of logic as an argument against Eli Hirsch's quantifier variance. There have been several responses to the argument in the literature, but none of them have identified the central failing of the argument, viz., the argument has two readings: one on which it is sound but doesn't refute quantifier variance and another on which it is unsound. The central lesson I draw (...) is that arguments against quantifier variance must pay strict attention to issues of translation and interpretation. The paper also has a substantial appendix in which I prove the equivalence of plural mereological nihilism and standard first-order atomistic mereology; results of this kind are often appealed to in the literature on quantifier variance but without many details on the nature or proof of the result. (shrink)

The signature of the formal language of mereology contains only one binary predicate which stands for the relation “being a part of” and it has been strongly suggested that such a predicate must at least define a partial ordering. Mereological theories owe their origin to Leśniewski. However, some more recent authors, such as Simons as well as Casati and Varzi, have reformulated mereology in a way most logicians today are familiar with. It turns out that any theory which can be (...) formed by using the reformulated mereological axioms or axiom schemas is in a sense a subtheory of the elementary theory of Boolean algebras or of the theory of infinite atomic Boolean algebras. It is known that the theory of partial orderings is undecidable while the elementary theory of Boolean algebras and the theory of infinite atomic Boolean algebras are decidable. In this paper, I will look into the behaviors in terms of decidability of those mereological theories located in between. More precisely, I will give a comprehensive picture of the said issue by offering solutions to the open problems which I have raised in some of my papers published previously. (shrink)

This paper discusses the history of the confusion and controversies over whether the definition of consequence presented in the 11-page 1936 Tarski consequence-definition paper is based on a monistic fixed-universe framework?like Begriffsschrift and Principia Mathematica. Monistic fixed-universe frameworks, common in pre-WWII logic, keep the range of the individual variables fixed as the class of all individuals. The contrary alternative is that the definition is predicated on a pluralistic multiple-universe framework?like the 1931 Gödel incompleteness paper. A pluralistic multiple-universe framework recognizes multiple (...) universes of discourse serving as different ranges of the individual variables in different interpretations?as in post-WWII model theory. In the early 1960s, many logicians?mistakenly, as we show?held the ?contrary alternative? that Tarski 1936 had already adopted a Gödel-type, pluralistic, multiple-universe framework. We explain that Tarski had not yet shifted out of the monistic, Frege?Russell, fixed-universe paradigm. We further argue that between his Principia-influenced pre-WWII Warsaw period and his model-theoretic post-WWII Berkeley period, Tarski's philosophy underwent many other radical changes. (shrink)

In this paper I shall present some of the results I have obtained on modal theories which contain quantifiers for propositions. The paper is in two parts: in the first part I consider theories whose non-quantificational part is S5; in the second part I consider theories whose non-quantificational part is weaker than or not contained in S5. Unless otherwise stated, each theory has the same language L. This consists of a countable set V of propositional variables pl, pa, ... , (...) the operators v (or), ~ (not) and □ (necessarily), the universal quantifier (p), p a propositional variable, and brackets ( and ). The formulas of L are then defined in the usual way. (shrink)

This papers deals with the class of axiomatic theories of truth for semantically closed languages, where the theories do not allow for standard models; i.e., those theories cannot be interpreted as referring to the natural number codes of sentences only (for an overview of axiomatic theories of truth in general, see Halbach[6]). We are going to give new proofs for two well-known results in this area, and we also prove a new theorem on the nonstandardness of a certain theory of (...) truth. The results indicate that the proof strategies for all the theorems on the nonstandardness of such theories are "essentially" of the same kind of structure. (shrink)

The conditions are examined under which one theory is said to be replaceable by another, while preserving those features of the original theory which made it serviceable for a given purpose. Among such replacements, special attention is given to ones which qualify as so-called reductions of a theory, and some theorems are proved concerning the notion of a reduction.

A theory T is tight if different deductively closed extensions of T (in the same language) cannot be bi-interpretable. Many well-studied foundational theories are tight, including $\mathsf {PA}$ [39], $\mathsf {ZF}$, $\mathsf {Z}_2$, and $\mathsf {KM}$ [6]. In this article we extend Enayat’s investigations to subsystems of these latter two theories. We prove that restricting the Comprehension schema of $\mathsf {Z}_2$ and $\mathsf {KM}$ gives non-tight theories. Specifically, we show that $\mathsf {GB}$ and $\mathsf {ACA}_0$ each admit different bi-interpretable extensions, (...) and the same holds for their extensions by adding $\Sigma ^1_k$ -Comprehension, for $k \ge 1$. These results provide evidence that tightness characterizes $\mathsf {Z}_2$ and $\mathsf {KM}$ in a minimal way. (shrink)

In _On Empirically Equivalent Systems of the World_ from 1975, Quine formulated a thesis of underdetermination roughly to the effect that every scientific theory has an empirically equivalent but logically incompatible rival, one that cannot be discarded merely as a terminological variant of the former. For Quine, the truth of this thesis was an open question. If true, some would argue that it undermines any belief in scientific theories that is based purely on their empirical success. But despite its potential (...) significance, surprisingly little has been done by way of establishing or refuting it. My aim is to establish the thesis for as large a class of theories as possible. Under various precisifications of the concepts involved, I show that it holds for all consistent and recursively axiomatizable theories that postulate infinitely many theoretical entities. (shrink)

Certain selected issues around the Gödelian anti-mechanist arguments which have received less attention are discussed.

Sometimes structures or theories are formulated with different sets of primitives and yet are definitionally equivalent. In a sense, the transformations between such equivalent formulations are rather like basis transformations in linear algebra or co-ordinate transformations in geometry. Here an analogous idea is investigated. Let a relational signature \ be given. For a set \ of \-formulas, we introduce a corresponding set \ of new relation symbols and a set of explicit definitions of the \ in terms of the \. (...) This is called a definition system, denoted \. A definition system \ determines a translation function\. Any \-structure A can be uniquely definitionally expanded to a model \, called \. The reduct \ to the Q-symbols is called the definitional image\ of A. Likewise, a theory T in \ may be extended a definitional extension \; the restriction of this extension \ to \ is called the definitional image\ of T. If \ and \ are in disjoint signatures and \, we say that \ and \ are definitionally equivalent and \). Some results relating these notions are given, culminating in two characterization theorems for the definitional equivalence of structures and theories. (shrink)

In this paper we study proofs of some general forms of the Second Incompleteness Theorem. These forms conform to the Feferman format, where the proof predicate is fixed and the representation of the set of axioms varies. We extend the Feferman framework in one important point: we allow the interpretation of number theory to vary.

For simplicity, most of the literature introduces the concept of definitional equivalence only for disjoint languages. In a recent paper, Barrett and Halvorson introduce a straightforward generalization to non-disjoint languages and they show that their generalization is not equivalent to intertranslatability in general. In this paper, we show that their generalization is not transitive and hence it is not an equivalence relation. Then we introduce another formalization of definitional equivalence due to Andréka and Németi which is equivalent to the Barrett–Halvorson (...) generalization in the case of disjoint languages. We show that the Andréka–Németi generalization is the smallest equivalence relation containing the Barrett–Halvorson generalization and it is equivalent to intertranslatability, which is another definition for definitional equivalence, even for non-disjoint languages. Finally, we investigate which definitions for definitional equivalences remain equivalent when we generalize them for theories in non-disjoint languages. (shrink)

For simplicity, most of the literature introduces the concept of definitional equivalence only to languages with disjoint signatures. In a recent paper, Barrett and Halvorson introduce a straightforward generalization to languages with non-disjoint signatures and they show that their generalization is not equivalent to intertranslatability in general. In this paper,we show that their generalization is not transitive and hence it is not an equivalence relation. Then we introduce the Andréka and Németi generalization as one of the many equivalent formulations for (...) languages with disjoint signatures. We show that the Andréka-Németi generalization is the smallest equivalence relation containing the Barrett–Halvorson generalization and it is equivalent to intertranslatability even for languages with non-disjoint signatures. Finally,we investigate which definitions for definitional equivalences remain equivalent when we generalize them for theories with non-disjoint signatures. (shrink)

A substitutional account of logical validity for formal first‐order languages is developed and defended against competing accounts such as the model‐theoretic definition of validity. Roughly, a substitution instance of a sentence is defined as the result of uniformly substituting nonlogical expressions in the sentence with expressions of the same grammatical category and possibly relativizing quantifiers. In particular, predicate symbols can be replaced with formulae possibly containing additional free variables. A sentence is defined to be logically true iff all its substitution (...) instances are satisfied by all variable assignments. Logical consequence is defined analogously. Satisfaction is taken to be a primitive notion and axiomatized.For every set‐theoretic model in the sense of model theory there exists a corresponding substitutional interpretation in a sense to be specified. Conversely, however, there are substitutional interpretations – in particular the ‘intended’ interpretation – that lack a model‐theoretic counterpart. The substitutional definition of logical validity overcomes the weaknesses of more restrictive accounts of substitutional validity; unlike model‐theoretic logical consequence, the substitutional notion is trivially and provably truth preserving. In Kreisel's squeezing argument the formal notion of substitutional validity naturally slots into the place of intuitive validity. (shrink)

Various proposals have suggested that an adequate explanatory theory should reduce the number or the cardinality of the set of logically independent claims that need be accepted in order to entail a body of data. A (and perhaps the only) well-formed proposal of this kind is William Kneale’s: an explanatory theory should be finitely axiomatizable but it’s set of logical consequences in the data language should not be finitely axiomatizable. Craig and Vaught showed that Kneale theories (almost) always exist for (...) any recursively enumerable but not finitely axiomatizable set of data sentences in a first order language with identity. Kneale’s criterion underdetermines explanation even given all possible data in the data language; gratuitous axioms may be “tacked on.” Define a Kneale theory, T, to be logically minimal if it is deducible from every Kneale theory (in the vocabulary of T) that entails the same statements in the data language as does T. If they exist, minimal Kneale theories are candidates for best explanations: they are “bold” in a sense close to Popper’s; some minimal Kneale theory is true if any Kneale theory is true; the minimal Kneale theory that is data equivalent to any given Kneale theory is unique; and no Kneale theory is more probable than some minimal Kneale theory. I show that under the Craig-Vaught conditions, no minimal Kneale theories exist. (shrink)

Graham Solomon, to whom this collection is dedicated, went into hospital for antibiotic treatment of pneumonia in Oc- ber, 2001. Three days later, on Nov. 1, he died of a massive stroke, at the age of 44. Solomon was well liked by those who got the chance to know him—it was a revelation to?nd out, when helping to sort out his a?airs after his death, how many “friends” he had whom he had actually never met, as his email included correspondence (...) with philosophers around the world running sometimes to hundreds of messages. He was well respected in the philosophical community more broadly. He was for several years a member of the editorial board for the Western Ontario Series in Philosophy of Science. While he was employed at Wilfrid Laurier University in Waterloo, Ontario, several of us at the University of Wat- loo always regarded our own department as a sort of second academic home for him. We therefore decided that it would be appropriate to hold a memorial conference in his honour. Thanks to the generous?nancial support of the Humphrey Conference Fund, we were able to do so in May 2003. Many of the papers in this volume were presented at that conf- ence. (shrink)

This paper is a presentation of astatus quæstionis, to wit of the problemof the interpretability logic of all reasonablearithmetical theories.We present both the arithmetical side and themodal side of the question.Dedicated to Dick de Jongh on the occasion of his 60th birthday.

The prospects and limitations of defining truth in a finite model in the same language whose truth one is considering are thoroughly examined. It is shown that in contradistinction to Tarski's undefinability theorem for arithmetic, it is in a definite sense possible in this case to define truth in the very language whose truth is in question.

A field K in a ring language $\mathcal {L}$ is finitely undecidable if $\mbox {Cons}(T)$ is undecidable for every nonempty finite $T \subseteq {\mathtt{Th}}(K; \mathcal {L})$. We extend a construction of Ziegler and (among other results) use a first-order classification of Anscombe and Jahnke to prove every NIP henselian nontrivially valued field is finitely undecidable. We conclude (assuming the NIP Fields Conjecture) that every NIP field is finitely undecidable. This work is drawn from the author’s PhD thesis [48, Chapter 3].

The prevalent interpretation of Gödel’s Second Theorem states that a sufficiently adequate and consistent theory does not prove its consistency. It is however not entirely clear how to justify this informal reading, as the formulation of the underlying mathematical theorem depends on several arbitrary formalisation choices. In this paper I examine the theorem’s dependency regarding Gödel numberings. I introducedeviantnumberings, yielding provability predicates satisfying Löb’s conditions, which result in provable consistency sentences. According to the main result of this paper however, these (...) “counterexamples” do not refute the theorem’s prevalent interpretation, since once a natural class ofadmissiblenumberings is singled out, invariance is maintained. (shrink)

In this paper we explore the following question: how weak can a logic be for Rosser's essential undecidability result to be provable for a weak arithmetical theory? It is well known that Robinson's Q is essentially undecidable in intuitionistic logic, and P. Hajek proved it in the fuzzy logic BL for Grzegorczyk's variant of Q which interprets the arithmetic operations as non-total non-functional relations. We present a proof of essential undecidability in a much weaker substructural logic and for a much (...) weaker arithmetic theory, a version of Robinson's R (with arithmetic operations also interpreted as mere relations). Our result is based on a structural version of the undecidability argument introduced by Kleene and we show that it goes well beyond the scope of the Boolean, intuitionistic, or fuzzy logic. (shrink)

The affirmative answer to the title question is justified in two ways: logical and empirical. The logical justification is due to Gödel’s discovery that in any axiomatic formalized theory, having at least the expressive power of PA, at any stage of development there must appear unsolvable problems. However, some of them become solvable in a further development of the theory in question, owing to subsequent investigations. These lead to new concepts, expressed with additional axioms or rules. Owing to the so-amplified (...) axiomatic basis, new routine procedures like algorithms, can be reached. Those, in turn, help to gain new insights which lead to still more powerful axioms, and consequently again to ampler algorithmic resources. Thus scientific progress proceeds to an ever higher scope of solvability. The existence of such feedback cycles –in a formal way rendered with Turing’s systems of logic based on ordinal – gets empirically supported by the history of mathematics and other exact sciences. An instructive instance of such a process is found in the history of the number zero. Without that insight due to some ancient Hindu mathematicians there could not arise such an axiomatic theory as PA. It defines the algorithms of arithmetical operations, which in turn help intuitions; those, inturn, give rise to algorithmic routines, not available in any of the previous phases of the process in question. While the logical substantiation of the point of this essay is a well-established result of logico-semantic inquiries, its empiricalclaim, based on historical evidences, remains open for discussion. Hence the author’s intention to address philosophers and historians of science, and to encourage their critical responses. (shrink)

We prove that all extensions of Heyting Arithmetic with a logic that has the finite frame property possess the de Jongh property.

This chapter presents a new semantics for inductive empirical knowledge. The epistemic agent is represented concretely as a learner who processes new inputs through time and who forms new beliefs from those inputs by means of a concrete, computable learning program. The agent’s belief state is represented hyper-intensionally as a set of time-indexed sentences. Knowledge is interpreted as avoidance of error in the limit and as having converged to true belief from the present time onward. Familiar topics are re-examined within (...) the semantics, such as inductive skepticism, the logic of discovery, Duhem’s problem, the articulation of theories by auxiliary hypotheses, the role of serendipity in scientific knowledge, Fitch’s paradox, deductive closure of knowability, whether one can know inductively that one knows inductively, whether one can know inductively that one does not know inductively, and whether expert instruction can spread common inductive knowledge—as opposed to mere, true belief—through a community of gullible pupils. (shrink)

In a series of articles dating from 1903 to 1906, Frege criticizes Hilbert’s methodology of proving the independence and consistency of various fragments of Euclidean geometry in his Foundations of Geometry. In the final part of the last article, Frege makes his own proposal as to how the independence of genuine axioms should be proved. Frege contends that independence proofs require the development of a ‘new science’ with its own basic truths. This paper aims to provide a reconstruction of this (...) New Science that meets modern standards and to examine possible problems surrounding Frege’s original proposal. The paper is organized as follows: the first two sections summarize the main points of the Frege–Hilbert controversy and discuss some issues surrounding the problem of independence proofs. Section 3 contains an informal presentation of Frege’s proposal. In section 4 a more detailed reconstruction of Frege’s New Science is set out while section 5 examines what is left out. The concluding section is devoted to a discussion of Frege’s strategy and its significance from a broader perspective. (shrink)