bluuebunny/crossref_metadata_2025 huggingface dataset:
Church's thesis without tears
Authors: Richman Fred
Published: May 2006

The modern theory of computability is based on the works of Church, Markov and Turing who, starting from quite different models of computation, arrived at the same class of computable functions. The purpose of this paper is the show how the main results of the Church-Markov-Turing theory of computable functions may quickly be derived and understood without recourse to the largely irrelevant theories of recursive functions, Markov algorithms, or Turing machines. We do this by ignoring the problem of what constitutes a computable function and concentrating on the central feature of the Church-Markov-Turing theory: that the set of computable partial functions can be effectively enumerated. In this manner we are led directly to the heart of the theory of computability without having to fuss about what a computable function is.

The spirit of this approach is similar to that of [RGRS]. A major difference is that we operate in the context of constructive mathematics in the sense of Bishop [BSH1], so all functions are computable by definition, and the phrase “you can find” implies “by a finite calculation.” In particular ifPis some property, then the statement “for eachmthere isnsuch thatP(m, n)” means that we can construct a (computable) functionθsuch thatP(m, θ(m))for allm. Church's thesis has a different flavor in an environment like this where the notion of a computable function is primitive.

One point of such a treatment of Church's thesis is to make available to Bishopstyle constructivists the Markovian counterexamples of Russian constructivism and recursive function theory. The lack of serious candidates for computable functions other than recursive functions makes it quite implausible that a Bishopstyle constructivist could refute Church's thesis, or any consequence of Church's thesis. Hence counterexamples such as Specker's bounded increasing sequence of rational numbers that is eventually bounded away from any given real number [SPEC] may be used, as Brouwerian counterexamples are, as evidence of the unprovability of certain assertions.
Cardinal collapsing and ordinal definability
Authors: Štěpánek Petr
Published: May 2006

We shall describe Boolean extensions of models of set theory with the axiom of choice in which cardinals are collapsed by mappings definable from parameters in the ground model. In particular, starting from the constructible universe, we get Boolean extensions in which constructible cardinals are collapsed by ordinal definable sets.

Let be a transitive model of set theory with the axiom of choice. Definability of sets in the generic extensions of is closely related to the automorphisms of the corresponding Boolean algebra. In particular, if G is an -generic ultrafilter on a rigid complete Boolean algebra C, then every set in [G] is definable from parameters in . Hence if B is a complete Boolean algebra containing a set of forcing conditions to collapse some cardinals in , it suffices to construct a rigid complete Boolean algebra C, in which B is completely embedded. If G is as above, then [G] satisfies “every set is -definable” and the inner model [G ∩ B] contains the collapsing mapping determined by B. To complete the result, it is necessary to give some conditions under which every cardinal from [G ∩ B] remains a cardinal in [G].

The absolutness is granted for every cardinal at least as large as the saturation of C. To keep the upper cardinals absolute, it often suffices to construct C with the same saturation as B. It was shown in [6] that this is always possible, namely, that every Boolean algebra can be completely embedded in a rigid complete Boolean algebra with the same saturation.
End extensions and numbers of countable models
Authors: Shelah Saharon
Published: May 2006

We prove that every model of T = Th(ω, <,…) (T countable) has an end extension; and that every countable theory with an infinite order and Skolem functions has nonisomorphic countable models; and that if every model of T has an end extension, then every ∣T∣-universal model of T has an end extension definable with parameters.
On the Gödel class with identity
Authors: Goldfarb Warren D.
Published: May 2006

The Gödel Class is the class of prenex formulas of pure quantification theory whose prefixes have the form ∀y1∀y2∃x1 … ∃xn. The Gödel Class with Identity, or GCI, is the corresponding class of formulas of quantification theory extended by inclusion of the identity-sign “ = ”. Although the Gödel Class has long been kndwn to be solvable, the decision problem for the Gödel Class with Identity is open. In this paper we prove that there is no primitive recursive decision procedure for the GCI, or, indeed, for the subclass of the GCI containing just those formulas with prefixes ∀y1∀y2∃x.

Throughout this paper we take quantification theory to include, aside from logical signs, infinitely many k-place predicate letters for each k > 0, but no function signs or constants. Moreover, by “prenex formula” we include only those without free variables. A decision procedure for a class of formulas is a recursive function that carries a formula in the class to 0 if the formula is satisfiable and to 1 if not. A class is solvable iff there exists a decision procedure for it. A class is finitely controllable iff every satisfiable formula in the class has a finite model. Since we speak only of effectively specified classes, finite controllability implies solvability (but not conversely).

The GCI has a curious history. Gödel showed the Gödel Class (without identity) solvable in 1932 [4] and finitely controllable in 1933 [5].
Rabin's uniformization problem
Authors: Gurevich Yuri , Shelah Saharon
Published: May 2006

The set of all words in the alphabet {l, r} forms the full binary tree T. If x ∈ T then xl and xr are the left and the right successors of x respectively. We consider the monadic second-order language of the full binary tree with the two successor relations. This language allows quantification over elements of rand over arbitrary subsets of T. We prove that there is no monadic second-order formula ϕ*(X, y) such that for every nonempty subset X of T there is a unique y ∈ X that satisfies ϕ*(X, y) in T.
Une théorie de Galois imaginaire
Authors: Poizat Bruno
Published: May 2006

