bluuebunny/crossref_metadata_2025 huggingface dataset:
Partition properties of M-ultrafilters and ideals
Authors: Takahashi Joji
Published: May 2006

As is well known, the following are equivalent for any uniform ultrafilter U on an uncountable cardinal:

(i) U is selective;

(ii) U → ;

(iii) U → .

In §1 of this paper, we consider this result in terms of M-ultrafilters (Definition 1.1), where M is a transitive model of ZFC (Zermelo-Fraenkel set theory with the axiom of choice). We define the partition properties and for M-ultrafilters (Definition 1.3), and characterize those M-ultrafilters that possess these properties (Theorem 1.5) so that the result mentioned at the beginning is subsumed as the special case that M is V, the universe of all sets. It turns out that the two properties have to be handled separately, and that, besides selectivity, we need to formulate additional conditions (Definition 1.4). The extra conditions become superfluous when M = V because they are then trivially satisfied. One of them is nothing new; it is none other than Kunen's iterability-of-ultrapowers condition.

In §2, we obtain characterizations of the partition properties I+ → and I+ → (Definition 2.3) of uniform ideals I on an infinite cardinal κ (Theorem 2.6). This is done by applying the main results of §1 to the canonical -ultrafilter in the Boolean-valued model constructed from the completion of the quotient algebra P(κ)/I. They are related to certain known characterizations of weakly compact and of Ramsey cardinals.

Our basic set theory is ZFC. In §1, it has to be supplemented by a new unary predicate symbol M and new nonlogical axioms that make M look like a transitive model of ZFC.
Polynomial size proofs of the propositional pigeonhole principle
Authors: Buss Samuel R.
Published: May 2006

Cook and Reckhow defined a propositional formulation of the pigeonhole principle. This paper shows that there are Frege proofs of this propositional pigeonhole principle of polynomial size. This together with a result of Haken gives another proof of Urquhart's theorem that Frege systems have an exponential speedup over resolution. We also discuss connections to provability in theories of bounded arithmetic.
A constructive analysis of RM
Authors: Avron Arnon
Published: May 2006

The system RM is the most well-understood (and to our opinion, also the most important) system among the logics developed by the Anderson and Belnap school. In this paper we investigate RM from a constructive point of view. For example, we give a new proof of the completeness of RM relative to the Sugihara matrix (first shown by Meyer), a proof in which a p.r. procedure is presented, applying which to a sentence A in RM language yields either a proof of it in RM or a refuting valuation for it in the Sugihara matrix SZ.

Two topics dealt with in this work deserve a special attention.

a) The admissibility of γ. This is a famous theorem of Meyer and Dunn. In [1] Anderson and Belnap emphasize that “the Meyer-Dunn argument … guarantees the existence of a proof of B, but there is no guarantee that the proof of B is related in any sort of plausible way to the proofs of A and Ā ∨ B.” In §2 we provide such a guarantee for the RM-case. In fact, we give there a direct method of obtaining a proof of B from given proofs of A and Ā ∨ B.

b) The relationships betweenRMand its full negation-implication fragment. RM is known ([1, pp. 148–149], and [3]) to be a conservative extension of (Sobociński 3-valued logic; see [4]). Anderson and Belnap admit [1, p. 149] that this fact came to them as a distinct surprise, since RM as a whole is far from being three-valued. In this paper, however, this “surprising” fact appears quite natural (see III.3). In fact, we show that , is the “hard core” of RM, since our proof of the completeness of RM is based in an essential way on the completeness of relative to the Sobociński matrix, and since the Gentzen-type calculus we develop for RM is a direct extension of a similar (but much simpler) calculus for . Because of the importance has in this work, we devote the first section to a constructive investigation of it.

We note, finally, that the Gentzen-type calculus mentioned above admits cut-elimination and normal-form techniques. (Such calculi were found till now only for RM without distribution.)
Uncountable master codes and the jump hierarchy
Authors: Lubarsky Robert S.
Published: May 2006

The Turing jump can easily be iterated any finite number of times. The challenge is posed by by transfinite iterations. a(ω) has an intuitively compelling definition: {‹m, n›: n ∈ a(m)}. Starting with Putnam et al. [1], [2], [9] and culminating in Jockusch-Simpson [8] and Hodes [6], recent work has justified this ω-jump and extended it through .

Of great use are the master codes of Jensen [3], [7]. Briefly, a Δn(Lβ)-master code is a complete Δn(Lβ) set of ordinals, with supremum as small as possible. Connections with classical recursion theory are tight. When the Δn(Lβ) master codes are reals, they are Turing equivalent. If a is a Δn(Lβ) MC, then a′ is a Δn + 1(Lβ) MC. Intuitively satisfying transfinite jumps, such as the ω-jump above, produce a Turing jump hierarchy equal to an initial segment of the master codes.

