bluuebunny/crossref_metadata_2025 huggingface dataset:
Two interpolation theorems for a predicate calculus
Authors: Maehara Shoji , Takeuti Gaisi
Published: May 2006

A second order formula is called Π1 if, in its prenex normal form, all second order quantifiers are universal. A sequent F1, … Fm → G1 …, Gn is called Π1 if a formula

is Π1

If we consider only Π1 sequents, then we can easily generalize the completeness theorem for the cut-free first order predicate calculus to a cut-free Π1 predicate calculus.

In this paper, we shall prove two interpolation theorems on the Π1 sequent, and show that Chang's theorem in [2] is a corollary of our theorem. This further supports our belief that any form of the interpolation theorem is a corollary of a cut-elimination theorem. We shall also show how to generalize our results for an infinitary language. Our method is proof-theoretic and an extension of a method introduced in Maehara [5]. The latter has been used frequently to prove the several forms of the interpolation theorem.
A generalization of Nelson's algorithm for obtaining prime implicants
Authors: House R. W. , Rado T.
Published: May 2006

In the design of multiple input-output logical systems, the authors have previously formulated and proved a computer program for obtaining optimal system representations satisfying three optimality criteria [1]. In that program, the need for obtaining prime implicants occurred. Two algorithms for this purpose are available in the literature; one due to Quine [2] and one due to Nelson [3], [4]. Nelson's, briefly, is to express the function (whose prime implicants are desired) as a product of sums of literals, multiply out, and discard repeated literals save one and proper multiples. (To obtain the function in the initial form, one can start with the complement of the function expressed as a sum of products and complement it using De Morgan's theorem.) In using these algorithms, it became apparent to us that in certain cases one of these two algorithms required less computer time than the other one. In particular, if the given system has a large number of don't cares then the Nelson algorithm seemed to be preferred [5]. Also in the case of a single function, if there are few zeroes in the truth table representation for the function, then Nelson's algorithm is preferable. It also became apparent to us that in certain situations one needs a generalized version of the Nelson algorithm.
On the axiomatizability of uniform spaces
Authors: Kopperman Ralph
Published: May 2006

A great deal of the interest in the theory of models of sets of sentences in the lower predicate calculus is due to the increasing success with which this theory has been applied to problems from algebra (see, for example [6, particularly pp. 90–103]).

The existence of nonstandard models prevents this language from being altogether appropriate for application to analysis.
Compactification of groups and rings and nonstandard analysis
Authors: Robinson Abraham
Published: May 2006

Let G be a separated (Hausdorff) topological group and let *G be an enlargement of G (see [8]). Thus, *G (i) possesses the same formal properties as G in the sense explained in [8], and (ii) every set of subsets {Aν} of G with the finite intersection property—i.e. such that every nonempty finite subset of {Aν} has a nonempty intersection—satisfies ∩*Aν ≠ ø, where the *Aν are the extensions of the Aν in *G, respectively.
Nonfinitizability of classes of representable polyadic algebras
Authors: Johnson James S.
Published: May 2006

The notion of polyadic algebra was introduced by Halmos to reflect algebraically the predicate logic without equality. Later Halmos enriched the study with the introduction of the notion of equality. These algebras are very closely related to the cylindric algebras of Tarski. The notion of diagonal free cylindric algebra predates that of cylindric algebra and is also due to Tarski. The theory of diagonal free algebras forms an important fragment of the theories of polyadic and cylindric algebras.
On the model theory of denumerably long formulas with finite strings of quantifiers
Authors: Makkai M.
Published: May 2006

In this paper we prove infinitary analogues of model-theoretic results known for finitary logic. The infinitary language we deal with is Lω1ω which is roughly described by saying that, in addition to the usual formation rules of the lower predicate calculus with identity, also the formation of the conjunction and disjunction of countably many formulas is allowed.
A choice free theory of Dedekind cardinals
Authors: Ellentuck Erik
Published: May 2006

In this paper we continue our investigation of the Dedekind cardinals which was initiated in [2]. Those results are summarized below. Let ω be the finite cardinals and Δ the Dedekind cardinals. In [7] Myhill defined a class of functions ƒ: Χκω→ω, which he called the combinatorial functions, and which he applied to the study of recursive equivalence types.
Independence of Rose's axioms for m-valued
implication
Authors: Edmonds Ernest
Published: May 2006

Rose has shown in [2] that the following axioms are sufficient, with
modus ponens, for m-valued
Łukasiewiczian implication.
Constructive order types on cuts
Authors: Soare Robert I.
Published: May 2006

If A and B are subsets of natural numbers
we say that A is recursively equivalent to
B (denoted A ≃ B) if there is
a one-one partial recursive function which maps A onto
B, and that A is recursively
isomorphic to B (denoted A ≅
B) if there is a one-one total recursive function which
maps A onto B and Ā (the
complement of A) onto B#x00AF;.
The inadequacy of Kripke's semantical analysis of D2 and D3
Authors: Routley R. , Montgomery H.
Published: May 2006

Kripke's model structure for D2 is a quadruple (G, K, R, N) where N is the set of normal elements, i.e., the subset of K such that for every H in N, HRH. (See [1, p. 220, p. 211].) In fact, however, this structure provides a model for E2, as the work of Lemmon shows ([2, pp. 58–62]).

