bluuebunny/crossref_metadata_2025 huggingface dataset:
A minimal pair of recursively enumerable degrees
Authors: Yates C. E. M.
Published: May 2006

Our principal result is that there exist two incomparable recursively enumerable degrees whose greatest lower bound in the upper semilattice of degrees is 0. This was conjectured by Sacks [5]. As a secondary result, we prove that on the other hand there exists a recursively enumerable degree a < 0(1) such that for no non-zero recursively enumerable degree b is 0 the greatest lower bound of a and b.

The proof of the main theorem involves a method that we have developed elsewhere [8] to deal with situations in which a partial recursive functional may interfere infinitely often with an opposed requirement of lower priority.
On simplifying the matrix of a wff
Authors: Andrews Peter
Published: May 2006

In [3], [4], and [5] Joyce Friedman formulated and investigated certain rules which constitute a semi-decision procedure for wffs of first order predicate calculus in closed prenex normal form with prefixes of the form ∀x1 … ∀xκ∃y1 … ∃ym∀z1 … ∀zn. Given such a wff QM, where Q is the prefix and M is the matrix in conjunctive normal form, Friedman's rules can be used, in effect, to construct a matrix M* which is obtained from M by deleting certain conjuncts of M.
Infinite products of recursive equivalence types
Authors: Ferguson Don C.
Published: May 2006

Remark 1. Finite sums and products of recursive equivalence types have been defined (see [1, p. 73 for sums and p. 130 for products]) and many of their algebraic properties revealed. It seems natural to ask if infinite sums and products can be defined in a natural manner and an algebra of such sums and products developed. The initial work in this direction is to be found in [2], [3] and [4]. In this paper we extend the above studies, concentrating for the most part on products.
Nonstandard logic
Authors: Geiser James R.
Published: May 2006

This paper is an exposition of the author's [2] investigations of a class of infinitary first order logics. These logics are sometimes characterized by saying that the syntactical role played by the positive integers in first order predicate logic is taken over by a nonstandard model of arithmetic. The result is then called a nonstandard logic.1 In particular the operations of conjunction, disjunction and quantification may be iterated infinitely (nonstandard finitely) often.

When the nonstandard model of arithmetic is an ultra power, the natural class of structures in which to interpret the nonstandard wffs is a class of ultra products. Within this framework, many model-theoretic properties of ultra products become manifest in the logical structure of the nonstandard language.
On the notion of algebraic closedness for noncommutative groups and fields
Authors: Robinson Abraham
Published: May 2006

The notion of algebraic closedness plays an important part in the theory of commutative fields. The corresponding notion in the theory of ordered fields is (not only intuitively but in a sense which can be made precise in a metamathematical framework, compare [4]) that of a real closed ordered field. Several suggestions have been made (see [2] and [8]) for the formulation of corresponding concepts in the theory of groups and in the theory of skew fields (division rings, noncommutative fields). Here we present a concept of this kind, which preserves the principal metamathematical properties of algebraically closed commutative fields and which applies to a wide class of first order theories K, including the theories of commutative and of skew fields and the theories of commutative and of general groups.
Incompleteness of a formal system for infinitary finite-quantifier formulas
Authors: Gregory John
Published: May 2006

In [1], various formal proof systems for infinitary formulas were defined. The formal proof system is the result of extending the basic predicate calculus by adding a collection Σ of axiom schemes and a collection Ω of rules of inference. Let Taut be the collection of all infinitary prepositional tautologies, considered as axiom schemes. Let ΩI consist of all the quantificational rules of independent choices. We will show, in §2 (see Theorem 2.1), that (Taut; 0) is not complete for L∞ω (i.e., infinitary finite-quantifier) sentences; that is, we will exhibit an L∞ω sentence ϕ such that ¬ϕ is true in all models, but ¬ϕ is not provable in (Taut; 0). (The unprovability is shown by a weak forcing version of Boolean general models.) This answers a question of Karp in [1,12.1(i)]. In §4, we will show that our ϕ is “ complete for L∞ω ) sentences.”
Nonstandard topology and extensions of monad systems to infinite points
Authors: Wattenberg Frank
Published: May 2006

Intuitively, a topological space is a set together with some notion of “nearness”. Classically, this notion of nearness is usually described by a collection of open sets. With the development of Non-standard analysis by Abraham Robinson [11], we have an alternative way to describe this notion. If X is any set and *X is a nonstandard extension of X then we can describe a topology on X by means of a relationship of “infinitely close” on some points of X. In many ways this latter approach is more intuitive and leads to more straightforward proofs [11] than the classical approach. The first section of this paper explores the connections between these two approaches. In the main section of the paper we extend the notion of “infinitely close” to infinite points of *X. In the final section we give a very intuitive characterization of the compact-open topology (when the domain is locally compact) and use it to give quick, straight-forward proofs of the usual facts about this topology [1], [2]. This last section can be read independently of the second section.
Metarecursively enumerable sets and their metadegrees
Authors: Driscoll Graham C.
Published: May 2006

