bluuebunny/crossref_metadata_2025 huggingface dataset:
Pure denumerable Łukasiewiczian implication
Authors: Meyer R. K.
Published: May 2006

In [1], McCall and I offered an axiomatization of the implicational fragment of the 3-valued Łukasiewiczian system defined in [2]. The following axiom schemata sufficed, together with the rule of modus ponens.1
The decidability of certain intermediate propositional logics
Authors: Mckay C. G.
Published: May 2006

Acquaintance with [11] and [8] will be assumed. Let be the alphabet →, &, ν, ┐, (,), A1, A2, … where →(I), &(C), ν (D) and ┐(N) are called the connectives. The letters appearing in parentheses are the names of the connectives. A1, A2 … are the atoms.

Definition 1.1. A string S is an ICDN word iff there is a finite sequence of strings S1 … Sn = S such that for i, 1 ≤ i ≤ n, either S1 is an atom or S1 is one of the forms (S1→Sk), (S1 & Sk), (S1, ν Sk) or ┐S1,j, k ≤ i.
Constructively accessible ordinal numbers
Authors: Richter Wayne
Published: May 2006

In [11] the constructive ordinals were extended to constructive finite number classes by using systems of notations where mappings at limit ordinals are just partial recursive functions. It turned out that these systems are equivalent, both in terms of ordinals represented and the forms of the sets of notations, to extensions obtained by using mappings at limit ordinals which are partial recursive in (sets of notations for) previously defined number classes. In this article these results are extended to constructive transfinite number classes. We present a system (F, ||) which, in terms of our analogy with the classical ordinals, provides notations for the ordinals less than the first “constructively inaccessible” ordinal, and show that the above equivalence holds at least this far.
Extensions of the constructive ordinals
Authors: Richter Wayne
Published: May 2006

Kleene [5] mentions two ways of extending the constructive ordinals. The first is by relativizing the setOof notations for the constructive ordinals, using fundamental sequences which are partial recursive inO. In this way we obtain the setOOwhich provides notations for the ordinals less than ω1O. Continuing the process, the sequenceO,OO,, … and the corresponding ordinalsare obtained. A second possibility is to define (constructive) higher number classes in which partial recursive functions are used at limit ordinals to provide an “accessibility” mapping from a previously defined number class. The relationship between the ordinals obtained by the two methods of extension has been an open problem. Methods developed in this article are used to show that the two ways of extending the constructive ordinals are equivalent, provided the sets of notations for the higher number classes satisfy certain natural conditions. Equivalence is obtained, not only with respect to ordinals, but also with respect to the forms of the sets of notations for the higher number classes. Specifically, the fundamental fact that the sets of notations for the constructive ordinals are complete Π11sets generalizes to suitably defined higher number classes. As an application we prove that the ordinals of the Addison and Kleene [1] constructive third number class are exactly the ordinals less than ω1Oand the setof notations for their third number class is recursively isomorphic toOO.
A reduction of the recursion scheme
Authors: Gladstone M. D.
Published: May 2006

The class of primitive recursive functions may be defined as the closure of certain initial functions, namely the zero, successor and identity functions, under two schemes, namely composition (sometimes called “substitution”) and recursion. For a detailed definition the reader is referred to any standard work, for instance p. 219 of [2], by Kleene.
Short definitions of the ordinals
Authors: Brown Kenneth R. , Wang Hao
Published: May 2006

In this paper, a simple inductive characterization of the ordinal numbers is stated and developed. The characterization forms the basis for a set of axioms for ordinal theory and also for several short explicit definitions of the ordinals. The axioms are shown to be sufficient for ordinal theory, and, subject to suitable existence assumptions, each of the definitions is shown to imply the axioms.

The present results apply to the familiar von Neumann version of the ordinals, but the methods used are easily adapted to other versions.
On a set theory of bernays
Authors: Tharp Leslie H.
Published: May 2006

We are concerned here with the set theory given in [1], which we call BL (Bernays-Levy). This theory can be given an elegant syntactical presentation which allows most of the usual axioms to be deduced from the reflection principle. However, it is more convenient here to take the usual Von Neumann-Bernays set theory [3] as a starting point, and to regard BL as arising from the addition of the schema

where S is the formal definition of satisfaction (with respect to models which are sets) and ┌φ┐ is the Gödel number of φ which has a single free variable X.
E, R AND γ
Authors: Meyer Robert K. , Michael Dunn J.
Published: May 2006

By γ, we mean the rule, “From ├ A and ├ Ā V B, infer ├ B”.1 This rule has played an important and a controversial role in a set of relevant logics free of certain well-known paradoxes of implication, like AĀ-→B and A-→(B-→B). Among these logics we count the pioneering systems of strenge Implikation presented by Ackermann in [1],2 as well as the Anderson-Belnap systems E of entail-ment and R of relevant implication.3
Real numbers and functions in the Kleene hierarchy and limits of
recursive, rational functions
Authors: Shapiro N. Z.
Published: May 2006

Let ƒ be a real number. It is well known [7] that the set
of rational numbers which are less than ƒ is a recursive
set if and only if ƒ is representable as the limit of a
recursive, recursively convergent sequence of rational numbers. In this
paper we replace the condition that the set of rational numbers less than
ƒ is recursive by the condition that this set is at
various points in the Kleene hierarchy, and we replace the recursive,
recursively convergent limit by a variety of other recursive limiting
processes.
Infinitary logic and admissible sets
Authors: Barwise Jon
Published: May 2006

