Various forms of mathematical induction are applicable to domains with some kinds of order. This naturally leads to the questions about the possibility of unification of different inductions and their generalization to wider classes of ordered domains. In the paper we propose a common framework for formulating induction proof principles in various structures and apply it to partially ordered sets. In this framework we propose a fixed induction principle which is indirectly applicable to the class of (...) all posets. In a certain sense, this result provides a solution to the problem of formulating a common generalization of a number of well-known induction principles for discrete and continuous ordered structures. (shrink)

We give a constructive proof of the open induction principle on real numbers, using bar induction and enumerative open sets. We comment the algorithmic content of this result.

We establish a course-of-values induction principle for K-finite sets in intuitionistic type theory. Using this principle, we prove a pigeonhole principle conjectured by Bénabou and Loiseau. We also comment on some variants of this pigeonhole principle.

This thesis presents a proof theoretical investigation of some constructive set theories with restricted set induction. The set theories considered are various systems of Constructive Zermelo Fraenkel set theory, CZF ([1]), in which the schema of $\in$ - Induction is either removed or weakened. We shall examine the theories $CZF^\Sigma_\omega$ and $CZF_\omega$, in which the $\in$ - Induction scheme is replaced by a scheme of induction on the natural numbers (only for  formulas in the case (...) of the first theory, for arbitrary formulas in the second theory). Of particular interest is the system CZF− + INAC, which is obtained by removing $\in$ - Induction and by adding an axiom, INAC, for inaccessible sets. The main outcome is that CZF− + INAC is a predicative set theory with inaccessible sets, its proof theoretic ordinal being $\Gamma_0$. The proof theoretic strength of these theories, has been determined by means of proof theoretical reductions. The upper bounds have been obtained by interpreting the set theories in classical theories of (iterated) inductive definitions with ordinals. A significant feature of these interpretations is that they are realizability interpretations, which make an indirect use of Aczel’s interpretation of CZF in Martin Löf type theory, and, in the case of CZF− + INAC, also employ a maximum bisimulation relation to represent equality between sets. The lower bounds are obtained by interpreting appropriate subsystems of intuitionistic second order arithmetic in the set theories. At the conclusion of the thesis we present work unrelated to the previous chapters. It is a preliminary study of the constructible hierarchy in CZF. We begin by formalizing the notion of definability in constructive set theory and then introduce Gödel’s L in CZF. We prove that intuitionistic L is a model of a subsystem of CZF strong enough to include intuitionistic Kripke-Platek set theory, and also that L is a model of the axiom of constructibility, provably in CZF. (shrink)

Goncharov and Peretyat'kin independently gave necessary and sufficient conditions for when a set of types of a complete theory is the type spectrum of some homogeneous model of. Their result can be stated as a principle of second order arithmetic, which is called the Homogeneous Model Theorem (HMT), and analyzed from the points of view of computability theory and reverse mathematics. Previous computability theoretic results by Lange suggested a close connection between HMT and the Atomic Model Theorem (AMT), which states (...) that every complete atomic theory has an atomic model. The authors show that HMT and AMT are indeed equivalent in the sense of reverse mathematics, as well as in a strong computability theoretic sense and do the same for an analogous result of Peretyat'kin giving necessary and sufficient conditions for when a set of types is the type spectrum of some model. (shrink)

Many theorists have proposed that we can use the principle of indifference to defeat the inductive sceptic. But any such theorist must confront the objection that different ways of applying the principle of indifference lead to incompatible probability assignments. Huemer offers the explanatory priority proviso as a strategy for overcoming this objection. With this proposal, Huemer claims that we can defend induction in a way that is not question-begging against the sceptic. But in this article, I argue that the (...) opposite is true: if anything, Huemer’s use of the principle of indifference supports the rationality of inductive scepticism. (shrink)

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

We show that many principles of first-order arithmetic, previously only known to lie strictly between [Formula: see text]-induction and [Formula: see text]-induction, are equivalent to the well-foundedness of [Formula: see text]. Among these principles are the iteration of partial functions of Hájek and Paris, the bounded monotone enumerations principle by Chong, Slaman, and Yang, the relativized Paris–Harrington principle for pairs, and the totality of the relativized Ackermann–Péter function. With this we show that the well-foundedness of [Formula: (...) see text] is a far more widespread than usually suspected. Further, we investigate the [Formula: see text]-iterated version of the bounded monotone iterations principle, and show that it is equivalent to the well-foundedness of the -height [Formula: see text]-tower [Formula: see text]. (shrink)

