Einleitung. Das “Auswahlaxiom” oder “multiplicative axiom” fordert in der gewöhnlichen, von B. Russell und Zermelo angegebenen Fassung, daß zu jeder Menge M, deren Elemente paarweise fremde und nicht-leere Mengen sind, mindestens eine “Auswahlmenge” existiere, die mit jedem Element von M genau éin Element gemeinsam hat. Die nächstliegende und mehrfach verwendete Methode, um ein schwächeres Postulat als die vorstehende Fassung zu formulieren, besteht darin, daß man entweder über die Mächtigkeit der Menge M, oder über die Mächtigkeiten ihrer Elemente, oder über beides gleichzeitig, einschränkende Bedingungen macht, also nur in diesen eingeschränkten Fällen die Existenz einer Auswahlmenge verlangt. Hinsichtlich der Mächtigkeit von M ist da sogleich die Bemerkung zu machen, daß sie jedenfalls transfinit (genauer: nicht endlich im induktiven Sinn) anzusetzen ist. Vermöge allgemeiner logischer Sachverhalte und des (eventuell zu beweisenden) Prinzips, das zu einem gegebenen Objekt a die Bildung der Menge {a} erlaubt, ist nämlich die Existenz einer Auswahlmenge von M beweisbar, falls M die Mächtigkeit 1 besitzt, und diese Beweisbarkeit überträgt sich mittels gewöhnlicher Induktion auf den Fall einer beliebigen endlichen Mächtigkeit. Dagegen ist die Existenz einer Auswahlmenge nicht mehr beweisbar, wenn (bei transfinitem M) die Elemente von M endliche Mengen mit Mächtigkeiten > 1 sind, z. B. also schon in dem Fall, wo M eine transfinite Menge von Paaren ist—natürlich “im allgemeinen,” d. h. wenn die Elemente von M nicht eine besondere Beschaffenheit haben, die die Auszeichnung gewisser Elemente in ihnen ermöglicht. Die Tatsache dieser Nichtbeweisbarkeit, d. h. der Unabhängigkeit des Auswahlaxioms sogar in diesem einfachsten Fall, ist vor längerer Zeit auf der Basis des Zermeloschen Axiomensystems der Mengenlehre nachgewiesen worden.

The sign ‘⊃’ (or ‘→’ or ‘C’) functions in many logical systems in a way which precludes its interpretation as either strict or material implication. For example, in the systems of Heyting, Johansson, Fitch and Bernays (positive logic), the following are theorems:

Now if ‘⊃’ were interpreted as strict implication, ⊃2 would mean ‘if p is true, then p is strictly implied by every proposition’, i.e. ‘if p is true, it is necessarily true’, which is false for contingently true p. If on the other hand ‘⊃’ were interpreted as material implication, ⊃1 would reduce to ‘~p ∨ p’, i.e. to the law of excluded middle, which is conspicuously lacking in the systems mentioned. The reader is likely in practice to veer between these two interpretations. Thus in Fitch or Heyting on realizing that ‘~p⊃▪ p⊃q’ is a theorem, one thinks of it as meaning ‘a false proposition implies everything’ and regards the implication as material; but the presence of ‘p⊃p’ as a theorem, even for choices of p which do not satisfy excluded middle, inclines one again to the strict interpretation. This vacillation, while it need not lead to the commission of any formal fallacies, tends to hamstring one's intuition and thus waste time. The purpose of this paper is to suggest an interpretation of ‘⊃’ which will prevent such havering.

Let two formulae A and B be called interdeducible if A ⊢ B and B ⊢ A.

In this paper we continue the study of the structure of the lattice of recursively enumerable (r.e.) open subsets of a topological space. Work in this approach to effective topology began in Kalantari and Retzlaff [5] and continued in Kalantari [2], Kalantari and Leggett [3] and Kalantari and Remmel [4]. Studies in effectiveness of results in structures other than integers began with the work of Specker [17] and Lacombe [8] on effective analysis.

