bluuebunny/crossref_metadata_2025_split huggingface dataset:
The Kunen-Miller chart (Lebesgue measure, the Baire property, Laver reals and preservation theorems for forcing)
Authors: Judah Haim , Shelah Saharon 
Published: May 2006

AbstractIn this work we give a complete answer as to the possible implications between some natural properties of Lebesgue measure and the Baire property. For this we prove general preservation theorems for forcing notions. Thus we answer a decade-old problem of J. Baumgartner and answer the last three open questions of the Kunen-Miller chart about measure and category. Explicitly, in §1: (i) We prove that if we add a Laver real, then the old reals have outer measure one. (ii) We prove a preservation theorem for countable-support forcing notions, and using this theorem we prove (iii) If we add ω2 Laver reals, then the old reals have outer measure one. From this we obtain (iv) Cons(ZF) ⇒ Cons(ZFC + ¬ B(m) + ¬ U(m) + U(c)). In §2: (i) We prove a preservation theorem, for the finite support forcing notion, of the property “F ⊆ ωω is an unbounded family.” (ii) We introduce a new forcing notion making the old reals a meager set but the old members of ωω remain an unbounded family. Using this we prove (iii) Cons(ZF) ⇒ Cons(ZFC + U(m) + ¬ B(c) + ¬ U(c) + C(c)). In §3: (i) We prove a preservation theorem, for the finite support forcing notion, of a property which implies “the union of the old measure zero sets is not a measure zero set,” and using this theorem we prove (ii) Cons(ZF) ⇒ Cons(ZFC + ¬U(m) + C(m) + ¬ C(c)).
Finite Kripke models and predicate logics of provability
Authors: Artemov Sergei , Dzhaparidze Giorgie 
Published: May 2006

AbstractThe paper proves a predicate version of Solovay's well-known theorem on provability interpretations of modal logic:If a closed modal predicate-logical formula R is not valid in some finite Kripke model, then there exists an arithmetical interpretation f such that PA ⊬ fR.This result implies the arithmetical completeness of arithmetically correct modal predicate logics with the finite model property (including the one-variable fragments of QGL and QS). The proof was obtained by adding “the predicate part” as a specific addition to the standard Solovay construction.
Upward directedness of the Rudin-Keisler ordering of p-points
Authors: Laflamme Claude 
Published: May 2006

It has been proven by Blass [1973] that any two P-points which have a P-point as a common upper bound in the Rudin-Keisler (RK) ordering necessarily have a common lower bound (necessarily a P-point). Hence two nonisomorphic Ramsey ultrafilters have neither a common lower nor a common upper bound which is a P-point. So in a model of CH for example (or MA, P(c),…), the RK ordering restricted to P-points is neither upward nor downward directed, since it is well known that nonisomorphic Ramsey ultrafilters exist in such models. On the other hand, we will see that in the model for “near coherence of filters” (NCF) produced by Blass and Shelah [1985], the RK ordering of P-points is upward, hence downward directed. This shows that the question of directedness of the RK ordering of P-points, upward or downward, cannot be decided in ZFC.There is a related question, asked by Blass in [1973], whether two P-points which have a common lower bound necessarily have a common upper bound which is a P-point. Our main result establishes the independence of this statement relative to ZFC. Its consistency will follow as soon as we show that the RK ordering of P-points is upward directed in the NCF model mentioned above, which we do in §2. But its independence will require a new construction, and will be given in §3.
The ordertype of β-R.E. sets
Authors: Sutner Klaus 
Published: May 2006

AbstractLet β be an arbitrary limit ordinal. A β-r.e. set is l-finite iff all its β-r.e. subsets are β-recursive. The l-finite sets correspond to the ideal of finite sets in the lattice of r.e. sets. We give a characterization of l-finite sets in terms of their ordertype: a β-r.e. set is l-finite iff it has ordertype less than β*, the Σ1, projectum of β).
An axiomatization of the logic with the rough quantifier
Authors: Krynicki Michał , Tuschik Hans-Peter 
Published: May 2006