In recent years much effort has gone into the study of languages which
strengthen the classical first-order predicate calculus in various ways.
This effort has been motivated by the desire to find a language which is

(I) strong enough to express interesting properties not expressible by the
classical language, but

(II) still simple enough to yield interesting general results. Languages
investigated include second-order logic, weak second-order logic, ω-logic,
languages with generalized quantifiers, and infinitary logic.
Axioms for strong reduction in combinatory logic
Authors: Hindley Roger
Published: May 2006

In combinatory logic there is a system of objects which intuitively represent functions, and a binary relation between these objects, which represents the process of evaluating the result of applying a function to an argument. (This is explained fully in [1].) From this relation called weak reduction, “≥,” an equivalence relation is defined by saying that X is weakly equivalent to Y if and only if there exist n (with 0 ≤ n) and X0,…,Xη such that

It turns out that equivalent objects represent the same function, but two objects representing the same function need not be equivalent.
Generic expansions of structures
Authors: Knight Julia F.
Published: May 2006

In this paper, Cohen's forcing technique is applied to some problems in model theory. Forcing has been used as a model-theoretic technique by several people, in particular, by A. Robinson in a series of papers [1], [10], [11]. Here forcing will be used to expand a family of structures in such a way that weak second-order embeddings are preserved. The forcing situation resembles that in Solovay's proof that for any theorem φ of GB (Godel-Bernays set theory with a strong form of the axiom of choice), if φ does not mention classes, then it is already a theorem of ZFC. (See [3, p. 105] and [2, p. 77].)

The first application of forcing here is to the problem (posed by Keisler) of when is it possible to add a Skolem function to a pair of structures, one of which is an elementary substructure of the other, in such a way that the elementary embedding is preserved.

It is not always possible to find such a Skolem function. Payne [9] found an example involving countable structures with uncountably many relations. The author [4], [6] found an example involving uncountable structures with only two relations. The problem remains open in case the structures are required both to be countable and to have countable type. Forcing is used to obtain a positive result under some special conditions.
An application of Σ40 determinacy to the degrees of unsolvability
Authors: Jockusch Carl G.
Published: May 2006

If a and b are degrees of unsolvability, a is called (as in [1]) a minimal cover of b if b < a and no degree c satisfies b < c < a. A degree a is called a minimal cover if it is a minimal cover of some degree b. We show in ZF set theory that there is a degree d such that every degree a ≥ d is a minimal cover. In [1] it was remarked that this result follows via a lemma of D. A. Martin [4] from the determinacy of a certain Σ50 Gale-Stewart game (which in turn follows [5] from the existence of a measurable cardinal). The argument here is parallel to that of [1], but the essential new ingredient is the result of Paris [6] that Σ50 determinacy can be proved in ZF. Also it is necessary to replace the Σ50 game of [1] by a related Σ40 game and to use the method, rather than just the statement, of Martin's lemma.

Theorem. There is a degreedsuch that every degreea ≥ dis a minimal cover.

Proof. In a (Gale–Stewart) game on 2ω, players I and II construct a set of integers A as follows: At the nth stage, player I determines whether n ϵ A if n is even and player II if n is odd. Thus player I controls A0 and player II controls A1 where Ai = {n: 2n + i ϵ A}. Let Aij denote (Ai)j and let M (A, B) mean that the degree of A is a minimal cover of that of B. Consider now the particular game in which player I wins iff M(A, A00) holds.
On deciding the provability of certain fixed point statements
Authors: Boolos George
Published: May 2006

Terminology. PA is Peano Arithmetic, classical first-order arithmetic with induction. ⌈A⌉ is the formal numeral in PA for the Gödel number of A. – A is the negation of A, (A&B) is the conjunction of A and B, and Bew(x) is the usual provability predicate for PA. neg(x), conj(x, y), bicond(x, y), and bew(x) are terms of PA such that for all sentences A and B of PA ⊢PA, neg(˹A˺) = ˹−A˺ ⊢PA Conj(˹A˺, ˹B˺)= ˹(A&B)˺ ⊢PA bicond(˹A˺, ˹B˺)= ˹(A ↔ B)˺, and ⊢PA bew(˹A˺) = ˹Bew(˹A˺)˺. T is the sentence ‘0 = 0’ and Con is the usual sentence expressing the consistency of PA. If A (x) is any formula of PA, then a fixed point of A(x) is a sentence S such that ⊢PAS ↔ A(˹S˺). (It is well known that every formula of PA with one free variable has a fixed point.) The P-terms are defined inductively by: the variable x is a P-term; if t(x) and u(x) are P-terms, so are neg(t(x)), conj(t(x), u(x)), and bew(t(x)). A basic P-formula is a formula Bew(t(x)), where t(x) is a P-term; and a P-formula is a truth-functional combination of basic P-formulas. An F-sentence is a member of the smallest class that contains Con and contains −A, (A&B), and −Bew(˹−A˺) whenever it contains A and B. In [B] we gave a decision procedure for the class of true F-sentences.

−Bew(x), Bew(x), and Bew(neg(x)) are examples of P-formulas, and fixed points of these particular P-formulas have been studied by Gödel, Henkin [H] and Löb [L], and Jeroslow [J], respectively. In this note we show how to decide whether or not a fixed point of any given P-formula is provable in PA.
Partially ordered interpretations
Authors: Motohashi Nobuyoshi
Published: May 2006

