bluuebunny/crossref_metadata_2025_split huggingface dataset:
On two hierarchies of dimensions
Authors: Baudisch Andreas 
Published: May 2006

AbstractLet T be a countable, complete, ω-stable, nonmultidimensional theory. By Lascar [7], in Teq there is in every dimension of T a type with Lascar rank ωα for some α. We give sufficient conditions for α to coincide with the level of that dimension in Pillay's [10] RK-hierarchy of dimensions computed in Teq. In particular, this is fulfilled for modules.
Locally finite theories
Authors: Mycielski Jan 
Published: May 2006

We say that a first order theoryTislocally finiteif every finite part ofThas a finite model. It is the purpose of this paper to construct in a uniform way for any consistent theoryTa locally finite theory FIN(T) which is syntactically (in a sense) isomorphic toT.Our construction draws upon the main idea of Paris and Harrington [6] (I have been influenced by some unpublished notes of Silver [7] on this subject) and generalizes the syntactic aspect of their result from arithmetic to arbitrary theories. (Our proof is syntactic, and it is simpler than the proofs of [5], [6] and [7]. This reminds me of the simple syntactic proofs of several variants of the Craig-Lyndon interpolation theorem, which seem more natural than the semantic proofs.)The first mathematically strong locally finite theory, called FIN, was defined in [1] (see also [2]). Now we get much stronger ones, e.g. FIN(ZF).From a physicalistic point of view the theorems of ZF and their FIN(ZF)-counterparts may have the same meaning. Therefore FIN(ZF) is a solution of Hilbert's second problem. It eliminates ideal (infinite) objects from the proofs of properties of concrete (finite) objects.In [4] we will demonstrate that one can develop a direct finitistic intuition that FIN(ZF) is locally finite. We will also prove a variant of Gödel's second incompleteness theorem for the theory FIN and for all its primitively recursively axiomatizable consistent extensions.The results of this paper were announced in [3].
Some results concerning strongly compact cardinals
Authors: Abe Yoshihiro 
Published: May 2006

This paper consists of two parts. In §1 we mention the first strongly compact cardinal. Magidor proved in [6] that it can be the first measurable and it can be also the first supercompact. In [2], Apter proved that Con(ZFC + there is a supercompact limit of supercompact cardinals) implies Con(ZFC + the first strongly compact cardinal κ is ϕ(κ)-supercompact + no α < κ is ϕ(α)-supercompact) for a formula ϕ which satisfies certain conditions.We shall get almost the same conclusion as Apter's theorem assuming only one supercompact cardinal. Our notion of forcing is the same as in [2] and a trick makes it possible.In §2 we study a kind of fine ultrafilter on Pκλ investigated by Menas in [7], where κ is a measurable limit of strongly compact cardinals. He showed that such an ultrafilter is not normal in some case (Theorems 2.21 and 2.22 in [7]). We shall show that it is not normal in any case (even if κ is supercompact). We also prove that it is weakly normal in some case.We work in ZFC and much of our notation is standard. But we mention the following: the letters α,β,γ… denote ordinals, whereas κ,λ,μ,… are reserved for cardinals. R(α) is the collection of sets rank <α. φM denotes the realization of a formula φ to a class M. Except when it is necessary, we drop “M”. For example, M ⊩ “κ is φ(κ)-supercompact” means “κ is φM(κ)-supercompact in M”. If x is a set, |x| is its cardinality, Px is its power set, and . If also x ⊆ OR, denotes its order type in the natural ordering. The identity function with the domain appropriate to the context is denoted by id. For the notation concerning ultrapowers and elementary embeddings, see [11]. When we talk about forcing, “⊩” will mean “weakly forces” and “p < q” means “p is stronger than q”.
On ideals of subsets of the plane and on Cohen reals
Authors: Cichoń Jacek , Pawlikowski Janusz 
Published: May 2006

AbstractLet be any proper ideal of subsets of the real line R which contains all finite subsets of R. We define an ideal * ∣ as follows: X ∈ * ∣ if there exists a Borel set B ⊂ R × R such that X ⊂ B and for any x ∈ R we have {y ∈ R: 〈x, y〉 ∈ B} ∈ . We show that there exists a family ⊂ * ∣ of power ω1 such that ⋃ ∉ * ∣ .In the last section we investigate properties of ideals of Lebesgue measure zero sets and meager sets in Cohen extensions of models of set theory.
Completeness theorem for biprobability models
Authors: Rašković Miodrag D. 
Published: May 2006