We consider the language L(Q), where L is a countable first-order language and Q is an additional generalized quantifier. A weak model for L(Q) is a pair 〈, q〉 where is a first-order structure for L and q is a family of subsets of its universe. In case that q is the set of classes of some equivalence relation the weak model 〈, q〉 is called a partition model. The interpretation of Q in partition models was studied by Szczerba [3], who was inspired by Pawlak's paper [2]. The corresponding set of tautologies in L(Q) is called rough logic. In the following we will give a set of axioms of rough logic and prove its completeness. Rough logic is designed for creating partition models.The partition models are the weak models arising from equivalence relations. For the basic properties of the logic of weak models the reader is referred to Keisler's paper [1]. In a weak model 〈, q〉 the formulas of L(Q) are interpreted as usual with the additional clause for the quantifier Q: 〈, q〉 ⊨ Qx φ(x) iff there is some X ∊ q such that 〈, q〉 ⊨ φ(a) for all a ∊ X.In case X satisfies the right side of the above equivalence we say that X is contained in φ(x) or, equivalently, φ(x) contains X.
Natural 3-valued logics—characterization and proof theory
Authors: Avron Arnon 
Published: May 2006

Many-valued logics in general and 3-valued logic in particular is an old subject which had its beginning in the work of Łukasiewicz [Łuk]. Recently there is a revived interest in this topic, both for its own sake (see, for example, [Ho]), and also because of its potential applications in several areas of computer science, such as proving correctness of programs [Jo], knowledge bases [CP] and artificial intelligence [Tu]. There are, however, a huge number of 3-valued systems which logicians have studied throughout the years. The motivation behind them and their properties are not always clear, and their proof theory is frequently not well developed. This state of affairs makes both the use of 3-valued logics and doing fruitful research on them rather difficult.Our first goal in this work is, accordingly, to identify and characterize a class of 3-valued logics which might be called natural. For this we use the general framework for characterizing and investigating logics which we have developed in [Av1]. Not many 3-valued logics appear as natural within this framework, but it turns out that those that do include some of the best known ones. These include the 3-valued logics of Łukasiewicz, Kleene and Sobociński, the logic LPF used in the VDM project, the logic RM3 from the relevance family and the paraconsistent 3-valued logic of [dCA]. Our presentation provides justifications for the introduction of certain connectives in these logics which are often regarded as ad hoc. It also shows that they are all closely related to each other. It is shown, for example, that Łukasiewicz 3-valued logic and RM3 (the strongest logic in the family of relevance logics) are in a strong sense dual to each other, and that both are derivable by the same general construction from, respectively, Kleene 3-valued logic and the 3-valued paraconsistent logic.
A proof of Beigel's cardinality conjecture
Authors: Kummer Martin 
Published: May 2006

In 1986, Beigel [Be87] (see also [Od89, III.5.9]) proved the nonspeedup theorem: if A, B ⊆ ω, and as a function of 2n variables can be computed by an algorithm which makes at most n queries to B, then A is recursive (informally, 2n parallel queries to a nonrecursive oracle A cannot be answered by making n sequential (or “adaptive”) queries to an arbitrary oracle B). Here, 2n cannot be replaced by 2n − 1. In subsequent papers of Beigel, Gasarch, Gill, Hay, and Owings the theory of “bounded query classes” has been further developed (see, for example, [BGGOta], [BGH89], and [Ow89]). The topic has also been studied in the context of structural complexity theory (see, for example, [AG88], [Be90], and [JY90]).If A ⊆ ω and n ≥ 1, let . Beigel [Be87] stated the powerful “cardinality conjecture” (CC): if A, B ⊆ ω, and can be computed by an algorithm which makes at most n queries to B, then A is recursive. Owings [Ow89] verified CC for n = 1, and, for n 1, he proved that A is recursive in the halting problem. We prove that CC is true for all n.
Ramsey sets, the Ramsey ideal, and other classes overR
Authors: Corazza Paul 
Published: May 2006