To show the inadequacy of Kripke's model structure, we show that the E2 thesis □B ⊃ B, not a thesis of D2, is valid under Kripke's modelling for D2. Suppose, for a reductio argument, that □ B ⊃ B is false for some valuation ϕ in some D2 model structure. Thenyϕ(□B ⊃ B, G) = F; so by truth-functional assignments
On size vs. efficiency for programs admitting speed-ups
Authors: Helm John , Young Paul
Published: May 2006

Since the publication in 1967 of the two papers [1] and [2] by Manuel Blum, the techniques and results of “pure” recursion theory, particularly the recursion theorem and priority methods, have come to play an increasingly important role in studies of computational complexity. This paper gives a typical application of the recursion theorem with a fairly intricate diagonalization to answer a question raised by Blum in [3]. Roughly, we prove the existence of functions which have the property that if we are given any program for computing the function and want to pass to a program which computes the function much more efficiently, then we can only do so at the expense of obtaining a much larger program: the function which describes the necessary increase in the size of the more efficient program must grow more rapidly than any recursive function.
Defining algebraic elements
Authors: Bacsich Paul D.
Published: May 2006

This paper is a survey and a synthesis of the various approaches to defining algebraic elements. Most of it is devoted to proving the following result.

Let T be a universal theory with the Amalgamation Property. Then for T the notions of algebraic element introduced by Robinson, Jónsson, and Morley are identical. Furthermore, they extend in a natural way the notion of algebraic element introduced by Park, and used by Lachlan and Baldwin and by Kueker.

In the course of proving this we shall construct the algebraic closure as a suitable injective hull and prove a unique factorisation theorem for algebraic predicates.

We shall also show (in §3) that if T is closed under products then algebraic elements all have degree 1. Thus in algebra, algebraic elements reduce to epimorphisms.

To demonstrate the remarkable stability of the notion we shall show (at the end of §5) that defining algebraic elements by infinitary formulas yields no new ones.

Let L be a language. The cardinality of the set of formulas of L is denoted by ∣L∣. An L-theory is a deductively closed set of L-sentences. We let denote the category of models of T and (L-structure) homomorphisms between them. If A is a substructure of B we write A ≤ B. We call u: A → B an injection if u is an isomorphism of A with a substructure of B, and let denote the subcategory of consisting of all injections.
A survey of partial degrees
Authors: Sasso Leonard P.
Published: May 2006

Partial degrees are equivalence classes of partial natural number functions under some suitable extension of relative recursiveness to partial functions. The usual definitions of relative recursiveness, equivalent in the context of total functions, are distinct when extended to partial functions. The purpose of this paper is to compare the upper semilattice structures of the resulting degrees.

Relative partial recursiveness of partial functions was first introduced in Kleene [2] as an extension of the definition by means of systems of equations of relative recursiveness of total functions. Kleene's relative partial recursiveness is equivalent to the relation between the graphs of partial functions induced by Rogers' [10] relation of relative enumerability (called enumeration reducibility) between sets. The resulting degrees are hence called enumeration degrees. In [2] Davis introduces completely computable or compact functionals of partial functions and uses these to define relative partial recursiveness of partial functions. Davis' functionals are equivalent to the recursive operators introduced in Rogers [10] where a theorem of Myhill and Shepherdson is used to show that the resulting reducibility, here called weak Turing reducibility, is stronger than (i.e., implies, but is not implied by) enumeration reducibility. As in Davis [2], relative recursiveness of total functions with range ⊆{0, 1} may be defined by means of Turing machines with oracles or equivalently as the closure of initial functions under composition, primitive re-cursion, and minimalization (i.e., relative μ-recursiveness). Extending either of these definitions yields a relation between partial functions, here called Turing reducibility, which is stronger still.
An algebraic characterization of power set in countable standard models of ZF
Authors: Metakides George , Plotkin J. M.
Published: May 2006

The following is a classical result:

Theorem 1.1. A complete atomic Boolean algebra is isomorphic to a power set algebra [2, p. 70].

One of the consequences of [3] is: If M is a countable standard model of ZF and is a countable (in M) model of a complete ℵ0-categorical theory T, then there is a countable standard model N of ZF and a Λ ∈ N such that the Boolean algebra of definable (in T with parameters from ) subsets of is isomorphic to the power set algebra of Λ in N. In particular if and T the theory of equality with additional axioms asserting the existence of at least n distinct elements for each n < ω, then there is an N and Λ ∈ N with 〈PN(Λ), ⊆〉 isomorphic to the countable, atomic, incomplete Boolean algebra of the finite and cofinite subsets of ω.

From the above we see that some incomplete Boolean algebras can be realized as power sets in standard models of ZF.

Definition 1.1. A countable Boolean algebra 〈B, ≤〉 is a pseudo-power set if there is a countable standard model of ZF, N and a set Λ ∈ N such that

It is clear that a pseudo-power set is atomic.
Degrees of sensible lambda theories
Authors: Barendregt Henk , Bergstra Jan , Klop Jan Willem , Volken Henri
Published: May 2006

A λ-theory T is a consistent set of equations between λ-terms closed under derivability. The degree of T is the degree of the set of Gödel numbers of its elements. is the λ-theory axiomatized by the set {M = N∣ M, N unsolvable}. A λ-theory is sensible iff T ⊃ ; for a motivation see [6] and [4].

