We prove that the sharply bounded arithmetic T02 in a language containing the function symbol ⌊x /2y⌋ is equivalent to PV1.

We show that the arithmetical theory -INDx5, formalized in the language of Buss, i.e. with x/2 but without the MSP function x/2y, does not prove that every nontrivial divisor of a power of 2 is even. It follows that this theory proves neither NP=coNP nor.

This paper deals with: (i) the theory ID # 1 which results from $\widehat{\mathrm{ID}}_1$ by restricting induction on the natural numbers to formulas which are positive in the fixed point constants, (ii) the theory BON(μ) plus various forms of positive induction, and (iii) a subtheory of Peano arithmetic with ordinals in which induction on the natural numbers is restricted to formulas which are Σ in the ordinals. We show that these systems have proof-theoretic strength φω 0.

In this paper, we show that equation image is a equation image-conservative extension of BΣ1 + exp, thus it does not imply IΣ1.

We characterize the proof-theoretic strength of systems of explicit mathematics with a general principle asserting the existence of least fixed points for monotone inductive definitions, in terms of certain systems of analysis and set theory. In the case of analysis, these are systems which contain the Σ12-axiom of choice and Π12-comprehension for formulas without set parameters. In the case of set theory, these are systems containing the Kripke-Platek axioms for a recursively inaccessible universe together with the existence of (...) a stable ordinal. In all cases, the exact strength depends on what forms of induction are admitted in the respective systems. (shrink)

This paper deals with: (i) the theory $\mathrm{ID}^{\tt\#}_1$ which results from $\widehat{\mathrm{ID}}_1$ by restricting induction on the natural numbers to formulas which are positive in the fixed point constants, (ii) the theory $\mathrm{BON}(\mu)$ plus various forms of positive induction, and (iii) a subtheory of Peano arithmetic with ordinals in which induction on the natural numbers is restricted to formulas which are $\Sigma$ in the ordinals. We show that these systems have proof-theoretic strength $\varphi\omega 0$.

We prove here that the intuitionistic theory $T_{0}\upharpoonright + UMID_{N}$ , or even $EEJ\upharpoonright + UMID_{N}$ , of Explicit Mathematics has the strength of $\prod_{2}^{1} - CA_{0}$ . In Section I we give a double-negation translation for the classical second-order $\mu-calculus$ , which was shown in [ $M\ddot{o}02$ ] to have the strength of $\prod_{2}^{1}-CA_{0}$ . In Section 2 we interpret the intuitionistic $\mu-calculus$ in the theory $EETJ\upharpoonright + UMID_{N}$ . The question about the strength of monotone (...) inductive definitions in $T_{0}$ was asked by S. Feferman in 1982, and - assuming classical logic - was addressed by M. Rathjen. (shrink)

We prove that the statement “there is aksuch that for everyfthere is ak-bounded diagonally nonrecursive function relative tof” does not imply weak König’s lemma over${\rm{RC}}{{\rm{A}}_0} + {\rm{B\Sigma }}_2^0$. This answers a question posed by Simpson. A recursion-theoretic consequence is that the classic fact that everyk-bounded diagonally nonrecursive function computes a 2-bounded diagonally nonrecursive function may fail in the absence of${\rm{I\Sigma }}_2^0$.

Bar Induction occupies a central place in Brouwerian mathematics. This note is concerned with the strength of Bar Induction on the basis of Constructive Zermelo-Fraenkel Set Theory, CZF. It is shown that CZF augmented by decidable Bar Induction proves the 1-consistency of CZF. This answers a question of P. Aczel who used Bar Induction to give a proof of the Lusin Separation Theorem in the constructive set theory CZF.

Induction–recursion is a powerful definition method in intuitionistic type theory. It extends inductive definitions and allows us to define all standard sets of Martin-Löf type theory as well as a large collection of commonly occurring inductive data structures. It also includes a variety of universes which are constructive analogues of inaccessibles and other large cardinals below the first Mahlo cardinal. In this article we give a new compact formalization of inductive–recursive definitions by modeling them as initial algebras (...) in slice categories. We give generic formation, introduction, elimination, and equality rules generalizing the usual rules of type theory. Moreover, we prove that the elimination and equality rules are equivalent to the principle of the existence of initial algebras for certain endofunctors. We also show the equivalence of the current formulation with the formulation of induction–recursion as a reflection principle given in Dybjer and Setzer 93). Finally, we discuss two type-theoretic analogues of Mahlo cardinals in set theory: an external Mahlo universe which is defined by induction–recursion and captured by our formalization, and an internal Mahlo universe, which goes beyond induction–recursion. We show that the external Mahlo universe, and therefore also the theory of inductive–recursive definitions, have proof-theoretical strength of at least Rathjen's theory KPM. (shrink)

A broad class of inductive logics that includes the probability calculus is defined by the conditions that the inductive strengths [A|B] are defined fully in terms of deductive relations in preferred partitions and that they are asymptotically stable. Inductive independence is shown to be generic for propositions in such logics; a notion of a scale-free inductive logic is identified; and a limit theorem is derived. If the presence of preferred partitions is not presumed, no inductive (...) logic is definable. This no-go result precludes many possible inductive logics, including versions of hypothetico-deductivism. (shrink)