AbstractWe improve results of Marczewski, Frankiewicz, Brown, and others comparing theω-ideals of measure zero, meager, Marczewski measure zero, and completely Ramsey null sets; in particular, we remove CH from the hypothesis of many of Brown's constructions of sets lying in some of these ideals but not in others. We improve upon work of Marczewski by constructing, without CH, a nonmeasurable Marczewski measure zero set lacking the property of Baire. We extend our analysis ofω-ideals to include the completely Ramsey null sets relative to a Ramsey ultrafilter and obtain all 32 possible examples of sets in some ideals and not others, some under the assumption of MA, but most in ZFC alone. We also improve upon the known constructions of a Marczewski measure zero set which is not Ramsey by using a set theoretic hypothesis which is weaker than those used by other authors. We give several consistency proofs: one concerning the relative sizes of the covering numbers for the meager sets and the completely Ramsey null sets; another concerning the size of non; and a third concerning the size of add. We also study those classes of perfect sets which are bases for the class of always first category sets.
Dual easy uniformization and model-theoretic descriptive set theory
Authors: Lavine Shaughan 
Published: May 2006

AbstractIt is well known that, in the terminology of Moschovakis, Descriptive set theory (1980), every adequate normed pointclass closed under ∀ω has an effective version of the generalized reduction property (GRP) called the easy uniformization property (EUP). We prove a dual result: every adequate normed pointclass closed under ∃ω has the EUP. Moschovakis was concerned with the descriptive set theory of subsets of Polish topological spaces. We set up a general framework for parts of descriptive set theory and prove results that have as special cases not only the just-mentioned topological results, but also corresponding results concerning the descriptive set theory of classes of classes of structures.Vaught (1973) asked whether the class of cPCδ classes of countable structures has the GRP. It does. A cPC(A) class is the class of all models of a sentence of the form , where ϕ is a sentence of ℒ∞ω that is in A and is a set of relation symbols that is in A. Vaught also asked whether there is any primitive recursively closed set A such that some effective version of the GRP holds for the class of cPC(A) classes of countable structures. There is: The class of cPC(A) classes of countable structures has the EUP if ω ∈ A and A is countable and primitive recursively closed. Those results and some extensions are obtained by first showing that the relevant classes of classes of structures, which Vaught showed normed, are in a suitable sense adequate and closed under ∃ω, and then applying the dual easy uniformization theorem.
The bounded proper forcing axiom
Authors: Goldstern Martin , Shelah Saharon 
Published: May 2006

AbstractThe bounded proper forcing axiom BPFA is the statement that for any family of ℵ1 many maximal antichains of a proper forcing notion, each of size ℵ1, there is a directed set meeting all these antichains.A regular cardinal κ is called ∑1-reflecting, if for any regular cardinal χ, for all formulas φ, “H(χ) ⊨ ‘φ’” implies “∃δ < κ, H(δ) ⊨ ‘φ’”.We investigate several algebraic consequences of BPFA, and we show that the consistency strength of the bounded proper forcing axiom is exactly the existence of a ∑1-reflecting cardinal (which is less than the existence of a Mahlo cardinal).We also show that the question of the existence of isomorphisms between two structures can be reduced to the question of rigidity of a structure.
T-convexity and tame extensions
Authors: van den Dries Lou , Lewenberg Adam H. 
Published: May 2006

AbstractLet T be a complete o-minimal extension of the theory of real closed fields. We characterize the convex hulls of elementary substructures of models of T and show that the residue field of such a convex hull has a natural expansion to a model of T. We give a quantifier elimination relative to T for the theory of pairs (ℛ, V) where ℛ ⊨ T and V ≠ ℛ is the convex hull of an elementary substructure of ℛ. We deduce that the theory of such pairs is complete and weakly o-minimal. We also give a quantifier elimination relative to T for the theory of pairs with ℛ a model of T and a proper elementary substructure that is Dedekind complete in ℛ. We deduce that the theory of such “tame” pairs is complete.
Hereditarily structurally complete modal logics
Authors: Rybakov V. V. 
Published: May 2006

AbstractWe consider structural completeness in modal logics. The main result is the necessary and sufficient condition for modal logics over K4 to be hereditarily structurally complete: a modal logic λ is hereditarily structurally complete iff λ is not included in any logic from the list of twenty special tabular logics. Hence there are exactly twenty maximal structurally incomplete modal logics above K4 and they are all tabular.
Generalized nonsplitting in the recursively enumerable degrees
Authors: Leonhardi Steven D. 
Published: May 2006

