Search

Frege’s Grundgesetze was one of the 19th century forerunners to contemporary set theory which was plagued by the Russell paradox. In recent years, it has been shown that subsystems of the Grundgesetze formed by restricting the comprehension schema are consistent. One aim of this paper is to ascertain how much set theory can be developed within these consistent fragments of the Grundgesetze, and our main theorem (Theorem 2.9) shows that there is a model of a fragment of the Grundgesetze which defines a model of all the axioms of Zermelo–Fraenkel set theory with the exception of the power set axiom. The proof of this result appeals to Gödel’s constructible universe of sets and to Kripke and Platek’s idea of the projectum, as well as to a weak version of uniformization (which does not involve knowledge of Jensen’s fine structure theory). The axioms of the Grundgesetze are examples of abstraction principles, and the other primary aim of this paper is to articulate a sufficient condition for the consistency of abstraction principles with limited amounts of comprehension (Theorem 3.5). As an application, we resolve an analogue of the joint consistency problem in the predicative setting. [ABSTRACT FROM PUBLISHER]

In his book on Pmax [7], Woodin presents a collection of partial orders whose extensions satisfy strong club guessing principles on ω1. In this paper we employ one of the techniques from this book to produce Pmax variations which separate various club guessing principles. The principle (+) and its variants are weak guessing principles which were first considered by the second author [4] while studying games of length ω1. It was shown in [1] that the Continuum Hypothesis does not imply (+) and that (+) does not imply the existence of a club guessing sequence on ω1. In this paper we give an alternate proof of the second of these results, using Woodin's Pmax technology, showing that a strengthening of (+) does not imply a weakening of club guessing known as the Interval Hitting Principle. The main technique in this paper, in addition to the standard Pmax machinery, is the use of condensation principles to build suitable iterations. [ABSTRACT FROM AUTHOR]

After showing the downwards density of nonhemimaximal degrees, Downey and Stob continued to prove that the existence of a low2, but not low, nonhemimaximal degree, and their proof uses the fact that incomplete m-topped degrees are low2 but not low. As commented in their paper, the construction of such a nonhemimaximal degree is actually a primitive 0'" argument. In this paper, we give another construction of such degrees, which is a standard 0"-argument, much simpler than Downey and Stob's construction mentioned above. [ABSTRACT FROM AUTHOR]

In this paper we deal with the model theory of differentially closed fields of characteristic zero with finitely many commuting derivations. First we observe that the only known lower bound for the Lascar rank of types in differentially closed fields, announced in a paper of McGrail, is false. This gives us a new class of regular types which are orthogonal to fields. Then we classify the subgroups of the additive group of Lascar rank omega with differential-type 1 which are nonorthogonal to fields. The last parts consist of an analaysis of the quotients of the heat variety. We show that the generic type of such a quotient is locally modular. Finally, we answer a question of Phylliss Cassidy about the existence of certain Jordan-Hölder type series in the negative. [ABSTRACT FROM AUTHOR]

Theories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders. for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out a sequence of examples. We follow recent work by Goncharov and Knight in using the degree of the isomorphism problem for a class to distinguish classifiable classes from non-classifiable. In this paper, we calculate the degree of the isomorphism problem for Abelian p-groups of bounded Ulm length. The result is a sequence of classes whose isomorphism problems are cofinal in the hyperarithmetical hierarchy. In the process, new back-and-forth relations on such groups are calculated. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to present an algebraic generalization of the traditional two- valued logic. This involves introducing a theory of automorphism algebras, which is an algebraic theory of many-valued logic having a complete lattice as the set of truth values. Two generalizations of the two-valued case will be considered, viz., the finite chain and the Boolean lattice. In the case of the Boolean lattice, on choosing a designated lattice value, this algebra has binary retracts that have the usual axiomatic theory of the propositional calculus as suitable theory. This suitability applies to the Boolean algebra of formalized token models [2] where the truth values are, for example, vocabularies. Finally, as the actual motivation for this paper, we indicate how the theory of formalized token models [2] is an example of a many-valued predicate calculus. [ABSTRACT FROM AUTHOR]

In [8], the third author defined a reducibility $\le _w^{\rm{*}}$ that lets us compare the computing power of structures of any cardinality. In [6], the first two authors showed that the ordered field of reals ${\cal R}$ lies strictly above certain related structures. In the present paper, we show that $\left( {{\cal R},exp} \right) \equiv _w^{\rm{*}}{\cal R}$. More generally, for the weak-looking structure ${\cal R}$ℚ consisting of the real numbers with just the ordering and constants naming the rationals, all o-minimal expansions of ${\cal R}$ℚ are equivalent to ${\cal R}$. Using this, we show that for any analytic function f, $\left( {{\cal R},f} \right) \equiv _w^{\rm{*}}{\cal R}$. (This is so even if $\left( {{\cal R},f} \right)$ is not o-minimal.) [ABSTRACT FROM PUBLISHER]