In this paper, we shall define the “partially ordered interpretation” of a first order theory in another first order theory and state some recent results. Although an exact definition will be given in §4 below, we now give a brief outline. First of all, let us recall the “interpretations” defined by A. Tarski et al. in [17] and the “parametrical interpretations” defined by P. Hájek in [6], [7] and U. Felgner in [3]. Since “interpretations” can be considered as a special case of “parametrical interpretations”, we consider only the latter type of “interpretations”. A parametrical interpretation I of a first order language L in a consistent theory T′ (formulated in another first order language L′) consists of the following formulas:

(i) a unary formula C(p) (i.e. a formula with one designated free variable p), which is used to denote the range of parameters,

(ii) a binary formula U(p, x), which is intended to denote the pth universe for each parameter p,

(iii) an (n + 1)-ary formula Fp(p, x1 …, xn) for each n-ary predicate symbol P in L,

such that the formulas (∃p)C(p) and (∀p)(C(p)→(∃x)U(p, x)) are provable in T". Then, given a formula A in L and a parameter p, we define the interpretation Ip (A ) of A by I at p to be the formula which is obtained from A by replacing every atomic subformula P(*, …, *) in A by Fp(p, *,…,*), and relativizing every occurrence of quantifiers in A by U(p, * ). A sentence A in L is said to be I-provable in T′ if the sentence (∀p) (C(p)→ Ip(A)) is provable in T′. Then, it is obvious that every provable sentence in L is I-provable in T′. This is a basic result of “parametrical interpretations” and is used to prove the “consistency” of a theory T in L by showing that every axiom of T is I-provable in T′ when I is said to be a parametrical interpretation of T in T′. As is shown above, the word “interpretation” is used in the following three senses: interpretations of languages, interpretations of formulas and interpretations of theories. So, in this introduction we let the word “interpretation” denote “interpretation of languages”, for short.
On certain types and models for arithmetic
Authors: Blass Andreas
Published: May 2006

There is an analogy between concepts such as end-extension types and minimal types in the model theory of Peano arithmetic and concepts such as P-points and selective ultrafilters in the theory of ultrafilters on N. Using the notion of conservative extensions of models, we prove some theorems clarifying the relation between these pairs of analogous concepts. We also use the analogy to obtain some model-theoretic results with techniques originally used in ultrafilter theory. These results assert that every countable nonstandard model of arithmetic has a bounded minimal extension and that some types in arithmetic are not 2-isolated.
Formalisations of further ℵ0-valued Łukasiewicz propositional calculi
Authors: Rose Alan
Published: May 2006

It has been shown that, for all rational numbers r such that 0≤ r ≤ 1, the ℵ0-valued Łukasiewicz propositional calculus whose designated truth-values are those truth-values x such that r ≤ x ≤ 1 may be formalised completely by means of finitely many axiom schemes and primitive rules of procedure. We shall consider now the case where r is rational, 0≥r≤1 and the designated truth-values are those truth-values x such that r≤x≤1.

We note that, in the subcase of the previous case where r = 1, a complete formalisation is given by the following four axiom schemes together with the rule of modus ponens (with respect to C),

the functor A being defined in the usual way. The functors B, K, L will also be considered to be defined in the usual way. Let us consider now the functor Dαβ such that if P, Dαβ take the truth-values x, dαβ(x) respectively, α, β are relatively prime integers and r = α/β then

It follows at once from a theorem of McNaughton that the functor Dαβ is definable in terms of C and N in an effective way. If r = 0 we make the definition

We note first that if x ≤ α/β then dαβ(x)≤(β + 1)α/β − α = α/β. Hence

Let us now define the functions dnαβ(x) (n = 0,1,…) by

Since

it follows easily that

and that

Thus, if x is designated, x − α/β > 0 and, if n > − log(x − α/β)/log(β + 1), then (β + 1)n(x−α/β) > 1.
General random sequences and learnable sequences
Authors: Schnorr C. P. , Fuchs P.
Published: May 2006

Abstract

We formalise the notion of those infinite binary sequences z that admit a single program P which expresses the entire algorithmical structure of z. Such a program P minimizes the information which must be used in a relative computation for z. We propose two concepts with different strength for this notion, the learnable and the super-learnable sequences. We establish three different equivalent characterizations of learnable (super-learnable, resp.) sequences. In particular, we prove that a sequence z is learnable (super-learnable, resp.) if and only if there is a computable probability measure p such that p is Schnorr (Martin-Löf, resp.) p-random. There is a recursively enumerable sequence which is not learnable. The learnable sequences are invariant with respect to all total and effective transformations of infinite binary sequences.
A system of abstract constructive ordinals
Authors: Howard W. A.
Published: May 2006

As Gödel [6] has pointed out, there is a certain interchangeability between the intuitionistic notion of proof and the notion of constructive functional of finite type. He achieves this interchange in the direction from logic to functionals by his functional interpretation of Heyting arithmetic H in a free variable theory T of primitive recursive functionals of finite type. In the present paper we shall extend Gödel's functional interpretation to the case in which H and T are extended by adding an abstract notion of constructive ordinal. In other words, we obtain the Gödel functional interpretation of an intuitionistic theory U of numbers (i.e., nonnegative integers) and constructive ordinals in a free variable theory V of finite type over both numbers and constructive ordinals. This allows us to obtain an analysis of noniterated positive inductive definitions [8].