Hodes capitalized on these facts by defining 0α, α < , set-theoretically as the degree of the αth MC which is a real, and then proving the equivalence of a jump-theoretic definition of 0α. The successor codes are jumps of their predecessors, and for a limit λ, 0λ is the minimum of a set of degrees associated with {0α: α: < λ}.
Théories d'algèbres de Boole munies d'idéaux distingués. I: Théories élémentaires
Authors: Touraille Alain
Published: May 2006

Une conséquence de la classification des théories complètes d'algèbres de Boole par Tarski [5] est que la théorie élémentaire d'une algèbre de Boole A est déterminée par le type d'isomorphisme du treillis de ses idéaux définissables et, pour chacun de ces idéaux, par le nombre d'atomes du quotient de A par cet idéal lorsque ce nombre est fini. Une remarque analogue peut être faite à propos des cas particuliers d'algèbres de Boole munies d'un idéal distingué étudiés par Ershov [1] et par Jurie et Touraille [3]; dans to us ces cas, c'est la simplicité des treillis possibles qui permet la classification des théories complètes. Le résultat principal de cet article est que, dans le cas général d'une algèbre de Boole munie d'une famille quelconque d'idéaux distingués, la théorie d'un modèle peut encore être caractérisée grâce à une structure algébrique sur l'ensemble de ses idéaux définissables. Il s'agit d'une structure d'algèbre de Heyting munie d'une opération unaire sa définie par sa(K) = {a: a/K est sans atome}, et cette structure s'avère être engendrée par les idéaux distingués du modèle. La méthode utilisée est l'élimination directe des quantificateurs, par réductions successives des formules. Elle nécessite des propriétés algébriques et topologiques qui sont données aux §§1 et 2: on introduit au §1 la notion d'algèbre de Heyting étoilée, c'est-à-dire d'algèbre de Heyting munie d'une opération unaire * vérifiant des égalités qui permettent de rendre compte, d'une certaine façon, de la dérivation de Cantor-Bendixon; le §2 est consacré à des propriétés topologiques qui, dans le cas de l'espace de Stone d'une algèbre de Boole A, permettent d'éclaircir les relations possibles entre les atomes des quotients de A par des idéaux différents.
No Jónsson filters over ℵω
Authors: Tryba Jan
Published: May 2006

Answering a question of A. Kanamori, we prove that there is no Jónsson filter over the least Jónsson cardinal. We also notice that, assuming □κ, the successor κ+ cannot be Jónsson.
Morasses and the Lévy-collapse
Authors: Komjáth P.
Published: May 2006

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

Our notations are standard. For excellent survey papers on morass-like principles and their uses in combinatorial set theory see [4,5,6].
Axioms for the set-theoretic hierarchy
Authors: van Aken James
Published: May 2006

The axioms for Zermelo-Fraenkel (ZF) set theory are an appealing but somewhat arbitrary-seeming assortment. A survey of the axioms does not suffice to reveal the source of their attraction. Accordingly, attempts have been made to ground ZF in principles whose appeal can be felt immediately. These attempts can be classified as follows. First, some of them propose to rest the ZF axioms directly on informal doctrine. The others propose to ground the ZF axioms in other formal axioms that can be regarded as more basic. When the latter approach is taken, ZF continues to draw on informal support, but the draft is made at a more basic level.

The same research can be classified in another way, according to the informal diagnosis offered for the paradoxes of set theory. In some cases, the diagnosis is that the paradoxical sets (such as the Russell set) fail to exist only because they would have to be too large; a set that would be sufficiently small must always exist. This is the doctrine of limitation of size. In other cases, the diagnosis is that the paradoxical sets fail to exist only because they would have to lie too high in a certain hierarchy of sets; a set that would lie sufficiently low in the hierarchy must always exist. This is the doctrine of the hierarchy. The present paper will investigate the latter doctrine, with the doctrine of size making a brief appearance at the end.
Degrees coded in jumps of orderings
Authors: Knight Julia F.
Published: May 2006

All structures to be considered here have universe ω, and all languages come equipped with Gödel numberings. If is a structure, then D(), the open diagram of , can be thought of as a subset of ω, and it makes sense to talk about the Turing degree deg(D()). This depends on the presentation as well as the isomorphism type of .

For example, consider the ordering = (ω, <). For any B ⊆ ω, it is possible to code B in a copy of as follows: Let π be the permutation of ω such that for each n ∈ ω, π leaves 2n and 2n + 1 fixed if n ∈ B and switches 2n with 2n + 1 if n ∉ B. Let be the copy of such that ≃π. Then n ∈ B iff the sentence 2n < 2n + 1 is in D(). In §4, this idea will be used to show that for any structure that is not completely trivial, {deg(D()): ≃ } is closed upwards.

It would be satisfying to have a way of assigning Turing degrees to structures such that the degree assigned to a given structure measured the recursion-theoretic complexity of the isomorphism type and was independent of the presentation. Jockusch suggested the following.
Partitions and filters
Authors: Matet P.
Published: May 2006

