bluuebunny/crossref_metadata_2025_split huggingface dataset:
Analytic cell decomposition and the closure of p-adic semianalytic sets
Authors: Liu Nianzheng 
Published: May 2006

The p-adic semianalytic sets are defined, locally, as boolean combinations of sets of the form over the p-adic fields ℚp, where f is an analytic function. A well-know example due to Osgood showed the projection of a semianalytic set need not be a semianalytic set. We call those sets that are, locally, the projections of p-adic semianalytic sets p-adic subanalytic sets. The theory of p-adic subanalytic sets was presented by Denef and Van den Dries in [5]. The basic tools are the quantifier elimination techniques together with the ultrametric Weierstrass Preparation Theorem. Simultaneously with their developments of the p-adic subanalytic sets, they established some basic properties of p-adic semianalytic sets.In this paper, we prove that the closure of any p-adic semianalytic set is also a semianalytic set. The analogous property for real semianalytic sets was proved in [12] and that for rigid semianalytic sets, informed by the referee, has been proved recently by a quite different method in [14] (cf. [9]). The keys to the proof are a separation lemma (Lemma 2) and an analytic cell decomposition theorem (Theorem 2) which is an analytic version of Denef's cell decomposition theorem (see [3, 4]; A total different form of anayltic cells appeared in [13]). The analytic cell decomposition theorem allows us to partition certain kinds of basic subsets into analytic cells that possess the closure property (see §1 for the definition).
Tailoring recursion for complexity
Authors: Grädel Erich , Gurevich Yuri 
Published: May 2006

AbstractWe design functional algebras that characterize various complexity classes of global functions. For this purpose, classical schemata from recursion theory are tailored for capturing complexity. In particular we present a functional analog of first-order logic and describe algebras of the functions computable in nondeterministic logarithmic space, deterministic and nondeterministic polynomial time, and for the functions computable by AC1 -circuits.
Intuitionistic sets and ordinals
Authors: Taylor Paul 
Published: May 2006

AbstractTransitive extensional well founded relations provide an intuitionistic notion of ordinals which admits transfinite induction. However these ordinals are not directed and their successor operation is poorly behaved, leading to problems of functoriality.We show how to make the successor monotone by introducing plumpness, which strengthens transitivity. This clarifies the traditional development of successors and unions, making it intuitionistic; even the (classical) proof of trichotomy is made simpler. The definition is, however, recursive, and, as their name suggests, the plump ordinals grow very rapidly.Directedness must be defined hereditarily. It is orthogonal to the other four conditions, and the lower powerdomain construction is shown to be the universal way of imposing it.We treat ordinals as order-types, and develop a corresponding set theory similar to Osius' transitive set objects. This presents Mostowski's theorem as a reflection of categories, and set-theoretic union is a corollary of the adjoint functor theorem. Mostowski's theorem and the rank for some of the notions of ordinal are formulated and proved without the axiom of replacement, but this seems to be unavoidable for the plump rank.The comparison between sets and toposes is developed as far as the identification of replacement with completeness, and there are some suggestions for further work in this area.Each notion of set or ordinal defines a free algebra for one of the theories discussed by Joyal and Moerdijk, namely joins of a family of arities together with an operation s satisfying conditions such as x ≤ sx, monotonicity or s(x ∨ y) ≤ sx ∨ sy.Finally we discuss the fixed point theorem for a monotone endofunction s of a poset with least element and directed joins. This may be proved under each of a variety of additional hypotheses. We explain why it is unlikely that any notion of ordinal obeying the induction scheme for arbitrary predicates will prove the pure result.
Analytic equivalence relations and Ulm-type classifications
Authors: Hjorth Greg , Kechris Alexander S. 
Published: May 2006