The notion of constructive ordinal to be treated is as follows. There is given a function J which embeds the nonnegative integers in the constructive ordinals. A constructive ordinal of the form Jn is said to be minimal. There is also given a function δ which associates to each constructive ordinal Z and number n a constructive ordinal δZn which we denote by Zn. When Z is nonminimal, each Zn is called an immediate predecessor of Z. The basic principle for forming constructive ordinals says: for every function f from numbers n to constructive ordinals, there exists a constructive ordinal Z such that Zn = fn for all n. The principle of transfinite induction with respect to constructive ordinals says: if a property Q(Z) of constructive ordinals Z holds for minimal Z, and if ∀nQ(Zn) → Q(Z) holds for all Z, then Q(Z) holds for all Z.
On the possibility of a Σ21well-ordering of the Baire space
Authors: Mansfield Richard
Published: May 2006

It is well known that the hypothesis that all real numbers are constructible in the sense of Gödel [1] implies the existence of a Σ21well-ordering of the Baire space [1, p. 67]. We are concerned with the converse to this theorem. From the assumption of the existence of a Σ21well-ordering with total domain, we derive various consequences which in the presence of a nonconstructible real seem highly pathological. However, while several of these consequences are obviously absurd, none have as yet been disproven. Indeed some of the stranger consistency proofs of Jensen seem to indicate that there is a possibility that they may be consistent. I am referring to such results as existence of a model for ZF set theory in which the degrees of constructibility form a sequence of typeω+ 1 with the (ω+ 1)st degree being the only one which contains a nonconstructible real, and that degree being the degree of a Δ31nonconstructible real.

In what follows we shall use the small Greek lettersα, β, γto range over the Baire spaceNNwhereNis the set of natural numbers. We assume that the reader is familiar with the use of trees to encode closed subsets of this space. The class Σ21is the collection of all those subsets of the Baire space which can be defined by a formula which is Σ21in a constructible parameter. Correspondingly Π21will be taken to mean Π11in a constructible parameter. The proof of the first lemma is left as an exercise. It involves nothing more than coding perfect sets by trees and then counting quantifiers.
Encodability of Kleene's O
Authors: Jockusch Carl G. , Soare Robert I.
Published: May 2006

Let ω be the nonnegative integers. G. E. Sacks once asked whether there exists an infinite X ⊆ ω such that, for all Y ⊆ X, ω1Yω1 where ω1 is the first nonrecursive ordinal. In this note we negatively answer this question by giving a simple proof that for every infinite set X ⊆ ω there exists Y ⊆ X such that the first recursively inaccessible ordinal. This is accomplished by proving that Hα is hyper-arithmetic in Y whereHα is the αth hyperjump of the empty set ∅, defined in a suitable sense for all ordinals

Background information and undefined notation can be found in Rogers [11]. In particular, we write A ≤hB(A ≤T B) if A is hyperarithmetical (recursive) in B, and A ≡hB if A ≤hB and B ≤hA. We will say that a set A is hyperarithmetically (recursively) encodable if, for every infinite set X ⊆ ω, there exists Y ⊆ X such that A ≤hY (A ≤TY). For any set A (hyperdegree a) let A′ (a′) denote the hyperjump of A (a). Let 0 denote the hyperdegree of ∅. A function f majorizes a function g if f(n) ≥ g(n) for every n. E1 is the representing (type-2) functional of

introduced by Tugué [13] (also Kleene [6]). Let be the smallest ordinal which is not the order type of any well-ordering recursive in E1. Information on can be found in Richter [9] and [10].
Hanf number of omitting type for simple first-order theories
Authors: Shelah Saharon
Published: May 2006

Let T be a complete countable first-order theory such that every ultrapower of a model of T is saturated. If T has a model omitting a type p in every cardinality < ℶ′, then T has a model omitting p in every cardinality. There is also a related theorem, and an example showing the ℶ′ cannot be improved.
Constructive assertions in an extension of classical mathematics
Authors: Lifschitz Vladimir
Published: May 2006

We distinguish between two kinds of mathematical assertions: objective and constructive. An objective assertion describes the universe of mathematical objects; a constructive one describes the (idealized) mathematician's ability to find mathematical objects with various properties. The familiar formalizations of classical mathematics are based on formal languages designed for expressing objective assertions only. The constructivist program stresses, on the contrary, the importance of constructive assertions; moreover, intuitionism claims that constructive activities of the mind constitute the very subject matter of mathematics, and thus questions the semantic status of objective assertions.

The purpose of this paper is to show that classical mathematics can be extended to include constructive sentences, so that both objective and constructive properties can be discussed in the framework of the same theory. To achieve this goal, we introduce a new property of mathematical objects, calculability.

The word “calculable” may be applied to objects of various types: natural numbers, integers, rational or real numbers, polynomials with rational or real coefficients, etc. In each case it has a different meaning, so that actually we define not one, but many new properties.
The equivalence of a generalized Martin's axiom to a combinatorial principle
Authors: Weiss William
Published: May 2006

A generalized version of Martin's axiom, called BACH, is shown to be equivalent to one of its combinatorial consequences, a generalization of P(c).
Decidability and finite axiomatizability of theories of ℵ0-categorical partially ordered sets
Authors: Schmerl James H.
Published: May 2006

