bluuebunny/crossref_metadata_2025_split huggingface dataset:
On the nonexistence of certain normal forms in the logic of provability
Authors: Boolos George 
Published: May 2006

G is the system of propositional modal logic whose axioms are all tautologies and all sentences □(A → B) → (□A → □B) and □(□A → A) → □A and whose rules are modus ponens and necessitation. For the connections between G and provability in formal systems, see [3] and [2].A letterless sentence is a modal sentence that contains no sentence letters at all. In [1] the author showed (in effect) the existence of simple normal forms in G for letterless sentences: every letterless sentence is equivalent in G to a truth-functional compound of sentences ⋄r ⊤ (⋄0B = B; ⋄r+1B = ⋄ ⋄r+1 B. ⊤ is the 0-ary connective that is always evaluated as true; we assume that the language contains ⊤ as a primitive.)A family of sets {Hn}n∈ω of modal sentences that contain no sentence letters other than some fixed one (say p) was introduced by Solovay in [3]: H0 = the set of sentences equivalent in G to one of p, −p, ⊤, and ⊥; Hn+x = the set of sentences equivalent in G to a truth-functional combination of sentences ⋄rB, where r ∈ ω and B ∈ Hn. (This definition of the Hn's differs inessentially from the one given in [3].) Since r may = 0, Hn ⊆ Hn+1 and thus if m ≤ n, Hm ⊆ Hn; every modal sentence containing no letter other than p is in some Hn. It follows from the normal form theorem for letterless sentences that every letterless sentence is in H1.In [3] Solovay stated without proof a result about the sets Hn: for every n, Hn ⊊ Hn+1; equivalently, for every n, there is a sentence containing no letter other than p not in Hn. Thus the existence of a normal form for letterless sentences is a very special feature of these sentences, for Solovay's result shows that normal forms like those obtainable for letterless sentences are not to be found in general. He takes this result to be one reason for regarding the Lindenbaum algebra in G of sentences containing no letter other than p as much more complicated than that of letterless sentences.
A lift of a theorem of Friedberg: A Banach-Mazur functional that coincides with no α-recursive functional on the class of α-recursive functions
Authors: di Paola Robert A. 
Published: May 2006

AbstractR. M. Friedberg demonstrated the existence of a recursive functional that agrees with no Banach-Mazur functional on the class of recursive functions. In this paper Friedberg's result is generalized to both α-recursive functionals and weak α-recursive functionals for all admissible ordinals α such that λ < α*, where α* is the Σ1-projectum of α and λ is the Σ2-cofinality of α. The theorem is also established for the metarecursive case, α = ω1, where α* = λ = ω.
Theories with recursive models
Authors: Lerman Manuel , Schmerl James H. 
Published: May 2006

A structure is recursive if the set of quantifier-free sentences in the complete diagram ⊿() of is recursive. It has been known for some time that every decidable theory has a recursive model. In fact, every decidable theory has a decidable model (that is a model such that ⊿() is recursive). In this paper we find other conditions which imply that a theory have a recursive model.In §1 we study the relation between an ℵ0-categorical theory T having a recursive model and the complexity of the quantificational hierarchy of that theory. We let ∃0 denote the set of quantifier-free sentences, and let ∃n÷1 denote the set of sentences beginning with an existential quantifier and having n alternations of quantifiers. (∀n is defined analogously.) Then we show that if T is an arithmetical ℵ0-categorical theory such that T ⋂ ∃n÷2 is Σn÷10 for each n < ω, then T has a recursive model. We show that this is a best possible result by giving an example of a ⊿n÷20 ℵ0-categorical theory T such that T ⋂ ∃n÷1 is recursive yet T has no recursive model.In §2 we consider the theory of trees. Ershov [1] had proved that every Σ10 theory of trees has a recursive model. We show this to be best possible by giving an example of a ⊿20 theory of trees which has no recursive model.
Sheaves and Boolean valued model theory
Authors: Loullis George 
Published: May 2006

In recent years model theorists have been studying various sheaf-theoretic notions as they apply to model theory. For quite a while however, a sheaf of structures was considered to be just a local homeomorphism between topological spaces such that each stalk Sx = p−1(x) is a model-theoretic structure and such that certain maps are continuous. Some of the model-theoretic work done with this notion of a sheaf of structures are the papers by Carson [2] and Macintyre [7]. Soon came the idea of considering a sheaf of structures not just as a collection of structures glued together in some continuous way, but rather as some sort of generalized structure. A significant model-theoretic study of sheaves in this new sense became possible only after the development of the theory of topoi. As F.W. Lawvere pointed out in [6], this represents the advance of mathematics (in our case the advance of model theory) from metaphysics to dialectics.A topos is the rather ingenious evolution of the notion of a Grothendieck topos [13]. It provides us with the idea that an object of a topos (e.g. the topos of sheaves over a topological space) may be thought of as a generalized set. Furthermore, all first-order logical operations have an interpretation in a topos, hence we may talk about generalized structures. Angus Macintyre suggested that some of his model-theoretic results about sheaves of structures may be understood better and perhaps simplified by doing model theory inside a topos of sheaves.
Adjoining dominating functions
Authors: Baumgartner James E. , Dordal Peter 
Published: May 2006

AbstractIf dominating functions in ωω are adjoined repeatedly over a model of GCH via a finite-support c.c.c. iteration, then in the resulting generic extension there are no long towers, every well-ordered unbounded family of increasing functions is a scale, and the splitting number (and hence the distributivity number ) remains at ω1.
Some new natural α-re-degrees
Authors: Bailey Colin G. 
Published: May 2006

AbstractIf α is a singular cardinal (either real or fake) in L, I exhibit many natural α-re subsets, defined uniformly from the ⊿1 subsets of a. If α. is a true cardinal this provides an uppersemilattice (usl) embedding from the lattice of ⊿1 subsets of α into the usl of α-re-degrees. It will also be shown that this embedding cannot be extended to the Σ1 subsets of α.
Sequential discreteness and clopen-I-Boolean classes
Authors: Dougherty Randall 
Published: May 2006

Kantorovich and Livenson [6] initiated the study of infinitary Boolean operations applied to the subsets of the Baire space and related spaces. It turns out that a number of interesting collections of subsets of the Baire space, such as the collection of Borel sets of a given type (e.g. the Fσ sets) or the collection of analytic sets, can be expressed as the range of an ω-ary Boolean operation applied to all possible ω-sequences of clopen sets. (Such collections are called clopen-ω-Boolean.) More recently, the ranges of I-ary Boolean operations for uncountable I have been considered; specific questions include whether the collection of Borel sets, or the collection of sets at finite levels in the Borel hierarchy, is clopen-I-Boolean.The main purpose of this paper is to give a characterization of those collections of subsets of the Baire space (or similar spaces) that are clopen-I-Boolean for some I. The Baire space version can be stated as follows: a collection of subsets of the Baire space is clopen-I-Boolean for some I iff it is nonempty and closed downward and σ-directed upward under Wadge reducibility, and in this case we may take I = ω2. The basic method of proof is to use discrete subsets of spaces of the form K2 to put a number of smaller clopen-I-Boolean classes together to form a large one. The final section of the paper gives converse results indicating that, at least in some cases, ω2 cannot be replaced by a smaller index set.
Transfer principles for pseudo real closed e-fold ordered fields
Authors: Basarab Şerban A. 
Published: May 2006

In his famous paper [1] on the elementary theory of finite fields Ax considered fields K with the property that every absolutely irreducible variety defined over K has K-rational points. These fields have been called pseudo algebraically closed (pac) and also regularly closed, and extensively studied by Jarden, Éršov, Fried, Wheeler and others, culminating with the basic works [8] and [11].The above algebraic-geometric definition of pac fields can be put into the following equivalent model-theoretic version: K is existentially complete (ec) relative to the first order language of fields into each regular field extension of K. It has been this characterization of pac fields which the author extended in [2] to ordered fields. An ordered field (K, <) is called in [2] pseudo real closed (prc) if (K, <) is ec in every ordered field extension (L, <) with L regular over K. The concept of pre ordered field has also been introduced by McKenna in his thesis [15] by analogy with the original algebraic-geometric definition of pac fields.Given a positive integer e, a system K = (K; P1, …, Pe), where K is a field and P1, …, Pe are orders of K (identified with the corresponding positive cones), is called an e-fold ordered field (e-field). In his thesis [9] van den Dries developed a model theory for e-fields. The main result proved in [9, Chapter II] states that the theory e-OF of e-fields is model con. panionable, and the models of the model companion e-OF are explicitly described.
Pragmatic truth and approximation to truth
Authors: Mikenberg Irene , da Costa Newton C. A. , Chuaqui Rolando 
Published: May 2006

There are several conceptions of truth, such as the classical correspondence conception, the coherence conception and the pragmatic conception. The classical correspondence conception, or Aristotelian conception, received a mathematical treatment in the hands of Tarski (cf. Tarski [1935] and [1944]), which was the starting point of a great progress in logic and in mathematics. In effect, Tarski's semantic ideas, especially his semantic characterization of truth, have exerted a major influence on various disciplines, besides logic and mathematics; for instance, linguistics, the philosophy of science, and the theory of knowledge.The importance of the Tarskian investigations derives, among other things, from the fact that they constitute a mathematical, formal mark to serve as a reference for the philosophical (informal) conceptions of truth. Today the philosopher knows that the classical conception can be developed and that it is free from paradoxes and other difficulties, if certain precautions are taken.We believe that is not an exaggeration if we assert that Tarski's theory should be considered as one of the greatest accomplishments of logic and mathematics of our time, an accomplishment which is also of extraordinary relevance to philosophy, as we have already remarked.In this paper we show that the pragmatic conception of truth, at least in one of its possible interpretations, has also a mathematical formulation, similar in spirit to that given by Tarski to the classical correspondence conception.
On the proof theory of the intermediate logic MH
Authors: Seldin Jonathan P. 
Published: May 2006

AbstractA natural deduction formulation is given for the intermediate logic called MH by Gabbay in [4]. Proof-theoretic methods are used to show that every deduction can be normalized, that MH is the weakest intermediate logic for which the Glivenko theorem holds, and that the Craig-Lyndon interpolation theorem holds for it.
Supercompact cardinals, trees of normal ultrafilters, and the partition property
Authors: Barbanel Julius B. 
Published: May 2006

AbstractSuppose κ is a supercompact cardinal. It is known that for every λ ≥ κ, many normal ultrafilters on Pκ(λ) have the partition property. It is also known that certain large cardinal assumptions imply the existence of normal ultrafilters without the partition property. In [1], we introduced the tree T of normal ultrafilters associated with κ. We investigate the distribution throughout T of normal ultrafilters with and normal ultrafilters without the partition property.
Small decidable sheaves
Authors: Blass Andreas , Scedrov Andre 
Published: May 2006

Fred Richman conjectured that the following principle is not constructive:(*) If A is a decidable subset of the set N of natural numbers and if, for every decidable subset B of N, either A ⊆ B or A ⊆ N − B, then, for some n ∈ N, A ⊆ {n}.A set A of natural numbers is called decidable if ∀n(n ∈ A ∨ ⌉ (n ∈ A)) holds. In recursive models, this agrees with the recursion-theoretic meaning of decidability. In other contexts, “complemented” and “detachable” are often used.Richman's conjecture was motivated by the problem of uniqueness of divisible hulls of abelian groups in constructive algebra. Richman showed that a countable discrete abelian p-group G has a unique (up to isomorphism over G) divisible hull if the subgroup pG is decidable. He also showed that the converse implies.We confirm the nonconstructive nature of by showing (in §1) that it is not provable in intuitionistic set theory, IZF. Thus, in the models we construct, there are countable discrete abelian p-groups G whose divisible hulls are unique but whose subgroups pG are not decidable.Our models do not satisfy further conditions imposed by Richman, namely Church's Thesis and Markov's Principle, so the full conjecture remains an open problem. We do, however, show (in §2) how to embellish our first model so that the fan theorem (i.e., compactness of 2N) fails. (Church's Thesis implies the stronger statement that the negation of the fan theorem holds.)Our models will be constructed by the method of sheaf semantics [1], [3]. That is, we shall construct Grothendieck topoi in whose internal logic fails.
A simple solution to Friedman's fourth problem
Authors: Caicedo Xavier 
Published: May 2006

