bluuebunny/crossref_metadata_2025 huggingface dataset:
On supervaluations in free logic
Authors: Woodruff Peter W.
Published: May 2006

The concepts “classical valuation” and “supervaluation” were introduced by van Fraassen around 1966, to provide a semantic analysis of the then extant axiomatic systems of free logic. Consider an atomic sentence

and a “partial” model which fails to interpret c. Then (1) has no truth value in , nor does

While the valuelessness of (1) was found intuitively acceptable, that of (2) was not. Indeed, (2) and all other tautologies are theorems of free logic.

Van Fraassen found a way to accommodate both intuitions. He interprets the unproblematic atomic sentences as usual, while “interpreting” those like (1) by simply assigning them a truth-value in arbitrary fashion. Then a truth-value for every sentence can be defined in the usual way; the result van Fraassen calls a “classical valuation” of the language. The arbitrary element in any given classical valuation is then eliminated by passage to the “supervaluation” over , which agrees with the classical valuations where they agree among themselves, and otherwise is undefined. In the supervaluation over , (1) is valueless but (2) true (since true on all classical valuations), as was required.

There is a slight, but crucial oversimplification in the preceding account. Evaluation of the sentence

requires prior evaluation of the open formula

But here mere assignment of truth-value is not enough; a whole set must be arbitrarily assigned as extension. The quantification over classical valuations involved in passage to the supervaluation thus involves an implicit quantification over subsets of the domain of : supervaluations are second order.
Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ2 sets are dense
Authors: Cooper S. B.
Published: May 2006

As in Rogers [3], we treat the partial degrees as notational variants of the enumeration degrees (that is, the partial degree of a function is identified with the enumeration degree of its graph). We showed in [1] that there are no minimal partial degrees. The purpose of this paper is to show that the partial degrees below 0′ (that is, the partial degrees of the Σ2 partial functions) are dense. From this we see that the Σ2 sets play an analagous role within the enumeration degrees to that played by the recursively enumerable sets within the Turing degrees. The techniques, of course, are very different to those required to prove the Sacks Density Theorem (see [4, p. 20]) for the recursively enumerable Turing degrees.

Notation and terminology are similar to those of [1]. In particular, We, Dx, 〈m, n〉, ψe are, respectively, notations for the e th r.e. set in a given standard listing of the r.e. sets, the finite set whose canonical index is x, the recursive code for (m, n) and the e th enumeration operator (derived from We). Recursive approximations etc. are also defined as in [1].

Theorem 1. If B and C are Σ2sets of numbers, and B ≰e C, then there is an e-operator Θ with

Proof. We enumerate an e-operator Θ so as to satisfy the list of conditions:

Let {Bs ∣ s ≥ 0}, {Cs ∣ s ≥ 0} be recursive sequences of approximations to B, C respectively, for which, for each х, х ∈ B ⇔ (∃s*)(∀s ≥ s*)(х ∈ Bs) and х ∈ C ⇔ (∃s*)(∀s ≥ s*)(х ∈ Cs).
The consistency of the axiom of universality for the ordering of cardinalities
Authors: Forti Marco , Honsell Furio
Published: May 2006

T. Jech [4] and M. Takahashi [7] proved that given any partial ordering R in a model of ZFC there is a symmetric submodel of a generic extension of where R is isomorphic to the injective ordering on a set of cardinals.

The authors raised the question whether the injective ordering of cardinals can be universal, i.e. whether the following axiom of “cardinal universality” is consistent:

CU. For any partially ordered set (X, ≼) there is a bijection f:X → Y such that

(i.e. x ≼ y iff ∃g: f(x) → f(y) injective). (See [1].)

The consistency of CU relative to ZF0 (Zermelo-Fraenkel set theory without foundation) is proved in [2], but the transfer method of Jech-Sochor-Pincus cannot be applied to obtain consistency with full ZF (including foundation), since CU apparently is not boundable.

In this paper the authors define a model of ZF + CU as a symmetric submodel of a generic extension obtained by forcing “à la Easton” with a class of conditions which add κ generic subsets to any regular cardinal κ of a ground model satisfying ZF + V = L.
Decidable subspaces and recursively enumerable subspaces
Authors: Ash C. J. , Downey R. G.
Published: May 2006

A subspace V of an infinite dimensional fully effective vector space V∞ is called decidable if V is r.e. and there exists an r.e. W such that V ⊕ W = V∞. These subspaces of V∞ are natural analogues of recursive subsets of ω. The set of r.e. subspaces forms a lattice L(V∞) and the set of decidable subspaces forms a lower semilattice S(V∞). We analyse S(V∞) and its relationship with L(V∞). We show:

Proposition. Let U, V, W ∈ L(V∞) where U is infinite dimensional andU ⊕ V = W. Then there exists a decidable subspace D such that U ⊕ D = W.

Corollary. Any r.e. subspace can be expressed as the direct sum of two decidable subspaces.

These results allow us to show:

Proposition. The first order theory of the lower semilattice of decidable subspaces, Th(S(V∞), is undecidable.

This contrasts sharply with the result for recursive sets.

Finally we examine various generalizations of our results. In particular we analyse S*(V∞), that is, S(V∞) modulo finite dimensional subspaces. We show S*(V∞) is not a lattice.
Bases of supermaximal subspaces and Steinitz systems. I
Authors: Downey Rod
Published: May 2006

One of the most interesting concepts arising from the study ofL(V∞), the lattice of r.e. subspaces of afully effectivevector space of infinite dimension (cf. [6], [7] or [10]), was that of asupermaximalsubspace. Supermaximal subspaces ofV∞were those with the fewest possible r.e. superspaces, that is, we sayM∈L(L∞) issupermaximalif dim(V∞/M) = ∞ and for allQ∈L(V∞) withQ⊇M, either dim(Q/M) < ∞ orQ=V∞. These spaces were particularly interesting because they had no natural analogue inL(ω), the lattice of r.e. sets. Later Metakides and Nerode [8], Baldwin [1] and the author [2] found that supermaximalsubstructuresoccurred in more general settings. In particular, they were found to occur inL(F∞), the lattice of r.e. algebraically closed subfields ofF∞(a recursively presented field of infinite transcendence degree) (cf. [3]). The main tool in these later papers was the concept of aSteinitz (closure) system with recursive dependence(cf. [1], [2], [4] or [8]). We assume familiarity with the definitions and basic results of Metakides and Nerode [8], and only give a brief sketch of some nonstandard facts in §2. If the reader is not familiar with Steinitz systems he is advised to either obtain [1] or [2], or simply identify aSteinitz system(U, cl) with (V∞, *), that is, he should identifyUwithV∞, and cl(A) withA*, the subspace generated byA.
A decidable subclass of the minimal Gödel class with identity
Authors: Goldfarb Warren D. , Gurevich Yuri , Shelah Saharon
Published: May 2006

The minimal Gödel class with identity (MGCI) is the class of closed, prenex quantificational formulas whose prefixes have the form ∀x1∀x2∃x3 and whose matrices contain arbitrary predicate letters and the identity sign “=”, but contain no function signs or individual constants. The MGCI was shown undecidable (for satisfiability) in 1983 [Go2]; this both refutes a claim of Gödel's [Gö, p. 443] and settles the decision problem for all prefix-classes of quantification theory with identity.

In this paper, we show the decidability of a natural subclass of the MGCI. The formulas in this subclass can be thought of as exploiting only half of the power of the existential quantifier. That is, since an MGCI formula has prefix ∀x1∀x2∃x3, in general its truth in a model requires for any elements a and b, the existence of both a witness for and a witness for . The formulas we consider demand less: they require, for any elements a and b, a witness for the unordered pair {a, b}, that is, a witness either for or for .
Categoricity and ranks
Authors: Saffe Jürgen
Published: May 2006

In this paper we investigate the connections between categoricity and ranks. We use stability theory to prove some old and new results.
Cylindric-relativised set algebras have strong amalgamation
Authors: Németi I.
Published: May 2006

In algebra, the properties of having the (strong) amalgamation property and epis being surjective are well investigated; see the survey [10]. In algebraic logic it is shown that to these algebraic properties there correspond interesting logical properties, see e.g. [15], [12], [4], and [8, p. 311, Problem 10 and the remark below it]. In the present paper we show that the varieties Crsα (of cylindric-relativised set algebras) and Boα (of Boolean algebras with operators) have the strong amalgamation property. These contrast to the following result proved in Pigozzi [15]: No class K with Gsα ⊆ K ⊆ CAα has amalgamation property. Note that Gsα ⊆ Crsα ⊆ Boα and CAα ⊆ Boα. For related results see [3], [1], [16], [11]. For more connections with logic and abstract model theory see [14] and §4.3 of [9].

BA denotes the class of all Boolean algebras. Let α be any ordinal. From now on, throughout in the paper, α is an arbitrary but fixed ordinal. Recall from [7, p. 430, Definition 2.7.1] that an α-dimensional BA with operators, a Boα, is an algebra = 〈A, + −, ci, dij〉i, j ∈ α of the same similarity type as CAα's such that , is a BA and the operations ci (i ∈ α) are additive, i.e., ⊨ ci(x + y) = cix + ciy for all i ⊨ α. If ⊨ Boα then I is called the Boolean reduct of . Note that BA = Bo0. A Boα is said to be normal if {ci 0 = 0: i ∈ α} is valid in it, and a Boα is said to be extensive if {x ≤ cix: i ∈ α} is valid in it. Boα's were introduced in [17].

The class Crsα of all cylindric-relativised set algebras is defined in Definition 1.1.1 (iii) of [8, p. 4]. We give a definition in the present paper, too—see Definition 5 below. It is shown in [13] that ICrsα is a variety.

Our main result is (i) of Theorem 1 below, but we obtain (ii)–(vi), too, as a byproduct from the proof.
A probabilistic interpolation theorem
Authors: Hoover Douglas N.
Published: May 2006

The probability logic is a logic with a natural interpretation on probability spaces (thus, a logic whose model theory is part of probability theory rather than a system for putting probabilities on formulas of first order logic). Its exact definition and basic development are contained in the paper [3] of H. J. Keisler and the papers [1] and [2] of the author. Building on work in [2], we prove in this paper the following probabilistic interpolation theorem for .

Let L be a countable relational language, and let A be a countable admissible set with ω ∈ A (in this paper some probabilistic notation will be used, but ω will always mean the least infinite ordinal). is the admissible fragment of corresponding to A. We will assume that L is a countable set in A, as is usual in practice, though all that is in fact needed for our proof is that L be a set in A which is wellordered in A.

Theorem. Let ϕ(x) and ψ(x) be formulas of LAP such that

where ε ∈ [0, 1) is a real in A (reals may be defined in the usual way as Dedekind cuts in the rationals). Then for any real d > ε¼, there is a formula θ(x) of (L(ϕ) ∩ L(ψ))AP such that

and
Decision problems concerning S-arithmetic groups
Authors: Grunewald Fritz , Segal Daniel
Published: May 2006

This paper is a continuation of our previous work in [12]. The results, and some applications, have been described in the announcement [13]; it may be useful to discuss here, a little more fully, the nature and purpose of this work.

We are concerned basically with three kinds of algorithmic problem: (1) isomorphism problems, (2) “orbit problems”, and (3) “effective generation”.

(1) Isomorphism problems. Here we have a class of algebraic objects of some kind, and ask: is there a uniform algorithm for deciding whether two arbitrary members of are isomorphic? In most cases, the answer is no: no such algorithm exists. Indeed this has been one of the most notable applications of methods of mathematical logic in algebra (see [26, Chapter IV, §4] for the case where is the class of all finitely presented groups). It turns out, however, that when consists of objects which are in a certain sense “finite-dimensional”, then the isomorphism problem is indeed algorithmically soluble. We gave such algorithms in [12] for the following cases:

= {finitely generated nilpotent groups};

= {(not necessarily associative) rings whose additive group is finitely generated};

= {finitely Z-generated modules over a fixed finitely generated ring}.

Combining the methods of [12] with his own earlier work, Sarkisian has obtained analogous results with the integers replaced by the rationals: in [20] and [21] he solves the isomorphism problem for radicable torsion-free nilpotent groups of finite rank and for finite-dimensional Q-algebras.
Jumps of quasi-minimal enumeration degrees
Authors: McEvoy Kevin
Published: May 2006

Enumeration reducibility is a reducibility between sets of natural numbers defined as follows: A is enumeration reducible to B if there is some effective operation on enumerations which when given any enumeration of B will produce an enumeration of A. One reason for interest in this reducibility is that it presents us with a natural reducibility between partial functions whose degree structure can be seen to extend the structure of the Turing degrees of unsolvability. In [7] Friedberg and Rogers gave a precise definition of enumeration reducibility, and in [12] Rogers presented a theorem of Medvedev [10] on the existence of what Case [1] was to call quasi-minimal degrees. Myhill [11] also defined this reducibility and proved that the class of quasi-minimal degrees is of second category in the usual topology. As Gutteridge [8] has shown that there are no minimal enumeration degrees (see Cooper [3]), the quasi-minimal degrees are very much of interest in the study of the structure of the enumeration degrees. In this paper we define a jump operator on the enumeration degrees which was introduced by Cooper [4], and show that every complete enumeration degree is the jump of a quasi-minimal degree. We also extend the notion of a high Turing degree to the enumeration degrees and construct a “high” quasi-minimal enumeration degree—a result which contrasts with Cooper's result in [2] that a high Turing degree cannot be minimal. Finally, we use the Sacks' Jump Theorem to characterise the jumps of the co-r.e. enumeration degrees.
Combinatorics on ideals and forcing with trees
Authors: Groszek Marcia J.
Published: May 2006

Classes of forcings which add a real by forcing with branching conditions are examined, and conditions are found which guarantee that the generic real is of minimal degree over the ground model. An application is made to almost-disjoint coding via a real of minimal degree.
Complete theories with only universal and existential axioms
Authors: Lachlan A. H.
Published: May 2006

Let T be a complete first-order theory over a finite relational language which is axiomatized by universal and existential sentences. It is shown that T is almost trivial in the sense that the universe of any model of T can be written . where F is finite and I1, I2, …, In are mutually indiscernible over F. Some results about complete theories with ∃∀-axioms over a finite relational language are also mentioned.
Nonstandard characterizations of recursive saturation and resplendency
Authors: Smith Stuart T.
Published: May 2006

We prove results about nonstandard formulas in models of Peano arithmetic which complement those of Kotlarski, Krajewski, and Lachlan in [KKL] and [L]. This enables us to characterize both recursive saturation and resplendency in terms of statements about nonstandard sentences. Specifically, a model of PA is recursively saturated iff is nonstandard and -logic is consistent. is resplendent iff is nonstandard, -logic is consistent, and every sentence φ which is consistent in -logic is contained in a full satisfaction class for . Thus, for models of PA, recursive saturation can be expressed by a (standard) -sentence and resplendency by a -sentence.
Tarski on truth and logical consequence
Authors: Etchemendy John
Published: May 2006

Tarski's writings on the concepts of truth and logical consequence rank among the most influential works in both logic and philosophy of the twentieth century. Because of this, it would be impossible to give a careful and accurate account of how far that influence reaches and of the complex route by which it spread. In logic, Tarski's methods of defining satisfaction and truth, as well as his work pioneering general model-theoretic techniques, have been entirely absorbed into the way the subject is presently done; they have become part of the fabric of contemporary logic, material presented in the initial pages of every modern textbook on the subject. In philosophy, the influence has been equally pervasive, extending not only to work in semantics and the philosophies of logic and language, but to less obviously allied areas such as epistemology and the philosophy of science as well.

Rather than try to chart the wide-ranging influence of these writings or catalog the important research they have inspired, I will concentrate on various confusions and misunderstandings that continue to surround this work. For in spite of the extensive attention the work has received in the past fifty years, especially in the philosophical literature, misunderstandings of both conceptual and historical sorts are still remarkably widespread. Indeed in the philosophical community, recent reactions to Tarski's work on truth range from Karl Popper's “intense joy and relief” at Tarski's “legitimation” of the notion [1974, p. 399], to Hilary Putnam's assessment that “as a philosophical account of truth, Tarski's theory fails as badly as it is possible for an account to fail” [1985, p. 64]. Opinions have not exactly converged.
Generalizations of Deissler's Minimality Rank
Authors: Kucera T. G.
Published: May 2006

This is the first of two papers based on Chapter V of the author's Ph.D. thesis [K1]. The second paper [K3] will deal with a specific application of the ideas presented here to the study of modules, mostly to questions concerning the complexity of injective modules over a commutative Noetherian ring.

In [D], R. Deissler introduced a “minimality rank” which I denote by “rk” here. This rank provides an ordinal measure on the difficulty of defining a given element b in a structure ℳ, allowing the use of parameters from definable subsets of ℳ. If A ⊂ M, rk(b, A, ℳ) = 0 if b is definable in ℳ by a formula with parameters from A. Roughly speaking, in the general case rk(b, A, ℳ) measures how hard we have to work at adding new parameters to A (from sets definable over A in ℳ) in order to be able to define b. “rk” is called a “minimality rank” because of the following: ℳ is a minimal model of the complete theory T = Th(ℳ) iff rk(b, Ø, ℳ) < ∞ for every b ∈ M. Deissler's rank was studied further by R. Woodrow and J. Knight [WK]. They improve on an example given by Deissler. The construction that they present illustrates well the difficulties and subtleties involved in exact calculations of rk.

The central concept underlying Deissler's rank is that of a definable set. In §1 I introduce the idea of a context for definability Φ(x). A set B is Φ-definable over A if for some formula and . For Deissler's rank, Φ is the set of all formulas; for rk+ used in the study of modules, Φ+ is the set of all positive primitive formulas. Associated with each Φ is a relation ≺Φ between structures which says that Φ-definitions are preserved. In §1 I develop the basic properties of these two concepts and give a list of examples.
Positive deissler rank and the complexity of injective modules
Authors: Kucera T. G.
Published: May 2006

This is the second of two papers based on Chapter V of the author's Ph.D. thesis [K1]. For acknowledgements please refer to [K3]. In this paper I apply some of the ideas and techniques introduced in [K3] to the study of a very specific example. I obtain an upper bound for the positive Deissler rank of an injective module over a commutative Noetherian ring in terms of Krull dimension. The problem of finding lower bounds is vastly more difficult and is not addressed here, although I make a few comments and a conjecture at the end.

For notation, terminology and definitions, I refer the reader to [K3]. I also use material on ideals and injective modules from [N] and [Ma]. Deissler's rank was introduced in [D].

For the most part, in this paper all modules are unitary left modules over a commutative Noetherian ring Λ but in §1 I begin with a few useful results on totally transcendental modules and the relation between Deissler's rank rk and rk+.

Recall that if P is a prime ideal of Λ, then an ideal I of Λ is P-primary if I ⊂ P, λ ∈ P implies that λn ∈ I for some n and if λµ ∈ I, λ ∉ P, then µ ∈ I. The intersection of finitely many P-primary ideals is again P-primary, and any P-primary ideal can be written as the intersection of finitely many irreducible P-primary ideals since Λ is Noetherian. Every irreducible ideal is P-primary for some prime ideal P. In addition, it will be important to recall that if P and Q are prime ideals, I is P-primary, J is Q-primary, and J ⊃ I, then Q ⊃ P. (All of these results can be found in [N].)
Partitioning pairs of countable sets of ordinals
Authors: Velleman Dan
Published: May 2006

In [3], Todorčević showed that ω1 ⇸ [ω1]ω12. In this paper we use similar methods to prove an analogous partition theorem for Pω1(λ), for certain uncountable cardinals λ.

Recall that ω1 → [ω1]ω12, means that for every function f: [ω1]2 → ω1 there is a set A ∈ [ω1]ω1 such that f“[A]2 ≠ ω1, and of course ω1 ⇸ [ω1]ω12, is the negation of this statement. For partition relations on Pω1(→) it is customary to partition only those pairs of sets in which the first set is a subset of the second. Thus for A ⊆ Pω1(λ) we define

We will write Pω1(λ) → [unbdd]λ2 to mean that for every function f: [Pω1(λ)]⊂2 → λ there is an unbounded set A ⊆ Pω1(λ) such that f“[A]⊂2 ≠ λ, and again Pω1(λ) ⇸ [unbdd]λ2 is the negation of this statement.
An existence theorem for recursion categories
Authors: Heller Alex
Published: May 2006

Recursion theory has been dominated by one example. The notion of a dominical category was introduced (see [2] and [3]) at least in part in the hope of subverting this dominance. The structures of number theory, freed from this original context, led to much of modern algebra with a consequent enrichment of number theory itself: it seemed not unreasonable to attempt to contribute, however modestly, to a similar development of recursion theory. Thus (in the loosest sort of analogy) recursion categories are intended to stand in relation to the class of partial recursive functions as rings do to the rational integers.

But if such a generalization is to serve its intended purpose, it ought to allow examples substantially different in spirit from the prototype. Recursion categories are, of course, the proper generalization of classical recursion theory. As a novice in this formidable field I am incapable of encompassing its full extent and must rely on the advice of others (I thank in particular R. DiPaola) in concluding that most of these earlier generalizations are not of this character. Indeed, the examples of recursion categories so far adduced (cf., in addition to the references above, [1] and [4]) are themselves closely tied to the classical one.

We attempt here to open the door to radically disparate examples by proving an existence theorem allowing the construction of recursion categories in a wide, and so far unexplored, variety of contexts very distant from that of the natural or ordinal numbers and their subsets, the locus of the traditional theory.

In order to do this, it has been necessary to introduce a number of unfamiliar notions—unfamiliar, that is, even in the context of the earlier discussion of dominical categories. This novelty is perhaps mitigated by the fact that, however unfamiliar, they cannot be said to be unusual, as the discussion later will show. We mention in particular those of a “formally free semigroup”, which retains the indexation function of a free semigroup, while giving up the characteristic universal property and that of “uniform generation”, which generalizes finite generation in the fashion assorted to our argument.
Hilbert's program sixty years later
Authors: Sieg Wilfried
Published: May 2006

On June 4, 1925, Hilbert delivered an address to the Westphalian Mathematical Society in Miinster; that was, as a quick calculation will convince you, almost exactly sixty years ago. The address was published in 1926 under the title Über das Unendliche and is perhaps Hilbert's most comprehensive presentation of his ideas concerning the finitist justification of classical mathematics and the role his proof theory was to play in it. But what has become of the ambitious program for securing all of mathematics, once and for all? What of proof theory, the very subject Hilbert invented to carry out his program? The Hilbertian ambition reached out too far: in its original form, the program was refuted by Gödel's Incompleteness Theorems. And even allowing more than finitist means in metamathematics, the Hilbertian expectations for proof theory have not been realized: a constructive consistency proof for second-order arithmetic is still out of reach. (And since that theory provides a formal framework for analysis, it was considered by Hilbert and Bernays as decisive for proof theory.) Nevertheless, remarkable progress has been made. Two separate, but complementary directions of research have led to surprising insights: classical analysis can be formally developed in conservative extensions of elementary number theory; relative consistency proofs can be given by constructive means for impredicative parts of second order arithmetic. The mathematical and metamathematical developments have been accompanied by sustained philosophical reflections on the foundations of mathematics. This indicates briefly the main themes of the contributions to the symposium; in my introductory remarks I want to give a very schematic perspective, that is partly historical and partly systematic.
Where MA first fails
Authors: Kunen Kenneth
Published: May 2006

If θ is any singular cardinal of cofinality ω1, we produce a forcing extension in which MA holds below θ but fails at θ. The failure is due to a partial order which splits a gap of size θ in .
Des belles paires aux beaux uples
Authors: Bouscaren Elisabeth , Poizat Bruno
Published: May 2006

Une bijection p de M2 dans M est dite sans cycles, ou encore localement libre, si pour tout terme t(x1,…,xn) formé à partir de p, et qui n'est pas une simple variable, on a, pour tous a1,…,an de M, t(a1,… an) ≠ a1; toutes ces “fonctions-paires” sont élémentairement équivalentes, à condition, bien sûr, que l'ensemble M soit non vide, et leur théorie (parfois traduite dans un autre langage) a été considérée par divers auteurs.

Ainsi, A. Mal'cev [Mal'cev 1962] a décrit toutes les théories d'algèbre localement libres, associées à un langage fonctionnel arbitraire; O. Belegradek [Belegradek] a étudié dans le détail leurs propriétés de stabilité; F. Lucas [Lucas 1978] avait également considéré des fonctions-paires localement libres; c'est encore une fonction-paire qui a été utilisée par J. F. Pabion [Pabion 1982], pour ω1-saturer, mais pas davantage, les modèles de l'Arithmétique; il a été remarqué, dans [Poizat 1984], combien il était utile pour cela de disposer d'une théorie non superstable sans propriété de recouvrement fini; dans un tout autre contexte, et pour de tout autres raisons, cette théorie de fonctions-paires a également été utilisée dans [Poizat 1986]; tous ces emplois supposent qu'on y maîtrise bien l'élimination des quanteurs.
Decidable discrete linear orders
Authors: Moses M.
Published: May 2006

