bluuebunny/crossref_metadata_2025_split huggingface dataset:
Martin's axioms, measurability and equiconsistency results
Authors: Ihoda Jaime I. , Shelah Saharon 
Published: May 2006

AbstractWe deal with the consistency strength of ZFC + variants of MA + suitable sets of reals are measurable (and/or Baire, and/or Ramsey). We improve the theorem of Harrington and Shelah [2] repairing the asymmetry between measure and category, obtaining also the same result for Ramsey. We then prove parallel theorems with weaker versions of Martin's axiom (MA(σ-centered), (MA(σ-linked)), , MA(K)), getting Mahlo, inaccessible and weakly compact cardinals respectively. We prove that if there exists r ∈ R such that and MA holds, then there exists a -selective filter on ω, and from the consistency of ZFC we build a model for ZFC + MA(I) + every -set of reals is Lebesgue measurable, has the property of Baire and is Ramsey.
A construction of type: type in Martin-Löf's partial type theory with one universe
Authors: Palmgren Erik 
Published: May 2006

In this note we construct Martin-Löf's inconsistent type theory, Type: Type (Martin-Löf [1971]), inside partial type theory with one universe. Thus adding a fixed point operator to type theory with one predicative universe gives impredicativity.We may describe the theory Type:Type as follows. It contains the rules for the product construction (II) of Martin-Löf [1984] except the η-rule and it contains the usual rules for definitional equality (=). Moreover it contains the following strongly impredicative universeThis theory is inconsistent (i.e. every set is inhabited), and this is seen by proving a variant of the Burali—Forti paradox—Girard's paradox—cf. Troelstra and van Dalen [1988]. Coquand [199?] has shown that by adding the well-order type and the strong dependent sum to the universe, the fixed point operator becomes definable. It is an open problem whether it is definable without the well-order type. The present result could be seen as a converse, namely by adding the fixed point operator to type theory with one universe, Type:Type becomes definable and, as is already known, so does the well-order type.
Strong measure zero sets without Cohen reals
Authors: Goldstern Martin , Judah Haim , Shelah Saharon 
Published: May 2006

AbstractIf ZFC is consistent, then each of the following is consistent with :(1) X ⊆ ℝ is of strong measure zero iff ∣X∣ ≤ ℵ1 + there is a generalized Sierpinski set.(2) The union of ℵ many strong measure zero sets is a strong measure zero set + there is a strong measure zero set of size ℵ2 + there is no Cohen real over L.
Functions and functional on finite systems
Authors: Lo Libo 
Published: May 2006

The global function on finite systems is a new concept defined by Gurevich in [1] and discussed in [2] and [3]. In the last ten years this concept has become more and more useful in computer science and logic. Gurevich also pointed out the importance of global functionals on finite systems. In this paper we will give a brief introduction to the concepts of global functions and global functionals on finite systems.In studying the natural number system N = 〈N, +,0〉 we often refer to its functions and functionals. There are a lot of books and papers in this area. Kleene in [4] gave a detailed introduction to the recursive functions of N. The functionals of N are normally very difficult to compute because here we need to tell the machine what the input function is, which is not very easy to do. In developing the theory of finite systems the functions and functionals are also very useful. For computing the functionals in finite systems we can take the entire graph of a function as the input, which is not possible in N. We will discuss recursive functions and functionals for finite systems. The definitions of recursive functions are very similar to the case in N, but we will have a very different situation. In N the number of elements is infinite. The number of all possible functions from N to N is the continuum. In a finite system the number of all possible functions is finite. It seems that there is no necessity to define the global functions.
Lusin-Sierpiński index for the internal sets
Authors: Živaljević Boško 
Published: May 2006

AbstractWe prove that there exists a function f which reduces a given subset P of an internal set X of an ω1 saturated nonstandard universe to the set WF of well-founded trees possessing properties similar to those possessed by the standard part map. We use f to define the Lusin-Sierpiński index of points in X, and prove the basic properties of that index using the classical properties of the Lusin-Sierpiński index. An example of a but not set is given.
Modules with regular generic types part iv
Authors: Herzog Ivo , Rothmaler Philipp 
Published: May 2006