A broad class of inductive logics that includes the probability calculus is defined by the conditions that the inductive strengths [A|B] are defined fully in terms of deductive relations in preferred partitions and that they are asymptotically stable. Inductive independence is shown to be generic for propositions in such logics; a notion of a scale-free inductive logic is identified; and a limit theorem is derived. If the presence of preferred partitions is not presumed, no inductive (...) logic is definable. This no-go result precludes many possible inductive logics, including versions of hypothetico-deductivism. (shrink)

One objective of this paper is the determination of the proof-theoretic strength of Martin-Löf's type theory with a universe and the type of well-founded trees. It is shown that this type system comprehends the consistency of a rather strong classical subsystem of second order arithmetic, namely the one with Δ 2 1 comprehension and bar induction. As Martin-Löf intended to formulate a system of constructive (intuitionistic) mathematics that has a sound philosophical basis, this yields a constructive consistency proof of (...) a strong classical theory. Also the proof-theoretic strength of other inductive types like Aczel's type of iterative sets is investigated in various contexts.Further, we study metamathematical relations between type theories and other frameworks for formalizing constructive mathematics, e.g. Aczel's set theories and theories of operations and classes as developed by Feferman. (shrink)

The relative strengths of first-order theories axiomatized by transfinite induction, for ordinals less-than 0, and formulas restricted in quantifier complexity, is determined. This is done, in part, by describing the provably recursive functions of such theories. Upper bounds for the provably recursive functions are obtained using model-theoretic techniques. A variety of additional results that come as an application of such techniques are mentioned.

Saunders Mac Lane has drawn attention many times, particularly in his book Mathematics: Form and Function, to the system of set theory of which the axioms are Extensionality, Null Set, Pairing, Union, Infinity, Power Set, Restricted Separation, Foundation, and Choice, to which system, afforced by the principle, , of Transitive Containment, we shall refer as . His system is naturally related to systems derived from topos-theoretic notions concerning the category of sets, and is, as Mac Lane emphasises, one that is (...) adequate for much of mathematics. In this paper we show that the consistency strength of Mac Lane's system is not increased by adding the axioms of Kripke–Platek set theory and even the Axiom of Constructibility to Mac Lane's axioms; our method requires a close study of Axiom H, which was proposed by Mitchell; we digress to apply these methods to subsystems of Zermelo set theory , and obtain an apparently new proof that is not finitely axiomatisable; we study Friedman's strengthening of , and the Forster–Kaye subsystem of , and use forcing over ill-founded models and forcing to establish independence results concerning and ; we show, again using ill-founded models, that proves the consistency of ; turning to systems that are type-theoretic in spirit or in fact, we show by arguments of Coret and Boffa that proves a weak form of Stratified Collection, and that is a conservative extension of for stratified sentences, from which we deduce that proves a strong stratified version of ; we analyse the known equiconsistency of with the simple theory of types and give Lake's proof that an instance of Mathematical Induction is unprovable in Mac Lane's system; we study a simple set theoretic assertion—namely that there exists an infinite set of infinite sets, no two of which have the same cardinal—and use it to establish the failure of the full schema of Stratified Collection in ; and we determine the point of failure of various other schemata in . The paper closes with some philosophical remarks. (shrink)

We define a fragment of Primitive Recursive Arithmetic by replacing the defining axioms for primitive recursive functions by those for functions in some specific complexity class. In this note we consider such theory for AC0. We present a model-theoretical property of this theory, by means of which we are able to characterize its provably total functions. Next we consider the problem of how strong the induction scheme can be in this theory.

How confident does the history of science allow us to be about our current well-tested scientific theories, and why? The scientific realist thinks we are well within our rights to believe our best-tested theories, or some aspects of them, are approximately true.2 Ambitious arguments have been made to this effect, such as that over historical time our scientific theories are converging to the truth, that the retention of concepts and claims is evidence for this, and that there can be no (...) other serious explanation of the success of science than that its theories are approximately true. There is appeal in each of these ideas, but making such strong claims has tended to be hazardous, leaving us open to charges that many typical episodes in the history of science just do not fit the model. (See, e.g., Laudan 1981.) Arguing for a realist attitude via general claims – properties ascribed to sets of theories, trends we see in progressions of theories, and claimed links between general properties like success and truth that apply or fail to apply to any theory regardless of its content – is like arguing for or via a theory of science, which brings with it the obligation to defend that theory. I think a realist attitude toward particular scientific theories for which we have evidence can be maintained rationally without such a theory, even in the face of the pessimistic induction over the history of science. The starting point at which questions arise as to what we have a right to believe about our theories is one where we have theories and evidence for them, and we are involved in the activity of apportioning our belief in each particular theory or hypothesis in accord with the strength of the particular evidence.3 The devil’s advocate sees our innocence and tries his best to sow seeds of doubt. If our starting point is as I say, though, the innocent believer in particular theories does not have to play offense and propose sweeping views about science in general, but only to respond to the skeptic’s challenges; the burden of initial argument is on the skeptic.. (shrink)