Three classes of decidable discrete linear orders with varying degrees of effectiveness are investigated. We consider how a classical order type may lie in relation to these three classes, and we characterize by their order types elements of these classes that have effective nontrivial self-embeddings.
Circumscription within monotonic inferences
Authors: López-Escobar E. G. K.
Published: May 2006

A conservative extension of first order logic, suitable for circumscriptive inference, is introduced.
Strongly 2-dimensional theories
Authors: Tsuboi Akito
Published: May 2006

In [8], we have shown the equivalence of almost strong minimality and strong unidimensionality. More precisely, we proved:

Theorem [8]. Let T be a countable stable theory. Then the following two conditions are equivalent:

(i) T is almost strongly minimal;

(ii) T can be extended to a theory such that any two nonalgebraic types are not almost orthogonal.

In the present paper, we define the notion of strong 2-dimensionality (of T). We show that if T is strongly 2-dimensional then T is ω-stable and its model has a simple structure. Roughly speaking, in a model of a strongly 2-dimensional theory, one of the following holds: (a) every element is in acl (δi is strongly minimal), or (b) every element is in acl (δ is strongly regular). Shelah's definition of 2-dimensionality does not imply even superstability. (See Exercise 5.5 in [6, Chapter V, §5].) We show also that condition (a) above implies strong 2-dimensionality of T. However condition (b) does not imply strong 2-dimensionality in general.

