bluuebunny/crossref_metadata_2025_split huggingface dataset:
Universal diophantine equation
Authors: Jones James P. 
Published: May 2006

In 1961 Martin Davis, Hilary Putnam and Julia Robinson [2] proved that every recursively enumerable set W is exponential diophantine, i.e. can be represented in the formHere P is a polynomial with integer coefficients and the variables range over positive integers.In 1970 Ju. V. Matijasevič used this result to establish the unsolvability of Hilbert's tenth problem. Matijasevič proved [11] that the exponential relation y = 2x is diophantine This together with [2] implies that every recursively enumerable set is diophantine, i.e. every r.e. set Wcan be represented in the formFrom this it follows that there does not exist an algorithm to decide solvability of diophantine equations. The nonexistence of such an algorithm follows immediately from the existence of r.e. nonrecursive sets.Now it is well known that the recursively enumerable sets W1, W2, W3, … can be enumerated in such a way that the binary relation x ∈ Wv is also recursively enumerable. Thus Matijasevič's theorem implies the existence of a diophantine equation U such that for all x and v,
Saturated models of Peano arithmetic
Authors: Pabion J. F. 
Published: May 2006

AbstractWe study reducts of Peano arithmetic for which conditions of saturation imply the corresponding conditions for the whole model. It is shown that very weak reducts (like pure order) have such a property for κ-saturation in every κ ≥ ω1. In contrast, other reducts do the job for ω and not for κ > ω1. This solves negatively a conjecture of Chang.
Implicational complexity in intuitionistic arithmetic
Authors: Leivant Daniel 
Published: May 2006

In classical arithmetic a natural measure for the complexity of relations is provided by the number of quantifier alternations in an equivalent prenex normal form. However, the proof of the Prenex Normal Form Theorem uses the following intuitionistically invalid rules for permuting quantifiers with propositional constants.Each one of these schemas, when added to Intuitionistic (Heyting's) Arithmetic IA, generates full Classical (Peano's) Arithmetic. Schema (3) is of little interest here, since one can obtain a formula intuitionistically equivalent to A ∨ ∀xBx, which is prenex if A and B are:For the two conjuncts on the r.h.s. (1) may be successively applied, since y = 0 is decidable.We shall readily verify that there is no way of similarly going around (1) or (2). This fact calls for counting implication (though not conjunction or disjunction) in measuring in IA the complexity of arithmetic relations. The natural implicational measure for our purpose is the depth of negative nestings of implication, defined as follows. I(F): = 0 if F is atomic; I(F ∧ G) = I(F ∨ G): = max[I(F), I(G)]; I(∀xF) = I(∃xF): = I(F); I(F → G):= max[I(F) + 1, I(G)].
Vaught's theorem recursively revisited
Authors: Millar Terrence 
Published: May 2006

In this paper we investigate the relationship between the number of countable and decidable models of a complete theory. The number of decidable models will be determined in two ways, in §1 with respect to abstract isomorphism type, and in §2 with respect to recursive isomorphism type.Definition 1. A complete theory is (α, β) if the number of countable models of T, up to abstract isomorphism, is β, and similarly the number of decidable models of T is α.Definition 2. A model is ω-decidable if ∣∣= ω and for an effective listing {θn∣n < ω} of all sentences in the language of Th() augmented by new constant symbols i*, i < ω, {n ∣〈, i〉i<ω ⊨ θn} is recursive, where i interprets i* (in these terms, is decidable if is abstractly isomorphic to an ω-decidable model).Definition 3. A complete theory is (α, β)r if it is (γ, β) for some γ and it has exactly αω-decidable models up to recursive isomorphism.Specifically we will show in §1 that there is a (2, ω) theory, and in §2 that although there is a (2, 2ω) theory, there is no (2, β)r theory for any β, β < 2ω.
Forcing and reducibilities. III. Forcing in fragments of set theory
Authors: Odifreddi Piergiorgio 
Published: May 2006

