bluuebunny/crossref_metadata_2025_split huggingface dataset:
Closure properties of almost-finiteness classes in recursive function theory
Authors: Rolletschek Heinrich 
Published: May 2006

In this paper we will investigate closure properties of the class of immune sets and of other, more restricted classes of sets of natural numbers under union and similar operations. Our main theorem states that there exists a hyperhyperimmune set A such that A join A is not hyperhyperimmune. We will prove this result in §3. The remaining questions about closure properties are all much easier and will be answered in §2.We consider the closure properties which are given in the followingDefinition. Let bea. class of subsets of N.(i) is closed under join, if A join B ∈ whenever A ∈ and B ∈ .(ii) is closed under self-join, if A join A ∈ whenever A ∈ .(iii) is closed under union, if A ⋃ B ∈ whenever A ∈ and B ∈ .(iv) is closed under cartesian product, if A × B ∈ whenever A ∈ and B ∈ .(v) is closed under cartesian self-product, if A × A ∈ whenever A ∈ .The almost-finiteness classes we consider are the following:1 = {X∣X is immune};2 = {X∣ simple};3 = {X∣X is hyperimmune};4 = {X∣ is hypersimple};5 = {X∣X is strongly hyperimmune};6 = {X∣ is strongly hypersimple};7 = {X∣X is hyperhyperimmune};8 = {X∣X is strongly hyperhyperimmune};9 = {X∣ is hyperhypersimple};10 = {X∣X is dense immune};11 = {X∣ is dense simple}.The definitions are all contained in Rogers [4, Chapter 12] and/or in Robinson [3]. In addition we could consider the class of -strongly hyperimmune sets and classes defined by lim-properties; see Rogers [4, pp. 243–244]. For other classes, however, such as the class of cohesive sets, the questions become trivial.Our aim is to establish the table on the next page.
A model of peano arithmetic with no elementary end extension
Authors: Mills George 
Published: May 2006

AbstractWe construct a model of Peano arithmetic in an uncountable language which has no elementary end extension. This answers a question of Gaifman and contrasts with the well-known theorem of MacDowell and Specker which states that every model of Peano arithmetic in a countable language has an elementary end extension. The construction employs forcing in a nonstandard model.
Groupes stables, avec types génériques réguliers
Authors: Poizat Bruno 
Published: May 2006

Cet article ne contient rien de révolutionnaire, et son auteur a conscience du risque qu'il court de le voir dépassé, lors de sa parution, par des travaux plus profonds. Il a pensé qu'il n'était pas inutile de publier, faute de mieux, les résultats simples auxquels il est parvenu (le lecteur lui saura gré de ce caractère reposant), en espérant qu'il passeront à la postérité sous forme d'exercices dans les manuels futurs où les petits enfants apprendront la théorie des modèles.Il s'agit de groupes stables; on sait depuis longtemps que la stabilité de la théorie d'un groupe impose des “conditions de chaîne” sur ses sous-groupes définissables : l'exploitation de ce phénomène, de nature bien algébrique, qui est brièvement exposé dans la première section de cet article, a fait le bonheur d'une génération de théoriciens des modèles. Un autre phénomène, plus subtil, semble ne pas avoir épuisé sa substance : c'est celui, dont l'apparition remonte aux travaux de B. Zilber, qui est décrit dans [7] sous le nom de “types de strate maximum”, et dans [2] sous le nom de “large sets”; la deuxième section lui est consacrée: elle a été écrite dans le désir de montrer l'équivalence de ces deux approches, et aussi par repentir de n'avoir pas suffisament éclairé ses motivations dans [7]. Ce souci d'unification a eu une influence, que j'espère salutaire, sur le vocabulaire: je parle ici de “types génériques” et d'“ensembles (ou de formules) génériques”. Ces termes, ainsi que celui de “composante connexe”, sont empruntés au langage de la géométrie: un groupe algébrique, étant définissable dans la théorie d'un corps algébriquement clos, est stable, et ses “types génériques” sont les “points génériques” des géomètres.
Countable models of multidimensional ℵ0-stable theories
Authors: Bouscaren Elisabeth 
Published: May 2006

