bluuebunny/crossref_metadata_2025_split huggingface dataset:
Simplicity in effective topology
Authors: Kalantari Iraj , Leggett Anne 
Published: May 2006

The recursion-theoretic study of mathematical structures other thanωis now a field of much activity. Analysis and algebra are two such structures which have been studied for their effective contents. Studies in analysis began with the work of Specker on nonconstructive proofs in analysis [16] and in Lacombe's inspiring notes on relevant notions of recursive analysis [8]. Studies in algebra originated in the work of Frolich and Shepherdson on effective extensions of explicit fields [1] and in Rabin's study of computable fields [15]. Equipped with the richness of modern techniques in recursion theory, Metakides and Nerode [11]–[13] began investigating the effective content of vector spaces and fields; these studies have been extended by Kalantari, Remmel, Retzlaff, Shore and others.Kalantari and Retzlaff [5] began a foundational inquiry into effectiveness in topological spaces. They consider a topological spaceXwith a countable basis ⊿ for the topology. The space isfully effective, that is, the basis elements are coded intoωand the operation of intersection of basis elements and the relation of inclusion among them are both computable. Similar to, the lattice of recursively enumerable (r.e.) subsets ofω, the collection of r.e. open subsets ofXforms a latticeℒ(X)under the usual operations of union and intersection.
On generalized quantifiers in arithmetic
Authors: Morgenstern Carl 
Published: May 2006

In this note we investigate an extension of Peano arithmetic which arises from adjoining generalized quantifiers to first-order logic. Markwald [2] first studied the definability properties of L1, the language of first-order arithmetic, L, with the additional quantifer Ux which denotes “there are infinitely many x such that…. Note that Ux is the same thing as the Keisler quantifier Qx in the ℵ0 interpretation.We consider L2, which is L together with the ℵ0 interpretation of the Magidor-Malitz quantifier Q2xy which denotes “there is an infinite set X such that for distinct x, y ∈ X …”. In [1] Magidor and Malitz presented an axiom system for languages which arise from adding Q2 to a first-order language. They proved that the axioms are valid in every regular interpretation, and, assuming ◊ω1, that the axioms are complete in the ℵ1 interpretation.If we let denote Peano arithmetic in L2 with induction for L2 formulas and the Magidor-Malitz axioms as logical axioms, we show that in we can give a truth definition for first-order Peano arithmetic, . Consequently we can prove in that is Πn sound for every n, thus in we can prove the Paris-Harrington combinatorial principle and the higher-order analogues due to Schlipf.
On forcing without the continuum hypothesis
Authors: Abraham Uri 
Published: May 2006

ℵ2. One of the first examples of the forcing method is cardinal collapsing (A. Levy, see [5]), for example, collapsing ℵ2 to ℵ1: the poset P is the collection of all countable functions from a countable ordinal into ℵ2. As is well known, in VP, , and because P is closed under union of countable chains, remains a cardinal and, in fact, no new countable sets are added. But to prove that remains a cardinal we need to conclude ∣P∣ ≤ ℵ2 and hence ℵ3 is not collapsed. If it has been observed that is actually collapsed in VP. Hence the following theorem, which makes no assumptions on the continuum, is relevant.1. Theorem. There is a poset R such that in VR ℵ2 becomes of cardinality ℵ1, but ℵ1 and the cardinals above ℵ2 are not collapsed.
κ-Suslin logic
Authors: Green Judy 
Published: May 2006