We conclude here the treatment of forcing in recursion theory begun in Part I and continued in Part II of [31]. The numbering of sections is the continuation of the numbering of the first two parts. The bibliography is independent.In Part I our language was a first-order language: the only set we considered was the (set constant for the) generic set. In Part II a second-order language was introduced, and we had to interpret the second-order variables in some way. What we did was to consider the ramified analytic hierarchy, defined by induction as:A0 = {X ⊆ ω: X is arithmetic},Aα+1 = {X ⊆ ω: X is definable (in 2nd order arithmetic) over Aα},Aλ = ⋃α<λAα (λ limit),RA = ⋃αAα.We then used (a relativized version of) the fact that (Kleene [27]). The definition of RA is obviously modeled on the definition of the constructible hierarchy introduced by Gödel [14]. For this we no longer work in a language for second-order arithmetic, but in a language for (first-order) set theory with membership as the only nonlogical relation:L0 = ⊘,Lα+1 = {X: X is (first-order) definable over Lα},Lλ = ⋃α<λLα (λ limit),L = ⋃αLα.
Degrees of types and independent sequences
Authors: Knight Julia F. 
Published: May 2006

The theories considered here are countable and complete, and the types are all complete too. Let T be an L-theory. A sequence σ = (σn(ν))n∈ω of L-formulas is said to be independent (with respect to T) if for each α ∈ 2<ω, the sentenceis in T. As an example, let T = Th(Z, +), and let σ be the sequence of formulas saying (in the language of groups) ν is divisible by the nth prime, for n ∈ ω.A theory T has an independent sequence of formulas just in case it has types. If T has one independent sequence σ, then it has other independent sequences of arbitrarily high degree. (These can be obtained by taking conjunctions of the formulas from σ. If T has an independent sequence that is recursive, or one that is recursive in some type, then T will have types of arbitrarily high degree. (This follows from the fact that the independent sequence can be used to encode any set in a type.)Nadel and the author had wondered whether a theory with types must have an independent sequence of formulas that is recursive in one of the types. The main result of the present paper is an example of a recursive theory for which this is not the case.
A boundedness theorem in ID1(W)
Authors: Jäger Gerhard 
Published: May 2006

In this paper we prove a boundedness theorem in the theory ID1(W). This answers a question asked by Feferman, for example in [3]. The background is the following.Let A[X, x] be an X-positive formula arithmetic in X. The theory ID1(PA) is an extension of Peano arithmetic PA by the following axioms:for arbitrary formulas F; PA is a constant for the least fixed point of A[X, x]. Set-theoretically, PA can be defined by recursion on the ordinals as follows:where is the first nonrecursive ordinal.Now let a ≺ b be the arithmetic relation which expresses that the recursive tree coded by a is a proper subtree of the tree coded by b, and defineThe least fixed point of Tree[X, x] is the set PTree of all well-founded recursive trees. We write W or Wα for PTree or , respectively. Since W is complete we have for all α < . If we define for each element a ∈ W its inductive norm ∣a∣ by ∣a∣≔ min{ξ: a ∈ Wξ}, then we have = {∣a∣: a ∈ W} and the elements of W can be used as codes for the ordinals less than .Assume that B[X, x] is an X-positive formula arithmetic in X with the only free variables X and x, and assume that QB is a relation that satisfiesIf we definethen we obviously have PB = IB.
The weak □* is really weaker than the full □
Authors: Ben-David Shai , Magidor Menachem 
Published: May 2006

AbstractWe show that relative to the consistency of a supercompact cardinal does not imply . The model-theoretic transfer property ⟨ℵ1, ℵ0⟩ → ⟨ℵω + 1, ℵω⟩ does not imply , and it is consistent to have an ultrafilter on ℵω + 1 which is λ-indecomposible for all ω < λ < ℵω.
A guide to “Coding the universe” by Beller, Jensen, Welch
Authors: Friedman Sy D. 
Published: May 2006

In the wake of Silver's breakthrough on the Singular Cardinals Problem (Silver [74]) followed one of the landmark results in set theory, Jensen's Covering Lemma (Devlin-Jensen [74]): If 0# does not exist then for every uncountable x ⊆ ORD there exists a constructible Y ⊇ X, card(Y) = card(X). Thus it is fair to say that in the absence of large cardinals, V is “close to L”.It is natural to ask, as did Solovay, if we can fairly interpret the phrase “close to L” to mean “generic over L”. For example, if V = L[a], a ⊆ ω and if 0# does not exist then is V-generic over L for some partial ordering ∈ L? Notice that an affirmative answer implies that in the absence of 0#, no real can “code” a proper class of information.Jensen's Coding Theorem provides a negative answer to Solovay's question, in a striking way: Any class can be “coded” by a real without introducing 0#. More precisely, if A ⊆ ORD then there is a forcing definable over 〈L[A], A〉 such that ⊩ V = L[a], a ⊆ ω, A is definable from a. Moreover if 0# ∉ L[A] then ⊩ 0# does not exist. Now as any M ⊨ ZFC can be generically extended to a model of the form L[A] (without introducing 0#) we obtain: For any 〈M, A〉 ⊨ ZFC (that is, M ⊨ ZFC and M obeys Replacement for formulas mentioning A as a predicate) there is an 〈M, A〉-definable forcing such that ⊩ V = L[a], a ⊆ ω, 〈M, A〉 is definable from a. Moreover if 0# ∉ M then ⊩ 0# does not exist.
Taking out LK parts from a proof in Peano arithmetic
Authors: Yukami Tsuyoshi 
Published: May 2006

Let PA be Peano arithmetic with function symbols′, + and ·. The length of a proof P, denoted by lh(P), is the maximum length of threads of P (for the term ‘thread’, see [T, p. 14]). For a formula A and a natural number m, PA ⊢mA denotes the fact that there is a proof in PA of A whose length is less than or equal to m. PA ⊢ A denotes the fact that there is a proof in PA of A.G. Kreisel conjectured that the following proposition holds.“Let m be a natural number and A(a) be a formula. If for each natural number n, then PA ⊢ ∀xA(x)”.Let PA1 be the corresponding system with + and · replaced by ternary predicates and axioms saying that these predicates represent functions. Parikh [P] proved the following proposition which is obtained from Kreisel's conjecture by replacing PA by PA1.Proposition. Let A(a) be a formula in PA1and m be a natural number. Assume thatfor each natural number n. Then PA1 ⊢ ∀xA(x).The reason why Parikh's method succeeds is the fact that the only function symbol ′ in PA1 is unary. So his method fails for PA.To solve this conjecture for PA, we must make syntactical investigation into proofs in PA of formulas of the form A() with length ≤ m. Even if lengths of proofs are less than or equal to m, depths of occurrences of bound variables in induction axiom schemata or equality axiom schemata in proofs are not always bounded.
Commutative regular rings and Boolean-valued fields
Authors: Smith Kay 
Published: May 2006

In this paper we present an equivalence between the category of commutative regular rings and the category of Boolean-valued fields, i.e., Boolean-valued sets for which the field axioms are true. The author used this equivalence in [12] to develop a Galois theory for commutative regular rings. Here we apply the equivalence to give an alternative construction of an algebraic closure for any commutative regular ring (the original proof is due to Carson [2]).Boolean-valued sets were developed in 1965 by Scott and Solovay [10] to simplify independence proofs in set theory. They later were applied by Takeuti [13] to obtain results on Hilbert and Banach spaces. Ellentuck [3] and Weispfenning [14] considered Boolean-valued rings which consisted of rings and associated Boolean-valued relations. (Lemma 4.2 shows that their equality relation is the same as the one used in this paper.) To the author's knowledge, the present work is the first to employ the Boolean-valued sets of Scott and Solovay to obtain results in algebra.The idea that commutative regular rings can be studied by examining the properties of related fields is not new. For several years algebraists and logicians have investigated commutative regular rings by representing a commutative regular ring as a subdirect product of fields or as the ring of global sections of a sheaf of fields over a Boolean space (see, for example, [9] and [8]). These representations depend, as does the work presented here, on the fact that the set of central idempotents of any ring with identity forms a Boolean algebra. The advantage of the Boolean-valued set approach is that the axioms of classical logic and set theory are true in the Boolean universe. Therefore, if the axioms for a field are true for a Boolean-valued set, then other properties of the set can be deduced immediately from field theory.
Monotone reducibility and the family of infinite sets
Authors: Cenzer Douglas 
Published: May 2006

AbstractLet A and B be subsets of the space 2N of sets of natural numbers. A is said to be Wadge reducible to B if there is a continuous map Φ from 2N into 2N such that A = Φ−1 (B); A is said to be monotone reducible to B if in addition the map Φ is monotone, that is, a ⊂ b implies Φ(a) ⊂ Φ(b). The set A is said to be monotone if a ∈ A and a ⊂ b imply b ∈ A. For monotone sets, it is shown that, as for Wadge reducibility, sets low in the arithmetical hierarchy are nicely ordered. The sets are all reducible to the ( but not ) sets, which are in turn all reducible to the strictly sets, which are all in turn reducible to the strictly sets. In addition, the nontrivial sets all have the same degree for n ≤ 2. For Wadge reducibility, these results extend throughout the Borel hierarchy. In contrast, we give two natural strictly monotone sets which have different monotone degrees. We show that every monotone set is actually positive. We also consider reducibility for subsets of the space of compact subsets of 2N. This leads to the result that the finitely iterated Cantor-Bendixson derivative Dn is a Borel map of class exactly 2n, which answers a question of Kuratowski.
A note on some intermediate propositional calculi
Authors: Boričić Branislav R. 
Published: May 2006

This note is written in reply to López-Escobar's paper [L-E] where a “sequence” of intermediate propositional systems NLCn (n ≥ 1) and corresponding implicative propositional systems NLICn (n ≥ 1) is given. We will show that the “sequence” NLCn contains three different systems only. These are the classical propositional calculus NLC1, Dummett's system NLC2 and the system NLC3. Accordingly (see [C], [Hs2], [Hs3], [B 1], [B2], [Hs4], [L-E]), the problem posed in the paper [L-E] can be formulated as follows: is NLC3a conservative extension of NLIC3? Having in mind investigations of intermediate propositional calculi that give more general results of this type (see V. I. Homič [H1], [H2], C. G. McKay [Mc], T. Hosoi [Hs 1]), in this note, using a result of Homič (Theorem 2, [H1]), we will give a positive solution to this problem.NLICnand NLCn. If X and Y are propositional logical systems, by X ⊆ Y we mean that the set of all provable formulas of X is included in that of Y. And X = Y means that X ⊆ Y and Y ⊆ X. A(P1/B1, …, Pn/Bn) is the formula (or the sequent) obtained from the formula (or the sequent) A by substituting simultaneously B1, …, Bn for the distinct propositional variables P1, …, Pn in A.Let Cn(n ≥ 1) be the string of the following sequents:Having in mind that the calculi of sequents can be understood as meta-calculi for the deducibility relation in the corresponding systems of natural deduction (see [P]), the systems of natural deductions NLCn and NLICn (n ≥ 1), introduced in [L-E], can be identified with the calculi of sequents obtained by adding the sequents Cn as axioms to a sequential formulation of the Heyting propositional calculus and to a system of positive implication, respectively (see [C], [Ch], [K], [P]).
Orthomodularity is not elementary
Authors: Goldblatt Robert 
Published: May 2006

In this note it is shown that the property of orthomodularity of the lattice of orthoclosed subspaces of a pre-Hilbert space is not determined by any first-order properties of the relation ⊥ of orthogonality between vectors in . Implications for the study of quantum logic are discussed at the end of the paper.The key to this result is the following:Ifis a separable Hilbert space, andis an infinite-dimensional pre-Hilbert subspace of, then (, ⊥) and (, ⊥) are elementarily equivalent in the first-order languageL2of a single binary relation.Choosing to be a pre-Hilbert space whose lattice of orthoclosed subspaces is not orthomodular, we obtain our desired conclusion. In this regard we may note the demonstration by Amemiya and Araki [1] that orthomodularity of the lattice of orthoclosed subspaces is necessary and sufficient for a pre-Hilbert space to be metrically complete, and hence be a Hilbert space. Metric completeness being a notoriously nonelementary property, our result is only to be expected (note also the parallel with the elementary L2-equivalence of the natural order (Q, <) of the rationals and its metric completion to the reals (R, <)).To derive (1), something stronger is proved, viz. that (, ⊥) is an elementary substructure of (, ⊥).
Global quantification in Zermelo-Fraenkel set theory
Authors: Mayberry John 
Published: May 2006

My aim here is to investigate the role of global quantifiers—quantifiers ranging over the entire universe of sets—in the formalization of Zermelo-Fraenkel set theory. The use of such quantifiers in the formulas substituted into axiom schemata introduces, at least prima facie, a strong element of impredicativity into the thapry. The axiom schema of replacement provides an example of this. For each instance of that schema enlarges the very domain over which its own global quantifiers vary. The fundamental question at issue is this: How does the employment of these global quantifiers, and the choice of logical principles governing their use, affect the strengths of the axiom schemata in which they occur?I shall attack this question by comparing three quite different formalizations of the intuitive principles which constitute the Zermelo-Fraenkel system. The first of these, local Zermelo-Fraenkel set theory (LZF), is formalized without using global quantifiers. The second, global Zermelo-Fraenkel set theory (GZF), is the extension of the local theory obtained by introducing global quantifiers subject to intuitionistic logical laws, and taking the axiom schema of strong collection (Schema XII, §2) as an additional assumption of the theory. The third system is the conventional formalization of Zermelo-Fraenkel as a classical, first order theory. The local theory, LZF, is already very strong, indeed strong enough to formalize any naturally occurring mathematical argument. I have argued (in [3]) that it is the natural formalization of naive set theory. My intention, therefore, is to use it as a standard against which to measure the strength of each of the other two systems.
On the ultrafilters and ultrapowers of strong partition cardinals
Authors: Henle J.M. , Kleinberg E.M. , Watro R.J. 
Published: May 2006

A strong partition cardinal is an uncountable well-ordered cardinal κ such that every partition of [κ]κ (the size κ subsets of κ) into less than κ many pieces has a homogeneous set of size κ. The existence of such cardinals is inconsistent with the axiom of choice, and our work concerning them is carried out in ZF set theory with just dependent choice (DC). The consistency of strong partition cardinals with this weaker theory remains an open question. The axiom of determinacy (AD) implies that a large number of cardinals including ℵ1 have the strong partition property. The hypothesis that AD holds in the inner model of constructible sets built over the real numbers as urelements has important consequences for descriptive set theory, and results concerning strong partition cardinals are often applied in this context. Kechris [4] and Kechris et al. [5] contain further information concerning the relationship between AD and strong partition cardinals.We assume familiarity with the basic results on strong partition cardinals as developed in Kleinberg [6], [7], [8] and Henle [2]. Recall that a strong partition cardinal κ is measurable; in fact every stationary subset of κ is measure one under some normal measure on κ. If μ is a countably additive ultrafilter extending the closed unbounded filter on κ, then the length of the ultrapower [κ]κ under the less than almost everywhere μ ordering is again a measurable cardinal. In §1 below we establish a polarized partition property on these measurable cardinals.
On Cantor-Bendixson spectra containing (1,1). II
Authors: Marcja Annalisa , Toffalori Carlo 
Published: May 2006

Let T be a (countable, complete, quantifier eliminable) ω-stable theory; an analysis of T, and consequently a classification of ω-stable theories, can be done by looking at the Boolean algebras B(M) of definable subsets of its countable models M (as usual, we often confuse a definable subset of M with the class of formulas defining it). If M ⊨ T, ∣M∣ = ℵ0, then, for every LM-formula ϕ(v) and for every ordinal α, we define a relation(CB = Cantor-Bendixson, of course) by induction on α:CB-rank ϕ(v) ≥ 0 if ϕ(M) ≠ ∅CB-rank ϕ(v) ≥ λ for λ a limit ordinal, if CB-rank ϕ(v) ≥ for all v < λ;CB-rank ϕ(v)≥ α + 1 if, for all n ∈ ω,(*) there are LM-formulas ϕ0(v), …, ϕn − 1(v) such thatIt is well known that the ω-stability of T implies that, for every consistent LM-formula ϕ(v), there is exactly one ordinal α < ω1 such that CB-rank ϕ(v) ≥ α and CB-rank ϕ(v)≱α + 1. Therefore we define:CB-rank ϕ(v) = αCB-degree ϕ(v) = d if d is the maximal n ∈ ω satisfying (*); andCB-type ϕ(v) = (α, d).
On Scott and Karp trees of uncountable models
Authors: Hyttinen Tapani , Väänänen Jouko 
Published: May 2006

AbstractLet and be two countable relational models of the same first order language. If the models are nonisomorphic, there is a unique countable ordinal α with the property thati.e. and are L∞ω-equivalent up to quantifier-rank α but not up to α + 1. In this paper we consider models and of cardinality ω1 and construct trees which have a similar relation to and as a above. For this purpose we introduce a new ordering T ≪ T′ of trees, which may have some independent interest of its own. It turns out that the above ordinal α has two qualities which coincide in countable models but will differ in uncountable models. Respectively, two kinds of trees emerge from α. We call them Scott trees and Karp trees, respectively. The definition and existence of these trees is based on an examination of the Ehrenfeucht game of length ω1 between and . We construct two models of power ω1 with mutually noncomparable Scott trees.