Our notations and conventions are standard. T is always countable and stable. We work in . A,B,… are used to denote small subsets of . , … are used to denote finite sequences of elements in . δ, φ,… are used to denote formulas (with parameters), p, q, … are used to denote types (with parameters). The fact that p is a nonforking (forking) extension of q is denoted by p ⊃nfq(p ⊃fq). If p is stationary, p∣A denotes the type in S(A) which is parallel to p. (or ) denotes the set of realizations of p (or δ). The Morley rank of p is denoted by RM(p).
Some properties of large filters
Authors: Freiling Chris , Payne T. H.
Published: May 2006

Dowker [1] raised the question of the existence of filters such that for every coloring (partition) of the underlying index set I with two colors there is a relation R on I which (i) is fat (in the sense that sets of the form {y Є I∣xRy} are in the filter) and (ii) has no bichromatic symmetric pairs (i.e., distinct indices x and y such that x R y and y R x). Additionally, he required that the filter have no anti-symmetric fat relation, for such a relation would vacuously satisfy (i) and (ii). The question of the existence of Dowker filters has been studied more recently by Rudin [3], [4], who conjectures [3] that such filters do not exist.

For ZFC the problem remains open. However, Example 2 of this paper shows that one can construct a Dowker filter provided one drops the axiom of choice in favor of the Baire Property (BP) axiom which is known to be incompatible with ZFC but relatively consistent with ZF. In fact, the filter constructed is super-Dowker in the sense that (ii) can be replaced by the requirement that all components of all symmetric pairs have the same color. But, in ZFC the existence of a super-Dowker filter implies the existence of a measurable cardinal.

