bluuebunny/crossref_metadata_2025 huggingface dataset:
An elementary sentence which has ordered models
Authors: Schmerl James H.
Published: May 2006

Let < and ≼ be two distinguished binary relation symbols. A structure is κ-like iff is a linear ordering of A, card(A) = κ, and every proper initial segment of A has cardinality < κ. A structure is α-ordered iff is a (reflexive) linear ordering of type α with field a subset of A. We define when a cardinal κ is α-inaccessible. (In this paper, inaccessible always means weakly inaccessible.) The 0-inaccessible cardinals are just the inaccessible cardinals; if α > 0, then κ is α-inaccessible iff for each β < α, each closed, cofinal subset of κ contains a β-inaccessible. (The (1 + α)-inaccessibles are just the ρα cardinals of Mahlo.) This paper is concerned with the proof of the following theorem.

Main Theorem. There is an elementary sentence σ with the property that whenever α is an ordinal and κ an infinite cardinal, then σ has an α-ordered κ-like model iff κ is not α-inaccessible.

This theorem gives some additional answers to a question of Mostowski about languages with generalized quantifiers. Fuhrken [1] showed that this question is equivalent to the following one: For which cardinals κ and λ is it true that if an elementary sentence has a κ-like model, then it has a λ-like model? It is actually this question to which the theorem refers. The theorem limits the possible pairs κ, λ of cardinals which answer the question. In fact, if the question is generalized so as to permit sentences from some more extensive language, then the theorem still limits the possible answers. For a more thorough introduction to this problem, the reader is referred to the aforementioned article of Fuhrken as well as Keisler [2] and Vaught [6].
Generalizing special Aronszajn trees
Authors: Schmerl James H.
Published: May 2006

In this paper we define by means of a partition property a decreasing sequence N = ‹Nα: α is an ordinal› of classes of ordinals. This property is a generalization of the nonexistence of special Aronszajn trees: the successor cardinal κ+ is in N0 iff there does not exist a special Aronszajn κ+-tree.

The interest in the classes Nα stems from their applicability in model theory, in particular to that aspect of model theory dealing with ordered and two-cardinal models. A model is κ-like iff < is a linear ordering of A of cardinality κ but such that every proper initial segment has cardinality < κ. is α-ordered iff ≼ is a reflexive, linear ordering of some subset of A with order type α. The sequence N can be characterized by a first-order sentence σ in the following manner: The sentence σ has a κ-like α-ordered model iff κ ∉ Nα. This characterization will allow us to translate various independence statements regarding the sequence N to statements about the independence of transfer properties. We say that the transfer property κ → λ holds iff every first-order sentence which has a κ-like model also has a λ-like model. κ ⇸ λ is the negation of κ → λ.
Ramsey's theorem in the hierarchy of choice principles
Authors: Blass Andreas
Published: May 2006

Ramsey's theorem [5] asserts that every infinite set X has the following partition property (RP): For every partition of the set [X]2 of two-element subsets of X into two pieces, there is an infinite subset Y of X such that [Y]2 is included in one of the pieces. Ramsey explicitly indicated that his proof of this theorem used the axiom of choice. Kleinberg [3] showed that every proof of Ramsey's theorem must use the axiom of choice, although rather weak forms of this axiom suffice. J. Dawson has raised the question of the position of Ramsey's theorem in the hierarchy of weak axioms of choice.

In this paper, we prove or refute the provability of each of the possible implications between Ramsey's theorem and the weak axioms of choice mentioned in Appendix A.3 of Jech's book [2]. Our results, along with some known facts which we include for completeness, may be summarized as follows (the notation being as in [2]):

A. The following principles do not (even jointly) imply Ramsey's theorem, nor does Ramsey's theorem imply any of them:

the Boolean prime ideal theorem,

the selection principle,

the order extension principle,

the ordering principle,

choice from wellordered sets (ACW),

choice from finite sets,

choice from pairs (C2).

B. Each of the following principles implies Ramsey's theorem, but none of them follows from Ramsey's theorem:

the axiom of choice,

wellordered choice (∀kACk),

dependent choice of any infinite length k (DCk),

countable choice (ACN0),

nonexistence of infinite Dedekind-finite sets (WN0).
Linear sampling and the ∀∃∀ case of the decision problem
Authors: Aanderaa Stål O. , Lewis Harry R.
Published: May 2006

Let Q be the class of closed quantificational formulas ∀x∃u∀yM without identity such that M is a quantifier-free matrix containing only monadic and dyadic predicate letters and containing no atomic subformula of the form Pyx or Puy for any predicate letter P. In [DKW] Dreben, Kahr, and Wang conjectured that Q is a solvable class for satisfiability and indeed contains no formula having only infinite models. As evidence for this conjecture they noted the solvability of the subclass of Q consisting of those formulas whose atomic subformulas are of only the two forms Pxy, Pyu and the fact that each such formula that has a model has a finite model. Furthermore, it seemed likely that the techniques used to show this subclass solvable could be extended to show the solvability of the full class Q, while the syntax of Q is so restricted that it seemed impossible to express in formulas of Q any unsolvable problem known at that time.

