By Solovay’s celebrated completeness result [31] on formal provability we know that the provability logic ${\textbf {GL}}$ describes exactly all provable structural properties for any sound and strong enough arithmetical theory with a decidable axiomatisation. Japaridze generalised this result in [22] by considering a polymodal version ${\mathsf {GLP}}$ of ${\textbf {GL}}$ with modalities $[n]$ for each natural number n referring to ever increasing notions of provability. Modern treatments of ${\mathsf {GLP}}$ tend to interpret the $[n]$ provability notion as “provable in a base theory T together with all true $\Pi ^0_n$ formulas as oracles.” In this paper we generalise this interpretation into the transfinite. In order to do so, a main difficulty to overcome is to generalise the syntactical characterisations of the oracle formulas of complexity $\Pi ^0_n$ to the hyper-arithmetical hierarchy. The paper exploits the fact that provability is $\Sigma ^0_1$ complete and that similar results hold for stronger provability notions. As such, the oracle sentences to define provability at level $\alpha $ will recursively be taken to be consistency statements at lower levels: provability through provability whence the name of the paper. The paper proves soundness and completeness for the proposed interpretation for a wide class of theories, namely for any theory that can formalise the recursion described above and that has some further very natural properties. Some remarks are provided on how the recursion can be formalised into second order arithmetic and on lowering the proof-theoretical strength of these systems of second order arithmetic.

Let ${\cal N}\left( G \right)$ be the maximal normal definable torsion-free subgroup of a group G definable in an o-minimal structure M. We prove that the quotient $G/{\cal N}\left( G \right)$ has a maximal definably compact subgroup K, which is definably connected and unique up to conjugation. Moreover, we show that K has a definable torsion-free complement, i.e., there is a definable torsion-free subgroup H such that $G/{\cal N}\left( G \right) = K \cdot H$ and $K\mathop \cap \nolimits^ \,H = \left\{ e \right\}$. It follows that G is definably homeomorphic to $K \times {M^s}$ (with $s = {\rm{dim}}\,G - {\rm{dim}}\,K$), and homotopy equivalent to K. This gives a (definably) topological reduction to the compact case, in analogy with Lie groups.

We characterize the ω-stable theories all of whose countable models admit decidable presentations. In particular, we show that for a countable ω-stable T, every countable model of T admits a decidable presentation if and only if all n-types in T are recursive and T has only countably many countable models. We further characterize the decidable models of ω-stable theories with countably many countable models as those which realize only recursive types.

By means of an Ehrenfeucht-Mostowski construction we obtain an automorphism theorem for a syntactically characterized class of Laa-theories comprising in particular the finitely determinate ones. Examples of Laa-theories with only rigid models show this result to be optimal with respect to a classification in terms of prenex quantifier type: Rigidity is seen to hinge on quantification of type … ∀ … stat … permitting of the parametrization of families of disjoint stationary systems by the elements of the universe.

Some highly saturated models of Peano Arithmetic are constructed in this paper, which consists of two independent sections. In § 1 we answer a question raised in [10] by constructing some highly saturated, rather classless models of PA. A question raised in [7], [3], ]4] is answered in §2, where highly saturated, nonstandard universes having no bad cuts are constructed.

Highly saturated, rather classless models of Peano Arithmetic were constructed in [10]. The main result proved there is the following theorem. If λ is a regular cardinal and is a λ-saturated model of PA such that ∣M∣ > λ, then has an elementary extension of the same cardinality which is also λ-saturated and which, in addition, is rather classless. The construction in [10] produced a model for which cf() = λ+. We asked in Question 5.1 of [10] what other cofinalities could such a model have. This question is answered here in Theorem 1.1 of §1 by showing that any cofinality not immediately excluded is possible. Its proof does not depend on the theorem from [10]; in fact, the proof presented here gives a proof of that theorem which is much simpler and shorter than the one in [10].

Recursively saturated, rather classless κ-like models of PA were constructed in [9]. In the case of singular κ such models were constructed whenever cf(κ) > ℵ0; no additional set-theoretic hypothesis was needed.

We develop the theory of germs of generic functions in simple theories. Starting with an algebraic quadrangle (or other similar hypotheses), we obtain an “almost” generic group chunk, where the product is defined up to a bounded number of possible values. This is the first step towards the proof of the group configuration theorem for simple theories, which is completed in [3].

Research in AI has recently begun to address the problems of nondeductive reasoning, i.e., the problems that arise when, on the basis of approximate or incomplete evidence, we form well-reasoned but possibly false judgments. Attempts to stimulate such reasoning fall into two main categories: the numerical approach is based on probabilities and the nonnumerical one tries to reconstruct nondeductive reasoning as a special type of deductive process. In this paper, we are concerned with the latter usually known as nonmonotonic deduction, because the set of theorems does not increase monotonically with the set of axioms.

It is generally acknowledged that nonmonotonic (n.m.) formalisms (e.g., [C], [MC1], [MC2] [MD], [MD-D], [Rl], [R2], [S]) are plagued by a number of difficulties. A key issue concerns the fact that most systems do not produce an axiomatizable set of validities. Thus, the chief objective of this paper is to develop an alternative approach in which the set of n.m. inferences, which somehow qualify as being deductively sound, is r.e.