An analogue of a theorem of Sierpinski about the classical operation () provides the motivation for studying κ-Suslin logic, an extension of Lκ+ω which is closed under a propositional connective based on (). This theorem is used to obtain a complete axiomatization for κ-Suslin logic and an upper bound on the κ-Suslin accessible ordinals (for κ = ω these results are due to Ellentuck [E]). It also yields a weak completeness theorem which we use to generalize a result of Barwise and Kunen [B-K] and show that the least ordinal not H(κ+) recursive is the least ordinal not κ-Suslin accessible.We assume familiarity with lectures 3, 4 and 10 of Keisler's Model theory for infinitary logic [Ke]. We use standard notation and terminology including the following.Lκ+ω is the logic closed under negation, finite quantification, and conjunction and disjunction over sets of formulas of cardinality at most κ. For κ singular, conjunctions and disjunctions over sets of cardinality κ can be replaced by conjunctions and disjunctions over sets of cardinality less than κ so that we can (and will in §2) assume the formation rules of Lκ+ω allow conjunctions and disjunctions only over sets of cardinality strictly less than κ whenever κ is singular.
Some independence results for Peano arithmetic
Authors: Paris J. B. 
Published: May 2006

In this paper we shall outline a purely model theoretic method for obtaining independence results for Peano's first order axioms (P). The method is of interest in that it provides for the first time elementary combinatorial statements about the natural numbers which are not provable in P. We give several examples of such statements.Central to this exposition will be the notion of an indicator. Indicators were introduced by L. Kirby and the author in [3] although they had occurred implicitly in earlier papers, for example Friedman [1]. The main result on indicators which we shall need (Lemma 1) was proved by Laurie Kirby and the author in the summer of 1976 but it was not until early in the following year that the author realised that this lemma could be used to give independence results.The first combinatorial independence results obtained were essentially statements about certain finite games and consequently were not immediately meaningful (see Example 2). This shortcoming was remedied by Leo Harrington who, upon hearing an incorrect version of our results, noticed a beautifully simply independent combinatorial statement. We outline this result in Example 3. An alternative, more detailed, proof may be found in [5].Clearly Laurie Kirby and Leo Harrington have made a very significant contribution to this paper and we wish to express our sincere thanks to them.
Set theory with a filter quantifier
Authors: Kaufmann Matt 
Published: May 2006

The incompleteness of ZF set theory leads one to look for natural extensions of ZF in which one can prove statements independent of ZF which appear to be “true”. One approach has been to add large cardinal axioms. Or, one can investigate second-order expansions like Kelley-Morse class theory, KM. In this paper we look at a set theory ZF(aa), with an added quantifier aa which ranges over ordinals. The “aa” stands for “almost all”, and although we will consider interpretations in terms of the closed unbounded filter on a regular cardinal κ, we will consider other interpretations also.We start in §1 by giving the axioms for the theory ZF(aa) and presenting a completeness theorem which gives a model-theoretic definition of ZF(aa). In §2 we investigate set theory with a satisfaction predicate and interpret it in a fragment of ZF(aa). In §3 we generalize the methods of §2 to obtain a hierarchy of satisfaction predicates. We use these predicates to prove reflection theorems, as well as to prove the consistency of certain fragments of ZF(aa). Next, in §4 we discuss expandability of models of ZF to models of fragments of ZF(aa) and of Kelley-Morse. We conclude in §5 with a discussion of an extension ZF(aa) + DET of ZF(aa) in which the quantifier aa is self-dual.
High and low Kleene degrees of coanalytic sets
Authors: Simpson Stephen G. , Weitkamp Galen 
Published: May 2006

We say that a set A of reals is recursive in a real y together with a set B of reals if one can imagine a computing machine with an ability to perform a countably infinite sequence of program steps in finite time and with oracles for B and y so that decides membership in A for any real x input to by way of an oracle for x. We write A ≤ yB. A precise definition of this notion of recursion was first considered in Kleene [9]. In the notation of that paper, A ≤yB if there is an integer e so that χA(x) = {e}(x y, χB, 2E). Here χA is the characteristic function of A. Thus Kleene would say that A is recursive in (y, B, 2E), where 2E is the existential integer quantifier.Gandy [5] observes that the halting problem for infinitary machines such as , as in the case of Turing machines, gives rise to a jump operator for higher type recursion. Thus given a set B of reals, the superjump B′ of B is defined to be the set of all triples 〈e, x, y〉 such that the eth machine with oracles for y and B eventually halts when given input x. A set A is said to be semirecursive in y together with B if for some integer e, A is the cross section {x: 〈e, x, y 〉 ∈ B′}. In Kleene [9] it is demonstrated that a set A is semirecursive in y alone if and only if it is
The countably based functionals
Authors: Hartley John P. 
Published: May 2006

