bluuebunny/crossref_metadata_2025_split huggingface dataset:
Saturated ideals and the singular cardinal hypothesis
Authors: Matsubara Yo 
Published: May 2006

The large cardinal-like properties of saturated ideals have been investigated by various authors, including Foreman [F], and Jech and Prikry [JP], among others. One of the most interesting consequences of a strongly compact cardinal is the following theorem of Solovay [So2]: if a strongly compact cardinal exists then the singular cardinal hypothesis holds above it. In this paper we discuss the question of relating the existence of saturated ideals and the singular cardinal hypothesis. We will show that the existence of “strongly” saturated ideals implies the singular cardinal hypothesis. As a biproduct we will present a proof of the above mentioned theorem of Solovay using generic ultrapowers. See Jech and Prikry [JP] for a nice exposition of generic ultrapowers. We owe a lot to the work of Foreman [F]. We would like to express our gratitude to Noa Goldring for many helpful comments and discussions.Throughout this paper we assume that κ is a strongly inaccessible cardinal and λ is a cardinal >κ. By an ideal on κλ we mean a κ-complete fine ideal on Pκλ. For I an ideal on κλ let PI denote the poset of I-positive subsets of κλ.Definition. Let I be an ideal on κλ. We say that I is a bounding ideal if 1 ⊩-PI “δ(δ is regular cardinal ”.We can show that if a normal ideal is “strongly” saturated then it is bounding.Theorem 1. If 1 is an η-saturated normal ideal onκλ, where η is a cardinal <λsuch that there are fewer thanκmany cardinals betweenκand η (i.e. η < κ+κ), then I is bounding.Proof. Let I be such an ideal on κλ. By the work of Foreman [F] and others, we know that every λ+-saturated normal ideal is precipitous. Suppose G is a generic filter for our PI. Let j: V → M be the corresponding generic elementary embedding. By a theorem of Foreman [F, Lemma 10], we know that Mλ ⊂ M in V[G]. By η-saturation, cofinalities ≥η are preserved; that is, if cfvα ≥ η, then cfvα = cfv[G]α. From j ↾ Vκ being the identity on Vκ and M being λ-closed in V[G], we conclude that cofinalities <κ are preserved. Therefore if cfvα ≠ cfv[G]α then κ ≤ cfvα < η.
Phase semantics and sequent calculus for pure noncommutative classical linear propositional logic
Authors: Abrusci V. Michele 
Published: May 2006

The linear logic introduced in [3] by J.-Y. Girard keeps one of the so-called structural rules of the sequent calculus: the exchange rule. In a one-sided sequent calculus this rule can be formulated asThe exchange rule allows one to disregard the order of the assumptions and the order of the conclusions of a proof, and this means, when the proof corresponds to a logically correct program, to disregard the order in which the inputs and the outputs occur in a program.In the linear logic introduced in [3], the exchange rule allows one to prove the commutativity of the multiplicative connectives, conjunction (⊗) and disjunction (⅋). Due to the presence of the exchange rule in linear logic, in the phase semantics for linear logic one starts with a commutative monoid. So, the usual linear logic may be called commutative linear logic.The aim of the investigations underlying this paper was to see, first, what happens when we remove the exchange rule from the sequent calculus for the linear propositional logic at all, and then, how to recover the strength of the exchange rule by means of exponential connectives (in the same way as by means of the exponential connectives ! and ? we recover the strength of the weakening and contraction rules).
Louveau's theorem for the descriptive set theory of internal sets
Authors: Schilling Kenneth , Živaljević Boško 
Published: May 2006

AbstractWe give positive answers to two open questions from [15]. (1) For every set C countably determined over , if C is then it must be over , and (2) every Borel subset of the product of two internal sets X and Y all of whose vertical sections are can be represented as an intersection (union) of Borel sets with vertical sections of lower Borel rank. We in fact show that (2) is a consequence of the analogous result in the case when X is a measurable space and Y a complete separable metric space (Polish space) which was proved by A. Louveau and that (1) is equivalent to the property shared by the inverse standard part map in Polish spaces of preserving almost all levels of the Borel hierarchy.
Peano arithmetic may not be interpretable in the monadic theory of linear orders
Authors: Lifsches Shmuel , Shelah Saharon 
Published: May 2006

AbstractGurevich and Shelah have shown that Peano Arithmetic cannot be interpreted in the monadic second-order theory of short chains (hence, in the monadic second-order theory of the real line). We will show here that it is consistent that the monadic second-order theory of no chain interprets Peano Arithmetic.
A sufficient condition for completability of partial combinatory algebras
Authors: Asperti Andrea , Ciabattoni Agata 
Published: May 2006

AbstractA Partial Combinatory Algebra is completable if it can be extended to a total one. In [1] it is asked (question 11, posed by D. Scott, H. Barendregt, and G. Mitschke) if every PCA can be completed. A negative answer to this question was given by Klop in [12, 11]; moreover he provided a sufficient condition for completability of a PCA (M, •, K,S) in the form of ten axioms (inequalities) on terms of M. We prove that just one of these axiom (the so called Barendregt's axiom) is sufficient to guarantee (a slightly weaker notion of) completability.
Stretchings
Authors: Finkel O. , Ressayre J. P. 
Published: May 2006

AbstractA structure is locally finite if every finitely generated substructure is finite; local sentences are universal sentences all models of which are locally finite. The stretching theorem for local sentences expresses a remarkable reflection phenomenon between the finite and the infinite models of local sentences. This result in part requires strong axioms to be proved; it was studied by the second named author, in a paper of this Journal, volume 53. Here we correct and extend this paper; in particular we show that the stretching theorem implies the existence of inaccessible cardinals, and has precisely the consistency strength of Mahlo cardinals of finite order. And we present a sequel due to the first named author:(i) decidability of the spectrum Sp(φ) of a local sentence φ, below ωω; where Sp(φ) is the set of ordinals α such that φ has a model of order type α(ii) proof that bethω = sup{Sp(φ): φ local sentence with a bounded spectrum}(iii) existence of a local sentence φ such that Sp(φ) contains all infinite ordinals except the inaccessible cardinals.
Automorphism–invariant measures on ℵ0-categorical structures without the independence property
Authors: Ensley Douglas E. 
Published: May 2006

AbstractWe address the classification of the possible finitely-additive probability measures on the Boolean algebra of definable subsets of M which are invariant under the natural action of Aut(M). This pursuit requires a generalization of Shelah's forking formulas [8] to “essentially measure zero” sets and an application of Myer's “rank diagram” [5] of the Boolean algebra under consideration. The classification is completed for a large class of ℵ0-categorical structures without the independence property including those which are stable.
A modified sentence unprovable in PA
Authors: Gordeev L. 
Published: May 2006

H. Friedman proved that the following sentence SWQO() is true but not provable in the theory ATR0 (cf. [S]; ≔ the set of finite rooted trees, ∣T∣ ≔ the cardinality of T ∈ ).For every k > 0 there is an n so large that for any T0, T1,…, Tn ∈ with ∀i ≤ n(∣Ti∣ ≤ k · (i + 1)) there are i < j ≤ n such that Ti is homeomorphically embeddable into Tj.Since ATR0 is stronger than PA, SWQO() is not provable in PA, either. Furthermore, SWQO() is proof-theoretically stronger than PA. A similar sentence whose proof-theoretical strength is exactly that of PA was obtained by replacing finite trees by finite sequences of bounded natural numbers under the embeddability with H. Friedman's asymmetrical gap-condition (see [SS]). The latter sentence was modified by using the weaker symmetrical gap-condition (see the corresponding particular case in [Gl]). Further improvement is indicated in [G2, Corollary 4.5]. Namely, the assertion ∣Xi∣ ≤ k · (i + 1) as in SWQO(J), above, can be weakened to.(in fact, to wt(Xi) ≤ k + ε · i for an arbitrary fixed ε = l−1, l < 0, where wt(X) is the weight of the “word” X).
Generalized quantification as substructural logic
Authors: Alechina Natasha , Lambalgen Michiel Van 
Published: May 2006

AbstractWe show how sequent calculi for some generalized quantifiers can be obtained by generalizing the Herbrand approach to ordinary first order proof theory. Typical of the Herbrand approach, as compared to plain sequent calculus, is increased control over relations of dependence between variables. In the case of generalized quantifiers, explicit attention to relations of dependence becomes indispensible for setting up proof systems. It is shown that this can be done by turning variables into structured objects, governed by various types of structural rules. These structured variables are interpreted semantically by means of a dependence relation. This relation is an analogue of the accessibility relation in modal logic. We then isolate a class of axioms for generalized quantifiers which correspond to first-order conditions on the dependence relation.
Cauchy completeness in elementary logic
Authors: Cifuentes J. C. , Sette A. M. , Mundici D. 
Published: May 2006

AbstractThe inverse of the distance between two structures≢of finite typeτis naturally measured by the smallest integerqsuch that a sentence of quantifier rankq− 1 is satisfied bybut not by. In this way the space Strτof structures of typeτis equipped with a pseudometric. The induced topology coincides with the elementary topology of Strτ. Using the rudiments of the theory of uniform spaces, in this elementary note we prove the convergence of every Cauchy net of structures, for any typeτ.
Forcing isomorphism II
Authors: Laskowski M. C. , Shelah S. 
Published: May 2006

AbstractIf T has only countably many complete types, yet has a type of infinite multiplicity then there is a c.c.c. forcing notion such that, in any -generic extension of the universe, there are non-isomorphic models M1 and M2 of T that can be forced isomorphic by a c.c.c. forcing. We give examples showing that the hypothesis on the number of complete types is necessary and what happens if ‘c.c.c’ is replaced by other cardinal-preserving adjectives. We also give an example showing that membership in a pseudo-elementary class can be altered by very simple cardinal-preserving forcings.
Complete problems for fixed-point logics
Authors: Grohe Martin 
Published: May 2006

The notion of logical reducibilities is derived from the idea of interpretations between theories. It was used by Lovász and Gács [LG77] and Immerman [Imm87] to give complete problems for certain complexity classes and hence establish new connections between logical definability and computational complexity.However, the notion is also interesting in a purely logical context. For example, it is helpful to establish nonexpressibility results.We say that a class of τ-structures is a >complete problem for a logic under L-reductions if it is definable in [τ] and if every class definable in can be ”translated” into by L-formulae (cf. §4).We prove the following theorem:1.1. Theorem. There are complete problemsfor partial fixed-point logic andfor inductive fixed-point logic under quantifier-free reductions.The main step of the proof is to establish a new normal form for fixed-point formulae (which might be of some interest itself). To obtain this normal form we use theorems of Abiteboul and Vianu [AV91a] that show the equivalence between the fixed-point logics we consider and certain extensions of the database query language Datalog.In [Dah87] Dahlhaus gave a complete problem for least fixed-point logic. Since least fixed-point logic equals inductive fixed-point logic by a well-known result of Gurevich and Shelah [GS86], this already proves one part of our theorem.However, our class gives a natural description of the fixed-point process of an inductive fixed-point formula and hence sheds some light on completely different aspects of the logic than Dahlhaus's construction, which is strongly based on the features of least fixed-point formulae.
Possible behaviours of the reflection ordering of stationary sets
Authors: Witzany Jiří 
Published: May 2006

AbstractIf S, T are stationary subsets of a regular uncountable cardinal κ, we say that S reflects fully in T, S < T, if for almost all α ∈ T (except a nonstationary set) S ∩ α stationary in α. This relation is known to be a well-founded partial ordering. We say that a given poset P is realized by the reflection ordering if there is a maximal antichain 〈Xp: p ∈ P〉 of stationary subsets of Reg(κ) so thatWe prove that if , and P is an arbitrary well-founded poset of cardinality ≤ κ+ then there is a generic extension where P is realized by the reflection ordering on κ.
The syntax and semantics of entailment in duality theory
Authors: Davey B. A. , Haviar M. , Priestley H. A. 
Published: May 2006

AbstractBoth syntactic and semantic solutions are given for the entailment problem of duality theory. The test algebra theorem provides both a syntactic solution to the entailment problem in terms of primitive positive formula and a new derivation of the corresponding result in clone theory, viz. the syntactic description of Inv(Pol(R)) for a given set R of unitary relations on a finite set. The semantic solution to the entailment problem follows from the syntactic one, or can be given in the form of an algorithm. It shows, in the special case of a purely relational type, that duality-theoretic entailment is describable in terms of five constructs, namely trivial relations, intersection, repetition removal, product, and retractive projection. All except the last are concrete, in the sense that they are described by a quantifier-free formula. It is proved that if the finite algebra M generates a congruence-distributive variety and all subalgebras of M are subdirectly irreducible, then concrete constructs suffice to describe entailment. The concept of entailment appropriate to strong dualities is also introduced, and described in terms of coordinate projections, restriction of domains, and composition of partial functions.
A reflection principle and its applications to nonstandard models
Authors: Schmerl James H. 
Published: May 2006

Some methods of constructing nonstandard models work only for particular theories, such as ZFC, or CA + AC (which is second order number theory with the choice scheme). The examples of this which motivated the results of this paper occur in the main theorems of [5], which state that if T is any consistent extension of either ZFC0 (which is ZFC but with only countable replacement) or CA + AC and if κ and λ are suitably chosen cardinals, then T has a model which is κ-saturated and has the λ-Bolzano-Weierstrass property. (Compare with Theorem 3.5.) Another example is a result from [12] which states that if T is any consistent extension of CA + AC and cf (λ) > ℵ0, then T has a natural λ-Archimedean model. (Compare with Theorem 3.1 and the comments following it.) Still another example is a result in [6] in which it is shown that if a model of Peano arithmetic is expandable to a model of ZF or of CA, then so is any cofinal extension of . (Compare with Theorem 3.10.) Related types of constructions can also be found in [10] and [11].A reflection principle will be proved here, allowing these constructions to be extended to models of many other theories, among which are some exceedingly weak theories and also all of their completions.
The largest countable inductive set is a mouse set
Authors: Rudominer Mitch 
Published: May 2006

AbstractLet κℝ be the least ordinal κ such that Lκ (ℝ) is admissible. Let A = {x ϵ ℝ ∣ (∃α < κℝ) such that x is ordinal definable in Lα (ℝ)}. It is well known that (assuming determinacy) A is the largest countable inductive set of reals. Let T be the theory: ZFC − Replacement + “There exists ω Woodin cardinals which are cofinal in the ordinals.” T has consistency strength weaker than that of the theory ZFC + “There exists ω Woodin cardinals”, but stronger than that of the theory ZFC + “There exists n Woodin Cardinals”, for each n ϵ ω. Let M be the canonical, minimal inner model for the theory T. In this paper we show that A = ℝ ∩ M. Since M is a mouse, we say that A is a mouse set. As an application, we use our characterization of A to give an inner-model-theoretic proof of a theorem of Martin which states that for all n, every real is in A.
Interpolation and preservation for pebble logics
Authors: Baltag Alexandru 
Published: May 2006

In Barwise and van Benthem [6], the authors give a general method for obtaining interpolation and preservation theorems for fragments of L∞ω, those for which there is a co-inductive pebble game Γ characterizing equivalence in the logic. The method is exemplified by an analysis of the following fragments: L∞ω itself, its existential fragment , its positive fragment , the k-variable fragment (and its existential and positive subfragments) and the modal fragment (and its existential and positive subfragments).While most of their method is general, there is one part (showing that Γ has the Scott property relative to the fragment) that required a case-by-case analysis. The purpose of our paper is to replace this case-by-case analysis by a general theorem, and to illustrate this method by obtaining their kinds of results for some additional fragments of L∞ω.Our general problem can be stated in the following way: Given a “nice” fragment F of L∞ω (one satisfying some natural closure conditions), find a pebble game characterization Γ of “preservation of F-formulas” and prove that Γ has the Scott property with respect to F. Applying the Abstract Interpolation Theorem from [6], we can conclude that F has Γ-interpolation, and the corresponding preservation result. In this paper, we shall give an answer to this question. (Our answer is “sufficient” but we don't know if our conditions are necessary.)
Coordinatisation and canonical bases in simple theories
Authors: Hart Bradd , Kim Byunghan , Pillay Anand 
Published: May 2006

In this paper we discuss several generalization of theorems from stability theory to simple theories. Cherlin and Hrushovski, in [2] develop a substitute for canonical bases in finite rank, ω-categorical supersimple theories. Motivated by methods there, we prove the existence of canonical bases (in a suitable sense) for types in any simple theory. This is done in Section 2. In general these canonical bases will (as far as we know) exist only as “hyperimaginaries”, namely objects of the forma/Ewhereais a possibly infinite tuple andEa type-definable equivalence relation. (In the supersimple, ω-categorical case, these reduce to ordinary imaginaries.) So in Section 1 we develop the general theory of hyperimaginaries and show how first order model theory (including the theory of forking) generalises to hyperimaginaries. We go on, in Section 3 to show the existence and ubiquity of regular types in supersimple theories, ω-categorical simple structures and modularity is discussed in Section 4. It is also shown here how the general machinery of simplicity simplifies some of the general theory of smoothly approximable (or Lie-coordinatizable) structures from [2].Throughout this paper we will work in a large, saturated modelMof a complete theoryT. All types, sets and sequences will have size smaller than the size ofM. We will assume that the reader is familiar with the basics of forking in simple theories as laid out in [4] and [6]. For basic stability-theoretic results concerning regular types, orthogonality etc., see [1] or [9].
Paires élémentaires de corps pseudo-finis: dénombrement des complétions (Elementary pairs of pseudo-finite fields: counting completions)
Authors: Lejeune Hélène 
Published: May 2006

AbstractLet Π be a complete théorie of pseudo-finite fields. In this article we prove that, in the langage of fields to which we add a unary predicate for a substructure, the theory of non trivial elementary pairs of models of Π has completions, that is, the maximum that could exist.
A note on uniform definability and minimal fields of definition
Authors: Moosa Rahim 
Published: May 2006

Let k ⊂ K be a field extension, where K is an algebraically closed field of any characteristic and k is the prime field. Recall the following property of Hilbert Schemes (see, for example, [1], Proposition 1.16): Suppose ⊂ × S is a flat family of closed subschemes of parametrised by a scheme S/k. Then for every closed subscheme Z ⊂ in , if [Z] denotes the Hilbert point of Z in Hilb() then the residue field of Hilb() at [Z] is the minimal field of definition for Z. Intuitively, this says that as a family parametrised by Hilb(), each fibre of lies above a point whose “co-ordinates” generate its minimal field of definition.In the following note we are concerned with a more naive form of the above situation, for which we wish to give an elementary account. Suppose ϕ(x,y) is a system of polynomial equations over k (in variables x = (x1,…, xm) and parameters y = (y1, …, yn)), such thatis a family of (possibly reducible) affine varieties in Km. Each nonempty member of this family has a unique minimal field of definition. The question arises as to whether it is possible to express this family of varieties using parameters that come, pointwise, from these minimal fields of definition. That is, is there a system of polynomial equations ψ(x, z) over k, such that each ψ(x, b) with b ∈ KN is of the form Va for some a ∈ Kn; and such that each Va ∈ is defined by ψ(x, b) for some b ∈ KN whose coordinates generate the minimal field of definition for Va? Moreover, we would like b to be obtained definably from a.
Definability and undefinability with real order at the background
Authors: Gurevich Yuri , Rabinovich Alexander 
Published: May 2006

We consider the monadic second-order theory of linear order. For the sake of brevity, linearly ordered sets will be called chains.Let = ⟨A <⟩ be a chain. A formula ø(t) with one free individual variable t defines a point-set on A which contains the points of A that satisfy ø(t). As usually we identify a subset of A with its characteristic predicate and we will say that such a formula defines a predicate on A.A formula (X) one free monadic predicate variable defines the set of predicates (or family of point-sets) on A that satisfy (X). This family is said to be definable by (X) in A. Suppose that is a subchain of = ⟨B, <⟩. With a formula (X, A) we associate the following family of point-sets (or set of predicates) {P : P ⊆ A and (P, A) holds in } on A. This family is said to be definable by in with at the background.Note that in such a definition bound individual (respectively predicate) variables of range over B (respectively over subsets of B). Hence, it is reasonable to expect that the presence of a background chain allows one to define point sets (or families of point-sets) on A which are not definable inside .
There exist exactly two maximal strictly relevant extensions of the relevant logic R
Authors: Swirydowicz Kazimierz 
Published: May 2006

AbstractIn [60] N. Belnap presented an 8-element matrix for the relevant logic R with the following property: if in an implication A → B the formulas A and B do not have a common variable then there exists a valuation v such that v (A → B) does not belong to the set of designated elements of this matrix. A 6-element matrix of this kind can be found in: R. Routley, R.K. Meyer, V. Plumwood and R.T. Brady [82], Below we prove that the logics generated by these two matrices are the only maximal extensions of the relevant logic R which have the relevance property: if A → B is provable in such a logic then A and B have a common propositional variable.