Metarecursion theory is an analogue of recursion theory which deals with sets of recursive, or constructive, ordinals rather than of natural numbers. It was originated by Kreisel and Sacks [3], who make extensive use of an equation calculus developed by Kripke. We assume that the reader is acquainted with the outline of it given in [3], and especially in [3, §3].
The semisubstitutivity of strict implication
Authors: Jay Zeman J.
Published: May 2006

In [1], the principle of semisubstitutivity of implication (SSI) was introduced for ordinary PC and quantification theory. This metatheorem generalizes the notions of “antecedent” and “consequent” to cover all wf subformulas of a given formula; each such subformula will be classified as being either in “antecedental position” (A-pos) or “consequential position” (C-pos). It is simplest to check these positions in a conjunction-negation primitive system: reduce a formula φ to primitive notation (K—N) ; choose a subformula ψ of φ; count the negation signs in φ within whose scope ψ falls.
Further results on infinite valued predicate logic
Authors: Belluce L. P.
Published: May 2006

In a previous paper [1] Chang and the present author presented a system of infinite valued predicate logic, the truth values being the closed interval [0, 1] of real numbers. That paper was the result of an investigation attempting to establish the completeness of the system using the real number 1 as the sole designated value. In fact, we fell short of our mark and proved a weakened form of completeness utilizing positive segments, [0, a], of linearly ordered abelian groups as admissible truth values. A result of Scarpellini [8], however, showing that the set of well-formed formulas of infinite valued logic valid (with respect to the sole designated real number 1) is not recursively enumerable indicates the above mentioned result is the best possible.
There are infinitely many Diodorean modal functions
Authors: Makinson D. C
Published: May 2006

It is well known that the modal calculus S4 has infinitely many non-equivalent formulae in a single proposition letter (in standard terminology, infinitely many modal functions), whilst S5 has only finitely many. However, the situation regarding the intermediate modal calculi S4.2, S4.3, and Prior's Diodorean tense-logic D does not seem to have been settled. In this note we show that each of these systems, together with a certain proper supersystem D* of D, has infinitely many modal functions.

This is in contrast with the fact that in the intermediate propositional logics KC and LC, which correspond under the McKinsey-Tarski translations to S4.2 and S4.3, there are only finitely many non-equivalent formulae in a single proposition letter.2
The impossibility of finding relative complements for recursively enumerable degrees
Authors: Lachlan A. H.
Published: May 2006

J. R. Shoenfield conjectured in a talk at the Berkeley Model Theory Symposium (1963) that, if b and d are non-zero recursively enumerable (r.e.) degrees such that b < d then there exists an r.e. degree c such that c < d and b U c = d. G. E. Sacks echoed this conjecture at the end of [3]. In this paper the conjecture is disproved. We construct r.e. degrees b, d such that 0 < b < d and such that for no r.e. degree c is it true that c < d and b U c = d. We are grateful to G. E. Sacks for suggesting this problem.
Testing singly quantified tautologies
Authors: Standley Gerald
Published: May 2006

An effective method for testing arguments consisting of singly quantified expressions has recourse to Parry's trapezoid symbolism.1 The procedure entails representing in that symbolism each premise of the argument and the negation of the conclusion. Variables are disregarded. After clearing away any negated quantifiers, the universal statements, including a denied existential conclusion, are first set down and their conjunction (KU) derived. Existential statements, including a denied universal conclusion, are then listed. The argument is valid if and only if some contradiction appears, whether as some premise empty of lines, as a KU empty of lines, or as some existential statement having no lines in common with the KU.
On the notational independence of various hierarchies of degrees of unsolvability
Authors: Hensel Gustav , Putnam Hilary
Published: May 2006

From the work of Kleene, Post and Davis it is well-known that the arithmetic sets can be characterized as those sets recursive in∅(n)for some natural numbern, where∅(0)=∅and. Actually the arithmetic sets which can be expressed in prenex form withnalternating quantifiers (applied to recursive predicates) are recursive in∅(n). Hence, starting with∅, the “jump operation”, which takes a set A into the set, serves to increase the “complexity” of sets in a uniform way.

As far as extending the ω-sequence of degrees of unsolvability (i.e. the degrees represented by the∅(n)) into the 2nd number class, there is an immediate problem. One knows from Spector [17], corollary 2, p. 585, that there is no l.u.b. for the ω-sequence. So, at ω one must pick a degree in some other “natural” way. Unfortunately, what has seemed “natural” to some mathematicians has not seemed natural to others. Kleene and Davis (cf. [10] and [3] respectively) extended this arithmetic hierarchy of degrees of unsolvability by making use of natural number notations for a certain segment of ordinals of the 1st and 2nd number classes, the “constructive” ordinals. Using the Church-Kleene system S3, one can “sum up” previously obtained sets at the limit notations in a way that is certainly natural from a notational point of view.
An Abstract form of the church-rosser theorem. I
Authors: Hindley R.
Published: May 2006

One of the basic results in the theory of λ-conversion is the Church-Rosser Theorem, which says that, using certain rules for conversion and reduction of λ-formulae, any two interconvertible formulae can both be reduced to one formula. (I will not explain this in detail, as λ-conversion is described fully in Church's [2], where the Church-Rosser Theorem is Theorem 7 XXVII; see also Chapter 4 of Curry and Feys' [3].) The first part of the present paper contains an abstract form of this theorem.
Reduced products and nonstandard logics
Authors: Benda M.
Published: May 2006