In [5], Kleene extended previous notions of computations to objects of higher finite type in the maximal type-structure of functionals given by:Tp(0) = N = the natural numbers,Tp(n + 1) = NTp(n) = the set of total maps from Tp(n) to N.He gave nine schemata, S1–S9, for describing algorithms for computations from a finite list of functionals, and indices to denote these algorithms. It is generally agreed that S1-S9 give a natural concept of computations in higher types.The type-structure of countable functions, Ct(n) for n ϵ N, was first developed by Kleene [6] and Kreisel [7]. It arises from the notions of ‘constructivity’, and has been extensively studied as a domain for higher type recursion theory. Each countable functional is globally described by a countable amount of information coded in its associate, and it is determined locally by a finite amount of information about its argument. The countable functionals are well summarised in Normann [9], and treated in detail in Normann [8].The purpose of this paper is to discuss a generalisation of the countable functionals, which we shall call the countably based functions, Cb(n) for n ϵ N. It is suggested by the notions of ‘predicativity’, in which we view N as a completed totality, and build higher types on it in a constructive manner. So we shall allow quantification over N and include application of 2E in our schemata. Each functional is determined locally by a countable amount of information about its argument, and so is globally described by a continuum of information coded in its associate, which will now be a type-2 object. This generalisation, obtained via associates, was proposed by Wainer, and seems to reflect topological properties of the countable functionals.
On a combinatorial property of menas related to the partition property for measures on supercompact cardinals
Authors: Kunen Kenneth , Pelletier Donald H. 
Published: May 2006

AbstractT.K. Menas [4, pp. 225–234] introduced a combinatorial property Χ(μ) of a measure μ on a supercompact cardinal κ and proved that measures with this property also have the partition property. We prove here that Menas' property is not equivalent to the partition property. We also show that if a is the least cardinal greater than κ such that Pκα bears a measure without the partition property, then α is inaccessible and -indescribable.
Countable functionals and the projective hierarchy
Authors: Normann Dag 
Published: May 2006

Kleene [7] and Kreisel [8] defined independently the countable (continuous) functionals. Kleene [7] defined the countable functionals of type k to be total functionals of type k acting in a continuous way when restricted to countable arguments of type k − 1. He also defined the associates for countable functionals. They are functions α: N → N containing information about how the functional acts on countable arguments. Kleene [7] showed that the countable functionals are closed under the computations derived from S1–S9 of his paper [6], and that every computable functional has a recursive associate.Kreisel defined the continuous functionals to be equivalence-classes of associates. By his definition it is meaningless to let a continuous functional act upon anything but continuous arguments.One disadvantage of Kleene's approach is that two different functionals may have the same associates We will later see that there may be two functionals φ1 and φ2 with the same associates but such that the relationsare not the same.In more recent papers on the countable functionals it is normal to regard the hierarchy 〈Ct(k)〉kϵN of countable functionals as a type-structure such that the functionals in Ct(k + 1) are maps from Ct(k) to N(Ct(0) = N), see e.g. Bergstra [1] and Gandy and Hyland [3].We will then enjoy the streamlined formalism of a type-structure in which S1–S9 have meaning, but avoid the ambiguities of Kleene's original approach.We will presuppose a brief familiarity with the theory of the countable functionals.
Discontinuities of provably correct operators on the provably recursive real numbers
Authors: Collins William J. , Young Paul 
Published: May 2006