In [2], Carlson and Simpson proved a dualized version of Ramsey's theorem obtained by coloring partitions of ω instead of subsets of ω. It was at the suggestion of Simpson that the author undertook to study the notion dual to that of a Ramsey ultrafilter. After stating the basic terminology and notation used in the paper in §1, in §2 we establish some basic properties of the lattice of all partitions of a cardinal κ. §3 is devoted to the study of families of pairwise disjoint partitions of ω. §4 is concerned with descending sequences of partitions. In §5, we give some examples of filters of partitions. Properties of such filters are discussed in §6. Co-Ramsey filters are introduced in §7, and it is shown how they can be associated with Ramsey ultrafilters. The main result of §8 is Proposition 8.1, which asserts the existence of a co-Ramsey filter under the continuum hypothesis.

We use standard set theoretic conventions and notation. Let κ be a cardinal. We set κ* = κ − {0}. For every ordinal α ≤ κ, (κ)α denotes the set of those sequences X(ν), ν < α, of pairwise disjoint nonempty subsets of κ such that ⋃ν<αX(ν) = κ, and ⋂X(ν) < ⋂X(ν′) whenever ν < ν′. We also let (κ)≤α = ⋃β≤α(κ)β and (κ)<α = ⋃β<α(κ)β. Given X ∈ (κ)α, we put xν = ⋂X(ν) for every ν < α, and we denote by Ax the set of all xν, 0 < ν < α.
Axioms of symmetry: Throwing darts at the real number line
Authors: Freiling Chris
Published: May 2006

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

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

In this paper we consider various generalizations of the notion of hugeness. We remind the reader that a cardinal κ is huge if there exist a cardinal λ > κ, an inner model M which is closed under λ-sequences, and an elementary embedding i: V → M with critical point κ such that i(κ) = λ. We shall call λ a target for κ and shall write κ → (λ) to express this fact. Equivalently, κ is huge with target λ if and only if there exists a normal ultrafilter on P=κ(λ) = {X ⊆ λ:X has order type κ}. For the proof and additional facts on hugeness, see [3].

We assume that the reader is familiar with the notions of measurability and supercompactness. If κ is γ-supercompact for each γ < λ, we shall say that κ is < λ-supercompact. We note that if κ → (λ), it follows immediately that κ is < λ-supercompact.

Throughout the paper, n shall be used to denote a positive integer, the letters α, β, and δ shall denote ordinals, while κ, λ, γ, and η shall be reserved for cardinals. All addition is ordinal addition. V denotes the universe of all sets.

All results except for Theorems 6b and 6c and Lemma 6d can be formalized in ZFC.

This paper was written while the first named author was at Rochester Institute of Technology, Rochester, New York. We wish to thank the department of mathematics at R.I.T. for secretarial time and facilities.
The strength of admissibility without foundation
Authors: Jäger Gerhard
Published: May 2006

The following is part of a series of papers on theories for (iterated) admissible sets (cf. [10], [11], [12], [14], [15]). Although these theories are weak subsystems of Zermelo-Fraenkel set theory, they allow one to formalize and prove a fair amount of definability theory and generalized recursion theory. Using this machinery it is in general not very hard to establish the connections between theories for admissible sets and (for example) systems of second order arithmetic. A proof-theoretic analysis of theories for admissible sets therefore provides quite a uniform and powerful framework for the proof-theoretic treatment of many systems of set theory, second order arithmetic and constructive mathematics (see [12] and [15]). The strongest result in this direction so far is the pair of proof-theoretic equivalences

where T0 is Feferman's system for explicit mathematics of [5] and [6], (-CA) + (BI) is the usual system of second order arithmetic with the axiom of -comprehension and bar induction and KPi is Kripke-Platek set theory with ∈-induction

for arbitrary formulas and the additional axiom

.

The least standard model of KPi is L(i0) where i0 is the first recursively inaccessible ordinal.

In this paper we are mainly interested in the theory KPi0 which results from KPi by severely restricting the principles of induction. Basically, complete induction on the natural numbers

is allowed only for ∆0-formulas, and (IND∈) is omitted completely.
On the embedding of α-recursive presentable lattices into the α-recursive degrees below 0′
Authors: Yang Dong Ping
Published: May 2006

An important problem, widely treated in the analysis of the structure of degree orderings, is that of partial order and lattice embeddings. Thus for example we have the results on embeddings of all countable partial orderings in the Turing degrees by Kleene and Post [3] and in the r.e. T-degrees by Sacks [10]. For lattice embeddings the work on T-degrees culminated in the characterization of countable initial segments by Lachlan and Lebeuf [4]. For the r.e. T-degrees there has been a continuing line of progress on this question. (See Soare [20] and Lerman, Shore, and Soare [8].) Similar projects have been undertaken for the T-degrees below 0′ (Kleene and Post [3], Lerman [6]) as well as for most other degree orderings. The results have been used not only to analyse individual orderings but also to distinguish between them (Shore [16], [19], [17]).

