bluuebunny/crossref_metadata_2025 huggingface dataset:
The Kunen-Miller chart (Lebesgue measure, the Baire property, Laver reals and preservation theorems for forcing)
Authors: Judah Haim , Shelah Saharon
Published: May 2006

In this work we give a complete answer as to the possible implications between some natural properties of Lebesgue measure and the Baire property. For this we prove general preservation theorems for forcing notions. Thus we answer a decade-old problem of J. Baumgartner and answer the last three open questions of the Kunen-Miller chart about measure and category. Explicitly, in §1: (i) We prove that if we add a Laver real, then the old reals have outer measure one. (ii) We prove a preservation theorem for countable-support forcing notions, and using this theorem we prove (iii) If we add ω2 Laver reals, then the old reals have outer measure one. From this we obtain (iv) Cons(ZF) ⇒ Cons(ZFC + ¬ B(m) + ¬ U(m) + U(c)). In §2: (i) We prove a preservation theorem, for the finite support forcing notion, of the property “F ⊆ ωω is an unbounded family.” (ii) We introduce a new forcing notion making the old reals a meager set but the old members of ωω remain an unbounded family. Using this we prove (iii) Cons(ZF) ⇒ Cons(ZFC + U(m) + ¬ B(c) + ¬ U(c) + C(c)). In §3: (i) We prove a preservation theorem, for the finite support forcing notion, of a property which implies “the union of the old measure zero sets is not a measure zero set,” and using this theorem we prove (ii) Cons(ZF) ⇒ Cons(ZFC + ¬U(m) + C(m) + ¬ C(c)).
Finite Kripke models and predicate logics of provability
Authors: Artemov Sergei , Dzhaparidze Giorgie
Published: May 2006

The paper proves a predicate version of Solovay's well-known theorem on provability interpretations of modal logic:

If a closed modal predicate-logical formula R is not valid in some finite Kripke model, then there exists an arithmetical interpretation f such that PA ⊬ fR.

This result implies the arithmetical completeness of arithmetically correct modal predicate logics with the finite model property (including the one-variable fragments of QGL and QS). The proof was obtained by adding “the predicate part” as a specific addition to the standard Solovay construction.
Upward directedness of the Rudin-Keisler ordering of p-points
Authors: Laflamme Claude
Published: May 2006

It has been proven by Blass [1973] that any two P-points which have a P-point as a common upper bound in the Rudin-Keisler (RK) ordering necessarily have a common lower bound (necessarily a P-point). Hence two nonisomorphic Ramsey ultrafilters have neither a common lower nor a common upper bound which is a P-point. So in a model of CH for example (or MA, P(c),…), the RK ordering restricted to P-points is neither upward nor downward directed, since it is well known that nonisomorphic Ramsey ultrafilters exist in such models. On the other hand, we will see that in the model for “near coherence of filters” (NCF) produced by Blass and Shelah [1985], the RK ordering of P-points is upward, hence downward directed. This shows that the question of directedness of the RK ordering of P-points, upward or downward, cannot be decided in ZFC.

There is a related question, asked by Blass in [1973], whether two P-points which have a common lower bound necessarily have a common upper bound which is a P-point. Our main result establishes the independence of this statement relative to ZFC. Its consistency will follow as soon as we show that the RK ordering of P-points is upward directed in the NCF model mentioned above, which we do in §2. But its independence will require a new construction, and will be given in §3.
The ordertype of β-R.E. sets
Authors: Sutner Klaus
Published: May 2006

Let β be an arbitrary limit ordinal. A β-r.e. set is l-finite iff all its β-r.e. subsets are β-recursive. The l-finite sets correspond to the ideal of finite sets in the lattice of r.e. sets. We give a characterization of l-finite sets in terms of their ordertype: a β-r.e. set is l-finite iff it has ordertype less than β*, the Σ1, projectum of β).
An axiomatization of the logic with the rough quantifier
Authors: Krynicki Michał , Tuschik Hans-Peter
Published: May 2006

We consider the language L(Q), where L is a countable first-order language and Q is an additional generalized quantifier. A weak model for L(Q) is a pair 〈, q〉 where is a first-order structure for L and q is a family of subsets of its universe. In case that q is the set of classes of some equivalence relation the weak model 〈, q〉 is called a partition model. The interpretation of Q in partition models was studied by Szczerba [3], who was inspired by Pawlak's paper [2]. The corresponding set of tautologies in L(Q) is called rough logic. In the following we will give a set of axioms of rough logic and prove its completeness. Rough logic is designed for creating partition models.

The partition models are the weak models arising from equivalence relations. For the basic properties of the logic of weak models the reader is referred to Keisler's paper [1]. In a weak model 〈, q〉 the formulas of L(Q) are interpreted as usual with the additional clause for the quantifier Q: 〈, q〉 ⊨ Qx φ(x) iff there is some X ∊ q such that 〈, q〉 ⊨ φ(a) for all a ∊ X.

In case X satisfies the right side of the above equivalence we say that X is contained in φ(x) or, equivalently, φ(x) contains X.
Natural 3-valued logics—characterization and proof theory
Authors: Avron Arnon
Published: May 2006

