We begin with a prepositional language Lp containing conjunction (Λ), a class of sentence names {Sα}αϵA, and a falsity predicate F. We (only) allow unrestricted infinite conjunctions, i.e., given any non-empty class of sentence names {Sβ}βϵB,

is a well-formed formula (we will use WFF to denote the set of well-formed formulae).

The language, as it stands, is unproblematic. Whether various paradoxes are produced depends on which names are assigned to which sentences. What is needed is a denotation function:

For example, the LP sentence “F(S1)” (i.e., Λ{F(S1)}), combined with a denotation function δ such that δ(S1)“F(S1)”, provides the (or, in this context, a) Liar Paradox.

To give a more interesting example, Yablo's Paradox [4] can be reconstructed within this framework. Yablo's Paradox consists of an ω-sequence of sentences {Sk}kϵω where, for each n ϵ ω:

Within LP an equivalent construction can be obtained using infinite conjunction in place of universal quantification - the sentence names are {Si}iϵω and the denotation function is given by:

We can express this in more familiar terms as:

etc.

For the formulation of the remaining axioms we need the notions of a function and of a one-to-one correspondence.

We define a function to be a class of pairs in which different elements always have different first members; or, in other words, a class F of pairs such that, to every element a of its domain there is a unique element b of its converse domain determined by the condition 〈a, b〉ηF. We shall call the set b so determined the value of F for a, and denote it (following the mathematical usage) by F(a).

A set which represents a function—i.e., a set of pairs in which different elements always have different first members—will be called a functional set.

If b is the value of the function F for a, we shall say that F assigns the set b to the set a; and if a functional set f represents F, we shall say also that f assigns the set b to the set a.

A class of pairs will be called a one-to-one correspondence if both it and its converse class are functions. We shall say that there exists a one-to-one correspondence between the classes A and B (or of A to B) if A and B are domain and converse domain of a one-to-one correspondence. Likewise we shall say that there exists a one-to-one correspondence between the sets a and b (or of a to b) if a and b respectively represent the domain and the converse domain of a one-to-one correspondence. In the same fashion we speak of a one-to-one correspondence between a class and a set, or a set and a class.

Since Birkhoff and von Neumann [2] a new area of logical investigation has grown up under the name of quantum logic. However it seems to me that many authors have been inclined to discuss algebraic semantics as such (mainly lattices of a certain kind) almost directly without presenting any axiomatic system, far from developing any proof theory of quantum logic. See, e.g., Gunson [9], Jauch [10], Varadarajan [15], Zeirler [16], etc. In this sense many works presented under the name of quantum logic are algebraic in essence rather than genuinely logical, though it is absurd to doubt the close relationship between algebraic and logical study on quantum mechanics.

The main purpose of this paper is to alter this situation by presenting an axiomatization of quantum logic as natural and as elegant as possible, which further proof-theoretical study is to be based on.

It is true that several axiomatizations of quantum logic are present now. Several authors have investigated the so-called material implication α → β ( = ¬α∨(α ∧ β)) very closely with due regard to its importance. See, e.g., Finch [5], Piziak [11], etc. Indeed material implication plays a predominant role in any axiomatization of a logic in Hilbert-style. Clark [4] has presented an axiomatization of quantum logic with negation ¬ and material implication → as primitive connectives. In this paper we do not follow this approach. First of all, this approach is greatly complicated because orthomodular lattices are only locally distributive.

We give characterizations for the (in ZFC unprovable) sentences “Every -set is measurable” and “Every -set is measurable” for various notions of measurability derived from well-known forcing partial orderings.

One of the most significant by-products of the study of admissible sets with urelements is the emphasis it has given to recursively saturated models. As suggested in [Schlipf, 1977], countable recursively saturated models (for finite languages) possess many of the desirable properties of saturated and special models. The notion of resplendency was introduced to isolate some of these desirable properties. In §§1 and 2 of this paper we study these parallels, showing how they can be exploited to give new proofs of some traditional model theoretic theorems. This yields both pedagogical and philosophical advantages: pedagogical since countable recursively saturated models are easier to build and manipulate than saturated and special models; philosophical since it shows that uncountable models — which the downward Lowenheim–Skolem theorem tells us are in some sense not basic in the study of countable theories — are not needed in model theoretic proofs of these theorems. In §3 we apply our local results to get results about resplendent models of ZF set theory and PA (Peano arithmetic). In §4 we shall examine certain analogous results for admissible languages, most similar to, and seemingly generally slightly weaker than, already known results. (The Chang–Makkai sort of result, however, is new.)

