Assuming the existence of a weakly compact hypermeasurable cardinal we prove that in some forcing extension ℵω is a strong limit cardinal and ℵω+2 has the tree property. This improves a result of Matthew Foreman (see [2]).

This paper developed from Shelah's proof of a zero-one law for the complexity class “choiceless polynomial time,” defined by Shelah and the authors. We present a detailed proof of Shelah's result for graphs, and describe the extent of its generalizability to other sorts of structures. The extension axioms, which form the basis for earlier zero-one laws (for first-order logic, fixed-point logic, and finite-variable infinitary logic) are inadequate in the case of choiceless polynomial time; they must be replaced by what we call the strong extension axioms. We present an extensive discussion of these axioms and their role both in the zero-one law and in general.

This paper continues joint work of the authors with P. Clote, R. Soare and S. Wainer (Annals of Pure and Applied Logic, vol. 31 (1986), pp. 145–163). An element x of the Cantor space 2ω is said have rank α in the closed set P if x is in Dα(P)/Dα + 1(P), where Dα is the iterated Cantor-Bendixson derivative. The rank of x is defined to be the least α such that x has rank a in some set. The main result of the five-author paper is that for any recursive ordinal λ + n (where λ is a limit and n is finite), there is a point with rank λ + n which is Turing equivalent to O(λ + 2n) All ranked points constructed in that paper are singletons. We now construct a ranked point which is not a singleton. In the previous paper the points of high rank were also of high hyperarithmetic degree. We now construct points with arbitrarily high rank. We also show that every nonrecursive RE point is Turing equivalent to an RE point of rank one and that every nonrecursive point is Turing equivalent to a hyperimmune point of rank one. We relate Clote's notion of the height of a singleton in the Baire space with the notion of rank. Finally, we show that every hyperimmune point x is Turing equivalent to a point which is not ranked.