In this paper, we continue the line of investigation undertaken in [HR], with which we assume familiarity. For a comprehensive reference we refer the reader to [P]. The authors would like to thank each other for their light spirit and good humor.Pillay and Prest [PP, Proposition 7.10] have shown that a module M of U-rank 1 which is not totally transcendental may be decomposed as M = Ml ⊕ Mu, where Ml, ⊨ Th(M) omits the unlimited type and Mu imbeds purely into a model of the unlimited part Tu, of T = Th(M). We devote the first section of this paper to a generalization of this result to the case when T has a regular generic and m-dim(M) = 1. (Note that m-dim(M) = 0 implies M is totally transcendental, in which case a general decomposition theorem was proved by Garavaglia [G].)
Diagonals and -maximal sets
Authors: Herrmann Eberhard , Kummer Martin 
Published: May 2006

In analogy to the definition of the halting problem K, an r.e. set A is called a diagonal iff there is a computable numbering ψ of the class of all partial recursive functions such that A = {i ∈ ω: ψi(i)↓} (in that case we say that A is the diagonal of ψ). This notion has been introduced in [10]. It captures all r.e. sets that can be constructed by diagonalization.It was shown that any nonrecursive r.e. T-degree contains a diagonal, that for any diagonal A there is an r.e. nonrecursive nondiagonal B ≤TA, and that there are r.e. degrees a such that any r.e. set from a is a diagonal.In §2 of the present paper we show that the property “A is a diagonal” is elementary lattice theoretic (e.l.t.). This result complements and generalizes previous results of Harrington and Lachlan, respectively. Harrington (see [16, XV. 1]) proved that the property of being the diagonal of some Gödelnumbering (i.e., of being creative) is e.l.t., and Lachlan [12] proved that the property of being a simple diagonal (i.e., of being simple and not hh-simple [10]) is e.l.t.In §§3 and 4 we study the position of diagonals and nondiagonals inside the lattice of r.e. sets. We concentrate on an important class of nondiagonals, generalizing the maximal and hemimaximal sets: the -maximal sets. Using the results from [6] we are able to classify the -maximal sets that can be obtained as halfs of splittings of hh-simple sets.
Kolmogorov and mathematical logic
Authors: Uspensky Vladimir A. 
Published: May 2006

There are human beings whose intellectual power exceeds that of ordinary men. In my life, in my personal experience, there were three such men, and one of them was Andrei Nikolaevich Kolmogorov. I was lucky enough to be his immediate pupil. He invited me to be his pupil at the third year of my being student at the Moscow University. This talk is my tribute, my homage to my great teacher.Andrei Nikolaevich Kolmogorov was born on April 25, 1903. He graduated from Moscow University in 1925, finished his post-graduate education at the same University in 1929, and since then without any interruption worked at Moscow University till his death on October 20, 1987, at the age 84½.Kolmogorov was not only one of the greatest mathematicians of the twentieth century. By the width of his scientific interests and results he reminds one of the titans of the Renaissance. Indeed, he made prominent contributions to various fields from the theory of shooting to the theory of versification, from hydrodynamics to set theory. In this talk I should like to expound his contributions to mathematical logic.Here the term “mathematical logic” is understood in a broad sense. In this sense it, like Gallia in Caesarian times, is divided into three parts:(1) mathematical logic in the strict sense, i.e. the theory of formalized languages including deduction theory,(2) the foundations of mathematics, and(3) the theory of algorithms.
Descriptive set theory and harmonic analysis
Authors: Kechris A. S. , Louveau A. 
Published: May 2006

During the 1989 European ASL Summer Meeting in Berlin, the authors gave a series of eight lectures (short course) on the topic of the title. This survey article consists basically of the lecture notes for that course distributed to the participants of that conference. We have purposely tried in this printed version to preserve the informal style of the original notes.Let us say first a few things aboui the content of these lectures. Our aim has been to present some recent work in descriptive set theory and its applications to an area of harmonic analysis. Typical uses of descriptive set theory in analysis are most often through regularity properties of definable sets, like measurability, the property of Baire, capacitability, etc., which are used to show that certain problems have solutions that behave nicely. In the theory we will present, definability itself, in fact the precise analysis of the “definable complexity” of certain sets, will be the main concern. It will be through such knowledge that we will be able to infer important structural properties of various objects which will then be used to solve analysis problems.The first lecture provides a short historical introduction to the subject of uniqueness for trigonometric series, which is the area of harmonic analysis whose problems are the origin of this work. As is well known, it was Cantor who proved the first major result in this subject in 1870, and it was his subsequent work here that led him to the creation of set theory.
Cuts in hyperfinite time lines
Authors: Jin Renling 
Published: May 2006