In 1966 Aanderaa refuted this conjecture. He first constructed a very complex formula in Q having an infinite model but no finite model, and then, by an extremely intricate argument, showed that Q (in fact, the subclass Q2 defined below) is unsolvable ([Aa1], [Aa2]). In this paper we develop stronger tools in order to simplify and extend the results of [Aa2]. Specifically, we show the unsolvability of an apparently new combinatorial problem, which we shall call the linear sampling problem (defined in §1.2 and §2.3). From the unsolvability of this problem there follows the unsolvability of two proper subclasses of Q, which we now define. For each i ≥ 0, let Pi be a dyadic predicate letter and let Ri be a monadic predicate letter.
Note on the Kondo-Addison theorem
Authors: Guaspari David
Published: May 2006

The Kondo-Addison theorem says that every set A of reals contains a real which is implicit (for short, Imp). Any real which is Imp is constructible, and it is the main purpose of this note to show that a close examination of the usual Kondo-Addison argument allows us to compute (in terms of the ordinals associated with A by the classical representation theorem) where in the constructible hierarchy an element of A ∩ Imp must occur. This result is related to a basis theorem of Barwise and Fisher [1] and is accompanied by a strong counterexample which shows that certain tepid improvements of their theorem (and, a fortiori, of the main theorem in this note) are impossible. As a final flourish, the ‘classifying ordinals’ used to compute the locations of the singletons are themselves characterized using an idea from [1].
A combinatorial property of pκλ
Authors: Menas Telis K.
Published: May 2006

In a paper on combinatorial properties and large cardinals [2], Jech extended several combinatorial properties of a cardinal κ to analogous properties of the set of all subsets of λ of cardinality less than κ, denoted by “pκλ”, where λ is any cardinal ≤κ. We shall consider in this paper one of these properties which is historically rooted in a theorem of Ramsey [10] and in work of Rowbottom [12].

As in [2], define [pκλ]2 = {{x, y}: x, y ∈ pκλ and x ≠ y}. An unbounded subset A of pκλ is homogeneous for a function F: [pκλ]2 → 2 if there is a k < 2 so that for all x, y ∈ A with either x ⊊ y or y ⊊ x, F({x, y}) = k. A two-valued measure ü on pκλ is fine if it is κ-complete and if for all α < λ, ü({x ∈ pκλ: α ∈ x}) = 1, and ü is normal if, in addition, for every function f: pκλ → λsuch that ü({x ∈ pκλ: f(x) ∈ x}) = 1, there is an α < λ such that ü({x ∈ pκλ: f(x) = α}) = 1. Finally, a fine measure on pκλ has the partition property if every F: [pκλ]2 → 2 has a homogeneous set of measure one.
The faithfulness of the interpretation of arithmetic in the theory of constructions
Authors: Goodman Nicolas D.
Published: May 2006

In my paper [1], with which I assume the reader is familiar, I defined an arithmetic theory of constructions ATC and gave an interpretation of intuitionistic arithmetic HA in ATC. I proved that, in a suitable sense, every formula provable in HA is also provable in ATC. I proved the converse of this result only for positive sentences. In the present paper I will prove in full generality that any formula of HA which is provable in ATC is already provable in HA. In a later paper I shall use this result to obtain new information about certain extensions of HA by addition of higher types.
On bar recursion of types 0 and 1
Authors: Schwichtenberg Helmut
Published: May 2006

For general information on bar recursion the reader should consult the papers of Spector [8], where it was introduced, Howard [2] and Tait [11]. In this note we shall prove that the terms of Gödel's theory T(in its extensional version of Spector [8]) are closed under the rule BR0,1 of bar recursion of types 0 and 1. Our method of proof is based on the notion of an infinite term introduced by Tait [9]. The main tools of the proof are (i) the normalization theorem for (notations for) infinite terms and (ii) valuation functionals. Both are elaborated in [6]; for brevity some familiarity with this paper is assumed here. Using (i) and (ii) we reduce BR0,1 to ξ-recursion with ξ < ε0. From this the result follows by work of Tait [10], who gave a reduction of 2ξ-recursion to ξ-recursion at a higher type. At the end of the paper we discuss a perhaps more natural variant of bar recursion introduced by Kreisel in [4].

Related results are due to Kreisel (in his appendix to [8]), who obtains results which imply, using the reduction given by Howard [2] of the constant of bar recursion of type τ to the rule of bar recursion of type (0 → τ) → τ, that T is not closed under the rule of bar recursion of a type of level ≥ 2, to Diller [1], who gave a reduction of BR0,1 to ξ-recursion with ξ bounded by the least ω-critical number, and to Howard [3], who gave an ordinal analysis of the constant of bar recursion of type 0. I am grateful to H. Barendregt, W. Howard and G. Kreisel for many useful comments and discussions.
The lattice of modal logics: an algebraic investigation
Authors: Blok W. J.
Published: May 2006

Modal logics are studied in their algebraic disguise of varieties of so-called modal algebras. This enables us to apply strong results of a universal algebraic nature, notably those obtained by B. Jónsson. It is shown that the degree of incompleteness with respect to Kripke semantics of any modal logic containing the axiom □p→P or containing an axiom of the form □mp↔□m+1p for some natural number m is . Furthermore, we show that there exists an immediate predecessor of classical logic (axiomatized by p↔□p) which is not characterized by any finite algebra. The existence of modal logics having immediate predecessors is established. In contrast with these results we prove that the lattice of extensions of S4 behaves much better: a logic extending S4 is characterized by a finite algebra iff it has finitely many extensions and any such logic has only finitely many immediate predecessors, all of which are characterized by a finite algebra.
Innocuous substitutions
Authors: Leivant Daniel
Published: May 2006