In the first-order language, quantifiers (∀x) and (∃#) are understood “to say” that “for all elements” and “there is at least one element such that …”, respectively. We are interested in changing the interpretation to “for all elements with fewer than κ exceptions” and “there are at least κ elements such that”, respectively, where κ is a cardinal. We call this the κ-interpretation of the quantifiers.1 The first question which presents itself is “What is the relationship between the κ-interpretation and the λ-interpretation?” For instance, is a formula valid under one interpretation also valid in all other interpretations? In the second section, it will be shown that as far as infinite interpretations, i.e. κ-interpretations for infinite cardinals κ, are concerned, the validity of a formula is preserved. Actually, a more general result is obtained there by model theoretic methods.

We prove the consistency of together with the existence of a -definable mad family, answering a question posed by Friedman and Zdomskyy in [7, Question 16]. For the proof we construct a mad family in L which is an ℵ1-union of perfect a.d. sets, such that this union remains mad in the iterated Hechler extension. The construction also leads us to isolate a new cardinal invariant, the Borel almost-disjointness number, defined as the least number of Borel a.d. sets whose union is a mad family. Our proof yields the consistency of (and hence, ).

The axioms for Zermelo-Fraenkel (ZF) set theory are an appealing but somewhat arbitrary-seeming assortment. A survey of the axioms does not suffice to reveal the source of their attraction. Accordingly, attempts have been made to ground ZF in principles whose appeal can be felt immediately. These attempts can be classified as follows. First, some of them propose to rest the ZF axioms directly on informal doctrine. The others propose to ground the ZF axioms in other formal axioms that can be regarded as more basic. When the latter approach is taken, ZF continues to draw on informal support, but the draft is made at a more basic level.

The same research can be classified in another way, according to the informal diagnosis offered for the paradoxes of set theory. In some cases, the diagnosis is that the paradoxical sets (such as the Russell set) fail to exist only because they would have to be too large; a set that would be sufficiently small must always exist. This is the doctrine of limitation of size. In other cases, the diagnosis is that the paradoxical sets fail to exist only because they would have to lie too high in a certain hierarchy of sets; a set that would lie sufficiently low in the hierarchy must always exist. This is the doctrine of the hierarchy. The present paper will investigate the latter doctrine, with the doctrine of size making a brief appearance at the end.

We give a full description of the structure under inclusion of all finite level Borel classes of functions, and provide an elementary proof of the well-known fact that not every Borel function can be written as a countable union of Σα0-measurable functions (for every fixed 1 ≤ α < ω1). Moreover, we present some results concerning those Borel functions which are ω-decomposable into continuous functions (also called countably continuous functions in the literature): such results should be viewed as a contribution towards the goal of generalizing a remarkable theorem of Jayne and Rogers to all finite levels, and in fact they allow us to prove some restricted forms of such generalizations. We also analyze finite level Borel functions in terms of composition of simpler functions, and we finally present an application to Banach space theory.

Let ℒ be the set of all formulas of a given first order predicate logic (with or without identity). For each positive integer n, let ℒn be the set of all formulas φ in ℒ logically equivalent to a formula of the form

where Q is a (possibly empty) string of quantifiers, m is a positive integer, and each αij is either an atomic formula or the negation of an atomic formula.

We give a model-theoretic proof of the fact that for all infinite Abelian groups P ≠ NP in the sense of binary nondeterminism. This result has been announced 1994 by Christine Gaßner.

We prove weak elimination of imaginary elements for Boolean orderings with finitely many atoms. As a consequence we obtain equivalence of the two notions of o-minimality for Boolean ordered structures, introduced by C. Toffalori. We investigate atoms in Boolean algebras induced by algebraically closed subsets of Boolean ordered structures. We prove uniqueness of prime models in strongly o-minimal theories of Boolean ordered structures.

Classical set theory is considered as the framework of contemporary mathematics. But there are aspects of our understanding of the real world about what it is not clear that they are described in Cantor's set theory in the best possible way. For example the formalization of some intuitive concepts such as the description of vague properties (which led to the theory of fuzzy sets) and the interpretation of the notion of infinitely small quantities (modelled by nonstandard models) is not quite simple in the classical set theory. Therefore it is natural to look for an alternative to Cantor's set theory which would enable us to formalize these considerations more naturally and which would be a sufficiently strong framework for mathematics at the same time.

The alternative set theory which was created by P. Vopěnka (cf. [V]) is an attempt to construct a theory that could serve as an alternative to Cantor's set theory. The ideas of the alternative set theory make it possible to constitute a new approach to mathematics. An effort to formalize mathematically our intuitive concepts once more is made, and moreover it seems that one can obtain in the alternative set theory mathematical formalizations of concepts which up to now were not adequately formalized.

In the alternative set theory we can build up all essential parts of mathematics. Development of the classical disciplines is described in [V]. Let us mention a few further results obtained in the alternative set theory: a connection between the discrete and the continuous on the basis of which it is possible to define topology (cf. [V]), investigation of motion (cf. [V]), construction of different types of σ-additive ultrafilters (cf. [S-V4]), classification of classes (measurement of vagueness of properties; cf. [Č-V]), possibility of definition of notions of nonstandard methods (cf. [S-V 1]) and valuations of ideals (cf. [M]). A series of articles has been written developing mathematics in the alternative set theory (for the full list of papers cf. [S]). For some remarks concerning the connection between the alternative set theory and nonstandard methods, the reader is refered to [S 4].

In 1885 Peirce axiomatised the propositional calculus on the basis of five ‘icons’ or axioms, which with Cpq for ‘If p then q’ and o for a false proposition, and with the source in Peirce's [2] beside each, may be represented as follows: 1. Cpp (3.376); 2. CCpCqrCqCpr (3.377); 3. CCpqCCqrCpr (3.379); 4. Cop (3.381); 5. CCCpqpp (3.384). From these Peirce proves, among other things, 6. CpCCpqq (3.377), 7. CpCqp (3.378), and with Np (Not p) for Cpo, 8. CNNpp (3.384).

By a well-known result of Wajsberg's II. 93, the entire two-valued propositional calculus is derivable by substitution and detachment from 3, 4, 5, and 7 (with Df. N). In Berry [1] this is taken to show the completeness of Peirce's basis; but this proof will not do as it stands. For Peirce's proof of 7 consists in first passing from 1 to CqCpp by the argument that ‘to say that (x ⥽ x) is generally true is to say that it is so in every state of things, say in that in which y is true’; and then from CqCpp to 7 by 2. This procedure clearly involves, formally, the use not only of substitution and detachment but of a rule to infer ⊦ Cqα. from ⊦α. Peirce's basis is sufficient with substitution and detachment nevertheless; for by a less well-known result of Wajsberg's II. 93, 3, 4, 5, and 6 are sufficient in this sense, and Peirce does prove 6 by substitution and detachment from 1 and 2.

A “foundational crisis” occurred already in Greek mathematics, brought about by the Pythagorean discovery of incommensurable quantities. It was Eudoxos who provided new foundations, and since then Greek mathematics has been unshakeable. If one reads modern mathematical textbooks, one is normally told that something very similar occurred in modern mathematics. The calculus invented in the seventeenth century had to go through a crisis caused by the use of divergent series. One is told that by the achievements of the nineteenth century from Cauchy to Cantor this crisis has definitely been overcome. It is well known, but it is nevertheless very often not taken seriously into account, that this is an illusion. The so-called ε-δ-definitions of the limit concepts are an admirable achievement, but they are only one step towards the goal of a final foundation of analysis. The nineteenth century solution of the problem of foundations consists of recognizing, in addition to the concept of natural number as the basis of arithmetic, another basic concept for analysis, namely the concept of set. By the inventors of set theory it was strongly held that these sets are self-evident to our intuition; but very soon the belief in their self-evidence was destroyed by the set-theoretic paradoxes. After that, about 1908, the period of axiomatic set theory began. In analogy to geometry there was put forward an uninterpreted system of axioms, a formal system. This, of course, is quite possible. A formal system contains strings of marks; and a special class of these strings, the class of the so-called “theorems”, is inductively defined.

We consider two generalizations of the recursion theorem, namely Visser’s ADN theorem and Arslanov’s completeness criterion, and we prove a joint generalization of these theorems.

Given a supercompact cardinal κ and a regular cardinal λ < κ, we describe a type of forcing such that in the generic extension the cofinality of κ is λ, there is a very good scale at κ, a bad scale at κ, and SCH at κ fails. When creating our model we have great freedom in assigning the value of 2κ, and so we can make SCH hold or fail arbitrarily badly.

Recursive model theory involves the study of relationships between recursion theory and model theory. One direction this often takes is to study the effectiveness of various aspects of model theory. This paper examines such questions by examining some properties of recursive models; that is, models whose basic relations, functions, and constants are all uniformly recursive (and whose universe is the set of natural numbers). Somewhat more precisely:

Let be a model whose universe is N, and let (θ())i be an effective enumeration of all quantifier-free formulas of the language of . Then is recursive if {〈, i〉: satisfies (θ())i, in } is a recursive subset of N. (Here and throughout the paper, 〈 〉 denotes an effective pairing function, or an effective coding of sequences, as required.) Similarly, let (ϕ())i be an effective enumeration of all existential formulas of the language of . Then is existentially decidable if {〈, i〉: satisfies (ϕ())i in } is a recursive subset of N.

It is clear that if is recursive and is a model isomorphic to , then may lose many of the recursive properties of . In the simplest example, could easily fail to be a recursive model. But even if we require that be a recursive model, it could still fail to retain other recursive properties of . An example of the sort of property which can be studied in this vein is the following notion, introduced by Ash and Nerode in [2].

We consider the following question of Kunen:

Does Con(ZFC + ∃M a transitive inner model and a non-trivial elementary embedding j: M → V)

imply Con(ZFC + ∃ a measurable cardinal)?

We use core model theory to investigate consequences of the existence of such a j: M → V. We prove, amongst other things, the existence of such an embedding implies that the core model K is a model of “there exists a proper class of almost Ramsey cardinals”. Conversely, if On is Ramsey, then such a j. M are definable.

We construe this as a negative answer to the question above. We consider further the consequences of strengthening the closure assumption on j to having various classes of fixed points.

A number of specific cardinal numbers have been defined in terms of /fin or ωω. Some have been generalized to higher cardinals, and some even to arbitrary Boolean algebras. Here we study eight of these cardinals, defining their generalizations to higher cardinals, and then defining them for Boolean algebras. We then attempt to completely describe their relationships within each of several important classes of Boolean algebras.

The generalizations to higher cardinals might involve several cardinals instead of just one as in the case of ω, For example, the number a associated with maximal almost disjoint families of infinite sets of integers can be generalized to talk about maximal subsets of [κ]μ subject to the pairwise intersections having size less than ν. (For this multiple generalization of . see Monk [2001].) For brevity we do not consider such generalizations, restricting ourselves to just one cardinal. The set-theoretic generalizations then associate with each infinite cardinal κ some other cardinal λ, defined as the minimum of cardinals with a certain property.

The generalizations to Boolean algebras assign to each Boolean algebra some cardinal λ, also defined as the minimum of cardinals with a certain property.

For the theory of the original “continuum” cardinal numbers, see Douwen [1984]. Balcar and Simon [1989]. and Vaughan [1990].

I am grateful to Mati Rubin for some conversations concerning these functions for superatomic algebras, and to Bohuslav Balcar for information concerning the function h.

The notation for set theory is standard. For Boolean algebras we follow Koppelberg [1989], but recall at the appropriate place any somewhat unusual notation.

We prove here that the intuitionistic theory T0↾ + UMIDN. or even EETJ↾ + UMIDN, of Explicit Mathematics has the strength of –CA0. In Section 1 we give a double-negation translation for the classical second-order μ-calculus, which was shown in [Mö02] to have the strength of –CA0. In Section 2 we interpret the intuitionistic μ-calculus in the theory EETJ↾ + UMIDN. The question about the strength of monotone inductive definitions in T0 was asked by S. Feferman in 1982, and — assuming classical logic — was addressed by M. Rathjen.