In §1 it is proved that the theory is Σ20-complete. We present Wadsworth's proof that its unique maximal consistent extension * (= Th(D∞)) is Π20-complete. In §2 it is proved that η (= λη-calculus + ) is not closed under the ω-rule (see [1]). In §3 arguments are given to conjecture that is Π11-complete. This is done by representing recursive sets of sequence numbers as λ-terms and by connecting wellfoundedness of trees with provability in ω. In §4 an infinite set of equations independent over η will be constructed. From this it follows that there are 2ℵ0 sensible theories T such that and 2ℵ0 sensible hard models of arbitrarily high degrees. In §5 some nonprovability results needed in §§1 and 2 are established. For this purpose one uses the theory η extended with a reduction relation for which the Church–Rosser theorem holds. The concept of Gross reduction is used in order to show that certain terms have no common reduct.
Sets which do not have subsets of every higher degree
Authors: Simpson Stephen G.
Published: May 2006

Let A be a subset of ω, the set of natural numbers. The degree of A is its degree of recursive unsolvability. We say that A is rich if every degree above that of A is represented by a subset of A. We say that A is poor if no degree strictly above that of A is represented by a subset of A. The existence of infinite poor (and hence nonrich) sets was proved by Soare [9].

Theorem 1. Suppose that A is infinite and not rich. Then every hyperarith-metical subset H of ω is recursive in A.

In the special case when H is arithmetical, Theorem 1 was proved by Jockusch [4] who employed a degree-theoretic analysis of Ramsey's theorem [3]. In our proof of Theorem 1 we employ a similar, degree-theoretic analysis of a certain generalization of Ramsey's theorem. The generalization of Ramsey's theorem is due to Nash-Williams [6]. If A ⊆ ω we write [A]ω for the set of all infinite subsets of A. If P ⊆ [ω]ω we let H(P) be the set of all infinite sets A such that either [A]ω ⊆ P = ∅. Nash-Williams' theorem is essentially the statement that if P ⊆ [ω]ω is clopen (in the usual, Baire topology on [ω]ω) then H(P) is nonempty. Subsequent, further generalizations of Ramsey's theorem were proved by Galvin and Prikry [1], Silver [8], Mathias [5], and analyzed degree-theoretically by Solovay [10]; those results are not needed for this paper.
Minimal degrees and the jump operator
Authors: Cooper S. B.
Published: May 2006

The jump a′ of a degree a is defined to be the largest degree recursively enumerable in a in the upper semilattice of degrees of unsolvability. We examine below some of the ways in which the jump operation is related to the partial ordering of the degrees. Fried berg [3] showed that the equation a = x′ is solvable if and only if a ≥ 0′. Sacks [13] showed that we can find a solution of a = x′ which is ≤ 0′ (and in fact is r.e.) if and only if a ≥ 0′ and is r.e. in 0′. Spector [16] constructed a minimal degree and Sacks [13] constructed one ≤ 0′. So far the only result concerning the relationship between minimal degrees and the jump operator is one due to Yates [17] who showed that there is a minimal predecessor for each non-recursive r.e. degree, and hence that there is a minimal degree with jump 0′. In §1, we obtain an analogue of Friedberg's theorem by constructing a minimal degree solution for a = x′ whenever a ≥ 0′. We incorporate Friedberg5s original number-theoretic device with a complicated sequence of approximations to the nest of trees necessary for the construction of a minimal degree. The proof of Theorem 1 is a revision of an earlier, shorter presentation, and incorporates many additions and modifications suggested by R. Epstein. In §2, we show that any hope for a result analogous to that of Sacks on the jumps of r.e. degrees cannot be fulfilled since 0″ is not the jump of any minimal degree below 0′. We use a characterization of the degrees below 0′ with jump 0″ similar to that found for r.e. degrees with jump 0′ by R. W. Robinson [12]. Finally, in §3, we give a proof that every degree a ≤ 0′ with a′ = 0″ has a minimal predecessor. Yates [17] has already shown that every nonzero r.e. degree has a minimal predecessor, but that there is a nonzero degree ≤ 0′ with no minimal predecessor (see [18]; or for the original unrelativized result see [10] or [4]).
PCA well-orderings of the line
Authors: Friedman Harvey
Published: May 2006

There is a PCA well-ordering of the real line if and only if there is a real from which every real is constructible.
The work of Kurt Gödel
Authors: Kleene Stephen C.
Published: May 2006

I first heard the name of Kurt Gödel when, as a graduate student at Princeton in the fall of 1931, I attended a colloquium at which John von Neumann was the speaker, von Neumann could have spoken on work of his own; but instead he gave an exposition of Gödel's results of formally undecidable propositions [1931].

Today I shall begin with Gödel's paper [1930] onThe completeness of the axioms of the functional calculus of logic, or of what we now often call “the first-order predicate calculus”, using “predicate” as synonymous with “propositional function”.

Alonzo Church wrote ([1944, p. 62] and [1956, pp. 288–289]), “the first explicit formulation of the functional calculus of first order as an independent logistic system is perhaps in the first edition of Hilbert and Ackermann'sGrundzüge der theoretischen Logik(1928).” Clearly, this formalism is not complete in the sense that each closed formula or its negation is provable. (Aclosed formula, orsentence, is a formula without free occurrences of variables.) But Hilbert and Ackermann observe, “Whether the system of axioms is complete at least in the sense that all the logical formulas which are correct for each domain of individuals can actually be derived from them is still an unsolved question.” [1928, p. 68].