The notations and the definitions used here are identical to those in [B.L.]. We also assume that the reader is familiar with the properties of the Rudin-Keisler order on types [L.].Let T denote an ℵ0-stable countable theory. The main result in [B.L.] is: All countable models of T are almost homogeneous if and only if T satisfies(*) For all models M of T and all ā ∈ M, if p ∈ S1(ā) is strongly regular multidimensional, then Dim(p; M) ≥ ℵ0.In this paper we investigate the case of a theory T which does not satisfy condition (*) and, under certain additional assumptions, we construct nonisomorphic and non-almost-homogeneous countable models. The same type of construction has been used before to show that if T is multidimensional, then for all α ≥ 1, T has at least nonisomorphic models of cardinality ℵα [La.], [Sh.]. As a corollary of our main theorem (Theorem 6) and of the previous result in [B.L.], we prove Vaught's Conjecture (and, in fact, Martin's Strong Conjecture) for theories T with αT finite.Although we are here interested in countable models, we can also note that our construction proves that theories satisfying the assumptions in Theorem 6 have at least nonisomorphic models of cardinality ℵα.
Model companions of distributive p-algebras
Authors: Schmid Jürg 
Published: May 2006

Let Bn, 0 ≤ n ≤ ω, be the equational classes of distributive p-algebras (precise definitions are given in §1). It has been known for some time that the elementary theories Tn of Bn possess model companions ; see, e.g., [6] and [14] and the references given there. However, no axiomatizations of were given, with the exception of n = 0 (Boolean case) and n= 1 (Stonian case). While the first case belongs to the folklore of the subject (see [6], also [11]), the second case presented considerable difficulties (see Schmitt [13]). Schmitt's use of methods characteristic for Stone algebras seems to prevent a ready adaptation of his results to the cases n ≥ 2.The natural way to get a hold on is to determine the class E(Bn) of existentially complete members of Bn: Since exists, it equals the elementary theory of E(Bn). The present author succeeded [12] in solving the simpler problem of determining the classes A(Bn) of algebraically closed algebras in Bn (exact definitions of A(Bn) and E(Bn) are given in §1) for all 0 > n < ω. A(Bn) is easier to handle since it contains sufficiently many “small” algebras-viz. finite direct products of certain subdirectly irreducibles-in terms of which the members of A(Bn) may be analyzed (in contrast, all members of E(Bn) are infinite and ℵ-homogeneous). As it turns out, A(Bn) is finitely axiomatizable for all n, and comparing the theories of A(B0), A(B1) with the explicitly known theories of E(B0), E(B1)-viz. , , a reasonable conjecture for , 2 ≤ n ≤ ω, is immediate. The main part of this paper is concerned with verifying that the conditions formalized by suffice to describe the algebras in E(Bn) (necessity is easy). This verification rests on the same combinatorial techniques as used in [12] to describe the members of A(Bn).
Measurability and degrees of strong compactness
Authors: Apter Arthur W. 
Published: May 2006

AbstractWe prove, relative to suitable hypotheses, that it is consistent for there to be unboundedly many measurable cardinals each of which possesses a large degree of strong compactness, and that it is consistent to assume that the least measurable is partially strongly compact and that the second measurable is strongly compact. These results partially answer questions of Magidor on the relationship of strong compactness to measurability.
Complexity bounds on proofs
Authors: Hatcher William S. , Hodgson Bernard R. 
Published: May 2006

In a recent article in this Journal (see [3]), J.P. Jones states and proves a theorem which purports to give an “absolute epistemological upper bound on the complexity of mathematical proofs” for recursively axiomatizable theories. However, Jones' statement of this result is misleading, and in fact defective, as can be seen by a close analysis of it. Such an analysis is the object of the present note.The main point is that Jones' “epistemological bound” can in no way be considered a computational bound on the complexity of proofs. Not only is the “proof-theoretic interpretation of the number 243” contained in Jones' article objectionable but, more fundamentally, there is in a strong sense no way one can hope to recover anything like the full force suggested by Jones' original statement of the theorem.We wish to insist that our comments concern only the difficulties surrounding Jones' Corollary 1 on p. 338 of his article and not his ingenious construction of universal Diophantine representations of r.e. sets presented in the same article.
The noncommutativity of random and generic extensions
Authors: Truss J.K. 
Published: May 2006

