This paper is the first of several works: the matter is the systematic rewriting of usual results of ordinal notations, using Π½-logic. The purpose of these articles is already realized in Π½-logic, in a relatively abstract form; also, they are examples for Π½-logic. The first and second articles in this series are complete versions of unpublished results that one of authors had announced in 1976.

Veblen introduced his hierarchy in 1908. The hierarchy has since been widely used in proof theory; in fact, what is actually needed is the more natural hierarchy: , with (not necessarily a Cantor normal form) and K the Veblen hierarchy.

We shall show:

i) φ is in fact a two-variables functor (denoted by V in the text) commuting with direct limits and with pull-backs.

ii) The property of commutation with pull-backs permits one to give a representation of each ordinal x < φα(0) by means of a finite sequence of ordinals < α. This representation is independent of α it is ⊆ x, and can be used in the building up of notations systems. This representation is the “blowing-up” of the Cantor normal form, and it corresponds exactly to the denotation of ordinals < φα(0) by means of the functions (φβ)β<α.

We present a formal theory of propositions and combinator terms, and in this theory we give an interpretation of Martin-Löf's type theory. The construction of the interpretation is inspired by the semantics for type theory, but it can also be viewed as a formalized realizability interpretation.

The universe of sets, V, is usually seen as an entity structured in successive levels, each level being made up of objects and collections of objects belonging to the previous levels. This process of obtaining sets and axioms for set theory can be seen in Scott [74] and Shoenfield [77].

The approach we want to take differs from the previous one very strongly: the seeds from which we want to generate our universe of classes are to be the one-variable predicates (given by one-free-variable formulas) of the formal language we shall be using. In other words, any one-variable predicate of the language is to be represented as a class in our universe. In this sense, we view our theory as being about a self-referential language, a language whose predicates refer to objects which are predicates of the language itself.

We want, in short, a system such that: (i) any predicate may be represented by an object to be studied by the theory itself; (ii) the axioms for the theory may be derived from the general principle that we are dealing with a language that aims at describing its own predicates; and (iii) the theory should be strong enough to derive ZFC and suggest answers to the existence of large cardinals and to the continuum hypothesis.

An objection to such a project arises immediately: in view of the Russell-Zermelo paradox, how is it possible to have all predicates of the language as elements of the universe? This objection will be easy to deal with: we shall provide our language with a type structure to avoid paradox.

Let A and B be subsets of the space 2N of sets of natural numbers. A is said to be Wadge reducible to B if there is a continuous map Φ from 2N into 2N such that A = Φ−1 (B); A is said to be monotone reducible to B if in addition the map Φ is monotone, that is, a ⊂ b implies Φ(a) ⊂ Φ(b). The set A is said to be monotone if a ∈ A and a ⊂ b imply b ∈ A. For monotone sets, it is shown that, as for Wadge reducibility, sets low in the arithmetical hierarchy are nicely ordered. The sets are all reducible to the ( but not ) sets, which are in turn all reducible to the strictly sets, which are all in turn reducible to the strictly sets. In addition, the nontrivial sets all have the same degree for n ≤ 2. For Wadge reducibility, these results extend throughout the Borel hierarchy. In contrast, we give two natural strictly monotone sets which have different monotone degrees. We show that every monotone set is actually positive. We also consider reducibility for subsets of the space of compact subsets of 2N. This leads to the result that the finitely iterated Cantor-Bendixson derivative Dn is a Borel map of class exactly 2n, which answers a question of Kuratowski.

We investigate the provability or nonprovability of certain ordinary mathematical theorems within certain weak subsystems of second order arithmetic. Specifically, we consider the Cauchy/Peano existence theorem for solutions of ordinary differential equations, in the context of the formal system RCA0 whose principal axioms are comprehension and induction. Our main result is that, over RCA0, the Cauchy/Peano Theorem is provably equivalent to weak König's lemma, i.e. the statement that every infinite {0, 1}-tree has a path. We also show that, over RCA0, the Ascoli lemma is provably equivalent to arithmetical comprehension, as is Osgood's theorem on the existence of maximum solutions. At the end of the paper we digress to relate our results to degrees of unsolvability and to computable analysis.

Cette note est consacrée à quelques compléments à mon article [6], que le lecteur est supposé avoir sous les yeux, et qui traite de la propriété de recouvrement fini, de Keisler. Je rappelle seulement ici que:

a) La définition originale est la suivante: une théorie complète T n'a pas la p.r.f. si à toute formule f(x, ȳ) de son langage est associé un entier n, de sorte que tout ensemble (fini!) {f(x, ā1), …, f(x, ās)}, où les āi; sont des paramètres extraits d'un modèle M de T, soit consistant dès que ses parties à n éléments le sont. Une théorie sans p.r.f. satisfait done un renforcement du théorème de compacité; elle est en ce sens plus simple qu'une théorie avec p.r.f.

b) T n'a pas la p.r.f. si et seulement si elle est stable (i.e. tout type sur un modèle M de T est définissable; à toute formule f(x, ȳ) est associée une formule g(ȳ, ā) à paramètres dans M, telle que les de M pour lesquels f(x, ) est dans le type en question soient précisément ceux qui vérifient g(ȳ, ā)), et si en outre on peut exprimer par une formule sur le paramètre ā que g(ȳ, ā) définit un f-type consistant: à f1(x, ȳ), …, fs(x, ȳ), g1(ȳ, ), …, gs(ȳ, ) est associé une formule h(), telle que pour tout ā de tout modèle M de T, ā satisfasse h si et seulement si l'ensemble de tous les fi(x, ), où est dans M et satisfait gi(ȳ, ā), est consistant.

J. Barbanel [1] characterized the class of cardinals fixed by an elementary embedding induced by a normal ultrafilter on Pκλ assuming that κ is supercompact. In this paper we shall prove the same results from the weaker hypothesis that κ is strongly compact and the ultrafilter is fine.

We work in ZFC throughout. Our set-theoretic notation is quite standard. In particular, if X is a set, ∣X∣ denotes the cardinality of X and P(X) denotes the power set of X. Greek letters will denote ordinals. In particular γ, κ, η and γ will denote cardinals. If κ and λ are cardinals, then λ<κ is defined to be supγ<κγγ. Cardinal exponentiation is always associated from the top. Thus, for example, 2λ<κ means 2(λ<κ). V denotes the universe of all sets. If M is an inner model of ZFC, ∣X∣M and P(X)M denote the cardinality of X in M and the power set of X in M respectively.

We review the basic facts on fine ultrafilters and the corresponding elementary embeddings. (For detail, see [2].)

Definition. Assume κ and λ are cardinals with κ ≤ λ. Then, Pκλ = {X ⊂ λ∣∣X∣ < κ}.

It is important to note that ∣Pκλ∣ = λ< κ.

An ideal I defined on a group G is called idempotent if for every A ∈ I, {g ∈ G:Ag−1 ∉ ∈ I} ∈ I. We show that a countably complete idempotent ideal on an abelian group cannot be prime but may have strong saturation properties.

The purpose of the present paper is to give a new, simple proof of the theorem of M. Davis, H. Putnam and J. Robinson [1961], which states that every recursively enumerable relation A(a1, …, an) is exponential diophantine, i.e. can be represented in the form

where a1 …, an, x1, …, xm range over natural numbers and R and S are functions built up from these variables and natural number constants by the operations of addition, A + B, multiplication, AB, and exponentiation, AB. We refer to the variables a1,…,an as parameters and the variables x1 …, xm as unknowns.

Historically, the Davis, Putnam and Robinson theorem was one of the important steps in the eventual solution of Hilbert's tenth problem by the second author [1970], who proved that the exponential relation, a = bc, is diophantine, and hence that the right side of (1) can be replaced by a polynomial equation. But this part will not be reproved here. Readers wishing to read about the proof of that are directed to the papers of Y. Matijasevič [1971a], M. Davis [1973], Y. Matijasevič and J. Robinson [1975] or C. Smoryński [1972]. We concern ourselves here for the most part only with exponential diophantine equations until §5 where we mention a few consequences for the class NP of sets computable in nondeterministic polynomial time.

c.c.c. posets are characterised in terms of -generic conditions. This characterisation can be applied to get simple proofs of many facts about c.c.c. forcing including Con(MA + ┐CH).

The purpose of this paper is to establish a connection between the complexity of κ-ultrafilters over a measurable cardinal κ, and the existence of ascending Rudin-Keisler chains of κ-ultrafilters and of inner models with several measurable cardinals.

If V is a model of ZFC + “There exists a measurable cardinal κ”, then V satisfies “There exists a normal κ-ultrafilter”, that is to say a “simple” κ-ultrafilter. The only known examples of “complex” κ-ultrafilters have been constructed by Kanamori [2], Ketonen [4] and Kunen (cf. [2]) with stronger hypotheses than measurability: compactness or supercompactness. Using the notions of skies and constellations defined by Kanamori [2] for the measurable case, and which witness the complexity of a κ-ultrafilter, we shall show the necessity of such assumptions, namely:

Theorem 1. If λ < κ is a strongly inaccessible cardinal, the existence of a κ-ultrafilter with more than λ constellations implies that there is an inner model with two measurable cardinals if λ = ω and λ + 1 measurable cardinals otherwise.

Theorem 2. Let θ < κ be an arbitrary ordinal. If there is a κ-ultrafilter such that the order-type of its skies is greater than ωθ, then there exists an inner model with θ + 1 measurable cardinals.

And as a corollary, we obtain:

Theorem 3. Let μ < κ be a regular cardinal. If there exists a κ-ultrafilter containing the closed-unbounded subsets of κ and {α < κ: cf(α) = μ}, then there is an inner model with two measurable cardinals if μ = ω, and μ + 1 measurable cardinals otherwise.

Problems of computing probabilities of statements about large, finite structures have become an important subject area of finite combinatorics. Within the last two decades many researchers have turned their attention to such problems and have developed a variety of methods for dealing with them. Applications of these ideas include nonconstructive existence proofs for graphs with certain properties by showing the properties occur with nonzero probabilities (for examples see Erdös and Spencer [ES] and Bollobás [Bo]), and determination of average running times for sorting algorithms by computing asymptotic probabilities of statements about permutations (see Knuth [Kn]). Two types of techniques recur in solutions to such problems: probabilistic techniques, such as those used by Erdös and Spencer [ES], and classical assymptotic techniques, such as those surveyed by Bender [Be] and de Bruijn [Br]. Studying this body of techniques, one notices that characteristics of these problems suggest certain methods of solution, in much the same way that the form of an integrand may suggest certain substitutions. The question arises, then, as to whether there is a systematic way to approach these problems: is there an algorithm for computing asymptotic probabilities? I will show that the answer is “no”—for any reasonable formulation, the problem of computing asymptotic probabilities is undecidable.

The main theorem of the paper is Theorem 1.6, which says that there is a finitely axiomatizable class in which every first order sentence has an asymptotic probability of 0 or 1—i.e., is almost always true or almost always false in finite structures—but for which the problem of deciding whether a sentence has asymptotic probability 0 or 1 is undecidable. Heretofore, classes known to have such a 0-1 law have had decidable asymptotic probability problems (see Lynch [Ly] for examples and a discussion of previous work in the area).

In 1965 Zadeh introduced the concept of fuzzy sets. The characteristic of fuzzy sets is that the range of truth value of the membership relation is the closed interval [0, 1] of real numbers. The logical operations ⊃, ∼ on [0, 1] which are used for Zadeh's fuzzy sets seem to be Łukasiewciz's logic, where p ⊃ q = min(1, 1 − p + q), ∼ p = 1 − p. L. S. Hay extended in [4] Łukasiewicz's logic to a predicate logic and proved its weak completeness theorem: if P is valid then P + Pn is provable for each positive integer n. She also showed that one can without losing consistency obtain completeness of the system by use of additional infinitary rule.

Now, from a logical standpoint, each logic has its corresponding set theory in which each logical operation is translated into a basic operation for set theory; namely, the relation ⊆ and = on sets are translation of the logical operations → and ↔. For Łukasiewicz's logic, P Λ (P ⊃ Q). ⊃ Q is not valid. Translating it to the set version, it follows that the axiom of extensionality does not hold. Thus this very basic principle of set theory is not valid in the corresponding set theory.

The following is part of a series of papers on theories for (iterated) admissible sets (cf. [10], [11], [12], [14], [15]). Although these theories are weak subsystems of Zermelo-Fraenkel set theory, they allow one to formalize and prove a fair amount of definability theory and generalized recursion theory. Using this machinery it is in general not very hard to establish the connections between theories for admissible sets and (for example) systems of second order arithmetic. A proof-theoretic analysis of theories for admissible sets therefore provides quite a uniform and powerful framework for the proof-theoretic treatment of many systems of set theory, second order arithmetic and constructive mathematics (see [12] and [15]). The strongest result in this direction so far is the pair of proof-theoretic equivalences

where T0 is Feferman's system for explicit mathematics of [5] and [6], (-CA) + (BI) is the usual system of second order arithmetic with the axiom of -comprehension and bar induction and KPi is Kripke-Platek set theory with ∈-induction

for arbitrary formulas and the additional axiom

.

The least standard model of KPi is L(i0) where i0 is the first recursively inaccessible ordinal.