The aim of the paper is to prove the completeness theorem for biprobability models. This also solves Keisler's Problem 5.4 (see [4]).Let be a countable admissible set and ω ∈ . The logic is similar to the standard probability logic . The only difference is that two types of probability quantifiers and are allowed.A biprobability model is a structure (, μ1, μ2) where is a classical structure without operations and μ1, μ2 are two types of probability measures such that μ1 is absolutely continuous with respect to μ2, i.e. μ1 ≪ μ2.The quantifiers are interpreted in the natural way, i.e.for i = 1, 2. (The measure is the restriction of the completion of to the σ-algebra generated by the measurable rectangles and the diagonal sets Axioms and rules of inference are those of , as listed in [2] with the axiom B4 from [4], with the remark that both P1 and P2 can play the role of P, together with the following axioms:Axioms of continuity.1) .2) .Axiom of absolute continuity:where and Φn = {φ ∈ Φ: φ has n free variables}.
On the Kleene degrees of Π11 sets
Authors: Slaman Theodore A. 
Published: May 2006

AbstractLet A and B be subsets of the reals. Say that AK≥ B, if there is a real a such that the relation “x ∈ B” is uniformly ⊿1 (a, A) in . This reducibility induces an equivalence relation ≡K on the sets of reals; the ≡K-equivalence class of a set is called its Kleene degree. Let be the structure that consists of the Kleene degrees and the induced partial order ≥. A substructure of that is of interest is , the Kleene degrees of the sets of reals. If sharps exist, then there is not much to , as Steel [9] has shown that the existence of sharps implies that has only two elements: the degree of the empty set and the degree of the complete set. Legrand [4] used the hypothesis that there is a real whose sharp does not exist to show that there are incomparable elements in ; in the context of V = L, Hrbáček has shown that is dense and has no minimal pairs. The Hrbáček results led Simpson [6] to make the following conjecture: if V = L, then forms a universal homogeneous upper semilattice with 0 and 1. Simpson's conjecture is shown to be false by showing that if V = L, then Gödel's maximal thin set is the infimum of two strictly larger elements of .The second main result deals with the notion of jump in . Let A′ be the complete Kleene enumerable set relative to A. Say that A is low-n if A(n) has the same degree as ⊘(n), and A is high-n if A(n) has the same degree as ⊘(n+1). Simpson and Weitkamp [7] have shown that there is a high (high-1) incomplete set in L. They have also shown that various other sets are neither high nor low in L. Legrand [5] extended their results by showing that, if there is a real x such that x# does not exist, then there is an element of that, for all n, is neither low-n nor high-n. In §2, ZFC is used to show that, for all n, if A is and low-n then A is Borel. The proof uses a strengthened version of Jensen's theorem on sequences of admissible ordinals that appears in [7, Simpson-Weitkamp].
Σ1 definitions with parameters
Authors: Slaman T. A. 
Published: May 2006

AbstractLet p be a set. A function Φ is uniformly Σ1(p) in every admissible set if there is a Σ1 formula ϕ in the parameter p so that ϕ defines Φ in every Σ1-admissible set which includes p. A theorem of Van de Wiele states that if Φ is a total function from sets to sets then Φ is uniformly Σ1 in every admissible set if and only if it is E-recursive. A function is ESp-recursive if it can be generated from the schemes for E-recursion together with a selection scheme over the transitive closure of p. The selection scheme is exactly what is needed to insure that the ESP-recursively enumerable predicates are closed under existential quantification over the transitive closure of p. Two theorems are established: a) If the transitive closure of p is countable then a total function on sets is ESp-recursive if and only if it is uniformly Σ1(p) in every admissible set. b) For any p, if Φ is a function on the ordinal numbers then Φ is ESP-recursive if and only if it is uniformly Σ1(p) in every admissible set.
The word problem for cancellation semigroups with zero
Authors: Gurevich Yuri , Lewis Harry R. 
Published: May 2006

