bluuebunny/crossref_metadata_2025_split huggingface dataset:
Existentially closed algebras and boolean products
Authors: Riedel Herbert H. J. 
Published: May 2006

AbstractA Boolean product construction is used to give examples of existentially closed algebras in the universal Horn class ISP(K) generated by a universal class K of finitely subdirectly irreducible algebras such that Γa(K) has the Fraser-Horn property. If ⟦a ≠ b⟧ ∩ ⟦c ≠ d ⟧ = ∅ is definable in K and K has a model companion of K-simple algebras, then it is shown that ISP(K) has a model companion. Conversely, a sufficient condition is given for ISP(K) to have no model companion.
The classification of small weakly minimal sets. II
Authors: Buechler Steven 
Published: May 2006

AbstractThe main result is Vaught's conjecture for weakly minimal, locally modular and non-ω-stable theories. The more general results yielding this are the following.Theorem A. Suppose that T is a small unidimensional theory and D is a weakly minimal set, definable over the finite set B. Then for all finite A ⊂ D there are only finitely many nonalgebraic strong types over B realized in acl(A) ∩ D.Theorem B. Suppose that T is a small, unidimensional, non-ω-stable theory such that the universe is weakly minimal and locally modular. Then for all finite A there is a finite B ⊂ cl(A) such that a ∈ cl(A) iff a ∈ cl(b) for some b ∈ B.Recall the property (S) defined in the abstract of [B1].Theorem C. Let T be as in Theorem B. Then, if T does not satisfy (S), T hasmany countable models.Combining Theorem C and the results in [B1] we obtain Vaught's conjecture for such theories.
The model theory of chain-closed fields
Authors: Dickmann M. A. 
Published: May 2006

The notion of a higher level ordering is a generalization of the usual notion of an order introduced by Becker in the study of sums of even powers in a field; see [1] for a general reference. A precise definition of an ordering of level 2n (level n in the terminology of [1]) is given in Definition 1.1(II) below.In [1] Becker worked out the extension theory of fields with a higher level ordering and introduced the notion of a (generalized) real closure for such fields. For a survey of (the analog of) the Artin-Schreier theory of fields with a higher level ordering, see [2]. In [10] Jacob proved decidability, completeness and model-completeness (in a suitable language) for the theory of generalized real-closed fields. Jacob's results are in a sense optimal insofar as the nonuniqueness of generalized real closures (see [1, Chapter IV, Theorems 12 and 13]) prevents quantifier elimination results from holding in languages natural from an algebraic point of view.The following remarkable fact stems from the work of Becker and Harman: a field having a proper ordering (i.e. one which is not just an order) of any level necessarily has an ordering of (exact) level 2n for each integer n ≥ 2, plus two usual orders, and, moreover, a tight connection holds between orderings of two consecutive levels (cf. [9, Corollary 1.4] and [1, Theorem 15, p. 37]).
Sheaves of continuous definable functions
Authors: Pillay Anand 
Published: May 2006

Let M be an o-minimal structure or a p-adically closed field. Let be the space of complete n-types over M equipped with the following topology: The basic open sets of are of the form Ũ = {p ∈ Sn (M): U ∈ p} for U an open definable subset of Mn. is a spectral space. (For M = K a real closed field, is precisely the real spectrum of K[X1, …, Xn]; see [CR].) We will equip with a sheaf of LM-structures (where LM is a suitable language). Again for M a real closed field this corresponds to the structure sheaf on (see [S]). Our main point is that when Th(M) has definable Skolem functions, then if p ∈ , it follows that M(p), the definable ultrapower of M at p, can be factored through Mp, the stalk at p with respect to the above sheaf. This depends on the observation that if M ≺ N, a ∈ Nn and f is an M-definable (partial) function defined at a, then there is an open M-definable set U ⊂ Nn with a ∈ U, and a continuous M-definable function g:U → N such that g(a) = f(a).In the case that M is an o-minimal expansion of a real closed field (or M is a p-adically closed field), it turns out that M(p) can be recovered as the unique quotient of Mp which is an elementary extension of M.
Provability of the pigeonhole principle and the existence of infinitely many primes
Authors: Paris J. B. , Wilkie A. J. , Woods A. R. 
Published: May 2006