Let F be a filter on an index set I. A set will be called big, small, or medium depending on whether F contains that set, its compliment, or neither, respectively. We define five cardinals associated with F:

α denotes the smallest cardinal such that there is a family of α big sets whose intersection is not big.

ν denotes the smallest cardinal such that there is a family of ν big sets whose intersection is small.
On parameter free induction schemas
Authors: Kaye R. , Paris J. , Dimitracopoulos C.
Published: May 2006

We present a comprehensive study of the axiom schemas (induction and collection schemas for parameter free Σn formulas) and some closely related schemas.
The false assumption underlying berry's paradox
Authors: French James D.
Published: May 2006

This paper is divided into three sections. §1 consists of an argument against the validity of Berry's paradox; §2 consists of supporting arguments for the thesis presented in §1; and §3 examines the possibility of re-establishing the paradox.

Berry's paradox, a semantic antinomy, is described on p. 4 of the textbook [4] as follows:

For the sake of argument, let us admit that all the words of the English language are listed in some standard dictionary. Let T be the set of all thenatural numbers that can be described in fewer than twenty words of the English language. Since there are only a finite number of English words, there are only finitely many combinations of fewer than twenty such words—that is, T is a finite set. Quite obviously, then, there are natural numbers which are greater than all the elements of T; hence there is a least natural number which cannot be described in fewer than twenty words of the English language. By definition, this number is not in T; yet we have described it in sixteen words, hence it is in T.

