bluuebunny/crossref_metadata_2025_split huggingface dataset:
A constructive analysis of RM
Authors: Avron Arnon 
Published: May 2006

The system RM is the most well-understood (and to our opinion, also the most important) system among the logics developed by the Anderson and Belnap school. In this paper we investigate RM from a constructive point of view. For example, we give a new proof of the completeness of RM relative to the Sugihara matrix (first shown by Meyer), a proof in which a p.r. procedure is presented, applying which to a sentence A in RM language yields either a proof of it in RM or a refuting valuation for it in the Sugihara matrix SZ.Two topics dealt with in this work deserve a special attention.a) The admissibility of γ. This is a famous theorem of Meyer and Dunn. In [1] Anderson and Belnap emphasize that “the Meyer-Dunn argument … guarantees the existence of a proof of B, but there is no guarantee that the proof of B is related in any sort of plausible way to the proofs of A and Ā ∨ B.” In §2 we provide such a guarantee for the RM-case. In fact, we give there a direct method of obtaining a proof of B from given proofs of A and Ā ∨ B.b) The relationships betweenRMand its full negation-implication fragment. RM is known ([1, pp. 148–149], and [3]) to be a conservative extension of (Sobociński 3-valued logic; see [4]). Anderson and Belnap admit [1, p. 149] that this fact came to them as a distinct surprise, since RM as a whole is far from being three-valued. In this paper, however, this “surprising” fact appears quite natural (see III.3). In fact, we show that , is the “hard core” of RM, since our proof of the completeness of RM is based in an essential way on the completeness of relative to the Sobociński matrix, and since the Gentzen-type calculus we develop for RM is a direct extension of a similar (but much simpler) calculus for . Because of the importance has in this work, we devote the first section to a constructive investigation of it.We note, finally, that the Gentzen-type calculus mentioned above admits cut-elimination and normal-form techniques. (Such calculi were found till now only for RM without distribution.)
Uncountable master codes and the jump hierarchy
Authors: Lubarsky Robert S. 
Published: May 2006

The Turing jump can easily be iterated any finite number of times. The challenge is posed by by transfinite iterations. a(ω) has an intuitively compelling definition: {‹m, n›: n ∈ a(m)}. Starting with Putnam et al. [1], [2], [9] and culminating in Jockusch-Simpson [8] and Hodes [6], recent work has justified this ω-jump and extended it through .Of great use are the master codes of Jensen [3], [7]. Briefly, a Δn(Lβ)-master code is a complete Δn(Lβ) set of ordinals, with supremum as small as possible. Connections with classical recursion theory are tight. When the Δn(Lβ) master codes are reals, they are Turing equivalent. If a is a Δn(Lβ) MC, then a′ is a Δn + 1(Lβ) MC. Intuitively satisfying transfinite jumps, such as the ω-jump above, produce a Turing jump hierarchy equal to an initial segment of the master codes.Hodes capitalized on these facts by defining 0α, α < , set-theoretically as the degree of the αth MC which is a real, and then proving the equivalence of a jump-theoretic definition of 0α. The successor codes are jumps of their predecessors, and for a limit λ, 0λ is the minimum of a set of degrees associated with {0α: α: < λ}.
Morasses and the Lévy-collapse
Authors: Komjáth P. 
Published: May 2006

For several old problems in combinatorial set theory A. Hajnal and the present author [2] showed that on collapsing a sufficiently Mahlo cardinal to ω1 by the Lévy-collapse one gets a model where these problems are solved in the “counter-example” direction. The authors of [2] have speculated that the theorems of that paper should hold in L, and this, in fact, was shown for some of the results by Todorčević and Velleman [7,8]. The observation that collapsing a large cardinal to ω1 may give rise to L-like constructions is not new. As it was shown long ago by Silver and Rowbottom, there is a Kurepa-tree if a strongly inaccessible cardinal is Lévy-collapsed to ω1. In [5] it is proved that even Silver's W holds in that model. Here we show that even a quagmire exists there, but not necessarily a morass. To be more exact, we show that if κ < λ are the first two strongly inaccessible cardinals, first λ is Lévy-collapsed to κ+, and then κ is Lévy-collapsed to then there is no ω1-morass with built-in diamond in the resulting model (GCH is assumed). If λ is Mahlo, there is not even a morass.Our notations are standard. For excellent survey papers on morass-like principles and their uses in combinatorial set theory see [4,5,6].
Axioms for the set-theoretic hierarchy
Authors: van Aken James 
Published: May 2006