In classical first-order predicate logic CL1 (without equality) only tautologies and antitautologies satisfy nontautological schemas. I.e., if F[p, Q] is a nontautological formula (fl) in the predicate letters shown, with p prepositional, then ⊬ F[K, Q] for any sentence K not containing some Q ∈ Q, unless ⊢ K or ⊢ ¬K. This is an easy consequence of the Completeness Theorem. Clearly, the analogous statement fails for intuitionistic predicate logic IL1; already when Q is empty: (i) ¬¬ K for, e.g., K ≡ p ∨ ¬p; (ii) ¬¬K → K for, e.g., K ≡ ¬p.
Indiscernibles and decidable models
Authors: Kierstead H. A. , Remmel J. B.
Published: May 2006

Ehrenfeucht and Mostowski [3] introduced the notion of indiscernibles and proved that every first order theory has a model with an infinite set of order indiscernibles. Since their work, techniques involving indiscernibles have proved to be extremely useful for constructing models with various specialized properties. In this paper and in a sequel [5], we investigate the effective content of Ehrenfeucht's and Mostowski's result. In this paper we consider the question of which decidable theories have decidable models with infinite recursive sets of indiscernibles. In §1, using some basic facts from stability theory, we show that certain large classes of decidable theories have decidable models with infinite recursive sets of indiscernibles. For example, we show that every ω-stable decidable theory and every stable theory which possesses a certain strong decidability property called ∃Q-decidability have such models. In §2 we construct several examples of decidable theories which have no decidable models with infinite recursive sets of indiscernibles. These examples show that our hypothesis for our positive results in §1 are necessary. Finally in §3 we give two applications of our results. First as an easy application of our results in §1, we show that every ω-stable decidable theory has uncountable models which realize only recursive types. Also our counterexamples in §2 allow us to answer negatively two questions of Baldwin and Kueker [1] concerning the effectiveness of their elimination of Ramsey quantifiers for certain theories.

In [5], we show that in general the problem of finding an infinite set of indiscernibles in a decidable model is recursively equivalent to finding a path through a recursive infinite branching tree. Similarly, we show that the problem of finding an co-type of a set of indiscernibles in a decidable ω-categorical theory is recursively equivalent to finding a path through a highly recursive finitely branching tree.
Post-scriptum à “Théories instables”
Authors: Poizat Bruno
Published: May 2006

Cette note est une suite à mon article Théories instables, this Journal, vol. 46 (1981), pp. 513–522. Quand il en a eu pris connaissance, Saharon Shelah–et c'est remplir un devoir agréable que de lui témoigner ici ma reconnaissance pour l'intérêt qu'il porte à mes travaux–m'a fait savoir qu'il pouvait en simplifier les résultats, et a publié le Théorème 1 de ce post-scriptum, pour le cas des cohéritiers, dans les “added in proof” de son Simple unstable théories, Annals of Mathematical Logic, vol. 19 (1980), pp. 177–203, plusieurs mois avant que ne paraisse l'article qu'il améliore. On verra ici que ce théorème se généralise sans problème aux fils spéciaux, et que son corollaire, le Théorème 2, représente un net progrès sur mon résultat original, puisqu'il est à la fois plus général, plus précis, et obtenu à moindre frais, le lemme sur les ultrafiltres devenant inutile.

Quelques rappels pour commencer: je considère une théorie complète T, sans propriété d'indépendance; cela signifie que toute suite … ai … indicernable dans l'ordre est insécable, c'est-à-dire qu'il ne peut exister de formule f(x, ȳ) et de paramètres tels que f(ai, ) soit vraie cofinalement, et fausse cofinalement, dans la suite; cela signifie encore que cette suite s est découpée par la formule f(x, ) en un nombre fini de segments S1, …, Sk, la formule prenant la même valeur de vérité dans chaque segment, et des valeurs opposées dans des segments consécutifs; ce nombre k de segments sera appelé nombre d'alternance de la formule f(x, ) sur la suite s. On remarquera que, par compacité, ce nombre d'alternance est majoré en fonction seulement de f(x, ȳ).
Core models
Authors: Dodd A.J.
Published: May 2006

The following rough summary is intended to give the non-specialist in fine-structure an idea of what core models are and what they are used for. References are usually given to proofs but very few proofs are given. Also attribution of results is rather careless: I hope to give full historical notes in a forthcoming more detailed exposition.

Jensen is certainly responsible for the bulk of these results. This paper is based in part on a lecture he gave in Oxford in 1979, and my warmest thanks are due to him for his patient explanations of these results. (I should add that he has not seen this paper in proof and should not be held responsible for any false claims which it contains.) Mitchell has been the main driving force behind the generalisations of K, and his influence on the results in §5 is perhaps not adequately reflected there. The language of “hypermeasures” has been replaced here by “extenders”, but the reader of [14] will find translation easy.

Graeme Forbes, Robin Gandy, Wilfrid Hodges and the referee read the paper in proof and I am most grateful for their many suggested improvements.
A cut-free Gentzen-type system for the modal logic S5
Authors: Sato Masahiko
Published: May 2006

The modal logic S5 has been formulated in Gentzen-style by several authors such as Ohnishi and Matsumoto [4], Kanger [2], Mints [3] and Sato [5]. The system by Ohnishi and Matsumoto is natural, but the cut-elimination theorem in it fails to hold. Kanger's system enjoys cut-elimination theorem, but, strictly speaking, it is not a Gentzen-type system since each formula in a sequent is indexed by a natural number. The system S5+ of Mints is also cut-free, and its cut-elimination theorem is proved constructively via the cut-elimination theorem of Gentzen's LK. However, one of his rules does not have the so-called subformula property, which is desirable from the proof-theoretic point of view. Our system in [5] also enjoys the cut-elimination theorem. However, it is also not a Gentzen-type system in the strict sense, since each sequent in this system consists of a pair of sequents in the usual sense.