La communauté mathématique doit être reconnaissante à Saharon Shelah pour une invention d'une ingénieuse simplicité, celle d'avoir associé à chaque structure M une structure Meq comprenant, outre les éléments de M, des “éléments imaginaires” qui sont virtuellement présents dans M. La finalité de cette construction est de pourvoir toute formule à paramètres dans M, et même dans Meq, d'un ensemble de définition minimum; tout cela est rappelé dans la première section du présent article.

On peut a priori douter de l'utilité d'une construction si innocente, dont la propriété fondamentale est pratiquement évidente; et pourtant elle a été abondamment montrée par son auteur, à qui elle a permis, dans les théorèmes de classification des modèles, une décomposition des types en éléments simples, qu'on ne voit pas dans M.

Cette construction d'un plus petit ensemble de définition pour une formule en rappelle une autre, qui est bien connue des algébristes, celle du corps de définition d'un idéal. Et comme la théorie des corps algébriquement clos de caractéristique donnée élimine les quanteurs, on a le sentiment que l'adjonction d'imaginaires aux modèles de cette théorie est inutile, en un mot qu'elle “élimine les imaginaires”; pour vérifier le bien-fondé de ce sentiment, il convient d'abord de préciser ce qu'on entend par là, ce qui est fait dans la deuxième section.
Algebraically closed commutative local rings
Authors: Podewski K.-P. , Reineke Joachim
Published: May 2006

A commutative ring R with identity is called a local ring if R has only one maximal ideal. This is equivalent to saying that the sum of two nonunits is a non-unit. Therefore the theory of all commutative local rings is axiomatizible by a finite set of A2-sentences. A commutative local ring with identity is said to be an algebraically closed local ring if every finite system of polynomial equations and inequations in one or more variables with coefficients in R which has a solution in some commutative local extension of R already has a solution in R. Much work connected with algebraically closed structures of classes of rings has been done, for example by Cherlin [2], Macintyre [4] and Lipschitz and Saracino [3]. We want to show similar results for commutative local rings with identity. Our main results are the following:

Theorem. The theory of commutative local rings with identity has no model-companion.

The finitely generic and infinitely generic local rings are algebraically closed local rings.

Theorem. There is an A3 sentence which holds for all finitely generic local rings whose negation holds in every infinitely generic local ring.
Recursion in a quantifier vs. elementary induction
Authors: Kolaitis Phokion G.
Published: May 2006