AbstractWe investigate the algebraic structure of the upper semi-lattice formed by the recursively enumerable Turing degrees. The following strong generalization of Lachlan's Nonsplitting Theorem is proved: Given n ≥ 1, there exists an r.e. degree d such that the interval [d, 0′] ⊂ R admits an embedding of the n-atom Boolean algebra preserving (least and) greatest element, but also such that there is no (n + 1 )-tuple of pairwise incomparable r.e. degrees above d which pairwise join to 0′ (and hence, the interval [d, 0′] ⊂ R does not admit a greatest-element-preserving embedding of any lattice which has n + 1 co-atoms, including ). This theorem is the dual of a theorem of Ambos-Spies and Soare, and yields an alternative proof of their result that the theory of R has infinitely many one-types.
Reflecting in epistemic arithmetic
Authors: Horsten Leon 
Published: May 2006

AbstractAn epistemic formalization of arithmetic is constructed in which certain non-trivial metatheoretical inferences about the system itself can be made. These inferences involve the notion of provability in principle, and cannot be made in any consistent extensions of Stewart Shapiro's system of epistemic arithmetic. The system constructed in the paper can be given a modal-structural interpretation
Countable models of trivial theories which admit finite coding
Authors: Loveys James , Tanović Predrag 
Published: May 2006

AbstractWe prove:Theorem. A complete first order theory in a countable language which is strictly stable, trivial and which admits finite coding hasnonisomorphic countable models.Combined with the corresponding result or superstable theories from [4] our result confirms the Vaught conjecture for trivial theories which admit finite coding.
Covering analytic sets by families of closed set
Authors: Solecki Sławomir 
Published: May 2006

AbstractWe prove that for every familyIof closed subsets of a Polish space eachset can be covered by countably many members ofIor else contains a nonemptyset which cannot be covered by countably many members ofI. We prove an analogous result forκ-Souslin sets and show that ifA#exists for anyA⊂ωω, then the above result is true forsets. A theorem of Martin is included stating that this result is also true for weakly homogeneously Souslin sets. As an application of our results we derive from them a general form of Hurewicz's theorem due to Kechris. Louveau, and Woodin and a theorem of Feng on the open covering axiom. Also some well-known theorems on finding “big” closed sets insideof“big”andare consequences of our results.
Anti-admissible sets
Authors: Lurie Jacob 
Published: May 2006

AbstractAczel's theory of hypersets provides an interesting alternative to the standard view of sets as inductively constructed, well-founded objects, thus providing a convienent formalism in which to consider non-well-founded versions of classically well-founded constructions, such as the “circular logic” of [3], This theory and ZFC are mutually interpretable; in particular, any model of ZFC has a canonical “extension” to a non-well-founded universe. The construction of this model does not immediately generalize to weaker set theories such as the theory of admissible sets. In this paper, we formulate a version of Aczel's antifoundation axiom suitable for the theory of admissible sets. We investigate the properties of models of the axiom system KPU−, that is, KPU with foundation replaced by an appropriate strengthening of the extensionality axiom. Finally, we forge connections between “non-wellfounded sets over the admissible set A” and the fragment LA of the modal language L∞.
Explicit mathematics with the monotone fixed point principle. II: Models
Authors: Rathjen Michael 
Published: May 2006

AbstractThis paper continues investigations of the monotone fixed point principle in the context of Feferman's explicit mathematics begun in [14]. Explicit mathematics is a versatile formal framework for representing Bishop-style constructive mathematics and generalized recursion theory. The object of investigation here is the theory of explicit mathematics augmented by the monotone fixed point principle, which asserts that any monotone operation on classifications (Feferman's notion of set) possesses a least fixed point. To be more precise, the new axiom not merely postulates the existence of a least solution, but, by adjoining a new constant to the language, it is ensured that a fixed point is uniformly presentable as a function of the monotone operation. Let T0 + UMID denote this extension of explicit mathematics. [14] gave lower bounds for the strength of two subtheories of To + UMID in relating them to fragments of second order arithmetic based on comprehension. [14] showed that To ↾ + UMID and To ↾ + INDk + UMID have at least the strength of ( – CA), and ↾ and – CA), respectively.Here we are concerned with the exact reversals. Let UMIDN be the monotone fixed-point principle for subclassifications of the natural numbers. Among other results, it is shown that To ↾ + UMIDN and To ↾ + INDN + UMIDN have the same strength as ( – CA) ↾ and ( – CA), respectively.The results are achieved by constructing set-theoretic models for the aforementioned systems of explicit mathematics in certain extensions of Kripke-Platek set theory and subsequently relating these set theories to subsystems of second arithmetic.
The anatytic conception of truth and the foundations of arithmetic
Authors: Apostoli Peter 
Published: May 2006