In the present paper, we give a Gentzen-type system for S5 and prove the cut-elimination theorem in a constructive way. A decision procedure for S5 can be obtained as a by-product.

The author wishes to thank the referee for pointing out some errors in the first version of the paper as well as for his suggestions which improved the readability of the paper.
Forcing with stable posets
Authors: Avraham Uri , Shelah Saharon
Published: May 2006

The class of stable posets is defined and investigated. We give a forcing construction of a universe of set theory which satisfies a weak form of Martin's Axiom and 2ℵ0 > ℵ1 and yet some propositions which follow from CH hold in this universe.
Independence of strong partition relation for small cardinals, and the free-subset problem
Authors: Shelah Saharon
Published: May 2006

We prove the independence of a strong partition relation on ℵω, answering a question of Erdös and Hajnal. We then give an almost complete answer to the free subset problem.
Orbits of hyperhypersimple sets and the lattice of Σ03 sets
Authors: Herrmann E.
Published: May 2006

It will be shown that in the lattice of recursively enumerable sets all lattices L3(X) are elementarily definable with parameters, where X is and L3(X) consists of all sets containing X.
A weak absolute consistency proof for some systems of illative combinatory logic
Authors: Bunder M.W.
Published: May 2006

A large number of formal systems based on combinatory logic or λ-calculus have been extended to include first order predicate calculus. Several of these however have been shown to be inconsistent, all, as far as the author knows, in the strong sense that all well formed formulas (which here include all strings of symbols) are provable. We will call the corresponding consistency notion—an arbitrary wff ⊥ is provable—weak consistency. We will say that a system is strongly consistent if no formula and its negation are provable.

Now for some systems, such as that of Kuzichev [11], the strong and weak consistency notions are equivalent, but in the systems of [5] and [6], which we will be considering, they are not. Each of these systems is strong enough to have all of ZF set theory, except Grounding and Choice, interpretable in it, and the system of [5] can also encompass first order arithmetic (see [7]). It therefore seems unlikely that a strong consistency result could be proved for these systems using elementary methods. In this paper however, we prove the weak consistency of both these systems by means that could be formulated, at least within the theory of [5]. The method also applies to the typed systems of Curry, Hindley and Seldin [10] and to Seldin's generalised types [12].
Sentences implying their own provability
Authors: Guaspari David
Published: May 2006

We begin with a simple observation and a simple question. If we fix Th(x), some reasonable formulation of “x is the Gödel number of a theorem of Peano Arithmetic”, then for any sentence σ, Peano Arithmetic proves σ → Th(⌈σ⌉). (Here ⌈σ⌉ is the canonical term denoting the Gödel number of σ.) This observation is crucial to the proof of the Second Incompleteness Theorem. Call ψ a self-prover (with respect to Th(x)) if ψ → Th(⌈ψ⌉) is a theorem of Peano Arithmetic (from now on, PA). Our simple question is this: Does the observation have a converse—must every self-prover be provably equivalent to a sentence? Whatever φ happens to be, the formula φ ∧ Th(⌈φ⌉) is a self-prover. This makes it seem clear that there must exist self-provers which are not provably : We need only use a suitably complicated φ.

Deciding what sort of complication is “suitable” and finding such a φ is surprisingly annoying. Here is a quick example: One might guess that any φ which is unprovable and would work. In that case we could take φ to be CON—that is, ¬Th(⌈0 = 1⌉); but CON ∧ Th(⌈CON⌉) is refutable in PA, so is provably equivalent to the quantifier-free formula 0 = 1.
Interpreting second-order logic in the monadic theory of order
Authors: Gurevich Yuri , Shelah Saharon
Published: May 2006

Under a weak set-theoretic assumption we interpret second-order logic in the monadic theory of order.
On the Hanf number of Souslin logic
Authors: Burgess John P.
Published: May 2006

We show it is consistent with ZFC that the Hanf number of Ellentuck's Souslin logic should be exactly .
An application of ultrapowers to changing cofinality
Authors: Dehornoy Patrick
Published: May 2006

The problem of changing the cofinality of a measurable cardinal to ω with the help of an iterated ultrapower construction has been introduced in [Bu] and more completely studied in [De]. The aim of this paper is to investigate how the construction above has to be changed to obtain an uncountable cofinality for the (previously) measurable cardinal.

A forcing approach of this question has been developed by Magidor in [Ma]. Just as in the countable case with Prikry forcing, it turns out that the needed hypothesis and the models constructed are the same in both techniques. However the ultrapowers yield a solution which may appear as more effective. In particular the sequence used to change the measurable cardinal into a cardinal of cofinality α has the property that for any β < α the restriction to β of this sequence can be used to change the cofinality of the (same) measurable cardinal to β.

The result we prove is as follows:

Theorem. Assume that α is a limit ordinal, that (Uβ)β<α is a sequence of complete ultrafilters on κ > α in the model N0, andfor B included in α let NB be the ultrapower of N0 by those Uβ which are such that β is in B.
Large families of incomparable A-isols
Authors: Heck William S.
Published: May 2006