By theword problemfor some class of algebraic structures we mean the problem of determining, given a finite setEof equations between words (i.e. terms) and an additional equationx=y, whetherx=ymust hold in all structures satisfying each member ofE. In 1947 Post [P] showed the word problem for semigroups to be undecidable. This result was strengthened in 1950 by Turing, who showed the word problem to be undecidable forcancellation semigroups,i.e. semigroups satisfying thecancellation propertyNovikov [N] eventually showed the word problem for groups to be undecidable.(Many flaws in Turing's proof were corrected by Boone [B]. Even after his corrections, at least one problem remains; the sentence on line 16 of p. 502 of [T] does not follow if one relation is principal and the other is a commutation relation. A corrected and somewhat simplified version of Turing's proof can be built on the construction given here.)In 1966 Gurevich [G] showed the word problem to be undecidable forfinitesemigroups. However, this result on finite structures has not been extended to cancellation semigroups or groups; indeed it is easy to see that a finite cancellation semigroup is a group, so both questions are the same. We do not here settle the word problem for finite groups, but we do show that the word problem is undecidable for finite semigroups with zero (that is, having an element 0 such thatx0 = 0x= 0 for allx) satisfying an approximation to the cancellation property (1).
Register machine proof of the theorem on exponential diophantine representation of enumerable sets
Authors: Jones J. P. , Matijasevič Y. V. 
Published: May 2006

The purpose of the present paper is to give a new, simple proof of the theorem of M. Davis, H. Putnam and J. Robinson [1961], which states that every recursively enumerable relation A(a1, …, an) is exponential diophantine, i.e. can be represented in the formwhere a1 …, an, x1, …, xm range over natural numbers and R and S are functions built up from these variables and natural number constants by the operations of addition, A + B, multiplication, AB, and exponentiation, AB. We refer to the variables a1,…,an as parameters and the variables x1 …, xm as unknowns.Historically, the Davis, Putnam and Robinson theorem was one of the important steps in the eventual solution of Hilbert's tenth problem by the second author [1970], who proved that the exponential relation, a = bc, is diophantine, and hence that the right side of (1) can be replaced by a polynomial equation. But this part will not be reproved here. Readers wishing to read about the proof of that are directed to the papers of Y. Matijasevič [1971a], M. Davis [1973], Y. Matijasevič and J. Robinson [1975] or C. Smoryński [1972]. We concern ourselves here for the most part only with exponential diophantine equations until §5 where we mention a few consequences for the class NP of sets computable in nondeterministic polynomial time.
Quelques précisions sur la D.O.P. et la profondeur d'une théorie
Authors: Lascar D. 
Published: May 2006

AbstractWe give here alternative definitions for the notions that S. Shelah has introduced in recent papers: the dimensional order property and the depth of a theory. We will also give a proof that the depth of a countable theory, when denned, is an ordinal recursive in T.
The hereditary partial effective functionals and recursion theory in higher types
Authors: Longo G. , Moggi E. 
Published: May 2006

AbstractA type-structure of partial effective functionals over the natural numbers, based on a canonical enumeration of the partial recursive functions, is developed. These partial functionals, defined by a direct elementary technique, turn out to be the computable elements of the hereditary continuous partial objects; moreover, there is a commutative system of enumerations of any given type by any type below (relative numberings).By this and by results in [1] and [2], the Kleene-Kreisel countable functionals and the hereditary effective operations (HEO) are easily characterized.
Two weak consequences of 0#
Authors: Gitik M. , Magidor M. , Woodin H. 
Published: May 2006

AbstractIt is proven that the following statement:“there exists a club C ⊆ κ such that every α ∈ C is an inaccessible cardinal in L and, for every δ a limit point of C, C ∩ δ is almost contained in every club of δ of L”is equiconsistent with a weakly compact cardinal if δ = ℵ1, and with a weakly compact cardinal of order 1 if δ = ℵ2.
Limit ultrapowers and abstract logics
Authors: Lipparini Paolo 
Published: May 2006

AbstractWe associate with any abstract logic L a family F(L) consisting, intuitively, of the limit ultrapowers which are complete extensions in the sense of L.For every countably generated [ω, ω]-compact logic L, our main applications are:(i) Elementary classes of L can be characterized in terms of ≡L only.(ii) If and are countable models of a countable superstable theory without the finite cover property, then .(iii) There exists the “largest” logic M such that complete extensions in the sense of M and L are the same; moreover M is still [ω, ω]-compact and satisfies an interpolation property stronger than unrelativized ⊿-closure.(iv) If L = Lωω(Qx), then cf(ωx) > ω and λω < ωx, for all λ < ωx.We also prove that no proper extension of Lωω generated by monadic quantifiers is compact. This strengthens a theorem of Makowsky and Shelah. We solve a problem of Makowsky concerning Lκλ-compact cardinals. We partially solve a problem of Makowsky and Shelah concerning the union of compact logics.
Complete Boolean ultraproducts
Authors: Canjar R. Michael 
Published: May 2006