Many-valued logics in general and 3-valued logic in particular is an old subject which had its beginning in the work of Łukasiewicz [Łuk]. Recently there is a revived interest in this topic, both for its own sake (see, for example, [Ho]), and also because of its potential applications in several areas of computer science, such as proving correctness of programs [Jo], knowledge bases [CP] and artificial intelligence [Tu]. There are, however, a huge number of 3-valued systems which logicians have studied throughout the years. The motivation behind them and their properties are not always clear, and their proof theory is frequently not well developed. This state of affairs makes both the use of 3-valued logics and doing fruitful research on them rather difficult.

Our first goal in this work is, accordingly, to identify and characterize a class of 3-valued logics which might be called natural. For this we use the general framework for characterizing and investigating logics which we have developed in [Av1]. Not many 3-valued logics appear as natural within this framework, but it turns out that those that do include some of the best known ones. These include the 3-valued logics of Łukasiewicz, Kleene and Sobociński, the logic LPF used in the VDM project, the logic RM3 from the relevance family and the paraconsistent 3-valued logic of [dCA]. Our presentation provides justifications for the introduction of certain connectives in these logics which are often regarded as ad hoc. It also shows that they are all closely related to each other. It is shown, for example, that Łukasiewicz 3-valued logic and RM3 (the strongest logic in the family of relevance logics) are in a strong sense dual to each other, and that both are derivable by the same general construction from, respectively, Kleene 3-valued logic and the 3-valued paraconsistent logic.
A remark on locally pure measures
Authors: Ng Siu-ah
Published: May 2006

In this note, we consider Keisler's stability theory and prove that every measure over a small submodel has a locally pure extension.
A relativization mechanism in recursion categories
Authors: Stefani Stefano
Published: May 2006

The study of recursion categories was introduced in [DH] to carry out an algebraic and intrinsic investigation of structures and phenomena which arise in the classical recursion theory. In this paper a recursion categorical arrangement is proposed for some of the concepts of reduction and relativization which are commonplace in studying classical recursive functions and operators. Indeed, this introduction can be done in a natural way, using categorical concepts already defined, without resorting to special structures. In developing the subject outlined one also has the opportunity of discussing the concept of uniform proof in the context of the recursion categories.
A proof of Beigel's cardinality conjecture
Authors: Kummer Martin
Published: May 2006

In 1986, Beigel [Be87] (see also [Od89, III.5.9]) proved the nonspeedup theorem: if A, B ⊆ ω, and as a function of 2n variables can be computed by an algorithm which makes at most n queries to B, then A is recursive (informally, 2n parallel queries to a nonrecursive oracle A cannot be answered by making n sequential (or “adaptive”) queries to an arbitrary oracle B). Here, 2n cannot be replaced by 2n − 1. In subsequent papers of Beigel, Gasarch, Gill, Hay, and Owings the theory of “bounded query classes” has been further developed (see, for example, [BGGOta], [BGH89], and [Ow89]). The topic has also been studied in the context of structural complexity theory (see, for example, [AG88], [Be90], and [JY90]).

If A ⊆ ω and n ≥ 1, let . Beigel [Be87] stated the powerful “cardinality conjecture” (CC): if A, B ⊆ ω, and can be computed by an algorithm which makes at most n queries to B, then A is recursive. Owings [Ow89] verified CC for n = 1, and, for n 1, he proved that A is recursive in the halting problem. We prove that CC is true for all n.
On sets ∀-definable from Pfaffian functions
Authors: Bianconi Ricardo
Published: May 2006

We prove the existence of a bound to the number of components of an ∀-definable set in the reals, using Pfaffian functions, and give some applications.
A note on exponentiation
Authors: Cornaros Ch. , Dimitracopoulos C.
Published: May 2006

We study the strength (over bounded induction) of axioms expressing particular cases of the Chinese Remainder Theorem with respect to the axiom ∀x, y∃z (z = xy).
Ramsey sets, the Ramsey ideal, and other classes overR
Authors: Corazza Paul
Published: May 2006

We improve results of Marczewski, Frankiewicz, Brown, and others comparing theω-ideals of measure zero, meager, Marczewski measure zero, and completely Ramsey null sets; in particular, we remove CH from the hypothesis of many of Brown's constructions of sets lying in some of these ideals but not in others. We improve upon work of Marczewski by constructing, without CH, a nonmeasurable Marczewski measure zero set lacking the property of Baire. We extend our analysis ofω-ideals to include the completely Ramsey null sets relative to a Ramsey ultrafilter and obtain all 32 possible examples of sets in some ideals and not others, some under the assumption of MA, but most in ZFC alone. We also improve upon the known constructions of a Marczewski measure zero set which is not Ramsey by using a set theoretic hypothesis which is weaker than those used by other authors. We give several consistency proofs: one concerning the relative sizes of the covering numbers for the meager sets and the completely Ramsey null sets; another concerning the size of non; and a third concerning the size of add. We also study those classes of perfect sets which are bases for the class of always first category sets.
The lattice of varieties of representable relation algebras
Authors: Andréka Hajnal , Givant Steven , Németi István
Published: May 2006

