In [1] McKinsey gives a method of defining possibility in terms of “substitutions”, or transformations of one sentence into another. Roughly, the motivation is that a sentence be possible if a sentence of “like form”, i.e. a transformation of it, is true.

The purpose of this paper is to show that the two systems given in [1], shown by McKinsey to be at least as strong as Lewis' systems S4 and S5, do exactly characterize S4 and S5, and that the system given by omitting rule A4 from the first system exactly characterizes von Wright's system M.1

This paper investigates the quantifier “there exist unboundedly many” in the context of first-order arithmetic. An alternative axiomatization is found for Peano arithmetic based on an axiom schema of regularity: The union of boundedly many bounded sets is bounded. We also obtain combinatorial equivalents of certain second-order theories associated with cuts in nonstandard models of arithmetic.

This paper continues the exposition of a demonstrably consistent foundation for mathematics begun in An extension of basic logic (hereafter referred to as EBL) and in The Heine-Borel theorem in extended basic logic (hereafter referred to as HB). Still earlier papers related to these are A basic logic (referred to as BL) and Representations of calculi (referred to as RC). The main conventions and results of all the above papers will be presupposed in what follows. The numbering of sections and paragraphs will be a continuation of that of EBL and HB.

The Uniformly Reflexive Structure was introduced by E. G. Wagner who showed that the theory of such structures generalized much of recursive function theory. In this paper Uniformly Reflexive Structures are constructed as factor algebras of free nonassociative algebras. Wagner's question about the existence of a model with no computable splinter (“successor set”) is answered in the affirmative by the construction of a model whose only computable sets are the finite sets and their complements. Finally, for each countable Boolean algebra R of subsets of a countable set which contains the finite subsets, a model is constructed with R as its family of computable sets.

A primitive-recursive sequence of rational numbers sn is said to be primitive-recursively irrational, if there are primitive recursive functions n(k), i(p, q) > 0 and N(p, q) such that:

1. (k)(n ≥ n(k) → ∣sn – sn(k)∣ < 2−k).

2. (p)(q)(q > 0 & n ≥ N(p, q) → ∣sn ± p/q∣ > 1/i(p, q)).

The object of the present note is to establish the primitive-recursive irrationality of a sequence which converges to π. In a previous paper we proved the primitive-recursive irrationality of the exponential series Σxn/n!, for all rational values of x, and showed that a primitive-(general-) recursively irrational sequence sn is strongly primitive-(general-)recursive convergent in any scale, where a recursive sequence sn is said to be strongly primitive-(general-)recursive convergent in the scale r (r ≥ 2), if there is a non-decreasing primitive-(general-) recursive function r(k) such that

,

where [x] is the greatest integer contained in x, i.e. [x] = i if i ≤ x < i + 1, [x] = —i if i ≤ —x < i+1, where i is a non-negative integer.

A rational recursive sequence sn is said to be recursive convergent, if there is a recursive function n(k) such that

.

If a sequence sn is strongly recursive convergent in a scale r, then it is recursive convergent and its limit is the recursive real number where, for any k ≥ 0,

.

We study classes of ultrafilters on ω defined by a natural property of the Loeb measure in the Nonstandard Universe corresponding to the ultrafilter. This class, the Property M ultrafilters, is shown to contain all ultrafilters built up by taking iterated products over collections of pairwise nonisomorphic selective ultrafilters. Results on Property M ultrafilters are applied to the construction of extensions of probability measures, and to the study of measurable reductions between ultrafilters.

Throughout, M will denote a transitive model of ZFC. Using the terms “random” and “generic” in the sense of [1], one may ask whether there can exist real numbers x and y such that x is generic over M[y] and y is random over M[x]. We shall see below by an elementary argument that this is not possible, and so, in a crude sense at least, random and generic extensions do not commute. This does not however rule out the possibility of a weaker commutativity. Let B be the complete Boolean algebra (in M) for adjoining a random real followed by a generic real and C be the complete Boolean algebra for adjoining a generic real followed by a random real. Then it still might be the case that B and C are isomorphic. This also fails, though, and we shall prove this by establishing the following combinatorial properties of MB and MC:

but

In addition this will show that C cannot be embedded as a complete subalgebra of B.

The property satisfied by B is reminiscent of calibre ℵ1 [2]. B would have calibre if we could replace “infinite” by “uncountable”, and this occurs if Martin's Axiom holds in M. To obtain the nonisomorphism of B and C in general necessitated looking at the weaker property.