The basic idea here is to reproduce the situation in First Order Logic where the metalogical concept of deduction translates into the logical notion of material implication. Since n.m. deductions are no longer truth preserving, our way to deal with a change in the metaconcept is to extend the standard logic apparatus so that it can reflect the new metaconcept. In other words, the intent is to study a concept of nonmonotonic implication that goes hand in hand with a notion of n.m. deduction. And in our case, it is convenient that the former be characterized within the more tractable context of monotonic logic.

It was conjectured by Halpern and Kapron (Annals of Pure and Applied Logic, vol. 69, 1994) that frame satisfiability of propositional modal formulas is incomparable in expressive power to both (Ackermann) and (Bernays-Schönfinkel). We prove this conjecture. Our results imply that (Ackermann) and (Bernays-Schönfinkel) are incomparable in expressive power, already on finite graphs. Moreover, we show that on ordered finite graphs, i.e., finite graphs with a successor, (Bernays-Schönfinkel) is strictly more expressive than (Ackermann).

Since 1934 various different techniques for natural deduction have been developed by Gentzen, Jaśkowski, Rosser, Quine, and others (see [1], pp. 147–167; [2], especially footnotes 1, 3, and 4; and [3], pp. 75-83, 96-107, and 289-294). It has been pointed out to me by Professor Donald Kalish of U.C.L.A. that the restrictions placed upon Universal Generalization (UG) and Existential Instantiation (EI) in [3] force one to construct a less natural proof than seems desirable for such arguments as

(cf. [3], p. 139, and [1], pp. 175f.) It is my purpose in this note to formulate an alternative restriction on UG which will permit a more natural proof for such arguments, and to prove the consistency of the altered rule.

In the notation of [3], “The expression ‘Φμ’ will denote any propositional function in which there is at least one free occurrence of the variable denoted by ‘μ’. The expression ‘Φν’ will denote the result of replacing all free occurrences of μ in Φμ by ν, with the added proviso that when ν is a variable it must occur free in Φν at all places at which μ occurs free in Φμ.” ([3], p. 100.) The statement of EI is relatively unrestricted; being

provided that ν is a variable which occurs free in no earlier step.” ([3], p. 104.)

It has been shown by Lewis and Langford that the postulate B8,

is not deducible in SI. From this it follows that neither are the paradoxes of strict implication deducible in that system. However, the following weaker—but perhaps philosophically equally important—analogues are deducible:

For a countable structure , the spectrum is the set of Turing degrees of isomorphic copies of . For a complete elementary first order theory T, the spectrum is the set of Turing degrees of models of T. We answer a question from [1] by showing that there is an atomic theory T whose spectrum does not match the spectrum of any structure.

The following theorems on the structure inside nonrecursive truth-table degrees are established: Dëgtev's result that the number of bounded truth-table degrees inside a truth-table degree is at least two is improved by showing that this number is infinite. There are even infinite chains and antichains of bounded truth-table degrees inside every truth-table degree. The latter implies an affirmative answer to the following question of Jockusch: does every truth-table degree contain an infinite antichain of many-one degrees? Some but not all truth-table degrees have a least bounded truth-table degree. The technique to construct such a degree is used to solve an open problem of Beigel, Gasarch and Owings: there are Turing degrees (constructed as hyperimmune-free truth-table degrees) which consist only of 2-subjective sets and therefore do not contain any objective set. Furthermore, a truth-table degree consisting of three positive degrees is constructed where one positive degree consists of enumerable semirecursive sets, one of coenumerable semirecursive sets and one of sets, which are neither enumerable nor coenumerable nor semirecursive. So Jockusch's result that there are at least three positive degrees inside a truth-table degree is optimal. The number of positive degrees inside a truth-table degree can also be some other odd integer as for example nineteen, but it is never an even finite number.

In [12]. T. Scanlon proved a quantifier elimination result for valued D-fields in a three-sorted language by using angular component functions. Here we prove an analogous theorem in a different language which was introduced by F. Delon in her thesis. This language allows us to lift the quantifier elimination result to a one-sorted language by a process described in the Appendix. As a byproduct, we state and prove a “positivstellensatz” theorem for the differential analogue of the theory of real-series closed fields in the valued D-field setting.

The following strong form of density of definable types is introduced for theories T admitting a fibered dimension function d: given a model M of T and a definable set X ⊆ Mn, there is a definable type p in X, definable over a code for X and of the same d-dimension as X. Both o-minimal theories and the theory of closed ordered differential fields (CODF) are shown to have this property. As an application, we derive a new proof of elimination of imaginaries for CODF.

We introduce a notion of ideal type such that any two ideals with the same ideal type are isomorphic. From this we infer, under the axiom t = h, that each ideal which consists of all nowhere Ramsey sets contained in some family of infinite subsets of natural numbers is isomorphic with the ideal of all nowhere Ramsey sets.

In this paper we give the complete list of the functions of one variable with some of their properties, and lists of functions corresponding to various properties of sum, product, implication, and equivalence. The range of the variables as well as that of functional values will be о (false), ½, 1 (true). As an application we consider Frege's, Russell's and Heyting's systems in ternary logic. The proofs are mostly omitted as obvious if sometimes laborious.

Functions will be denned by matrices: e.g. F(p, q)