The results of the present paper were announced in [1]. The work is divided into our parts. In the first part we define relations (relations between relational struc tures) and we show their connection with the equivalence of the languages LΚ,λ (Theorem 1). The relations generalize the games Gn (n < ω) of Ehrenfeucht (see [2]) and the conditions (i)–(ii) which were used by Karp in [5].
A system of axiomatic set theory. Part V. General set theory (continued)
Authors: Bernays Paul
Published: May 2006

We have still to consider the extension of the methods of number theory to infinite ordinals—or to transfinite numbers as they may also, as usual, be called.

The means for establishing number theory are, as we know, recursive definition, complete induction, and the “principle of the least number.” The last of these applies to arbitrary ordinals as well as to finite ordinals, since every nonempty class of ordinals has a lowest element. Hence immediately results also the following generalization of complete induction, called transfinite induction: If A is a class of ordinals such that (1) ΟηA, and (2) αηA → α′ηA, and (3) for every limiting number l, (x)(xεl → xηA) → lηA, then every ordinal belongs to A.
The unsolvability of the uniform halting problem for two state
Turing machines
Authors: Herman Gabor T.
Published: May 2006

The uniform halting problem (UH) can be stated as follows:

Give a decision procedure which for any given Turing machine (TM) will
decide whether or not it has an immortal instantaneous description (ID).

An ID is called immortal if it has no terminal successor. As it is generally
the case in the literature (see e.g. Minsky [4, p. 118]) we assume that in
an ID the tape must be blank except for some finite number of squares. If we
remove this restriction the UH becomes the immortality problem (IP).
Hierarchies based on objects of finite
type1
Authors: Grilliot Thomas J.
Published: May 2006

Shoenfield [8] has shown that a hierarchy for the functions recursive in a
type-2 object can be set up whenever E2 (the
type-2 object that introduces numerical quantification) is recursive in that
type-2 object. With a restriction that we will discuss in the next
paragraph, Moschovakis [4, pp. 254–259] has solved the analogous problem for
type-3 objects. His method seems to generalize for any type-n object, where
n ≥ 2. We will solve this same problem of finding
hierarchies based on type-n objects by a different method.
Instead of using ordinal notations for indexing stages of hierarchies, as do
Shoenfield and Moschovakis, we will define notation-independent stages.
Π11 Sets,
ω-Sets, and metacompleteness
Authors: Owings James C.
Published: May 2006

An ω-set is a subset of the recursive ordinals whose
complement with respect to the recursive ordinals is unbounded and has order
type ω. This concept has proved fruitful in the study of sets in relation to metarecursion theory. We prove
that the metadegrees of the sets
coincide with those of the meta-r.e. ω-sets. We then show that, given any
set, a
metacomplete set can be
found which is weakly metarecursive in it. It then follows that weak
relative metarecursiveness is not a transitive relation on the
sets,
extending a result of G. Driscoll [2, Theorem 3.1]. Coincidentally, we
discuss the notions of total and complete regularity. Finally, we solve
Post's problem for the transitive closure of weak relative
metarecursiveness. We recommend the reader look at pp. 324–328 of the
fundamental article [6] of Kreisel and Sacks before proceeding. He will find
there a proof of the following very basic fact: a subset of the integers is
iff it is
metarecursively enumerable (metafinite).
Eliminating the continuum hypothesis
Authors: Platek Richard A.
Published: May 2006

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.
A conjunctive normal form for S3.5
Authors: Cresswell M. J.
Published: May 2006

In this note we sketch a decision procedure for S3.51 based on
reduction to conjunctive normal form. Using the following theorem of S3.5:
and its
dual for M over a conjunction, any formula can be reduced
by standard methods (as in S52) to a conjunction of disjunctions
of the form where Í is
(p ⊃ p), 0 is ∼(p ⊃ p)
and α — λ are all PC-wffs (i.e. they contain no modal operators).
A note on degrees of subsets1
Authors: Soare Robert I.
Published: May 2006

In [2] we constructed an infinite set of natural numbers containing no
subset of higher (Turing) degree. Since it is well known
that there are nonrecursive sets (e.g. sets of minimal degree) containing no
nonrecursive subset of lower degree, it is natural to
suppose that these arguments may be combined, but this is false. We prove
that every infinite set must contain a nonrecursive subset of either higher
or lower degree.
On theories T categorical in |T|
Authors: Shelah Saharon
Published: May 2006

Morley conjectured that if an infinite first-order theory T is categorical in the power |T| > ℵ0, then it has a model of power < |T| Here we affirm this conjecture for the case |T|ℵ0=|T|.
Intensional models for first degree formulas
Authors: Belnap Nuel D.
Published: May 2006