Throughout, M will denote a transitive model of ZFC. Using the terms “random” and “generic” in the sense of [1], one may ask whether there can exist real numbers x and y such that x is generic over M[y] and y is random over M[x]. We shall see below by an elementary argument that this is not possible, and so, in a crude sense at least, random and generic extensions do not commute. This does not however rule out the possibility of a weaker commutativity. Let B be the complete Boolean algebra (in M) for adjoining a random real followed by a generic real and C be the complete Boolean algebra for adjoining a generic real followed by a random real. Then it still might be the case that B and C are isomorphic. This also fails, though, and we shall prove this by establishing the following combinatorial properties of MB and MC:butIn addition this will show that C cannot be embedded as a complete subalgebra of B.The property satisfied by B is reminiscent of calibre ℵ1 [2]. B would have calibre if we could replace “infinite” by “uncountable”, and this occurs if Martin's Axiom holds in M. To obtain the nonisomorphism of B and C in general necessitated looking at the weaker property.
LA(Ⅎ)
Authors: Bruce Kim , Keisler H. J. 
Published: May 2006

AbstractThe language LA(Ⅎ) is formed by adding the quantifier Ⅎx, “few x”, to the infinitary logic LA on an admissible set A. A complete axiomatization is obtained for models whose universe is the set of ordinals of A and where Ⅎx is interpreted as there exist A-finitely many x. For well-behaved A, every consistent sentence has a model with an A-recursive diagram. A principal tool is forcing for LA(Ⅎ).
Recursive isomorphism types of recursive Boolean algebras
Authors: Remmel J. B. 
Published: May 2006

A Boolean algebra is recursive if B is a recursive subset of the natural numbers N and the operations ∧ (meet), ∨ (join), and ¬ (complement) are partial recursive. Given two Boolean algebras and , we write if is isomorphic to and if is recursively isomorphic to , that is, if there is a partial recursive function f: B1 → B2 which is an isomorphism from to . will denote the set of atoms of and () will denote the ideal generated by the atoms of .One of the main questions which motivated this paper is “To what extent does the classical isomorphism type of a recursive Boolean algebra restrict the possible recursion theoretic properties of ?” For example, it is easy to see that must be co-r.e. (i.e., N − is an r.e. set), but can be immune, not immune, cohesive, etc? It follows from a result of Goncharov [4] that there exist classical isomorphism types which contain recursive Boolean algebras but do not contain any recursive Boolean algebras such that is recursive. Thus the classical isomorphism can restrict the possible Turing degrees of , but what is the extent of this restriction? Another main question is “What is the recursion theoretic relationship between and () in a recursive Boolean algebra?” In our attempt to answer these questions, we were led to a wide variety of recursive isomorphism types which are contained in the classical isomorphism type of any recursive Boolean algebra with an infinite set of atoms.
Fibered categories and the foundations of naive category theory
Authors: Bénabou Jean 
Published: May 2006

Any attempt to give “foundations”, for category theory or any domain in mathematics, could have two objectives, of course related.(0.1)Noncontradiction: Namely, to provide a formal frame rich enough so that all the actual activity in the domain can be carried out within this frame, and consistent, or at least relatively consistent with a well-established and “safe” theory, e.g. Zermelo-Frankel (ZF).(0.2)Adequacy, in the following, nontechnical sense:(i) The basic notions must be simple enough to make transparent the syntactic structures involved.(ii) The translation between the formal language and the usual language must be, or very quickly become, obvious. This implies in particular that the terminology and notations in the formal system should be identical, or very similar, to the current ones. Although this may seem minor, it is in fact very important.(iii) “Foundations” can only be “foundations of a given domain at a given moment”, therefore the frame should be easily adaptable to extensions or generalizations of the domain, and, even better, in view of (i), it should suggest how to find meaningful generalizations.(iv) Sometimes (ii) and (iii) can be incompatible because the current notations are not adapted to a more general situation. A compromise is then necessary. Usually when the tradition is very strong (ii) is predominant, but this causes some incoherence for the notations in the more general case (e.g. the notationf(x) for the value of a functionfatxobliges one, in category theory, to denote the composition of arrows (f, g) →g∘f, and all attempts to change this notation have, so far, failed).
Categorical semantics for higher order polymorphic lambda calculus
Authors: Seely R. A. G. 
Published: May 2006