We are faced with a glaring contradiction; since the above argument would be unimpeachable if we admitted the existence of the set T, we are irrevocably led to the conclusion that a set such as T simply cannot exist.
The last word on elimination of quantifiers in modules
Authors: Gute Hans B. , Reuter K. K.
Published: May 2006

In what follows, a coset is a subset of a group G of the form aH, where H is a subgroup of G; H can be recovered from the coset C: it is the only subgroup which is obtained from C by a left translation; we note in passing that these cosets, that we write systematically with the group to the right, are also of the form Ka, since aH = aHa−1a. A classical combinatorial lemma involving cosets appears in Neumann [1952]: If the coset C = aH is the union of the finite family of cosets C1 = a1H1,…,Cn = anHn, then it is the union of those Ci whose corresponding Hi has finite index in H.

In a structure where a group G is defined, Boolean combinations of cosets modulo its definable subgroups form a family of definable sets (by definable, we mean “definable with parameters”). The situation when any definable set is of that kind has been characterized model-theoretically in Hrushovski and Pillay [1987]: A group G is one-based if and only if, for each n, every definable subset of the cartesian power Gn is a(finite!) Boolean combination of cosets modulo definable subgroups. One side is given by a beautiful lemma of Pillay, stating that, in a one-based group which is saturated enough, every type is a right translate of the generic of its left stabilizer.
An infinite superstable group has infinitely many conjugacy classes
Authors: Aguzarov I. , Farey R. E. , Goode J. B.
Published: May 2006

We begin with some notes concerning the genesis of this paper. A preliminary version of it was written by the third author, who was moved by the desire to correct a mistake in Poizat [1987, p. 97], and to refresh some other minor results of the same book, concerning equations which are satisfied generically in a stable group. The book in question will be considered here as our basic reference on stable groups, and these other results will be discussed elsewhere.