AbstractIt is shown that Friedman's problem, whether there exists a proper extension of first order logic satisfying the compactness and interpolation theorems, has extremely simple positive solutions if one considers extensions by generalized (finitary) propositional connectives. This does not solve, however, the problem of whether such extensions exist which are also closed under relativization of formulas.
On the orbits of hyperhypersimple sets
Authors: Maass Wolfgang 
Published: May 2006

AbstractThis paper contributes to the question of under which conditions recursively enumerable sets with isomorphic lattices of recursively enumerable-supersets are automorphic in the lattice of all recursively enumerable sets. We show that hyperhypersimple sets (i.e. sets where the recursively enumerable supersets form a Boolean algebra) are automorphic if there is a -definable isomorphism between their lattices of supersets. Lerman, Shore and Soare have shown that this is not true if one replaces by .
On the compactness of some Boolean algebras
Authors: Cichoń Jacek 
Published: May 2006

We say that the Boolean algebra B is λ-compact, where λ is a cardinal number, if for every family Z ⊆ B∖{0} of power at most λ, if inf Z = 0 then for some finite subfamily Z0 ⊆ Z we have inf Z0 = 0.On the set of all finite subsets of a cardinal number κ, which is denoted [κ]<ω, the sets of the form for any p Є [κ]<ω generate the filter Tκ.This filter is a standard example of a κ-regular filter (see [2]). Because of the importance of κ-regular filters in studying the saturatedness of ultraproducts and reduced products by model-theoretic methods, the question of compactness of the algebra Bκ = P([κ]<ω/Tκ was natural. This question in the most optimistical way was formulated by M. Benda [1, Problem 5c]: is the algebra Bκω-compact for every uncountable κ?In this paper we show that for most of the cardinal numbers which are greater or equal to 2ω the algebra Bκ is not ω-compact. Hence, in view of obtained results, the following question appears: does there exist an uncountable κ such that the algebra Bκ is κ-compact?We use standard set-theoretical notations. CH denotes the Continuum Hypothesis, GCH denotes the General Continuum Hypothesis and MA denotes Martin's Axiom.
Generic graph construction
Authors: Baumgartner James E. 
Published: May 2006

AbstractIt is shown that if ZF is consistent, then so is ZFC + GCH + “There is a graph with cardinality ℵ2 and chromatic number ℵ2 such that every subgraph of cardinality ≤ ℵ1, has chromatic number ≤ ℵ0”. This partially answers a question of Erdös and Hajnal.
Regularity in models of arithmetic
Authors: Mills George , Paris Jeff 
Published: May 2006

AbstractThis paper investigates the quantifier “there exist unboundedly many” in the context of first-order arithmetic. An alternative axiomatization is found for Peano arithmetic based on an axiom schema of regularity: The union of boundedly many bounded sets is bounded. We also obtain combinatorial equivalents of certain second-order theories associated with cuts in nonstandard models of arithmetic.
Functors and ordinal notations. I: A functorial construction of the veblen hierarchy
Authors: Girard Jean-Yves , Vauzeilles Jacqueline 
Published: May 2006

This paper is the first of several works: the matter is the systematic rewriting of usual results of ordinal notations, using Π½-logic. The purpose of these articles is already realized in Π½-logic, in a relatively abstract form; also, they are examples for Π½-logic. The first and second articles in this series are complete versions of unpublished results that one of authors had announced in 1976.Veblen introduced his hierarchy in 1908. The hierarchy has since been widely used in proof theory; in fact, what is actually needed is the more natural hierarchy: , with (not necessarily a Cantor normal form) and K the Veblen hierarchy.We shall show:i) φ is in fact a two-variables functor (denoted by V in the text) commuting with direct limits and with pull-backs.ii) The property of commutation with pull-backs permits one to give a representation of each ordinal x < φα(0) by means of a finite sequence of ordinals < α. This representation is independent of α it is ⊆ x, and can be used in the building up of notations systems. This representation is the “blowing-up” of the Cantor normal form, and it corresponds exactly to the denotation of ordinals < φα(0) by means of the functions (φβ)β<α.
Functors and ordinal notations. IV: The Howard ordinal and the functor ∧.
Authors: Vauzeilles Jacqueline 
Published: May 2006