The renewed activity in the study of the effective content of mathematical structures owes much to Nerode's program and Metakides' and Nerode's [11], [12] work on vector spaces and fields. These studies have been extended by Kalantari, Remmel, Retzlaff, Shore and Smith. Similar studies on the effective content of other mathematical structures have been conducted. These include work on topological vector spaces, boolean algebras, linear orderings etc.

Kalantari and Retzlaff [5] began a study of effective topological spaces by considering a topological space with a countable basis ⊿ for the topology. The space X is to be fully effective; that is, the basis elements are coded into ω and the operations of intersection of basis elements and the relation of inclusion among them are both computable. An r.e. open subset of X is then represented as the union of basic open sets whose codes lie in an r.e. subset of ω.

The notion of ∀-recursiviness, introduced by Lacombe [1], is intended to describe the effectively definable functions and predicates in abstract structures with equality and denumerable domains. The fact that on every such structure ∀-recursiviness and search computability are equivalent is proved by Moschovakis in [2].

The definition of search computability [3] does not require the presence of the equality among the basic predicates of the structure. There exist abstract structures where the equality is not search-computable and even not semicomputable. On the other hand, in some structures the equality is not an “effective” predicate. Consider, for example, a structure whose domain consists of all partial recursive functions.

A notion of relative computability in abstract structures with denumerable domains, which we shall call here ∀-admissibility, was introduced by D. Skordev in 1977. The notion of ∀-admissibility is a generalization of Lacombe's ∀-recursiviness and does not require the presence of the equality among the basic predicates. In 1977 Skordev conjectured that, in every partial structure with denumerable domain, ∀-admissibility and search computability are equivalent.

Since 1977 some attempts have been made to establish Skordev's conjecture. It is proved in [4] for structures with total basic functions and without basic predicates, and in [5] for structures with finite domains. The proofs in [4] and [5] make use of the priority method and are very complicated.

I investigate versions of the Maximality Principles for the classes of forcings which are <κ-closed, <κ-directed-closed, or of the form Col(κ, <λ). These principles come in many variants, depending on the parameters which are allowed, I shall write MPΓ (A) for the maximality principle for forcings in Γ, with parameters from A. The main results of this paper are:

• The principles have many consequences, such as <κ-closed-generic (Hκ) absoluteness, and imply, e.g., that ◊κ holds. I give an application to the automorphism tower problem, showing that there are Souslin trees which are able to realize any equivalence relation, and hence that there are groups whose automorphism tower is highly sensitive to forcing.

• The principles can be separated into a hierarchy which is strict, for many κ.

• Some of the principles can be combined, in the sense that they can hold at many different κ simultaneously.

The possibilities of combining the principles are limited, though: While it is consistent that MP<κ-closed(Hκ +) holds at all regular κ below any fixed α, the “global” maximality principle, stating that MP<κ-closed (Hκ ∪ {κ} ) holds at every regular κ, is inconsistent. In contrast to this, it is equiconsistent with ZFC that the maximality principle for directed-closed forcings without any parameters holds at every regular cardinal. It is also consistent that every local statement with parameters from Hκ⊦ that's provably <κ-closed-forceably necessary is true, for all regular κ.

A propositional system of modal logic is second-order if it contains quantifiers ∀p and ∃p which, in the standard interpretation, are construed as ranging over sets of possible worlds (propositions). Most second-order systems of modal logic are highly intractable; for instance, when augmented with propositional quantifiers, K, B, T, K4 and S4 all become effectively equivalent to full second-order logic. An exception is S5, which, being interpretable in monadic second-order logic, is decidable.

In this paper we generalize this framework by allowing multiple modalities. While this does not affect the undecidability of K, B, T, K4 and S4, poly-modal second-order S5 is dramatically more expressive than its mono-modal counterpart. As an example, we establish the definability of the transitive closure of finitely many modal operators. We also take up the decidability issue, and, using a novel encoding of sets of unordered pairs by partitions of the leaves of certain graphs, we show that the second-order propositional logic of two S5 modalitities is also equivalent to full second-order logic.