Our main goal in this paper is to establish a Glimm-Effros type dichotomy for arbitrary analytic equivalence relations.The original Glimm-Effros dichotomy, established by Effros [Ef], [Ef1], who generalized work of Glimm [G1], asserts that if an Fσ equivalence relation on a Polish space X is induced by the continuous action of a Polish group G on X, then exactly one of the following alternatives holds:(I) Elements of X can be classified up to E-equivalence by “concrete invariants” computable in a reasonably definable way, i.e., there is a Borel function f: X → Y, Y a Polish space, such that xEy ⇔ f(x) = f(y), or else(II) E contains a copy of a canonical equivalence relation which fails to have such a classification, namely the relation xE0y ⇔ ∃n∀m ≥ n(x(n) = y(n)) on the Cantor space 2ω (ω = {0,1,2, …}), i.e., there is a continuous embedding g: 2ω → X such that xE0y ⇔ g(x)Eg(y).Moreover, alternative (II) is equivalent to:(II)′ There exists an E-ergodic, nonatomic probability Borel measure on X, where E-ergodic means that every E-invariant Borel set has measure 0 or 1 and E-nonatomic means that every E-equivalence class has measure 0.
On a generalization of distributivity
Authors: Kanai Yasuo 
Published: May 2006

In this paper, we generalize the notion of distributivity and consider some properties of distributive ideals, that is, ideals I such that the algebra P(κ)/I is distributive in our sense.Our notation and terminology is explained in §1, while the main results of this paper begin in §2. We shall show here some relations of the distributivity and the ideal theoretic partitions. In §3, we shall study the class of distributive ideals over κ whose existence is equivalent to the ineffability of κ, and other classes. Finally, in §4, we shall consider the equivalence of the Boolean prime ideal theorem and show that the existence of certain distributive ideals characterizes several large cardinals. As a byproduct, we can give a simple proof of Ketonen's theorem that κ is strongly compact if and only if for any regular cardinal λ ≥ κ there exists a nontrivial κ-complete prime ideal over λ.
Cut-elimination for simple type theory with an axiom of choice
Authors: Mints G. 
Published: May 2006

AbstractWe present a cut-elimination proof for simple type theory with an axiom of choice formulated in the language with an epsilon-symbol. The proof is modeled after Takahashi's proof of cut-elimination for simple type theory with extensionality. The same proof works when types are restricted, for example for second-order classical logic with an axiom of choice.
Generalized cohesiveness
Authors: Hummel Tamara , Jockusch Carl G. 
Published: May 2006

AbstractWe study some generalized notions of cohesiveness which arise naturally in connection with effective versions of Ramsey's Theorem. An infinite set A of natural numbers is n-cohesive (respectively, n-r-cohesive) if A is almost homogeneous for every computably enumerable (respectively, computable) 2-coloring of the n-element sets of natural numbers. (Thus the 1-cohesive and 1-r-cohesive sets coincide with the cohesive and r-cohesive sets, respectively.) We consider the degrees of unsolvability and arithmetical definability levels of n-cohesive and n-r-cohesive sets. For example, we show that for all n ≥ 2, there exists a n-cohesive set. We improve this result for n = 2 by showing that there is a 2-cohesive set. We show that the n-cohesive and n-r-cohesive degrees together form a linear, non-collapsing hierarchy of degrees for n ≥ 2. In addition, for n ≥ 2 we characterize the jumps of n-cohesive degrees as exactly the degrees ≥ 0(n+1) and also characterize the jumps of the n-r-cohesive degrees.
Unions of rectifiable curves in Euclidean space and the covering number of the meagre ideal
Authors: Steprāns Juris 
Published: May 2006

AbstractTo any metric space it is possible to associate the cardinal invariant corresponding to the least number of rectifiable curves in the space whose union is not meagre. It is shown that this invariant can vary with the metric space considered, even when restricted to the class of convex subspaces of separable Banach spaces. As a corollary it is obtained that it is consistent with set theory that any set of reals of size ℵ1 is meagre yet there are ℵ1 rectifiable curves in ℝ3 whose union is not meagre. The consistency of this statement when the phrase “rectifiable curves” is replaced by “straight lines” remains open.
A finite basis theorem for residually finite, congruence meet-semidistributive varieties
Authors: Willard Ross 
Published: May 2006

AbstractWe derive a Mal'cev condition for congruence meet-semidistributivity and then use it to prove two theorems. Theorem A: if a variety in a finite language is congruence meet-semidistributive and residually less than some finite cardinal, then it is finitely based. Theorem B: there is an algorithm which, given m < ω and a finite algebra in a finite language, determines whether the variety generated by the algebra is congruence meet-semidistributive and residually less than m.
Doughnuts, floating ordinals, square brackets, and ultraflitters
Authors: Prisco Carlos A. Di , Henle James M. 
Published: May 2006