In this paper we are mainly interested in the theory KPi0 which results from KPi by severely restricting the principles of induction. Basically, complete induction on the natural numbers

is allowed only for ∆0-formulas, and (IND∈) is omitted completely.

We define a hierarchy on the regular types of an ω-stable nonmultidimensional theory, using generalised notions of algebraic and strongly minimal formulae. As an application we show that any resplendent model of an ω-stable finite-dimensional theory is saturated.

In classical prepositional calculus for each proposition A(p) the following holds: ⊢A(p) ↔ A3(p). In this paper we consider what remains of this in the intuitionistic case. It turns out that for each proposition A(p) the following holds: there is an n ∈ N such that

As a byproduct of the proof we give some theorems which may be useful elsewhere in propositional calculus.

A countable group is ℵ0-categorical if it is characterized up to isomorphism among all countable groups by its first order theory. We investigate countable ℵ0-categorical groups which are characteristically simple and have proper subgroups of finite index. We determine such groups up to isomorphism (Corollary 4 to Proposition 3), and we show that their theories are finitely axiomatizable (Proposition 2).

Let K be a finite nonabelian simple group. In §3 we construct from K two denumberable groups, K* and K#, and use them to classify countable direct limits of finite Cartesian powers of K (Proposition 1). The results of §3 are used in §4 to show that K* and K# are ℵ0-categorical and to find axioms for their theories. By Corollary 2 to Proposition 2, K* and K# are counterexamples to the conjecture of U. Feigner [3, p. 309] that ℵ0-categorical groups are FC-solvable. Also in §4 the results mentioned in the first paragraph are proved. §2 is devoted to preliminary lemmas about finite Cartesian powers of K.

A characteristic subgroup of a group G is a subgroup which is mapped onto itself by all automorphisms of G. G is characteristically simple if its only characteristic subgroups are itself and the identity subgroup. Each characteristic subgroup of a group is a union of orbits of the automorphism group of the group. If G is ℵ0-categorical, then as the automorphism group of G has only a finite number of orbits, G has only a finite number of characteristic subgroups.

From the moment choice sequences appear in Brouwer's writings, they do so as elements of a spread. This led Kreisel to take the so-called axiom of spreaddata as the basic axiom in a formal theory of choice sequences (Kreisel [1965, pp. 133–136]). This axiom expresses the idea that to be given a choice sequence means to be given a spread to which the choice sequence belongs. Subsequently, however, it was discovered that there is a formal clash between this axiom and closure of the domain of choice sequences under arbitrary (lawlike) continuous operations (Troelstra [1968]). For this reason, the formal system CS was introduced (Kreisel and Troelstra [1970]), in which spreaddata is replaced by analytic data. In this system CS, the domain of choice sequences is closed under all continuous operations, and therefore it provides a workable basis for intuitionistic analysis. But the problem whether the axiom of spreaddata is compatible with closure of the domain of choice sequences under the continuous operations from a restricted class, which is still rich enough to validate the typical axioms of continuous choice, remained open. It is precisely this problem that we aim to discuss in this paper.

Recall that a spread is a (lawlike, inhabited) decidable subtree S of the tree N< N of all finite sequences, having all branches infinite:

This paper develops in certain directions the work of Meyer in [3], [4], [5] and [6] (see also Routley [10] and Asenjo [11]). In those works, Peano's axioms for arithmetic were formulated with a logical base of the relevant logic R, and it was proved finitistically that the resulting arithmetic, called R#, was absolutely consistent. It was pointed out that such a result escapes incautious formulations of Gödel's second incompleteness theorem, and provides a basis for a revived Hilbert programme. The absolute consistency result used as a model arithmetic modulo two. Modulo arithmetics are not ordinarily thought of as an extension of Peano arithmetic, since some of the propositions of the latter, such as that zero is the successor of no number, fail in the former. Consequently a logical base which, unlike classical logic, tolerates contradictory theories was used for the model. The logical base for the model was the three-valued logic RM3 (see e.g. [1] or [8]), which has the advantage that while it is an extension of R, it is finite valued and so easier to handle.

The resulting model-theoretic structure (called in this paper RM32) is interesting in its own right in that the set of sentences true therein constitutes a negation inconsistent but absolutely consistent arithmetic which is an extension of R#. In fact, in the light of the result of [6], it is an extension of Peano arithmetic with a base of a classical logic, P#. A generalisation of the structure is to modulo arithmetics with the same logical base RM3, but with varying moduli (called RM3i here).

We prove that if every uncountable model of a first-order theory T is ω-saturated and T is superstable then T is categorical in some infinite power.