Spector [21] proved that a relation R on ω is Π11 if and only if it is (positive elementary) inductive on the structure 〈ω, +, ·〉; Kleene [8] showed that R is Π11 if and only if it is semirecursive in the type 2 object E. These two “constructive” characterizations of the Π11 relations have led to the independent study of (positive elementary) induction and recursion in E on an arbitrary structure, as natural generalizations of the theory of Π11 relations on (ω, +, · 〉.

The theory of (positive elementary) induction on an arbitrary structure was developed by Moschovakis in his book Elementary induction on abstract structures (EIAS); one of the most important theorems there is a generalization of the classical theorem of Spector [20] and Gandy [3] about the Π11 relations on ω: a relation R is inductive on an acceptable structure . if and only if there is a formula φ(Y, x) of the language of such that:

where HYP is the collection of hyperelementary relations on .

Moschovakis [17] and Kechris and Moschovakis [6] showed how to develop the theory of recursion in higher types as a chapter in the general theory of inductive definability. This approach to recursion in higher types makes it possible to use methods from the theory of inductive definability in studying recursion in E.

In this paper we establish some results about recursion in E on a structure which bolster the naturalness of this theory and contribute to its comparison with (positive elementary) induction.
Ramsey cardinals and constructibility
Authors: Mitchell William
Published: May 2006

Large cardinal properties divide rather strikingly into two groups. “Small” large cardinal properties such as weak compactness always relativize to L, while in contrast “large” large cardinal properties such as Ramsey are incompatible with L. These properties seem to be similar otherwise and this sense of similarity is reinforced by the fact that many of the large cardinals do exist in the L-like model L(μ). This paper will show that the division is caused by an artificially restrictive class of “constructible” sets rather than an essential difference in the properties themselves. Specifically, we consider the class K of sets constructible from mice as defined by Dodd and Jensen [3] and prove

Theorem 1. If ρ is Ramsey then ρ is Ramsey in K.

A modification of the proof will show

Theorem 2. If ρ is Jonson, then ρ is Ramsey in K.

Since Ramsey implies Jonson this shows that the notions are equiconsistent. Theorem 2 was proved by Kunen [5] under the assumption that V = L(μ).

The proof of Theorems 1 and 2 depends heavily on results of Dodd and Jensen [3] about K and mice. These results are stated without proof in §2. §2 also contains elementary (to a reader familiar with the theory of iterated ultrapowers) proofs of special cases of some of these lemmas sufficient to give a self contained proof of the following corollary of Theorem 1:

Corollary. If ρ ≤ κ,ρ is Ramsey and L(μ) ⊨ μ is a measure on κ then L(μ) ⊨ ρ is Ramsey.
Automorphisms of supermaximal subspaces
Authors: Downey R. G. , Hird G. R.
Published: May 2006

An infinite-dimensional vector space V∞ over a recursive field F is called fully effective if V∞ is a recursive set identified with ω upon which the operations of vector addition and scalar multiplication are recursive functions, identity is a recursive relation, and V∞ has a dependence algorithm, that is a uniformly effective procedure which when applied to x, a1,…,an, ∈ V∞ determines whether or not x is an element of {a1,…,an}* (the subspace generated by {a1,…,an}). The study of V∞, and of its lattice of r.e. subspaces L(V∞), was introduced in Metakides and Nerode [15]. Since then both V∞ and L(V∞) (and many other effective algebraic systems) have been studied quite intensively. The reader is directed to [5] and [17] for a good bibliography in this area, and to [15] for any unexplained notation and terminology.

In [15] Metakides and Nerode observed that a study of L(V∞) may in some ways be modelled upon a study of L(ω), the lattice of r.e. sets. For example, they showed how an e-state construction could be modified to produce an r.e. maximal subspace, where M ∈ L(V∞) is maximal if dim(V∞/M) = ∞ and, for all W ∈ L(V∞), if W ⊃ M then either dim(W/M) < ∞ or dim(V∞/W) < ∞.

However, some of the most interesting features of L(V∞) are those which do not have analogues in L(ω). Our concern here, which is probably one of the most striking characteristics of L(V∞), falls into this category. We say M ∈ L(V∞) is supermaximal if dim(V∞/M) = ∞ and for all W ∈ L(V∞), if W ⊃ M then dim(W/M) < ∞ or W = V∞. These subspaces were discovered by Kalantari and Retzlaff [13].
Bounded existential induction
Authors: Wilmers George
Published: May 2006

The present work may perhaps be seen as a point of convergence of two historically distinct sequences of results. One sequence of results started with the work of Tennenbaum [59] who showed that there could be no nonstandard recursive model of the system PA of first order Peano arithmetic. Shepherdson [65] on the other hand showed that the system of arithmetic with open induction was sufficiently weak to allow the construction of nonstandard recursive models. Between these two results there remained for many years a large gap occasioned by a general lack of interest in weak systems of arithmetic. However Dana Scott observed that the addition alone of a nonstandard model of PA could not be recursive, while more recently McAloon [82] improved these results by showing that even for the weaker system of arithmetic with only bounded induction, neither the addition nor the multiplication of a nonstandard model could be recursive.

Another sequence of results starts with the work of Lessan [78], and independently Jensen and Ehrenfeucht [76], who showed that the structures which may be obtained as the reducts to addition of countable nonstandard models of PA are exactly the countable recursively saturated models of Presburger arithmetic. More recently, Cegielski, McAloon and the author [81] showed that the above result holds true if PA is replaced by the much weaker system of bounded induction.

However in both the case of the Tennenbaum phenomenon and in that of the recursive saturation of addition the problem remained open as to how strong a system was really necessary to generate the required phenomenon. All that was clear a priori was that open induction was too weak to produce either result.
Tarski's problem for varieties of groups with a commutator identity
Authors: Lawrence John
Published: May 2006

It is proved that for a variety of groups in which the relatively free groups are solvable, the relatively free groups of distinct finite rank are not elementarily equivalent.
On minimal pairs of enumeration degrees
Authors: McEvoy Kevin , Cooper S. Barry
Published: May 2006

For sets of natural numbers A and B, A is enumeration reducible to B if there is some effective algorithm which when given any enumeration of B will produce an enumeration of A. Gutteridge [5] has shown that in the upper semilattice of the enumeration degrees there are no minimal degrees (see Cooper [3]), and in this paper we study those pairs of degrees with gib 0. Case [1] constructed a minimal pair. This minimal pair construction can be relativised to any gib, and following a suggestion of Jockusch we can also fix one of the degrees and still construct the pair. These methods yield an easier proof of Case's exact pair theorem for countable ideals. 0″ is an upper bound for the minimal pair constructed in §1, and in §2 we improve this bound to any Σ2-high Δ2 degree. In contrast to this we show that every low degree c bounds a degree a which is not in any minimal pair bounded by c. The structure of the co-r.e. e-degrees is isomorphic to that of the r.e. Turing degrees, and Gutteridge has constructed co-r.e. degrees which form a minimal pair in the e-degrees. In §3 we show that if a, b is any minimal pair of co-r.e. degrees such that a is low then a, b is a minimal pair in the e-degrees (and so Gutteridge's result follows). As a corollary of this we can embed any countable distributive lattice and the two nondistributive five-element lattices in the e-degrees below 0′. However the lowness assumption is necessary, as we also prove that there is a minimal pair of (high) r.e. degrees which is not a minimal pair in the e-degrees (under the isomorphism). In §4 we present more concise proofs of some unpublished work of Lagemann on bounding incomparable pairs and embedding partial orderings.

As usual, {Wi}i ∈ ω is the standard listing of the recursively enumerable sets, Du is the finite set with canonical index u and {‹ m, n ›}m, n ∈ ω is a recursive, one-to-one coding of the pairs of numbers onto the numbers. Capital italic letters will be variables over sets of natural numbers, and lower case boldface letters from the beginning of the alphabet will vary over degrees.
Between strong and superstrong
Authors: Baldwin Stewart
Published: May 2006

Definition. A cardinal κ is strong iff for every x there is an elementary embedding j:V → M with critical point κ such that x ∈ M.

κ is superstrong iff ∃j:V → M with critical point κ such that Vj(κ) ∈ M.

These definitions are natural weakenings of supercompactness and hugeness respectively and display some of the same relations. For example, if κ is superstrong then Vκ ⊨ “∃ proper class of strong cardinals”, but the smallest superstrong cardinal is less than the smallest strong cardinal (if both types exist). (See [SRK] and [Mo] for the arguments involving supercompact and huge, which translate routinely to strong and superstrong.)