This question Gödel answered in the affirmative in his Ph.D. thesis (Vienna, 1930), of which the paper under discussion is a rewritten version.

I shall not describe Gödel's proof. Perhaps no theorem in modern logic has been proved more often than Gödel's completeness theorem for the first-order predicate calculus. It stands at the focus of a complex of fundamental theorems, which different scholars have approached from various directions (e.g. Kleene [1967, Chapter VI]).
Generalized prime models
Authors: Fittler Robert
Published: May 2006

A prime model O of some complete theory T is a model which can be elementarily imbedded into any model of T (cf. Vaught [7, Introduction]). We are going to replace the assumption that T is complete and that the maps between the models of T are elementary imbeddings (elementary extensions) by more general conditions. T will always be a first order theory with identity and may have function symbols. The language L(T) of T will be denumerable. The maps between models will be so called F-maps, i.e. maps which preserve a certain set F of formulas of L(T) (cf. I.1, 2). Roughly speaking a generalized prime model of T is a denumerable model O which permits an F-map O→M into any model M of T. Furthermore O has to be “generated” by formulas which belong to a certain subset G of F.
Describing ordinals using functionals of transfinite type
Authors: Aczel Peter
Published: May 2006

Bachmann, in [2] shows how certain ordinals <Ω(Ω = Ω1 where Ωξ is the (1 + ξ)th infinite initial ordinal) may be described from below using suitable descriptions of ordinals <Ω2. The aim of this paper is to consider another approach to describing ordinal <Ω and compare it with the Bachmann method. Our approach will use functionals of transfinite type based on Ω.

The Bachmann method consists in denning a hierarchy of normal functions ϕδ: Ω → Ω (i.e. continuous and strictly increasing) for δ ≤ η0 < Ω2, starting with ϕ0(λ) = ω1 + λ. The definition of depends on a suitable description of the ordinals ≤ η0. This is obtained by defining a hierarchy 〈Fδ ∣ δ ≤ Ω2〉 of normal functions Fδ: Ω2 → Ω2 analogously to the definition of the initial segment 〈ϕδ ∣ δ ≤ Ω〉 of . The ordinal η0 is .

Note. Our description of Bachmann's hierarchies will differ slightly from those in Bachmann's paper. Let and denote the hierarchies in [2]. Then as Bachmann's normal functions are not defined at 0 we let for λ, δ < Ω2. Bachmann defines for 0 < λ < Ω2 but it seems more natural to omit this so that we let . The situation is analogous for and leads to the following definitions:

where n < ω and ξ is a limit number of cofinality Ω, and
Computational speed-up by effective operators
Authors: Meyer Albert R. , Fischer Patrick C.
Published: May 2006

The complexity of a computable function can be measured by considering the time or space required to compute its values. Particular notions of time and space arising from variants of Turing machines have been investigated by R. W. Ritchie [14], Hartmanis and Stearns [8], and Arbib and Blum [1], among others. General properties of such complexity measures have been characterized axiomatically by Rabin [12], Blum [2], Young [16], [17], and McCreight and Meyer [10].

In this paper the speed-up and super-speed-up theorems of Blum [2] are generalized to speed-up by arbitrary total effective operators. The significance of such theorems is that one cannot equate the complexity of a computable function with the running time of its fastest program, for the simple reason that there are computable functions which in a very strong sense have no fastest programs.

Let φi be the ith partial recursive function of one variable in a standard Gödel numbering of partial recursive functions. A family Φ0, Φ1, … of functions of one variable is called a Blum measure on computation providing

(1) domain (φi) = domain (Φi), and

(2) the predicate [Φi(x) = m] is recursive in i, x and m.

Typical interpretations of Φi(x) are the number of steps required by the ith Turing machine (in a standard enumeration of Turing machines) to converge on input x, the space or number of tape squares required by the ith Turing machine to converge on input x (with the convention that Φi(x) is undefined even if the machine fails to halt in a finite loop), and the length of the shortest derivation of the value of φi(x) from the ith set of recursive equations.
A transfinite sequence of ω-models
Authors: Mostowski Andrzej
Published: May 2006

Let A2 be the axiomatic system of second order arithmetic as described in [2]. One of the models of A2 is the “principal model” Mpr consisting of all integers and all sets of integers. Obviously there exist many denumerable ω-models elementarily equivalent to Mpr and we shall deal in this paper with some questions pertaining to this family which we denote by .

In §1 we define a rather natural relation ε between two denumerable families of sets of integers. From the upward Skolem-Löwenheim theorem it follows easily that there exists a family ordered by ε in the type ω1, but it is not immediately obvious whether there exist a subfamily of not well-ordered by ε. In the present paper we construct such a family of type η. ω1 where η is the order type of rationals and indicate some applications to hyperdegrees.

We adopt the terminology and notation of [2], with the only change that we adjoin to the language of A2 the constants ν0, ν1, … for the consecutive numerals 0, 1, 2, … and axioms which characterise them:

Also we modify the axioms of A2 given in [2] by prefixing them by general quantifiers bounded either to S or to N.
On projective ordinals
Authors: Kechris Alexander S.
Published: May 2006

We study in this paper the projective ordinals , where = sup{ξ: ξis the length of a Δn1prewellordering of the continuum}. These ordinals were introduced by Moschovakis in [8] to serve as a measure of the “definable length” of the continuum. We prove first in §2 that projective determinacy implies , for all even n > 0 (the same result for odd n is due to Moschovakis). Next, in the context of full determinacy, we partly generalize (in §3) the classical fact that δ11 = ℵ1 and the result of Martin that δ31 = ℵω+1 by proving that , where λ2n+1 is a cardinal of cofinality ω. Finally we discuss in §4 the connection between the projective ordinals and Solovay's uniform indiscernibles. We prove among other things that ∀α(α# exists) implies that every δn1 with n ≥ 3 is a fixed point of the increasing enumeration of the uniform indiscernibles.
On the inadequacy of inner models
Authors: Blass Andreas
Published: May 2006

The method of inner models, used by Gödel to prove the (relative) consistency of the axiom of choice and the generalized continuum hypothesis [2], cannot be used to prove the (relative) consistency of any statement which contradicts the axiom of constructibility (V = L). A more precise statement of this well-known fact is:

(*)For any formula θ(x) of the language of ZF, there is an axiom α of the theory ZF + V ≠ L such that the relativization α(θ) is not a theorem of ZF.

On p. 108 of [1], Cohen gives a proof of (*) in ZF assuming the existence of a standard model of ZF, and he indicates that this assumption can be avoided. However, (*) is not a theorem of ZF (unless ZF is inconsistent), because (*) trivially implies the consistency of ZF. What assumptions are needed to prove (*)? We know that the existence of a standard model implies (*) which, in turn, implies the consistency of ZF. Is either implication reversible?

From our main result, it will follow that, if the converse of the first implication is provable in ZF, then ZF has no standard model, and if the converse of the second implication is provable in ZF, then so is the inconsistency of ZF. Thus, it is quite improbable that either converse is provable in ZF.
Simple and hyperhypersimple vector spaces
Authors: Retzlaff Allen
Published: May 2006

Let V∞ be a fixed, fully effective, infinite dimensional vector space. Let be the lattice consisting of the recursively enumerable (r.e.) subspaces of V∞, under the operations of intersection and weak sum (see §1 for precise definitions). In this article we examine the algebraic properties of .

Early research on recursively enumerable algebraic structures was done by Rabin [14], Frölich and Shepherdson [5], Dekker [3], Hamilton [7], and Guhl [6]. Our results are based upon the more recent work concerning vector spaces of Metakides and Nerode [12], Crossley and Nerode [2], Remmel [15], [16], and Kalantari [8].

In the main theorem below, we extend a result of Lachlan from the lattice of r.e. sets to . We define hyperhypersimple vector spaces, discuss some of their properties and show if A, B ∈ , and A is a hyperhypersimple subspace of B then there is a recursive space C such that A + C = B. It will be proven that if V ∈ and the lattice of superspaces of V is a complemented modular lattice then V is hyperhypersimple. The final section contains a summary of related results concerning maximality and simplicity.
Ordinal bounds for κ-consistency
Authors: Goldfarb Warren D.
Published: May 2006

In [1] the ω-consistency of arithmetic was proved by a method which yields fine ordinal bounds for κ-consistency, κ ≥ 1. In this paper these bounds are shown to be best possible. The ω-consistency of a number-theoretic system S can be expressed thus: for all sentences ∃xM,

where ProvS is the proof predicate for S, if n is a nonnegative integer then n is the formal numeral (of S) for n, and if G is a formula then ˹G˺ is the Gödel number of G. The κ-consistency of S is the restriction of (1) to Σκ0 sentences ∃xM. The proof in [1] establishes the no-counterexample interpretation of (1), that is, the existence of a constructive functional Φ such that, for all sentences ∃xM, all numbers p, and all functions f,

(see [1, §2]). A functional Φ is an ω-consistency functional for S if it satisfies (2) for all sentences ∃xM, and a κ-consistency functional for S if it satisfies (2) for all Σκ0 sentences ∃xM.

The systems considered in [1] are those obtained from classical first-order arithmetic Z, including the schema for definition of primitive recursive (p.r.) functions, by adjoining, for some p.r. well-founded ordering ≺ of the nonnegative integers, the axiom schema

that is, the least number principle on ≺; it is equivalent to the schema of transfinite induction on ≺.
Prime model extensions for differential fields of characteristic p ≠ 0
Authors: Wood Carol
Published: May 2006

The main purpose of this paper is to show that there exists a prime differentially closed extension over each differentially perfect field. We do this in a roundabout manner by first giving new and simple axioms for the theory of differentially closed fields (in the manner of Blum [1] for characteristic 0) and by proving that this theory is the model completion of the theory of differentially perfect fields. This paper can be read independently from [10], where we gave more complicated axioms for the same theory (in the manner of Robinson [6] for characteristic 0).

I am indebted to E. R. Kolchin for answering many questions and for making the manuscript of his forthcoming book [2] available to me.
Note on deducibility and many-valuedness
Authors: Wójcicki Ryszard
Published: May 2006

