bluuebunny/crossref_metadata_2025 huggingface dataset:
New set-theoretic axioms derived from a lean metamathematics
Authors: Mycielski Jan
Published: May 2006

I will formulate in this paper three set-theoretic axioms, (A1), (A2), and (A3), which appear natural and settle some well-known questions, and I will give some metamathematical evidence supporting these axioms. I build upon a distinction between pure mathematics and applied metamathematics which views the first as an art dealing with imaginary objects, where following Poincaré we can say to exist is to be free of contradiction, and the second as a science describing the phenomenon of mathematics, where science means a description of some physical reality (in this case the reality of thoughts in our brains which underlie spoken or written mathematics). Of course this distinction is not new, but it has been disregarded by many mathematicians and philosophers who wrote about the nature of mathematics, e.g. by the Platonists, and even by some empiricists who thought that mathematics is a science. Since applied metamathematics is a science, unlike pure mathematics it has to be lean, i.e., to obey Ockham's principle of economy of concepts (entia non sunt multiplicanda praeter necessitatem).

In this lean metamathematics we describe pure mathematics as a finite structure of thoughts in our brains, and we think that written or spoken mathematics is an abstract description of this structure. (I think that this is the view which Poincaré expressed informally in his discussions with the logicians and set theorists of his times, although his idea has to be modified to some extent; see Remark 4 at the end of this paper.) We claim that all mathematical objects which are imagined when we develop a (first-order) theory T can be represented by means of terms of the language of a Skolemization of the set of sentences consisting of the axioms of T and of all theorems of logic.
Fine hierarchies and Boolean terms
Authors: Selivanov V. L.
Published: May 2006

We consider fine hierarchies in recursion theory, descriptive set theory, logic and complexity theory. The main results state that the sets of values of different Boolean terms coincide with the levels of suitable fine hierarchies. This gives new short descriptions of these hierarchies and shows that collections of sets of values of Boolean terms are almost well ordered by inclusion. For the sake of completeness we mention also some earlier results demonstrating the usefulness of fine hierarchies.
A semantics of evidence for classical arithmetic
Authors: Coquand Thierry
Published: May 2006

If it is difficult to give the exact significance of consistency proofs from a classical point of view, in particular the proofs of Gentzen [2, 6], and Novikoff [14], the motivations of these proofs are quite clear intuitionistically. Their significance is then less to give a mere consistency proof than to present an intuitionistic explanation of the notion of classical truth. Gentzen for instance summarizes his proof as follows [6]: “Thus propositions of actualist mathematics seem to have a certain utility, but no sense. The major part of my consistency proof, however, consists precisely in ascribing a finitist sense to actualist propositions.” From this point of view, the main part of both Gentzen's and Novikoff's arguments can be stated as establishing that modus ponens is valid w.r.t. this interpretation ascribing a “finitist sense” to classical propositions.

In this paper, we reformulate Gentzen's and Novikoff's “finitist sense” of an arithmetic proposition as a winning strategy for a game associated to it. (To see a proof as a winning strategy has been considered by Lorenzen [10] for intuitionistic logic.) In the light of concurrency theory [7], it is tempting to consider a strategy as an interactive program (which represents thus the “finitist sense” of an arithmetic proposition). We shall show that the validity of modus ponens then gets a quite natural formulation, showing that “internal chatters” between two programs end eventually.

We first present Novikoff's notion of regular formulae, that can be seen as an intuitionistic truth definition for classical infinitary propositional calculus. We use this in order to motivate the second part, which presents a game-theoretic interpretation of the notion of regular formulae, and a proof of the admissibility of modus ponens which is based on this interpretation.
Relativized logspace and generalized quantifiers over finite ordered structures
Authors: Gottlob Georg
Published: May 2006

We here examine the expressive power of first order logic with generalized quantifiers over finite ordered structures. In particular, we address the following problem: Given a familyQof generalized quantifiers expressing a complexity classC, what is the expressive power of first order logic FO(Q) extended by the quantifiers inQ? From previously studied examples, one would expect that FO(Q) capturesLC, i.e., logarithmic space relativized to an oracle inC. We show that this is not always true. However, after studying the problem from a general point of view, we derive sufficient conditions onCsuch that FO(Q) capturesLC. These conditions are fulfilled by a large number of relevant complexity classes, in particular, for example, byNP. As an application of this result, it follows that first order logic extended by Henkin quantifiers capturesLNP. This answers a question raised by Blass and Gurevich [Ann. Pure Appl. Logic, vol. 32, 1986]. Furthermore we show that for many familiesQof generalized quantifiers (including the family of Henkin quantifiers), each FO(Q)-formula can be replaced by an equivalent FO(Q)-formula with only two occurrences of generalized quantifiers. This generalizes and extends an earlier normal-form result by I. A. Stewart [Fundamenta Inform, vol. 18, 1993].
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.
Accessible categories, saturation and categoricity
Authors: Rosický Jiří
Published: May 2006