In Anderson and Belnap [8] there was developed a semantics for first degree entailments (fde), i.e., entailments A → B between formulas A and B involving only truth-functions (defined in terms of “or” and “not”) and quantifiers. The key ideas were (i) the notion of a frame ⟨P, FIP, I⟩, where P is a set of (intensional) propositions closed under negation and multiple disjunction, I is a domain of individuals, and FIP is the set of functions from I into P; and (ii) the semantic relation of cons (consequence), as obtaining between a set of propositions taken conjunctively, and a set taken disjunctively; and (iii) the notion of an atomic frame, i.e., a frame generated by a set of propositions X closed under negation, such that for any disjoint subclasses Y and Z of X, Y does not bear cons to Z.
Connexive class logic
Authors: McCall Storrs
Published: May 2006

Student. I've been studying the logic of classes, and can't see how any class can be included in its own complement.

Teacher. Surely you've heard of the null class, which is included in every class, and hence in its own complement?

Student. That also strikes me as somehow implausible. How do you define ‘inclusion’?

Teacher. In the usual way. a is included in b if and only if the intersection of a with the complement of b is null.
Some remarks concerning theories with recursively enumerable complements
Authors: Cobham Alan
Published: May 2006

A system formalized within the first order predicate calculus either with or without the identity but without predicate or function variables we call simply a theory. We say that a theory T has a recursively enumerable complement (r.e. Comp.) if the set of all sentences of T not valid in T is recursively enumerable. This is equivalent to saying that there exists an effective, purely mechanical procedure for establishing the non-validity in T of precisely those sentences of T which are in fact not theorems of T. If in addition T is recursively enumerable, that is, if there is an effective procedure for establishing the validity in T of its theorems, then T is decidable. It will be shown here that several well-known results concerning decidable theories can be extended to cover theories with r.e. comps. In this respect it should be observed that there exist theories having r.e. comps. which are not decidable. An example is the theory which has as valid sentences just those which contain a given two-place predicate and which are valid in all non-void finite universes [3], [4].
Analytic cut
Authors: Smullyan Raymond M.
Published: May 2006

The real importance of cut-free proofs is not the elimination of cuts per se, but rather that such proofs obey the subformula principle. In this paper we accomplish this latter objective in a different manner.

In the usual formulations of Gentzen systems, there is only one axiom scheme; all the other postulates are inference rules. By contrast, we consider here some Gentzen type axiom systems for propositional logic and Quantification Theory in which there is only one inference rule; all the other postulates are axiom schemes. This admits of an unusually elegant axiomatization of logic.
A class of decidable intermediate propositional logics
Authors: McKay C. G.
Published: May 2006

For the terminology and motivation of this note, my earlier paper [3] should be consulted. Here I make a slight change by requiring the Intuitionist Propositional Logic H to be given in terms of axiom schemata rather than axioms.

Definition. An axiom schema F is essentially negative iff each schematic letter appearing in F is negated.

Thus the schemata (¬P ∨ ¬¬P), (¬¬(¬P ∨ ¬Q)→(¬P ∨ ¬Q)) are essentially negative, whereas (¬P ∨ P) and (¬¬P→P) are not.

Lemma. Let F be an essentially negative axiom schema. Then F yields at most finitely many intuitionistically nonequivalent axioms whose atoms are chosen from a fixed finite set.
“Helping”: several formalizations
Authors: Lynch Nancy
Published: May 2006

Much recent work in the theory of computational complexity ([Me], [FR]. [SI]) is concerned with establishing “the complexity” of various recursive functions, as measured by the time or space requirements of Turing machines which compute them. In the above work, we also observe another phenomenon: knowing the values of certain functions makes certain other functions easier to compute than they would be without this knowledge. We could say that the auxiliary functions “help” the computation of the other functions.

For example, we may conjecture that the “polynomial-complete” problems of Cook [C] and Karp [K] and Stockmeyer [S2], such as satisfiability of propositional formulas or 3-colorability of planar graphs, in fact require time proportional to nlog2n to be computed on a deterministic Turing machine. Then since the time required to decide if a planar graph with n nodes is 3-colorable can be lowered to a polynomial in n if we have a precomputed table of the satisfiable formulas in the propositional calculus, it is natural to say that the satisfiability problem “helps” the computation of the answers to the 3-coloring problem. Similar remarks may be made for any pair of polynomial-complete problems.

As a further illustration, Meyer and Stockmeyer [MS] have shown that, for a certain alphabet Σ, recognition of the set of regular expressions with squaring which are equivalent to Σ* requires Turing machine space cn for some constant c, on an infinite set of arguments. We also know that this set of regular expressions, which we call RSQ, may actually be recognized in space dn for some other constant d. Theorem 6.2 in [LMF] implies that there is some problem (not necessarily an interesting one) of complexity approximately equal to that of RSQ, which does not reduce the complexity of RSQ below cn. It does not “help” the computation of RSQ.
Two forms of the axiom of choice for an elementary topos
Authors: Penk Anna Michaelides
Published: May 2006

The concept of a topos as a system, or world in which mathematics could be defined and interpreted, was developed by F. W. Lawvere and M. Tierney. Much of their work is embodied in the lecture notes Elementary toposes by A. Kock and G. C. Wraith [6].