In this paper, we prove a result that J. Y. Girard has conjectured for the last few years. That is,This result is part of a study of ordinal notations. For the proof, we use some concepts introduced in Parts I, II and III of this article (see [GV1], [GV2] and [V]); in particular, in Part III (see [V]) we defined the category GAR of gardens (of type Ω), and we have shown that there is an isomorphism between GAR and the category DIL Ω of dilators which send Ω into Ω. To describe this isomorphism, we defined a functor SYN from GAR to DIL Ω and a functor DEC from DIL Ω to GAR which are inverse to each other. The functor SYN is constructed by induction on the height x of the garden Jx, iterating, at each step of cofinality Ω, the operation UN (unification of variables; see [G1, Chapter 3]). Here, we define the functor S⊿ from GAR to DIL Ω: this construction is very close to that of SYN, but we iterate, at each step of cofinality Ω, the operation ⊿ (identification of variables; see [G, Chapter 3]). Technically, the definition of S⊿ is easier and more natural than that of SYN (as ⊿ is easier than UN) but is not inversible (as ⊿); for example, if we consider the (regular) garden GεΩ+1 introduced in [GV2],S⊿(GεΩ+1) is exactly the dilator N = ⋃0<n<ωNn, with N1 = 2 + Id, and , but we are incapable of expressing SYN(GεΩ+1).
Universal recursion theoretic properties of r.e. preordered structures
Authors: Montagna Franco , Sorbi Andrea 
Published: May 2006