The situation for α-jecursive theory, the study of recursion in (admissible) ordinals, is similar to, though not as well developed as, that for Turing degrees. All afinite partial orderings have been embedded even in the α-r.e. degrees (see Lerman [5]). Lattice embedding results are somewhat fragmentary however. In terms of initial segments even the question of the existence of a minimal α-degree has not been settled for all admissibles. (See Shore [12] for a proof for Σ2-admissible ordinals, however.) Results on more complicated lattices have only reached to the finite distributive ones for Σ3-admissible ordinals (see Dorer [1]).
Models of the alternative set theory
Authors: Pudlák P. , Sochor A.
Published: May 2006

Classical set theory is considered as the framework of contemporary mathematics. But there are aspects of our understanding of the real world about what it is not clear that they are described in Cantor's set theory in the best possible way. For example the formalization of some intuitive concepts such as the description of vague properties (which led to the theory of fuzzy sets) and the interpretation of the notion of infinitely small quantities (modelled by nonstandard models) is not quite simple in the classical set theory. Therefore it is natural to look for an alternative to Cantor's set theory which would enable us to formalize these considerations more naturally and which would be a sufficiently strong framework for mathematics at the same time.

The alternative set theory which was created by P. Vopěnka (cf. [V]) is an attempt to construct a theory that could serve as an alternative to Cantor's set theory. The ideas of the alternative set theory make it possible to constitute a new approach to mathematics. An effort to formalize mathematically our intuitive concepts once more is made, and moreover it seems that one can obtain in the alternative set theory mathematical formalizations of concepts which up to now were not adequately formalized.

In the alternative set theory we can build up all essential parts of mathematics. Development of the classical disciplines is described in [V]. Let us mention a few further results obtained in the alternative set theory: a connection between the discrete and the continuous on the basis of which it is possible to define topology (cf. [V]), investigation of motion (cf. [V]), construction of different types of σ-additive ultrafilters (cf. [S-V4]), classification of classes (measurement of vagueness of properties; cf. [Č-V]), possibility of definition of notions of nonstandard methods (cf. [S-V 1]) and valuations of ideals (cf. [M]). A series of articles has been written developing mathematics in the alternative set theory (for the full list of papers cf. [S]). For some remarks concerning the connection between the alternative set theory and nonstandard methods, the reader is refered to [S 4].
Church's thesis, continuity, and set theory
Authors: Beeson M. , Ščedrov A.
Published: May 2006

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

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

In this paper we investigate the first order metatheory of the classical propositional logic. In the first section we prove that the first order metatheory of the classical propositional logic is undecidable. Thus as a mathematical object even the simplest of logics is, from a logical standpoint, quite complex. In fact it is of the same complexity as true first order number theory.

This result answers negatively a question of J. F. A. K. van Benthem (see [van Benthem and Doets 1983]) as to whether the interpolation theorem in some sense completes the metatheory of the calculus. Let us begin by motivating the question that we answer. In [van Benthem and Doets 1983] it is claimed that a folklore prejudice has it that interpolation was the final elementary property of first order logic to be discovered. Even though other properties of the propositional calculus have been discovered since Craig's orginal paper [Craig 1957] (see for example [Reznikoff 1965]) there is a lot of evidence for the fundamental nature of the property. In abstract model theory for example one finds that very few logics have the interpolation property. There are two well-known open problems in this area. These are

1. Is there a logic satisfying the full compactness theorem as well as the interpolation theorem that is not equivalent to first order logic even for finite models?

2. Is there a logic stronger than L(Q), the logic with the quantifierthere exist uncountably many, that is countably compact and has the interpolation property?
On the logic of theory change: Partial meet contraction and revision functions
Authors: Alchourrón Carlos E. , Gärdenfors Peter , Makinson David
Published: May 2006

This paper extends earlier work by its authors on formal aspects of the processes of contracting a theory to eliminate a proposition and revising a theory to introduce a proposition. In the course of the earlier work, Gärdenfors developed general postulates of a more or less equational nature for such processes, whilst Alchourrón and Makinson studied the particular case of contraction functions that are maximal, in the sense of yielding a maximal subset of the theory (or alternatively, of one of its axiomatic bases), that fails to imply the proposition being eliminated.

In the present paper, the authors study a broader class, including contraction functions that may be less than maximal. Specifically, they investigate “partial meet contraction functions”, which are defined to yield the intersection of some nonempty family of maximal subsets of the theory that fail to imply the proposition being eliminated. Basic properties of these functions are established: it is shown in particular that they satisfy the Gärdenfors postulates, and moreover that they are sufficiently general to provide a representation theorem for those postulates. Some special classes of partial meet contraction functions, notably those that are “relational” and “transitively relational”, are studied in detail, and their connections with certain “supplementary postulates” of Gàrdenfors investigated, with a further representation theorem established.
The undecidability of entailment and relevant implication
Authors: Urquhart Alasdair
Published: May 2006

In this paper we show that the propositional logics E of entailment, R of relevant implication and T of ticket entailment are undecidable. The decision problem is also shown to be unsolvable in an extensive class of related logics. The main tool used in establishing these results is an adaptation of the von Neumann coordinatization theorem for modular lattices.