In an early paper Lawvere set forth a set of axioms for approximately such a system [8]. The topos constructed there is a set-like category that includes among its axioms an axiom of infinity and an axiom of choice.

In its final form an elementary topos is freed from any such axioms.

The most prominent example of an elementary topos is a set theory with the usual Zermelo-Fraenkel or Godel-Bernays set of axioms.

In this paper I have tried to determine what, if any, is the effect of an axiom of choice introduced in a topos, and how are some of the set-theoretic equivalents of such an axiom related in topos theory.

Since the set-theoretic membership relation ∈, the notions of an “empty” set and a “power” set are definable in topos theory, it makes sense to talk about a “choice map” that picks a single element out of every nonempty object, provided that these objects can be somehow collected into a single object or “family.” In other words, an analogue of the usual choice axiom can be formulated in elementary topos language; this is axiom AC2 of the text.
First steps in intuitionistic model theory
Authors: de Swart H.
Published: May 2006

In this paper we will do some model theory with respect to the models, defined in [7] and, as in [7], we will work again in intuitionistic metamathematics.

In this paper we will only consider models M = ‹S, TM›, where S is one fixed spreadlaw for all models M, namely the universal spreadlaw. That we can restrict ourselves to this class of models is a consequence of the completeness proof, which is sketched in [7, §3].

The main tools in this paper will be two model-constructions:

(i) In §1 we will consider, under a certain condition C(M0, M, s), the construction of a model R(M0, M, s) from two models M0 and M with respect to the finite sequence s.

(ii) In §2 we will construct from an infinite sequence M0, M1, M2, … of models a new model Σi∈INMi.

Syntactic proofs of the disjunction property and the explicit definability theorem are well known.

C. Smorynski [8] gave semantic proofs of these theorems with respect to Kripke models, however using classical metamathematics. In §1 we will give intuitionistically correct, semantic proofs with respect to the models, defined in [7] using Brouwer's continuity principle.

Let W be the fan of all models (see [7, Theorem 2.7]) and let Γ be a countably infinite sequence of sentences.
Relativized realizability in intuitionistic arithmetic of all finite types
Authors: Goodman Nicolas D.
Published: May 2006

In this paper we introduce a new notion of realizability for intuitionistic arithmetic in all finite types. The notion seems to us to capture some of the intuition underlying both the recursive realizability of Kjeene [5] and the semantics of Kripke [7]. After some preliminaries of a syntactic and recursion-theoretic character in §1, we motivate and define our notion of realizability in §2. In §3 we prove a soundness theorem, and in §4 we apply that theorem to obtain new information about provability in some extensions of intuitionistic arithmetic in all finite types. In §5 we consider a special case of our general notion and prove a kind of reflection theorem for it. Finally, in §6, we consider a formalized version of our realizability notion and use it to give a new proof of the conservative extension theorem discussed in Goodman and Myhill [4] and proved in our [3]. (Apparently, a form of this result is also proved in Mine [13]. We have not seen this paper, but are relying on [12].) As a corollary, we obtain the following somewhat strengthened result: Let Σ be any extension of first-order intuitionistic arithmetic (HA) formalized in the language of HA. Let Σω be the theory obtained from Σ by adding functionals of finite type with intuitionistic logic, intensional identity, and axioms of choice and dependent choice at all types. Then Σω is a conservative extension of Σ. An interesting example of this theorem is obtained by taking Σ to be classical first-order arithmetic.
Rings which admit elimination of quantifiers
Authors: Rose Bruce I.
Published: May 2006

We say that a ring admits elimination of quantifiers, if in the language of rings, {0, 1, +, ·}, the complete theory of R admits elimination of quantifiers.

Theorem 1. Let D be a division ring. Then D admits elimination of quantifiers if and only if D is an algebraically closed or finite field.

A ring is prime if it satisfies the sentence: ∀x∀y∃z (x =0 ∨ y = 0∨ xzy ≠ 0).

Theorem 2. If R is a prime ring with an infinite center and R admits elimination of quantifiers, then R is an algebraically closed field.

Let be the class of finite fields. Let be the class of 2 × 2 matrix rings over a field with a prime number of elements. Let be the class of rings of the form GF(pn)⊕GF(pk) such that either n = k or g.c.d. (n, k) = 1. Let be the set of ordered pairs (f, Q) where Q is a finite set of primes and such that the characteristic of the ring f(q) is q. Finally, let be the class of rings of the form ⊕q ∈ Qf(q), for some (f, Q) in .

Theorem 3. Let R be a finite ring without nonzero trivial ideals. Then R admits elimination of quantifiers if and only if R belongs to.

Theorem 4. Let R be a ring with the descending chain condition of left ideals and without nonzero trivial ideals. Then R admits elimination of quantifiers if and only if R is an algebraically closed field or R belongs to.

In contrast to Theorems 2 and 4, we have

Theorem 5. If R is an atomless p-ring, then R is finite, commutative, has no nonzero trivial ideals and admits elimination of quantifiers, but is not prime and does not have the descending chain condition.

We also generalize Theorems 1, 2 and 4 to alternative rings.
A proof of the cut-elimination theorem in simple type theory
Authors: Titani Satoko
Published: May 2006