Every ℵ0-categorical partially ordered set of finite width has a finitely axiomatizable theory. Every ℵ0-categorical partially ordered set of finite weak width has a decidable theory. This last statement constitutes a major portion of the complete (with three exceptions) characterization of those finite partially ordered sets for which any ℵ0-categorical partially ordered set not embedding one of them has a decidable theory.
Recursive constructions in topological spaces
Authors: Kalantari Iraj , Retzlaff Allen
Published: May 2006

We study topological constructions in the recursion theoretic framework of the lattice of recursively enumerable open subsets of a topological spaceX. Various constructions produce complemented recursively enumerable open sets with additional recursion theoretic properties, as well as noncomplemented open sets. In contrast to techniques in classical topology, we construct a disjoint recursively enumerable collection of basic open sets which cannot be extended to a recursively enumerable disjoint collection of basic open sets whose union is dense inX.
On the standard part of nonstandard models of set theory
Authors: Magidor Menachem , Shelah Saharon , Stavi Jonathan
Published: May 2006

We characterize the ordinals α of uncountable cofinality such that α is the standard part of a nonstandard model of ZFC (or equivalently KP).
Choice principles, the bar rule and autonomously iterated comprehension schemes in analysis
Authors: Feferman S. , Jäger G.
Published: May 2006

In [10] Friedman showed that (-AC) is a conservative extension of (-CA)<ε0for-sentences wherei= min(n+ 2, 4), i.e.,i= 2, 3, 4 forn= 0, 1, 2 +m. Feferman [5], [7] and Tait [11], [12] reobtained this result forn= 0, 1 and even with (-DC) instead of (-AC). Feferman and Sieg established in [9] the conservativeness of (-DC) over (-CA)<ε0for-sentences (ias above) for alln. In each paper, different methods of proof have been used. In particular, Feferman and Sieg showed how to apply familiar proof-theoretical techniques by passing through languages with Skolem functionals.

In this paper we study the same choice principles in the presence of theBar Rule(BR), which permits one to infer the scheme of transfinite induction on a primitive recursive relation ≺ when it has been proved that ≺ is wellfounded. The main result (Theorem 1 below) characterizes (-DC) + (BR) as a conservative extension of a system of the autonomously iterated-comprehension axiom for-sentences (idepending onnas above). Forn= 0 this has been proved by Feferman in the form that (-DC) + (BR) is a conservative extension of (-CA)<Γ0; this was first done in [8] by use of the Gödel functional interpretation for the stronger systemZω+μ+ (QF-AC) + (BR) and then more recently by the simpler methods of [9]. Jäger showed how the latter methods could also be used to obtain the general result of Theorem 1 below.
Real functions on the family of all well-ordered subsets of a partially ordered set
Authors: Todorčević Stevo
Published: May 2006

Definition 1 (Kurepa [3, p. 99]). Let E be a partially ordered set. Then σE denotes the set of all bounded well-ordered subsets of E. We consider σE as a partially ordered set with ordering defined as follows: st if and only if s is an initial segment of t.

Then σE is a tree, i.e., {s ∈ σ E∣ st} is well-ordered for every t ∈ σE. The trees of the form αE were extensively studied by Kurepa in [3]–[10]. For example, in [4], he used σQ and σR to construct various sorts of Aronszajn trees. (Here Q and R denote the rationals and reals, respectively.) While considering monotone mapping between some kind of ordered sets, he came to the following two questions several times:

P.1. Does there exist a strictly increasing rational function on σQ? (See [4, Problème 2], [5, p. 1033], [6, p. 841], [7, Problem 23.3.3].)

P.2. Let T be a tree in which every chain is countable and every level has cardinality <2ℵ0. Does there exist a strictly increasing real function on T? (See [6, p. 246] and [7].)

It is known today that Problem 2 is independent of the usual axioms of set theory (see [1]). Concerning Problem 1 we have the following.
QE rings in characteristic pn
Authors: Berline Chantal , Cherlin Gregory
Published: May 2006

We show that all QE rings of prime power characteristic are constructed in a straightforward way out of three components: a filtered Boolean power of a finite field, a nilpotent Jacobson radical, and the ring Zp. or the Witt ring W2(F4) (which is the characteristic four analogue of the Galois field with four elements).
Game sentences, recursive saturation and definability
Authors: Harnik Victor
Published: May 2006

In the past 10 years much progress occurred in the direction of unifying the treatment of finitary Lωω and infinitary logic. We have especially in mind the study of countable admissible fragments (of which Lωω is a particular case) initiated by Barwise in [1] (cf. also [2]), the introduction of -recursively saturated structures by Ressayre in [22] (for these were independently introduced in [3]) and game sentences as studied by Vaught in [26] (see also Svenonius [25] and Moschovakis [19], [20]). A good reference for these topics is [17].

In this paper we illustrate the use of these tools for deducing definability theorems. We go beyond the known results as seen from the discussion that follows.

Let L be a language and P a (say, unary) additional predicate. Consider a sentence σ(P) in the language L(P). There are two types of definability theorems: the “Beth type” and the “Svenonius type”. Beth's theorem [4] characterizes the condition:

(i)′ for any ;

while Svenonius' result [24] characterizes:

(i)″ for any , every L-automorphism of is an L(P)-automorphism.
Model companions and k-model completeness for the complete theories of Boolean algebras
Authors: Mead J. , Nelson G. C.
Published: May 2006