In this note we shall be interested in the following problems.Problem 1. Can IΔ0 ⊢ ∀x∃y > x(y is prime)?Here I Δ0 is Peano arithmetic with the induction axiom restricted to bounded (i.e. Δ0) formulae.Problem 2. Can IΔ0 ⊢ Δ0 PHP?Here Δ0 PHP (Δ0 pigeonhole principle) is the schemafor θ ∈ Δ0, or equivalently in IΔ0, for a Δ0 formula F(x,y)written .By obtaining partial solutions to Problem 2 we shall show that Problem 1 has a positive solution if IΔ0 is replaced by IΔ0 + ∀xxlog(x) exists.Our notation will be entirely standard (see for example [3] and [4]). In particular all logarithms will be to the base 2 and in expressions like log(x), (1 + ε)x, etc. we shall always mean the integer part of these quantities.Concerning Problem 2 we remark that it is shown in [5] that for k ∈ N and F ∈ Δ0,As far as we know this is the best result of this form, in that we do not know how to replace log(z)k by anything larger. However, as we shall show in Theorem 1, we can do much better if we increase the difference between the sizes of the domain and range of F.In what follows let M be a countable nonstandard model of IΔ0, and let be those subsets of M defined by Δ0 formulae with parameters from M.Theorem 1. For k ∈ N andF ∈ Δ0,Here log0(x) = x, logk + 1(x) = log(logk(x)).Proof. To simplify matters, consider first the case k = 1. So assume M ⊨ alog(a) exists and with and a > 1. The idea of the proof is the following.
Mechanical learners pay a price for Bayesianism
Authors: Osherson Daniel N. , Stob Michael , Weinstein Scott 
Published: May 2006

The price is failure on a class of inductive inference problems that are easily solved, in contrast, by nonBayesian mechanical learners. By “mechanical” is meant “simulable by Turing machine”.One of the central tenets of Bayesianism, which is common to the heterogeneous collection of views which fall under this rubric, is that hypothesis change proceeds via conditionalization on accumulated evidence, the posterior probability of a given hypothesis on the evidence being computed using Bayes's theorem. We show that this strategy for hypothesis change precludes the solution of certain problems of inductive inference by mechanical means—problems which are solvable by mechanical means when the restriction to this Bayesian strategy is lifted. Our discussion proceeds as follows. After some technical preliminaries, the concept of (formal) learner is introduced along with a criterion of inferential success. Next we specify a class of inductive inference problems, and then define the notion of “Bayesian behavior” on those problems. Finally, we exhibit an inductive inference problem from the specified class such that (a) some nonmechanical Bayesian learner solves the problem, (b) some nonBayesian mechanical learner solves the problem, (c) some mechanical learner manifests Bayesian behavior on the problem, but (d) no mechanical Bayesian learner solves the problem.Insofar as possible terminology and notation are drawn from Osherson, Stob, and Weinstein [1986].
The equivalence of determinacy and iterated sharps
Authors: Dubose Derrick Albert 
Published: May 2006

AbstractWe characterize, in terms of determinacy, the existence of 0## as well as the existence of each of the following: 0###, 0####, 0#####,…. For κ Є ω, we define two classes of sets, and , which lie strictly between and . We also define 01# as# and in general, 0(k+1)# as (0k#)#. We then show that the existence of 0(k + 1)# is equivalent to the determinacy of as well as the determinacy of .
Boolean algebras and orbits of the lattice of r.e sets modulo the finite sets
Authors: Cholak Peter 
Published: May 2006

An important program in the study of the structure the lattice of r.e. sets modulo finite sets, is the classification of the orbits under Aut(), the automorphism group of , If Φ ∈ Aut() and Φ(We) =* Wh(e) for all e ∈ ω, then h is called a presentation of Φ. Define Autχ() to be the class of those elements of Aut() that have a presentation in the class of functions X, where for instance X might be the class of Δn functions for n ∈ ω. If Φ ∈ Autx() then we will say that Φ is an X-automorphism. Note that we only need to consider Δn- and Πn-orbits and automorphisms since if f is a Σn-presentation, then f is a total function and therefore Δn.Definition. If X is a class of functions and ⊆ {Wi: i < ω}, then is an X-orbit iff is an orbit under Aut() and for all A, B ∈ there is a Φ ∈ Autx() satisfying Φ(A) =* B. (Here Φ: → .)Harrington proved that the creative sets form a Δ0-orbit and Soare proved that the maximal sets form Δ3-orbit. We will show that there is no Boolean algebra such that {A: A is r.e. and ℒ*(A) ≈ ] forms a Δ2-orbit, where ℒ*(A) is the principal filter of A in ; ℒ*(A) = {B: B ⊆* A & B ∈ }. The idea behind the proof of this theorem is very similar to the proof by Soare that maximal sets do not form a Δ2-orbit (see Soare [1974] or Soare [1987]).
On Diophantine equations solvable in models of open induction
Authors: Otero Margarita 
Published: May 2006