This paper continues investigations of the monotone fixed point principle in the context of Feferman's explicit mathematics begun in [14]. Explicit mathematics is a versatile formal framework for representing Bishop-style constructive mathematics and generalized recursion theory. The object of investigation here is the theory of explicit mathematics augmented by the monotone fixed point principle, which asserts that any monotone operation on classifications (Feferman's notion of set) possesses a least fixed point. To be more precise, the new axiom not merely postulates the existence of a least solution, but, by adjoining a new constant to the language, it is ensured that a fixed point is uniformly presentable as a function of the monotone operation. Let T0 + UMID denote this extension of explicit mathematics. [14] gave lower bounds for the strength of two subtheories of To + UMID in relating them to fragments of second order arithmetic based on comprehension. [14] showed that To ↾ + UMID and To ↾ + INDk + UMID have at least the strength of ( – CA), and ↾ and – CA), respectively.

Here we are concerned with the exact reversals. Let UMIDN be the monotone fixed-point principle for subclassifications of the natural numbers. Among other results, it is shown that To ↾ + UMIDN and To ↾ + INDN + UMIDN have the same strength as ( – CA) ↾ and ( – CA), respectively.

The results are achieved by constructing set-theoretic models for the aforementioned systems of explicit mathematics in certain extensions of Kripke-Platek set theory and subsequently relating these set theories to subsystems of second arithmetic.

In the literature, a type Γ is a set of formulas ϕ(ν0) in the one free variable ν0. A model M realizes Γ if there is an element a of M such that

M ╞ ϕ [a] for all ϕ ∈ Γ.

A model M omits Γ if no element of M realizes Γ. Evidently, the two statements:

(*) M realizes Γ

and

(**) M omits Γ

Let IPC be the intuitionistic first-order predicate calculus. From the definition of derivability in IPC the following is clear:

(1) If A is derivable in IPC, denoted by “⊦IPCA”, then A is intuitively true, that means, true according to the intuitionistic interpretation of the logical symbols. To be able to settle the converse question: “if A is intuitively true, then ⊦IPCA”, one should make the notion of intuitionistic truth more easily amenable to mathematical treatment. So we have to look then for a definition of “A is valid”, denoted by “⊨A”, such that the following holds:

(2) If A is intuitively true, then ⊨ A.

Then one might hope to be able to prove

(3) If ⊨ A, then ⊦IPCA.

If one would succeed in finding a notion of “⊨ A”, such that all the conditions (1), (2) and (3) are satisfied, then the chain would be closed, i.e. all the arrows in the scheme below would hold.

Several suggestions for ⊨ A have been made in the past: Topological and algebraic interpretations, see Rasiowa and Sikorski [1]; the intuitionistic models of Beth, see [2] and [3]; the interpretation of Grzegorczyk, see [4] and [5]; the models of Kripke, see [6] and [7]. In Thirty years of foundational studies, A. Mostowski [8] gives a review of the interpretations, proposed for intuitionistic logic, on pp. 90–98.

The aim of this paper is to characterize varieties of Heyting algebras with decidable theory of their finite members. Actually we prove that such varieties are exactly the varieties generated by linearly ordered algebras. It contrasts to the result of Burris [2] saying that in the case of whole varieties, only trivial variety and the variety of Boolean algebras have decidable first order theories.

It is natural, given the usual iterative description of the universe of sets, to investigate set theories which in some way take account of the unfinished character of the universe. We do not here consider any arguments aimed at justifying one system over another, or at clarifying the basic philosophy. Rather, we look at an obvious candidate which is similar to a system discussed by L. Pozsgay in [1]. Pozsgay sketched the development of the ordinary theorems in such a system and attempted to show it equiconsistent with ZF. In this paper we show that the consistency of the system we call IZF can be proved in the usual ZF set theory.