We shall show that certain natural and interesting intervals in the lattice of varieties of representable relation algebras embed the lattice of all subsets of the natural numbers, and therefore must have a very complicated lattice-theoretic structure.
Dual easy uniformization and model-theoretic descriptive set theory
Authors: Lavine Shaughan
Published: May 2006

It is well known that, in the terminology of Moschovakis, Descriptive set theory (1980), every adequate normed pointclass closed under ∀ω has an effective version of the generalized reduction property (GRP) called the easy uniformization property (EUP). We prove a dual result: every adequate normed pointclass closed under ∃ω has the EUP. Moschovakis was concerned with the descriptive set theory of subsets of Polish topological spaces. We set up a general framework for parts of descriptive set theory and prove results that have as special cases not only the just-mentioned topological results, but also corresponding results concerning the descriptive set theory of classes of classes of structures.

Vaught (1973) asked whether the class of cPCδ classes of countable structures has the GRP. It does. A cPC(A) class is the class of all models of a sentence of the form , where ϕ is a sentence of ℒ∞ω that is in A and is a set of relation symbols that is in A. Vaught also asked whether there is any primitive recursively closed set A such that some effective version of the GRP holds for the class of cPC(A) classes of countable structures. There is: The class of cPC(A) classes of countable structures has the EUP if ω ∈ A and A is countable and primitive recursively closed. Those results and some extensions are obtained by first showing that the relevant classes of classes of structures, which Vaught showed normed, are in a suitable sense adequate and closed under ∃ω, and then applying the dual easy uniformization theorem.
The bounded proper forcing axiom
Authors: Goldstern Martin , Shelah Saharon
Published: May 2006

The bounded proper forcing axiom BPFA is the statement that for any family of ℵ1 many maximal antichains of a proper forcing notion, each of size ℵ1, there is a directed set meeting all these antichains.

A regular cardinal κ is called ∑1-reflecting, if for any regular cardinal χ, for all formulas φ, “H(χ) ⊨ ‘φ’” implies “∃δ < κ, H(δ) ⊨ ‘φ’”.

We investigate several algebraic consequences of BPFA, and we show that the consistency strength of the bounded proper forcing axiom is exactly the existence of a ∑1-reflecting cardinal (which is less than the existence of a Mahlo cardinal).

We also show that the question of the existence of isomorphisms between two structures can be reduced to the question of rigidity of a structure.
T-convexity and tame extensions
Authors: van den Dries Lou , Lewenberg Adam H.
Published: May 2006

Let T be a complete o-minimal extension of the theory of real closed fields. We characterize the convex hulls of elementary substructures of models of T and show that the residue field of such a convex hull has a natural expansion to a model of T. We give a quantifier elimination relative to T for the theory of pairs (ℛ, V) where ℛ ⊨ T and V ≠ ℛ is the convex hull of an elementary substructure of ℛ. We deduce that the theory of such pairs is complete and weakly o-minimal. We also give a quantifier elimination relative to T for the theory of pairs with ℛ a model of T and a proper elementary substructure that is Dedekind complete in ℛ. We deduce that the theory of such “tame” pairs is complete.
Hereditarily structurally complete modal logics
Authors: Rybakov V. V.
Published: May 2006

We consider structural completeness in modal logics. The main result is the necessary and sufficient condition for modal logics over K4 to be hereditarily structurally complete: a modal logic λ is hereditarily structurally complete iff λ is not included in any logic from the list of twenty special tabular logics. Hence there are exactly twenty maximal structurally incomplete modal logics above K4 and they are all tabular.
Generalized nonsplitting in the recursively enumerable degrees
Authors: Leonhardi Steven D.
Published: May 2006

We investigate the algebraic structure of the upper semi-lattice formed by the recursively enumerable Turing degrees. The following strong generalization of Lachlan's Nonsplitting Theorem is proved: Given n ≥ 1, there exists an r.e. degree d such that the interval [d, 0′] ⊂ R admits an embedding of the n-atom Boolean algebra preserving (least and) greatest element, but also such that there is no (n + 1 )-tuple of pairwise incomparable r.e. degrees above d which pairwise join to 0′ (and hence, the interval [d, 0′] ⊂ R does not admit a greatest-element-preserving embedding of any lattice which has n + 1 co-atoms, including ). This theorem is the dual of a theorem of Ambos-Spies and Soare, and yields an alternative proof of their result that the theory of R has infinitely many one-types.
Reflecting in epistemic arithmetic
Authors: Horsten Leon
Published: May 2006

An epistemic formalization of arithmetic is constructed in which certain non-trivial metatheoretical inferences about the system itself can be made. These inferences involve the notion of provability in principle, and cannot be made in any consistent extensions of Stewart Shapiro's system of epistemic arithmetic. The system constructed in the paper can be given a modal-structural interpretation
Countable models of trivial theories which admit finite coding
Authors: Loveys James , Tanović Predrag
Published: May 2006

We prove:

Theorem. A complete first order theory in a countable language which is strictly stable, trivial and which admits finite coding hasnonisomorphic countable models.