The set Λ of isols was extensively studied by Dekker and Myhill in [1]. Subsequently, Nerode [3] developed the theory of Λ(A), the set of isols relative to some recursively closed set of functions A.

One of the main areas of interest of [1] was the natural partial order ≤ on Λ. In this paper we will examine some of the properties of ≤A on Λ(A). We use the following notations: ∣A∣ is the cardinality of the set A, ⊃ denotes strict inclusion, (a) is the power set of the set a, c is the cardinality of the continuum, and ω = {0, 1, 2, …}. The terms A-isol, A-immune, A-r.e., A-incomparable, etc. all refer to the usual meaning of these words, only taken in the context of the recursively closed set A. ReqA(a) is the A-r.e.t. of which a is a representative. By identifying a finite natural number with the A-r.e.t. consisting of sets of a given finite cardinality we see that ω ⊆ Λ(A); Λ(A) is said to be nontrivial iff ω ⊃ Λ(A). The three results proven in this paper are:

Theorem 1. If Λ(A) is nontrivial, then ∣Λ(A)∣ = c.

Theorem 2. If∣A∣ < c, then Λ(A) is nontrivial.

Theorem 3. If ∣A∣ < c and ∣⊿∣ < c and ⊿ ⊆ Λ(A) − ω, then there is aΓ ⊆ Λ(A) − ω such that:

(a) ∣Γ∣ = c.

(b) Every member of Γ is A-incomparable with every member of Δ.

(c) Any two distinct members of Γ are A-incomparable.
The monadic theory of ω2
Authors: Gurevich Yuri , Magidor Menachem , Shelah Saharon
Published: May 2006

Assume ZFC + “There is a weakly compact cardinal” is consistent. Then:

(i) For every S ⊆ ω, ZFC + “S and the monadic theory of ω2 are recursive each in the other” is consistent; and

(ii) ZFC + “The full second-order theory of ω2 is interpretable in the monadic theory of ω2” is consistent.
Axiomatization of polynomial substitution algebras
Authors: Feldman Norman
Published: May 2006

The axiomatization of algebras of functions or partial functions under various operations has been studied by several authors. Menger [2] deals with the problem of axiomatizing the algebraic properties of 1-ary functions from the reals to the reals. He considers algebras with one of three binary operations corresponding to addition, multiplication or composition. This study is furthered by Schweizer and Sklar in [3]–[6]. In addition to the operations mentioned above they also introduce a partial ordering which corresponds to restriction of functions. In the second of these papers they give a set of axioms such that any system satisfying these axioms is order isomorphic to a concrete system of partial functions under composition and ordered by restriction. In [7] Schweizer and Sklar extend their work to the algebra of multiplace vector-valued functions. In [8] Whitlock studies abstract multiplaced function systems given by super-associative laws and shows that these systems are isomorphically embeddable in a concrete system of multiplaced functions where the operation on the functions is substitution of an m-ary function in an n-ary function.

In this paper we consider the set of functions from Uα, the set of α-sequences, to U where a is an infinite ordinal. As opposed to the composition operations studied in the above works, we consider the composition operations *κ, for κ < α, in a narrow sense—the substitution of one function in the κth place of another. The algebras studied have the form ‹A, *κ, Vκ› κ<α where Vκ are the projection (selector) functions on the κth place. In particular, the polynomials over an algebra form such an algebra called a polynomial substitution algebra. In §6 we show that a first-order axiom system and a condition of local finiteness, given by Pinter in a talk at Berkeley in 1972 to characterize term substitution abgebras, also characterize these polynomial substitution algebras.
A normal form theorem for Lω1p, with applications
Authors: Hoover Douglas N.
Published: May 2006

We show that every formula of Lω1P is equivalent to one which is a propositional combination of formulas with only one quantifier. It follows that the complete theory of a probability model is determined by the distribution of a family of random variables induced by the model. We characterize the class of distribution which can arise in such a way. We use these results together with a form of de Finetti’s theorem to prove an almost sure interpolation theorem for Lω1P.
A new inner model for ZFC
Authors: Zadrozny Wlodzimierz
Published: May 2006

Assume (∃κ) [κ → (κ)<ω & Rκ ≺ V]. Then a new inner model H exists and has the following properties: (1) H ≠ HOD; (2) Th(H) = Th(HOD); (3) there is j: H → H; (4) there is a c.u.b. class of indiscernibles for H.
On the Ramsey property for sets of reals
Authors: Kastanas Ilias G.
Published: May 2006

We review some known results about the Ramsey property for partitions of reals, and we present a certain two-person game such that if either player has a winning strategy then a homogeneous set for the partition can be constructed, and conversely. This gives alternative proofs of some of the known results. We then discuss possible uses of the game in obtaining effective versions of Ramsey's theorem and prove a theorem along these lines.
On a generalization of Jensen's □κ, and strategic closure of partial orders
Authors: Velleman Dan
Published: May 2006

It is well known that many statements provable from combinatorial principles true in the constructible universe L can also be shown to be consistent with ZFC by forcing. Recent work by Shelah and Stanley [4] and the author [5] has clarified the relationship between the axiom of constructibility and forcing by providing Martin's Axiom-type forcing axioms equivalent to ◊ and the existence of morasses. In this paper we continue this line of research by providing a forcing axiom equivalent to □κ. The forcing axiom generalizes easily to inaccessible, non-Mahlo cardinals, and provides the motivation for a corresponding generalization of □κ.