The axioms for Zermelo-Fraenkel (ZF) set theory are an appealing but somewhat arbitrary-seeming assortment. A survey of the axioms does not suffice to reveal the source of their attraction. Accordingly, attempts have been made to ground ZF in principles whose appeal can be felt immediately. These attempts can be classified as follows. First, some of them propose to rest the ZF axioms directly on informal doctrine. The others propose to ground the ZF axioms in other formal axioms that can be regarded as more basic. When the latter approach is taken, ZF continues to draw on informal support, but the draft is made at a more basic level.The same research can be classified in another way, according to the informal diagnosis offered for the paradoxes of set theory. In some cases, the diagnosis is that the paradoxical sets (such as the Russell set) fail to exist only because they would have to be too large; a set that would be sufficiently small must always exist. This is the doctrine of limitation of size. In other cases, the diagnosis is that the paradoxical sets fail to exist only because they would have to lie too high in a certain hierarchy of sets; a set that would lie sufficiently low in the hierarchy must always exist. This is the doctrine of the hierarchy. The present paper will investigate the latter doctrine, with the doctrine of size making a brief appearance at the end.
Degrees coded in jumps of orderings
Authors: Knight Julia F. 
Published: May 2006

All structures to be considered here have universe ω, and all languages come equipped with Gödel numberings. If is a structure, then D(), the open diagram of , can be thought of as a subset of ω, and it makes sense to talk about the Turing degree deg(D()). This depends on the presentation as well as the isomorphism type of .For example, consider the ordering = (ω, <). For any B ⊆ ω, it is possible to code B in a copy of as follows: Let π be the permutation of ω such that for each n ∈ ω, π leaves 2n and 2n + 1 fixed if n ∈ B and switches 2n with 2n + 1 if n ∉ B. Let be the copy of such that ≃π. Then n ∈ B iff the sentence 2n < 2n + 1 is in D(). In §4, this idea will be used to show that for any structure that is not completely trivial, {deg(D()): ≃ } is closed upwards.It would be satisfying to have a way of assigning Turing degrees to structures such that the degree assigned to a given structure measured the recursion-theoretic complexity of the isomorphism type and was independent of the presentation. Jockusch suggested the following.
Partitions and filters
Authors: Matet P. 
Published: May 2006

In [2], Carlson and Simpson proved a dualized version of Ramsey's theorem obtained by coloring partitions of ω instead of subsets of ω. It was at the suggestion of Simpson that the author undertook to study the notion dual to that of a Ramsey ultrafilter. After stating the basic terminology and notation used in the paper in §1, in §2 we establish some basic properties of the lattice of all partitions of a cardinal κ. §3 is devoted to the study of families of pairwise disjoint partitions of ω. §4 is concerned with descending sequences of partitions. In §5, we give some examples of filters of partitions. Properties of such filters are discussed in §6. Co-Ramsey filters are introduced in §7, and it is shown how they can be associated with Ramsey ultrafilters. The main result of §8 is Proposition 8.1, which asserts the existence of a co-Ramsey filter under the continuum hypothesis.We use standard set theoretic conventions and notation. Let κ be a cardinal. We set κ* = κ − {0}. For every ordinal α ≤ κ, (κ)α denotes the set of those sequences X(ν), ν < α, of pairwise disjoint nonempty subsets of κ such that ⋃ν<αX(ν) = κ, and ⋂X(ν) < ⋂X(ν′) whenever ν < ν′. We also let (κ)≤α = ⋃β≤α(κ)β and (κ)<α = ⋃β<α(κ)β. Given X ∈ (κ)α, we put xν = ⋂X(ν) for every ν < α, and we denote by Ax the set of all xν, 0 < ν < α.
Axioms of symmetry: Throwing darts at the real number line
Authors: Freiling Chris 
Published: May 2006