Given any two types of large cardinals, a typical vague question which is often asked is “How large is the gap in consistency strength?” In one sense the gap might be considered relatively small, since the “higher degree” strong cardinals described below (a standard trick that is nearly always available) and the Shelah and Woodin hierarchies of cardinals (see [St] for a definition of these) seem to be (at least at this point in time) the only “natural” large cardinal properties lying between strong cardinals and superstrong cardinals in consistency strength.
Attention à la marche!
Authors: Poizat Bruno
Published: May 2006

Quoi qu'en pensent certains, la déviation de Saharon Shelah n'est pas qu'une construction technique servant à un résultat plus technique encore, le théorème de classification; c'est la notion de dépendance la plus générale qui soit apparue dans un contexte mathématique, si bien que toute propriété qu'on pourra attribuer à cette déviation sera, dans le fond, une propriété de la notion même de corrélation.

L'auteur de ces lignes a trouvé la vie beaucoup plus plaisante quand il a pu lire la déviation, associée à une théorie stable T, dans un ordre qu'il était facile de définir sur les types complets au-dessus des modèles de T; s'il a qualifié cet ordre de “fondamental”, ce n'est pas pour donner une emphase hors de propos à sa modeste contribution au démélage de l'échevau shelahien, mais parce que le rang U de Lascar n'était autre que le rang de fondation de l'ordre fondamental.

L'ordre fondamental condense l'essentiel de la déviation, sous une forme pour ainsi dire graphique; certes, tout ne peut s'y retrouver, et en particulier des théories peuvent avoir des ordres fondamentaux semblables si on se limite aux 1-types, et fort différents si on regarde aussi les bitypes; mais il est clair que dès qu'apparait l'ordre fondamental se pose de façon urgente le problème de décrire tous les ordres qui peuvent être ordre fondamental d'une théorie stable: tant que ce programme n'est pas rempli, il reste des propriétés cachées de la déviation.
Stability theory for topological logic, with applications to topological modules
Authors: Kucera T. G.
Published: May 2006

In this paper I show how to develop stability theory within the context of the topological logic first introduced by McKee [Mc 76], Garavaglia [G 78] and Ziegler [Z 76]. I then study some specific applications to topological modules; in particular I prove two quantifier élimination theorems, one a generalization of a result of Garavaglia.

In the first section I present a summary of basic results on topological model theory, mostly taken from the book of Flum and Ziegler [FZ 80]. This is done primarily to fix notation, but I also introduce the notion of anLt-elementary substructure. The important point with this concept, as with many others, appears to be to allow only individuals to appear as parameters, not open sets.

In the second section I begin the study of stability theory forLt. I first develop a translation of the topological languageLtinto an ordinary first-order languageL*. The first main theorem is (2.3), which shows that the translation is faithful to the model-theoretic content ofLt, and provides the necessary tools for studyingLttheories in the context of ordinary first-order logic. The translation allows me to considerindividual stability theoryforLt: the stability-theoretic study of those types ofLtin which only individual variables occur freely and in which only individuals occur as parameters. I originally developed this stability theory entirely withinLt; the fact that the theorems and their proofs were virtually identical to those in ordinary first order logic suggested the reduction fromLttoL*.
Inverse topological systems and compactness in abstract model theory
Authors: Mundici Daniele
Published: May 2006

Given an abstract logic , generated by a set of quantifiers Qi, one can construct for each type τ a topological space Sτ, exactly as one constructs the Stone space for τ in first-order logic. Letting T be an arbitrary directed set of types, the set is an inverse topological system whose bonding mappings are naturally determined by the reduct operation on structures. We relate the compactness of to the topological properties of ST. For example, if I is countable then is compact iff for every τ each clopen subset of Sτ is of finite type and Sτ, is homeomorphic to limST, where T is the set of finite subtypes of τ. We finally apply our results to concrete logics.
Toward useful type-free theories. I
Authors: Feferman Solomon
Published: May 2006

There is a distinction betweensemantical paradoxeson the one hand andlogicalormathematical paradoxeson the other, going back to Ramsey [1925]. Those falling under the first heading have to do with such notions astruth, assertion(orproposition), definition, etc., while those falling under the second have to do withmembership, class, relation, function(and derivative notions such ascardinalandordinal number), etc. There are a number of compelling reasons for maintaining this separation but, as we shall see, there are also many close parallels from the logical point of view.

The initial solutions to the paradoxes on each side—namely Russell's theory of types for mathematics and Tarski's hierarchy of language levels for semantics— were early recognized to be excessively restrictive. The first really workable solution to the mathematical paradoxes was provided by Zermelo's theory of sets, subsequently improved by Fraenkel. The informal argument that the paradoxes are blocked in ZF is that its axioms are true in thecumulative hierarchy of setswhere (i) unlike the theory of types, a set may have members of various (ordinal) levels, but (ii) as in the theory of types, the level of a set is greater than that of each of its members. Thus in ZF there is no set of all sets, nor any Russell set {x∣x∉x} (which would be universal since∀x(x∉x) holds in ZF). Nor is there a set of all ordinal numbers (and so the Burali-Forti paradox is blocked).
Effectively nowhere simple sets
Authors: Miller D. , Remmel J. B.
Published: May 2006