In order to state our forcing axiom, we will need to define a strategic closure condition for partial orders. Suppose P = 〈P, ≤〉 is a partial order. For each ordinal α we will consider a game played by two players, Good and Bad. The players choose, in order, the terms in a descending sequence of conditions 〈pβ∣β < α〉 Good chooses all terms pβ for limit β, and Bad chooses all the others. Bad wins if for some limit β<α, Good is unable to move at stage β because 〈pγ∣γ < β〉 has no lower bound. Otherwise, Good wins. Of course, we will be rooting for Good.
An undecidability result for relation algebras
Authors: Schönfeld Wolfgang
Published: May 2006

The elementary calculus of binary relations as developed by Tarski in [5] may be thought of as a certain part of the first-order predicate calculus. Though less expressive, its theory (i.e. the set of its valid sentences) was shown to be undecidable by Tarski in [6]. Translated into algebraic logic this means that the equational theory of the class of relation algebras is undecidable. Similarly it can be proved that the same holds for the (sub-) class of proper relation algebras.

The idea in Tarski's proof is to describe a pairing function by which any quantifier prefix may be contracted. In this note we apply a different method to treat the case of finite structures. We prove the

Theorem. The equational theory of the class of finite proper relation algebras is undecidable.

This result was announced in [4]. The main tool is representing the graph of primitive recursive functions via the cardinalities in finite simple models of equations.
The metamathematics of model theory: Discovering language in action
Authors: Miller Douglas E.
Published: May 2006

We discuss the problem of defining the collection of first-order elementary classes in terms of the natural topological space of countable models.
The number of one-generated cylindric set algebras of dimension greater than two
Authors: Larson Jean A.
Published: May 2006

S. Ulam asked about the number of nonisomorphic projective algebras with κ generators. This paper answers his question for projective algebras of finite dimension at least three and shows that there are the maximum possible number, continuum many, of nonisomorphic one-generated structures of finite dimension n, where n is at least three, of the following kinds: projective set algebras, projective algebras, diagonal-free cylindric set algebras, diagonal-free cylindric algebras, cylindric set algebras, and cylindric algebras. The results of this paper extend earlier results to the collection of cylindric set algebras and provide a uniform proof for all the results. Extensions of these results for dimension two are discussed where some modifications on the hypotheses are needed. Furthermore for α ≥ 2, the number of isomorphism classes of regular locally finite cylindric set algebras of dimension α of the following two kinds are computed: ones of power κ for infinite κ ≥ ∣α∣, and ones with a single generator.
Logics without the contraction rule
Authors: Ono Hiroakira , Komori Yuichi
Published: May 2006

We will study syntactical and semantical properties of propositional logics weaker than the intuitionistic, in which the contraction rule (or, the exchange rule or the weakening rule, in some cases) does not hold. Here, the contraction rule means the rule of inference of the form

if we formulate our logics in a Gentzen-type formal system. Some syntactical properties of these logics have been studied firstly by the second author in [11], in connection with the study of BCK-algebras (for information on BCK-algebras, see [9]). There, it turned out that such a syntactical method is a powerful and promising tool in studying BCK-algebras. Using this method, considerable progress has been made since then (see, e.g., [8], [18], [27]).

In this paper, we will study these logics more comprehensively. We notice here that the distributive law

does not hold necessarily in these logics. By adding some axioms (or initial sequents) and rules of inference to these basic logics, we can obtain a lot of interesting nonclassical logics such as Łukasiewicz's many-valued logics, relevant logics, the intuitionistic logic and logics related to BCK-algebras, which have been studied separately until now. Thus, our approach will give a uniform way of dealing with these logics. One of our two main tools in doing so is Gentzen-type formulation of logics in syntax, and the other is semantics defined by using partially ordered monoids.
Co-critical points of elementary embeddings
Authors: Sheard Michael
Published: May 2006

Probably the two most famous examples of elementary embeddings between inner models of set theory are the embeddings of the universe into an inner model given by a measurable cardinal and the embeddings of the constructible universeLinto itself given by 0#. In both of these examples, the “target model” is a subclass of the “ground model” (and in the latter case they are equal). It is not hard to find examples of embeddings in which the target model is not a subclass of the ground model: ifis a generic ultrafilter arising from forcing with a precipitous ideal on a successor cardinalκ, then the ultraproduct of the ground model viacollapsesκ. Such considerations suggest a classification of how close the target model comes to “fitting inside” the ground model.

Definition 1.1. LetMandNbe inner models (transitive, proper class models) of ZFC, and letj:M→Nbe an elementary embedding. Theco-critical pointofjis the least ordinalλ, if any exist, such that there isX⊆λ, X∈NbutX∉M. Such anXis called anew subsetofλ.

It is easy to see that the co-critical point ofj:M→Nis a cardinal inN.
On two hierarchies of dimensions
Authors: Baudisch Andreas
Published: May 2006

Let T be a countable, complete, ω-stable, nonmultidimensional theory. By Lascar [7], in Teq there is in every dimension of T a type with Lascar rank ωα for some α. We give sufficient conditions for α to coincide with the level of that dimension in Pillay's [10] RK-hierarchy of dimensions computed in Teq. In particular, this is fulfilled for modules.
Corps portant un nombre fini de valuations
Authors: Delon Françoise
Published: May 2006

L. van den Dries proved that the theory of n-valued rings has a model companion. We show here that this result is still true when the valuation rings are required to satisfy given inclusion relations (we restrict ourselves to the case of residual characteristic zero).
Locally finite theories
Authors: Mycielski Jan
Published: May 2006