In this paper, we study partition properties of the set of real numbers. The meaning of “set of real numbers” will vary, referring at times to the collection of sequences of natural numbers, ωω; the collection of infinite sets of natural numbers [ω]ω; the collection of infinite sequences of zeroes and ones, 2ω; or (ω), the power set of ω.The archetype for the relations is the property: “all sets of reals are Ramsey,” in the notation of Erdős and Hajnal, ω → (ω)ω. This states that for every partition F : [ω]ω → 2, there is an infinite set H ∈ [ω]ω such that F is constant on [H]ω. Like virtually all of the properties we will discuss, it contradicts the Axiom of Choice but is compatible with the principle of dependent choices (DC). DC will be used throughout the paper wihtout further mention.The properties discussed in this paper will vary in two respects. Some, like ω → (ω)ω, will be incompatible with the existence of an ultrafilter on ω (UF) and some will not. Some are known to be consistent relative to ZF alone, and for some, such as ω → (ω)ω, the question is still open. All properties, however, are true in Solovay's model and hence are consistent relative to Con(ZF + “there exists an inaccessible cardinal”).
Laver sequences for extendible and super-almost-huge cardinals
Authors: Corazza Paul 
Published: May 2006

AbstractVersions of Laver sequences are known to exist for supercompact and strong cardinals. Assuming very strong axioms of infinity, Laver sequences can be constructed for virtually any globally defined large cardinal not weaker than a strong cardinal; indeed, under strong hypotheses. Laver sequences can be constructed for virtually any regular class of embeddings. We show here that if there is a regular class of embeddings with critical point κ, and there is an inaccessible above κ, then it is consistent for there to be a regular class that admits no Laver sequence. We also show that extendible cardinals are Laver-generating, i.e., that assuming only that κ is extendible, there is an extendible Laver sequence at κ. We use the method of proof to answer a question about Laver-closure of extendible cardinals at inaccessibles. Finally, we consider Laver sequences for super-almost-huge cardinals. Assuming slightly more than super-almost-hugeness, we show that there are super-almost-huge Laver sequences, improving the previously known upper bound for such Laver sequences. We also describe conditions under which the canonical construction of a Laver sequence fails for super-almost-huge cardinals.
Flat Morley sequences
Authors: Newelski Ludomir 
Published: May 2006

AbstractAssumeTis a small superstable theory. We introduce the notion of a flat Morley sequence, which is a counterpart of the notion of an infinite Morley sequence in a typep, in case whenpis a complete type over a finite set of parameters. We show that for any flat Morley sequenceQthere is a modelMofTwhich isτ-atomic over {Q}. When additionallyThas few countable models and is 1-based, we prove that withinMthere is an infinite Morley sequenceI, withI⊂ dcl(Q), such thatMis prime overI.
Finite powers of strong measure zero sets
Authors: Scheepers Marion 
Published: May 2006

AbstractIn a previous paper—[17]—we characterized strong measure zero sets of reals in terms of a Ramseyan partition relation on certain subspaces of the Alexandroff duplicate of the unit interval. This framework gave only indirect access to the relevant sets of real numbers. We now work more directly with the sets in question, and since it costs little in additional technicalities, we consider the more general context of metric spaces and prove:1. If a metric space has a covering property of Hurewicz and has strong measure zero, then its product with any strong measure zero metric space is a strong measure zero metric space (Theorem 1 and Lemma 3).2. A subspaceXof a σ-compact metric spaceYhas strong measure zero if, and only if, a certain Ramseyan partition relation holds forY(Theorem 9).3. A subspaceXof a σ-compact metric spaceYhas strong measure zero in all finite powers if, and only if, a certain Ramseyan partition relation holds forY(Theorem 12).Then 2 and 3 yield characterizations of strong measure zeroness for σ-totally bounded metric spaces in terms of Ramseyan theorems.
Undecidability of the real-algebraic structure of models of intuitionistic elementary analysis
Authors: Erdélyi-Szabó Miklós 
Published: May 2006