The paper proves a conjecture of Solomon Feferman concerning the indefiniteness of the continuum hypothesis relative to a semi-intuitionistic set theory. [ABSTRACT FROM PUBLISHER]

Let E be a computably enumerable (c.e.) equivalence relation on the set ω of natural numbers. We say that the quotient set $\omega /E$ (or equivalently, the relation E) realizes a linearly ordered set ${\cal L}$ if there exists a c.e. relation ⊴ respecting E such that the induced structure ($\omega /E$; ⊴) is isomorphic to ${\cal L}$. Thus, one can consider the class of all linearly ordered sets that are realized by $\omega /E$; formally, ${\cal K}\left( E \right) = \left\{ {{\cal L}\,|\,{\rm{the}}\,{\rm{order}}\, - \,{\rm{type}}\,{\cal L}\,{\rm{is}}\,{\rm{realized}}\,{\rm{by}}\,E} \right\}$. In this paper we study the relationship between computability-theoretic properties of E and algebraic properties of linearly ordered sets realized by E. One can also define the following pre-order $ \le _{lo} $ on the class of all c.e. equivalence relations: $E_1 \le _{lo} E_2 $ if every linear order realized by E1 is also realized by E2. Following the tradition of computability theory, the lo-degrees are the classes of equivalence relations induced by the pre-order $ \le _{lo} $. We study the partially ordered set of lo-degrees. For instance, we construct various chains and anti-chains and show the existence of a maximal element among the lo-degrees. [ABSTRACT FROM PUBLISHER]

S-measures are Loeb measures restricted to the sigma algebra generated by standard sets. This paper gives new extensions of the S-measure machinery, with applications to standard measure theory. [ABSTRACT FROM AUTHOR]

We introduce the notions of copyable and diagonalizable classes of structures. We then show how these notions are connected to two other notions that had already been studied for some particular classes of structures, namely the listability property and the low property. The main result of this paper is the characterizations of the classes of structures with the low property, that is, the classes whose low members all have computable copies. We characterize these classes as the ones whose structural jumps are listable. [ABSTRACT FROM AUTHOR]

In this paper, we propose a weak regularity principle which is similar to both weak König's lemma and Ramsey's theorem. We begin by studying the computational strength of this principle in the context of reverse mathematics. We then analyze different ways of generalizing this principle. [ABSTRACT FROM AUTHOR]

This paper studies homogeneously Suslin (hom) sets of reals in tame mice. The following results are established: In 0¶ the hom sets are precisely the Π̰1¹ sets. In Mn every hom set is correctly Δ̰ n+1¹, and (δ + 1)-universally Baire where δ is the least Woodin. In Mω every hom set is <λ-hom, where λ is the supremum of the Woodins. [ABSTRACT FROM AUTHOR]

In this paper we study with proof-theoretic methods the function(al)s provably recursive relative to Ramsey's theorem for pairs and the cohesive principle (COH). Our main result on COH is that the type 2 functionals provably recursive from Due to image rights restrictions, multiple equation(s) cannot be graphically displayed. are primitive recursive. This also provides a uniform method to extract bounds from proofs that use these principles. As a consequence we obtain a new proof of the fact that Due to image rights restrictions, multiple equation(s) cannot be graphically displayed. is Due to image rights restrictions, multiple equation(s) cannot be graphically displayed. over PRA. Recent work of the first author showed that Due to image rights restrictions, multiple equation(s) cannot be graphically displayed. is equivalent to a weak variant of the Bolzano-Weierstraß principle. This makes it possible to use our results to analyze not only combinatorial but also analytical proofs. For Ramsey's theorem for pairs and two colors Due to image rights restrictions, multiple equation(s) cannot be graphically displayed. we obtain the upper bounded that the type 2 functionals provable recursive relative to Due to image rights restrictions, multiple equation(s) cannot be graphically displayed. are in T1, This is the fragment of Gödel's system T containing only type 1 recursion--roughly speaking it consists of functions of Ackermann type. With this we also obtain a uniform method for the extraction of T1-bounds from proofs that use Due to image rights restrictions, multiple equation(s) cannot be graphically displayed. Moreover, this yields a new proof of the fact that Due to image rights restrictions, multiple equation(s) cannot be graphically displayed. over Due to image rights restrictions, multiple equation(s) cannot be graphically displayed. The results are obtained in two steps: in the first step a term including Skolem functions for the above principles is extracted from a given proof This is done using Gödel's functional interpretation. After this the term is normalized, such that only specific instances of the Skolem functions are used. In the second step this term is interpreted using ∏ Due to image rights, restrictions, multiple equation(s) cannot be graphically displayed -comprehension. The comprehension is then eliminated in favor of induction using either elimination of monotone Skolem functions (for COH) or Howard's ordinal analysis of bar recursion Due to image rights restrictions, multiple equation(s) cannot be graphically displayed. [ABSTRACT FROM AUTHOR]