AbstractWe consider IOpen, the subsystem of PA (Peano Arithmetic) with the induction scheme restricted to quantifier-free formulas.We prove that each model of IOpen can be embedded in a model where the equation has a solution. The main lemma states that there is no polynomial f{x,y) with coefficients in a (nonstandard) DOR M such that ∣f(x,y) ∣ < 1 for every (x,y) Є C, where C is the curve defined on the real closure of M by C: x2 + y2 = a and a > 0 is a nonstandard element of M.
A metatheorem for constructions by finitely many workers
Authors: Knight J. F. 
Published: May 2006

The aim of the present paper is to give some general conditions for constructions by finitely many workers. Constructions using infinitely many workers will not be considered here, although there are examples of such constructions. The original construction using the method of workers, due to Harrington [H], has a worker n for each n ∈ ω, as do the constructions in [K1] and [K2]. Marker [M] obtains a result using three workers. In [AJK], there are two constructions that use three workers. There are also two constructions that have, for an arbitrary recursive ordinal α, one worker for each β < α.The main result here is a metatheorem, which is patterned after Proposition 1 of Ash [A]. As in [A], the object of the construction is to attach “labels” to the nodes in a highly nonrecursive path through a tree, while recursively enumerating neighborhoods of an “adherent” point in a metric space. There is a family of relations associated with the labels, and the metatheorem here and the one in [A] both say that the construction will succeed if these relations satisfy a list of properties. There are significant differences between the result here and that in [A]. One difference is that certain relations which in [A] were required to be r.e. need not be r.e. here. Another difference is that there are extra relations here, and as a result, the list of properties to be satisfied is longer and more horrible than that in [A].
Lifschitz' realizability
Authors: van Oosten Jaap 
Published: May 2006

AbstractV. Lifschitz defined in 1979 a variant of realizability which validates Church's thesis with uniqueness condition, but not the general form of Church's thesis. In this paper we describe an extension of intuitionistic arithmetic in which the soundness of Lifschitz' realizability can be proved, and we give an axiomatic characterization of the Lifschitz-realizable formulas relative to this extension. By a “q-variant” we obtain a new derived rule. We also show how to extend Lifschitz' realizability to second-order arithmetic. Finally we describe an analogous development for elementary analysis, with partial continuous application replacing partial recursive application.
Nonuniformization results for the projective hierarchy
Authors: Jackson Steve , Mauldin R. Daniel 
Published: May 2006

AbstractLet X and Y be uncountable Polish spaces. We show in ZF that there is a coanalytic subset P of X × Y with countable sections which cannot be expressed as the union of countably many partial coanalytic, or even PCA = , graphs. If X = Y = ωω, P may be taken to be . Assuming stronger set theoretic axioms, we identify the least pointclass such that any such coanalytic P can be expressed as the union of countably many graphs in this pointclass. This last result is extended (under suitable hypotheses) to all levels of the projective hierarchy.
A cardinality version of Beigel's nonspeedup theorem
Authors: Owings James C. 
Published: May 2006

AbstractIf S is a finite set, let ∣S∣ be the cardinality of S. We show that if m ∈ ω, A ⊆ ω, B ⊆ ω, and ∣i: ≤ i ≤ 2m & xi ∈ A}∣ can be computed by an algorithm which, for all x1, …, x2m, makes at most m queries to B, then A is recursive in the halting set K. If m = 1, we show that A is recursive.
A note on the multiplicative semigroup of models of Peano arithmetic
Authors: Kossak Roman , Nadel Mark , Schmerl James 
Published: May 2006