Model-theoretic concepts of saturation and categoricity are studied in the context of accessible categories. Accessible categories which are categorical in a strong sense are related to categories of M-sets (M is a monoid). Typical examples of such categories are categories of λ-saturated objects.
The cofinality spectrum of the infinite symmetric group
Authors: Shelah Saharon , Thomas Simon
Published: May 2006

LetSbe 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

The 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.
Power types in explicit mathematics?
Authors: Jäger Gerhard
Published: May 2006

In this note it is shown that in explicit mathematics the strong power type axiom is inconsistent with (uniform) elementary comprehension and discuss some general aspects of power types in explicit mathematics.
Type two cuts, bad cuts and very bad cut
Authors: Jin Renling
Published: May 2006

Type 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

Scientific 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

This 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

Partial 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

Using 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

We 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

We 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

Let 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.
Model completions and omitting types
Authors: Millar Terrence
Published: May 2006

Universal theories with model completions are characterized. A new omitting types theorem is proved. These two results are used to prove the existence of a universal ℵ0-categorical partial order with an interesting embedding property. Other aspects of these results also are considered.
Minimal readability of intuitionistic arithmetic and elementary analysis
Authors: Damnjanovic Zlatan
Published: May 2006

A 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.
Kernel contraction
Authors: Hansson Sven Ove
Published: May 2006

Kernel contraction is a natural nonrelational generalization of safe contraction. All partial meet contractions are kernel contractions, but the converse relationship does not hold. Kernel contraction is axiomatically characterized. It is shown to be better suited than partial meet contraction for formal treatments of iterated belief change.
Connections between axioms of set theory and basic theorems of universal algebra
Authors: Andréka H. , Kurucz Á. , Németi I.
Published: May 2006

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

We 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

We 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

We 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

We 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.
Équations génériques dans un groupe stable nilpotent
Authors: Jaber Khaled
Published: May 2006

We prove that in a nilpotent-by-finite stable group an equation that holds generically holds everywhere. Combining this result with results of Wagner and Bryant, we conclude that a soluble-by-finite stable group of generic exponentnhas exponentn.
Ordinal inequalities, transfinite induction, and reverse mathematics
Authors: Hirst Jeffry L.
Published: May 2006

If α 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

The 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

Let θ, θ′ 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 〈ℕ: + 〉.
Maharam spectra of Loeb spaces
Authors: Jin Renling , Keisler H. Jerome
Published: May 2006

We characterize Maharam spectra of Loeb probability spaces and give some applications of the results.
Belief contraction as nonmonotonic inference
Authors: Bochman Alexander
Published: May 2006

A notion of an epistemic state is introduced as a generalization of common representations suggested for belief change. Based on it, a new kind of nonmonotonic inference relation corresponding to belief contractions is defined. A number of representation results is established that cover both traditional AGM contractions and contractions that do not satisfy recovery.
Expressivity in polygonal, plane mereotopology
Authors: Pratt Ian , Schoop Dominik
Published: May 2006

In 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.
Model completeness of the new strongly minimal sets
Authors: Holland Kitty L.
Published: May 2006

Boris Zil'ber conjectured that all strongly minimal theories are bi-interpretable with one of the “classical” sorts: theories of algebraically closed fields, theories of infinite vector spaces over division rings and theories with trivial algebraic closure relations. Hrushovski produced the first two classes of counterexample to this conjecture in [10] and [9]. Subsequently, in [8], the author gave an explicit axiomatization of a special case of [9] from which model completeness could quickly be deduced. It was unclear at that writing whether the model completeness result was true in the general case or was due to peculiarities of the case under consideration. The main new result of this paper is model completeness, not only of the general case in [9], but also of the theories described in [10]. Specifically, we present a general framework in which producing a strongly minimal theory is reduced to finding an elementary class of theories satisfying certain requirements (see below). We present the theories of [10] and [9] as special instances of such theories, giving an explicit axiomatization from which model completeness immediately follows in each case.

We hope by presenting these constructions in parallel, using common language and extracting common elements, to make easier both the exploitation of the ideas involved in their making and their comparison with other recent constructions of a similar flavor. For a selection of such constructions, see [6], [1], [2] and [3]. For more general background, see [2], [4] and [11].
Lascar and Morley ranks differ in differentially closed fields
Authors: Hrushovski Ehud , Scanlon Thomas
Published: May 2006