Several definitions of “compact” for topological spaces have appeared in the literature (see [5]). We will consider the following:

Definition. A topological space X is

1. Compact(1) if every open cover of X has a finite subcover.

2. Compact(2) if every infinite subset E of X has a complete accumulation point (i.e., a point x0 ∈ X such that for every neighborhood U of x0, |E ∩ U| = |E|).

3. Compact(3) if there is a subbase S for the topology on X such that every cover of X by members of S has a finite subcover.

4. Compact(4) if each nest of closed, nonempty sets has a nonempty intersection.

5. Compact(5) if every family of closed sets in X which has the finite intersection property (every finite subfamily has a nonempty intersection) has a nonempty intersection.

6. Compact(6) if each net in X has a cluster point.

7. Compact(7) if each net in X has a convergent subnet.

This work was motivated primarily by consideration of various proofs that the Tychonoff theorem, T (“the product of compact topological spaces is compact”) is equivalent to the Axiom of Choice, AC. Tychonoff's original proof that AC implies T used Definition 2 [13]. Other proofs have used Definitions 3 and 5; see [5]. The proof by Kelley that T implies AC uses Definition 5 [6].

The completeness of the prepositional calculus was first proved by Post. His somewhat condensed proof has been succeeded by more detailed presentations of substantially the same argument, and also by several proofs of radically different forms. The present paper contains still another proof, offered because of its relative simplicity. In part this proof follows a plan which was sketched by Wajsberg for another purpose, viz. for proving the completeness of the sub-calculus involving only the material conditional.

For the present proof a systematization of the propositional calculus will be used which is due to Tarski, Bernays, and Wajsberg. It involves the material conditional “⊃” and the falsehood “F” as primitive; thus the formulae are recursively describable as comprising “F”, the variables “p”, “q”, “r”, …, and all results of putting formulae for “p” and “q” in “(p⊃q)”. The denial “˜p” is definable as “(p⊃F)”, and all other truth functions are then definable in familiar fashion. (Conversely, in a system admitting “˜” instead of “F” as primitive, “F” might be explained as an abbreviation of “˜(P⊃P)”.) The postulates are four:

(1) ((p⊃q)⊃((q⊃r)⊃ (p⊃ r)))