Some of the theorems contained in the interesting and incisive paper [*] (D. J. Shoesmith and T. J. Smiley, Deducibility and many-valuedness, this Journal, vol. 36 (1970), pp. 610–622) are strongly connected with some earlier results, especially those presented in the paper of Łoś and Suszko [2]. The lack of appropriate bibliographical references in [*] shows that some results which have been obtained relatively long ago are, unfortunately, not so widely known as one might expect. The main task of this short note is to inform briefly on a few results and problems related to those examined in [*].
On Σ1 well-orderings of the universe
Authors: Harrington Leo , Jech Thomas
Published: May 2006

The constructible universe L of Gödel [2] has a natural well-ordering <L given by the order of construction; a closer look reveals that this well-ordering is definable by a Σ1 formula. Cohen's method of forcing provides several examples of models of ZF + V ≠ L which have a definable well-ordering but none is definable by a relatively simple formula.

Recently, Mansfield [7] has shown that if a set of reals (or hereditarily countable sets) has a Σ1, well-ordering then each of its elements is constructible. A question has thus arisen whether one can find a model of ZF + V ≠ L that has a Σ1 well-ordering of the universe. We answer this question in the affirmative.

The main result of this paper is

Theorem. There is a model of ZF + V ≠ L which has a Σ1 well-ordering.

The model is a generic extension of L by adjoining a branch through a Suslin tree with certain properties. The branch is a nonconstructible subset of ℵ1. Note that by Mansfield's theorem, the model must not have nonconstructible subsets of ω.

Our results can be generalized in several directions. We note that in particular, we can get a model with a Σ1 well-ordering that is not L[X] for any set X. As one might expect from a joint paper by a recursion theorist and a set theorist, the proof consists of a construction and a computation.
The ⊰-order on submodels
Authors: Marcus Leo
Published: May 2006

The relation M1 ⊰ M2, where M1 and M2 are elementary submodels of a given model M, defines a partial ordering ⊰(M). A natural question is: What are the general properties of this ordering and what special properties can it have for given M? Here we give an example of a prime model M for which ⊰(M) is a dense linear order, in particular ⊰(M) is isomorphic to the natural order of (− ∞, ∞], the reals with a last element (Theorem 1). In fact, this is the only way for ⊰(M) to be a linear order when M is prime (Theorem 3).

We then remark that if N is a model of an ℵ0-categorical theory then ⊰(N) cannot be a linear order, but we give an example where ⊰(N) is a dense partial order, N a model of an ℵ0-categorical theory.

Independently, and about the same time, Benda [1] found nonprime models M where ⊰(M) is isomorphic to any one of a large class of orders, including (− ∞, ∞]. His methods are very similar to ours.

Notation. We assume the reader is familar with Vaught [2] where he will find the definitions and standard results pertaining to prime models, homogeneous models, and ℵ0-categorical theories.
Existentially closed structures
Authors: Simmons H.
Published: May 2006

One of the major problems of model theory is the spectrum problem, i.e. the development of structure theorems for the spectrum of models of a given theory. I hope that this paper will make a (small) contribution to the solution of this problem.

Broadly speaking, in this paper we take a fixed (but arbitrary) theory T and consider a particular class ℰ of models of T. The structures in ℰ (which are known as existentially closed structures) are connected with the model complete extensions of T. These structures have already appeared several times in the literature.

In §1 we survey the notation and terminology that we use, as well as the well known facts that we require. We also consider several concepts which are not new here but which may not be well known.

In §2 we define, and give the basic results concerning existentially closed structures. For most theories, T, the class ℰ is not elementary and hence is not directly amenable to a model theoretic study. Because of this we consider a smaller class of structures—the uniformly existentially closed structures. These are discussed in §3.

In §4 we look at model complete theories via existentially closed structures. This section is essentially a refinement of parts of [6].

In §5 we look at model companions of theories via existentially closed structures.

Finally, in §6 we make some remarks on the relevance of existentially closed structures to the spectrum problem.
Limitations on the Fraenkel-Mostowski method of independence proofs
Authors: Howard Paul E.
Published: May 2006

The Fraenkel-Mostowski method has been widely used to prove independence results among weak versions of the axiom of choice. In this paper it is shown that certain statements cannot be proved by this method. More specifically it is shown that in all Fraenkel-Mostowski models the following hold:

1. The axiom of choice for sets of finite sets implies the axiom of choice for sets of well-orderable sets.

2. The Boolean prime ideal theorem implies a weakened form of Sikorski's theorem.
The word problem for division rings
Authors: Macintyre Angus
Published: May 2006

In this paper we prove that the word problem for division rings is recursively unsolvable. Our proof relies on the corresponding result for groups [7], [28], and makes essential use of P. M. Cohn's recent work [11], [13], [15], [16] on division rings.

The word problem for groups is usually formulated in terms of group presentations or finitely presented groups, as in [7], [24], [28], [30]. An equivalent formulation, in terms of the universal Horn sentences of group theory, is mentioned in [32]. This formulation makes sense for arbitrary first-order theories, and it is with respect to this formulation that we show that the word problem for division rings has degree 0′.
Iterated reflection principles and the ω-rule
Authors: Schmerl Ulf R.
Published: May 2006

The ω-rule,