AbstractIn this paper we continue, from [2], the development of provably recursive analysis, that is, the study of real numbers defined by programs which can be proven to be correct in some fixed axiom systemS. In particular we develop the provable analogue of an effective operator on the setof recursive real numbers, namely, a provably correct operator on the setof provably recursive real numbers. In Theorems 1 and 2 we exhibit a provably correct operator onwhich is discontinuous at 0; we thus disprove the analogue of the Ceitin-Moschovakis theorem of recursive analysis, which states that every effective operator onis (effectively) continuous. Our final theorems show, however, that no provably correct operator oncan be proven (inS) to be discontinuous.
Algebraic semantics for quasi-classical modal logics
Authors: Blok W.J. , Köhler P. 
Published: May 2006

A well-known result, going back to the twenties, states that, under some reasonable assumptions, any logic can be characterized as the set of formulas satisfied by a matrix 〈,F〉, whereis an algebra of the appropriate type, andFa subset of the domain of, called the set of designated elements. In particular, every quasi-classical modal logic—a set of modal formulas, containing the smallest classical modal logicE, which is closed under the inference rules of substitution and modus ponens—is characterized by such a matrix, wherenow is a modal algebra, andFis a filter of. If the modal logic is in fact normal, then we can do away with the filter; we can study normal modal logics in the setting of varieties of modal algebras. This point of view was adopted already quite explicitly in McKinsey and Tarski [8]. The observation that the lattice of normal modal logics is dually isomorphic to the lattice of subvarieties of a variety of modal algebras paved the road for an algebraic study of normal modal logics. The algebraic approach made available some general results from Universal Algebra, notably those obtained by Jónsson [6], and thereby was able to contribute new insights in the realm of normal modal logics [2], [3], [4], [10].The requirement that a modal logic be normal is rather a severe one, however, and many of the systems which have been considered in the literature do not meet it. For instance, of the five celebrated modal systems, S1–S5, introduced by Lewis, S4 and S5 are the only normal ones, while only SI fails to be quasi-classical. The purpose of this paper is to generalize the algebraic approach so as to be applicable not just to normal modal logics, but to quasi-classical modal logics in general.
The relative expressive power of some logics extending first-order logic
Authors: Cowles John 
Published: May 2006

In recent years there has been a proliferation of logics which extend first-order logic, e.g., logics with infinite sentences, logics with cardinal quantifiers such as “there exist infinitely many…” and “there exist uncountably many…”, and a weak second-order logic with variables and quantifiers for finite sets of individuals. It is well known that first-order logic has a limited ability to express many of the concepts studied by mathematicians, e.g., the concept of a wellordering. However, first-order logic, being among the simplest logics with applications to mathematics, does have an extensively developed and well understood model theory. On the other hand, full second-order logic has all the expressive power needed to do mathematics, but has an unworkable model theory. Indeed, the search for a logic with a semantics complex enough to say something, yet at the same time simple enough to say somethingabout, accounts for the proliferation of logics mentioned above. In this paper, a number of proposed strengthenings of first-order logic are examined with respect to their relative expressive power, i.e., given two logics, what concepts can be expressed in one but not the other?For the most part, the notation is standard. Most of the notation is either explained in the text or can be found in the book [2] of Chang and Keisler. Some notational conventions used throughout the text are listed below: the empty set is denoted by ∅.
Twilight graphs
Authors: Dekker J. C. E. 
Published: May 2006