We note here, in answer to a question of Poizat, that the Morley and Lascar ranks need not coincide in differentially closed fields. We will approach this through the (perhaps) more fundamental issue of the variation of Morley rank in families. We will be interested here only in sets of finite Morley rank. Section 1 consists of some general lemmas relating the above issues. Section 2 points out a family of sets of finite Morley rank, whose Morley rank exhibits discontinuous upward jumps. To make the base of the family itself have finite Morley rank, we use a theorem of Buium.
Solovay-type characterizations for forcing-algebras
Authors: Brendle Jörg , Löwe Benedikt
Published: May 2006

We give characterizations for the (in ZFC unprovable) sentences “Every -set is measurable” and “Every -set is measurable” for various notions of measurability derived from well-known forcing partial orderings.
Quantifier elimination for neocompact sets
Authors: Keisler H. Jerome
Published: May 2006

We shall prove quantifier elimination theorems for neocompact formulas, which define neocompact sets and are built from atomic formulas using finite disjunctions, infinite conjunctions, existential quantifiers, and bounded universal quantifiers. The neocompact sets were first introduced to provide an easy alternative to nonstandard methods of proving existence theorems in probability theory, where they behave like compact sets. The quantifier elimination theorems in this paper can be applied in a general setting to show that the family of neocompact sets is countably compact. To provide the necessary setting we introduce the notion of a law structure. This notion was motivated by the probability law of a random variable. However, in this paper we discuss a variety of model theoretic examples of the notion in the light of our quantifier elimination results.
The Logic of Choice
Authors: Blass Andreas , Gurevich Yuri
Published: May 2006

The choice construct (choosex: φ(x)) is useful in software specifications. We study extensions of first-order logic with the choice construct. We prove some results about Hilbert'sεoperator, but in the main part of the paper we consider the case when all choices are independent.
Chains of end elementary extensions of models of set theory
Authors: Villaveces Andrés
Published: May 2006

Large cardinals arising from the existence of arbitrarily long end elementary extension chains over models of set theory are studied here. In particular, we show that the large cardinals obtained in this fashion (‘unfoldable cardinals’) lie in the boundary of the propositions consistent with ‘V = L’ and the existence of 0#. We also provide an ‘embedding characterisation’ of the unfoldable cardinals and study their preservation and destruction by various forcing constructions.
Cartesian isomorphisms are symmetric monoidal: A justification of linear logic
Authors: Došen Kosta , Petrić Zoran
Published: May 2006

It is proved that all the isomorphisms in the cartesian category freely generated by a set of objects (i.e., a graph without arrows) can be written in terms of arrows from the symmetric monoidal category freely generated by the same set of objects. This proof yields an algorithm for deciding whether an arrow in this free cartesian category is an isomorphism.
No elementary embedding from v into v is definable from parameters
Authors: Suzuki Akira
Published: May 2006

In 1970, Kenneth Kunen showed that there is no non-trivial elementary embedding of the universe V into itself [2] using the axiom of choice. Kunen remarked in his paper that the result can be formalized in Morse-Kelley theory of sets and classes. In this paper, we will work within ZF, Zermelo-Fraenkel axioms, and deal with embeddings definable with a formula and a parameter.

In ZF, a “class” is usually synonymous with “property”, that is a class definable with a parameter, C = {x: φ(x,p)}, where φ is a formula in the language [∈}. Using this convention, let j be a class. Then “j is an elementary embedding of V into V” is not a single statement but a schema of statements “j preserves ψ” for each formula ψ. We prove that this schema is expressible in the language {∈} by a single formula:

Lemma. An embedding j: V → V is elementary iff j preservesψ.

Here ψ(α, ψ, a) is the property “a is an ordinal, φ is a formula and Vα.”

The lemma is of course a schema of lemmas, one for each formula denning j and for each ψ to be preserved.

Using this we prove our theorem in ZF (again, a schema of theorems.):

Theorem 1.1. There is no nontrivial definable elementary embedding j: V → V.

Many symbols and their definitions follow those used by Drake's book [1]. The formula Sat expresses the satisfaction relation . The formula Fmla(u) expresses that u is the Gödel-set for a formula.
Relative enumerability in the difference hierarchy
Authors: Arslanov Marat M. , Laforte Geoffrey L. , Slaman Theodore A.
Published: May 2006