AbstractWe show that true first-order arithmetic is interpretable over the real-algebraic structure of models of intuitionistic analysis built upon a certain class of complete Heyting algebras. From this the undecidability of the structures follows. We also show that Scott's model is equivalent to true second-order arithmetic. In the appendix we argue that undecidability on the language of ordered rings follows from intuitionistically plausible properties of the real numbers.
Stationary sets and infinitary logic
Authors: Shelah Saharon , Väänänen Jouko 
Published: May 2006

AbstractLet be the class of structures 〈λ, <, A〉, where A ⊆ λ is disjoint from a club, and let be the class of structures 〈λ, <, A), where A ⊆ λ contains a club. We prove that if λ = λ<κ is regular, then no sentence of Lλ + κ separates and On the other hand, we prove that if λ = μ+ , μ = μ<μ, and a forcing axiom holds (and if μ = ℵ0), then there is a sentence of Lλλ which separates and .
Completeness of the propositions-as-types interpretation of intuitionistic logic into illative combinatory logic
Authors: Dekkers Wil , Bunder Martin , Barendregt Henk 
Published: May 2006

AbstractIllative combinatory logic consists of the theory of combinators or lambda calculus extended by extra constants (and corresponding axioms and rules) intended to capture inference. In a preceding paper, [2], we considered 4 systems of illative combinatory logic that are sound for first order intuitionistic propositional and predicate logic. The interpretation from ordinary logic into the illative systems can be done in two ways: following the propositions-as-types paradigm, in which derivations become combinators, or in a more direct way, in which derivations are not translated. Both translations are closely related in a canonical way. In the cited paper we proved completeness of the two direct translations. In the present paper we prove that also the two indirect translations are complete. These proofs are direct whereas in another version, [3], we proved completeness by showing that the two corresponding illative systems are conservative over the two systems for the direct translations. Moreover we shall prove that one of the systems is also complete for predicate calculus with higher type functions.
Effective presentability of Boolean algebras of Cantor-Bendixson rank 1
Authors: Downey Rod , Jockusch Carl G. 
Published: May 2006

AbstractWe show that there is a computable Boolean algebra and a computably enumerable ideal I of such that the quotient algebra /I is of Cantor-Bendixson rank 1 and is not isomorphic to any computable Boolean algebra. This extends a result of L. Feiner and is deduced from Feiner's result even though Feiner's construction yields a Boolean algebra of infinite Cantor-Bendixson rank.
The complexity of decision procedures in relevance logic II
Authors: Urquhart Alasdair 
Published: May 2006

In this paper, we show that there is no primitive recursive decision procedure for the implication-conjunction fragments of the relevant logics R, E and T, as well as for a family of related logics. The lower bound on the complexity is proved by combining the techniques of an earlier paper on the same subject [20] with a method used by Lincoln, Mitchell, Scedrov and Shankar in proving that propositional linear logic is undecidable.The decision problem for the pure implicational fragments of E and R were solved by Saul Kripke in a tour de force of combinatorial reasoning, published only as an abstract [9]. Belnap and Wallace extended Kripke's decision procedure to the implication-negation fragment of E in [3]; an account of their decision method is to be found in [1, pp. 124–139]. The decision method extends immediately to the implication/negation fragment of R. In fact, in the case of R we can go farther: Meyer in his thesis [13] showed how to translate the logic LR, which results from R by omitting the distribution axiom, into R→⋀, so that the decision procedure can be extended to all of LR. This decision procedure has been implemented as a program Kripke by Thistlewaite, McRobbie and Meyer [17]. The program is not simply a straightforward implementation of the decision procedure; finite matrices are used extensively to prune invalid nodes from the search tree.
The logic of recursive equations
Authors: Hurkens A. J. C. , McArthur Monica , Moschovakis Yiannis N. , Moss Lawrence S. , Whitney Glen T. 
Published: May 2006

AbstractWe study logical systems for reasoning about equations involving recursive definitions. In particular, we are interested in “propositional” fragments of the functional language of recursion FLR [18, 17], i.e., without the value passing or abstraction allowed in FLR. The “pure,” propositional fragment FLR0 turns out to coincide with the iteration theories of [1]. Our main focus here concerns the sharp contrast between the simple class of valid identities and the very complex consequence relation over several natural classes of models.
On the strength of Ramsey's theorem for pairs
Authors: Cholak Peter A. , Jockusch Carl G. , Slaman Theodore A. 
Published: May 2006