This paper compares the roles classical and intuitionistic logic play in restricting the free use of truth principles in arithmetic. We consider fifteen of the most commonly used axiomatic principles of truth and classify every subset of them as either consistent or inconsistent over a weak purely intuitionistic theory of truth. [ABSTRACT FROM AUTHOR]

In this paper, using definability of types over indiscernible sequences as a template, we study a property of formulas and theories called "uniform definability of types over finite sets" (UDTFS). We explore UDTFS and show how it relates to well-known properties in model theory. We recall that stable theories and weakly o-minimal theories have UDTFS and UDTFS implies dependence. We then show that all dp-minimal theories have UDTFS. [ABSTRACT FROM AUTHOR]

In 1984, Henson and Rubel [2] proved the following theorem: If p(x1,…, xn) is an exponential polynomial with coefficients in C with no zeroes in C, then p(x1,…, xn) = Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed. where g(xl,…, xn) is some exponential polynomial over C. In this paper, I will prove the analog of this theorem for Zilber's Pseudoexponential fields directly from the axioms. Furthermore, this proof relies only on the existential closedness axiom without any reference to Schanuel's conjecture. [ABSTRACT FROM AUTHOR]

This work builds on previous papers by Hrushovski, Pillay and the author where Keisler measures over NIP theories are studied. We discuss two constructions for obtaining generically stable measures in this context. First. we show how to symmetrize an arbitrary invariant measure to obtain a generically stable one from it. Next. we show that suitable sigma-additive probability measures give rise to generically stable Keisler measures. Also included is a proof that generically stable measures over o-minimal theories and the p-adics are smooth. [ABSTRACT FROM AUTHOR]

Let A be a non-empty set. A set S ⊆ 풫(A) is said to be stationary in 풫(A) if for every ƒ: [A]<ω → A there exists x ∈ S such that x ≠ A and ƒ"[x]<ω ⊆ x. In this paper we prove the following: For an uncountable cardinal λ and a stationary set S in 풫(λ), if there is a regular uncountable cardinal κ ≤ λ such that {x ∈ S : x ∩ κ ∈ κ} is stationary, then S can be split into κ disjoint stationary subsets. [ABSTRACT FROM AUTHOR]

In this paper we prove that a degree a is array nonrecursive (ANR) if and only if every degree b ≥ a is r.e. in and strictly above another degree (RRE). This result will answer some questions in [ASDWY]. We also deduce an interesting corollary that every n-REA degree has a strong minimal cover if and only if it is array recursive. [ABSTRACT FROM AUTHOR]

Jullien's indecomposability theorem (INDEC) states that if a scattered countable linear order is indecomposable, then it is either indecomposable to the left or indecomposable to the right. The theorem was shown by Montalbán to be a theorem of hyperarithmetic analysis, and then, in the base system RCA0 plus ∑11 induction, it was shown by Neeman to have strength strictly between weak ∑11 choice and Δ11 comprehension. We prove in this paper that ∑11 induction is needed for the reversal of INDEC, that is for the proof that INDEC implies weak ∑11 choice. This is in contrast with the typical situation in reverse mathematics, where reversals can usually be refined to use only ∑11 induction. [ABSTRACT FROM AUTHOR]