with the meaning “if the formula A(n) is provable for all n, then the formula ∀xA(x) is provable”, has a certain formal similarity with a uniform reflection principle saying “if A(n) is provable for all n, then ∀xA(x) is true”. There are indeed some hints in the literature that uniform reflection has sometimes been understood as a “formalized ω-rule” (cf. for example S. Feferman [1], G. Kreisel [3], G. H. Müller [7]). This similarity has even another aspect: replacing the induction rule or scheme in Peano arithmetic PA by the ω-rule leads to a complete and sound system PA∞, where each true arithmetical statement is provable. In [2] Feferman showed that an equivalent system can be obtained by erecting on PA a transfinite progression of formal systems PAα based on iterations of the uniform reflection principle according to the following scheme:

Then T = (∪dЄ, PAd, being Kleene's system of ordinal notations, is equivalent to PA∞. Of course, T cannot be an axiomatizable theory.
The combinatorial principle ⋄#
Authors: Devlin Keith J.
Published: May 2006

We consider various strengthenings of the combinatorial principle ◊+ which are provable from V = L, and give applications in set theory.
On computational complexity in weakly admissible structures
Authors: Stoltenberg-Hansen Viggo
Published: May 2006

The theory of abstract computational complexity in ordinary recursion theory (ORT) was initiated by Rabin [7] and Blum [1]. Jacobs [5] generalized the notions to recursion theory on an admissible ordinal α(α-recursion theory) and proved in this setting certain main theorems such as Blum's Theorem and the Compression Theorem.

In ORT the notions of “finite” and “bounded” coincide. Thus when lifting a theorem from ORT to α-recursion theory, “finite” may be translated to either “bounded below α” or to the stronger and more natural “α-finite”. Jacobs conjectured that “bounded below α” was the best possible in the theorems mentioned above. In this paper we shall prove that the stronger version of these theorems are, in fact, true. Furthermore our constructions are uniform for all admissible α.

Rather than restricting ourselves to α-recursion theory we shall consider transitive rudimentarily closed structures M = 〈M, ∈, R〉 which admit what we call an acceptable prewellordering. The special case M = 〈Lα, ∈〉 and M = 〈Sβ, ∈〉 where α is admissible and β a limit ordinal constitute, respectively, α-recursion theory and β-recursion theory (see Friedman [4]).
Changing cofinalities and infinite exponents
Authors: Apter Arthur W.
Published: May 2006

Ever since Cohen invented forcing in 1963, people have studied the properties that cardinals can have in generic extensions of the ground model. A very early result of Lévy shows that if κ is a regular cardinal and λ > κ is strongly inaccessible, then there is a notion of forcing which collapses every cardinal strictly between κ and λ yet preserves every other cardinal. This, of course, answers one question of the genre “What properties can a cardinal have in a generic extension?”

Another question of the same genre that can be asked is the following: Is it possible to have a generic extension of the ground model in which all cardinals are preserved and yet the cofinalities of some cardinals are different? This question was first answered in the affirmative by Prikry, who proved the following theorem.

Theorem 1.1 (Prikry [5]). Assume that V ⊨ “ZFC + κ is measurable”. Then there is a notion of forcing, P, such that for G V-generic over P:

(1) V and V[G] have the same cardinals.

(2) V and V[G] have the same bounded subsets of κ.

(3) V[G], i.e, V[G] ⊨ “κ is Rowbottom”.

(4) V[G] ⊨ “cof(κ) = ω”.

Prikry's result naturally raises the following question: Is it possible to get a generic extension in which cardinals are preserved and yet the cofinalities of certain cardinals are different from the ground model's but are uncountable? This question was first answered in the affirmative by Magidor, who proved the following theorem.
A new omitting types theorem for L(Q)
Authors: Kaufmann Matt
Published: May 2006

For L a countable first-order language, let L(Q) be logic with the quantifier Qx which means “there exist uncountably many x”. We assume a little familiarity with Keisler's paper [8]. One finds there completeness and compactness theorems for L(Q), as well as an omitting types theorem: a syntactic condition is given for a consistent countable theory to have a model satisfying ∀x⋁Σ(x), where Σ is a countable set of formulas of L(Q). (See also Chang and Keisler [3] for the first-order omitting types theorem, due to Henkin and Orey.) An analogous theorem is proved in Barwise, Kaufmann, and Makkai [1] and in Kaufmann [6] for stationary logic. However, a more general theorem than just an anlaogue to Keisler's is proved there. Conditions are given which are sufficient for a theory T to have models satisfying sentences such as aas1aas2 … aasn⋁Σ(s1, … sn), ∀xaas ∨ Σ(x, s), and so forth. Bruce [2] had asked whether such a theorem can be proved for L(Q). with “aa” replaced by “Q*”, where Q* is ¬Q¬ (“for all but countably many”).
Stability theory and Algebra
Authors: Baldwin John T.
Published: May 2006

There are two origins for first-order theories. One type of theory arises by generalizing the common features of a number of different structures, e.g. the theory of groups, and formulating a set of axioms to encode these common features. Here the set of axioms is well understood, frequently it is finite or at least recursive, but there usually is no clear understanding of all the logical consequences of these axioms. The second type of theory arises by considering the set, T = Th(A), of all sentences true in a fixed structure A,3 e.g. the theory of arithmetic (N, +, 0) or the theory of the field of complex numbers (alias: the theory of algebraically closed fields of characteristic zero). The second case gives little more insight as to the truth in A (i.e. membership in T) of a given sentence ∅. But it does guarantee that for a given sentence ∅, either ∅ or ¬∅ is in T, that is, that T is a complete theory. When does a theory T of the first type, i.e. with well-understood axioms, posses this completeness property? An obvious sufficient condition is that T be secretly of the second type, that it have only one model, or, in jargon, T is categorical. Unfortunately (or fortunately depending on your point of view) for any theory with an infinite model, the Löwenheim-Skolem theorem shows this to be impossible: The theory has a model in every infinite power. In the mid-50's Łoś and Vaught discovered that if a theory T with no finite models is categorical in some infinite power α (all models with cardinality α are isomorphic) then T is complete. We will be dealing below with countable complete theories and will assume, unless stated to the contrary, that each theory has no finite models.
Maximality in effective topology
Authors: Kalantari Iraj , Leggett Anne
Published: May 2006

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 ω.
Hyperhypersimple supersets in admissible recursion theory
Authors: Chong C. T.
Published: May 2006

Let α be an admissible ordinal. An α-recursively enumerable set H is hyper-hypersimple (hh-simple) if its lattice of α-r.e. supersets forms a Boolean algebra. In [3], Chong and Lerman characterized the class ℋ() of hh-simple -r.e. sets as precisely those -r.e. sets whose complements are unbounded and of order type less than . Perhaps a nice example of such a set is {σ∣σ is not for any n < ω}. It follows that all hh-simple sets in are nonhyperregular and therefore of degree 0′. That ℋ() is a natural class to study can be seen from the role played by its ω-counterpart in the study of decision problems and automorphisms of ℰ*(ω), the lattice of ω-r.e. sets modulo finite sets (Soare [13] gives an extensive literature on these topics). In α-recursion theory the existence of hh-simple sets is not an all pervasive phenomenon, and there is as yet no complete characterization of the admissible ordinal α for which ℋ(α) is nonempty. While this situation is admittedly unsatisfactory, we feel that the lattice ℰ*(α) of α-r.e. sets modulo α*-finite sets for which ℋ(α) ≠ ∅ deserves a careful study. Indeed armed with some understanding over the last few years of the general theory of admissible ordinals, it is tempting to focus one's attention on some specific ordinals whose characteristics admit a more detailed analysis of the fine structure of sets and degrees. From this point of view, and ℋ() are natural objects of study since the former is a typical example of a non-Σ2-projectible, Σ2-inadmissible ordinal, while the latter is important for the investigations of automorphisms over ℰ*().
Decomposition of totally transcendental modules
Authors: Garavaglia Steven
Published: May 2006

The main theorem of this paper states that if R is a ring and is a totally transcendental R-module, then has a unique decomposition as a direct sum of indecomposable R-modules. Natural examples of totally transcendental modules are injective modules over noetherian rings, artinian modules over commutative rings, projective modules over left-perfect, right-coherent rings, and arbitrary modules over Σ – α-gens rings. Therefore, our decomposition theorem yields as special cases the purely algebraic unique decomposition theorems for these four classes of modules due to Matlis; Warfield; Mueller, Eklof, and Sabbagh; and Shelah and Fisher. These results and a number of other corollaries about totally transcendental modules are covered in §1. In §2, I show how the results of § 1 can be used to give an improvement of Baur's classification of ω-categorical modules over countable rings. In §3, the decomposition theorem is used to study modules with quantifier elimination over noetherian rings.

The goals of this section are to prove the decomposition theorem and to derive some of its immediate corollaries. I will begin with some notational conventions. R will denote a ring with an identity element. LR is the language of left R-modules described in [4, p. 251] and TR is the theory of left R-modules. “R-module” will mean “unital left R-module”. A formula will mean an LR-formula.
Supercompact cardinals, elementary embeddings and fixed points
Authors: Barbanel Julius B.
Published: May 2006

Supercompactness is usually defined in terms of the existence of certain ultrafilters. By the well-known procedure of taking ultrapowers of V (the universe of sets) and transitive collapses, one obtains transitive inner models of V and corresponding elementary embeddings from V into these inner models. These embeddings have been studied extensively (see, e.g. [3] or [4]). We investigate the action of these embeddings on cardinals. In particular, we establish a characterization, based upon cofinality, of which cardinals are fixed by these embeddings.
Ultrafilters on spaces of partitions
Authors: Henle James M. , Zwicker William S.
Published: May 2006

Qκλ. Pκλ the space of all < κ-sized subsets of λ, has provided numerous opportunities for the gainful employment of set theorists in recent years, thanks to its combinatorial richness and to its relationships with various large cardinals. In the spirit of Pκλ we offer the following definition:

For κ ≤ λ both cardinals, Qκλ is the set of all partitions of λ into < κ-many pieces (an element of q ∈ Qκλ is called a piece of q). Equivalently

An element of Pκλ may be viewed as an injection from a < κ-sized set into λ, with some information thrown away. An element of Qκλ is a surjection from λ onto a < κ-sized set, with analogous loss of information.

For p, q ∈ Qκλ, we say p ≤ q iff q is a refinement of p (every piece of q is contained in a piece of p).