Combined with the corresponding result or superstable theories from [4] our result confirms the Vaught conjecture for trivial theories which admit finite coding.
Covering analytic sets by families of closed set
Authors: Solecki Sławomir
Published: May 2006

We prove that for every familyIof closed subsets of a Polish space eachset can be covered by countably many members ofIor else contains a nonemptyset which cannot be covered by countably many members ofI. We prove an analogous result forκ-Souslin sets and show that ifA#exists for anyA⊂ωω, then the above result is true forsets. A theorem of Martin is included stating that this result is also true for weakly homogeneously Souslin sets. As an application of our results we derive from them a general form of Hurewicz's theorem due to Kechris. Louveau, and Woodin and a theorem of Feng on the open covering axiom. Also some well-known theorems on finding “big” closed sets insideof“big”andare consequences of our results.
Anti-admissible sets
Authors: Lurie Jacob
Published: May 2006

Aczel's theory of hypersets provides an interesting alternative to the standard view of sets as inductively constructed, well-founded objects, thus providing a convienent formalism in which to consider non-well-founded versions of classically well-founded constructions, such as the “circular logic” of [3], This theory and ZFC are mutually interpretable; in particular, any model of ZFC has a canonical “extension” to a non-well-founded universe. The construction of this model does not immediately generalize to weaker set theories such as the theory of admissible sets. In this paper, we formulate a version of Aczel's antifoundation axiom suitable for the theory of admissible sets. We investigate the properties of models of the axiom system KPU−, that is, KPU with foundation replaced by an appropriate strengthening of the extensionality axiom. Finally, we forge connections between “non-wellfounded sets over the admissible set A” and the fragment LA of the modal language L∞.
Explicit mathematics with the monotone fixed point principle. II: Models
Authors: Rathjen Michael
Published: May 2006

This paper continues investigations of the monotone fixed point principle in the context of Feferman's explicit mathematics begun in [14]. Explicit mathematics is a versatile formal framework for representing Bishop-style constructive mathematics and generalized recursion theory. The object of investigation here is the theory of explicit mathematics augmented by the monotone fixed point principle, which asserts that any monotone operation on classifications (Feferman's notion of set) possesses a least fixed point. To be more precise, the new axiom not merely postulates the existence of a least solution, but, by adjoining a new constant to the language, it is ensured that a fixed point is uniformly presentable as a function of the monotone operation. Let T0 + UMID denote this extension of explicit mathematics. [14] gave lower bounds for the strength of two subtheories of To + UMID in relating them to fragments of second order arithmetic based on comprehension. [14] showed that To ↾ + UMID and To ↾ + INDk + UMID have at least the strength of ( – CA), and ↾ and – CA), respectively.

Here we are concerned with the exact reversals. Let UMIDN be the monotone fixed-point principle for subclassifications of the natural numbers. Among other results, it is shown that To ↾ + UMIDN and To ↾ + INDN + UMIDN have the same strength as ( – CA) ↾ and ( – CA), respectively.

The results are achieved by constructing set-theoretic models for the aforementioned systems of explicit mathematics in certain extensions of Kripke-Platek set theory and subsequently relating these set theories to subsystems of second arithmetic.
The anatytic conception of truth and the foundations of arithmetic
Authors: Apostoli Peter
Published: May 2006

Until very recently, it was thought that there couldn't be anycurrentinterest in logicism as a philosophy of mathematics. Indeed, there is an old argument one often finds that logicism is a simple nonstarter just in virtue of the fact that if it were a logical truth that there are infinitely many natural numbers, then this would be in conflict with the existence of finite models. It is certainly true that from the perspective of model theory, arithmetic cannot be a part of logic. However, it is equally true that model theory's reliance on a background of axiomatic set theory renders it unable to match Frege's Theorem, the derivation within second order logic of the infinity of the number series from the contextual “definition” of the cardinality operator. Called “Hume's Principle” by Boolos, the contextual definition of the cardinality operator is presented in Section 63 ofGrundlagen, as the statement that, for any conceptsFandG,

the number ofFs = the number ofGs

if, and only if,

Fis equinumerous withG.

The philosophical interest in Frege's Theorem derives from the thesis, defended for example by Crispin Wright, that Hume's principle expresses our pre-analytic conception of assertions of numerical identity. However, Boolos cites the very fact that Hume's principle has only infinite models as grounds for denying that it is logically true: For Boolos, Hume's principle is simply a disguised axiom of infinity.
Two consistency results on set mappings
Authors: Komjáth Péter , Shelah Saharon
Published: May 2006

It is consistent that there is a set mapping from the four-tuples of ωninto the finite subsets with no free subsets of sizetnfor some natural numbertn. For anyn< ω it is consistent that there is a set mapping from the pairs of ωninto the finite subsets with no infinite free sets. For anyn< ω it is consistent that there is a set mapping from the pairs of ωninto ωnwith no uncountable free sets.
Toward a constructive theory of unbounded linear operators
Authors: Ye Feng
Published: May 2006