This paper continues the study of the Ramsey-like large cardinals introduced in [5] and [14]. Ramsey-like cardinals are defined by generalizing the characterization of Ramsey cardinals via the existence of elementary embeddings. Ultrafilters derived from such embeddings are fully iterable and so it is natural to ask about large cardinal notions asserting the existence of ultrafilters allowing only α-many iterations for some countable ordinal α. Here we study such α-iterable cardinals. We show that the α-iterable cardinals form a strict hierarchy for α ≤ ω1, that they are downward absolute to L for α < ω1L, and that the consistency strength of Schindler's remarkable cardinals is strictly between 1-iterable and 2-iterable cardinals. We show that the strongly Ramsey and super Ramsey cardinals from [5] are downward absolute to the core model K. Finally, we use a forcing argument from a strongly Ramsey cardinal to separate the notions of Ramsey and virtually Ramsey cardinals. These were introduced in [14] as an tipper bound on the consistency strength of the Intermediate Chang's Conjecture. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the systems ns-ACA0 and ns-WKL0 of non-standard second-order arithmetic in which we can formalize non-standard arguments in ACA0 and WKL0, respectively. Then, we give direct transformations from non-standard proofs in ns-ACA0 or ns-WKL0 into proofs in ACA0 or WKL0. [ABSTRACT FROM AUTHOR]

To each computable enumerable (c.e.) set A with a particular enumeration {As}sϵω, there is associated a settling function mA,(x). where mA(x) is the last stage when a number less than or equal to x was enumerated into A. One c.e. set A is settling time dominated by another set B (B >st, A) if for every computable function f, for all but finitely many x, mB(x) > f(mA(x)). This settling-time ordering, which is a natural extension to an ordering of the idea of domination, was first introduced by Nabutovsky and Weinberger in [3] and Soare [6]. They desired a sequence of sets descending in this relationship to give results in differential geometry. In this paper we examine properties of the <st ordering. We show that it is not invariant under computable isomorphism, that any countable partial ordering embeds into it, that there are maximal and minimal sets, and that two c.e. sets need not have an inf or sup in the ordering. We also examine a related ordering, the strong settling-time ordering where we require for all computable f and g. for almost all x, mB (x) > f(mA(g(x))). [ABSTRACT FROM AUTHOR]

In [3], two different effective versions of Borel embedding are defined. The first, called computable embedding, is based on uniform enumeration reducibility, while the second, called Turing computable embedding, is based on uniform Turing reducibility. White [3] focused mainly on computable embeddings, the present paper considers Turing computable embeddings. Although the two notions are not equivalent, we can show that they behave alike on the mathematically interesting classes chosen for investigation in [3]. We give a "Pull-back Theorem", saying that if Φ is a Turing computable embedding of K into K¹, then for any computable infinitary sentence ϕ in the language of K¹. we can find a computable infinitary sentence ϕ* in the language of K such that for all … ε K, … …ϕ* iff Φ(…) … ϕ, and ϕ* has the same "complexity" as ϕ (i.e., if ϕ is computable Σα, or computable Πα, for α ≥ 1, then so is ϕ*), The Pull-back Theorem is useful in proving non-embeddability, and it has other applications as well. [ABSTRACT FROM AUTHOR]

Generic automorphisms of certain homogeneous structures are considered, for instance, the rationals as an ordered set, the countable universal homogeneous partial order, and the random graph. Two of these cases were discussed in [7], where it was shown that there is a generic automorphism of the second in the sense introduced in [10]. In this paper, I study various possible definitions of 'generic' and 'mutually generic', and discuss the existence of mutually generic automorphisms in some cases. In addition, generics in the automorphism group of the rational circular order are considered. [ABSTRACT FROM AUTHOR]

In [9], Yates proved the existence of a Turing degree a such that 0, 0′ are the only c.e. degrees comparable with it. By Slaman and Steel [7], every degree below 0′ has a 1-generic complement, and as a consequence, Yates degrees can be 1-generic, and hence can be low. In this paper, we prove that Yates degrees occur in every jump class. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new natural deduction system for the logic of lattices, and a number of extensions of lattice logic with different negation connectives. We provide the class of natural deduction proofs with both a standard inductive definition and a global graph-theoretical criterion for correctness, and we show how normalisation in this system corresponds to cut elimination in the sequent calculus for lattice logic. This natural deduction system is inspired both by Shoesmith and Smiley's multiple conclusion systems for classical logic and Girard's proofnets for linear logic. [ABSTRACT FROM AUTHOR]

Up to equivalence, a substitution in propositional logic is an endomorphism of its free algebra. On the dual space, this results in a continuous function, and whenever the space carries a natural measure one may ask about the stochastic properties of the action. In classical logic there is a strong dichotomy: while over finitely many propositional variables everything is trivial, the study of the continuous transformations of the Cantor space is the subject of an extensive literature, and is far from being a completed task. In many-valued logic this dichotomy disappears: already in the finite-variable case many interesting phenomena occur, and the present paper aims at displaying some of these. [ABSTRACT FROM AUTHOR]