In studying mathematical logic, Boolean algebras can play an important role in the organization of syntactic properties of first-order theories. In this paper we are concerned with syntactical questions about the complete theories of Boolean algebras, Tarski [12] and Ershov [4]. We give a syntactic characterization of the languages introduced in [4] by Ershov in terms of number of alternations of quantifiers and show that extensions with respect to these natural languages are equivalent to extensions with respect to ∀k(L−1) ⋃ ∃k(L−1) for specified, k. The main motivation for this paper was to examine a generalized notion of model completeness of A. Robinson [14], called k-model completeness, and to find real mathematical structures having these properties in a nontrivial way; this turns out to be realized in the very natural setting of Boolean algebras and our results are very definitive about these notions in that setting. Also, we point out here the connections of these notions with those examined by Chang in [2] and observe that the syntactic properties of the complete theories of Boolean algebras have much in common with those properties enjoyed by ∀n-axiomatizable theories which are categorical for “some” infinite cardinal. Finally, a complete characterization of the model companions of the complete theories of Boolean algebras is given with respect to Ershov's languages [4].
Two-dimensional partial orderings: Undecidability
Authors: Manaster Alfred B. , Rosenstein Joseph G.
Published: May 2006

In this paper we examine the class of two-dimensional partial orderings from the perspective of undecidability. We shall see that from this perspective the class of 2dpo's is more similar to the class of all partial orderings than to its one-dimensional subclass, the class of all linear orderings. More specifically, we shall describe an argument which lends itself to proofs of the following four results:

(A) the theory of 2dpo's is undecidable:

(B) the theory of 2dpo's is recursively inseparable from the set of sentences refutable in some finite 2dpo;

(C) there is a sentence which is true in some 2dpo but which has no recursive model;

(D) the theory of planar lattices is undecidable.

It is known that the theory of linear orderings is decidable (Lauchli and Leonard [4]). On the other hand, the theories of partial orderings and lattices were shown to be undecidable by Tarski [14], and that each of these theories is recursively inseparable from its finitely refutable statements was shown by Taitslin [13]. Thus, the complexity of the theories of partial orderings and lattices is, by (A), (B) and (D), already reflected in the 2dpo's and planar lattices.

As pointed out by J. Schmerl, bipartite graphs can be coded into 2dpo's, so that (A) and (B) could also be obtained by applying a Rabin-Scott style argument [9] to Rogers' result [11] that the theory of bipartite graphs is undecidable and to Lavrov's result [5] that the theory of bipartite graphs is recursively inseparable from the set of sentences refutable in some finite bipartite graph. (However, (C) and (D) do not seem to follow from this type of argument.)
Minimal forms inλ-cakulus computations
Authors: Böhm Corrado , Micali Silvio
Published: May 2006

The notion of a minimal form is defined as an extension of the notion of a normal form inλ-β-calculus and its meaning is discussed in a computational environment. The features of the Knuth-Gross reduction strategy are used to prove that to possess a minimal form, for a generic term, is a semidecidable predicate.
An invariance notion in recursion theory
Authors: Byerly Robert E.
Published: May 2006

A set of gödel numbers is invariant if it is closed under automorphisms of (ω, ·), where ω is the set of all gödel numbers of partial recursive functions and · is application (i.e., n · m ≃ φn(m)). The invariant arithmetic sets are investigated, and the invariant recursively enumerable sets and partial recursive functions are partially characterized.
On the expressibility hierarchy of Magidor-Malitz quantifiers
Authors: Rubin Matatyahu , Shelah Saharon
Published: May 2006

We prove that the logics of Magidor-Malitz and their generalization by Rubin are distinct even for PC classes.

Let M ⊨ Qnx1 … xnφ(x1 … xn) mean that there is an uncountable subset A of ∣M∣ such that for every a1 …, an ∈ A, M ⊨ φ[a1, …, an].

Theorem 1.1 (Shelah) (♢ℵ1). For every n ∈ ωthe classKn+1 = {‹A, R› ∣ ‹A, R› ⊨ ¬ Qn+1x1 … xn+1R(x1, …, xn+1)} is not an ℵ0-PC-class in the logic ℒn, obtained by closing first order logic underQ1, …, Qn. I.e. for no countable ℒn-theory T, isKn+1the class of reducts of the models of T.

Theorem 1.2 (Rubin) (♢ℵ1). Let M ⊨ QE x yφ(x, y) mean that there is A ⊆ ∣M∣ such thatEA, φ = {‹a, b› ∣ a, b ∈ A and M ⊨ φ[a, b]) is an equivalence relation on A with uncountably many equivalence classes, and such that each equivalence class is uncountable. Let KE = {‹A, R› ∣ ‹A, R› ⊨ ¬ QExyR(x, y)}. Then KE is not an ℵ0-PC-class in the logic gotten by closing first order logic under the set of quantifiers {Qn ∣ n ∈ ω) which were defined in Theorem 1.1.
Some model theory of modules. I. On total transcendence of modules
Authors: Rothmaler Philipp
Published: May 2006

This is the first part of a series of papers on certain topics of model theory of modules, which will further consist of Part II. On stability and categoricity of flat modules and Part III. On infiniteness of sets definable in modules. Although these parts are only weakly connected, it is convenient to have common background and notation. The first part was written in Summer 1980, when I did not know about either footnote (3) appearing in the final version of [GA 2] or about the work of the “Bedford College Group” concerning stability theory of modules. I would like to thank Wilfrid Hodges and Mike Prest for their interest in this note, which encouraged me to include it as the first part of the present series, and for acquainting me with their unpublished work, to which I refer in footnotes. I should also like to thank the referee for his suggestions, in particular for correcting the argument in Remark (5) and for drawing my attention to [Z-H].

