bluuebunny/crossref_metadata_2025_split huggingface dataset:
Coding without fine structure
Authors: Friedman Sy D. 
Published: May 2006

In this paper we prove Jensen's Coding Theorem, assuming ˜ 0#, via a proof that makes no use of the fine structure theory. We do need to quote Jensen's Covering Theorem, whose proof uses fine-structural ideas, but make no direct use of these ideas. The key to our proof is the use of “coding delays.”Coding Theorem (Jensen). Suppose 〈M,A〉 is a model of ZFC + O#does not exist. Then there is an 〈M, A〉-definable class forcing P such that if G ⊆ P is P-generic over 〈M, A〉:(a) 〈M[G],A,G〉 ⊨ NZFC.(b) M[G] ⊨ V = L[R], R ⊆ ωand 〈M[G], A, G〉 ⊨ A,G are definable from the parameter R.In the above statement when we say “〈M, A〉 ⊨ ZFC” we mean that M ⊨ ZFC and in addition M satisfies replacement for formulas that mention A as a predicate. And “P-generic over 〈M, A〉” means that all 〈M, A〉-definable dense classes are met.The consequence of ˜ O# that we need follows directly from the Covering Theorem.
The cofinality spectrum of the infinite symmetric group
Authors: Shelah Saharon , Thomas Simon 
Published: May 2006

AbstractLetSbe the group of all permutations of the set of natural numbers. The cofinality spectrumCF(S)ofSis the set of all regular cardinalsλsuch thatScan be expressed as the union of a chain ofλproper subgroups. This paper investigates which setsCof regular uncountable cardinals can be the cofinality spectrum ofS. The following theorem.is the main result of this paper.Theorem.Suppose that V ⊨ GCH. Let C be a set of regular uncountable cardinals which satisfies the following conditions.(a)C contains a maximum element.(b)Ifμis an inaccessible cardinal such thatμ= sup(C∩μ),thenμ∈C.(c)ifμis a singular cardinal such thatμ= sup(C∩μ),thenμ+∈C.Then there exists a c.c.c. notion of forcing ℙ such that Vℙ⊨ CF(S) = C.We shall also investigate the connections between the cofinality spectrum andpcftheory; and show thatCF(S)cannot be an arbitrarily prescribed set of regular uncountable cardinals.
Canonical formulas for K4. Part III: the finite model property
Authors: Zakharyaschev Michael 
Published: May 2006

