The purpose of this paper is to construct a non-finitary system of logic S, based on the theory of types, in which classical quantification theory holds without restriction and the axiom of reducibility holds with such slight restriction as is perhaps unlikely to interfere with the construction of classical mathematics. The system will be shown to be consistent.

For purposes of orientation, a rough description of the ontology of the system will first be given. The ‘individuals’ are expressions built up in the following way: ‘0’ is an individual, and if ϕ and ψ are individuals, so is ˹*ϕψ˺. The usual apparatus of truth functional connectives and quantifiers is employed, and one primitive four place predicate ‘S’. ˹Sϕψχω˺ says that ϕ is the result of writing ψ for all occurrences of χ in ω, where ϕ, ψ, χ and ω may be formulae, individuals, or members of a wider category called ‘expressions’ which includes individuals, formulae, and other things as well. (At first sight this looks like a confusion of use and mention, but the formation rules and rules of inference are so phrased that no ambiguity arises.)

The individuals are divided into types concentrically, so that type 0 has them all as members and type n includes type m for m > n. There is no highest type, but we shall find it convenient from the point of view of exposition to construct an infinity of ‘auxiliary’ systems Q(k), restricted to types ≦ k, before presenting the system S.

In this paper the symbolism, definitions and results of my two papers, namely A test for the existence of tautologies according to many-valued truth-tables (hereafter referred to as ET) and Note on truth-tables (hereafter referred to as TT) will be presupposed.

The problem whether two arbitrary truth-tables with finite number of elements are equal or not was reduced in TT to the question of equality of two identical tables in which different elements have been designated. However, no general method for testing the equality of truth-tables was given there, although some cases were discussed for which such a method is available. In the present paper we shall describe a general method using the considerations of ET and TT.

A computer handles λ-terms more easily if these are translated into combinatory terms. This translation process is called bracket abstraction. The simplest abstraction algorithm—the (fab) algorithm of Curry (see Curry and Feys [6])—is lengthy to implement and produces combinatory terms that increase rapidly in length as the number of variables to be abstracted increases.

There are several ways in which these problems can be alleviated:

(1) A change in order of the clauses in the algorithm so that (f) is performed as a last resort.

(2) The use of an extra clause (c), appropriate to βη reduction.

(3) The introduction of a finite number of extra combinators.

The original 1924 form of bracket abstraction of Schönfinkel [17], which in fact predates λ-calculus, uses all three of these techniques; all are also mentioned in Curry and Feys [6].

A technique employed by many computing scientists (Turner [20], Peyton Jones [16], Oberhauser [15]) is to use the (fab) algorithm followed by certain “optimizations” or simplifications involving extra combinators and sometimes special cases of (c).

Another is either to allow a fixed infinite set of (super-) combinators (Abdali [1], Kennaway and Sleep [10], Krishnamurthy [12], Tonino [19]) or to allow new combinators to be defined one by one during the abstraction process (Hughes [7] and [8]).

A final method encodes the variables to be abstracted as an n-tuple—this requires only a finite number of combinators (Curien [5], Statman [18]).

By using a provability predicate of PA, we define ThmPA(M) as the set of theorems of PA in a model M of PA. We say a model M of PA is (1) illusory if ThmPA(M) ⊈ ThmPA(ℕ), (2) heterodox if ThmPA(M) ⊈ TA, (3) sane if M ⊨ ConPA, and insane if it is not sane, (4) maximally sane if it is sane and ThmPA(M) ⊆ ThmPA(N) implies ThmPA(M) = ThmPA(N) for every sane model N of PA. We firstly show that M is heterodox if and only if it is illusory, and that ThmPA(M) ∩ TA ≠ ThmPA(ℕ) for any illusory model M. Then we show that there exists a maximally sane model, every maximally sane model satisfies ¬ConPA+ConPA, and there exists a sane model of ¬ConPA+ConPA which is not maximally sane. We define that an insane model is (5) illusory by nature if its every initial segment being a nonstandard model of PA is illusory, and (6) going insane suddenly if its every initial segment being a sane model of PA is not illusory. We show that there exists a model of PA which is illusory by nature, and we prove the existence of a model of PA which is going insane suddenly.

In this paper it will be shown that the three primitive symbols used by Lewis are independent in each one of his systems S1–S6.