In a model of Peano arithmetic, the isomorphism type of the multiplicative semigroup uniquely determines the isomorphism type of the additive semigroup. In fact, for any prime p of , the function x ↦ px is an isomorphism of the additive semigroup with the multiplicative subsemigroup of powers of p. It was observed by Jensen and Ehrenfeucht [3] that for countable models of PA, the isomorphism type of the additive semigroup (or even the additive group) determines the isomorphism type of the multiplicative semigroup. (See Theorem 3 below.)In this note we will show that the countability restriction cannot be dropped. First, we show (as Theorem 2) that for uncountable models of PA the isomorphism type of the additive group never determines the isomorphism type of the multiplicative semigroup. Our main result is Theorem 5 in which we show that the isomorphism type of the additive semigroup need not determine the isomorphism type of the multiplicative semigroup, thereby improving upon Harnik [2], where Theorem 5 is proved under the assumption of ♢. For completeness, a sketch of the proof of the Jensen-Ehrenfeucht result is included.The history of this paper begins with Nadel's question, asked in 1981, whether the countability assumption can be eliminated in the Jensen-Ehrenfeucht theorem. Soon afterwards, Nadel obtained the strong counterexample of Theorem 2, which applied to the additive group rather than the additive semigroup. A result of Pabion [8] shows that such a strong result is not possible for the additive semigroup.
The roots of contemporary Platonism
Authors: Maddy Penelope 
Published: May 2006

Though many working mathematicians embrace a rough and ready form of Platonism, that venerable position has suffered a checkered philosophical career. Indeed the three schools of thought with which most of us began our official philosophizing about mathematics—Intuitionism, Formalism, and Logicism—all stand in fundamental disagreement with Platonism. Nevertheless, various versions of Platonistic thinking survive in contemporary philosophical circles. The aim of this paper is to describe these views, and, as my title suggests, to trace their roots.I'll begin with some preliminary remarks about the big three schools. This seems a reasonable approach to the issues both because most observers are familiar, at least in a general way, with the tenets of Intuitionism, Formalism, and Logicism, and because it is in reaction to these that contemporary Platonism has taken shape.
Coding over a measurable cardinal
Authors: Friedman Sy D. 
Published: May 2006

The purpose of this paper is to extend the coding method (see Beller, Jensen and Welch [82]) into the context of large cardinals.Theorem. Suppose μ is a normal measure on κ in V and 〈 V, A〉 ⊨ ZFC. Then there is a 〈V, A〉-definable forcing for producing a real R such that:(a) V[R] ⊨ ZFC and A is V[R]-definable with parameter R.(b) V[R] = L[μ*, R], where μ* is a normal measure on κ in V[R] extending μ.(c) V ⊨ GCH → is cardinal and cofinality preserving.Corollary. It is consistent that μ is a normal measure, R ⊆ ω is not set-generic over L[μ] and 0+ ∉ L[μ, R].Some other corollaries will be discussed in §4 of the paper.The main difficulty in L[μ]-coding lies in the problem of “stationary restraint”.As in all coding constructions, conditions will be of the form belonging to an initial segment of the cardinals, where p(γ) is a condition for almost disjoint coding into a subset of γ+. In addition for limit cardinals γ in Domain(p), 〈pγ′∣γ′ < γ〉 serves to code pγ.An important restriction in coding arguments is that for inaccessible for only a nonstationary set of γ′ < γ. The reason is that otherwise there are conflicts between the restraint imposed by the different and the need to code extensions of pγ below γ.
Descriptive set theory over hyperfinite sets
Authors: Keisler H. Jerome , Kunen Kenneth , Miller Arnold , Leth Steven 
Published: May 2006

AbstractThe separation, uniformization, and other properties of the Borel and projective hierarchies over hyperfinite sets are investigated and compared to the corresponding properties in classical descriptive set theory. The techniques used in this investigation also provide some results about countably determined sets and functions, as well as an improvement of an earlier theorem of Kunen and Miller.
Large resplendent models generated by indiscernibles
Authors: Schmerl James H. 
Published: May 2006

The motivation for the results presented here comes from the following two known theorems which concern countable, recursively saturated models of Peano arithmetic.(1) if is a countable, recursively saturated model of PA, then for each infinite cardinal κ there is a resplendent which has cardinality κ. (See Theorem 10 of [1].)(2) if is a countable, recursively saturated model of PA, then is generated by a set of indiscernibles. (See [4].)It will be shown here that (1) and (2) can be amalgamated into a common generalization.(3) if is a countable, recursively saturated model of PA, then for each infinite cardinal κ there is a resplendent which has cardinality κ and which is generated by a set of indiscernibles.By way of contrast we will also get recursively saturated models of PA which fail to be resplendent and yet are generated by indiscernibles.(4) if is a countable, recursively saturated model of PA, then for each uncountable cardinal κ there is a κ-like recursively saturated generated by a set of indiscernibles.None of (1), (2) or (3) is stated in its most general form. We will make some comments concerning their generalizations. From now on let us fix a finite language L; all structures considered are infinite L-structures unless otherwise indicated.
The equivalence of the disjunction and existence properties for modal arithmetic
Authors: Friedman Harvey , Sheard Michael 
Published: May 2006