Although this paper is an outgrowth of work with admissible sets with urelements, I have tried to keep it as accessible as possible to those with a background only in finitary model theory. Thus §§1,2, and 3 should not involve any work with admissible sets. §4, however, is concerned with some admissible analogues to results in §2 and necessarily uses certain technical results of §11 5 of [Schlipf, 1977].

We prove a categoricity transfer theorem for tame abstract elementary classes.

Suppose that K is a χ-tame abstract elementary class and satisfies the amalgamation and joint embedding properties and has arbitrarily large models. Let λ ≥ Max{χ, LS(K+}. If K is categorical in λ and λ+, then K is categorical in λ++.

Combining this theorem with some results from [37]. we derive a form of Shelah's Categoricity Conjecture for tame abstract elementary classes:

Suppose K is χ-tame abstract elementary class satisfying the amalgamation and joint embedding properties. Let μ0 ≔ Hanf(K). Ifand K is categorical in somethen K is categorical in μ for all μ .

Let us consider the following infinite game between two players, Empty and Nonempty. We are given a large set S. Empty opens the game by choosing a large subset S0 of S; then Nonempty chooses a large set S1 ⊆ S0; then Empty chooses large S2 ⊆ S, etc. The game is over after ω moves. If ⋂n=0xSn is empty then Empty wins, and if ⋂n=0∞Sn is nonempty then Nonempty wins.

If “large” means “infinite”, then Empty can beat Nonempty rather easily: he chooses So countable, S0 = {a0, a1,…, an,…}, and then he chooses S2 such that a0 ∉ S2, S4 such that a1, ∉ S4 and so on.

Next we assume that S is a set of uncountable cardinality, and that “large” means “of cardinality ∣S∣”. Then still Empty can win, but his winning strategy is somewhat more sophisticated: Let us identify S with a cardinal number κ. Thus each subset of S of size κ is a set of ordinals below κ. For each X ⊆ κ of size κ, let fx be the unique order-preserving mapping of X onto κ, and let F(X) = {x ϵ X: f(x) is a successor ordinal}. Empty's strategy is to play S0 = F(K), and when Nonempty plays S2k − 1, let S2k = F(S2k − 1).

We characterise explicitly the decidable predicates on integers of Infinite Time Turing machines, in terms of admissibility theory and the constructible hierarchy. We do this by pinning down ζ, the least ordinal not the length of any eventual output of an Infinite Time Turing machine (halting or otherwise); using this the Infinite Time Turing Degrees are considered, and it is shown how the jump operator coincides with the production of mastercodes for the constructible hierarchy; further that the natural ordinals associated with the jump operator satisfy a Spector criterion, and correspond to the Lζ-stables. It also implies that the machines devised are “Σ2 Complete” amongst all such other possible machines. It is shown that least upper bounds of an “eventual jump” hierarchy exist on an initial segment.

In this paper, we show that the theory of ordered differential fields has a model completion. We also show that any real differential field, finitely generated over the rational numbers, is isomorphic to some field of real meromorphic functions. In the last section of this paper, we combine these two results and discuss the problem of deciding if a system of differential equations has real analytic solutions. The author wishes to thank G. Stengle for some stimulating and helpful conversations and for drawing our attention to fields of real meromorphic functions.

§ 1. Real and ordered fields. A real field is a field in which −1 is not a sum of squares. An ordered field is a field F together with a binary relation < which totally orders F and satisfies the two properties: (1) If 0 < x and 0 < y then 0 < xy. (2) If x < y then, for all z in F, x + z < y + z. An element x of an ordered field is positive if x > 0. One can see that the square of any element is positive and that the sum of positive elements is positive. Since −1 is not positive, an ordered field is a real field. Conversely, given a real field F, it is known that one can define an ordering (not necessarily uniquely) on F [2, p. 274]. An ordered field F is a real closed field if: (1) every positive element is a square, and (2) every polynomial of odd degree with coefficients in F has a root in F. For example, the real numbers form a real closed field. Every ordered field can be embedded in a real closed field. It is also known that, in a real closed field K, polynomials satisfy the intermediate value property, i.e. if f(x) ∈ K[x] and a, b ∈ K, a < b, and f(a)f(b) < 0 then there is a c in K such that f(c) = 0.

Recent work in natural language semantics leads to some new observations on generalized quantifiers. In §1 we show that English quantifiers of type 〈1, 1〉 are booleanly generated by their generalized universal and generalized existential members. These two classes also constitute the sortally reducible members of this type.

Section 2 presents our main result — the Generalized Prefix Theorem (GPT). This theorem characterizes the conditions under which formulas of the form (Q1x1…QnxnRx1…xn and q1x1…qnxnRx1…xn are logically equivalent for arbitrary generalized quantifiers Qi, qi. GPT generalizes, perhaps in an unexpectedly strong form, the Linear Prefix Theorem (appropriately modified) of Keisler & Walkoe (1973).

In this paper we discuss several generalization of theorems from stability theory to simple theories. Cherlin and Hrushovski, in [2] develop a substitute for canonical bases in finite rank, ω-categorical supersimple theories. Motivated by methods there, we prove the existence of canonical bases (in a suitable sense) for types in any simple theory. This is done in Section 2. In general these canonical bases will (as far as we know) exist only as “hyperimaginaries”, namely objects of the form a/E where a is a possibly infinite tuple and E a type-definable equivalence relation. (In the supersimple, ω-categorical case, these reduce to ordinary imaginaries.) So in Section 1 we develop the general theory of hyperimaginaries and show how first order model theory (including the theory of forking) generalises to hyperimaginaries. We go on, in Section 3 to show the existence and ubiquity of regular types in supersimple theories, ω-categorical simple structures and modularity is discussed in Section 4. It is also shown here how the general machinery of simplicity simplifies some of the general theory of smoothly approximable (or Lie-coordinatizable) structures from [2].

Throughout this paper we will work in a large, saturated model M of a complete theory T. All types, sets and sequences will have size smaller than the size of M. We will assume that the reader is familiar with the basics of forking in simple theories as laid out in [4] and [6]. For basic stability-theoretic results concerning regular types, orthogonality etc., see [1] or [9].

Quantification theory, or the first-order predicate calculus, is ordinarily so formulated as to provide as theorems all and only those formulas which come out true under all interpretations in all non-empty domains. There are two strong reasons for thus leaving aside the empty domain.

(i) Where D is any non-empty domain, any quantificational formula which comes out true under all interpretations in all domains larger than D will come out true also under all interpretations in D. (Cf. [4], p. 92.) Thus, though any small domain has a certain triviality, all but one of them, the empty domain, can be included without cost. To include the empty one, on the other hand, would mean surrendering some formulas which are valid everywhere else and thus generally useful.

(ii) An easy supplementary test enables us anyway, when we please, to decide whether a formula holds for the empty domain. We have only to mark the universal quantifications as true and the existential ones as false, and apply truth-table considerations.

Incidentally, the existence of that supplementary test shows that there is no difficulty in framing an inclusive quantification theory (i.e., inclusive of the empty domain) if we so desire. A proof in this theory can be made to consist simply of a proof in the exclusive (or usual) theory followed by a check by the method of (ii). We may, however, be curious to see a more direct or autonomous formulation: one which does not consist, like the above, of the exclusive theory plus a rule of expurgation. And, in fact, such formulations have of late been forthcoming: Mostowski [5], Hailperin [3], and, as part of a broader context, Church [2]. I shall not presuppose acquaintance with these papers, except in my final paragraph (and then only with [3]).

The Gödel class with identity (GCI) is the class of closed, prenex quantificational formulas whose prefixes have the form ∀∀∃ … ∃ and whose matrices contain arbitrary predicate letters and the identity sign “ = ”, but do not contain function signs or individual constants. The ∀∀∃ … ∃ class without identity was shown solvable over fifty years ago ([4], [12], [17]); slightly later, that class was shown to possess the stronger property of finite controllability ([5], [18]). (A class of formulas is solvable iff it is decidable for satisfiability; it is finitely controllable iff every satisfiable formula in it has a finite model.) At the end of [5], Gödel claims that the finite controllability of the GCI can be shown “by the same method” as he employed to show this for the class without identity. This claim has been questioned for nearly twenty years; in §1 below we give a brief history of investigations into it. The major result of this paper shows Gödel to have been mistaken: the GCI is unsolvable. §2 contains the basic construction, which yields a satisfiable formula in the GCI that lacks finite models. This formula may easily be exploited to encode undecidable problems into the GCI.

The main result of this paper is a probabilistic construction of finite rigid structures. It yields a finitely axiomatizable class of finite rigid structures where no formula with counting quantifiers defines a linear order.

This paper contains a joint study of two sentential logics that combine a many-valued character, namely tetravalence, with a modal character; one of them is normal and the other one quasinormal. The method is to study their algebraic counterparts and their abstract models with the tools of Abstract Algebraic Logic, and particularly with those of Brown and Suszko's theory of abstract logics as recently developed by Font and Jansana in their “A General Algebraic Semantics for Sentential Logics”. The logics studied here arise from the algebraic and lattice-theoretical properties we review of Tetravalent Modal Algebras, a class of algebras studied mainly by Loureiro, and also by Figallo. Landini and Ziliani, at the suggestion of the late Antonio Monteiro.

If T is a complete first-order totally transcendental theory then over every T-structure A there is a prime model unique up to isomorphism over A. Moreover M is a prime model over A iff: (1) every finite sequence from M realizes an isolated type over A, and (2) there is no uncountable indiscernible set over A in M.

The existence of prime models was proved by Morley [3] and their uniqueness for countable A by Vaught [9]. Sacks asked (see Chang and Keisler [1, question 25]) whether the prime model is unique. After proving this I heard Ressayre had proved that every two strictly prime models over any T-structure A are isomorphic, by a strikingly simple proof. From this follows

If T is totally transcendental, M a strictly prime model over A then every elementary permutation of A can be extended to an automorphism of M. (The existence of M follows by [3].)

By our results this holds for any prime model. On the other hand Ressayre's result applies to more theories. For more information see [6, §0A]. A conclusion of our theorem is the uniqueness of the prime differentially closed field over a differential field. See Blum [8] for the total transcendency of the theory of differentially closed fields.

We can note that the prime model M over A is minimal over A iff in M there is no indiscernible set over A (which is infinite).

In [2], Fischer has shown the existence of a bounded-truth-table degree of unsolvability which contains a collection of many-one degrees which has, under many-one reducibility, the order type, ω, of the positive integers. In [1; pg. 124], Dekker and Myhill give a construction which shows that the many-one degree of any simple set contains a collection of one-one degrees of simple sets which has, under one-one reducibility, the order type (ω + ω*) ·ω. A basic result of recursive function theory (due to Myhill) is that the creative sets form a many-one degree which consists of a single one-one degree (i.e. a single recursive isomorphism type).

It is well known that the recursive sets form three many-one degrees. Two of these, the degrees of the empty set and of the set of all integers, consist of single one-one degrees.

In a paper J. Łukasiewicz and A. Tarski study the systems arising out of the implication function C (x, y) = min(1, 1 – x + y) and the negation function Nx = 1 – x, where x, y are real numbers between 0 and 1 inclusive. Let us then writeСxy = min(1, 1 – x + y) and Nx = 1 – x. (1)

In this note we shall consider another implication function, namelyС′xy = ССNxyy, (2)

The area of interest of this paper is recursively enumerable vector spaces; its origins lie in the works of Rabin [16], Dekker [4], [5], Crossley and Nerode [3], and Metakides and Nerode [14]. We concern ourselves here with questions about maximal vector spaces, a notion introduced by Metakides and Nerode in [14]. The domain of discourse is V∞ a fully effective, countably infinite dimensional vector space over a recursive infinite field F.

By fully effective we mean that V∞, under a fixed Gödel numbering, has the following properties:

(i) The operations of vector addition and scalar multiplication on V∞ are represented by recursive functions.

(ii) There is a uniform effective procedure which, given n vectors, determines whether or not they are linearly dependent (the procedure is called a dependence algorithm).

We denote the Gödel number of x by ⌈x⌉ By taking {εn ∣ n > 0} to be a fixed recursive basis for V∞, we may effectively represent elements of V∞ in terms of this basis. Each element of V∞ may be identified uniquely by a finitely-nonzero sequence from F Under this identification, εn corresponds to the sequence whose n th entry is 1 and all other entries are 0. A recursively enumerable (r.e.) space is a subspace of V∞ which is an r.e. set of integers, ℒ(V∞) denotes the lattice of all r.e. spaces under the operations of intersection and weak sum. For V, W ∈ ℒ(V∞), let V mod W denote the quotient space. Metakides and Nerode define an r.e. space M to be maximal if V∞ mod M is infinite dimensional and for all V ∈ ℒ(V∞), if V ⊇ M then either V mod M or V∞ mod V is finite dimensional. That is, M has a very simple lattice of r.e. superspaces.

We define a structure which is much simpler than a morass, but whose existence is equivalent to the existence of a morass.