Interest in the decision problem for these systems dates from the late 1950s. The earliest result was obtained by Anderson and Belnap who proved that the first degree fragment of all these logics is decidable. Kripke [11] proved that the pure implicational fragments R→ and E→ of R and E are decidable. His methods were extended by Belnap and Wallace to the implication-negation fragments of these systems [3]; Kripke's methods also extend easily to include the implication-conjunction fragments of R and E. Meyer in his thesis [14] extended the result for R to include a primitive necessity operator. He also proved decidable the system R-mingle, an extension of R, and ortho-R (OR), the logic obtained from R by omitting the distribution axiom. Various weak relevant logics are also known to be decidable by model-theoretic proofs of the finite model property (see Fine [5]). Finally, S. Giambrone [7] has solved the decision problem for various logics obtained by the omission of the contraction axiom (A → ⦁ A → B) → ⦁ A → B, including R+ − W (R+ minus contraction). It is worth noting that even where positive results were obtained, the decision methods were usually of a complexity considerably greater than in the case of other nonclassical logics such as intuitionistic logic or modal logic, a fact which already indicates the difficulty of the decision problem.
Forcing the failure of CH by adding a real
Authors: Shelah Saharon , Woodin Hugh
Published: May 2006

We prove several independence results relevant to an old question in the folklore of set theory. These results complement those in [Sh, Chapter XIII, §4]. The question is the following. Suppose V ⊨ “ZFC + CH” and r is a real not in V. Must V[r] ⊨ CH? To avoid trivialities assume = .

We answer this question negatively. Specifically we find pairs of models (W, V) such that W ⊨ ZFC + CH, V = W[r], r a real, = and V ⊨ ¬CH. Actually we find a spectrum of such pairs using ZFC up to “ZFC + there exist measurable cardinals”. Basically the nicer the pair is as a solution, the more we need to assume in order to construct it.

The relevant results in [Sh, Chapter XIII] state that if a pair (of inner models) (W, V) satisfies (1) and (2) then there is an inaccessible cardinal in L; if in addition V ⊨ 2ℵ0 > ℵ2 then 0# exists; and finally if (W, V) satisfies (1), (2) and (3) with V ⊨ 2ℵ0 > ℵω, then there is an inner model with a measurable cardinal.

Definition 1. For a pair (W, V) we shall consider the following conditions:

(1) V = W[r], r a real, = , W ⊨ ZFC + CH but CH fails in V.

(2) W ⊨ GCH.

(3) W and V have the same cardinals.
The consistency strength of the free-subset property for ωω
Authors: Koepke Peter
Published: May 2006

A subset X of a structure S is called free in S if ∀x ∈ Xx ∉ S[X − {x}]; here, S[Y] is the substructure of S generated from Y by the functions of S. For κ, λ, μ cardinals, let Frμ(κ, λ) be the assertion:

for every structure S with κ ⊂ S which has at most μ functions and relations there is a subset X ⊂ κ free in S of cardinality ≥ λ.

We show that Frω(ωω, ω), the free-subset property for ωω, is equiconsistent with the existence of a measurable cardinal (2.2,4.4). This answers a question of Devlin [De].

In the first section of this paper we prove some combinatorial facts about Frμ(κ, λ); in particular the first cardinal κ such that Frω(κ, ω) is weakly inaccessible or of cofinality ω (1.2). The second section shows that, under Frω(ωω, ω), ωω is measurable in an inner model. For the convenience of readers not acquainted with the core model κ, we first deduce the existence of 0# (2.1) using the inner model L. Then we adapt the proof to the core model and obtain that ωω is measurable in an inner model. For the reverse direction, we essentially apply a construction of Shelah [Sh] who forced Frω(ωω, ω) over a ground model which contains an ω-sequence of measurable cardinals. We show in §4 that indeed a coherent sequence of Ramsey cardinals suffices. In §3 we obtain such a sequence as an endsegment of a Prikry sequence.
The unsolvability of the Gödel class with identity
Authors: Goldfarb Warren D.
Published: May 2006

The Gödel class with identity (GCI) is the class of closed, prenex quantificational formulas whose prefixes have the form ∀∀∃ … ∃ and whose matrices contain arbitrary predicate letters and the identity sign “ = ”, but do not contain function signs or individual constants. The ∀∀∃ … ∃ class without identity was shown solvable over fifty years ago ([4], [12], [17]); slightly later, that class was shown to possess the stronger property of finite controllability ([5], [18]). (A class of formulas is solvable iff it is decidable for satisfiability; it is finitely controllable iff every satisfiable formula in it has a finite model.) At the end of [5], Gödel claims that the finite controllability of the GCI can be shown “by the same method” as he employed to show this for the class without identity. This claim has been questioned for nearly twenty years; in §1 below we give a brief history of investigations into it. The major result of this paper shows Gödel to have been mistaken: the GCI is unsolvable. §2 contains the basic construction, which yields a satisfiable formula in the GCI that lacks finite models. This formula may easily be exploited to encode undecidable problems into the GCI.
A natural extension of natural deduction
Authors: Schroeder-Heister Peter
Published: May 2006