When dealing with axiomatic theories from a recursion-theoretic point of view, the notion of r.e. preordering naturally arises. We agree that an r.e. preorder is a pair = 〈P, ≤P〉 such that P is an r.e. subset of the set of natural numbers (denoted by ω), ≤P is a preordering on P and the set {〈;x, y〉: x ≤Py} is r.e.. Indeed, if is an axiomatic theory, the provable implication of yields a preordering on the class of (Gödel numbers of) formulas of .Of course, if ≤P is a preordering on P, then it yields an equivalence relation ~P on P, by simply letting x ~Py iff x ≤Py and y ≤Px. Hence, in the case of P = ω, any preordering yields an equivalence relation on ω and consequently a numeration in the sense of [4]. It is also clear that any equivalence relation on ω (hence any numeration) can be regarded as a preordering on ω. In view of this connection, we sometimes apply to the theory of preorders some of the concepts from the theory of numerations (see also Eršov [6]).Our main concern will be in applications of these concepts to logic, in particular as regards sufficiently strong axiomatic theories (essentially the ones in which recursive functions are representable). From this point of view it seems to be of some interest to study some remarkable prelattices and Boolean prealgebras which arise from such theories. It turns out that these structures enjoy some rather surprising lattice-theoretic and universal recursion-theoretic properties.After making our main definitions in §1, we examine universal recursion-theoretic properties of some r.e. prelattices in §2.
The uniqueness of envelopes in ℵ0-categorical, ℵ0-stable structures
Authors: Loveys James 
Published: May 2006