This preliminary version contained §§1, 2 and 3 of the present paper, restricted to the context of groups of finite Morley rank. It was observed that a counterexample of finite rank to the above theorem would be an extreme refutation of a conjecture by Zil'ber and Cherlin (cyrillic alphabet order), that may be not so solid as was believed some time ago, which states that a simple group of finite rank should be an algebraic group. Additional motivation for the problem was seen in Reineke's theorem (Reineke [1975]), stating that a connected group of rank one is abelian—the cornerstone for the study of superstable groups—whose proof rests on the fact that a group with two conjugacy classes either has only two elements, or has infinite chains of centralizers (a property that violates stability).
Some trivial considerations
Authors: Goode John B.
Published: May 2006

At the source of what is now known as “geometric stability theory” was Zil'ber's intuition that the essential properties of an aleph-one-categorical theory were controlled by the geometries of its minimal types. (However, the situation is much more complex than was assumed in Zil'ber [1984], since the main conjecture of that paper has been disproved by Hrushovski.) This is not unnatural in this unidimensional case, where all these geometries have isomorphic contractions, but it was even realized later, in Cherlin, Harrington and Lachlan [1985] and Buechler [1986], that, for any superstable theory with finite ranks, a certain “local” property, i.e. a property satisfied by the geometry of each type of rank one (namely: to have a projective contraction), was equivalent to a “global” one (the theory is one-based, hence satisfies a coordinatization lemma). Then it was shown, in Pillay [1986], that this situation does not generalize to the infinite rank case, that, even for a theory of rank omega, the (local) assumption of projectivity for all the regular types of the theory does not have an exact global counterpart.

To clarify this kind of phenomena, I suggest here the elimination of their geometrical aspect, considering only the case where all of the geometries are degenerate. I will study various notions of triviality, which make sense in a stable context, and turn out to be equivalent in the finite rank case; some of them have a definite global flavour, others are of local character.
A direct proof of the Feferman-Vaught theorem and other preservation theorems in products
Authors: Vourtsanis Yiannis
Published: May 2006

Here we give short and direct proofs of the Feferman-Vaught theorem and other preservation theorems in products of structures. In 1952, Mostowski [5] first showed the preservation of ≡ωω by direct powers of structures. Subsequently, in 1959, Feferman and Vaught [2] proved the preservation of ≡ωω by arbitrary direct products and also by reduced products with respect to cofinite filters. In 1962, Frayne, Morel and Scott [3] noticed that the results extend to arbitrary reduced products. In 1970, Barwise and Eklof [1] showed the preservation of ≡∞λ by products and in 1971 Malitz [4] showed the preservation of ≡κλ with κ strongly inaccessible (or ∞) by products. Below, we give short proofs of the above results. The ideas used here have initiated, in [7], [8], [9], [10], [11], the introduction of several new methods in the theory of products, which on the one hand give new, direct proofs of the known results in the area, including generalizations or strengthenings of some of those, and, on the other hand, give several new results as well in the theory of products and related areas.

Below, L denotes a (first order) language, and by a structure we mean an L-structure. 0 and 1 denote the logically valid and false sentence, respectively. We may write ā ∈ A for ā ∈ An for some n. Also, the values 1 and 2 of a parameter l in the definitions below express a duality corresponding to disjunctive and conjunctive forms.
Nonabsoluteness of elementary embeddings
Authors: Wehrung Friedrich
Published: May 2006

Ifκis a measurable cardinal, let us say that a measure onκis aκ-complete nonprincipal ultrafilter onκ. IfUis a measure onκ, letjUbe the canonical elementary embedding ofVinto its Ultrapower UltU(V). Ifxis a set, say thatUmovesxwhenjU(x)≠x; say thatκmovesxwhen some measure onκmovesx. Recall Kunen's lemma (see [K]): “Every ordinal is moved only by finitely many measurable cardinals.” Kunen's proof (see [K]) and Fleissner's proof (see [KM, III, §10]) are essentially nonconstructive.

The following proposition can be proved by using elementary facts about iterated ultrapowers.

Proposition.Let ‹Un: n ∈ ω› be a sequence of measures on a strictly increasing sequence ‹κn: n ∈ ω› of measurable cardinals. Let U = ‹ Wα: α < ω2›, where Wωm + n= Um(m, n ∈ ω). Then, for each θ inUltU(V),if E is the (minimal) support of θ inUltU(V),then, for all m ∈ ω, Ummoves θ iff E ∩ [ωm, ω(m + 1))≠ ∅.
On the ranked points of a Π10 set
Authors: Cenzer Douglas , Smith Rick L.
Published: May 2006

This paper continues joint work of the authors with P. Clote, R. Soare and S. Wainer (Annals of Pure and Applied Logic, vol. 31 (1986), pp. 145–163). An element x of the Cantor space 2ω is said have rank α in the closed set P if x is in Dα(P)/Dα + 1(P), where Dα is the iterated Cantor-Bendixson derivative. The rank of x is defined to be the least α such that x has rank a in some set. The main result of the five-author paper is that for any recursive ordinal λ + n (where λ is a limit and n is finite), there is a point with rank λ + n which is Turing equivalent to O(λ + 2n) All ranked points constructed in that paper are singletons. We now construct a ranked point which is not a singleton. In the previous paper the points of high rank were also of high hyperarithmetic degree. We now construct points with arbitrarily high rank. We also show that every nonrecursive RE point is Turing equivalent to an RE point of rank one and that every nonrecursive point is Turing equivalent to a hyperimmune point of rank one. We relate Clote's notion of the height of a singleton in the Baire space with the notion of rank. Finally, we show that every hyperimmune point x is Turing equivalent to a point which is not ranked.
The strong anticupping property for recursively enumerable degrees
Authors: Cooper S. B.
Published: May 2006

Following Soare [11] we say a recursively enumerable (r.e.) degree a has the anticupping (a.c.) property if there is a nonzero r.e. degree b < a such that for no r.e. c < a does a = b ∪ c.

Cooper [2] and Yates showed that 0′ has the a.c. property, while Harrington (see Miller [6]) proved that every high r.e. degree a has the a.c. property.

The recent paper by Ambos-Spies, Jockusch, Shore and Soare [1] describes a general theoretical framework for cupping and capping below 0′ which seems likely to be useful in a wider context.

Definition. (1) We say b is strongly noncuppable belowa if 0 < b < a and, for each d < a, b ∪ d ≠ a.

(2) We say an r.e. a has the strong anticupping property if there is an r.e. b which is strongly noncuppable below a.

The main results on cupping in (≤ 0′) are due to Epstein, Posner and Robinson. For instance it is known (Posner and Robinson [8]) that the s.a.c. property fails for 0′.

We prove below that r.e. degrees with the s.a.c. property do exist, hence obtaining a nonzero r.e. degree a such that (≤ a) ≢e(≤h) for any high r.e. degree h. This result, obtained by means of an infinite injury construction in (≤ 0′), extends Theorem 2 of [3], proved using a finite injury construction in (≤ 0′).

Our main source of notation and terminology is [3].
Minimal prime ideals and arithmetic comprehension
Authors: Hatzikiriakou Kostas
Published: May 2006

We assume that the reader is familiar with the program of “reverse mathematics” and the development of countable algebra in subsystems of second order arithmetic. The subsystems we are using in this paper are RCA0, WKL0 and ACA0. (The reader who wants to learn about them should study [1].) In [1] it was shown that the statement “Every countable commutative ring has a prime ideal” is equivalent to Weak Konig's Lemma over RCA0, while the statement “Every countable commutative ring has a maximal ideal” is equivalent to Arithmetic Comprehension over RCA0. Our main result in this paper is that the statement “Every countable commutative ring has a minimal prime ideal” is equivalent to Arithmetic Comprehension over RCA0. Minimal prime ideals play an important role in the study of countable commutative rings; see [2, pp. 1–7].
The elementary class of products of totally ordered abelian group
Authors: Gluschankof Daniel
Published: May 2006

A basic goal in model-theoretic algebra is to obtain the classification of the complete extensions of a given (first-order) algebraic theory.

Results of this type, for the theory of totally ordered abelian groups, were obtained first by A. Robinson and E. Zakon [5] in 1960, later extended by Yu. Gurevich [4] in 1964, and further clarified by P. Schmitt in [6].

Within this circle of ideas, we give in this paper an axiomatization of the first-order theory of the class of all direct products of totally ordered abelian groups, construed as lattice-ordered groups (l-groups)—see the theorem below. We think of this result as constituing a first step—undoubtedly only a small one—towards the more general goal of classifying the first-order theory of abelian l-groups.

We write groups for abelian l-groups construed as structures in the language 〈 ∨, ∧, +, −, 0〉 (“−” is an unary operation). For unproved statements and unexplicated definitions, the reader is referred to [1].
Principal type-schemes and condensed detachment
Authors: Hindley J. Roger , Meredith David
Published: May 2006

The condensed detachment rule, or ruleD, was first proposed by Carew Meredith in the 1950's for propositional logic based on implication. It is a combination of modus ponens with a “minimal” amount of substitution. We shall give a precise detailed statement of rule D. (Some attempts in the published literature to do this have been inaccurate.)

The D-completeness question for a given set of logical axioms is whether every formula deducible from the axioms by modus ponens and substitution can be deduced instead by rule D alone. Under the well-known formulae-as-types correspondence between propositional logic and combinator-based type-theory, rule D turns out to correspond exactly to an algorithm for computing principal type-schemes in combinatory logic. Using this fact, we shall show that D is complete for intuitionistic and classical implicational logic. We shall also show that D is incomplete for two weaker systems, BCK- and BCI-logic.

In describing the formulae-as-types correspondence it is common to say that combinators correspond to proofs in implicational logic. But if “proofs” means “proofs by the usual rules of modus ponens and substitution”, then this is not true. It only becomes true when we say “proofs by rule D”; we shall describe the precise correspondence in Corollary 6.7.1 below.

This paper is written for readers in propositional logic and in combinatory logic. Since workers in one field may not feel totally happy in the other, we include short introductions to both fields.

We wish to record thanks to Martin Bunder, Adrian Rezus and the referee for helpful comments and advice.
On the formalization of semantic conventions
Authors: Williams James G.
Published: May 2006

This paper discusses six formalization techniques, of varying strengths, for extending a formal system based on traditional mathematical logic. The purpose of these formalization techniques is to simulate the introduction of new syntactic constructs, along with associated semantics for them. We show that certain techniques (among the six) subsume others. To illustrate sharpness, we also consider a selection of constructs and show which techniques can and cannot be used to introduce them. The six studied techniques were selected on the basis of actual practice in logic and computing. They do not form an exhaustive list.