We say that a first order theoryTislocally finiteif every finite part ofThas a finite model. It is the purpose of this paper to construct in a uniform way for any consistent theoryTa locally finite theory FIN(T) which is syntactically (in a sense) isomorphic toT.

Our construction draws upon the main idea of Paris and Harrington [6] (I have been influenced by some unpublished notes of Silver [7] on this subject) and generalizes the syntactic aspect of their result from arithmetic to arbitrary theories. (Our proof is syntactic, and it is simpler than the proofs of [5], [6] and [7]. This reminds me of the simple syntactic proofs of several variants of the Craig-Lyndon interpolation theorem, which seem more natural than the semantic proofs.)

The first mathematically strong locally finite theory, called FIN, was defined in [1] (see also [2]). Now we get much stronger ones, e.g. FIN(ZF).

From a physicalistic point of view the theorems of ZF and their FIN(ZF)-counterparts may have the same meaning. Therefore FIN(ZF) is a solution of Hilbert's second problem. It eliminates ideal (infinite) objects from the proofs of properties of concrete (finite) objects.

In [4] we will demonstrate that one can develop a direct finitistic intuition that FIN(ZF) is locally finite. We will also prove a variant of Gödel's second incompleteness theorem for the theory FIN and for all its primitively recursively axiomatizable consistent extensions.

The results of this paper were announced in [3].
Some results concerning strongly compact cardinals
Authors: Abe Yoshihiro
Published: May 2006

This paper consists of two parts. In §1 we mention the first strongly compact cardinal. Magidor proved in [6] that it can be the first measurable and it can be also the first supercompact. In [2], Apter proved that Con(ZFC + there is a supercompact limit of supercompact cardinals) implies Con(ZFC + the first strongly compact cardinal κ is ϕ(κ)-supercompact + no α < κ is ϕ(α)-supercompact) for a formula ϕ which satisfies certain conditions.

We shall get almost the same conclusion as Apter's theorem assuming only one supercompact cardinal. Our notion of forcing is the same as in [2] and a trick makes it possible.

In §2 we study a kind of fine ultrafilter on Pκλ investigated by Menas in [7], where κ is a measurable limit of strongly compact cardinals. He showed that such an ultrafilter is not normal in some case (Theorems 2.21 and 2.22 in [7]). We shall show that it is not normal in any case (even if κ is supercompact). We also prove that it is weakly normal in some case.

We work in ZFC and much of our notation is standard. But we mention the following: the letters α,β,γ… denote ordinals, whereas κ,λ,μ,… are reserved for cardinals. R(α) is the collection of sets rank <α. φM denotes the realization of a formula φ to a class M. Except when it is necessary, we drop “M”. For example, M ⊩ “κ is φ(κ)-supercompact” means “κ is φM(κ)-supercompact in M”. If x is a set, |x| is its cardinality, Px is its power set, and . If also x ⊆ OR, denotes its order type in the natural ordering. The identity function with the domain appropriate to the context is denoted by id. For the notation concerning ultrapowers and elementary embeddings, see [11]. When we talk about forcing, “⊩” will mean “weakly forces” and “p < q” means “p is stronger than q”.
On ideals of subsets of the plane and on Cohen reals
Authors: Cichoń Jacek , Pawlikowski Janusz
Published: May 2006

Let be any proper ideal of subsets of the real line R which contains all finite subsets of R. We define an ideal * ∣ as follows: X ∈ * ∣ if there exists a Borel set B ⊂ R × R such that X ⊂ B and for any x ∈ R we have {y ∈ R: 〈x, y〉 ∈ B} ∈ . We show that there exists a family ⊂ * ∣ of power ω1 such that ⋃ ∉ * ∣ .

In the last section we investigate properties of ideals of Lebesgue measure zero sets and meager sets in Cohen extensions of models of set theory.
Completeness theorem for biprobability models
Authors: Rašković Miodrag D.
Published: May 2006

The aim of the paper is to prove the completeness theorem for biprobability models. This also solves Keisler's Problem 5.4 (see [4]).

Let be a countable admissible set and ω ∈ . The logic is similar to the standard probability logic . The only difference is that two types of probability quantifiers and are allowed.

A biprobability model is a structure (, μ1, μ2) where is a classical structure without operations and μ1, μ2 are two types of probability measures such that μ1 is absolutely continuous with respect to μ2, i.e. μ1 ≪ μ2.

The quantifiers are interpreted in the natural way, i.e.

for i = 1, 2. (The measure is the restriction of the completion of to the σ-algebra generated by the measurable rectangles and the diagonal sets

Axioms and rules of inference are those of , as listed in [2] with the axiom B4 from [4], with the remark that both P1 and P2 can play the role of P, together with the following axioms:

Axioms of continuity.

1) .

2) .

Axiom of absolute continuity:

where and Φn = {φ ∈ Φ: φ has n free variables}.
On the Kleene degrees of Π11 sets
Authors: Slaman Theodore A.
Published: May 2006