Until very recently, it was thought that there couldn't be anycurrentinterest in logicism as a philosophy of mathematics. Indeed, there is an old argument one often finds that logicism is a simple nonstarter just in virtue of the fact that if it were a logical truth that there are infinitely many natural numbers, then this would be in conflict with the existence of finite models. It is certainly true that from the perspective of model theory, arithmetic cannot be a part of logic. However, it is equally true that model theory's reliance on a background of axiomatic set theory renders it unable to match Frege's Theorem, the derivation within second order logic of the infinity of the number series from the contextual “definition” of the cardinality operator. Called “Hume's Principle” by Boolos, the contextual definition of the cardinality operator is presented in Section 63 ofGrundlagen, as the statement that, for any conceptsFandG,the number ofFs = the number ofGsif, and only if,Fis equinumerous withG.The philosophical interest in Frege's Theorem derives from the thesis, defended for example by Crispin Wright, that Hume's principle expresses our pre-analytic conception of assertions of numerical identity. However, Boolos cites the very fact that Hume's principle has only infinite models as grounds for denying that it is logically true: For Boolos, Hume's principle is simply a disguised axiom of infinity.
Two consistency results on set mappings
Authors: Komjáth Péter , Shelah Saharon 
Published: May 2006

AbstractIt is consistent that there is a set mapping from the four-tuples of ωninto the finite subsets with no free subsets of sizetnfor some natural numbertn. For anyn< ω it is consistent that there is a set mapping from the pairs of ωninto the finite subsets with no infinite free sets. For anyn< ω it is consistent that there is a set mapping from the pairs of ωninto ωnwith no uncountable free sets.
Toward a constructive theory of unbounded linear operators
Authors: Ye Feng 
Published: May 2006

AbstractWe show that the following results in the classical theory of unbounded linear operators on Hilbert spaces can be proved within the framework of Bishop's constructive mathematics: the Kato-Rellich theorem, the spectral theorem. Stone's theorem, and the self-adjointness of the most common quantum mechanical operators, including the Hamiltonians of electro-magnetic fields with some general forms of potentials.
On recursive enumerability with finite repetitions
Authors: Wehner Stephan 
Published: May 2006

AbstractIt is an open problem within the study of recursively enumerable classes of recursively enumerable sets to characterize those recursively enumerable classes which can be recursively enumerated without repetitions. This paper is concerned with a weaker property of r.e. classes, namely that of being recursively enumerable with at most finite repetitions.This property is shown to behave more naturally: First we prove an extension theorem for classes satisfying this property. Then the analogous theorem for the property of recursively enumerable classes of being recursively enumerable with a bounded number of repetitions is shown not to hold. The index set of the property of recursively enumerable classes “having an enumeration with finite repetitions” is shown to be -complete.
Relative constructivity
Authors: Kohlenbach Ulrich 
Published: May 2006

In a previous paper [13] we introduced a hierarchy (GnAω)n∈ℕ of subsystems of classical arithmetic in all finite types where the growth of definable functions of GnAω corresponds to the well-known Grzegorczyk hierarchy. Let AC-qf denote the schema of quantifier-free choice.[11], [13], [8] and [7] study various analytical principles Γ in the context of the theories GnAω + AC-qf (mainly for n = 2) and use proof-theoretic tools like, e.g., monotone functional interpretation (which was introduced in [12]) to determine their impact on the growth of uniform bounds Φ such thatwhich are extractable from given proofs (based on these principles Γ) of sentencesHere A0(u, k, v, w) is quantifier-free and contains only u, k, v, w as free variables; t is a closed term and ≤p is defined pointwise. The term ‘uniform bound’ refers to the fact that Φ does not depend on v ≤ptuk (see [12] for the relevance of such uniform bounds in numerical analysis and for concrete applications to approximation theory).