The Classification Theorem for ℵ0-categorical strictly minimal sets says that if H is strictly minimal and ℵ0-categorical, either H has in effect no structure at all or is essentially an affine or projective space over a finite field. Zil′ber, in [Z2], showed that if H were a counterexample to this Classification Theorem it would interpret a rank 2, degree 1 pseudoplane. Cherlin later noticed (see [CHL, Appendices 2 and 3], for the proof) that the Classification Theorem is a consequence of the Classification Theorem for finite simple groups. In [Z4] and [Z5], Zil′ber found a quite different proof of the Classification Theorem using no deep group theory.Meanwhile in [Z3], Zil′ber introduced the notion of envelope in an attempt to prove that no complete totally categorical theory T can be finitely axiomatizable. The idea of the proof was to show that if M is a model of such a T and H ⊆ M is strongly minimal, then an envelope of any sufficiently large finite subset of H is a finite model of any fixed finite subset of T. [Z3] contains an error, which Zil′ber has since corrected (in a nontrivial way).In [CHL], Cherlin, Harrington and Lachlan used the Classification Theorem to expand and reorganize Zil′ber's work. In particular, they generalized most of his work to ℵ0-categorical, ℵ0-stable structures, proved the Morley rank is finite in these structures, and introduced the powerful Coordinatization Theorem (Theorem 3.1 of [CHL]; Proposition 1.14 of the present paper). They also showed that ℵ0-categorical, ℵ0-stable structures are not finitely axiomatizable using a notion of envelope that is the same as Zil′ber's except in one particularly perverse case; [CHL]'s notion of envelope is used throughout the current paper. Peretyat'kin [P] has found an example of an ℵ1-categorical finitely axiomatizable structure.
On the T-degrees of partial functions
Authors: Casalegno Paolo 
Published: May 2006

AbstractLet 〈, ≤ 〉 be the usual structure of the degrees of unsolvability and 〈, ≤ 〉 the structure of the T-degrees of partial functions defined in [7]. We prove that every countable distributive lattice with a least element can be isomorphically embedded as an initial segment of 〈, ≤ 〉: as a corollary, the first order theory of 〈, ≤ 〉 is recursively isomorphic to that of 〈, ≤ 〉. We also show that 〈, ≤ 〉 and 〈, ≤ 〉 are not elementarily equivalent.