One of the main ideas of calculi of natural deduction, as introduced by Jaśkowski and Gentzen, is that assumptions may be discharged in the course of a derivation. As regards sentential logic, this conception will be extended in so far as not only formulas but also rules may serve as assumptions which can be discharged. The resulting calculi and derivations with rules of any finite level are informally introduced in §1, while §§2 and 3 state formal definitions of the concepts involved and basic lemmata. Within this framework, a standard form for introduction and elimination rules for arbitrary n-ary sentential operators is motivated in §4, understood as a contribution to the theory of meaning for logical signs. §5 proves that the set {&, ∨, ⊃, ⋏} of standard intuitionistic connectives is complete, i.e. &, ∨, ⊃, and ⋏ suffice to express each n-ary sentential operator having rules of the standard form given in §4. §6 makes some remarks on related approaches. For an extension of the conception presented here to quantifier logic, see [11].
A preservation theorem for ec-structures with applications
Authors: Albert Michael H.
Published: May 2006

We characterize the model companions of universal Horn classes generated by a two-element algebra (or ordered two-element algebra). We begin by proving that given two mutually model consistent classes M and N of (respectively ) structures, with , , provided that an -definability condition for the function and relation symbols of holds. We use this, together with Post's characterization of ISP(A), where A is a two-element algebra, to show that the model companions of these classes essentially lie in the classes of posets and semilattices, or characteristic two groups and relatively complemented distributive lattices.
A note on elementary equivalence of C(K) spaces
Authors: Heinrich S. , Henson C. Ward , Moore L. C.
Published: May 2006

In this paper we give a closer analysis of the elementary properties of the Banach spaces C(K), where K is a totally disconnected, compact Hausdorff space, in terms of the Boolean algebra B(K) of clopen subsets of K. In particular we sharpen a result in [4] by showing that if B(K1) and B(K2) satisfy the same sentences with ≤ n alternations of quantifiers, then the same is true of C(K1) and C(K2). As a consequence we show that for each n there exist C(K) spaces which are elementarily equivalent for sentences with ≤ n quantifier alternations, but which are not elementary equivalent in the full sense. Thus the elementary properties of Banach spaces cannot be determined by looking at sentences with a bounded number of quantifier alternations.

The notion of elementary equivalence for Banach spaces which is studied here was introduced by the second author [4] and is expressed using the language of positive bounded formulas in a first-order language for Banach spaces. As was shown in [4], two Banach spaces are elementarily equivalent in this sense if and only if they have isometrically isomorphic Banach space ultrapowers (or, equivalently, isometrically isomorphic nonstandard hulls.)

We consider Banach spaces over the field of real numbers. If X is such a space, Bx will denote the closed unit ball of X, Bx = {x ϵ X∣ ∣∣x∣∣ ≤ 1}. Given a compact Hausdorff space K, we let C(K) denote the Banach space of all continuous real-valued functions on K, under the supremum norm. We will especially be concerned with such spaces when K is a totally disconnected compact Hausdorff space. In that case B(K) will denote the Boolean algebra of all clopen subsets of K. We adopt the standard notation from model theory and Banach space theory.
Martin's axiom and a regular topological space with uncountable net weight whose countable product is hereditarily separable and hereditarily Lindelöf
Authors: Ciesielski Krzysztof
Published: May 2006

In [1, p. 51] A. V. Arhangel'skiĭ, in connection with the problems of L-spaces and S-spaces, examined further the notions of hereditary separability and hereditary Lindelöfness. In particular he considered the following property P: “Every regular topological space has a countable net weight provided its countable product is hereditarily Lindelöf and hereditarily separable.” He noticed that the continuum hypothesis implies negation of the property P and posed a question: “Do Martin's Axiom and the negation of the continuum hypothesis imply P?” The purpose of this paper is to give a negative answer to this question.

The set-theoretical and topological notation that we use is standard and can be found in [6] and [5] respectively.

Throughout the paper we will use the notation H(X, Y) to denote the set of all finite functions from a set X to Y.

Theorem. Con(ZFC) → Con(ZFC + MA + ¬CH + there exists a 0-dimensional Hausdorff space X such that nw(X) = с and nw(Y) = ω for any Y ϵ [X]<с).

Proof. Let M be a model of ZFC satisfying CH and let F be an M-generic filter over the Cohen forcing {H(ω2 × ω2, 2), ⊃). Then f = ⋃F is a function and f: ω2 × ω2 → 2.
Isolated types in a weakly minimal set
Authors: Buechler Steven
Published: May 2006

Theorem A. Let T be a small superstable theory, A a finite set, and ψ a weakly minimal formula over A which is contained in some nontrivial type which does not have Morley rank. Then ψ is contained in some nonalqebraic isolated type over A.

As an application we prove