A syntactical analysis of Zimmermann's notion of “endlich matriziellen Untergruppen” of modules [ZI, p. 1087] shows that it coincides with the notion of subgroups definable by positive primitive formulae (without parameters) [GA 1, p. 80]. Then combination of [ZI, Folgerung 3.4] with [GA 1, Lemma 5] (or [GA 2, Theorem 1] for uncountable rings) yields purely algebraic criteria for total transcendence of modules. I present here a proof of this result using only the following facts.

(G1) A module M is totally transcendental iff it satisfies the minimal condition on subgroups definable by positive primitive formulae (without parameters) [GA 1, Lemma 5] (and [GA 2, Theorem 1] for uncountable rings).
Arithmetical interpretations of dynamic logic
Authors: Hájek Petr
Published: May 2006

An arithmetical interpretation of dynamic propositional logic (DPL) is a mapping ƒ satisfying the following: (1) ƒ associates with each formula A of DPL a sentence ƒ(A) of Peano arithmetic (PA) and with each program α a formula ƒ(α) of PA with one free variable describing formally a supertheory of PA; (2) ƒ commutes with logical connectives; (3) ƒ([α]A) is the sentence saying that ƒ(A) is provable in the theory ƒ(α); (4) for each axiom A of DPL, ƒ(A) is provable in PA (and consequently, for each A provable in DPL, ƒ(A) is provable in PA). The arithmetical completeness theorem is proved saying that a formula A of DPL is provable in DPL iff for each arithmetical interpretation ƒ, ƒ(A) is provable in PA. Various modifications of this result are considered.
Rungs and trees
Authors: Masseron Marcel
Published: May 2006

In a recent work on -recursivity ([M] in which the principal result of [G.2] is obtained by more direct methods) I have given a very simple lemma on the structure of the so-called rungs [G.1] which enables us to describe precisely the relation they have with Jervell's tree [J] in the wellfounded case (R.O. Gandy has also worked out this relation in the wellfounded case, but with techniques very different from those introduced here).

In the present work I treat the general case in §§I and II. The results are summarized in §III. These results are then exploited by means of the operator Σ*, which is the principal tool of Lemma (4.1) (i.e. the generalized version of the previous structural lemma). A systematical use of Σ* is also the basis of the study of ladders in the last section.

Recall that the notions of rungs and ladders were introduced by J.-Y. Girard [G, 0] and [G.1] as a basic tool for ordinal analysis of Π½-logic (i.e. roughly speaking, logic with β-rule) and the introduction of trees and homogeneous trees by H.R. Jervell is a first attempt to give to these notions a geometrical interpretation without any explicit mention of functors and categorical limits. In fact, as it is evident in the last section of the present paper, limits play a modest role in the study of ladders, but their properties with respect to limits are of fundamental interest in their applications (a domain which is out of the scope of this basic work. Readers interested in applications to ordinal analysis are invited to consult the references). Note that my trees are not exactly those introduced by H.R. Jervell: his extra symbols λ and ρ are respectively changed into 0 and the type of the concerned tree. More important is the fact that we consider only the extremal nodes of the trees. The objects so obtained are then as close as possible to Girard's dendroids.

I am indebted to J.-Y. Girard for his advice about my work.
Double jumps of minimal degrees
Authors: Jockusch Carl G. , Posner David B.
Published: May 2006

This paper concerns certain relationships between the ordering of degrees of unsolvability and the jump operation. It is shown that every minimal degree a < 0′ satisfies a″ = 0″. To restate this result in more suggestive language and compare it with related results, we shall use notation based on the now standard terminology of “high” and “low” degrees. Let Hn be the class of degrees a < 0′ such that a(n) = 0(n+1), and let Ln be the class of degrees a ≤ 0′ such that an = 0n. (Observe that Hi ⊆ Lj and Li ⊆ Lj, whenever i ≤ j, and Hi ∩ Lj = ∅ for all i andj.) The result mentioned above may now be restated in the form that every minimal degree a ≤ 0′ is in L2. This extends an earlier result of S. B. Cooper ([1], see also [4]) that no minimal degree a < 0′ is in H1. In the other direction, Sasso, Epstein, and Cooper ([10], [15]) have shown that there is a minimal degree a < 0′ which is not in L1. Also, C.E.M. Yates [14, Corollary 11.14], showed the existence of a minimal degree a < 0′ in L1. Thus each minimal degree a < 0′ lies in exactly one of the two classes L1L2 – L1 and each of the classes contains minimal degrees.

Our results are not restricted to the degrees below 0′. We show in fact that every minimal degree a satisfies a″ = (a ∪ 0′)′. To restate this result and discuss extensions of it, we extend the “high-low” classification of degrees from the degrees below 0′ to degrees in general. There are a number of fairly plausible ways of doing this, but we choose the one way we know of doing so which leads to interesting results. Let GHn be the class of degrees a such that a(n) = (a ∪ 0′)(n), and let GLn be the class of degrees a such that a(n) = (a ∪ 0′)(n−1).
Theories with a finite number of countable models
Authors: Woodrow Robert E.
Published: May 2006