AbstractA categorical structure suitable for interpreting polymorphic lambda calculus (PLC) is defined, providing an algebraic semantics for PLC which is sound and complete. In fact, there is an equivalence between the theories and the categories. Also presented is a definitional extension of PLC including “subtypes”, for example, equality subtypes, together with a construction providing models of the extended language, and a context for Girard's extension of the Dialectica interpretation.
Omitting types and the real line
Authors: Newelski Ludomir 
Published: May 2006

We investigate some relations between omitting types of a countable theory and some notions defined in terms of the real line, such as for example the ideal of meager subsets ofR. We also try to express connections between the logical structure of a theory and the existence of its countable models omitting certain families of types.It is well known that assuming MA we can omit <nonisolated types. But MA is rather a strong axiom. We prove that in order to be able to omit <nonisolated types it is sufficient to assume that the real line cannot be covered by less thanmeager sets; and this is in fact the weakest possible condition. It is worth pointing out that by means of forcing we can easily obtain the model of ZFC in whichRcannot be covered by <meager sets. It suffices to add to the ground modelCohen generic reals.We also formulate similar results for omitting pairwise contradictory types. It turns out that from some point of view it is much more difficult to find the family of pairwise contradictory types which cannot be omitted by a model ofT, than to find such a family of possibly noncontradictory types. Moreover, for any two countable theoriesT1,T2without prime models, the existence of a family ofκtypes which cannot be omitted by a model ofT1is equivalent to the existence of such a family forT2. This means that from the point of view of omitting types all theories without prime models are identical. Similar results hold for omitting pairwise contradictory types.
Modules of existentially closed algebras
Authors: Eklof Paul C. , Mez Hans-Christian 
Published: May 2006

AbstractThe underlying modules of existentially closed ⊿-algebras are studied. Among other things, it is proved that they are all elementarily equivalent, and that all of them are existentially closed as modules if and only if ⊿ is regular. It is also proved that every saturated module in the appropriate elementary equivalence class underlies an ex. ⊿-algebra. Applications to some problems in module theory are given. A number of open questions are mentioned.
The reals in core models
Authors: Welch Philip 
Published: May 2006

AbstractWe set = ‹, ≤L, # ›, where is the set of degrees of nonconstructibility for countable sets of countable ordinals. We show how to define inductively over this structure the degrees of such sets of ordinals in Κ, the core model, and the next few core models thereafter, i.e. without reference to mice, premice or measurable cardinals
On Dedekind complete o-minimal structures
Authors: Pillay Anand , Steinhorn Charles 
Published: May 2006

AbstractFor a countable complete o-minimal theory T, we introduce the notion of a sequentially complete model of T. We show that a model of T is sequentially complete if and only if ≺ for some Dedekind complete model . We also prove that if T has a Dedekind complete model of power greater than , then T has Dedekind complete models of arbitrarily large powers. Lastly, we show that a dyadic theory—namely, a theory relative to which every formula is equivalent to a Boolean combination of formulas in two variables—that has some Dedekind complete model has Dedekind complete models in arbitrarily large powers.
A strongly minimal expansion of (ω, s)
Authors: Marker David 
Published: May 2006

We will show that there is a nontrivial strongly minimal expansion of (ω, s), the natural numbers with successor. Pillay and Steinhorn [1] proved that there is no -minimal expansion of (ω, ≤). This result provides an interesting contrast.The strongly minimal expansion of (ω, s) is very easy to describe. Consider the order-two permutation of ω, π recursively defined byLet T be Th(ω, s, π, 0).
Strong analogues of Martin's axiom Imply Axiom R
Authors: Beaudoin Robert E. 
Published: May 2006

AbstractWe show that either PFA+ or Martin's maximum implies Fleissner's Axiom R, a reflection principle for stationary subsets of Pℵ(λ). In fact, the “plus version” (for one term denoting a stationary set) of Martin's axiom for countably closed partial orders implies Axiom R.
Conservative extensions of models of set theory and generalizations
Authors: Enayat Ali 
Published: May 2006