Theorem B. Suppose that T is small and superstable, A is finite, and there is a nontrivial weakly minimal type p ∈ S(A) which does not have Morley rank. Then the prime model over A is not minimal over A.
MM. Borel, Tits, Zil′ber et le Général Nonsense
Authors: Poizat Bruno
Published: May 2006

Le rêve secret de tout logicien, c’est de prouver un résultat mathématique significatif avec des moyens de fortune; ce rêve se réalise parfois de manière quelque peu biaisée, le théorème obtenu n’étant qu’une version trop simplifiée, ou bien trop adaptée aux besoins de la logique, pour convaincre un mathématicien normal. C’est pour cela que j’annonce d’emblée la couleur, et que je précise les règles du jeu: la version du théorème de Borel-Tits que je vais montrer, concernant les groupes algébriques simples sur un corps de base algébriquement clos, sera considérée comme pratiquement évidente par un géomètre; mais c’est, à mon avis, la seule qui ait un intérêt pour un théoricien des modèles.

Quand on entreprend ainsi de redémontrer une version simple d’un résultat par ailleurs bien connu, le seul intérêt est dans la méthode: ce que je veux, ici, c’est présenter une preuve qui n’utilise aucune information, ou presque, sur la structure algébrique de ces groupes; il est même souhaitable d’oublier qu’il s’agit de groupes linéaires! Elle repose sur des résultats généraux concernant les groupes de rang de Morley fini, dus à divers auteurs, dont le principal, Boris Iosifovič Zil′ber, a déjà fait une tentative similaire [Zil′ber 1984]; je poursuis ici cette tentative, mais en me limitant à des arguments encore moins spécifiques au contexte de la géométrie.

Si je fais ainsi, ce n’est pas pour donner l’impression que l’unique ambition de la théorie des modèles est de montrer des résultats triviaux par des méthodes triviales.
Boolean simple groups and boolean simple rings
Authors: Takeuti Gaisi
Published: May 2006

Let be a complete Boolean algebra and G a finite simple group in the Scott-Solovay -valued model V() of set theory. If we observe G outside V(), then we get a new group which is denoted by Ĝ. In general, Ĝ is not finite nor simple. Nevertheless Ĝ satisfies every property satisfied by a finite simple group with some translation. In this way, we can get a class of groups for which we can use a well-developed theory of the finite simple groups. We call Ĝ Boolean simple if G is simple in some V(). In the same way we define Boolean simple rings. The main purpose of this paper is a study of structures of Boolean simple groups and Boolean simple rings. As for Boolean simple rings, K. Eda previously constructed Boolean completion of rings with a certain condition. His construction is useful for our purpose.

The present work is a part of a series of systematic applications of Boolean valued method. The reader who is interested in this subject should consult with papers by Eda, Nishimura, Ozawa, and the author in the list of references.
Σ2-collection and the infinite injury priority method
Authors: Mytilinaios Michael E. , Slaman Theodore A.
Published: May 2006

We show that the existence of a recursively enumerable set whose Turing degree is neither low nor complete cannot be proven from the basic axioms of first order arithmetic (P−) together with Σ2-collection (BΣ2). In contrast, a high (hence, not low) incomplete recursively enumerable set can be assembled by a standard application of the infinite injury priority method. Similarly, for each n, the existence of an incomplete recursively enumerable set that is neither lown nor highn-1, while true, cannot be established in P− + BΣn+1. Consequently, no bounded fragment of first order arithmetic establishes the facts that the highn and lown jump hierarchies are proper on the recursively enumerable degrees.
Relational structures determined by their finite induced substructures
Authors: Hodkinson I. M. , Macpherson H. D.
Published: May 2006

A countably infinite relational structure M is called absolutely ubiquitous if the following holds: whenever N is a countably infinite structure, and M and N have the same isomorphism types of finite induced substructures, there is an isomorphism from M to N. Here a characterisation is given of absolutely ubiquitous structures over languages with finitely many relation symbols. A corresponding result is proved for uncountable structures.
Partition properties and Prikry forcing on simple spaces
Authors: Henle J. M.
Published: May 2006

One of the simplest and yet most fruitful ideas in forcing was the notion of Karel Prikry in which he used a measure on a cardinal κ to change the cofinality of κ to ω without collapsing it. The idea has found connections to almost every branch of modern set theory, from large cardinals to small, from combinatorics to models, from Choice to Determinacy, and from consistency to inconsistency. The long list of generalizers and modifiers includes Apter, Gitik, Henle, Spector, Shelah, Mathias, Magidor, Radin, Blass and Kimchi.

This paper is about generalizing Prikry forcing and partition properties to “simple spaces”. The concept of a simple space is itself the generalization of those combinatorial objects upon which the notions of “measurable”, “compact”, “supercompact”, “huge”, etc. are based. Simple spaces were introduced in [ADHZ1] and [ADHZ2] together with a broader generalization, “filter spaces”. The definition provided here is a small simplification of earlier versions. The author is indebted to Mitchell Spector, whose careful reading turned up numerous errors, some subtle, some flagrant.