AbstractWe will give a simple philosophical “proof” of the negation of Cantor's continuum hypothesis (CH). (A formal proof for or against CH from the axioms of ZFC is impossible; see Cohen [1].) We will assume the axioms of ZFC together with intuitively clear axioms which are based on some intuition of Stuart Davidson and an old theorem of Sierpiński and are justified by the symmetry in a thought experiment throwing darts at the real number line. We will in fact show why there must be an infinity of cardinalities between the integers and the reals. We will also show why Martin's Axiom must be false, and we will prove the extension of Fubini's Theorem for Lebesgue measure where joint measurability is not assumed. Following the philosophy—if you reject CH you are only two steps away from rejecting the axiom of choice (AC)—we will point out along the way some extensions of our intuition which contradict AC.
Magidor-Malitz quantifiers in modules
Authors: Baudisch Andreas 
Published: May 2006

AbstractWe prove the elimination of Magidor-Malitz quantifiers for R-modules relative to certain -core sentences and positive primitive formulas. For complete extensions of the elementary theory of R-modules it follows that all Ramsey quantifiers (ℵ0-interpretation) are eliminable. By a result of Baldwin and Kueker [1] this implies that there is no R-module having the finite cover property.
Many-times huge and superhuge cardinals
Authors: Barbanel Julius B. , Diprisco Carlos A. , Tan It Beng 
Published: May 2006

In this paper we consider various generalizations of the notion of hugeness. We remind the reader that a cardinal κ is huge if there exist a cardinal λ > κ, an inner model M which is closed under λ-sequences, and an elementary embedding i: V → M with critical point κ such that i(κ) = λ. We shall call λ a target for κ and shall write κ → (λ) to express this fact. Equivalently, κ is huge with target λ if and only if there exists a normal ultrafilter on P=κ(λ) = {X ⊆ λ:X has order type κ}. For the proof and additional facts on hugeness, see [3].We assume that the reader is familiar with the notions of measurability and supercompactness. If κ is γ-supercompact for each γ < λ, we shall say that κ is < λ-supercompact. We note that if κ → (λ), it follows immediately that κ is < λ-supercompact.Throughout the paper, n shall be used to denote a positive integer, the letters α, β, and δ shall denote ordinals, while κ, λ, γ, and η shall be reserved for cardinals. All addition is ordinal addition. V denotes the universe of all sets.All results except for Theorems 6b and 6c and Lemma 6d can be formalized in ZFC.This paper was written while the first named author was at Rochester Institute of Technology, Rochester, New York. We wish to thank the department of mathematics at R.I.T. for secretarial time and facilities.
The strength of admissibility without foundation
Authors: Jäger Gerhard 
Published: May 2006

The following is part of a series of papers on theories for (iterated) admissible sets (cf. [10], [11], [12], [14], [15]). Although these theories are weak subsystems of Zermelo-Fraenkel set theory, they allow one to formalize and prove a fair amount of definability theory and generalized recursion theory. Using this machinery it is in general not very hard to establish the connections between theories for admissible sets and (for example) systems of second order arithmetic. A proof-theoretic analysis of theories for admissible sets therefore provides quite a uniform and powerful framework for the proof-theoretic treatment of many systems of set theory, second order arithmetic and constructive mathematics (see [12] and [15]). The strongest result in this direction so far is the pair of proof-theoretic equivalenceswhere T0 is Feferman's system for explicit mathematics of [5] and [6], (-CA) + (BI) is the usual system of second order arithmetic with the axiom of -comprehension and bar induction and KPi is Kripke-Platek set theory with ∈-inductionfor arbitrary formulas and the additional axiom.The least standard model of KPi is L(i0) where i0 is the first recursively inaccessible ordinal.In this paper we are mainly interested in the theory KPi0 which results from KPi by severely restricting the principles of induction. Basically, complete induction on the natural numbersis allowed only for ∆0-formulas, and (IND∈) is omitted completely.
On the embedding of α-recursive presentable lattices into the α-recursive degrees below 0′
Authors: Yang Dong Ping 
Published: May 2006