AbstractIn an ω1-saturated nonstandard universe a cut is an initial segment of the hyperinlegers which is closed under addition. Keisler and Leth in [KL] introduced, for each given cut U, a corresponding U-topology on the hyperintegers by letting O be U-open if for any x ϵ O there is a y greater than all the elements in U such that the interval [x − y, x + y] ⊆ O. Let U be a cut in a hyperfinite time line , which is a hyperfinite initial segment of the hyperintegers. U is called a good cut if there exists a U-meager subset of of Loeb measure one. Otherwise U is bad. In this paper we discuss the questions of Keisler and Leth about the existence of bad cuts and related cuts. We show that assuming b > ω1, every hyperfinite time line has a cut with both cofinality and coinitiality uncountable. We construct bad cuts in a nonstandard universe under ZFC. We also give two results about the existence of other kinds of cuts.
Continuity properties in constructive mathematics
Authors: Ishihara Hajime 
Published: May 2006

AbstractThe purpose of this paper is an axiomatic study of the interrelations between certain continuity properties. We deal with principles which are equivalent to the statements “every mapping is sequentially nondiscontinuous”, “every sequentially nondiscontinuous mapping is sequentially continuous”, and “every sequentially continuous mapping is continuous”. As corollaries, we show that every mapping of a complete separable space is continuous in constructive recursive mathematics (the Kreisel-Lacombe-Schoenfield-Tsejtin theorem) and in intuitionism.
The density of the meet-inaccessible r. e. degrees
Authors: Qinglong Zhang 
Published: May 2006

AbstractIn this paper it is shown that the meet-inaccessible degrees are dense in R. The construction uses an 0′-priority argument. As a consequence, the meet-inaccessible degrees and the meet-accessible degrees give a partition of R into two sets, either of which is a nontrivial dense subset of R and generates R − {0} under joins (thus an automorphism base of R).
A sharp version of the bounded Matijasevich conjecture and the end-extension problem
Authors: Adamowicz Zofia 
Published: May 2006

Under a sharp version of the assumption I∆0 ⊢ ¬ ∆0H we characterize models of I∆0 + BΣ1 having a proper end extension to a model of I∆0.In [WP] Wilkie and Paris study the relationship between the existence of a proper end extension of a model and its “fullness”, which is related to a certain weak overspill principle (we recall the definition of fullness in §3). Let M be a countable nonstandard model of I∆0 + BΣ1. Under the hypothesis I∆0 ⊢ ¬ ∆0H they prove the following (Corollaries 7 and 8):The following are equivalent:1) M has a proper end extension to a model of I∆0 + BΣ1.2) M is (I∆0 + BΣ1)-full.Moreover, assuming that there is no t ∈ M such that for v ∈ M, 2[t/v]exists if and only if v < N, the following are equivalent:1) M has a proper end extension to a model of I∆0.2) M is I∆0-full.Wilkie and Paris ask whether the assumption on the structure of the model can be eliminated from the second equivalence.We eliminate it, but we sharpen the assumption I∆0 ⊢ ¬ ∆0H. So we partially answer their question.
Nonmonotonic consequence based on intuitionistic logic
Authors: Servi Gisèle Fischer 
Published: May 2006