In this paper we show how the assumption of the generalized continuum hypothesis (GCH) can be removed or partially removed from proofs in Zermelo-Frankel set theory (ZF) of statements expressible in the simple theory of types. We assume the reader is familiar with the latter language, especially with the classification of formulas and sentences of that language into Σκη and Πκη form (cf. [1]) and with how that language can be relatively interpreted into the language of ZF.

Acceptable programming systems have many nice properties like s-m-n-Theorem, Composition and Kleene Recursion Theorem. Those properties are sometimes called control structures, to emphasize that they yield tools to implement programs in programming systems. It has been studied, among others by Riccardi and Royer, how these control structures influence or even characterize the notion of acceptable programming system. The following is an investigation, how these control structures behave in the more general setting of complete numberings as defined by Mal'cev and Eršov.

We study extensions of Presburger arithmetic with a unary predicate R and we show that under certain conditions on R, R is sparse (a notion introduced by A. L. Semënov) and the theory of 〈ℕ, +, R〉 is decidable. We axiomatize this theory and we show that in a reasonable language, it admits quantifier elimination. We obtain similar results for the structure 〈ℚ, +, R〉.

Applying the seed concept to Prikry tree forcing ℙμ, I investigate how well ℙμ preserves the maximality property of ordinary Prikry forcing and prove that ℙμ, Prikry sequences are maximal exactly when μ admits no non-canonical seeds via a finite iteration. In particular, I conclude that if μ is a strongly normal supercompactness measure, then ℙμ Prikry sequences are maximal, thereby proving, for a large class of measures, a conjecture of W. Hugh Woodin's.

We design functional algebras that characterize various complexity classes of global functions. For this purpose, classical schemata from recursion theory are tailored for capturing complexity. In particular we present a functional analog of first-order logic and describe algebras of the functions computable in nondeterministic logarithmic space, deterministic and nondeterministic polynomial time, and for the functions computable by AC1 -circuits.

It is known [1] p. 312 that a simultaneous enumeration of the recursively enumerable sets can be achieved by a Σ10-predicate. We shall show that a simultaneous enumeration of the recursive sets can be achieved by a predicate of the same form.

Briefly, the following things are done in this paper. An informal exposition of the significance of partial truth tables in modal logic is presented. The intuitive concept of a truth tabular sentence connective is examined and made precise. From among a vast assortment of truth tabular connectives, the semantically well-behaved ones (called regular connectives) are singled out for close investigation. The familiar concept of functional completeness is generalized to all sets of regular connectives, and the functional completeness (or incompleteness) of selected sets of connectives is established. Some modal analogues of Sheffer's stroke are presented, i.e., single connectives are introduced which serve to define not only the truth functional connectives but all the regular modal connectives as well. The notion of duality is extended to all regular connectives and a general duality theorem is proved. Lastly, simplified proofs are given of several metatheorems about the system S5.

In recent years there has been a proliferation of logics which extend first-order logic, e.g., logics with infinite sentences, logics with cardinal quantifiers such as “there exist infinitely many…” and “there exist uncountably many…”, and a weak second-order logic with variables and quantifiers for finite sets of individuals. It is well known that first-order logic has a limited ability to express many of the concepts studied by mathematicians, e.g., the concept of a wellordering. However, first-order logic, being among the simplest logics with applications to mathematics, does have an extensively developed and well understood model theory. On the other hand, full second-order logic has all the expressive power needed to do mathematics, but has an unworkable model theory. Indeed, the search for a logic with a semantics complex enough to say something, yet at the same time simple enough to say something about, accounts for the proliferation of logics mentioned above. In this paper, a number of proposed strengthenings of first-order logic are examined with respect to their relative expressive power, i.e., given two logics, what concepts can be expressed in one but not the other?

For the most part, the notation is standard. Most of the notation is either explained in the text or can be found in the book [2] of Chang and Keisler. Some notational conventions used throughout the text are listed below: the empty set is denoted by ∅.