AbstractThis paper deals primarily with countable, simple, connected graphs and the following two conditions which are trivially satisfied if the graphs are finite:(a) there is an edge-recognition algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to decide whether they are adjacent,(b) there is a shortest path algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to find a minimal path joining them.A graph G = ‹ν, η› with ν as set of vertices and η as set of edges is an α-graph if it satisfies (a); it is an ω-graph if it satisfies (b). G is called r.e. (isolic) if the sets ν and η are r.e. (isolated). While every ω-graph is an α-graph, the converse is false, even if G is r.e. or isolic. Several basic properties of finite graphs do not generalize to ω-graphs. For example, an ω-tree with more than one vertex need not have two pendant vertices, but may have only one or none, since it may be a 1-way or 2-way infinite path. Nevertheless, some elementary propositions for finite graphs G = ‹ν, η› with n = card(ν), e = card(η), do generalize to isolic ω-graphs, e.g., n − 1 ≤ e ≤ n(n − 1)/2. Let N and E be the recursive equivalence types of ν and η respectively. Then we have for an isolic α-tree G = ‹ν, η›: N = E + 1 iff G is an ω-tree. The theorem that every finite graph has a spanning tree has a natural, effective analogue for ω-graphs.The structural difference between isolic α-graphs and isolic ω-graphs will be illustrated by: (i) every infinite graph is isomorphic to some isolic α-graph; (ii) there is an infinite graph which is not isomorphic to any isolic ω-graph.An isolic α-graph is also called a twilight graph. There are c such graphs, c denoting the cardinality of the continuum.
Analysis without actual infinity
Authors: Mycielski Jan 
Published: May 2006

AbstractWe define a first-order theory FIN which has a recursive axiomatization and has the following two properties. Each finite part of FIN has finite models. FIN is strong enough to develop that part of mathematics which is used or has potential applications in natural science. This work can also be regarded as a consistency proof of this hitherto informal part of mathematics. In FIN one can count every set; this permits one to prove some new probabilistic theorems.
A consistent prepositional logic without any finite models
Authors: McKay C. G. 
Published: May 2006

Some propositional logics (e.g. the classical system) can be characterized by a finite model, while others (e.g. Heyting's) which have the finite model property (FMP) can be characterized by an infinite set of finite models. Still others (e.g. certain extensions of Heyting's logic) which lack the FMP can only be characterized by a set of models, at least one of which is infinite. Yet all these logics admit finite models even though they may not be characterized by them. (For example, they all admit the 2-element Boolean algebra as a model in the sense that all their theorems are valid on that algebra when the propositional connectives are interpreted in the usual manner.) The object of the present paper is to give a (not too artificial) example of a propositional logic which is consistent and which admits only infinite models. It therefore lacks the FMP in a very strong sense. Such a propositional logic, I shall call hyperinfinite. The existence of hyperinfinite logics was already plausible from a result in abstract algebra which says that there are varieties of algebras of which the only finite element is the trivial algebra (see [3]).I wish to thank Professor A. S. Troelstra, Amsterdam, for comments on an early version of this paper. The constructive criticism of two anonymous referees has also been useful.The hyperinfinite propositional logic to be described is obtained from Positive Logic—the negative-free part of Heyting's logic—by adjoining certain axioms which govern the use of a unary modal connective.
Prikry forcing at κ+ and beyond
Authors: Mitchell William 
Published: May 2006

If U is a normal measure on κ then we can add indiscernibles for U either by Prikry forcing [P] or by taking an iterated ultrapower which will add a sequence of indiscernibles for over M. These constructions are equivalent: the set C of indiscernibles for added by the iterated ultrapower is Prikry generic for [Mat]. Prikry forcing has been extended for sequences of measures of length by Magidor [Mag], and his method readily extends to . In this case the measure U is replaced by a sequence of measures and the set C of indiscernibles is replaced by a system of indiscernibles for : is a function such that (κ, β) is a set of indiscernibles for (κ, β) for each . The equivalence between forcing and iterated ultra-powers still holds true for such sequences: there is an interated ultrapower j: V → M (which is defined in detail later in this paper) such that the system of indiscernibles for j() constructed by j is Magidor generic over M.The construction of the system of indiscernibles works equally well for o(κ) ≧ κ+. Radin has defined a variant of Prikry forcing which also works for o(κ) > κ+ ([R]; see also [Mi82] where Radin forcing is applied specifically to sequences of measures, rather than to hypermeasures as in Radin's paper), but Radin's forcing is weaker than Magidor's extension of Prikry forcing in the sense that the system of indiscernibles generated by the interated ultrapower is not Radin generic for j(), but only the set . That is, an indiscernible does not belong to a specific measure, but only to the whole sequence of measures on the cardinal κ.