In [4], I introduced a quasi-Boolean algebra, and showed that in a formal system of simple type theory, from which the cut rule is omitted, wffs form a quasi-Boolean algebra, and that the cut-elimination theorem can be formulated in algebraic language. In this paper we use the result of [4] to prove the cut-elimination theorem in simple type theory. The theorem was proved by M. Takahashi [2] in 1967 by using the concept of Schütte's semivaluation. We use maximal ideals of a quasi-Boolean algebra instead of semivaluations.

The logical system we are concerned with is a modification of Schütte's formal system of simple type theory in [1] into Gentzen style.

Inductive definition of types.

0 and 1 are types.

If τ1, …, τn are types, then (τ1, …, τn) is a type.

Basic symbols.

a1τ, a2τ, … for free variables of type τ.

x1τ, x2τ, … for bound variables of type τ.

An arbitrary number of constants of certain types.

An arbitrary number of function symbols with certain argument places.
An interpretation of “finite” modal first-order languages in classical second-order languages
Authors: Lehmann Scott K.
Published: May 2006

This note describes a simple interpretation * of modal first-order languages K with but finitely many predicates in derived classical second-order languages L(K) such that if Γ is a set of K-formulae, Γ is satisfiable (according to Kripke's 55 semantics) iff Γ* is satisfiable (according to standard (or nonstandard) second-order semantics).

The motivation for the interpretation is roughly as follows. Consider the “true” modal semantics, in which the relative possibility relation is universal. Here the necessity operator can be considered a universal quantifier over possible worlds. A possible world itself can be identified with an assignment of extensions to the predicates and of a range to the quantifiers; if the quantifiers are first relativized to an existence predicate, a possible world becomes simply an assignment of extensions to the predicates. Thus the necessity operator can be taken to be a universal quantifier over a class of assignments of extensions to the predicates. So if these predicates are regarded as naming functions from extensions to extensions, the necessity operator can be taken as a string of universal quantifiers over extensions.

The alphabet of a “finite” modal first-order language K shall consist of a non-empty countable set Var of individual variables, a nonempty finite set Pred of predicates, the logical symbols ‘¬’ ‘∧’, and ‘∧’, and the operator ‘◊’. The formation rules of K generate the usual Polish notations as K-formulae. ‘ν’, ‘ν1’, … range over Var, ‘P’ over Pred, ‘A’ over K-formulae, and ‘Γ’ over sets of K-formulae.
Descending sequences of degrees
Authors: Steel John
Published: May 2006

Our unexplained notation is that of Rogers [4]. Let P ⊆ 2N × 2N. We call a sequence  of subsets of N a P-sequence iff ∀n(An+1 = the unique B such that P(An, B)).

Theorem. Let P ⊆ 2N × 2N be arithmetical. Then there is no P-sequence  such that ∀n(A′n+1 ≤T An).

This theorem improves a result of Friedman [2] who showed that for no arithmetical P is there a P-sequence  such that An + 1 is a code for an ω-model of the relative arithmetic comprehension schema, and An + 1 is present in the model coded by An, for all n. Other related results are those of Harrison [3], who showed there is a sequence  such that ∀n, and of Enderton and Putnam [1], who showed there is no sequence  with ∀n(A′n + 1 ≤T An) and A0 hyperarithmetic.

Our theorem is closely connected to Gödel's second incompleteness theorem. Its proof is a recursion theoretic parallel to the proof of Gödel's theorem. In §2 we draw a version of Gödel's theorem as a corollary to ours.
Skolem reduction classes
Authors: Goldfarb Warren D. , Lewis Harry R.
Published: May 2006

Among the earliest and best-known theorems on the decision problem is Skolem's result [7] that the class of all closed formulas with prefixes of the form ∀···∀∃···∃ is a reduction class for satisfiability for the whole of quantification theory. This result can be refined in various ways. If the Skolem prefix alone is considered, the best result [8] is that the ∀∀∀∃ class is a reduction class, for Gödel [3], Kalmár [4], and Schütte [6] showed the ∀∀∃···∃ class to be solvable. The purpose of this paper is to describe the more complex situation that arises when (Skolem) formulas are restricted with respect to the arguments of their atomic subformulas. Before stating our theorem, we must introduce some notation.

Let x, y1, y2, be distinct variables (we shall use v1, v2, ··· and w1, w2, ··· as metavariables ranging over these variables), and for each i ≥ 1 let Y(i) be the set {y1, ···, yi}. An atomic formula Pv1 ··· vk will be said to be {v1, ···, vk}-based. For any n ≥ 1, p ≥ 1, and any subsets Y1, ··· Yp of Y(n), let C(n, Y1, ···, Yp) be the class of all those closed formulas with prefix ∀y1 ··· ∀yn∃x such that each atomic subformula not containing the variable x is Yi-based for some i, 1 ≤ i ≤ p.
A sequent calculus for type assignment
Authors: Seldin Jonathan P.
Published: May 2006

The sequent calculus formulation (L-formulation) of the theory of functionality without the rules allowing for conversion of subjects of [3, §14E6] fails because the (cut) elimination theorem (ET) fails. This can be most easily seen by the fact that it is easy to prove in the system

and

but not (as is obvious if α is an atomic type [an F-simple])

The error in the “proof” of ET in [14, §3E6], [3, §14E6], and [7, §9C] occurs in Stage 3, where it is implicitly assumed that if [x]X ≡ [x] Y then X ≡ Y. In the above counterexample, we have [x]x ≡ ∣ ≡ [x](∣x) but x ≢ ∣x. Since the formulation of [2, §9F] is not really satisfactory (for reasons stated in [3, §14E]), a new seguent calculus formulation is needed for the case in which the rules for subject conversions are not present. The main part of this paper is devoted to presenting such a formulation and proving it equivalent to the natural deduction formulation (T-formulation). The paper will conclude in §6 with some remarks on the result that every ob (term) with a type (functional character) has a normal form.

The conventions and definitions of [3], especially of §12D and Chapter 14, will be used throughout the paper.
A note on the number of zeros of polynomials and exponential polynomials
Authors: Smorynski C.
Published: May 2006

The negative solution of Hilbert's Tenth Problem brought with it a number of unsolvable Diophantine problems. Moreover, by actually providing a Diophantine characterization of recursive enumerability, the proof of the negative solution opened the door to the techniques of recursion theory. In this note, we wish to apply several recursion-theoretic facts and an improvement on the exponential Diophantine representation to refine the exponential case of a result of Davis [1972] regarding the difficulty of determining the number of zeros of a polynomial.

P, Q, etc. will denote polynomials or exponential polynomials–exactly which will be clear from the context. Let # (P) denote the number of distinct nonnegative zeros of P. Further, let C = {0,1, …,ℵ0} be the set of possible values of # (P). For A ⊆ C, we define A * to be

With this notation, Davis' result reads:

Theorem 0.1 (DAVIS). A* is recursive iff A = ∅ or A = C.

The refinement we will prove is:

Theorem 0.2 (Exponential Case). A * is r.e. iff A = ∅ or A = {c: c ≥ a: m} for some finite m.
Beth definability in infinitary languages
Authors: Gregory John
Published: May 2006

Some negative results will be proved concerning the following for certain infinitary languages ℒ1 and ℒ2.

Definition. Beth(ℒ1, ℒ2) iff, for every sentence ϕ(R) of ℒ1, and n-place relation symbols R and S such that S does not occur in ϕ(R), if

then there is an ℒ2 formula θ(x1, …, xn) such that

and θ is built up using only those constant and relation symbols of ϕ other than R.

That is, Beth(ℒ1, ℒ2) iff for every implicit ℒ1 definition ϕ(R) of relations, there is a corresponding explicit ℒ2 definition θ. Beth(ℒωω, ℒωω) was proved by Beth.

Malitz proved that not Beth(ℒω1 ω1, ℒ∞∞) (hence not Beth (ℒ∞∞, ℒ∞∞)), but Beth (ℒ∞ω, ℒ∞∞). In §1, it is shown that Beth(ℒ∞ω, ℒ∞ω) is false. In §2, we strengthen this by showing that, for every cardinal κ, not Beth(ℒ∞ω, ℒ∞κ). In fact, not Beth (ℒκ+ω, ℒ∞κ) follows from property A(κ) defined in §2, and A(κ) is known for regular κ > ω (unpublished result of Morley).

More information on infinitary Beth and Craig theorems is given in [2] and [3]. We assume that the reader is acquainted with the languages ℒκλ which allow conjunctions over ≺κ formulas and quantifiers over ≺λ variables. Thus, we assume that the reader is acquainted with the back and forth argument for showing that two structures are ≡∞κ (ℒ∞κ-elementarily equivalent). Our notation is fairly standard.
A formalization of Essenin-Volpin's proof theoretical studies by means of nonstandard analysis
Authors: Geiser James R.
Published: May 2006

This paper constitutes a short report on the proof theory which developed in the course of an investigation of Essenin-Volpin's foundational studies (see his paper in Infinitistic methods.) The Infinitistic methods paper is primarily concerned with proving the consistency of ZF. His arguments employ some very unusual ideas, especially that of the possibility of different length natural number series. The modal setting which he uses for these ideas and which is really all important is not reflected in the present paper. Only a simple representation of this idea is considered, namely, the use of *N, the nonstandard natural numbers, together with N, the standard natural numbers, to play the roles of a “long” and a “short” number series.

It will be useful to make a few general remarks before beginning on the technical details. These remarks are especially directed towards those people who have read Essenin-Volpin's work, the above-mentioned paper in particular and the one appearing in the proceedings of the 1968 Conference on Intuitionism and Proof Theory at Buffalo, New York.

I want to draw a comparison between the ultra-intuitionistic position of Essenin-Volpin on the one hand with the intuitionistic and realistic positions on the foundations of mathematics on the other hand. Intuitionism makes a transition from the traditional mathematical position (realism) that the rules of mathematical reasoning must be constructed so as to preserve truth (as known by an omniscient being about “the real world” of abstract mathematical objects) to the position that the rules of mathematical reasoning must be in accord with the process of knowing (performed by the “ideal mathematician” or “creative subject”) about the world of mental constructions. Ultra-intuitionism deepens and extends this transition to the position that the fundamental rules of mathematical reasoning must be in accord with processes of knowing accessible to human beings.
Π10 classes and Boolean combinations of recursively enumerable sets
Authors: Jockusch Carl G.
Published: May 2006

Let be the collection of all sets which are finite Boolean combinations of recursively enumerable (r.e.) sets of numbers. Dale Myers asked [private correspondence] whether there exists a nonempty class of sets containing no member of . In this note we construct such a class. The motivation for Myers' question was his observation (reported in [1]) that the existence of such a class is equivalent to the assertion that there is a finite consistent set of tiles which has no m-trial tiling of the plane for any m (obeying the “origin constraint”). (For explanations of these terms and further results on tilings of the plane, cf. [1] and [5].) In addition to the application to tilings, the proof of our results gives some information on bi-immune sets and on complete extensions of first-order Peano arithmetic.

A class of sets may be roughly described as the class of infinite binary input tapes for which a fixed Turing machine fails to halt, or alternatively as the class of infinite branches of a recursive tree of finite binary sequences. (In these definitions, sets of numbers are identified with the corresponding binary sequences.) Precise definitions, as well as many results concerning such classes, may be found in [3] and [4].
ZF ⊦ Σ40 determinateness
Authors: Paris J. B.
Published: May 2006

In this paper we show that in Zermelo-Fraenkel set theory (ZF) sets of reals are determinate.

Before proceeding to the proof it will be helpful to consider some previous work in this area. The first major result was obtained by Gale and Stewart [3] who showed that in ZF open games are determinate. This was then successively improved by Wolfe [4] to (and so of course ) and then by Morton Davis [1] to . The results of Morton Davis further showed that countable unions of sufficiently ‘simple’ determinate sets are also determinate. At this time, however, sets did not appear sufficiently simple for this method to be applied in order to get determinacy.

The next major advance was made by D. A. Martin who showed, using indiscernibles, that with large cardinal assumptions games are equivalent to certain open games (i.e., player I (II) has a winning strategy for the game iff I (II) has a winning strategy for the open game). Thus, by the Gale–Stewart result, games are determinate. Martin's result also showed that under these large cardinal assumptions sets are sufficiently simple for the Morton Davis method to be applied to them.
On descendingly incomplete ultrafilters
Authors: Kunen Kenneth , Prikry Karel
Published: May 2006

Throughout this paper, the letters α, β, κ, λ will denote infinite cardinals. Other Greek letters range over the ordinals.

The following definition is taken from Chang [1].
On order-types of models
Authors: Hodges Wilfrid
Published: May 2006

Let T be a theory in a first-order language L. Let L have a predicate ν0 ≺ ν1 such that in every model of T, the interpretation of ≺ is a linear ordering with infinite field. The order-type of this ordering will be called the order-type of the model .

Several recent theorems have the following form: if T has a model of order-type ξ then T has a model of order-type ζ (see [1]). We shall add one to the list. The new feature of our result is that the order-type ζ may be in a sense “opposite” to ξ. Silver's Theorem 2.24 of [3] is a corollary of Theorem 1 below.

Theorem 1. Let κ be a strong limit number (i.e. μ < κ implies 2μ < κ). Suppose λ < κ, and suppose that for every cardinal μ < κ, T has a model with where the order-type of contains no descending well-ordered sequences of length λ. Then for every cardinal μ ≥ the cardinality ∣L∣ of the language L, T has models and such that

(a) the field of is the union of ≤ ∣L∣ well-ordered (inversely well-ordered) parts;

(b) .

The proof is by Ehrenfeucht-Mostowski models; we presuppose [2].
Uniqueness and characterization of prime models over sets for totally transcendental first-order theories
Authors: Shelah Saharon
Published: May 2006

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).
Nonrecursive tilings of the plane. I
Authors: Hanf William
Published: May 2006

A finite set of tiles (unit squares with colored edges) is said to tile the plane if there exists an arrangement of translated (but not rotated or reflected) copies of the squares which fill the plane in such a way that abutting edges of the squares have the same color. The problem of whether there exists a finite set of tiles which can be used to tile the plane but not in any periodic fashion was proposed by Hao Wang [9] and solved by Robert Berger [1]. Raphael Robinson [7] gives a more detailed history and a very economical solution to this and related problems; we will assume that the reader is familiar with §4 of [7]. In 1971, Dale Myers asked whether there exists a finite set of tiles which can tile the plane but not in any recursive fashion. If we make an additional restriction (called the origin constraint) that a given tile must be used at least once, then the positive answer is given by the main theorem of this paper. Using the Turing machine constructed here and a more complicated version of Berger and Robinson's construction, Myers [5] has recently solved the problem without the origin constraint.

Given a finite set of tiles T1, …, Tn, we can describe a tiling of the plane by a function f of two variables ranging over the integers. f(i, j) = k specifies that the tile Tk is to be placed at the position in the plane with coordinates (i, j). The tiling will be said to be recursive if f is a recursive function.