Aristotle's cognitive ideal is a form of understanding that requires a sophisticated grasp of scientific first principles. At the end of the Analytics, Aristotle tells us that we learn these principles by induction. But on the whole, commentators have found this an implausible claim: induction seems far too basic a process to yield the sort of knowledge Aristotle's account requires. In this paper I argue that this criticism is misguided. I defend a broader reading of Aristotelian (...) induction, on which there's good sense to be made of the claim that we come to grasp first principles inductively, and show that this reading is a natural one given Aristotle's broader views on scientific learning. (shrink)

Modern Empiricists are typically troubled by the two following problems: (1) There is an epistemic gap between experience of individuals and understanding universals such that empiricist accounts of concept formation seem to beg the question. (2) There needs to be an answer to the skeptic who denies that sensory experience warrants our belief in the existence of the material substances that underlie sensible qualities. Although Aristotle’s account of induction is subject to these problems prima facie, his theory of perception, (...) his teleologically driven reliabilism about the senses, and his broader metaphysical views concerning the relation between substance and accident serve to insulate his account of induction from the pitfalls of modern empiricism. The resolution to these problems proposed in this paper allows for a consistent reading of otherwise controversial Aristotelian texts, while recommending a defense of realism about material substance against the claims of the Humean skeptic. (shrink)

A foundational text in modern empiricist method, published in 1843 by Victorian England's foremost philosopher of political and social life.

CHAPTER I. THE FOUNDATIONS OF LOGIC :— THE UNIVERSE AS THE MATERIAL LOGICIAN REGARDS IT. SINCE Logic, as conceived and expounded in this work, ...

This two-volume work, first published in 1843, was John Stuart Mill's first major book. It reinvented the modern study of logic and laid the foundations for his later work in the areas of political economy, women's rights and representative government. In clear, systematic prose, Mill disentangles syllogistic logic from its origins in Aristotle and scholasticism and grounds it instead in processes of inductive reasoning. An important attempt at integrating empiricism within a more general theory of human knowledge, the work constitutes (...) essential reading for anyone seeking a full understanding of Mill's thought. Volume 1 contains Mill's introduction, which elaborates upon his definition of logic as 'not the science of Belief, but the science of Proof, or Evidence'. It also features discussions of the central components of logical reasoning - propositions and syllogisms - in relation to Mill's theories of inductive reasoning and experimental method. (shrink)

This article argues that a successful answer to Hume's problem of induction can be developed from a sub-genre of philosophy of science known as formal learning theory. One of the central concepts of formal learning theory is logical reliability: roughly, a method is logically reliable when it is assured of eventually settling on the truth for every sequence of data that is possible given what we know. I show that the principle of induction (PI) is necessary and sufficient (...) for logical reliability in what I call simple enumerative induction. This answer to Hume's problem rests on interpreting PI as a normative claim justified by a non-empirical epistemic means-ends argument. In such an argument, a rule of inference is shown by mathematical or logical proof to promote a specified epistemic end. Since the proof concerning PI and logical reliability is not based on inductive reasoning, this argument avoids the circularity that Hume argued was inherent in any attempt to justify PI. (shrink)

We propose an Analogy Principle in the context of Unary Inductive Logic and characterize the probability functions which satisfy it. In particular in the case of a language with just two predicates the probability functions satisfying this principle correspond to solutions of Skyrmsʼ ‘Wheel of Fortune’.

We extend the framework of Inductive Logic to Second Order languages and introduce Wilmers' Principle, a rational principle for probability functions on Second Order languages. We derive a representation theorem for functions satisfying this principle and investigate its relationship to the first order principles of Regularity and Super Regularity.

This two-volume work, first published in 1843, was John Stuart Mill's first major book. It reinvented the modern study of logic and laid the foundations for his later work in the areas of political economy, women's rights and representative government. In clear, systematic prose, Mill disentangles syllogistic logic from its origins in Aristotle and scholasticism and grounds it instead in processes of inductive reasoning. An important attempt at integrating empiricism within a more general theory of human knowledge, the work constitutes (...) essential reading for anyone seeking a full understanding of Mill's thought. Continuing the discussion of induction, Volume 2 concludes with Book VI, 'On the Logic of the Moral Sciences', in which Mill applies empirical reasoning to human behaviour. A crucial early formulation of his thinking regarding free will and necessity, this book establishes the centrality of 'the social science' to Mill's philosophy. (shrink)