AbstractWe study the proof–theoretic strength and effective content of the infinite form of Ramsey's theorem for pairs. Let RTkndenote Ramsey's theorem fork–colorings ofn–element sets, and let RT<∞ndenote (∀k)RTkn. Our main result on computability is: For anyn≥ 2 and any computable (recursive)k–coloring of then–element sets of natural numbers, there is an infinite homogeneous setXwithX″ ≤T0(n). LetIΣnandBΣndenote the Σninduction and bounding schemes, respectively. Adapting the casen= 2 of the above result (whereXis low2) to models of arithmetic enables us to show that RCA0+IΣ2+ RT22is conservative over RCA0+IΣ2for Π11statements and that RCA0+IΣ3+ RT<∞2is Π11-conservative over RCA0+IΣ3. It follows that RCA0+ RT22does not implyBΣ3. In contrast, J. Hirst showed that RCA0+ RT<∞2does implyBΣ3, and we include a proof of a slightly strengthened version of this result. It follows that RT<∞2is strictly stronger than RT22overRCA0.
Hyperimaginaries and automorphism groups
Authors: Lascar D. , Pillay A. 
Published: May 2006

A hyperimaginary is an equivalence class of a type-definable equivalence relation on tuples of possibly infinite length. The notion was recently introduced in [1], mainly with reference to simple theories. It was pointed out there how hyperimaginaries still remain in a sense within the domain of first order logic. In this paper we are concerned with several issues: on the one hand, various levels of complexity of hyperimaginaries, and when hyperimaginaries can be reduced to simpler hyperimaginaries. On the other hand the issue of what information about hyperimaginaries in a saturated structure M can be obtained from the abstract group Aut(M).In Section 2 we show that if T is simple and canonical bases of Lascar strong types exist in Meq then hyperimaginaries can be eliminated in favour of sequences of ordinary imaginaries. In Section 3, given a type-definable equivalence relation with a bounded number of classes, we show how the quotient space can be equipped with a certain compact topology. In Section 4 we study a certain group introduced in [5], which we call the Galois group of T, develop a Galois theory and make the connection with the ideas in Section 3. We also give some applications, making use of the structure of compact groups. One of these applications states roughly that bounded hyperimaginaries can be eliminated in favour of sequences of finitary hyperimaginaries. In Sections 3 and 4 there is some overlap with parts of Hrushovski's paper [2].
Pure type systems with more liberal rules
Authors: Bunder Martin , Dekkers Wil 
Published: May 2006

Abstract.Pure Type Systems. PTSs, introduced as a generalisation of the type systems of Barendregt's lambda-cube, provide a foundation for actual proof assistants, aiming at the mechanic verification of formal proofs. In this paper we consider simplifications of some of the rules of PTSs. This is of independent interest for PTSs as this produces more flexible PTS-like systems, but it will also help, in a later paper, to bridge the gap between PTSs and systems of Illative Combinatory Logic.First we consider a simplification of the start and weakening rules of PTSs. which allows contexts to be sets of statements, and a generalisation of the conversion rule. The resulting Set-modified PTSs or SPTSs, though essentially equivalent to PTSs, are closer to standard logical systems.A simplification of the abstraction rule results in Abstraction-modified PTSs or APTSs. These turn out to be equivalent to standard PTSs if and only if a condition (*) holds. Finally we consider SAPTSs which have both modifications.
On tarski on models
Authors: Bays Timothy 
Published: May 2006

Abstract.This paper concerns Tarski's use of the term “model” in his 1936 paper “On the Concept of Logical Consequence.” Against several of Tarski's recent defenders. I argue that Tarski employed a non-standard conception of models in that paper. Against Tarski's detractors. I argue that this nonstandard conception is more philosophically plausible than it may appear. Finally, I make a few comments concerning the traditionally puzzling case of Tarski's ω-rule example.
Exchange rules
Authors: Piazza Mario 
Published: May 2006

AbstractIn this paper, we show by a proof-theoretical argument that in a logic without structural rules, that is in noncommutative linear logic with exponentials, every formula A for which exchange rules (and weakening and contraction as well) are admissible is provably equivalent to? A. This property shows that the expressive power of “noncommutative exponentials” is much more important than that of “commutative exponentials”.