In this thesis, we study the least fixed point principle in a constructive setting. A constructive theory of functions and sets has been developed by Feferman. This theory deals both with sets and with functions over sets as independent notions. In the language of Feferman's theory, we are able to formulate the least fixed point principle for monotone inductive definitions as: every operation on classes to classes which satisfies the monotonicity condition has a least fixed point. This is called (...) the principle of monotone inductive definition. Furthermore, we may formulate this principle in a uniform way as: there is an operation which maps a monotone operation to its least fixed point. This is called the principle of uniform monotone inductive definition. Feferman raised the question of the strength of the principle of monotone inductive definition when adjoined to his theory . This question is our primary concern in this thesis. ;Our main results are the consistency of both the principle of monotone inductive definition and the principle of uniform monotone inductive definition adjoined to his theory, and the proof theoretical equivalence between the principle of monotone inductive definition with Feferman's system without the inductive generation axiom and the system of the Pi-one-one Comprehension Axiom. Determination of the proof-theoretical strength of the principle of monotone inductive definition adjoined to Feferman's theory still remains open. ;The consistency of both the principle of monotone inductive definition and the principle of uniform monotone inductive definition with Feferman's theory will be achieved by constructing their models in set theoretical sense. The proof theoretical equivalence between the principle of monotone inductive definition with Feferman's system without the inductive generation axiom and the system of the Pi-one-one Comprehension Axiom can be obtained by a careful examination of the model construction for the principle of monotone inductive definition with Feferman's system without the inductive generation axiom, which is parallel to the model construction for the principle of monotone inductive definition with his theory. (shrink)

We argue that Cohen’s concept of inductive or ampliative probability facilitates proper explication of sufficient strength for non-demonstrative arguments conforming to the Toulmin model. The data and claims of such arguments are singular statements. We may epistemically classify the warrants of such arguments as empirical (either physical or personal), institutional, or evaluative. Backing evidence and rebutting considerations vary with the epistemic type of warrant, but in each case the notion of ampliative probability for arguments with warrants of that (...) type can be characterized. We may then use ampliative probability to define sufficient strength and related notions for Toulmin arguments. (shrink)

We introduce a new axiom called inductive dichotomy, a weak variant of the axiom of inductive definition, and analyze the relationships with other variants of inductive definition and with related axioms, in the general second order framework, including second order arithmetic, second order set theory and higher order arithmetic. By applying these results to the investigations on the determinacy axioms, we show the following. (i) Clopen determinacy is consistency-wise strictly weaker than open determinacy in these frameworks, except (...) second order arithmetic; this is an enhancement of Schweber–Hachtman separation of open and clopen determinacy into the consistency-wise separation. (ii) Hausdorff–Kuratowski hierarchy of differences of opens is faithfully reflected by the hierarchy of consistency strengths of corresponding parameter-free determinacies in the aforementioned frameworks; this result is valid also in second order arithmetic only except clopen determinacy. (shrink)

There are two important traditions in the philosophy of induction. According to one tradition, which has dominated for the last couple of centuries, inductive arguments are warranted by rules. Bayesianism is the most popular view within this tradition. Rules of induction provide functional accounts of inductive support, but no rule is universal; hence, no rule is by itself an accurate model of inductive support. According to another tradition, inductive arguments are not warranted by rules but by (...) matters of fact. Norton’s material theory of induction (MTI) is an influential view within this tradition. Norton’s MTI fails to provide an account of inductive support, but it provides a good account of inductive warrant that can help us define the domain of validity of each rule of induction. Despite their limitations, both approaches to induction are illuminating important aspects of how relations of inductive support work. In this article I present a hybrid theory of induction (HTI), in which I acknowledge and articulate the role of both rules and matters of fact in our understanding of inductive support. According to the HTI, rules of induction accurately describe relations of inductive support when they are warranted, and a rule of induction is warranted if the right facts about the matter of the induction obtain. Crucially, the HTI allows us to address the main challenges that each tradition faces while retaining their strengths, thus obtaining a functional and accurate account of inductive support. The HTI also provides a useful general framework to examine and understand induction, to make sense of how different rules of induction can coexist and to tackle some problems in epistemology. Moreover, the HTI allows us to clarify and resolve some current debates on induction, like the apparent divide between Norton and rule-based theorists. (shrink)