An important problem, widely treated in the analysis of the structure of degree orderings, is that of partial order and lattice embeddings. Thus for example we have the results on embeddings of all countable partial orderings in the Turing degrees by Kleene and Post [3] and in the r.e. T-degrees by Sacks [10]. For lattice embeddings the work on T-degrees culminated in the characterization of countable initial segments by Lachlan and Lebeuf [4]. For the r.e. T-degrees there has been a continuing line of progress on this question. (See Soare [20] and Lerman, Shore, and Soare [8].) Similar projects have been undertaken for the T-degrees below 0′ (Kleene and Post [3], Lerman [6]) as well as for most other degree orderings. The results have been used not only to analyse individual orderings but also to distinguish between them (Shore [16], [19], [17]).The situation for α-jecursive theory, the study of recursion in (admissible) ordinals, is similar to, though not as well developed as, that for Turing degrees. All afinite partial orderings have been embedded even in the α-r.e. degrees (see Lerman [5]). Lattice embedding results are somewhat fragmentary however. In terms of initial segments even the question of the existence of a minimal α-degree has not been settled for all admissibles. (See Shore [12] for a proof for Σ2-admissible ordinals, however.) Results on more complicated lattices have only reached to the finite distributive ones for Σ3-admissible ordinals (see Dorer [1]).
Models of the alternative set theory
Authors: Pudlák P. , Sochor A. 
Published: May 2006

Classical set theory is considered as the framework of contemporary mathematics. But there are aspects of our understanding of the real world about what it is not clear that they are described in Cantor's set theory in the best possible way. For example the formalization of some intuitive concepts such as the description of vague properties (which led to the theory of fuzzy sets) and the interpretation of the notion of infinitely small quantities (modelled by nonstandard models) is not quite simple in the classical set theory. Therefore it is natural to look for an alternative to Cantor's set theory which would enable us to formalize these considerations more naturally and which would be a sufficiently strong framework for mathematics at the same time.The alternative set theory which was created by P. Vopěnka (cf. [V]) is an attempt to construct a theory that could serve as an alternative to Cantor's set theory. The ideas of the alternative set theory make it possible to constitute a new approach to mathematics. An effort to formalize mathematically our intuitive concepts once more is made, and moreover it seems that one can obtain in the alternative set theory mathematical formalizations of concepts which up to now were not adequately formalized.In the alternative set theory we can build up all essential parts of mathematics. Development of the classical disciplines is described in [V]. Let us mention a few further results obtained in the alternative set theory: a connection between the discrete and the continuous on the basis of which it is possible to define topology (cf. [V]), investigation of motion (cf. [V]), construction of different types of σ-additive ultrafilters (cf. [S-V4]), classification of classes (measurement of vagueness of properties; cf. [Č-V]), possibility of definition of notions of nonstandard methods (cf. [S-V 1]) and valuations of ideals (cf. [M]). A series of articles has been written developing mathematics in the alternative set theory (for the full list of papers cf. [S]). For some remarks concerning the connection between the alternative set theory and nonstandard methods, the reader is refered to [S 4].
Church's thesis, continuity, and set theory
Authors: Beeson M. , Ščedrov A. 
Published: May 2006

AbstractUnder the assumption that all “rules” are recursive (ECT) the statement Cont(NN, N) that all functions from NN to N are continuous becomes equivalent to a statement KLS in the language of arithmetic about “effective operations”. Our main result is that KLS is underivable in intuitionistic Zermelo-Fraenkel set theory + ECT. Similar results apply for functions from R to R and from 2N to N. Such results were known for weaker theories, e.g. HA and HAS. We extend not only the theorem but the method, fp-realizability, to intuitionistic ZF.
Axiomatic recursion theory and the continuous functionals
Authors: Thompson Simon 
Published: May 2006

AbstractWe define, in the spirit of Fenstad [2], a higher type computation theory, and show that countable recursion over the continuous functionals forms such a theory. We also discuss Hyland's proposal from [4] for a scheme with which to supplement S1–S9, and show that this augmented set of schemes fails to generate countable recursion. We make another proposal to which the methods of this section do not apply.
The metatheory of the classical propositional calculus is not axiomatizable
Authors: Mason Ian 
Published: May 2006