This paper, a continuation of the series [22, 24], presents two methods for establishing the finite model property (FMP, for short) of normal modal logics containing K4. The methods are oriented mainly to logics represented by their canonical axioms and yield for such axiomatizations several sufficient conditions of FMP. We use them to obtain solutions to two well known open FMP problems. Namely, we prove that• every normal extension of K4 with modal reduction principles has FMP and• every normal extension of S4 with a formula of one variable has FMP.These results are interesting not only from the technical point of view. Actually, they reveal important properties of a quite natural family of modal logics—formulas of one variable and, in particular, modal reduction principles are typical axioms in modal logic. Unfortunately, the technical apparatus developed in this paper is applicable only to logics with transitive frames, and the situation with FMP of extensions of K by modal reduction principles, even by axioms of the form □np → □mp still remains unclear. I think at present this is one of the major challenges in completeness theory.The language of the canonical formulas, introduced in [22] (I'll refer to that paper as Part I), is a way of describing the “geometry and topology” of formulas' refutation (general) frames by means of some finite refutation patterns.
Monotone inductive definitions in explicit mathematics
Authors: Rathjen Michael 
Published: May 2006

AbstractThe context for this paper is Feferman's theory of explicit mathematics, T0. We address a problem that was posed in [6]. Let MID be the principle stating that any monotone operation on classifications has a least fixed point. The main objective of this paper is to show that T0 + MID, when based on classical logic, also proves the existence of non-monotone inductive definitions that arise from arbitrary extensional operations on classifications. From the latter we deduce that MID, when adjoined to classical T0, leads to a much stronger theory than T0.
Type two cuts, bad cuts and very bad cut
Authors: Jin Renling 
Published: May 2006

AbstractType two cuts, bad cuts and very bad cuts are introduced in [10] for studying the relationship between Loeb measure and U-topology of a hyperfinite time line in an ω1-saturated nonstandard universe. The questions concerning the existence of those cuts are asked there. In this paper we answer, fully or partially, some of those questions by showing that: (1) type two cuts exist, (2) the ℵ1-isomorphism property implies that bad cuts exist, but no bad cuts are very bad.
Scientific discovery based on belief revision
Authors: Martin Eric , Osherson Daniel 
Published: May 2006

AbstractScientific inquiry is represented as a process of rational hypothesis revision in the face of data. For the concept of rationality, we rely on the theory of belief dynamics as developed in [5, 9]. Among other things, it is shown that if belief states are left unclosed under deductive logic then scientific theories can be expanded in a uniform, consistent fashion that allows inquiry to proceed by any method of hypothesis revision based on “kernel” contraction. In contrast, if belief states are closed under logic, then no such expansion is possible.
Gentzenizations of relevant logics without distribution. II
Authors: Brady Ross T. 
Published: May 2006

In Part I, we produced a Gentzenization L6LBQ of the distributionless relevant logic LBQ, which contained just the one structural connective ‘:’ and no structural rules. We compared it with the corresponding “right-handed” system and then proved interpolability and decidability of LBQ. Knowledge of Part I is presupposed.In Part II of this paper, we will establish Gentzenizations, with appropriate interpolation and decidability results, for the further distributionless logics LDWQ, LTWQo, LEWQot, LRWQ, LRWKQ and LRQ, using essentially the same methods as were used for LBQ in Part I. LRWQ has been Gentzenized by Grishin [2], but the interpolation result is new and the decidability result is proved by a substantial simplification of his method. LR has been Gentzenized and shown to be decidable by Meyer in [5], by extending a method of Kripke in [3], and McRobbie has proved interpolation for it in [4], but here the Gentzenization and interpolation results are extended to quantifiers.We axiomatize these logics as follows. The primitives and formation rules are as before, except that LTWQ and LEWQ require the extra primitive ‘o’, a 2-place connective (called ‘fusion’), and LEWQ also requires ‘t’, a sentential constant.
On power set in explicit mathematics
Authors: Glass Thomas 
Published: May 2006

AbstractThis paper is concerned with the determination of the proof-strength of the power set axiom relative to axiom systems for Feferman's explicit mathematics. As conjectured by Feferman, we obtain that the presence of the power set axiom does not increase proof-strength.Results are achieved by reducing the systems including the power set axiom to subsystems of classical analysis. In those cases where only the induction axiom is available, we make use of the technique of asymmetrical interpretations.
A partial model of NF with E
Authors: Prati N. 
Published: May 2006

AbstractPartial models of the theory New Foundations (NF) introduced by Quine have already appeared in the literature, but in every model the membership set of NF is missing. On the other hand, Jensen showed that “NF + Urelements” is consistent with respect to ZF and, in the model built there, the membership set of the theory exists, Here we build a partial model of NF from the one of Jensen in which the membership set exists.
Hereditary undecidability of some theories of finite structures
Authors: Willard Ross 
Published: May 2006

AbstractUsing a result of Gurevich and Lewis on the word problem for finite semigroups, we give short proofs that the following theories are hereditarily undecidable: (1) finite graphs of vertex-degree at most 3; (2) finite nonvoid sets with two distinguished permutations; (3) finite-dimensional vector spaces over a finite field with two distinguished endomorphisms.
Generic trees
Authors: Spinas Otmar 
Published: May 2006

AbstractWe continue the investigation of the Laver ideal ℓ0 and Miller ideal m0 started in [GJSp] and [GRShSp]; these are the ideals on the Baire space associated with Laver forcing and Miller forcing. We solve several open problems from these papers. The main result is the construction of models for t < add(ℓ0), < add(m0), where add denotes the additivity coefficient of an ideal. For this we construct amoeba forcings for these forcings which do not add Cohen reals. We show that = ω2 implies add(m0) ≤ . We show that , implies cov(ℓ0) ≤ +, cov(m0) ≤ + respectively. Here cov denotes the covering coefficient. We also show that in the Cohen model cov(m0) < holds. Finally we prove that Cohen forcing does not add a superperfect tree of Cohen reals.
Perfect extensions and derived algebras
Authors: Andréka Hajnal , Givant Steven , Németi István 
Published: May 2006

Jónsson and Tarski [1951] introduced the notion of a Boolean algebra with (additive) operators (for short, a Bo). They showed that every Bo can be extended to a complete and atomic Bo satisfying certain additional conditions, and that any two complete, atomic extensions of satisfying these conditions are isomorphic over . Henkin [1970] extended these results to Boolean algebras with generalized (i.e., weakly additive) operators. The particular complete, atomic extension of studied by Jónsson and Tarski is called the perfect extension of , and is denoted by +. It is very useful in algebraic investigations of classes of algebras that are associated with logics.Interesting examples of Bos abound in algebraic logic, and include relation algebras, cylindric algebras, and polyadic and quasi-polyadic algebras (with or without equality). Moreover, there are several important constructions that, when applied to certain Bos, lead to other, derived Bos. Obvious examples include the formation of subalgebras, homomorphic images, relativizations, and direct products. Other examples include the Boolean algebra of ideal elements of a Bo, the neat β;-reduct of an α-dimensional cylindric algebra (β; < α), and the relation algebraic reduct of a cylindric algebra (of dimension at least 3). It is natural to ask about the relationship between the perfect extension of a Bo and the perfect extension of one of its derived algebras ′: Is the perfect extension of the derived algebra just the derived algebra of the perfect extension? In symbols, is (′)+ = (+)′? For example, is the perfect extension of a subalgebra, homomorphic image, relativization, or direct product, just the corresponding subalgebra, homomorphic image, relativization, or direct product of the perfect extension (up to isomorphisms)? Is the perfect extension of the Boolean algebra of ideal elements, or the neat reduct of a cylindric algebra, or the relation algebraic reduct of a cylindric algebra just the Boolean algebra of ideal elements, or the neat β;-reduct, or the relation algebraic reduct, of the perfect extension? We shall prove a general result in this direction; namely, if the derived algebra is constructed as the range of a relatively multiplicative operator, then the answer to our question is “yes”. We shall also give examples to show that in “infinitary” constructions, our question can have a spectacularly negative answer.
Simple Gentzenizations for the normal formulae of contraction-less logics
Authors: Brady Ross T. 
Published: May 2006

In [1], we established Gentzenizations for a good range of relevant logics with distribution, but, in the process, we added inversion rules, which involved extra structural connectives, and also added the sentential constantt. Instead of eliminating them, we used conservative extension results to relate them back to the original logics. In [4], we eliminated the inversion rules andtand established a much simpler Gentzenization for the weak sentential relevant logicDW, and also for its quantificational extensionDWQ, but a restriction to normal formulae (defined below) was required to enable these results to be proved. This method was quite general and hope was expressed about extending it to other relevant logics.In this paper, we develop an innovative method, which makes essential use of this restriction to normality, to establish two simple Gentzenizations for the normal formulae of the slightly weaker logic B, and then extend the method to other sentential contraction-less logics. To obtain the first of these Gentzenizations, for the logicsBandDW, we remove the two branching rules (F&) and (T∨), together with the structural connective ‘,’, to simplify the elimination of the inversion rules andt. We then eliminate the rules (T&) and (F∨), thus reducing the Gentzen system to one containing only ˜ and → and their four associated rules, and reduce the remaining types of structures to four simple finite types. Subsequently, we re-introduce (T&) and (F∨), and also (F&) and (T∨), to obtain the second Gentzenization, which contains ‘,’ but no structural rules.
Hechler reals
Authors: Łabędzki Grzegorz , Miroslav Repický  
Published: May 2006

AbstractWe define a σ-ideal on the set of functions ωω with the property that a real x ∈ ωω is a Hechler real over V if and only if x omits all Borel sets in . In fact we define a topology on ωω related to Hechler forcing such that is the family of first category sets in . We study cardinal invariants of the ideal .
Models of intuitionistic TT and NF
Authors: Dzierzgowski Daniel 
Published: May 2006

AbstractLet us define the intuitionistic part of a classical theory T as the intuitionistic theory whose proper axioms are identical with the proper axioms of T. For example, Heyting arithmetic HA is the intuitionistic part of classical Peano arithmetic PA.It's a well-known fact, proved by Heyting and Myhill, that ZF is identical with its intuitionistic part.In this paper, we mainly prove that TT, Russell's Simple Theory of Types, and NF, Quine's “New Foundations,” are not equal to their intuitionistic part. So, an intuitionistic version of TT or NF seems more naturally definable than an intuitionistic version of ZF.In the first section, we present a simple technique to build Kripke models of the intuitionistic part of TT (with short examples showing bad properties of finite sets if they are defined in the usual classical way).In the remaining sections, we show how models of intuitionistic NF2 and NF can be obtained from well-chosen classical ones. In these models, the excluded middle will not be satisfied for some non-stratified sentences.
Minimal readability of intuitionistic arithmetic and elementary analysis
Authors: Damnjanovic Zlatan 
Published: May 2006

AbstractA new method of “minimal” readability is proposed and applied to show that the definable functions of Heyting arithmetic (HA)—functions f such that HA ⊢ ∀x∃!yA(x, y) ⇒ for all m, A(m, f(m)) is true, where A(x, y) may be an arbitrary formula of ℒ(HA) with only x,y free—are precisely the provably recursive functions of the classical Peano arithmetic (PA), i.e., the < ε0-recursive functions. It is proved that, for prenex sentences provable in HA, Skolem functions may always be chosen to be < ε0-recursive. The method is extended to intuitionistic finite-type arithmetic, , and elementary analysis. Generalized forms of Kreisel's characterization of the provably recursive functions of PA and of the no-counterexample-interpretation for PA are consequently derived.
Connections between axioms of set theory and basic theorems of universal algebra
Authors: Andréka H. , Kurucz Á. , Németi I. 
Published: May 2006

Abstract.One of the basic theorems in universal algebra is Birkhoff's variety theorem: the smallest equationally axiomatizable class containing a classKof algebras coincides with the class obtained by taking homomorphic images of subalgebras of direct products of elements ofK. G. Grätzer asked whether the variety theorem is equivalent to the Axiom of Choice. In 1980, two of the present authors proved that Birkhoff's theorem can already be derived inZF. Surprisingly, the Axiom of Foundation plays a crucial role here: we show that Birkhoff's theorem cannot be derived inZF+AC\{Foundation}, even if we add Foundation for Finite Sets. We also prove that the variety theorem is equivalent to a purely set-theoretical statement, the Collection Principle. This principle is independent ofZF\{Foundation}. The second part of the paper deals with further connections between axioms ofZF-set theory and theorems of universal algebra.
A feasible theory for analysis
Authors: Ferreira Fernando 
Published: May 2006

AbstractWe construct a weak second-order theory of arithmetic which includes Weak König's Lemma (WKL) for trees defined by bounded formulae. The provably total functions (with -graphs) of this theory are the polynomial time computable functions. It is shown that the first-order strength of this version of WKL is exactly that of the scheme of collection for bounded formulae.
Diophantine equivalence and countable rings
Authors: Shlapentokh Alexandra 
Published: May 2006

AbstractWe show that Diophantine equivalence of two suitably presented countable rings implies that the existential polynomial languages of the two rings have the same “expressive power” and that their Diophantine sets are in some sense the same. We also show that a Diophantine class of countable rings is contained completely within a relative enumeration class and demonstrate that one consequence of this fact is the existence of infinitely many Diophantine classes containing holomorphy rings of ℚ.
On non-wellfounded iterations of the perfect set forcing
Authors: Kanovei Vladimir 
Published: May 2006

AbstractWe prove that ifIis a partially ordered set in a countable transitive modelof ZFC thencan be extended by a generic sequence of realsai,i∈I, such thatis preserved and everyaiis Sacks generic over[〈aj:j<i〉]. The structure of the degrees of-constructibility of reals in the extension is investigated.As applications of the methods involved, we define a cardinal invariant to distinguish product and iterated Sacks extensions, and give a short proof of a theorem (by Budinas) that in ω2-iterated Sacks extension of L the Burgess selection principle for analytic equivalence relations holds.
Tensor product and theories of modules
Authors: Prest Mike 
Published: May 2006

Modules over a ring R, when tensored with an (R, S)-bimodule, are converted to S-modules. Here I consider, from the standpoint of the model theory of modules, the effect of this operation. The primary motivation arises from questions concerning representation type of algebras and interpretability of modules, where such tensor functors play a key role, but this paper is devoted to more general considerations. For instance, the elementary duality of [2] and [1] is generalised here. It is also shown that, although tensor product does not preserve elementary equivalence, one can define the tensor product of two complete theories of R-modules. The results in Section 1 grew out of a number of discussions with T. Kucera.This is our generic situation. We have an (R, S)-bimodule B and we are considering the functor –⊗RBS from Mod – R (the category of right R-modules) to Mod – S which is given on objects by MR ↦ (M ⊗RB)s and has the obvious action on morphisms. There is a somewhat more general situation: namely we may consider the effect of tensoring (T, R)-bimodules over R with B to obtain (T, S)-bimodules. For the intended applications this case is not needed. Moreover, although some results extend to this more general case, there are some which definitely do not (see the example after 2.1). Therefore we confine ourselves to the case first described. We will also consider B itself as a variable and so ask “What is the effect of tensoring R-modules with (R, S)-bimodules?”.
On the cofinality of ultrapowers
Authors: Blass Andreas , Mildenberger Heike 
Published: May 2006

AbstractWe prove some restrictions on the possible cofinalities of ultrapowers of the natural numbers with respect to ultrafilters on the natural numbers. The restrictions involve three cardinal characteristics of the continuum, the splitting numbers, the unsplitting numberr, and the groupwise density numberg. We also prove some related results for reduced powers with respect to filters other than ultrafilters.
Ordinal inequalities, transfinite induction, and reverse mathematics
Authors: Hirst Jeffry L. 
Published: May 2006

AbstractIf α and β are ordinals, α ≤ β, and β ≰ α then α+ 1 < β. The first result of this paper shows that the restriction of this statement to countable well orderings is provably equivalent to ACA0, a subsystem of second order arithmetic introduced by Friedman. The proof of the equivalence is reminiscent of Dekker's construction of a hypersimple set. An application of the theorem yields the equivalence of the set comprehension scheme ACA0 and an arithmetical transfinite induction scheme.
Existentially closed models of the theory of artinian local rings
Authors: Schoutens Hans 
Published: May 2006

AbstractThe class of all Artinian local rings of length at most l is ∀2-elementary, axiomatised by a finite set of axioms τtl. We show that its existentially closed models are Gorenstein. of length exactly l and their residue fields are algebraically closed, and, conversely, every existentially closed model is of this form. The theory oτl of all Artinian local Gorenstein rings of length l with algebraically closed residue field is model complete and the theory τtl is companionable, with model-companion oτl.
An extension of the Cobham-Semënov Theorem
Authors: Bès Alexis 
Published: May 2006

AbstractLet θ, θ′ be two multiplicatively independent Pisot numbers, and letU,U′ be two linear numeration systems whose characteristic polynomial is the minimal polynomial of θ and θ′, respectively. For everyn≥ 1, ifA⊆ ℕnisU-andU′ -recognizable thenAis definable in 〈ℕ: + 〉.
Expressivity in polygonal, plane mereotopology
Authors: Pratt Ian , Schoop Dominik 
Published: May 2006

AbstractIn recent years, there has been renewed interest in the development of formal languages for describing mereological (part-whole) and topological relationships between objects in space. Typically, the non-logical primitives of these languages are properties and relations such as ‘xis connected’ or ‘xis a part ofy’, and the entities over which their variables range are, accordingly, notpoints, butregions: spatial entities other than regions are admitted, if at all, only as logical constructs of regions. This paper considers two first-order mereotopological languages, and investigates their expressive power. It turns out that these languages, notwithstanding the simplicity of their primitives, are surprisingly expressive. In particular, it is shown that infinitary versions of these languages are adequate to express (in a sense made precise below) all topological relations over the domain of polygons in the closed plane.