We show that the following results in the classical theory of unbounded linear operators on Hilbert spaces can be proved within the framework of Bishop's constructive mathematics: the Kato-Rellich theorem, the spectral theorem. Stone's theorem, and the self-adjointness of the most common quantum mechanical operators, including the Hamiltonians of electro-magnetic fields with some general forms of potentials.
Categorical quasivarieties via Morita equivalence
Authors: Kearnes Keith A.
Published: May 2006

We give a new proof of the classification of ℵ0-categorical quasivarieties by using Morita equivalence to reduce to term minimal quasivarieties.
On recursive enumerability with finite repetitions
Authors: Wehner Stephan
Published: May 2006

It is an open problem within the study of recursively enumerable classes of recursively enumerable sets to characterize those recursively enumerable classes which can be recursively enumerated without repetitions. This paper is concerned with a weaker property of r.e. classes, namely that of being recursively enumerable with at most finite repetitions.

This property is shown to behave more naturally: First we prove an extension theorem for classes satisfying this property. Then the analogous theorem for the property of recursively enumerable classes of being recursively enumerable with a bounded number of repetitions is shown not to hold. The index set of the property of recursively enumerable classes “having an enumeration with finite repetitions” is shown to be -complete.
Relative constructivity
Authors: Kohlenbach Ulrich
Published: May 2006

In a previous paper [13] we introduced a hierarchy (GnAω)n∈ℕ of subsystems of classical arithmetic in all finite types where the growth of definable functions of GnAω corresponds to the well-known Grzegorczyk hierarchy. Let AC-qf denote the schema of quantifier-free choice.

[11], [13], [8] and [7] study various analytical principles Γ in the context of the theories GnAω + AC-qf (mainly for n = 2) and use proof-theoretic tools like, e.g., monotone functional interpretation (which was introduced in [12]) to determine their impact on the growth of uniform bounds Φ such that

which are extractable from given proofs (based on these principles Γ) of sentences

Here A0(u, k, v, w) is quantifier-free and contains only u, k, v, w as free variables; t is a closed term and ≤p is defined pointwise. The term ‘uniform bound’ refers to the fact that Φ does not depend on v ≤ptuk (see [12] for the relevance of such uniform bounds in numerical analysis and for concrete applications to approximation theory).
The shuffle Hopf algebra and noncommutative full completeness
Authors: Blute R. F. , Scott P. J.
Published: May 2006

We present a full completeness theorem for the multiplicative fragment of a variant of noncommutative linear logic, Yetter'scyclic linear logic(CyLL). The semantics is obtained by interpreting proofs as dinatural transformations on a category of topological vector spaces, these transformations being equivariant under certain actions of a noncocommutative Hopf algebra called theshuffle algebraMultiplicative sequents are assigned a vector space of such dinaturals, and we show that this space has as a basis the denotations of cut-free proofs in CyLL + MIX. This can be viewed as a fully faithful representation of a free *-autonomous category, canonically enriched over vector spaces.

This paper is a natural extension of the authors' previous work, “Linear Läuchli Semantics”, where a similar theorem is obtained for the commutative logic MLL + MIX. In that paper, we interpret proofs as dinaturals which are invariant under certain actions of the additive group of integers. Here we also present a simplification of that work by showing that the invariance criterion is actually a consequence of dinaturality. The passage from groups to Hopf algebras in this paper corresponds to the passage from commutative to noncommutative logic. However, in our noncommutative setting, one must still keep the invariance condition on dinaturals.
Large cardinals and large dilators
Authors: Lewis Andy
Published: May 2006

Applying Woodin's non-stationary tower notion of forcing, I prove that the existence of a supercompact cardinal κ in V and a Ramsey dilator in some small forcing extension V[G] implies the existence in V of a measurable dilator of size κ, measurable by κ-complete measures.
On the consistency of the Definable Tree Property on ℵ1
Authors: Leshem Amir
Published: May 2006

In this paper we prove the equiconsistency of “Every ω1 –tree which is first order definable over (, ε) has a cofinal branch” with the existence of a reflecting cardinal. We also prove that the addition of MA to the definable tree property increases the consistency strength to that of a weakly compact cardinal. Finally we comment on the generalization to higher cardinals.
Minimal types in separably closed field
Authors: Chatzidakis Zoé , Wood Carol
Published: May 2006

In [1], examples of types of U-rank 1 (i.e., minimal types) in the theories of separably closed fields were constructed, en route to displaying certain dimension phenomena. We construct here additional examples with U-rank 1 and of various transcendence degrees over arbitrary separably closed fields. Our examples include ones which are minimal but of infinite transcendence degree, i.e., not thin. Our interest in building new examples was piqued after seeing the role played by minimal types over separably closed fields in Hrushovski's analysis of abelian varieties. This article is the result of several working sessions between the authors at Wesleyan University and Paris 7, and was completed during the Model Theory of Fields program at MSRI in 1998. We are grateful for the hospitality and support of all three institutions. We thank Elisabeth Bouscaren and Françoise Delon for reading an earlier version of this paper, providing useful suggestions and corrections.
The fine structure of real mice
Authors: Cunningham Daniel W.
Published: May 2006