(2) (((p⊃(q⊃p)⊃p)

(3) (p⊃(q⊃p))

(4) (F⊃p).

The field K((G)) of generalized power series with coefficients in the field K of characteristic 0 and exponents in the ordered additive abelian group G plays an important role in the study of real closed fields. Conway and Gonshor (see [2, 4]) considered the problem of existence of non-standard irreducible (respectively prime) elements in the huge “ring” of omnific integers, which is indeed equivalent to the existence of irreducible (respectively prime) elements in the ring K((G≤0)) of series with non-positive exponents. Berarducci (see [1]) proved that K((G≤0)) does have irreducible elements, but it remained open whether the irreducibles are prime i.e., generate a prime ideal. In this paper we prove that K((G≤0)) does have prime elements if G = (ℝ, +) is the additive group of the reals, or more generally if G contains a maximal proper convex subgroup.

We use a fundamental theorem of Vaught, called the covering theorem in [V] (cf. theorem 0.1 below) as well as a generalization of it (cf. Theorem 0.1* below) to derive several known and a few new results related to the logic . Among others, we prove that if every countable model in a PCφ1ω class has only countably many automorphisms, then the class has either ≤ℵ0 or exactly nonisomorphic countable members (cf. Theorem 4.3*) and that the class of countable saturated structures of a sufficiently large countable similarity type is not among countable structures (cf. Theorem 5.2). We also give a simple proof of the Lachlan-Sacks theorem on bounds of Morley ranks (§7).

We formulate and prove (in ZFC) a strong coloring theorem which holds at successors of singular cardinals, and use it to answer several questions concerning Shelah's principle Pr1 (μ+, μ+, μ+, cf (μ)) for singular μ.

Motivated by the search for a logic for polynomial time, we study rank logic (FPR) which extends fixed-point logic with counting (FPC) by operators that determine the rank of matrices over finite fields. While FPR can express most of the known queries that separate FPC from Ptime, almost nothing was known about the limitations of its expressive power.

In our first main result we show that the extensions of FPC by rank operators over different prime fields are incomparable. This solves an open question posed by Dawar and Holm and also implies that rank logic, in its original definition with a distinct rank operator for every field, fails to capture polynomial time. In particular we show that the variant of rank logic ${\text{FPR}}^{\text{*}}$ with an operator that uniformly expresses the matrix rank over finite fields is more expressive than FPR.

One important step in our proof is to consider solvability logic FPS which is the analogous extension of FPC by quantifiers which express the solvability problem for linear equation systems over finite fields. Solvability logic can easily be embedded into rank logic, but it is open whether it is a strict fragment. In our second main result we give a partial answer to this question: in the absence of counting, rank operators are strictly more expressive than solvability quantifiers.

This paper introduces valuation structures associated with preferential models. Based on KLM valuation structures, we present a canonical approach to obtain injective preferential models for any preferential relation satisfying the property INJ, and give uniform proofs of representation theorems for injective preferential relations appeared in the literature. In particular, we show that, in any propositional language (finite or infinite), a preferential inference relation satisfies INJ if and only if it can be represented by a standard preferential model. This conclusion generalizes the result obtained by Freund. In addition, we prove that, when the language is finite, our framework is sufficient to establish a representation theorem for any injective relation.

We show the faithful embedding of common knowledge logic CKL into game logic GL, that is, CKL is embedded into GL and GL is a conservative extension of the fragment obtained by this embedding. Then many results in GL are available in CKL, and vice versa. For example, an epistemic consideration of Nash equilibrium for a game with pure strategies in GL is carried over to CKL. Another important application is to obtain a Gentzen-style sequent calculus formulation of CKL and its cut-elimination. The faithful embedding theorem is proved for the KD4–type propositional CKL and GL, but it holds for some variants of them.

In analogy to the definition of the halting problem K, an r.e. set A is called a diagonal iff there is a computable numbering ψ of the class of all partial recursive functions such that A = {i ∈ ω: ψi(i)↓} (in that case we say that A is the diagonal of ψ). This notion has been introduced in [10]. It captures all r.e. sets that can be constructed by diagonalization.

It was shown that any nonrecursive r.e. T-degree contains a diagonal, that for any diagonal A there is an r.e. nonrecursive nondiagonal B ≤TA, and that there are r.e. degrees a such that any r.e. set from a is a diagonal.

In §2 of the present paper we show that the property “A is a diagonal” is elementary lattice theoretic (e.l.t.). This result complements and generalizes previous results of Harrington and Lachlan, respectively. Harrington (see [16, XV. 1]) proved that the property of being the diagonal of some Gödelnumbering (i.e., of being creative) is e.l.t., and Lachlan [12] proved that the property of being a simple diagonal (i.e., of being simple and not hh-simple [10]) is e.l.t.

In §§3 and 4 we study the position of diagonals and nondiagonals inside the lattice of r.e. sets. We concentrate on an important class of nondiagonals, generalizing the maximal and hemimaximal sets: the -maximal sets. Using the results from [6] we are able to classify the -maximal sets that can be obtained as halfs of splittings of hh-simple sets.

Cartesian closed categories (CCCs) have played and continue to play an important role in the study of the semantics of programming languages. An axiomatization of the isomorphisms which hold in all Cartesian closed categories discovered independently by Soloviev and Bruce, Di Cosmo and Longo leads to seven equalities. We show that the unification problem for this theory is undecidable, thus settling an open question. We also show that an important subcase, namely unification modulo the linear isomorphisms, is NP-complete. Furthermore, the problem of matching in CCCs is NP-complete when the subject term is irreducible.

CCC-matching and unification form the basis for an elegant and practical solution to the problem of retrieving functions from a library indexed by types investigated by Rittri. It also has potential applications to the problem of polymorphic type inference and polymorphic higher-order unification, which in turn is relevant to theorem proving and logic programming.

In this article an application of extended fields of real numbers to the proof of theorems in the theory of cooperative games will be presented. The proofs set forth below involve the use of A. Robinson's theory of nonstandard analysis and are metamathematical in character. Alternative proofs utilizing ordinary topological methods can in fact be carried out quite briefly. However, attempts to apply nonstandard analysis to game theory are relatively novel. For this reason these results may be of interest not only insofar as they present new information on the theory of the kernel of a cooperative game, but also in that they serve to demonstrate the possibility of effectively exploiting nonstandard analysis as a tool for future investigation in this area. It may well turn out that nonstandard analysis could serve as the most natural vehicle through which concepts defined for games with a finite number of players might be extended to games with a continuum of players.

A minimal field of non-zero characteristic is algebraically closed.