An r.e. set A is nowhere simple if for every r.e. set We such that We − A is infinite, there is an infinite r.e. set W such that W ⊆ We − A. The definition of nowhere simple sets is due to R. Shore in [4]. In [4], Shore studied various properties of nowhere simple sets and showed that they could be used to give an elegant and simple proof of the fact that every nontrivial class of r.e. sets C closed under recursive isomorphisms is an automorphism base for , the lattice of r.e. sets modulo finite sets, (that is, an automorphism α of is completely determined by its action on C; see Theorem 8 of [4]). Shore also defined the notion of effectively nowhere simple sets.

Definition. An r.e. set A is effectively nowhere simple if there is a recursive function f such that for every i, Wf(i) ⊆ Wi − A and Wf(i) is infinite iff Wi − A is infinite. f is called a witness function for A.

Other than to produce examples of effectively nowhere simple sets and nowhere simple sets that are not effectively nowhere simple, Shore did not concern himself with the properties of effectively nowhere simple sets since he felt that effectively nowhere simple sets were unlikely to be lattice invariant in either E, the lattice of r.e. sets, or in .
An extended joint consistency theorem for a family of free modal logics with equality
Authors: Gumb Raymond D.
Published: May 2006

In this paper, we establish an extended joint consistency theorem for an infinite family of free modal logics with equality. The extended joint consistency theorem incorporates the Craig and Lyndon interpolation lemmas and the Robinson joint consistency theorem. In part, the theorem states that two theories which are jointly unsatisfiable are separated by a sentence in the vocabulary common to both theories.

Our family of free modal logics includes the free versions of I, M, and S4 studied by Leblanc [5, Chapters 8 and 9], supplemented with equality as in [3]. In the relational semantics for these logics, there is no restriction on the accessibility relation in I, while in M(S4) the restriction is reflexivity (refiexivity and transitivity). We say that a restriction on the accessibility relation countenances backward-looping if it implies a sentence of the form ∀x1 …xn(x1Rx2 &…&xn ⊃ xkRxj) (1 ≤ j < k ≤ n ≥ 2), where the xi (1 ≤ i ≤ n) are distinct individual variables. Just as reflexivity and transitivity do not countenance backward-looping, neither do any of the restrictions in our family of free modal logics. (The above terminology is derived from the effect of such restrictions on Kripke tableaux constructions.) The Barcan formula, its converse, the Fitch formula, and the formula T ≠ T′ ⊃ □T ≠ T′ do not hold in our logics.
Epistemic arithmetic is a conservative extension of intuitionistic arithmetic
Authors: Goodman Nicolas D.
Published: May 2006

Questions about the constructive or effective character of particular arguments arise in several areas of classical mathematics, such as in the theory of recursive functions and in numerical analysis. Some philosophers have advocated Lewis's S4 as the proper logic in which to formalize such epistemic notions. (The fundamental work on this is Hintikka [4].) Recently there have been studies of mathematical theories formalized with S4 as the underlying logic so that these epistemic notions can be expressed. (See Shapiro [7], Myhill [5], and Goodman [2]. The motivation for this work is discussed in Goodman [3].) The present paper is a contribution to the study of the simplest of these theories, namely first-order arithmetic as formalized in S4. Following Shapiro, we call this theory epistemic arithmetic (EA). More specifically, we show that EA is a conservative extension of Hey ting's arithmetic HA (ordinary first-order intuitionistic arithmetic). The question of whether EA is conservative over HA was raised but left open in Shapiro [7].

The idea of our proof is as follows. We interpret EA in an infinitary propositional S4, pretty much as Tait, for example, interprets classical arithmetic in his infinitary classical propositional calculus in [8]. We then prove a cut-elimination theorem for this infinitary propositional S4. A suitable version of the cut-elimination theorem can be formalized in HA. For cut-free infinitary proofs, there is a reflection principle provable in HA. That is, we can prove in HA that if there is a cut-free proof of the interpretation of a sentence ϕ then ϕ is true. Combining these results shows that if the interpretation of ϕ is provable in EA, then ϕ is provable in HA.
Existentially closed torsion-free nilpotent groups of class three
Authors: Maier Berthold J.
Published: May 2006

We denote by and the classes of torsion-free nilpotent groups of nilpotency class at most two and three, respectively. In this paper we show that most of the known results about existentially closed (e.c.) groups in remain true in : Up to isomorphism, there exist only countably many countable e.c. groups and they are distinguished by the ranks of their centers. An e.c. group is finitely (infinitely) generic if and only if the center has dimension one (≥ω). Apart from trivial exceptions, e.c, algebraically closed, and “closed with respect to systems of equations in one unknown” are equivalent.

Let K be a class of groups. A group G ϵ K is called existentially closed in K if G contains a solution of any finite system Σ of equations and inequations with constants in G and one or more unknowns, provided that Σ has a solution in some in K. If Σ may contain equations (in at most n unknowns) only, G is called algebraically closed (n-unknown closed [1]). We use the abbreviations e.c, a.c and n-u.c. throughout. For more background on these terms the reader is referred to [3] and [4]. We also assume a basic knowledge of generic structures. The main group theoretic notions needed here are explained in §2; [2] and [11] are the general references for this field.
On choice sequences determined by spreads
Authors: van der Hoeven Gerrit , Moerdijk Ieke
Published: May 2006