Before one can construct scales of minimal complexity in the Real Core Model, K(ℝ), one needs to develop the fine-structure theory of K (ℝ). In this paper, the fine structure theory of mice, first introduced by Dodd and Jensen, is generalized to that of real mice. A relative criterion for mouse iterability is presented together with two theorems concerning the definability of this criterion. The proof of the first theorem requires only fine structure; whereas, the second theorem applies to real mice satisfying AD and follows from a general definability result obtained by abstracting work of John Steel on L(ℝ). In conclusion, we discuss several consequences of the work presented in this paper relevant to two issues: the complexity of scales in K(ℝ)and the strength of the theory ZF + AD + ┐DCℝ.
Kolmogorov complexity and symmetric relational structures
Authors: Fouché W. L. , Potgieter P. H.
Published: May 2006

We study partitions of Fraïssé limits of classes of finite relational structures where the partitions are encoded by infinite binary strings which are random in the sense of Kolmogorov-Chaitin.
Logics which capture complexity classes over the reals
Authors: Cucker Felipe , Meer Klaus
Published: May 2006

In this paper we deal with the logical description of complexity classes arising in the real number model of computation introduced by Blum, Shub, and Smale [4]. We adapt the approach of descriptive complexity theory for this model developped in [14] and extend it to capture some further complexity classes over the reals by logical means. Among the latter we find NCℝ, PARℝ, EXPℝ and some others more.
The Rudin-Blass ordering of ultrafilters
Authors: Laflamme Claude , Zhu Jian-Ping
Published: May 2006

We discuss the finite-to-one Rudin-Keisler ordering of ultrafilters on the natural numbers, which we baptize the Rudin-Blass ordering in honour of Professor Andreas Blass who worked extensively in the area.

We develop and summarize many of its properties in relation to its bounding and dominating numbers, directedness, and provide applications to continuum theory. In particular, we prove in ZFC alone that there exists an ultrafilter with no Q-point below in the Rudin-Blass ordering.
An intensional type theory: motivation and cut-elimination
Authors: Gilmore Paul C
Published: May 2006

By the theory TT is meant the higher order predicate logic with the following recursively defined types:

(1) 1 is the type of individuals and [] is the type of the truth values:

(2) [τ1…..τn] is the type of the predicates with arguments of the types τ1…..τn.

The theory ITT described in this paper is an intensional version of TT. The types of ITT are the same as the types of TT, but the membership of the type 1 of individuals in ITT is an extension of the membership in TT. The extension consists of allowing any higher order term, in which only variables of type 1 have a free occurrence, to be a term of type 1. This feature of ITT is motivated by a nominalist interpretation of higher order predication.

In ITT both well-founded and non-well-founded recursive predicates can be defined as abstraction terms from which all the properties of the predicates can be derived without the use of non-logical axioms.

The elementary syntax, semantics, and proof theory for ITT are defined. A semantic consistency proof for ITT is provided and the completeness proof of Takahashi and Prawitz for a version of TT without cut is adapted for ITT: a consequence is the redundancy of cut.
Credibility limited revision
Authors: Hansson Sven Ove , Fermé Eduardo Leopoldo , Cantwell John , Falappa Marcelo Alejandro
Published: May 2006

Five types of constructions are introduced for non-prioritized belief revision, i.e., belief revision in which the input sentence is not always accepted. These constructions include generalizations of entrenchment-based and sphere-based revision. Axiomatic characterizations are provided, and close interconnections are shown to hold between the different constructions.
Proper forcing and L(ℝ)
Authors: Neeman Itay , Zapletal Jindřich
Published: May 2006

We present two ways in which the model L(ℝ) is canonical assuming the existence of large cardinals. We show that the theory of this model, with ordinal parameters, cannot be changed by small forcing: we show further that a set of ordinals in V cannot be added to L(ℝ) by small forcing. The large cardinal needed corresponds to the consistency strength of ADL(ℝ): roughly ω Woodin cardinals.
Elementary equivalence for abelian-by-finite and nilpotent groups
Authors: Oger Francis
Published: May 2006

We show that two abelian-by-finite groups are elementarily equivalent if and only if they satisfy the same sentences with two alternations of quantifiers. We also prove that abelian-by-finite groups satisfy a quantifier elimination property. On the other hand, for each integer n, we give some examples of nilpotent groups which satisfy the same sentences with n alternations of quantifiers and do not satisfy the same sentences with n + 1 alternations of quantifiers.
Constitution v. Constitutional Theory: The Question of the States v. the Nation
Authors: Corwin Edward S.
Published: May 2006

The relation of the states and the nation is a topic on which there is a good deal of discussion these days. One week last spring brought to my desk four pamphlets on the subject—all of them from an anti-nationalistic point of view, and most of them emanating from the sovereign state of Maryland. At the same time The Times newspaper carried several articles on the subject. One was a rebuke by the President of the present tendency to look toward the national government for everything. A day or two later another utterance from the same distinguished source called for the establishment of a “federal” bureau of recreation.

But, along with this ancient issue, whose infinite variety time has never yet been able to wither or custom to stale, goes another of even broader import.

