Abstract We consider the version of Pure Inductive Logic which obtains for the language with equality and a single unary function symbol giving a complete characterization of the probability functions on this language which satisfy Constant Exchangeability.

Abstract We prove that: • if there is a model of IΔ0 + ¬exp with cofinal Σ1-definable elements and a Σ1 truth definition for Σ1 sentences, then IΔ0 + ¬exp + ¬BΣ1 is consistent, • there is a model of IΔ0 + Ω1 + ¬exp with cofinal Σ1-definable elements, both a Σ2 and a Π2 truth definition for Σ1 sentences, and for each n ≥ 2, a Σn truth definition for Σn sentences. The latter result is obtained by constructing a model with a recursive truth-preserving translation of Σ1 sentences into boolean combinations of sentences. We also present an old but previously unpublished proof of the consistency of IΔ0 + ¬exp + ¬BΣ1 under the assumption that the size parameter in Lessan's Δ0 universal formula is optimal. We then discuss a possible reason why proving the consistency of IΔ0 + ¬exp + ¬BΣ1 unconditionally has turned out to be so difficult.

Abstract We answer some problems set by Priest in [11] and [12], in particular refuting Priest's Conjecture that all LP-models of Th(ℕ) essentially arise via congruence relations on classical models of Th(ℕ). We also show that the analogue of Priest's Conjecture for IΔ0 + Exp implies the existence of truth definitions for intervals [0, a] ⊂eM ⊨ IΔ0 + Exp in any cut [0, a] ⊂eK ⊆eM closed under successor and multiplication.

This paper considers the problem and appropriateness of filling-in missing conditional probabilities in causal networks by the use of maximum entropy. Results generalizing earlier work of Rhodes, Garside & Holmes are proved straightforwardly by the direct application of principles satisfied by the maximum entropy inference process under the assumed uniqueness of the maximum entropy solution. It is however demonstrated that the implicit assumption of uniqueness in the Rhodes, Garside & Holmes papers may fail even in the case of inverted trees. An alternative approach to filling in missing values using the limiting centre of mass inference process is then described which does not suffer this shortcoming, is trivially computationally feasible and arguably enjoys more justification in the context when the probabilities are objective (for example derived from frequencies) than by taking maximum entropy values.

We introduce a generalization of ∈‐probability functions and a new correspondence with rational consequence relations. The rational consequence relations corresponding to the generalized ∈‐probability functions of maximum entropy are investigated and it is shown that in this case the analogous notion of ‘maximum entropy closure’ equals the rational closure, thus reconfirming the rational closure of a conditional knowledge base as the simplest, least prejudiced, rational consequence relation satisfying that knowledge base.

The purpose of this paper is to describe the underlying insights and results obtained by the authors, and others, in a series of papers aimed at modeling the distribution of 'natural' probability functions, more precisely the probability functions on {0, 1}n which we encounter naturally in the real world as subjects for statistical inference, by identifying such functions with large, random, sentences of the propositional calculus. We explain how this approach produces a robust parameterized family of priors, Jn, with several of the properties we might have hoped for in the context, for example marginalisation, invariance under (weak) renaming, and an emphasis on multivariate probability functions exhibiting high interdependence between features.

Abstract Can one extend crisp Peano arithmetic PA by a possibly many-valued predicate Tr(x) saying “xis true” and satisfying the “dequotation schema” for all sentences φ? This problem is investigated in the frame of Łukasiewicz infinitely valued logic.

Abstract Rational Pavelka logic extends Łukasiewicz infinitely valued logic by adding truth constants r̄ for rationals in [0. 1]. We show that this is a conservative extension. We note that this shows that provability degree can be defined in Łukasiewicz logic. We also give a counterexample to a soundness theorem of Belluce and Chang published in 1963.

Abstract The paper describes and proves completeness theorems for a series of proof systems formalizing common sense reasoning about uncertain knowledge in the case where this consists of sets of linear constraints on a probability function.

We observe that it follows from currently held conjectures in computational complexity that a wide class of inference processes considered for reasoning about uncertainty in AI are computationally infeasible.

Abstract We present a comprehensive study of the axiom schemas (induction and collection schemas for parameter free Σn formulas) and some closely related schemas.

In this note we shall be interested in the following problems. Problem 1. Can IΔ0 ⊢ ∀x∃y > x(y is prime)? Here I Δ0 is Peano arithmetic with the induction axiom restricted to bounded (i.e. Δ0) formulae. Problem 2. Can IΔ0 ⊢ Δ0 PHP? Here Δ0 PHP (Δ0 pigeonhole principle) is the schema for θ ∈ Δ0, or equivalently in IΔ0, for a Δ0 formula F(x,y) written . By obtaining partial solutions to Problem 2 we shall show that Problem 1 has a positive solution if IΔ0 is replaced by IΔ0 + ∀xxlog(x) exists. Our notation will be entirely standard (see for example [3] and [4]). In particular all logarithms will be to the base 2 and in expressions like log(x), (1 + ε)x, etc. we shall always mean the integer part of these quantities. Concerning Problem 2 we remark that it is shown in [5] that for k ∈ N and F ∈ Δ0, As far as we know this is the best result of this form, in that we do not know how to replace log(z)k by anything larger. However, as we shall show in Theorem 1, we can do much better if we increase the difference between the sizes of the domain and range of F. In what follows let M be a countable nonstandard model of IΔ0, and let be those subsets of M defined by Δ0 formulae with parameters from M. Theorem 1. For k ∈ N andF ∈ Δ0, Here log0(x) = x, logk + 1(x) = log(logk(x)). Proof. To simplify matters, consider first the case k = 1. So assume M ⊨ alog(a) exists and with and a > 1. The idea of the proof is the following.