From the moment choice sequences appear in Brouwer's writings, they do so as elements of a spread. This led Kreisel to take the so-called axiom of spreaddata as the basic axiom in a formal theory of choice sequences (Kreisel [1965, pp. 133–136]). This axiom expresses the idea that to be given a choice sequence means to be given a spread to which the choice sequence belongs. Subsequently, however, it was discovered that there is a formal clash between this axiom and closure of the domain of choice sequences under arbitrary (lawlike) continuous operations (Troelstra [1968]). For this reason, the formal system CS was introduced (Kreisel and Troelstra [1970]), in which spreaddata is replaced by analytic data. In this system CS, the domain of choice sequences is closed under all continuous operations, and therefore it provides a workable basis for intuitionistic analysis. But the problem whether the axiom of spreaddata is compatible with closure of the domain of choice sequences under the continuous operations from a restricted class, which is still rich enough to validate the typical axioms of continuous choice, remained open. It is precisely this problem that we aim to discuss in this paper.

Recall that a spread is a (lawlike, inhabited) decidable subtree S of the tree N< N of all finite sequences, having all branches infinite:
Some remarks on initial segments in models of Peano arithmetic
Authors: Kotlarski Henryk
Published: May 2006

If M ⊨ PA (= Peano Arithmetic), we set AM = {N ⊂eM: N ⊨ PA} and study this family.
Relevant entailment—semantics and formal systems
Authors: Avron Arnon
Published: May 2006

This work results from an attempt to give the vague notion of relevance a concrete semantical interpretation. The idea is that propositions may be divided into different “domains of relevance”. Each “domain” has its own “T” and “F” values, and propositions “belonging” to one domain can never entail propositions “belonging” to another, unconnected one.

The semantics we have developed were found to correspond to an already known system, which we call here RMI⥲. Its axioms are the implication-negation axioms of the system RM ([1, Chapter 5]). However, as Meyer has shown, RM is not a conservative extension of RMI⥲, since RMI⥲ has the sharing-of-variables property ([5], and [1, pp. 148–149[), which the implication-negation fragment of RM has not.

RMI⥲ has four advantages in comparison to its more famous sister R⥲ (the pure intentional fragment of the system R; see [1]):

a) It has a very natural (from a relevance point of view) many-valued semantics, the simple form of which we describe here.

b) RMI⥲, ⊢ A1 → [A2 → (… → (An → A) …)] iff there is a proof of A from the set {A1, …, An} that actually uses all the members of this set. In R⥲, this holds only if we talk about “sequences” instead of “sets”. This is somewhat less intuitive (see [1, pp. 394–395]).

c) RMI⥲ is a maximal “natural” relevance logic, in the sense that every proper extension of it limits the number of “domains of relevance” (§III).
Espaces ultramétriques
Authors: Delon Françoise
Published: May 2006

Un espace ultramétrique est un ensemble muni d'une distance à valeurs dans un ordre total avec premier élément et pour laquelle tout triangle est isocèle avex deux grands côtés égaux. Les deux cas importants d'espaces ultramétriques sont:

(1) les corps valués lorsqu'on ne considère que leur structure métrique, et

(2) les ensembles Aλ, où λ est un ensemble bien ordonné, munis de la distance d(α, β) = inf {γ ∈ λ; α(γ) ≠ β(γ)} si α ≠ β et d(α, β) = 0 sinon; distance à valeurs dans l'ordre inverse de λ enrichi d'un premier élément 0.

Nous étudions ces structures dans un langage comportant un seul type de variables, les points de l'espace, et un prédicat à quatre places traduisant l'ordre sur les distances

Nous définissons la notion d'espace riche, qui est la modèle-complétion relative à un ensemble des distances fixé: un espace est riche si et seulement s'il est existentiellement clos dans toute extension qui n'ajoute pas de nouvelle distance. Les deux exemples précédemment donnés, espaces Aλ et corps valués, fournissent des espaces riches. La suite de l'article s'attache à la description des espaces riches.
Co-immune subspaces and complementation inV∞
Authors: Downey R.
Published: May 2006

We examine the multiplicity of complementation amongst subspaces ofV∞. A subspaceVis acomplementof a subspaceWifV∩W= {0} and (V∪W)* =V∞. A subspace is calledfully co-r.e.if it is generated by a co-r.e. subset of a recursive basis ofV∞. We observe that every r.e. subspace has a fully co-r.e. complement.

Theorem.If S is any fully co-r.e. subspace then S has a decidable complement.

We give an analysis of other types of complementsSmay have. For example, ifSis fully co-r.e. and nonrecursive, thenShas a (nonrecursive) r.e. nowhere simple complement.

We impose the condition of immunity upon our subspaces.

Theorem.SupposeVis fully co-r.e. ThenVis immune iff there exist M1,M2∈L(V∞),with M1supermaximal and M2k-thin, such that M1, ⊕V=M2⊕V=V∞.

Corollary.SupposeVis any r.e. subspace with a fully co-r.e. immune complement W(e.g.,Vis maximal orVis h-immune). Then there exist an r.e. supermaximal subspace M and a decidable subspace D such thatV⊕W=M⊕W=D⊕W=V∞.

We indicate how one may obtain many further results of this type. Finally we examine a generalization of the concepts of immunity and soundness. A subspaceVofV∞isnowhere soundif (i) for allQ ∈ L(V∞)ifQ⊃VthenQ =V∞, (ii)Vis immune and (iii) every complement ofVis immune. We analyse the existence (and ramifications of the existence) of nowhere sound spaces.
Weak strong partition cardinals
Authors: Henle J. M.
Published: May 2006