Like other branches of learning, constitutional interpretation pretends to a certain terminology or jargon of its own, but just how accurate this is, is indeed a question. And if it be inaccurate, this fact furnishes all the more reason why some attempt at defining terms should accompany a consideration of the question of the constitutional relationship of the states and the nation.
Neighborhood Poverty and African American Politics
Authors: Cohen Cathy J. , Dawson Michael C.
Published: May 2006

William Wilson and other scholars argue that one of the attributes of devastated neighborhoods is social isolation. We shall explore whether neighborhoods that seem to indicate significant social isolation also foster political isolation. We begin our examination by providing a description of the poor in the samples from the 1989 Detroit Area Study. We then turn our attention toward analyzing the effects of neighborhood poverty on African–American public opinion and political participation. We conclude with a discussion of how neighborhood poverty affects African-American politics and the consequences of those politics for the theory and practice of American democracy.
Power Politics and International Trade
Authors: Gowa Joanne , Mansfield Edward D.
Published: May 2006

Recent literature attributes the relative scarcity of open international markets to the prisoner's dilemma structure of state preferences with respect to trade. We argue that the prisoner's dilemma representation does not reflect the most critical aspect of free trade agreements in an anarchic international system, namely, their security externalities. We consider these external effects explicitly. Doing so leads us to two conclusions: (1) free trade is more likely within, rather than across, political-military alliances; and (2) alliances are more likely to evolve into free-trade coalitions if they are embedded in bipolar systems than in multipolar systems. Using data drawn from an 80-year period beginning in 1905, we test these hypotheses. The results of the analysis make it clear that alliances do have a direct, statistically significant, and large impact on bilateral trade flows and that this relationship is stronger in bipolar, rather than in multipolar, systems.
Rainfall and the Populist Party in Nebraska
Authors: Barnhart John D.
Published: May 2006

The significance of Populism is being increasingly recognized. In this day of independent voting, and of the “farm bloc,” it is unnecessary to stimulate interest in this phase of American political, economic, and agricultural history. Although its term of life was short and turbid, its relation to other movements and questions gives it importance beyond that which it would otherwise enjoy.

Many have endeavored to explain its rise. To some it represented an outpouring of the dangerous elements of the frontier combined with the beginnings of socialistic and anarchistic tendencies in the cities. An English observer characterized the supporters of Bryan in 1896 as the “forces of political and social revolution.” A western editorial writer wrote that ninety per cent of the leaders of the Populist Party were “destitute of personal or political integrity” and classed them as “vagabonds, slanderers, and demagogues.”
Heidegger on Freedom: Political not Metaphysical
Authors: Thiele Leslie Paul
Published: May 2006

This essay analyzes modern and postmodern concepts of freedom and contrasts them to a Heideggerian understanding. Positive, negative, and what might be called Foucaultian or Nietzschean liberty are demonstrated to bear a common trait. In such modern and postmodern formulations, freedom is consistently identified with a form of mastery. This identification of freedom with mastery, I argue, encourages ecological abuse, supports the dangerous prerogatives of statist sovereignty, and strengthens the resilience of patriarchy. The political significance of Heidegger's alternative vision is addressed.
Civic Culture and Democracy: The Question of Causal Relationships
Authors: Muller Edward N. , Seligson Mitchell A.
Published: May 2006

A causal model of relationships between structural properties of states, civic culture attitudes of the general public, and change in level of democracy is tested with cross-national data. The model permits inferences about the possibility of unidirectional or reciprocal causation between civic culture attitudes and democracy, controlling for macrosocietal variables such as economic development, income inequality, and subcultural pluralism. Most civic culture attitudes do not have any significant impact on change in democracy. One of them, interpersonal trust, appears clearly to be an effect rather than a cause of democracy. The exception is the percentage of the general public that prefers gradual reform of society instead of revolutionary change or intransigent defense of the status quo. Support for gradual reform has a positive impact on change in democracy, and it is unrelated to a country's years of continuous democracy—findings that support the hypothesis of a unidirectional civic culture effect on democracy.
An Individual-Level Multiequation Model of Expenditure Effects in Contested House Elections
Authors: Kenny Christopher , McBurnett Michael
Published: May 2006

We shall address questions concerning the impact of candidate spending in congressional elections in a new way. We develop a multiequation model of congressional vote choice that takes the endogeneity of expenditures into account. We then estimate both this model and the more traditional single-equation model using individual level survey data. The substantial differences we find between the two models indicates that the simultaneity bias present in the single-equation model is not trivial. The challenger and incumbent expenditure terms are each significant (whereas only challenger expenditures are in the single-equation setup) and of much greater magnitude in the multiequation case. In addition, we evaluate hypotheses grounded in persuasive communications theory concerning the type of individuals most affected by the messages emanating from the campaigns. We find that individuals with higher education, those with greater interest in campaigns, and those with strongly held convictions are unaffected by candidate spending, whereas individuals lacking each of these attributes are greatly influenced by campaign expenditures.
Democracy and the Peaceful Settlement of International Conflict
Authors: Dixon William J.
Published: May 2006