We show that the intersection of the class of 2-REA degrees with that of the ω-r.e. degrees consists precisely of the class of d.r.e. degrees. We also include some applications and show that there is no natural generalization of this result to higher levels of the REA hierarchy.
There are many almost strongly minimal generalizedn-gons that do not interpret an infinite group
Authors: Debonis Mark J. , Nesin Ali
Published: May 2006

Generalizedn-gons are certain geometric structures (incidence geometries) that generalize the concept of projective planes (the nontrivial generalized 3-gons are exactly the projective planes).

In a simplified world, every generalizedn-gon of finite Morley rank would be an algebraic one, i.e., one of the three families described in [9] for example. To our horror, John Baldwin [2], using methods discovered by Hrushovski [7], constructed ℵ1-categorical projective planes which are not algebraic. The projective planes that Baldwin constructed fail to be algebraic in a dramatic way.

Indeed, every algebraic projective plane over an algebraically closed field is Desarguesian [12]. In particular, an algebraically closed field (isomorphic to the base field) can be interpreted in every one of them. However, in the projective planes that Baldwin constructed, one cannot even interpret an infinite group.

In this article we show that the same phenomenon occurs for the generalizedn-gons ifn≥ 3 is an odd integer. For each suchnwe constructmany nonisomorphic generalizedn-gons of finite Morley rank that do not interpret an infinite group. As one may expect, our method is inspired by Hrushovski and Baldwin, and we follow Baldwin's line of approach. Quite often our proofs are a verification of the fact that the proofs of Baldwin [2] forn= 3 carry over to an arbitrary positive odd integern(which is sometimes far from being obvious). As in [2], we begin by defining a certain collection of finite graphsK* and a binary relation ≤ on these graphs. We show that (K*, ≤) satisfies the amalgamation property.
Superdestructibility: A dual to Laver's indestructibility
Authors: Hamkins Joel David , Shelah Saharon
Published: May 2006

After small forcing, any <κ-closed forcing will destroy the supercompactness and even the strong compactness of κ.
Ultrafilters which extend measures
Authors: Benedikt Michael
Published: May 2006

We study classes of ultrafilters on ω defined by a natural property of the Loeb measure in the Nonstandard Universe corresponding to the ultrafilter. This class, the Property M ultrafilters, is shown to contain all ultrafilters built up by taking iterated products over collections of pairwise nonisomorphic selective ultrafilters. Results on Property M ultrafilters are applied to the construction of extensions of probability measures, and to the study of measurable reductions between ultrafilters.
Minimum propositional proof length is NP-hard to linearly approximate
Authors: Alekhnovich Michael , Buss Sam , Moran Shlomo , Pitassi Toniann
Published: May 2006

We prove that the problem of determining the minimum propositional proof length is NP-hard to approximate within a factor of . These results are very robust in that they hold for almost all natural proof systems, including: Frege systems, extended Frege systems, resolution. Horn resolution, the polynomial calculus, the sequent calculus, the cut-free sequent calculus, as well as the polynomial calculus. Our hardness of approximation results usually apply to proof length measured either by number of symbols or by number of inferences, for tree-like or dag-like proofs. We introduce the Monotone Minimum (Circuit) Satisfying Assignment problem and reduce it to the problems of approximation of the length of proofs.
Power-like models of set theory
Authors: Enayat Ali
Published: May 2006

A model = (M. E, …) of Zermelo-Fraenkel set theory ZF is said to be 0-like. where E interprets ∈ and θ is an uncountable cardinal, if ∣M∣ = θ but ∣{b ∈ M: bEa}∣ < 0 for each a ∈ M, An immediate corollary of the classical theorem of Keisler and Morley on elementary end extensions of models of set theory is that every consistent extension of ZF has an ℵ1-like model. Coupled with Chang's two cardinal theorem this implies that if θ is a regular cardinal 0 such that 2<0 = 0 then every consistent extension of ZF also has a 0+-like model. In particular, in the presence of the continuum hypothesis every consistent extension of ZF has an ℵ2-like model. Here we prove:

Theorem A. If 0 has the tree property then the following are equivalent for any completion T of ZFC:

(i) T has a 0-like model.

(ii) Ф ⊆ T. where Ф is the recursive set of axioms {∃κ (κ is n-Mahlo and “Vκis a Σn-elementary submodel of the universe”): n ∈ ω}.

(iii) T has a λ-like model for every uncountable cardinal λ.

Theorem B. The following are equiconsistent over ZFC:

(i) “There exists an ω-Mahlo cardinal”.