In this paper we investigate the first order metatheory of the classical propositional logic. In the first section we prove that the first order metatheory of the classical propositional logic is undecidable. Thus as a mathematical object even the simplest of logics is, from a logical standpoint, quite complex. In fact it is of the same complexity as true first order number theory.This result answers negatively a question of J. F. A. K. van Benthem (see [van Benthem and Doets 1983]) as to whether the interpolation theorem in some sense completes the metatheory of the calculus. Let us begin by motivating the question that we answer. In [van Benthem and Doets 1983] it is claimed that a folklore prejudice has it that interpolation was the final elementary property of first order logic to be discovered. Even though other properties of the propositional calculus have been discovered since Craig's orginal paper [Craig 1957] (see for example [Reznikoff 1965]) there is a lot of evidence for the fundamental nature of the property. In abstract model theory for example one finds that very few logics have the interpolation property. There are two well-known open problems in this area. These are1. Is there a logic satisfying the full compactness theorem as well as the interpolation theorem that is not equivalent to first order logic even for finite models?2. Is there a logic stronger than L(Q), the logic with the quantifierthere exist uncountably many, that is countably compact and has the interpolation property?
On the logic of theory change: Partial meet contraction and revision functions
Authors: Alchourrón Carlos E. , Gärdenfors Peter , Makinson David 
Published: May 2006

AbstractThis paper extends earlier work by its authors on formal aspects of the processes of contracting a theory to eliminate a proposition and revising a theory to introduce a proposition. In the course of the earlier work, Gärdenfors developed general postulates of a more or less equational nature for such processes, whilst Alchourrón and Makinson studied the particular case of contraction functions that are maximal, in the sense of yielding a maximal subset of the theory (or alternatively, of one of its axiomatic bases), that fails to imply the proposition being eliminated.In the present paper, the authors study a broader class, including contraction functions that may be less than maximal. Specifically, they investigate “partial meet contraction functions”, which are defined to yield the intersection of some nonempty family of maximal subsets of the theory that fail to imply the proposition being eliminated. Basic properties of these functions are established: it is shown in particular that they satisfy the Gärdenfors postulates, and moreover that they are sufficiently general to provide a representation theorem for those postulates. Some special classes of partial meet contraction functions, notably those that are “relational” and “transitively relational”, are studied in detail, and their connections with certain “supplementary postulates” of Gàrdenfors investigated, with a further representation theorem established.
The undecidability of entailment and relevant implication
Authors: Urquhart Alasdair 
Published: May 2006

In this paper we show that the propositional logics E of entailment, R of relevant implication and T of ticket entailment are undecidable. The decision problem is also shown to be unsolvable in an extensive class of related logics. The main tool used in establishing these results is an adaptation of the von Neumann coordinatization theorem for modular lattices.Interest in the decision problem for these systems dates from the late 1950s. The earliest result was obtained by Anderson and Belnap who proved that the first degree fragment of all these logics is decidable. Kripke [11] proved that the pure implicational fragments R→ and E→ of R and E are decidable. His methods were extended by Belnap and Wallace to the implication-negation fragments of these systems [3]; Kripke's methods also extend easily to include the implication-conjunction fragments of R and E. Meyer in his thesis [14] extended the result for R to include a primitive necessity operator. He also proved decidable the system R-mingle, an extension of R, and ortho-R (OR), the logic obtained from R by omitting the distribution axiom. Various weak relevant logics are also known to be decidable by model-theoretic proofs of the finite model property (see Fine [5]). Finally, S. Giambrone [7] has solved the decision problem for various logics obtained by the omission of the contraction axiom (A → ⦁ A → B) → ⦁ A → B, including R+ − W (R+ minus contraction). It is worth noting that even where positive results were obtained, the decision methods were usually of a complexity considerably greater than in the case of other nonclassical logics such as intuitionistic logic or modal logic, a fact which already indicates the difficulty of the decision problem.