Research in AI has recently begun to address the problems of nondeductive reasoning, i.e., the problems that arise when, on the basis of approximate or incomplete evidence, we form well-reasoned but possibly false judgments. Attempts to stimulate such reasoning fall into two main categories: the numerical approach is based on probabilities and the nonnumerical one tries to reconstruct nondeductive reasoning as a special type of deductive process. In this paper, we are concerned with the latter usually known as nonmonotonic deduction, because the set of theorems does not increase monotonically with the set of axioms.It is generally acknowledged that nonmonotonic (n.m.) formalisms (e.g., [C], [MC1], [MC2] [MD], [MD-D], [Rl], [R2], [S]) are plagued by a number of difficulties. A key issue concerns the fact that most systems do not produce an axiomatizable set of validities. Thus, the chief objective of this paper is to develop an alternative approach in which the set of n.m. inferences, which somehow qualify as being deductively sound, is r.e.The basic idea here is to reproduce the situation in First Order Logic where the metalogical concept of deduction translates into the logical notion of material implication. Since n.m. deductions are no longer truth preserving, our way to deal with a change in the metaconcept is to extend the standard logic apparatus so that it can reflect the new metaconcept. In other words, the intent is to study a concept of nonmonotonic implication that goes hand in hand with a notion of n.m. deduction. And in our case, it is convenient that the former be characterized within the more tractable context of monotonic logic.
There is no sharp transitivity on q6 when q is a type of Morley rank 2
Authors: Gropp Ursula 
Published: May 2006

In this paper we study transitive group actions.:G × X → X, definable in an ω-stable theory, where G is a connected group and X a set of Morley rank 2, with respect to sharp transitivity on qα. Here q is the generic type of X (X is of degree 1 by Proposition (1)), for ordinals α > 0, qα is the αth power of q, i.e. (aβ)β < α, ⊨ qα iff (aβ)β < α is an independent sequence (in the sense of forking) of realizations of q, and G is defined to be sharply transitive on qα iff for all (aβ)β < α, (bβ)β < α ⊨ qα there is one and only one g ∈ G with g.aβ = bβ for all β < α. The question studied here is: For which powers α of q are there group actions subject to the above conditions with G sharply transitive on qα?In §1 we will see that for group actions satisfying the above conditions, G can be sharply transitive only on finite powers of q. Moreover, if G is sharply transitive on qn for some n ≥ 2, then the action of the stabilizer Ga on a certain subset Y of X satisfies the conditions above with Ga being sharply transitive on qm−1, where q′ is the generic type of Y (Proposition (8)). Thus, there would be a complete answer to the question if one could find some n < ω such that there is no group action as above with G sharply transitive on qn, but for n – 1 there is. In this paper we prove that such n exists and that it is either 5 or 6. More precisely, in §2 we prove that there is no group action satisfying the above conditions with G sharply transitive on q6. This is the main result of this paper. It is not known to the author whether the same also holds for q5 instead of q6. However, it does not hold for q4, as is seen in §3. There we give an example provided from projective geometry, for a group action satisfying the above conditions with G sharply transitive on q4; for G we choose PGL(3, K) and for X the projective plane over K, where K is some algebraically closed field.
Full reflection at a measurable cardinal
Authors: Jech Thomas , Witzany Jiří 
Published: May 2006

AbstractA stationary subset S of a regular uncountable cardinal κreflects fully at regular cardinals if for every stationary set T ⊆ κ of higher order consisting of regular cardinals there exists an α Є T such that S ∩ α is a stationary subset of α. Full Reflection states that every stationary set reflects fully at regular cardinals. We will prove that under a slightly weaker assumption than κ having the Mitchell order κ++ it is consistent that Full Reflection holds at every λ ≤ κ and κ is measurable.
Nonexistence of universal orders in many cardinals
Authors: Kojman Menachem , Shelah Saharon 
Published: May 2006

AbstractOur theme is that not every interesting question in set theory is independent of ZFC. We give an example of a first order theoryTwith countableD(T)which cannot have a universal model at ℵ1; without CH; we prove in ZFC a covering theorem from the hypothesis of the existence of a universal model for some theory; and we prove—again in ZFC—that for a large class of cardinals there is no universal linear order (e.g. in every regular). In fact, what we show is that if there is a universal linear order at a regularλand its existence is not a result of a trivial cardinal arithmetical reason, thenλ“resembles” ℵ1—a cardinal for which the consistency of having a universal order is known. As for singular cardinals, we show that for many singular cardinals, if they are not strong limits then they have no universal linear order. As a result of the nonexistence of a universal linear order, we show the nonexistence of universal models for all theories possessing the strict order property (for example, ordered fields and groups, Boolean algebras,p-adic rings and fields, partial orders, models of PA and so on).
A characterization of ML in many-sorted arithmetic with conditional application
Authors: Swaen M. D. G. 
Published: May 2006