This work is in two parts. The main aim of part 1 is a systematic examination of deductive, probabilistic, inductive and purely inductive dependence relations within the framework of Kolmogorov probability semantics. The main aim of part 2 is a systematic comparison of (in all) 20 different relations of probabilistic (in)dependence within the framework of Popper probability semantics (for Kolmogorov probability semantics does not allow such a comparison). Added to this comparison is an examination of (in all) 15 (...) purely inductive dependence relations. ————Part 1 leads in an axiomatic step-by-step development from the elementary classical truth value semantics of a sentential-logical language, called ‘L’, (chapter 1) to the elementary Kolmogorov probability semantics of L (chapter 2), which is then extended to four axiomatic semantical theories of dependence relations between the formulae of L. First the elementary Kolmogorov probability semantics of L is extended to a theory, called ‘Kdd’, of the relations of deductive dependence and deductive independence between formulae of L (chapter 3). Then Kdd is extended to a theory, called ‘Kpd1’, of the degree to which formulae of L probabilistically depend on each other in regard to a given probability distribution on the set of all formulae of L (chapter 4). Kpd1, in its turn, gets extended to a theory, called ‘Kpd2’, of the relations of probabilistic dependence and independence, relativized to unary Kolmogorov probability functions defined on L (chapter 5). Then Kpd2 is extended to a theory, called ‘Kid’, of the relations of inductive dependence and inductive independence, again relativized to unary Kolmogorov probability functions defined on L (chapter 6). Finally, Kid is extended to a theory, called ‘Kpid’, of the relations of purely inductive positive and negative dependence, relativized to unary Kolmogorov probability functions defined on L (chapter 7). ——Chapter 1, which deals with the familiar notions of truth value functions, tautologies, consequence relations and relations of logical opposition, is naturally the shortest chapter of part 1.——In chapter 2, the elementary classical semantics of L is extended to the elementary Kolmogorov probability semantics of L, i.e. to an axiomatic theory of unary and of binary Kolmogorov probability functions defined on the set of formulae of L. Because of the elementary character of this theory, chapter 2 is also rather short.——Chapter 3 introduces the first theory on dependence relations, to wit: Kdd, the theory of deductive (in)dependence between formulae of L. I follow here the well-known idea of Popper and Miller, who have used it in a famous discussion on the nature of probabilistic support for their arguments that probabilistic support is deductive, not inductive. I develop Kdd in the form of about 100 theorems, making ample use of the fact that deductive independence is nothing but subcontrary opposition, and close with a remark on the fundamental difference between deductive and logical dependence—two relations the ideas of which are all too easily mixed up.——Chapters 4 and 5 deal extensively with the traditional ideas of probabilistic (in)dependence, applied to formulae rather than to events. As always, I proceed axiomatically in a step-by-step process under systematic viewpoints and obtain about 300 theorems in this way. In the formulation of the theorems, I took special care to state clearly and expressly so-called tacit assumptions, especially those concerning the probability values of the formulae said to be dependent on each other. These assumptions are usually missing in the literature, due either to economy of writing or to sloppiness of thinking. Presumably, both chapters contain little that is new, their value lying more in the systematic grouping and organic development of the theorems than in the newness of these.——In chapter 6, I extend the axiomatic theory about probabilistic (in)dependence which has been elaborated in chapter 5, to an axiomatic theory of inductive (in)dependence by requiring of the relation of inductive (in)dependence that it be probabilistic (in)dependence, but not also logical implication or logical opposition. I point out the differences between probabilistic and inductive (in)dependence by means of some 60 theorems and close my examination of inductive (in)dependence by considering its relationship to the notion of support in the philosophy of science.——Finally, in chapter 7, the last of part 1, I take the step from inductive dependence to what I call ‘purely inductive dependence’ by combining the idea of inductive dependence with that of deductive independence in a way which is suggested by writings of Popper and Miller. I arrive at two noteworthy theorems. Firstly, there is indeed no purely inductive support. But secondly, and perhaps amazingly, countersupport is purely inductive.————Whereas the probabilistic framework of part 1 of the present work is Kolmogorov probability semantics, the framework of part 2 is Popper probability semantics, which is not only worth examining as a fascinating alternative to orthodox Kolmogorov probability semantics, but also allows us to examine dependence relations more deeply, than Kolmogorov probability semantics does. Part 2 leads—again in an axiomatic step-by-step development—from the basic Popper probability semantics of L, called ‘Pb’, (chapter 8) via a probabilistic theory of logical attributes, called ‘Ps’, (chapter 9) to four axiomatic semantical theories of dependence relations between the formulae of L. First, Ps is extended to a theory, called ‘Pdd’, of the relations of deductive dependence and deductive independence between formulae of L (chapter 10). Then Pdd is extended to a theory, called ‘Ppd’, of (in all) 20 relations of probabilistic (in)dependence, relativized to binary Popper probability functions defined on L (chapter 11). Ppd, in its turn, is extended to a theory, called ‘Pid’, of (in all) 10 relations of inductive dependence, again relativized to binary Popper probability functions defined on L (first part of chapter 12). Finally, Pid is extended to a theory, called ‘Ppid’, of (in all) 15 relations of purely inductive positive and negative dependence, relativized to binary Popper probability functions defined on L (second part of chapter 12).——Chapter 8, the first chapter of part 2 of the present work, is entirely preparatory. It introduces the axioms and about 180 theorems (150 of them together with their proofs) of basic Popper probability semantics in order to set this kind of semantics under way.——Then, in chapter 9, basic Popper probability semantics is extended to a probabilistic theory of logical properties of and relations between the formulae of L. Although I think that the way I did this extension is of some interest in itself, the main task of chapter 9 is again a preparatory one: to yield the indispensable lemmata (about 90 in number) for the theorems concerning probabilistic dependence relations in chapter 11 and concerning inductive dependence relations in chapter 12.——Chapter 10 brings the extension of Ps to the theory Pdd of deductive (in)dependence. Only half a dozen theorems are noted here for later use in the Pdd-extensions Ppd and Ppid. In view of the over 100 theorems already gained on this topic in the Kolmogorovian framework (cf. chapter 3), a similar extensive elaboration of Pdd would have been superfluous.——Chapter 11 is the most important one of part 2. It consists of a systematic comparison of 20 probabilistic (in)dependence concepts by means of about 230 theorems, obtained within the axiomatic theory Ppd, which is built up as an extension of Pdd. The main points of comparison were: differences in logical strength; reflexivity and symmetry; behaviour under the condition that the probability values of the formulae in question are extreme. It turned out that each of the examined concepts violates a strong and straightforward version of the intuitive requirement that probabilistic dependence should go with logical dependence. Whereas the corresponding chapter 5 in part 1 of the present work may not have led to new theorems, chapter 11 yields dozens of them in the process of comparison of concepts of dependence and independence which had—as far as I know—never before been treated in a single theoretical framework. With Popper probability semantics, this framework has become available, and here I have simply made full use of it.——In chapter 12, I extend the theory Ppd of probabilistic (in)dependence to the theories Pid and Ppid of inductive and purely inductive dependence, in a way very similar to that in which I have extended the theory Kpd2 to the theories Kid and Kpid in chapters 6 and 7. The first main result of Kpid (roughly: there is no purely inductive support) could be repeated for four of the five purely inductive positive dependence relations considered in chapter 12, whereas the second main result of Kpid (roughly: there is purely inductive countersupport ) could be repeated for each of the five examined purely inductive negative dependence relations. Chapter 12 closes with a brief recapitulation and critical discussion of the main results. (shrink)