AbstractIn a modal system of arithmetic, a theory S has the modal disjunction property if whenever S ⊢ □φ ∨ □ψ, either S ⊢ □φ or S ⊢ □ψ. S has the modal numerical existence property if whenever S ⊢ ∃x □φ(x), there is some natural number n such that S ⊢ □φ(n). Under certain broadly applicable assumptions, these two properties are equivalent.
Undecidable complexity statements in -arithmetic
Authors: Sigal Ron 
Published: May 2006

The failure of a large and diverse body of work to settle some of the now-classical questions of computational complexity (notably P =? NP) suggests that they might not, in fact, be resolvable by established proof techniques.Hartmanis and Hopcroft [HH] raised the issue of independent statements about computational complexity in 1976, constructing, for any consistent r.e. theory T capable of expressing statements about Turing machines, a Turing machine MT such that statements which intuitively express the computational complexity of MT are independent of T. Their technique involves a simple diagonalizing search over the theorems of T. In this paper we prove a constructive version of their independence result in the context of a generalization of a hierarchy of free variable logics defined by Rose [R1]. These logics are based on an axiomatized treatment of an extension by Löb and Wainer [LW] of Grzegorczyk's [G] hierarchy into the transfinite. Associated with each extended Grzegorczyk class (relative to an ordinal notation system S satisfying certain conditions) is the logic -arithmetic.Free variable logics are interesting from the perspective of theoretical computer science. We may construe the equational definition of functions as a form of programming system. Each -arithmetic, then, has the nice property of containing both a programming system and a logic for stating and proving facts about programs.
Two recursion theoretic characterizations of proof speed-ups
Authors: Royer James S. 
Published: May 2006

Smullyan in [Smu61] identified the recursion theoretic essence of incompleteness results such as Gödel's first incompleteness theorem and Rosser's theorem. Smullyan (improving upon [Kle50] and [Kle52]) showed that, for sufficiently complex theories, the collection of provable formulae and the collection of refutable formulae are effectively inseparable—where formulae and their Gödel numbers are identified. This paper gives a similar treatment for proof speed-up. We say that a formal system S1is speedable over another system S0on a set of formulaeAiff, for each recursive functionh, there is a formulaαinAsuch that the length of the shortest proof ofαin S0is larger thanhof the shortest proof ofαin S1. (Here we equate the length of a proof with something like the number of characters making it up,notits number of lines.) We characterize speedability in terms of the inseparability by r.e. sets of the collection of formulae which are provable in S1but unprovable in S0from the collectionA–where again formulae and their Gödel numbers are identified. We provide precise definitions of proof length, speedability and r.e. inseparability below.We follow the terminology and notation of [Rog87] with borrowings from [Soa87]. Below,ϕis an acceptable numbering of the partial recursive functions [Rog87] andΦa (Blum) complexity measure associated withϕ[Blu67], [DW83].
Meager sets on the hyperfinite time line
Authors: Keisler H. Jerome , Leth Steven C. 
Published: May 2006

In this paper we study notions of a “meager subset” of a hyper-finite set. We work within an ω-saturated nonstandard universe and fix a hyperfinite natural number Є *N∖N. We shall consider subsets of the set = {1, 2, …,H}.By analogy with the meager subsets of the real interval [0, 1], a notion of meager subset of should have the following properties.1. Finite sets, countable unions of meager sets, subsets of meager sets, and translates of meager sets should be meager.2. The Baire Category Theorem should hold; that is, should not be meager.3. The internal analogue of the Cantor set should be meager.4. The notion of a meager set should be with respect to a natural topology on .5. There should exist meager subsets of of Loeb measure one.6. Sierpiński and Lusin sets should have hyperfinite counterparts with properties similar to the classical case.Property 5 is desirable so that, as with Lebesgue measure and Baire category on [0, 1], the topological and measure-theoretic notions of “large” and “small” sets are incomparable.Property 6, while not as necessary as the other five, is desirable because of the strong interplay between measure and category in the classical results about Lusin and Sierpinski sets. Our objective is to find notions of meager set which have a relationship to Loeb measure similar to the classical relationship between meager sets and Lebesgue measure.