In this first section, we review simple spaces briefly, including a short introduction to the space Qκλ. In §2, we describe our generalizations of partition property and Prikry forcing, and discuss the relationship between them. In §3, we find a partition property for the huge space [λ]κ, but show that Prikry forcing here is impossible. We find partition properties for Qκλ and show that Prikry forcing can be done here.
Undecidability and initial segments of the (r.e.) tt-degrees
Authors: Haught Christine Ann , Shore Richard A.
Published: May 2006

A notion of reducibility ≤r between sets is specified by giving a set of procedures for computing one set from another. We say that a set A is r-reducible to a set B, A ≤rB, if one of the procedures applied to B gives A. Associated with any such reducibility notion is the structure of r-degrees, the equivalence classes of sets with respect to this reducibility, with the induced ordering. The most general notion of a computable reducibility is that of Turing, ≤T. Here we say that A ≤TB if there is a Turing machine φe which, when equipped with an oracle for B, computes A: φeB = A. Such Turing degree computations are characterized by the phenomenon that only during the computation itself do we discover which questions about B need to be answered to compute A(x). In contrast, for nearly all other computable reducibilities the set of questions needed is given in advance by a recursive procedure. Perhaps the most common example of such a procedure is many-one reducibility, ≤m: A ≤mB if there is a recursive function f such that x ∈ A ⇔ f(x) ∈ B.

Reducibilities with the property that the output, A(x), is determined by the answers that B gives to a set of questions calculated recursively from x are said to be of tabular type. The most general tabular reducibility is called truth-table reducibility, ≤tt. The procedures [e] associated with this reducibility are specified by a recursive function f (= {e}) which, for each x, gives a set of n questions about the oracle and, for each of the possible 2n sets of answers, gives the corresponding output. As usual this defines A ≤ttB as “there is an e such that [e]B = A”. It is with this notion of reducibility and the associated tt-degrees that we shall be concerned in this paper. Basic information on several such strong reducibilities can be found in Rogers [28]. For more information we recommend the survey articles by Odifreddi [25] and Degtev [2] as well as Odifreddi's book [26].
Effective model theory vs. recursive model theory
Authors: Chisholm John
Published: May 2006

Recursive model theory is supposed to be the study of the effectiveness of constructions and theorems in model theory. This often involves getting “effective” versions of various classical model-theoretic notions. The traditional way of doing this is to restrict attention to recursive models, and recursive isomorphisms between them, etc. Thus for example the following definition appears in the literature (in [3] and [1]).

Definition. Given a recursive model A and an n Є ω, a subset R ⊆ An is called intrinsically r.e. provided that for every recursive model B ≈ A, the isomorphic image in B of R is an r.e. subset of Bn.

It is clear that if R is definable by a (recursive, infinitary) Σ10 formula (with finitely many parameters from A), then R is intrinsically r.e. It seems natural for the converse to be true. Indeed, provided that (A, R) is sufficiently “regular” in a sense made precise in a theorem of Ash and Nerode (see [3]), the converse is true. However, if we drop the (rather strong) regularity conditions, there exist “pathological” examples of intrinsically r.e. relations which are not definable by a Σ10 formula (see [7]).

In this paper, we suggest a rather different approach to studying the effectiveness of model theory, an approach we have dubbed “effective model theory”. The basic idea is to allow arbitrary nonrecursive models, but to require all notions to be relativized to the complexity of the models involved. (Much the same notion has been used in [2] under the name “relatively recursive model theory”.) Thus for example we have the following effective model theory version of the property of being intrinsically r.e.
Partial realizations of Hilbert's program
Authors: Simpson Stephen G.
Published: May 2006

§0. Introduction. What follows is a write-up of my contribution to the symposium “Hilbert's Program Sixty Years Later” which was sponsored jointly by the American Philosophical Association and the Association for Symbolic Logic. The symposium was held on December 29,1985 in Washington, D. C. The panelists were Solomon Feferman, Dag Prawitz and myself. The moderator was Wilfried Sieg. The research which I discuss here was partially supported by NSF Grant DMS-8317874.

I am grateful to the organizers of this timely symposium on an important topic. As a mathematician I particularly value the opportunity to address an audience consisting largely of philosophers. It is true that I was asked to concentrate on the mathematical aspects of Hilbert's program. But since Hilbert's program is concerned solely with the foundations of mathematics, the restriction to mathematical aspects is really no restriction at all.

Hilbert assigned a special role to a certain restricted kind of mathematical reasoning known as finitistic. The essence of Hilbert's program was to justify all of set-theoretical mathematics by means of a reduction to finitism. It is now well known that this task cannot be carried out. Any such possibility is refuted by Gödel's theorem. Nevertheless, recent research has revealed the feasibility of a significant partial realization of Hilbert's program. Despite Gödel's theorem, one can give a finitistic reduction for a substantial portion of infinitistic mathematics including many of the best-known nonconstructive theorems. My purpose here is to call attention to these modern developments.