Children’s reasoning on food properties and health relationships can contribute to healthier food choices. Food properties can either be positive (“gives strength”) or negative (“gives nausea”). One of the main challenges in public health is to foster children’s dietary variety, which contributes to a normal and healthy development. To face this challenge, it is essential to investigate how children generalize these positive and negative properties to other foods, including familiar and unfamiliar ones. In the present experiment, we hypothesized that (...) children might rely on cues of food processing (e.g., signs of human intervention such as slicing) to convey information about item edibility. Furthermore, capitalizing on previous results showing that food rejections (i.e., food neophobia and picky eating) are a significant source of inter-individual variability to children’s inferences in the food domain, we followed an individual approach. We expected that children would generalize the positive properties to familiar foods and, in contrast, that they would generalize more often the negative properties to unfamiliar foods. However, we expected that children would generalize more positive and less negative properties to unfamiliar sliced foods than to whole unfamiliar foods. Finally, we expected that children displaying higher levels of food rejections would generalize more negative properties than children displaying lower levels of food rejections. One-hundred and twenty-six children, aged 3–6 years, performed an induction task in which they had to generalize positive or negative health-related properties to familiar or unfamiliar foods, whole or sliced. We measured children’s probability of generalization for positive and negative properties. The children’s food rejection score was assessed on a standardized scale. Results indicated that children evaluated positively familiar foods (regardless of processing), whereas they tend to view unfamiliar food negatively. In contrast, children were at chance for processed unfamiliar foods. Furthermore, children displaying higher levels of food rejections were more likely to generalize the negative properties to all kinds of foods than children displaying lower levels of food rejections. These findings entitle us to hypothesize that knowledge-based food education programs should take into account the valence of the properties taught to children, as well as the state of processing of the food presented. Furthermore, one should take children’s interindividual differences into account because they influence how the knowledge gained through these programs may be generalized. (shrink)