Lemma I. “·” is not definable in terms of “∼” and “◊” in any one of the systems S1–S6.

Proof. This is obvious, since no binary operation can be defined by unary operations alone.

Lemma II. “∼” is not definable in terms of “˙” and “◊” in any one of the systems S1–S5.

It is well known that if a postulate LLCpp or a rule of procedure ├α→├Lα (from a thesis α of a considered system to infer a thesis Lα of that system) is added to Lewis's modal system S3, we get his system S4 (see [7], p. 148). It is also known that the addition of this rule to S2 and SI has the effect of converting these systems into the Gödel-Feys-von Wright system T (M). My purpose in this paper is first to draw attention to some other ways of converting S3 and S2 into S4 and T respectively, as well as to extend a theorem of Halldén on S3, S4 and S7 to S2, T and S6. The results reached will also apply to the systems S3.5, S5 and S7.5, where S3.5 and S7.5 are obtained, respectively, from S3 and S7 by the addition of the postulate CNLpLNLp; an answer will be given to the question of irreducible modalities in S3.5. Moreover, two results will be proved that bear on the problem whether the systems S2 and T can be axiomatized by means of a finite number of axiom schemata and material detachment as the only primitive rule of inference.

We point out that a group first order definable in a differentially closed field K of characteristic 0 can be definably equipped with the structure of a differentially algebraic group over K. This is a translation into the framework of differentially closed fields of what is known for groups definable in algebraically closed fields (Weil's theorem).

I restrict myself here to showing (Theorem 20) how one can find a large “differentially algebraic group chunk” inside a group defined in a differentially closed field. The rest of the translation (Theorem 21) follows routinely, as in [B].

What is, perhaps, of interest is that the proof proceeds at a completely general (soft) model theoretic level, once Facts 1–4 below are known.

Fact 1. The theory of differentially closed fields of characteristic 0 is complete and has quantifier elimination in the language of differential fields (+, ·,0,1, −1,d).

Fact 2. Affine n-space over a differentially closed field is a Noetherian space when equipped with the differential Zariski topology.

Fact 3. If K is a differentially closed field, k ⊆ K a differential field, and a and are in k, then a is in the definable closure of k ◡ iff a ∈ ‹› (where k ‹› denotes the differential field generated by k and).

Fact 4. The theory of differentially closed fields of characteristic zero is totally transcendental (in particular, stable).

The current paper studies the formal properties of the Global Reflection Principle, to wit the assertion “All theorems of $\mathrm {Th}$ are true,” where $\mathrm {Th}$ is a theory in the language of arithmetic and the truth predicate satisfies the usual Tarskian inductive conditions for formulae in the language of arithmetic. We fix the gap in Kotlarski’s proof from [15], showing that the Global Reflection Principle for Peano Arithmetic is provable in the theory of compositional truth with bounded induction only ( $\mathrm {CT}_0$ ). Furthermore, we extend the above result showing that $\Sigma _1$ -uniform reflection over a theory of uniform Tarski biconditionals ( $\mathrm {UTB}^-$ ) is provable in $\mathrm {CT}_0$ , thus answering the question of Beklemishev and Pakhomov [2]. Finally, we introduce the notion of a prolongable satisfaction class and use it to study the structure of models of $\mathrm {CT}_0$ . In particular, we provide a new model-theoretical characterization of theories of finite iterations of uniform reflection and present a new proof characterizing the arithmetical consequences of $\mathrm {CT}_0$ .

In this paper we consider decision problems for subclasses of Kr, the class of those formulas of pure quantification theory whose matrices are conjunctions of binary disjunctions of signed atomic formulas. If each of Q1, …, Qn is an ∀ or an ∃, then let Q1 … Qn be the class of those closed prenex formulas with prefixes of the form (Q1x1)… (Qnxn). Our results may then be stated as follows:

Theorem 1. The decision problem for satisfiability is solvable for the class ∀∃∀ ∩ Kr.

Theorem 2. The classes ∀∃∀∀ ∩ Kr and ∀∀∃∀ ∩ Kr are reduction classes for satisfiability.

Maslov [11] showed that the class ∃…∃∀…∀∃…∃ ∩ Kr is solvable, while the first author [1, Corollary 4] showed ∃∀∃∀ ∩ Kr and ∀∃∃∀ ∩ Kr to be reduction classes. Thus the only prefix subclass of Kr for which the decision problem remains open is ∀∃∀∃…∃∩ Kr.

The class ∀∃∀ ∩ Kr, though solvable, contains formulas whose only models are infinite (e.g., (∀x)(∃u)(∀y)[(Pxy ∨ Pyx) ∧ (¬ Pxy ∨ ¬Pyu)], which can be satisfied over the integers by taking P to be ≥). This is not the case for Maslov's class ∃…∃∀…∀∃…∃ ∩ Kr, which contains no formula whose only models are infinite ([2] [5]).

Theorem 1 was announced in [1, Theorem 4], but the proof sketched there is defective: Lemma 4 (p. 17) is incorrectly stated. Theorem 2 was announced in [9].

J. D. Monk has shown that for first order languages with finitely many variables there is no finite set of schema which axiomatizes the universally valid formulas. There are such finite sets of schema which axiomatize the formulas valid in all structures of some fixed finite size.

Kleene [7] and Kreisel [8] defined independently the countable (continuous) functionals. Kleene [7] defined the countable functionals of type k to be total functionals of type k acting in a continuous way when restricted to countable arguments of type k − 1. He also defined the associates for countable functionals. They are functions α: N → N containing information about how the functional acts on countable arguments. Kleene [7] showed that the countable functionals are closed under the computations derived from S1–S9 of his paper [6], and that every computable functional has a recursive associate.

Kreisel defined the continuous functionals to be equivalence-classes of associates. By his definition it is meaningless to let a continuous functional act upon anything but continuous arguments.

One disadvantage of Kleene's approach is that two different functionals may have the same associates We will later see that there may be two functionals φ1 and φ2 with the same associates but such that the relations

are not the same.

In more recent papers on the countable functionals it is normal to regard the hierarchy 〈Ct(k)〉kϵN of countable functionals as a type-structure such that the functionals in Ct(k + 1) are maps from Ct(k) to N(Ct(0) = N), see e.g. Bergstra [1] and Gandy and Hyland [3].

We will then enjoy the streamlined formalism of a type-structure in which S1–S9 have meaning, but avoid the ambiguities of Kleene's original approach.

We will presuppose a brief familiarity with the theory of the countable functionals.

Extending Gödel's Dialectica interpretation, we provide a functional interpretation of classical theories of positive arithmetic inductive definitions, reducing them to theories of finite-type functionals defined using transfinite recursion on well-founded trees.

We define a class of productiveσ-ideals of subsets of the Cantor space 2ω and observe that both σ-ideals of meagre sets and of null sets are in this class. From every productive σ-ideal we produce a σ-ideal of subsets of the generalized Cantor space 2κ. In particular, starting from meagre sets and null sets in 2ω we obtain meagre sets and null sets in 2ω, respectively. Then we investigate additivity, covering number, uniformity and cofinality of . For example, we show that

Our results generalizes those from [5].

Let (X, T) be a topological space and *X a nonstandard extension of X. Sets of the form *G. where G ∈ T, form a base for the “standard” topology ST on *X. The topological space (*X, ST) will be used to study compactifications of (X, T) in a systematic way.

We define elementary extension and elementary equivalence in Positive Logic.

We show that Blackwell determinacy in L(ℝ) implies determinacy in L(ℝ).

Any model of ZFC + GCH has a generic extension (made with a poset of size ℵ2) in which the following hold: there exists a-well ordering of the reals, The proof consists in iterating posets designed to change at will the guessing properties of ladder systems on ω1. Therefore, the study of such ladders is a main concern of this article.

We introduce a very weak language on p-adic fields K, which is just rich enough to have exactly the same definable subsets of the line K that one has using the ring language. (In our context, definable always means definable with parameters.) We prove that the only definable functions in the language are trivial functions. We also give a definitional expansion of in which K has quantifier elimination, and we obtain a cell decomposition result for -definable sets.

Our language can serve as a p-adic analogue of the very weak language (<) on the real numbers, to define a notion of minimality on the field of p-adic numbers and on related valued fields. These fields are not necessarily Henselian and may have positive characteristic.