Throughout this paper, B will always be a Boolean algebra and Γ an ultrafilter on B. We use + and Σ for the Boolean join operation and · and Π for the Boolean meet.κ is always a regular cardinal. C(κ) is the full structure of κ, the structure with universe κ and whose functions and relations consist of all unitary functions and relations on κ. κB is the collection of all B-valued names for elements of κ. We use symbols f, g, h for members of κB. Formally an element f ∈ κB is a mapping κ → B with the properties that Σα∈κf(α) = 1B and that f(α) · f(β) = 0B whenever α ≠ β. We view f(α) as the Boolean-truth value indicating the extent to which the name f is equal to α, and we will hereafter write ∥f = α∥ for f(α). For every α ∈ κ there is a canonical name fα ∈ κB which has the property that ∥fα = α∥ = 1. Hereafter we identify α and fα.If B is a κ+-complete Boolean algebra and Γ is an ultrafilter on B, then we may define the Boolean ultraproduct C(κ)B/Γ in the following manner. If ϕ(x0, x1, …, xn) is a formula of Lκ, the language for C(κ) (which has symbols for all finitary functions and relations on κ), and f0, f1, …, fn−1 are elements of κB then we define the Boolean-truth value of ϕ(f0, f1, …, fn−1) as
Correction to “Simple r. e. degree structures”
Authors: Lubarsky Robert S. 
Published: May 2006

In the paper mentioned in the title (this Journal, vol. 52 (1987), pp. 208–213), it is shown that if ⊨ “V = HC is recursively inaccessible” is ω-standard -nonstandard, then = s.p.() has at most four r. e. degrees. They are 0 = deg(∅), = deg{e ∣ We is a recursive well-ordering of ω}, = deg{R ∣ ⊨ “R codes a well-ordering”}, and ∨ . Furthermore, 0 < < ∨ and 0 < . Then it is claimed that < < ∨ and = ∨ if are each possible. In fact, < < ∨ always.The mistake in the argument is that the model ≤T is really a structure on a set, which we may as well take as ω: there is an R ⊆ ω × ω, R ≤T, and ‹ω, R› ≃ . So a copy of coded as a relation on ω is ≤ over . But there is no reason to think that the restriction of the isomorphism of and ‹ω, R› to is Σ1().
Differentially algebraic group chunks
Authors: Pillay Anand 
Published: May 2006