Let A and B be subsets of the reals. Say that AK≥ B, if there is a real a such that the relation “x ∈ B” is uniformly ⊿1 (a, A) in . This reducibility induces an equivalence relation ≡K on the sets of reals; the ≡K-equivalence class of a set is called its Kleene degree. Let be the structure that consists of the Kleene degrees and the induced partial order ≥. A substructure of that is of interest is , the Kleene degrees of the sets of reals. If sharps exist, then there is not much to , as Steel [9] has shown that the existence of sharps implies that has only two elements: the degree of the empty set and the degree of the complete set. Legrand [4] used the hypothesis that there is a real whose sharp does not exist to show that there are incomparable elements in ; in the context of V = L, Hrbáček has shown that is dense and has no minimal pairs. The Hrbáček results led Simpson [6] to make the following conjecture: if V = L, then forms a universal homogeneous upper semilattice with 0 and 1. Simpson's conjecture is shown to be false by showing that if V = L, then Gödel's maximal thin set is the infimum of two strictly larger elements of .

The second main result deals with the notion of jump in . Let A′ be the complete Kleene enumerable set relative to A. Say that A is low-n if A(n) has the same degree as ⊘(n), and A is high-n if A(n) has the same degree as ⊘(n+1). Simpson and Weitkamp [7] have shown that there is a high (high-1) incomplete set in L. They have also shown that various other sets are neither high nor low in L. Legrand [5] extended their results by showing that, if there is a real x such that x# does not exist, then there is an element of that, for all n, is neither low-n nor high-n. In §2, ZFC is used to show that, for all n, if A is and low-n then A is Borel. The proof uses a strengthened version of Jensen's theorem on sequences of admissible ordinals that appears in [7, Simpson-Weitkamp].
Σ1 definitions with parameters
Authors: Slaman T. A.
Published: May 2006

Let p be a set. A function Φ is uniformly Σ1(p) in every admissible set if there is a Σ1 formula ϕ in the parameter p so that ϕ defines Φ in every Σ1-admissible set which includes p. A theorem of Van de Wiele states that if Φ is a total function from sets to sets then Φ is uniformly Σ1 in every admissible set if and only if it is E-recursive. A function is ESp-recursive if it can be generated from the schemes for E-recursion together with a selection scheme over the transitive closure of p. The selection scheme is exactly what is needed to insure that the ESP-recursively enumerable predicates are closed under existential quantification over the transitive closure of p. Two theorems are established: a) If the transitive closure of p is countable then a total function on sets is ESp-recursive if and only if it is uniformly Σ1(p) in every admissible set. b) For any p, if Φ is a function on the ordinal numbers then Φ is ESP-recursive if and only if it is uniformly Σ1(p) in every admissible set.
The word problem for cancellation semigroups with zero
Authors: Gurevich Yuri , Lewis Harry R.
Published: May 2006

By theword problemfor some class of algebraic structures we mean the problem of determining, given a finite setEof equations between words (i.e. terms) and an additional equationx=y, whetherx=ymust hold in all structures satisfying each member ofE. In 1947 Post [P] showed the word problem for semigroups to be undecidable. This result was strengthened in 1950 by Turing, who showed the word problem to be undecidable forcancellation semigroups,i.e. semigroups satisfying thecancellation property

Novikov [N] eventually showed the word problem for groups to be undecidable.

(Many flaws in Turing's proof were corrected by Boone [B]. Even after his corrections, at least one problem remains; the sentence on line 16 of p. 502 of [T] does not follow if one relation is principal and the other is a commutation relation. A corrected and somewhat simplified version of Turing's proof can be built on the construction given here.)

In 1966 Gurevich [G] showed the word problem to be undecidable forfinitesemigroups. However, this result on finite structures has not been extended to cancellation semigroups or groups; indeed it is easy to see that a finite cancellation semigroup is a group, so both questions are the same. We do not here settle the word problem for finite groups, but we do show that the word problem is undecidable for finite semigroups with zero (that is, having an element 0 such thatx0 = 0x= 0 for allx) satisfying an approximation to the cancellation property (1).
A minimal degree which collapses ω1
Authors: Carlson Tim , Kunen Kenneth , Miller Arnold W.
Published: May 2006

We consider a well-known partial order of Prikry for producing a collapsing function of minimal degree. Assuming MA + ¬CH, every new real constructs the collapsing map.
Register machine proof of the theorem on exponential diophantine representation of enumerable sets
Authors: Jones J. P. , Matijasevič Y. V.
Published: May 2006

The purpose of the present paper is to give a new, simple proof of the theorem of M. Davis, H. Putnam and J. Robinson [1961], which states that every recursively enumerable relation A(a1, …, an) is exponential diophantine, i.e. can be represented in the form

where a1 …, an, x1, …, xm range over natural numbers and R and S are functions built up from these variables and natural number constants by the operations of addition, A + B, multiplication, AB, and exponentiation, AB. We refer to the variables a1,…,an as parameters and the variables x1 …, xm as unknowns.

Historically, the Davis, Putnam and Robinson theorem was one of the important steps in the eventual solution of Hilbert's tenth problem by the second author [1970], who proved that the exponential relation, a = bc, is diophantine, and hence that the right side of (1) can be replaced by a polynomial equation. But this part will not be reproved here. Readers wishing to read about the proof of that are directed to the papers of Y. Matijasevič [1971a], M. Davis [1973], Y. Matijasevič and J. Robinson [1975] or C. Smoryński [1972]. We concern ourselves here for the most part only with exponential diophantine equations until §5 where we mention a few consequences for the class NP of sets computable in nondeterministic polynomial time.
Quelques précisions sur la D.O.P. et la profondeur d'une théorie
Authors: Lascar D.
Published: May 2006

We give here alternative definitions for the notions that S. Shelah has introduced in recent papers: the dimensional order property and the depth of a theory. We will also give a proof that the depth of a countable theory, when denned, is an ordinal recursive in T.