In this paper we consider a natural generalization of the Principle of Instantial Relevance and give a complete characterization of the probabilistic belief functions satisfying this principle as a family of discrete probability functions parameterized by a single real δ ∊ [0, 1).

I develop a critique of Hume’s infamous problem of induction based upon the idea that the principle of induction (PI) is a normative rather than descriptive claim. I argue that Hume’s problem is a false dilemma, since the PI might be neither a “relation of ideas” nor a “matter of fact” but rather what I call a contingent normative statement. In this case, the PI could be justified by a means-ends argument in which the link between means and (...) end is established solely by deductive reasoning. The means-ends argument is an elementary result from formal learning theory that you must be willing to make inductive generalizations if you want to be logically reliable in the types of examples Hume described. This justification of the PI avoids both horns of Hume’s dilemma. Since no contradiction ensues from rejecting logical reliability as an aim, the PI is contingent. Yet since the proof concerning the PI and logical reliability is not based on inductive reasoning, there is no threat of circularity. (shrink)

An improvement on Horwich's so-called "pseudo-proof" of Russell's principle of induction is offered, which, we believe, avoids certain objections to the former. Although strictly independent of our other work in this area, a connection can be made and in the final section we comment on this and certain questions regarding rationality, etc.

In "Intuitionistic validity in -normal Kripke structures," Buss asked whether every intuitionistic theory is, for some classical theory , that of all -normal Kripke structures for which he gave an r.e. axiomatization. In the language of arithmetic and denote PA plus Open Induction or Open LNP, and are their intuitionistic deductive closures. We show is recursively axiomatizable and , while . If proves PEM but not totality of a classically provably total Diophantine function of , then and so . (...) A result due to Wehmeier then implies . We prove is not -conservative over . If , then is not closed under MR or Friedman's translation, so range (). Both and are closed under the negative translation. (shrink)

An improvement on Horwich's so-called pseudo-proof of Russell 's principle of induction is offered, which, we believe, avoids certain objections to the former. Although strictly independent of our other work in this area, a connection can be made and in the final section we comment on this and certain questions regarding rationality, etc.

We postulate the Testing Principle : that individuals ''act like statisticians'' when they face uncertainty in a decision problem, ranking alternatives to the extent that available evidence allows. The Testing Principle implies that completeness of preferences, rather than the sure-thing principle , is violated in the Ellsberg Paradox. In the experiment, subjects chose between risky and uncertain acts in modified Ellsberg-type urn problems, with sample information about the uncertain urn. Our results show, consistent with the Testing Principle, that the uncertain (...) urn is chosen more often when the sample size is larger, holding constant a measure of ambiguity (proportion of balls of unknown colour in the urn). The Testing Principle rationalises the Ellsberg Paradox. Behaviour consistent with the principle leads to a reduction in Ellsberg-type violations as the statistical quality of sample information is improved, holding ambiguity constant. The Testing Principle also provides a normative rationale for the Ellsberg paradox that is consistent with procedural rationality. (shrink)

The account of meta-induction (G. Schurz, Hume’s problem solved: the optimality of meta-induction, MIT Press, Cambridge, 2019) proposes a two-step solution to the problem of induction. Step 1 consists in a mathematical a priori justification of the predictive optimality of meta-induction, upon which step 2 builds a meta-inductive a posteriori justification of object-induction based on its superior track record (Sect. 1). Sterkenburg (Br J Philos Sci, forthcoming. 10.1086/717068/) challenged this account by arguing that meta-induction (...) can only provide a (non-circular) justification of inductive predictions for now and for the next future, but not a justification of inductive generalizations (Sect. 2). This paper develops a meta-inductive method that does provide an a posteriori justification of inductive generalizations, in the form of exchangeability conditions (Sect. 3). In Sect. 4, a limitation of the proposed method is worked out: while the method can justify weakly lawlike generalizations, the justification of strongly lawlike generalizations (claimed to hold for all eternity) requires epistemic principles going beyond meta-induction based on predictive success. (shrink)

Some new double analogues of induction and transfinite recursion are given which yields a relatively simple proof of a result of Robert Cowen, [2] which in turn is a strengthening of an earlier result of Smullyan [1], which in turn gives a unified approach to Zorn's Lemma, the transfinite recursion theorem and certain results about ordinal numbers.