In a series of papers [K2], [K3], [K4], E. M. Kleinberg established the extensive properties of what are now called “strong partition cardinals”, cardinals satisfying for all λ < κ. The purpose of this note is to show that all these consequences and the results in [H] and [W] can be obtained from the weaker relation and many from .

We assume the reader is generally familiar with Kleinberg's machinery and with the definition of . We recall that a cardinal κ satisfies iff for every partition F: [κ]κ → A there is a p ∈ [κ]κ such that F″ [p]κ ≠ A. We take the liberty of regarding a p ∈ [κ]κ both as a subset of κ and as a function from κ to κ. We assume DC throughout.

§1. From. Our results stem from the observation that the proofs in the papers cited above only require homogeneous sets for certain classes of partitions.

Definition. A partition F: [κ]κ → λ, λ < λ, is called clopen if for all p ∈ [κ]κ there is an α < κ such that whenever -clopen is the assertion that all clopen partitions have homogeneous sets (Spector-Watro).
Infinite subscripts from infinite exponents
Authors: Baumgartner James E. , Henle James M.
Published: May 2006

Definition. For ordinals α ≤ κ, = [X]α = {p ⊆ X ∣ ot (p) = α}. For α ≤, κ, κ a cardinal, holds iff for every partition F: [Κ]κ → A, there is an X ∈ [Κ]κ with F constant on [X]α. X is called homogeneous for F. When A = 2 the subscript is omitted.

It has been known since the sixties that for finite exponents all such properties are equivalent, i.e., κ→ (κ)2 iff for all n < ω, β < κ. The infinite case is much more difficult, though it is not actually known to be different. The usual methods for dealing with partitions fail, and as the weakest of these properties violates the Axiom of Choice, many techniques are unavailable.

It is extremely unlikely that an infinite exponent can be increased, but infinite subscripts are generally possible.

Theorem. If ∥ α ∥ · 2 ≤ α, then κ → (κ)α implies for all λ < κ.

In §1, we show the subscript can be any λ < κ. In §2 we extend this to 2λ. In §3 we discuss the possibilities with limited amounts of well-ordered choice, and apply the theorem to the problem of obliging ordinals. Except in §3, we assume no choice. For the story of finite exponents, see [1]. For the relationship between infinite-exponent partition relations and choice, see [4].
Definable structures in the lattice of recursively enumerable sets
Authors: Herrmann E.
Published: May 2006

It will be shown that in the lattice of recursively enumerable sets one can define elementarily with parameters a structure isomorphic to (), i.e. isomorphic to the lattice of sets together with a unary predicate selecting out exactly the sets.
Finitely generic models of TUH, for certain model companionable theories T
Authors: Point Francoise
Published: May 2006

The starting point of this work was Saracino and Wood's description of the finitely generic abelian ordered groups [S-W].

We generalize the result of Saracino and Wood to a class ∑UH of subdirect products of substructures of elements of a class ∑, which has some relationships with the discriminator variety V(∑t) generated by ∑. More precisely, let ∑ be an elementary class of L-algebras with theory T. Burris and Werner have shown that if ∑ has a model companion then the existentially closed models in the discriminator variety V(∑t) form an elementary class which they have axiomatized. In general it is not the case that the existentially closed elements of ∑UH form an elementary class. For instance, take for ∑ the class ∑0 of linearly ordered abelian groups (see [G-P]).

We determine the finitely generic elements of ∑UH via the three following conditions on T:

(1) There is an open L-formula which says in any element of ∑UH that the complement of equalizers do not overlap.

(2) There is an existentially closed element of ∑UH which is an L-reduct of an element of V(∑t) and whose L-extensions respect the relationships between the complements of the equalizers.

(3) For any models A, B of T, there exists a model C of TUH such that A and B embed in C.

(Condition (3) is weaker then “T has the joint embedding property”. It is satisfied for example if every model of T has a one-element substructure. Condition (3) implies that ∑UH has the joint embedding property and therefore that the class of finitely generic elements of ∑UH is complete.)
Strongly majorizable functionals of finite type: A model for barrecursion containing discontinuous functionals
Authors: Bezem Marc
Published: May 2006

In this paper a model for barrecursion is presented. It has as a novelty that it contains discontinuous functionals. The model is based on a concept called strong majorizability. This concept is a modification of Howard's majorizability notion; see [T, p. 456].
Syntactic translations and provably recursive functions
Authors: Leivant Daniel
Published: May 2006

Syntactic translations of classical logic C into intuitionistic logic I are well known (see [Kol25], [Gli29], [Göd32], [Kre58b], [M063], [Cel69] and [Lei71]). Harvey Friedman [Fri78] used a translation of a similar nature, from I into itself, to reprove a theorem of Kreisel [Kre58a] that various theories based on I are closed under Markov's rule: if ¬¬∃x.α is a theorem, where x is a numeric variable and α is a primitive recursive relation, then ∃x.α is a theorem. Composing this with Gödel's translation from classical to intuitionistic theories, it follows that the functions provably recursive in the classical version of the theories considered are provably recursive already in their intuitionistic version. This conservation result is important in that it guarantees that no information about the convergence of recursive functions is lost when proofs are restricted to constructive logic, thus removing a potential objection to the use of constructive logic in reasoning about programs (see [C078] for example). Conversely, no objection can be raised by intuitionists to proofs of formulas that use classical reasoning, because such proofs can be converted to constructive proofs (this has been exploited extensively; see [Smo82]).