Abstract This paper investigates the quantifier “there exist unboundedly many” in the context of first-order arithmetic. An alternative axiomatization is found for Peano arithmetic based on an axiom schema of regularity: The union of boundedly many bounded sets is bounded. We also obtain combinatorial equivalents of certain second-order theories associated with cuts in nonstandard models of arithmetic.

The results in this paper were motivated by the following result due to R. Solovay. Theorem 1 (Solovay). Let M be a nonstandard model of Peano's first order axioms P and let I ⊂e M (i.e. ϕ ≠ ⊂ M and I is closed under < and successor). Then for each of the functions we can define J ⊆e I in ‹M, I› such that J is closed under that function. (∣x∣ denotes [log2(x)].) Proof. Just notice that the cuts defined by are successively closed under In view of Theorem 1, the following question was raised by R. Solovay: Can we define J ⊆ I in ‹M, I› such that J is closed under exponentiation? In Theorem 2 we show that the answer is “no”. Theorem 3 is based on Theorem 2 and extends the technique to cuts which are models of subsystems of P. To prove both theorems we shall need an estimate due to R. Parikh (see [1], especially the proof of Theorem 2.2a). For the sake of completeness, and also to introduce some notation we shall sketch Parikh's estimate in the next section. At all times we shall give the easiest estimates which still work rather than the sharpest ones.

Let θ(ν) be a formula in the first-order language of arithmetic and let In this note we study the relationship between the schemas I′ and I+. Our interest in I+ lies in the fact that it is ostensibly a more reasonable schema than I′. For, if we believe the hypothesis of I+(θ) then to verify θ(n) only requires at most 2log2(n) steps, whereas assuming the hypothesis of I′(θ) we require n steps to verify θ(n). In the physical world naturally occurring numbers n rarely exceed 10100. For such n applying 2log2(n) steps is quite feasible whereas applying n steps may well not be. Of course this is very much an anthropomorphic argument so we would expect that it would be most likely to be valid when we restrict our attention to relatively simple formulas θ. We shall show that when restricted to open formulas I+ does not imply I′ but that this fails for the classes Σn, Πn, n ≥ 0. We shall work in PA−, where PA− consists of Peano's Axioms less induction together with ∀u, w(u + w = w + u ∧ u · w = w · u), ∀u, w, t ((u + w) + t = u + (w + t) ∧ (u · w) · t = u · (w · t)), ∀u, w, t(u · (w + t) = u · w + u · t), ∀u, w(u ≤ w ↔ ∃t(u + t = w)), ∀u, w(u ≤ w ∨ w ≤ u), ∀u, w, t(u + w = u + t → w = t). The reasons for working with PA− rather than Peano's Axioms less induction is that our additional axioms, whilst intuitively reasonable, will not necessarily follow from some of the weaker forms of I+ which we shall be considering. Of course PA− still contains those Peano Axioms which define + and Notice that, trivially, PA− ⊦ I′(θ) → I+(θ) for any formula θ.

In this paper we shall outline a purely model theoretic method for obtaining independence results for Peano's first order axioms (P). The method is of interest in that it provides for the first time elementary combinatorial statements about the natural numbers which are not provable in P. We give several examples of such statements. Central to this exposition will be the notion of an indicator. Indicators were introduced by L. Kirby and the author in [3] although they had occurred implicitly in earlier papers, for example Friedman [1]. The main result on indicators which we shall need (Lemma 1) was proved by Laurie Kirby and the author in the summer of 1976 but it was not until early in the following year that the author realised that this lemma could be used to give independence results. The first combinatorial independence results obtained were essentially statements about certain finite games and consequently were not immediately meaningful (see Example 2). This shortcoming was remedied by Leo Harrington who, upon hearing an incorrect version of our results, noticed a beautifully simply independent combinatorial statement. We outline this result in Example 3. An alternative, more detailed, proof may be found in [5]. Clearly Laurie Kirby and Leo Harrington have made a very significant contribution to this paper and we wish to express our sincere thanks to them.

In this paper we show that in Zermelo-Fraenkel set theory (ZF) sets of reals are determinate. Before proceeding to the proof it will be helpful to consider some previous work in this area. The first major result was obtained by Gale and Stewart [3] who showed that in ZF open games are determinate. This was then successively improved by Wolfe [4] to (and so of course ) and then by Morton Davis [1] to . The results of Morton Davis further showed that countable unions of sufficiently ‘simple’ determinate sets are also determinate. At this time, however, sets did not appear sufficiently simple for this method to be applied in order to get determinacy. The next major advance was made by D. A. Martin who showed, using indiscernibles, that with large cardinal assumptions games are equivalent to certain open games (i.e., player I (II) has a winning strategy for the game iff I (II) has a winning strategy for the open game). Thus, by the Gale–Stewart result, games are determinate. Martin's result also showed that under these large cardinal assumptions sets are sufficiently simple for the Morton Davis method to be applied to them.