An attempt to answer the following question gave rise to the results of the present paper. Let be an arbitrary model of set theory. Does there exist an elementary extension of satisfying the two requirements: (1) contains an ordinal exceeding all the ordinals of ; (2) does not enlarge any (hyper) integer of ? Note that a trivial application of the ordinary compactness theorem produces a model satisfying condition (1); and an internal ultrapower modulo an internal ultrafilter produces a model satisfying condition (2) (but not (1), because of the axiom of replacement). Also, such a satisfying both conditions (1) and (2) exists if the external cofinality of the ordinals of is countable, since by [KM], would then have an elementary end extension.Using a class of models constructed by M. Rubin using in [RS], and already employed in [E1], we prove that our question in general has a negative answer (see Theorem 2.3). This result generalizes the results of M. Kaufmann and the author (appearing respectively in [Ka] and [E1]) concerning models of set theory with no elementary end extensions.In the course of the proof it was necessary to establish that all conservative extensions (see Definition 2.1) of models of ZF must be cofinal. This is in direct contrast with the case of Peano arithmetic where all conservative extensions are end extensional (as observed by Phillips in [Ph1]). This led the author to introduce two useful weakenings of the notion of a conservative end extension which, as shown by the “completeness” theorems in §3, can exist.
Preservation theorem and relativization theorem for cofinal extensions
Authors: Motohashi Nobuyoshi 
Published: May 2006

One of the typical preservation theorems in a first order classical predicate logic with equality L is the following theorem due to J. Łoś [4] and A. Tarski [9] (also cf. [1, p. 139]).Theorem A (Łoś-Tarski). For any sentences A and B in L, the following two conditions (i) and (ii) are equivalent.(i) Every extension of any model of A is a model of B.(ii) The two sentences A ⊃ C and C ⊃ B are provable in L for some existential sentence C in L.In [2], S. Feferman obtained a similar preservation theorem for outer extensions. In the following, we assume that L has a fixed binary predicate symbol <. Then Σ-formulas are formulas in L which are constructed from atomic formulas and their negations by applying ∧ (conjunctions), ∨ (disjunctions), ∀x < y (bounded universal quantifications), and ∃ (existential quantifications). An extension of an L-structure is said to be an outer extension of if ⊨ a < b and b ϵ ∣∣ imply a ϵ ∣∣ for any elements a, b in ∣∣.Theorem B (Feferman). For any sentences A and B in L, the following two conditions (i) and (ii) are equivalent.(i) Every outer extension of any model of A is a model of B.(ii) The two sentences A ⊃ C and C ⊃ B are provable in L for some Σ-sentence C in L.
Intuitionistic tense and modal logic
Authors: Ewald W. B. 
Published: May 2006

In this article we shall construct intuitionistic analogues to the main systems of classical tense logic. Since each classical modal logic can be gotten from some tense logic by one of the definitions(i) □ p ≡ p ∧ Gp ∧ Hp, ◇p ≡ p ∨ Fp ∨ Pp; or,(ii) □ p ≡ p ∧ Gp, ◇p = p ∨ Fp(see [5]), we shall find that our intuitionistic tense logics give us analogues to the classical modal logics as well.We shall not here discuss the philosophical issues raised by our logics. Readers interested in the intuitionistic view of time and modality should see [2] for a detailed discussion.In §2 we define the Kripke models for IKt, the intuitionistic analogue to Lemmon's system Kt. We then prove the completeness and decidability of this system (§§3–5). Finally, we extend our results to other sorts of tense logic and to modal logic.In the language of IKt, we have: sentence-letters p, q, r, etc.; the (intuitionistic) connectives ∧, ∨, →, ¬; and unary operators P (“it was the case”), F (it will be the case”), H (“it has always been the case”) and G (“it will always be the case”). Formulas are defined inductively: all sentence-letters are formulas; if X is a formula, so are ¬X, PX, FX, HX, and GX; if X and Y are formulas, so are X ∧ Y, X ∨ Y, and X → Y. We shall see that, in contrast to classical tense logic, F and P cannot be defined in terms of G and H.