We study the proof-theoretic strength and effective content of the infinite form of Ramsey's theorem for pairs. Let RT n k denote Ramsey's theorem for k-colorings of n-element sets, and let RT $^n_{ denote (∀ k)RT n k . Our main result on computability is: For any n ≥ 2 and any computable (recursive) k-coloring of the n-element sets of natural numbers, there is an infinite homogeneous set X with X'' ≤ T 0 (n) . Let IΣ n and (...) BΣ n denote the Σ n induction and bounding schemes, respectively. Adapting the case n = 2 of the above result (where X is low 2 ) to models of arithmetic enables us to show that RCA 0 + IΣ 2 + RT 2 2 is conservative over RCA 0 + IΣ 2 for Π 1 1 statements and that $RCA_0 + I\Sigma_3 + RT^2_{ , is Π 1 1 -conservative over RCA 0 + IΣ 3 . It follows that RCA 0 + RT 2 2 does not imply BΣ 3 . In contrast, J. Hirst showed that $RCA_0 + RT^2_{ does imply BΣ 3 , and we include a proof of a slightly strengthened version of this result. It follows that $RT^2_{ is strictly stronger than RT 2 2 over RCA 0. (shrink)

Inductive generalization asserts that what obtains in known instances can be generalized to all. Its original form is enumerative induction, the earliest form of inductive inference, and it has been elaborated in various ways, largely with the goal of extending its reach. Its principal problem is that it supplies no intrinsic notion of strength of support so that one cannot tell if the generalization has weak or strong support.

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)

The first main topic of this paper is a weak second-order theory that sits between firstorder Peano Arithmetic PA1 and axiomatized second-order Peano Arithmetic PA2 – namely, that much-investigated theory known in the trade as ACA0. What I’m going to argue is that ACA0, in its standard form, lacks a cogent conceptual motivation. Now, that claim – when the wraps are off – will turn out to be rather less exciting than it sounds. It isn’t that all the work that (...) has been done on ACA0 has been hopelessly misplaced: that would be a quite absurd suggestion. The mistake, if that’s what it is, has been a relatively small one. Still, we really ought to try to put things into conceptual good order here. That’s part of what philosophers are for. Here’s the structure of my main claim. On the one hand, interesting work on ACA0 actually only uses part of the strength of the theory: or as we might put it, the interesting work is actually carried on in a cut-down theory I’ll call ACA!. This theory, I’ll be claiming, does have a good conceptual motivation – it is in fact the theory that the putative conceptual grounding for ACA0 actually underpins. On the other hand, I’ll be arguing that original-strength ACA0 inductively inflates. I mean, to put it more carefully, that anyone who accepts ACA0 as a cogent theory can have no reason not to accept a certain significantly stronger theory, with a stronger induction principle. This stronger theory is standardly known as plain ACA. So, my claim comes to this: you can either go for the cut-down theory ACA!; or you can go for the much richer theory ACA. What you can’t do is – I mean, what you can’t have a stable conceptual motivation for doing – is to rest content with the intermediate strength ACA0 in its standard presentation. Yet in much of the literature, in particular in Simpson’s encyclopedic book Subsystems of Second-Order Arithmetic (1991), neither ACA! nor full ACA gets so much as a mention, and the conceptually unstable theory ACA0 gets all the glory. Why is my claim at all interesting? For at least two reasons.. (shrink)

In their logical analysis of theorems about disjoint rays in graphs, Barnes, Shore, and the author (hereafter BGS) introduced a weak choice scheme in second-order arithmetic, called the $\Sigma ^1_1$ axiom of finite choice (hereafter finite choice). This is a special case of the $\Sigma ^1_1$ axiom of choice ( $\Sigma ^1_1\text {-}\mathsf {AC}_0$ ) introduced by Kreisel. BGS showed that $\Sigma ^1_1\text {-}\mathsf {AC}_0$ suffices for proving many of the aforementioned theorems in graph theory. While it is not known (...) if these implications reverse, BGS also showed that those theorems imply finite choice (in some cases, with additional induction assumptions). This motivated us to study the proof-theoretic strength of finite choice. Using a variant of Steel forcing with tagged trees, we show that finite choice is not provable from the $\Delta ^1_1$ -comprehension scheme (even over $\omega $ -models). We also show that finite choice is a consequence of the arithmetic Bolzano–Weierstrass theorem (introduced by Friedman and studied by Conidis), assuming $\Sigma ^1_1$ -induction. Our results were used by BGS to show that several theorems in graph theory cannot be proved using $\Delta ^1_1$ -comprehension. Our results also strengthen results of Conidis. (shrink)

Research on human causal induction has shown that people have general prior assumptions about causal strength and about how causes interact with the background. We propose that these prior assumptions about the parameters of causal systems do not only manifest themselves in estimations of causal strength or the selection of causes but also when deciding between alternative causal structures. In three experiments, we requested subjects to choose which of two observable variables was the cause and which the effect. (...) We found strong evidence that learners have interindividually variable but intraindividually stable priors about causal parameters that express a preference for causal determinism. These priors predict which structure subjects preferentially select. The priors can be manipulated experimentally and appear to be domain-general. Heuristic strategies of structure induction are suggested that can be viewed as simplified implementations of the priors. (shrink)

Jullien's indecomposability theorem (INDEC) states that if a scattered countable linear order is indecomposable, then it is either indecomposable to the left, or indecomposable to the right. The theorem was shown by Montalbán to be a theorem of hyperarithmetic analysis, and then, in the base system RCA₀ plus ${\mathrm{\Sigma }}_{1}^{1}\text{\hspace{0.17em}}$ induction, it was shown by Neeman to have strength strictly between weak ${\mathrm{\Sigma }}_{1}^{1}$ choice and ${\mathrm{\Delta }}_{1}^{1}$ comprehension. We prove in this paper that ${\mathrm{\Sigma }}_{1}^{1}$ induction is needed (...) for the reversal of INDEC, that is for the proof that INDEC implies weak ${\mathrm{\Sigma }}_{1}^{1}$ choice. This is in contrast with the typical situation in reverse mathematics, where reversals can usually be refined to use only ${\mathrm{\Sigma }}_{1}^{0}$ induction. (shrink)

A two-fold challenge faces any account of inductive inference. It must provide means to discern which are the good inductive inferences or which relations capture correctly the strength of inductive support. It must show us that those means are the right ones. Formal theories of inductive inference provide the means through universally applicable formal schema. They have failed, I argue, to meet either part of the challenge. In their place, I urge that background facts in (...) each domain determine which are the good inductive inferences; and we can see that they are good in virtue of the meaning of the pertinent background facts. This material theory of induction is used to assess the competing inductive inferences in the debate in 1972 between John N. Bahcall and Halton Arp over the import of the redshift of light from the galaxies. (shrink)

Inductive logic would be the logic of arguments that are not valid, but nevertheless justify belief in something like the way in which valid arguments would. Maybe we could describe it as the logic of “almost valid” arguments. There is a sort of transitivity to valid arguments. Valid arguments can be chained together to form arguments and such arguments are themselves valid. One wants to distinguish the “almost valid” arguments by noting that chains of “almost valid” arguments are weaker (...) than the links that form them. But it is not clear that this is so. I have an apparent counterexample the claim. Though: as is typical in these sorts of situations, it is hard to tell where the problem lies. (shrink)

The transformers that drive chatbots and other AI systems constitute large language models (LLMs). These are currently the focus of a lively discussion in both the scientific literature and the popular media. This discussion ranges from hyperbolic claims that attribute general intelligence and sentience to LLMs, to the skeptical view that these devices are no more than “stochastic parrots”. I present an overview of some of the weak arguments that have been presented against LLMs, and I consider several of the (...) more compelling criticisms of these devices. The former significantly underestimate the capacity of transformers to achieve subtle inductive inferences required for high levels of performance on complex, cognitively significant tasks. In some instances, these arguments misconstrue the nature of deep learning. The latter criticisms identify significant limitations in the way in which transformers learn and represent patterns in data. They also point out important differences between the procedures through which deep neural networks and humans acquire knowledge of natural language. It is necessary to look carefully at both sets of arguments in order to achieve a balanced assessment of the potential and the limitations of LLMs. (shrink)

We extend the core model induction technique to a choiceless context, and we exploit it to show that each one of the following two hypotheses individually implies that , the Axiom of Determinacy, holds in the of a generic extension of : every uncountable cardinal is singular, and every infinite successor cardinal is weakly compact and every uncountable limit cardinal is singular.

Logic is the study of the quality of arguments. An argument consists of a set of premises and a conclusion. The quality of an argument depends on at least two factors: the truth of the premises, and the strength with which the premises confirm the conclusion. The truth of the premises is a contingent factor that depends on the state of the world. The strength with which the premises confirm the conclusion is supposed to be independent of the (...) state of the world. Logic is only concerned with this second, logical factor of the quality of arguments. (shrink)

Let κ R be the least ordinal κ such that L κ (R) is admissible. Let $A = \{x \in \mathbb{R} \mid (\exists\alpha such that x is ordinal definable in L α (R)}. It is well known that (assuming determinacy) A is the largest countable inductive set of reals. Let T be the theory: ZFC - Replacement + "There exists ω Woodin cardinals which are cofinal in the ordinals." T has consistency strength weaker than that of the theory (...) ZFC + "There exists ω Woodin cardinals", but stronger than that of the theory ZFC + "There exists n Woodin Cardinals", for each n ∈ ω. Let M be the canonical, minimal inner model for the theory T. In this paper we show that A = R ∩ M. Since M is a mouse, we say that A is a mouse set. As an application, we use our characterization of A to give an inner-model-theoretic proof of a theorem of Martin which states that for all n, every Σ * n real is in A. (shrink)

This essay discusses and criticizes Richard Swinburne's inductive argument for the existence of God. In his The Existence of God, Swinburne aims at showing that the existence of God is more probable than not. This is an argument taking into consideration the premises of all traditional arguments for the existence of God. Swinburne uses the phenomena and events that constitute the premises of these arguments as evidence in an attempt to show that his hypothesis is more probably true than (...) nor. Swinburne pursues this task by way of applying Bayes' theorem. The aim of this essay is normative - to judge the strength of Swinburne's argument for the existence of God. My primary objections towards Swinburne is that he professes a subjective concept of probability, that he relies too heavily on simplicity as a virtue of plausible and probable hypotheses and that his concept of God involves an incoherent picture of God's nature. I question not only the actual success of Swinburne's project but what his argument, if it had been successful, would have been able to establish. (shrink)

Statements that share an explanation tend to lend inductive support to one another. For example, being told that Many furniture movers have a hard time financing a house increases the judged probability that Secretaries have a hard time financing a house. In contrast, statements with different explanations reduce one another s judged probability. Being told that Many furniture movers have bad backs decreases the judged probability that Secretaries have bad backs. I pose two questions concerning such discounting effects. First, (...) does the reduction depend on explanations being mutually incompatible or does it occur when explanations are deemed irrelevant to one another? I found that a small discounting effect occurred with statements that were blatantly unrelated. However, the discounting effect also depended on a factor external to the argument being judged; the composition of the argument set. Second, are explanation effects attributable to changes in the belief afforded statements or to response-specific changes resulting from misunderstanding of the probability rating task or response bias? The results implicate changes in belief. Prior belief influenced conditional probability more than argument strength judgements, as it would if participants understood the tasks in the same way as the experimenter. Also, conditional probability true and false judgements were complementary, suggesting no response bias. (shrink)

The article shows a simple way of calibrating the strength of the theory of positive induction, ${{\rm ID}^{*}_{1}}$ . Crucially the proof exploits the equivalence of ${\Sigma^{1}_{1}}$ dependent choice and ω-model reflection for ${\Pi^{1}_{2}}$ formulae over ACA 0. Unbeknown to the authors, D. Probst had already determined the proof-theoretic strength of ${{\rm ID}^{*}_{1}}$ in Probst, J Symb Log, 71, 721–746, 2006.

A productive way to think about imagistic mental models of physical systems is as though they were sources of quasi‐empirical evidence. People depict or imagine events at those points in time when they would experiment with the world if possible. Moreover, just as they would do when observing the world, people induce patterns of behavior from the results depicted in their imaginations. These resulting patterns of behavior can then be cast into symbolic rules to simplify thinking about future problems and (...) to reveal higher order relationships. Using simple gear problems, three experiments explored the occasions of use for, and the inductive transitions between, depictive models and number‐based rules. The first two experiments used the convergent evidence of problem‐solving latencies, hand motions, referential language and error data to document the initial use of a model, the induction of rules from the modeling results, and the fallback to a model when a rule fails. The third experiment explored the intermediate representations that facilitate the induction of rules from depictive models. The strengths and weaknesses of depictive modeling and more analytic systems of reasoning are delineated to motivate the reasons for these transitions. (shrink)

Selectional preferences have a long history in both generative and computational linguistics. However, since the publication of Resnik's dissertation in 1993, a new approach has surfaced in the computational linguistics community. This new line of research combines knowledge represented in a pre‐defined semantic class hierarchy with statistical tools including information theory, statistical modeling, and Bayesian inference. These tools are used to learn selectional preferences from examples in a corpus. Instead of simple sets of semantic classes, selectional preferences are viewed as (...) probability distributions over various entities. We survey research that extends Resnik's initial work, discuss the strengths and weaknesses of each approach, and show how they together form a cohesive line of research. (shrink)

Above all other titles, Charles Sanders Peirce (1839-1914) prized that of logician. He thought of logic broadly, such that it includes not merely formal logic but an examination of the entire process of inquiry. His works are replete with detailed investigations into logical questions. Peirce is especially concerned to show that valid inferential processes, diligently followed, will eventually root out error and alight on the truth. Peirce on Inference draws together diverse strands from Peirce's lifelong reflections on logic in order (...) to develop a comprehensive perspective on Peirce's theory of inference. -/- Peirce argues that each genus of inference--deduction, induction, and abduction--has a different truth-producing virtue. An inference is valid just in case the procedure used in fact has the truth-producing virtue claimed for it and the person making the inference adheres to the procedure. In successive chapters, this book shows how Peirce supports the thesis that these genera of inference have the truth-producing virtues claimed for them and how Peirce responds to objections. Among the objections given consideration are the liar paradox, Hume's problem of induction, Goodman's new riddle of induction, that this may be a chance world, and that we are incapable of conceiving the true hypothesis. The book defends several controversial theses, including that Peirce does not so strongly object to Bayesianism as is sometimes claimed and that prior to 1900 Peirce had no explicit theory of abduction. It also proposes a novel account of abduction. (shrink)

We locate winning strategies for various ${\mathrm{\Sigma }}_{3}^{0}$ -games in the L-hierarchy in order to prove the following: Theorem 1. KP+Σ₂-Comprehension $\vdash \exists \alpha L_{\alpha}\ models"\Sigma _{2}-{\bf KP}+\Sigma _{3}^{0}-\text{Determinacy}."$ Alternatively: ${\mathrm{\Pi }}_{3}^{1}\text{\hspace{0.17em}}-{\mathrm{C}\mathrm{A}}_{0}\phantom{\rule{0ex}{0ex}}$ "there is a β-model of ${\mathrm{\Delta }}_{3}^{1}-{\mathrm{C}\mathrm{A}}_{0}\text{\hspace{0.17em}}\text{\hspace{0.17em}}+\text{\hspace{0.17 em}}{\mathrm{\Sigma }}_{3}^{0}$ -Determinacy." The implication is not reversible. (The antecedent here may be replaced with ${\mathrm{\Pi }}_{3}^{1}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\left({\mathrm{\Pi }}_{3}^{1}\right)-{\mathrm{C}\mathrm{A}}_{0}:\text{\hspace{0.17em}}{\mathrm{\Pi }}_{3}^{1}$ instances of Comprehension with only ${\mathrm{\Pi }}_{3}^{1}$ -lightface definable parameters—or even weaker theories.) Theorem 2. KP +Δ₂-Comprehension +Σ₂-Replacement + ${\mathrm{\Sigma }}_{3}^{0}\phantom{\rule{0ex}{0ex}}$ -Determinacy. (Here AQI (...) is the assertion that every arithmetical quasi-inductive definition converges.) Alternatively: $\Delta _{3}^{1}{\rm CA}_{0}+{\rm AQI}\nvdash \Sigma _{3}^{0}$ -Determinacy. Hence the theories: ${\mathrm{\Pi }}_{3}^{1}-{\mathrm{C}\mathrm{A}}_{0},\text{\hspace{0.17em}}{\mathrm{\Delta }}_{3}^{1}-{\mathrm{C}\mathrm{A}}_{0}+\text{\hspace{0.17em}}{\mathrm{\Sigma }}_{3}^{0}-\mathrm{D}\mathrm{e}\mathrm{t}\phantom{\rule{0ex}{0ex}}$ -Det, ${\mathrm{\Delta }}_{3}^{1}-{\mathrm{C}\mathrm{A}}_{0}+\mathrm{A}\mathrm{Q}\mathrm{I}$ , and ${\mathrm{\Delta }}_{3}^{1}-{\mathrm{C}\mathrm{A}}_{0}\phantom{\rule{0ex}{0ex}}$ are in strictly descending order of strength. (shrink)

The hidden strength of Goodman's ingenious "new riddle of induction" lies in the perfect symmetry of grue/bleen and green/blue. The very same sentence forms used to define grue/bleen in terms of green/blue can be used to define green/blue in terms of grue/bleen by permutation of terms. Therein lies its undoing. In the artificially restricted case in which there are no additional facts that can break the symmetry, grue/bleen and green/blue are merely notational variants of the same facts; or, if (...) they represent different facts, the differences are ineffable, and no account of induction should be expected to pick between them. This still obtains in the more interesting case in which we embed grue/bleen in a grue-ified total science; the grue-ified and regular total sciences are merely equivalent descriptions of the same facts. In the most realistic case, we allow additional facts that break the symmetry and then we can also evade Goodman's new riddle by employing an account of induction rich enough to exploit these facts. Unaugmented enumerative induction is not such an account and it is the primary casualty of Goodman's new riddle. (shrink)