AbstractIn this paper we discuss an interpretation of intuitionistic type theory in many-sorted arithmetic with so-called conditional application. Via the formulas-as-types correspondence the arithmetical system in turn can be embedded inML, resulting in a characterization of strong Σ-elimination by an axiom of conditional choice.
A theorem on the isomorphism property
Authors: Jin Renling 
Published: May 2006

AbstractAn -structure is called internally presented in a nonstandard universe if its base set and interpretation of every symbol in are internal. A nonstandard universe is said to satisfy the κ-isomorphism property if for any two internally presented -structures and , where has less than κ many symbols, is elementarily equivalent to implies that is isomorphic to . In this paper we prove that the ℵ1-isomorphism property is equivalent to the ℵ0-isomorphism property plus ℵ1-saturation.
Delineating classes of computational complexity via second order theories with weak set existence principles. I
Authors: Ignjatović Aleksandar 
Published: May 2006

AbstractIn this paper we characterize the well-known computational complexity classes of the polynomial time hierarchy as classes of provably recursive functions (with graphs of suitable bounded complexity) of some second order theories with weak comprehension axiom schemas but without any induction schemas (Theorem 6). We also find a natural relationship between our theories and the theories of bounded arithmetic (Lemmas 4 and 5). Our proofs use a technique which enables us to “speed up” induction without increasing the bounded complexity of the induction formulas. This technique is also used to obtain an interpretability result for the theories of bounded arithmetic (Theorem 4).
The dense linear ordering principle
Authors: Pincus David 
Published: May 2006

AbstractLet DO denote the principle: Every infinite set has a dense linear ordering. DO is compared to other ordering principles such as O, the Linear Ordering principle, KW, the Kinna-Wagner Principle, and PI, the Prime Ideal Theorem, in ZF, Zermelo-Fraenkel set theory without AC, the Axiom of Choice.The main result is:Theorem. AC ⇒ KW ⇒ DO ⇒ O, and none of the implications is reversible in ZF + PI.The first and third implications and their irreversibilities were known. The middle one is new. Along the way other results of interest are established. O, while not quite implying DO, does imply that every set differs finitely from a densely ordered set. The independence result for ZF is reduced to one for Fraenkel-Mostowski models by showing that DO falls into two of the known classes of statements automatically transferable from Fraenkel-Mostowski to ZF models. Finally, the proof of PI in the Fraenkel-Mostowski model leads naturally to versions of the Ramsey and Ehrenfeucht-Mostowski theorems involving sets that are both ordered and colored.
Undefinability of κ-well-orderings in L∞κ
Authors: Oikkonen Juha 
Published: May 2006

AbstractWe prove that the class of trees with no branches of cardinality ≤ κ is not RPC definable in L∞κ when κ is regular. Earlier such a result was known for under the assumption κ<κ = κ. Our main result is actually proved in a stronger form which covers also L∞κ (and makes sense there) for every strong limit cardinal λ < κ of cofinality κ.
Contiguity and distributivity in the enumerable Turing degrees
Authors: Downey Rodney G. , Lempp Steffen 
Published: May 2006

AbstractWe prove that a (recursively) enumerable degree is contiguous iff it is locally distributive. This settles a twenty-year old question going back to Ladner and Sasso. We also prove that strong contiguity and contiguity coincide, settling a question of the first author, and prove that no m-topped degree is contiguous, settling a question of the first author and Carl Jockusch [11]. Finally, we prove some results concerning local distributivity and relativized weak truth table reducibility.
Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem
Authors: Bès Alexis 
Published: May 2006

AbstractLetkandlbe two multiplicatively independent integers, and letL⊆ ℕnbe al-recognizable set which is not definable in 〈ℕ; +〉. We prove that the elementary theory of 〈ℕ; +,Vk, L〉, whereVk(x)denotes the greatest power ofkdividingx, is undecidable. This result leads to a new proof of the Cobham-Semënov theorem.