(ii) “For every finite language , all ℵ2-like models of ZFC() satisfy the schemeФ().
An open mapping theorem for o-minimal structures
Authors: Johns Joseph
Published: May 2006

We fix an arbitrary o-minimal structure (R, ω, …), where (R, <) is a dense linearly ordered set without end points. In this paper “definable” means “definable with parameters from R”, We equip R with the interval topology and Rn with the induced product topology. The main result of this paper is the following.

Theorem. Let V ⊆ Rnbe a definable open set and suppose that f: V → Rnis a continuous injective definable map. Then f is open, that is, f(U) is open whenever U is an open subset of V.

Woerheide [6] proved the above theorem for o-minimal expansions of a real closed field using ideas of homology. The case of an arbitrary o-minimal structure remained an open problem, see [4] and [1]. In this paper we will give an elementary proof of the general case.

Basic definitions and notation. A box B ⊆ Rn is a Cartesian product of n definable open intervals: B = (a1, b1) × … × (an, bn) for some ai, bi, ∈ R ∪ {−∞, +∞}, with ai < bi, Given A ⊆ Rn, cl(A) denotes the closure of A, int(A) denotes the interior of A, bd(A) ≔ cl(A) − int(A) denotes the boundary of A, and ∂A ≔ cl(A) − A denotes the frontier of A, Finally, we let π: Rn → Rn− denote the projection map onto the first n − 1 coordinates.

Background material. Without mention we will use notions and facts discussed in [5] and [3]. We will also make use of the following result, which appears in [2].
The consistency strength of successive cardinals with the tree property
Authors: Foreman Matthew , Magidor Menachem , Schindler Ralf-Dieter
Published: May 2006

If ωn has the tree property for all 2 ≤ n < ω and , then for all and n < ω. Mnt(X) exists.
Shelah's work on non-semi-proper iterations, II
Authors: Schlindwein Chaz
Published: May 2006

One of the main goals in the theory of forcing iteration is to formulate preservation theorems for not collapsing ω1 which are as general as possible. This line leads from c.c.c. forcings using finite support iterations to Axiom A forcings and proper forcings using countable support iterations to semi-proper forcings using revised countable support iterations, and more recently, in work of Shelah, to yet more general classes of posets. In this paper we concentrate on a special case of the very general iteration theorem of Shelah from [5, chapter XV]. The class of posets handled by this theorem includes all semi-proper posets and also includes, among others, Namba forcing.

In [5, chapter XV] Shelah shows that, roughly, revised countable support forcing iterations in which the constituent posets are either semi-proper or Namba forcing or P[W] (the forcing for collapsing a stationary co-stationary subset of

with countable conditions) do not collapse ℵ1. The iteration must contain sufficiently many cardinal collapses, for example, Levy collapses. The most easily quotable combinatorial application is the consistency (relative to a Mahlo cardinal) of ZFC + CH fails + whenever A ∪ B = ω2 then one of A or B contains an uncountable sequentially closed subset. The iteration Shelah uses to construct this model is built using P[W] to “attack” potential counterexamples, Levy collapses to ensure that the cardinals collapsed by the various P[W]'s are sufficiently well separated, and Cohen forcings to ensure the failure of CH in the final model.

In this paper we give details of the iteration theorem, but we do not address the combinatorial applications such as the one quoted above.

These theorems from [5, chapter XV] are closely related to earlier work of Shelah [5, chapter XI], which dealt with iterated Namba and P[W] without allowing arbitrary semi-proper forcings to be included in the iteration. By allowing the inclusion of semi-proper forcings, [5, chapter XV] generalizes the conjunction of [5, Theorem XI.3.6] with [5, Conclusion XI.6.7].
Supercompactness and measurable limits of strong cardinals
Authors: Apter Arthur W.
Published: May 2006

In this paper, two theorems concerning measurable limits of strong cardinals and supercompactness are proven. This generalizes earlier work, both individual and joint with Shelah.
Strong 0-1 laws in finite model theory
Authors: Lotfallah Wafik Boulos
Published: May 2006

We introduce a new framework for asymptotic probabilities of sentences, in which we have a σ-additive measure on the sample space of all sequencesA= {} of finite models, where the universe ofis {1,2, …, n}. and use this framework to strengthen 0-1 laws for logics.
Nonstandard analysis in topology: nonstandard and standard compactifications
Authors: Salbany S. , Todorov Todor
Published: May 2006

Let (X, T) be a topological space and *X a nonstandard extension of X. Sets of the form *G. where G ∈ T, form a base for the “standard” topology ST on *X. The topological space (*X, ST) will be used to study compactifications of (X, T) in a systematic way.