Proofs of closure under Markov's rule had required, until Friedman's proof, a relatively sophisticated mathematical apparatus. The chief method used Godel's “Dialectica” interpretation (see [Tro73, §3]). Other proofs used cut-elimination, provable reflection for subsystems [Gir73], and Kripke models [Smo73]. Moreover, adapting these proofs to new theories had required that the underlying meta-mathematical techniques be adapted first, not always a trivial step.
On the consistency of self-referential systems
Authors: Sobrinho J. Zimbarg
Published: May 2006

In [2], Hiller and myself have introduced what we have called self-referential systems. Under this name we categorize models of a theory whose predicates refer to objects which are themselves predicates of the language—this particular interpretation being considered as the intended one.

is formulated in a language whose variables are typed: as types become “larger”, the corresponding objects become “smaller”; for this reason, we have suggestively chosen types to be negative integers: 0, −1, −2, and so on.

The consistency of has been questioned several times, and it has also been referred to as an “intriguing possibility”. Under such motivation, we are most willing to present a consistency proof for , and we do it relative to the theory ZFC + “there exists a Ramsey cardinal”. The only use of the Ramsey cardinal is to justify the existence of 0#, and the existence of 0# is known to be weaker than the existence of a Ramsey cardinal. For this reason, we note that the minimum we need for our proof is the existence of the set 0#.

To begin with, we prove that the consistency of implies the existence of intended models for : these are models in which every element is definable by a one-free-variable formula of the language. In intended models we also show that the axiom holds, and, besides, these models possess -indescribable cardinals. These two results imply the relative consistency of with respect to and, moreover, that any proof of the consistency of cannot be carried out without the use of some large cardinal axiom: such an axiom which, when added to ZFC, produces a theory equiconsistent to —if it exists—remains unknown. At the end of this article we finally exhibit the consistency proof of , our main result.
Seminormal λ-generated ideals on Pκλ
Authors: Johnson C. A.
Published: May 2006

In this paper we consider the problem of lifting properties of the Fréchet ideal Iκ = {X ⊆ κ: ∣X∣ < κ} on a regular uncountable cardinal κ, to an analogue about Iκλ, the ideal of not unbounded subsets of Pκλ. With this in mind, in §1 we introduce and study the class of seminormal λ-generated ideals on Pκλ. We shall see that ideals belonging to this class display properties which are clearly analogous to those of the Fréchet ideal on κ (for instance, with regard to saturation, normality and weak selectivity) and yet are closely related to Iκλ. Our results here show that if λ<λ = λ, then many restrictions of Iκλ are weakly selective, nowhere precipitous and, quite suprisingly, seminormal (but nowhere normal). These latter two results suggest the question of whether any restriction of Iκλ can ever be normal. In §2 we prove that if κ is strongly inaccessible, λ<κ = 2λ and NSκλ, the ideal of nonstationary subsets of Pκλ, has a mild selective property, then NSκλ∣A = Iκλ∣A for some stationary A ⊆ Pκλ.

In [1] Baumgartner showed that if κ is weakly compact and P is the collection of indescribable subsets of κ, then P → (P, κ)2. As a Pκλ analogue of indescribability, Carr (see [3]–[5]) introduced the λ-Shelah property, but was unable to derive the natural Pκλ analogue of Baumgartner's result, (where NShκλ is the normal ideal on Pκλ induced by the λ-Shelah property). In §3 we show that the problem lies in the fact that, as far as we know, NShκλ is not sufficiently distributive, and derive conditions which are sufficient and, in a sense, necessary to yield partitions related to .
Weakly minimal groups of unbounded exponent
Authors: Loveys James
Published: May 2006

Weakly minimal sets were first invented by Shelah [S] to solve Łoś' conjecture for uncountable theories. The first major result about them, which is that any nonalgebraic strong type either is of Morley rank 1 or has locally modular geometry, was proved by Buechler [B1]. Recently, Hrushovski [Hr] showed that a locally modular weakly minimal set interprets an abelian group, a result which revolutionized the study of these sets. Also Hrushovski showed that the geometry on the connected component of a weakly minimal locally modular group is that of a vector space over a division ring. This is also implicit in the result of Pillay and Hrushovski (Theorem 1.3 from [HP]) quoted below. In a sense, this completes their study, as any vector space over any division ring is in fact strongly minimal if there is no other structure. But the question remains as to what other structure such a group could have. This is the issue we address here.

Some work has been done on this question; in fact, Pillay ([Pi], generalized in [HP]) has demonstrated, in the more general context of a weakly normal group A, that any definable subset of An is in fact a Boolean combination of almost 0-definable cosets of almost 0-definable subgroups. In the weakly minimal case this can be sharpened a fair bit. The case of a weakly minimal group of bounded exponent is dealt with in [HL]. Here we consider the case where the group has unbounded exponent.
Decidability problem for finite Heyting algebras
Authors: Idziak Katarzyna , Idziak Pawel M.
Published: May 2006

The aim of this paper is to characterize varieties of Heyting algebras with decidable theory of their finite members. Actually we prove that such varieties are exactly the varieties generated by linearly ordered algebras. It contrasts to the result of Burris [2] saying that in the case of whole varieties, only trivial variety and the variety of Boolean algebras have decidable first order theories.