We give two examples. T0 has nine countable models and a nonprincipal 1-type which contains infinitely many 2-types. T1, has four models and an inessential extension T2 having infinitely many models.
Further consistency and independence results in NF obtained by the permutation method
Authors: Forster T. E.
Published: May 2006

The permutation method was first applied to NF by Scott; other workers have published results ([2], [3]; or see [4] for a survey). Some of the results proved here have a more metalogical character than most previously yielded by this method. Hinnion and Petry (unpublished, but see [4]) proved that the existence of objects x such that x = {y: x∈y} is consistent with NF. (The significance of this is that the operation that sends x to {y: x∈y} respects ∈ and is thus an embedding.) It is demonstrated below that the existence of such objects is independent of the axioms of NF.

The existence of nontrivial automorphisms of the universe is not an interesting possibility in ZF, since it contradicts wellfoundedness. Similar auguments are not available in NF, however, and it is shown below that if NF + AC for pairs is consistent, then we can consistently add an axiom stating that there is a ∈-automorphism of the universe that is a set of the model. (In the proof given below, the automorphism is in fact of order 2, but natural enrichments of the construction enable one to find automorphisms of other orders with suitable versions of choice as additional hypotheses.)
A complete theory with arbitrarily large minimality ranks
Authors: Woodrow Robert E. , Knight Julia F.
Published: May 2006

An example is given of a complete theory with minimal models of arbitrarily large minimality rank.
R. e. presented linear orders
Authors: Roy Dev Kumar
Published: May 2006

This paper looks at linear orders in the following way. A preordering is given, which is linear and recursively enumerable. By performing the natural identification, one obtains a linear order for which equality is not necessarily recursive. A format similar to Metakides and Nerode's [3] is used to study these linear orders. In effective studies of linear orders thus far, the law of antisymmetry (x ≦ y ∧ y ≦ x ⇒ y) has been assumed, so that if the order relation x ≦ y is r.e. then x < y is also r.e. Here the assumption is dropped, so that x < y may not be r.e. and the equality relation may not be recursive; the possibility that equality is not recursive leads to new twists which sometimes lead to negative results.

Reported here are some interesting preliminary results with simple proofs, which are obtained if one looks at these objects with a view to doing recursion theory in the style of Metakides and Nerode. (This style, set in [3], is seen in many subsequent papers by Metakides and Nerode, Kalantari, Remmel, Retzlaff, Shore, and others, e.g. [1], [4], [6], [7], [8], [11]. In a sequel, further investigations will be reported which look at r.e. presented linear orders in this fashion and in the context of Rosenstein's comprehensive work [10].

Obviously, only countable linear orders are under consideration here. For recursion-theoretic notation and terminology see Rogers [9].
Some contributions to definability theory for languages with generalized quantifiers
Authors: Baldwin John T. , Miller Douglas E.
Published: May 2006

One of the first results in model theory [12] asserts that a first-order sentence is preserved in extensions if and only if it is equivalent to an existential sentence.

In the first section of this paper, we analyze a natural program for extending this result to a class of languages extending first-order logic, notably including L(Q) and L(aa), respectively the languages with the quantifiers “there exist un-countably many” and “for almost all countable subsets”.

In the second section we answer a question of Bruce [3] by showing that this program cannot resolve the question for L(Q). We also consider whether the natural class of “generalized Σ-sentences” in L(Q) characterizes the class of sentences preserved in extensions, refuting the relativized version but leaving the unrestricted question open.

In the third section we show that the analogous class of L(aa)-sentences preserved in extensions does not include (up to elementary equivalence) all such sentences. This particular candidate class was nominated, rather tentatively, by Bruce [3].

In the fourth section we show that under rather general conditions, if L is a countably compact extension of first-order logic and T is an ℵ1-categorical first-order theory, then L is trivial relative to T.
Calculating self-referential statements: Guaspari sentences of the first kind
Authors: Smoryński C.
Published: May 2006

Beginning in 1960, and continuing for about a decade and a half, Shepherdson's self-referential formulae dominated the applications of diagonalization in metamathematics. In 1976, it was doubly toppled from its position of supremacy by two demonstrably more powerful such sentences introduced by D. Guaspari. The goal of the present note is to understand and explain the first (and, for the time being, more important) of Guaspari's self-referential sentences, which we dub “Guaspari sentences of the first kind”, or, less poetically, “Guaspari fixed points”.

Both Shepherdson's and Guaspari's fixed points are generalizations of the Rosser sentence. But, where Shepherdson merely tacks on side-formulae, Guaspari takes a more revolutionary step: He views the basic components, PrT(⌈¬φ⌉) and PrT(⌈φ⌉), of the Rosser sentence as attempts to refute something and replaces them by refutations of something else. Ignoring their Shepherdsonesque side-formulae (tacked on for the sake of more esoteric applications), our analysis of Guaspari fixed points can be viewed as merely the isolation of those properties whose refutations can be used in this context.

In §1 we offer the outcome of this analysis—i.e. a delineation of properties whose refutations can so be used. Some simple examples are cited and the Guaspari fixed points are defined. The main theorem—a master Fixed Point Calculation—is proven in §2.
Canonization theorems and applications
Authors: Shelah Saharon
Published: May 2006

We improve the canonization theorems generalizing the Erdös-Rado theorem, and as a result complete the answer to “When does a Hausdorff space of cardinality χ necessarily have a discrete subspace of cardinality k” We also improve the results on existence of free subsets.