We point out that a group first order definable in a differentially closed field K of characteristic 0 can be definably equipped with the structure of a differentially algebraic group over K. This is a translation into the framework of differentially closed fields of what is known for groups definable in algebraically closed fields (Weil's theorem).I restrict myself here to showing (Theorem 20) how one can find a large “differentially algebraic group chunk” inside a group defined in a differentially closed field. The rest of the translation (Theorem 21) follows routinely, as in [B].What is, perhaps, of interest is that the proof proceeds at a completely general (soft) model theoretic level, once Facts 1–4 below are known.Fact 1. The theory of differentially closed fields of characteristic 0 is complete and has quantifier elimination in the language of differential fields (+, ·,0,1, −1,d).Fact 2. Affine n-space over a differentially closed field is a Noetherian space when equipped with the differential Zariski topology.Fact 3. If K is a differentially closed field, k ⊆ K a differential field, and a and are in k, then a is in the definable closure of k ◡ iff a ∈ ‹› (where k ‹› denotes the differential field generated by k and).Fact 4. The theory of differentially closed fields of characteristic zero is totally transcendental (in particular, stable).
The classification of small weakly minimal sets. III: Modules
Authors: Buechler Steven 
Published: May 2006

AbstractTheorem A. Let M be a left R-module such that Th(M) is small and weakly minimal, but does not have Morley rank 1. Let A = acl(∅) ⋂ M and I = {r ∈ R: rM ⊂ A}. Notice that I is an ideal.(i) F = R/Iis a finite field.(ii) Suppose that a, b0,…,bn, ∈ M and . Then there are s, ri ∈ R, i ≤ n, such that sa + Σi≤nribi ∈ A and s ∉ I.It follows from Theorem A that algebraic closure in M is modular. Using this and results in [B1] and [B2], we obtainTheorem B. Let M be as in Theorem A. Then Vaught's conjecture holds for Th(M).
Cylindric algebras with terms
Authors: Feldman Norman 
Published: May 2006

In this paper we discuss cylindric algebras with terms. The setting is two—sorted algebras—one sort for terms and one for Boolean elements. As with cylindric algebras, a cylindric algebra with terms has its roots in first order predicate logic [HMT1].Let Σ be a set of sentences in a first order language with terms, equality and variables u0,u1,u2, …, Define a relation ≡Σ on Fm, the set of formulas, by φ ≡Σθ if and only if Σ ⊢ φ ↔ θ, and on Tm, the set of terms, by τ ≡Σσ if and only if Σ ⊢ τ ≈ σ. The operations +, ·, cκ, 0, 1 are defined as usual on equivalence classes. Define , where is σ with τ substituted for all occurrences of uκ. That the operation *κ, for κ < α, is well defined follows from the first order axioms of equality. Let vκ = [uκ]. To establish the link between terms and Booleans, define operations oκ as follows: , where φ' is a variant of φ such that uκ is free for τ in φ′ and is φ′ with τ substituted for all free occurrences of uκ in φ′. From the first order axioms it follows that oκ, for κ < α, is well defined. Finally, instead of diagonal elements, we define a Boolean-valued operation on terms as follows: [τ] e [σ] = [τ ≈ σ].
Poly-separated and ω-stable nilpotent groups
Authors: Nesin Ali 
Published: May 2006

Let π be a set of primes. We will call a group π-separated if it can be decomposed as a central product of a π-torsion group of bounded exponent and a π-radicable group. It is easy to see that an abelian π-separated group can in fact be decomposed as a direct product of bounded and π-radicable factors (Lemma 1.1 below). A poly-π-separated group is one which can be obtained from π-separated groups by forming a finite series of group extensions. We will show here:Theorem 1. Every poly-π-separated nilpotent group is π-separated.The need for such a result arises in model theory in the case that π is the set of all primes, in which case we refer simply to separated and poly-separated groups. In connection with the conjecture that ω-stable simple groups are algebraic, it is useful to have a structure theory for solvable ω-stable groups analogous to the theory available in the algebraic case over algebraically closed fields. In particular the structure of nilpotent ω-stable groups is of interest, for example in connection with the known result [Zi1], [Ne] that the derived subgroup of a connected solvable ω-stable group of finite Morley rank is nilpotent.As a model-theoretic application of Theorem 1 we obtain:Theorem 2. If G is an ω-stable nilpotent group then G may be decomposed as a central product B * D with B and D 0-definable subgroups, B torsion of bounded exponent, and D radicable. In particular, B and D are ω-stable. Furthermore, ω · rk(B ∩ D) ≤ rk D.Corollary. The ω-stable groups of finite Morley rank are exactly the central products B * D of ω-stable nilpotent groups of finite Morley rank with B torsion of bounded exponent, D radicable, and B ∩ D finite.In addition to the purely algebraic Theorem 1, these results depend on Macintyre's characterization [Mac] of the ω-stable abelian groups as exactly the separated ones.
Lattice embeddings into the recursively enumerable degrees. II
Authors: Ambos-Spies K. , Lerman M. 
Published: May 2006

The problem of characterizing the finite lattices which can be embedded into the recursively enumerable degrees has a long history, which is summarized in [AL]. This problem is an important one, as its solution is necessary if a decision procedure for the ∀∃-theory of the poset of recursively emumerable degrees is to be found. A recursive nonembeddability condition, NEC, which subsumes all known nonembeddability conditions was presented in [AL]. This paper focuses on embeddability. An embeddability condition, EC, is introduced, and we prove that every finite lattice having EC can be embedded (as a lattice) into . EC subsumes all known embeddability conditions.EC is a Π3 condition which states that certain obstructions to proving embeddability do not exist. It seems likely that the recursive labeled trees used in EC can be replaced with trees which are effectively generated from uniformly defined finite trees, in which case EC would be equivalent to a recursive condition. We do not know whether EC and NEC are complementary. This problem seems to be combinatorial, rather than recursion-theoretic in nature. Our efforts to find a finite lattice satisfying neither EC nor NEC have, to this point, been unsuccessful. It is the second author's conjecture that the techniques for proving embeddability which are used in this paper cannot be refined very much to obtain new embeddability results.EC is introduced in §2, and the various conditions and definitions are motivated by presenting examples of embeddable lattices and indicating how the embedding proof works in those particular cases. The embedding construction is presented in §3, and the proof in §4.