The research reported here develops an explanation for the often-noted absence of international war between democratic states. This explanation is derived from a theoretical rationale centered on universal democratic norms for reconciling competing values and interests. I argue that democratic states locked in disputes are better equipped than others with the means for diffusing conflict situations at an early stage before they have an opportunity to escalate to military violence. Not only is this explanatory logic consistent with the published findings on democracy and war, but it also entails the novel empirical proposition that disputes between democracies are more amenable than are other disputes to peaceful settlements, the hypothesis I examine here. Analyses of contemporary interstate disputes reveal that even when potentially confounding factors are controlled, democratic opponents are significantly more likely to reach peaceful settlements than other types of disputants.
Voting and Vetoing
Authors: Winter Eyal
Published: May 2006

The consequences of veto power in committees is analyzed using the approach of noncooperative bargaining theory. It is first shown that in equilibrium nonveto players do not share in the benefits gained by the decision making of the committee, that is, in every equilibrium outcome of the bargaining game, nonveto players earn zero. Some measures for reducing the excessive power of veto members in committees are analyzed. Specifically, I study the effects of imposing a deadline on negotiations and of expanding the committee by increasing the number of nonveto players. Quantitative results are given for the case of the UN Security Council.
Voting Correctly
Authors: Lau Richard R. , Redlawsk David P.
Published: May 2006

The average voter falls far short of the prescriptions of classic democratic theory in terms of interest, knowledge, and participation in politics. We suggest a more realistic standard: Citizens fulfill their democratic duties if, most of the time, they vote “correctly.” Relying on an operationalization of correct voting based on fully informed interests, we present experimental data showing that, most of the time, people do indeed manage to vote correctly. We also show that voters' determinations of their correct vote choices can be predicted reasonably well with widely available survey data. We illustrate how this measure can be used to determine the proportion of the electorate voting correctly, which we calculate at about 75% for the five American presidential elections between 1972 and 1988. With a standard for correct vote decisions, political science can turn to exploring the factors that make it more likely that people will vote correctly.
Political Constructivism in Rawls'sPolitical Liberalism
Authors: Klosko George
Published: May 2006

InPolitical Liberalism, John Rawls employs a distinctive method of “political constructivism” to establish his well-known principles of justice, arguing that his principles are suited to bridge the ineradicable pluralism of liberal societies and so to ground an “overlapping consensus.” Setting aside the question of whether Rawls's method supports his principles, I argue that he does not adequately defend reliance on this particular method rather than alternatives. If the goal of Rawls's “political” philosophy is to derive principles that are able to overcome liberal pluralism, then another and simpler method should be employed. The “method of convergence” would develop liberal principles directly from the convergence of comprehensive views in existing societies, and so give rise to quite different moral principles.
Inference by complementary elimination
Authors: Symonds Bernard K. , Chisholm Roderick M.
Published: May 2006

The inferences countenanced by the traditional rules of modus ponens, modus tollens, disjunctive syllogism, hypothetical syllogism, and the complex types of dilemma may be regarded as single applications of one rule of inference, “the rule of complementary elimination”. In the present paper, we shall discuss this rule informally and illustrate it in application to expressions written in the language of Principia Mathematica. Our illustrations will contain no connectives except for those for conjunction, disjunction, and negation; we use parentheses in place of dots; and we allow disjunction and conjunction to have any number of operands more than two.

In applying complementary elimination to a set of premises, we take the following three steps, (i) We form, merely by disjoining the premises, an expression which we shall call a premise disjunction, (ii) If we have n premises, we eliminate n minus one (or fewer) pairs of the following sort from our premise disjunction: each pair is such that one of its members is the negation of the other and both members are specific occurrences of disjuncts of our premise disjunction. We shall call such pairs complementary pairs, (iii) The formula obtained by means of our second step is one that may be made well-formed merely by eliminating parentheses or connectives other than negation; we make such elimination, and any formula we thus obtain is a consequence of our premises.
Horn sentences in identity theory
Authors: Appel K. I.
Published: May 2006

Horn [2] obtained a sufficient condition for an elementary class to be closed under direct product. Chang and Morel [1] showed that this is not a necessary condition. We will show that, if consideration is restricted to identity theory, that is, a first-order predicate calculus with equality but no other relation symbols or operation symbols, Horn's condition is necessary and sufficient.

A model for identity theory consists of a non-empty domain A, but no relations or operations except equality. If I is an index set, and for each is a model for identity theory, then the direct product of the is a model for identity theory and has domain A, the cartesian product of the Ai.
Uniformization of linear arrays
Authors: Fine N. J. , Harrop R.
Published: May 2006

In Chapter X of his book on The structure of appearance, Goodman [1] studies the concept of linear order in finite linear arrays in terms of a two-place symmetrical predicate M, M(x, y) being read as x matches y. Although arising in the development of a nominalistic philosophical system, many problems relating to the properties of M are essentially of a mathematical and not of a philosophical nature. Some were considered by Fine in [2]. In the terminology of [1] and [2], the main result of this paper is that there is an effective method for embedding a weakly mapped array (consistently) in a uniform array. This carries with it the result that it is possible to obtain effectively a minimal uniform extension of the original array, that is, a uniform extension with minimum span for such an extension and with the minimum number of elements possible for a uniform extension with this span.