bluuebunny/crossref_metadata_2025 huggingface dataset:
Determinateness of certain almost-Borel games
Authors: Wolf Robert S.
Published: May 2006

We prove (in ZFC Set Theory) that all infinite games whose winning sets are of the following forms are determined:

(1) (A − S) ∪ B, where A is , , and the game whose winning set is B is “strongly determined” (meaning that all of its subgames are determined).

(2) A Boolean combination of sets and sets smaller than the continuum.

This also enables us to show that strong determinateness is not preserved under complementation, improving a result of Morton Davis which required the continuum hypothesis to prove this fact.

Various open questions related to the above results are discussed. Our main conjecture is that (2) above remains true when is replaced by “Borel”.
The status of the axiom of choice in set theory with a universal set
Authors: Forster T. E.
Published: May 2006

The purpose of this paper is not to produce a survey of systems with a universal set: we do not yet understand them well enough. Rather it will concentrate on one particular aspect of them: the curious circumstance that there are half-a-dozen or so distinct proofs of ~ AC available in set theories with a universal set. This began to emerge in 1953 when Specker published in [2] a proof of ~ AC in Quine's system NF. Until recently this was an isolated phenomenon and poorly understood. The proof answered few questions and seemed rather ad hoc, thus inviting an investigation to determine whether this was an artefact caused by the particular axioms for NF, or part of a general conflict between the demands of big sets and AC.

We will start with an informal discussion of the genesis of set theories with a universal set, collecting, en route, a number of desiderata for such theories. A number of new refutations of AC in systems meeting some or all of these conditions will then be presented. The conclusion the reader is invited to draw is that any sensible set theory with a universal set will probably have trouble with AC.

Why do set theory with V e V at all? It contradicts conventional wisdom which teaches us that e is wellfounded. It must be said for this doctrine (let us abbreviate it to WOOF) that it has enabled the rapid execution of the logicist programme, so if that were the sole purpose of set theory we could consider ourselves well served. However most pure mathematicians are platonists and study things not because they are useful but simply because they are there. And the belief that V is not there can, after all, only be the result of early conditioning.
Second-order languages and mathematical practice
Authors: Shapiro Stewart
Published: May 2006

There are well-known theorems in mathematical logic that indicate rather profound differences between the logic of first-order languages and the logic of second-order languages. In the first-order case, for example, there is Gödel's completeness theorem: every consistent set of sentences (vis-à-vis a standard axiomatization) has a model. As a corollary, first-order logic is compact: if a set of formulas is not satisfiable, then it has a finite subset which also is not satisfiable. The downward Löwenheim-Skolem theorem is that every set of satisfiable first-order sentences has a model whose cardinality is at most countable (or the cardinality of the set of sentences, whichever is greater), and the upward Löwenheim-Skolem theorem is that if a set of first-order sentences has, for each natural number n, a model whose cardinality is at least n, then it has, for each infinite cardinal κ (greater than or equal to the cardinality of the set of sentences), a model of cardinality κ. It follows, of course, that no set of first-order sentences that has an infinite model can be categorical. Second-order logic, on the other hand, is inherently incomplete in the sense that no recursive, sound axiomatization of it is complete. It is not compact, and there are many well-known categorical sets of second-order sentences (with infinite models). Thus, there are no straightforward analogues to the Löwenheim-Skolem theorems for second-order languages and logic.

There has been some controversy in recent years as to whether “second-order logic” should be considered a part of logic, but this boundary issue does not concern me directly, at least not here.
Model theory under the axiom of determinateness
Authors: Spector Mitchell
Published: May 2006

We initiate the study of model theory in the absence of the Axiom of Choice, using the Axiom of Determinateness as a powerful substitute. We first show that, in this context, is no more powerful than first-order logic. The emphasis then turns to upward Löwenhein-Skolem theorems; ℵ1 is the Hanf number of first-order logic, of , and of a strong fragment of , The main technical innovation is the development of iterated ultrapowers using infinite supports; this requires an application of infinite-exponent partition relations. All our theorems can be proven from hypotheses weaker than AD.
Omitting types for stable ccc theories
Authors: Newelski Ludomir
Published: May 2006

In this paper we investigate omitting types for a certain kind of stable theories which we call stable ccc theories. In Theorem 2.1 we improve Steinhorn's result from [St]. We prove also some independence results concerning omitting types. The main results presented in this paper were part of the author's Ph.D. thesis [N1].

Throughout, we use the standard set-theoretic and model-theoretic notation, such as can be found for example in [Sh] or [M]. So in particular T is always a countable complete theory in the language L. We consider all models of T and all sets of parameters subsets of the monster model ℭ, which is very saturated. Ln(A) denotes the Lindenbaum-Tarski algebra of formulas with parameters from A and n free variables. We omit n in Ln(A) when n = 1 or when it is clear from the context what n is. If φ, ψ ∈ L(A) are consistent then we say that φ is below ψ if ψ⊢ψ. For a type p and a set A ⊆ ℭ, p(A) is the set of tuples of elements of A which satisfy p. Formulas are special cases of types. We say that a type p is isolated over A if, for some φ() ∈ L(A), φ() ⊢ p(x), i.e. φ isolates p. For a formula φ, [φ] denotes the class of types which contain φ. We assume that the reader is familiar with some basic knowledge of forking, as presented in [Sh, III] or [M].

Throughout, we work in ZFC. and denote (countable) transitive models of ZFC. cov K is the minimal number of meager sets covering the real line R. In this paper we prove theorems showing connections between omitting types and the combinatorics of the real line. More results in this direction are presented in [N2] and [N3].
Hilbert's program relativized; Proof-theoretical and foundational reductions
Authors: Feferman Solomon
Published: May 2006

In the Symposium on Hilbert's Program to which the following was contributed, I was asked to talk about the metamathematical aspects of Hilbert's Program (H.P.), while the other two speakers (Simpson and Prawitz) were to deal with the mathematical and philosophical aspects respectively. However, more so than for other foundational schemes, these three aspects of H.P., both as originally conceived and in its subsequent developments, are intimately linked.

Here I shall survey a body of proof-theoretical results stemming from H.P., but organized in a way that is closely tied to various reductive foundational aims, albeit going beyond those advanced by Hilbert. I believe this view of reductive proof-theory (not original with me) helps one to better understand what has been achieved thereby than other, more familiar accounts.
Some remarks on the algebraic structure of the Medvedev Lattice
Authors: Sorbi Andrea
Published: May 2006

This paper investigates the algebraic structure of the Medvedev lattice . We prove that is not a Heyting algebra. We point out some relations between and the Dyment lattice and the Mučnik lattice. Some properties of the degrees of enumerability are considered. We give also a result on embedding countable distributive lattices in the Medvedev lattice.
The McKinsey axiom is not canonical
Authors: Goldblatt Robert
Published: May 2006

The logic KM is the smallest normal modal logic that includes the McKinsey axiom

It is shown here that this axiom is not valid in the canonical frame for KM, answering a question first posed in the Lemmon-Scott manuscript [Lemmon, 1966].

The result is not just an esoteric counterexample: apart from interest generated by the long delay in a solution being found, the problem has been of historical importance in the development of our understanding of intensional model theory, and is of some conceptual significance, as will now be explained.

The relational semantics for normal modal logics first appeared in [Kripke, 1963], where a number of well-known systems were shown to be characterised by simple first-order conditions on binary relations (frames). This phenomenon was systematically investigated in [Lemmon, 1966], which introduced the technique of associating with each logic L a canonical frame which invalidates every nontheorem of L. If, in addition, each L-theorem is valid in , then L is said to be canonical. The problem of showing that L is determined by some validating condition C, meaning that the L-theorems are precisely those formulae valid in all frames satisfying C, can be solved by showing that satisfies C—in which case canonicity is also established. Numerous cases were studied, leading to the definition of a first-order condition Cφ associated with each formula φ of the form

where Ψ is a positive modal formula.
On adding (ξ) to weak equality in combinatory logic
Authors: Bunder Martin W. , Hindley J. Roger , Seldin Jonathan P.
Published: May 2006

Because the main difference between combinatory weak equality and λβ-equality is that the rule

is valid for the latter but not the former, it is easy to assume that another way of defining combinatory β-equality is to add rule (ξ) to the postulates for weak equality. However, to make this true, one must choose the definition of combinatory abstraction in (ξ) very carefully. If one tries to use one of the more common abstraction algorithms, the result will be an equality, =ξ, that is either equivalent to βη-equality (and so strictly stronger than β-equality) or else strictly weaker than β-equality. This paper will study the relations =ξ for several commonly used abstraction-algorithms, distinguish between them, and axiomatize them.
Reducts of the random graph
Authors: Thomas Simon
Published: May 2006

Let Γ be the unique (up to isomorphism) countable graph with the following property: (*) Given any two finite disjoint subsets U and V of Γ, there exists a vertex z ∈ Γ joined to every vertex in U and to none in V.

Thus Γ is the countable, universal, homogeneous graph; also known as the random graph. In this paper, we shall study the reducts of Γ Here a reduct of Γ is defined to be a permutation group (G, Γ) such that:

(i) Aut(Γ) ≤ G; and

(ii) G is a closed subgroup of Sym(Γ).

Equivalently, there exists a structure for some language L such that:

(iii) has universe Γ;

(iv) for each R ∈ L, is definable without parameters in Γ; and

(v) G = Aut().
Belief contraction in the context of the general theory of rational choice
Authors: Rott Hans
Published: May 2006

This paper reorganizes and further develops the theory of partial meet contraction which was introduced in a classic paper by Alchourrón, Gärdenfors, and Makinson. Our purpose is threefold. First, we put the theory in a broader perspective by decomposing it into two layers which can respectively be treated by the general theory of choice and preference and elementary model theory. Second, we reprove the two main representation theorems of AGM and present two more representation results for the finite case that “lie between” the former, thereby partially answering an open question of AGM. Our method of proof is uniform insofar as it uses only one form of “revealed preference”, and it explains where and why the finiteness assumption is needed. Third, as an application, we explore the logic characterizing theory contractions in the finite case which are governed by the structure of simple and prioritized belief bases.
On an interpretation of second order quantification in first order intuitionistic propositional logic
Authors: Pitts Andrew M.
Published: May 2006

We prove the following surprising property of Heyting's intuitionistic propositional calculus, IpC. Consider the collection of formulas, ϕ, built up from propositional variables (p, q, r, …) and falsity (⊥) using conjunction (∧), disjunction (∨) and implication (→). Write ⊢ϕ to indicate that such a formula is intuitionistically valid. We show that for each variablepand formula ϕ there exists a formulaApϕ (effectively computable from ϕ), containing only variables not equal topwhich occur in ϕ, and such that for all formulas ψ not involvingp, ⊢ψ →Apϕ if and only if ⊢ψ → ϕ. Consequently quantification over propositional variables can be modelled in IpC, and there is an interpretation of the second order propositional calculus, IpC2, in IpC which restricts to the identity on first order propositions.

An immediate corollary is the strengthening of the usual interpolation theorem for IpC to the statement that there are least and greatest interpolant formulas for any given pair of formulas. The result also has a number of interesting consequences for the algebraic counterpart of IpC, the theory of Heyting algebras. In particular we show that a model of IpC2can be constructed whose algebra of truth-values is equal to any given Heyting algebra.
The strength of the isomorphism property
Authors: Jin Renling , Shelah Saharon
Published: May 2006

In § 1 of this paper, we characterize the isomorphism property of nonstandard universes in terms of the realization of some second-order types in model theory. In §2, several applications are given. One of the applications answers a question of D. Ross in [this Journal, vol. 55 (1990), pp. 1233–1242] about infinite Loeb measure spaces.
U-monad topologies of hyperfinite time lines
Authors: Jin Renling
Published: May 2006

In an ω1-saturated nonstandard universe a cut is an initial segment of the hyperintegers which is closed under addition. Keisler and Leth in [KL] introduced, for each given cut U, a corresponding U-topology on the hyperintegers by letting O be U-open if for any x ϵ O there is a y greater than all the elements in U such that the interval [x − y, x + y] ⊆ O. Let U be a cut in a hyperfinite time line , which is a hyperfinite initial segment of the hyperintegers. The U-monad topology of is the quotient topology of the U-topological space modulo U. In this paper we answer a question of Keisler and Leth about the U-monad topologies by showing that when is κ-saturated and has cardinality κ,(1) if the coinitiality of U1, is uncountable, then the U1,-monad topology and the U2-monad topology are homcomorphic iff both U1, and U2 have the same coinitiality; and (2) can produce exactly three different U-monad topologies (up to homeomorphism) for those U's with countable coinitiality. As a corollary can produce exactly four different U-monad topologies if the cardinality of is ω1.
On strong provability predicates and the associated modal logics
Authors: Ignatiev Konstantin N.
Published: May 2006

PA is Peano Arithmetic. Pr(x) is the usual Σ1,-formula representing provability in PA. A strong provability predicate is a formula which has the same properties as Pr(·) but is not Σ1. An example: Q is ω-provable if PA + ¬Q is ω-inconsistent (Boolos [4]). In [5] Dzhaparidze introduced a joint provability logic for iterated ω-provability and obtained its arithmetical completeness.

In this paper we prove some further modal properties of Dzhaparidze's logic, e.g., the fixed point property and the Craig interpolation lemma. We also consider other examples of the strong provability predicates and their applications.
Interpolation in fragments of classical linear logic
Authors: Roorda Dirk
Published: May 2006

We study interpolation for elementary fragments of classical linear logic. Unlike in intuitionistic logic (see [Renardel de Lavalette, 1989]) there are fragments in linear logic for which interpolation does not hold. We prove interpolation for a lot of fragments and refute it for the multiplicative fragment (→, +), using proof nets and quantum graphs. We give a separate proof for the fragment with implication and product, but without the structural rule of permutation. This is nearly the Lambek calculus. There is an appendix explaining what quantum graphs are and how they relate to proof nets.
Contraction-free sequent calculi for intuitionistic logic
Authors: Dyckhoff Roy
Published: May 2006

Gentzen's sequent calculus LJ, and its variants such as G3 [21], are (as is well known) convenient as a basis for automating proof search for IPC (intuitionistic propositional calculus). But a problem arises: that of detecting loops, arising from the use (in reverse) of the rule ⊃⇒ for implication introduction on the left. We describe below an equivalent calculus, yet another variant on these systems, where the problem no longer arises: this gives a simple but effective decision procedure for IPC.

The underlying method can be traced back forty years to Vorob′ev [33], [34]. It has been rediscovered recently by several authors (the present author in August 1990, Hudelmaier [18], [19], Paulson [27], and Lincoln et al. [23]). Since the main idea is not plainly apparent in Vorob′ev's work, and there are mathematical applications [28], it is desirable to have a simple proof. We present such a proof, exploiting the Dershowtiz-Manna theorem [4] on multiset orderings.

Consider the task of constructing proofs in Gentzen's sequent calculus LJ of intuitionistic sequents Γ⇒ G, where Γ is a set of assumption formulae and G is a formula (in the language of zero-order logic, using the nullary constant f [absurdity], the unary constant ¬ [negation, with ¬A =defA ⊃ f] and the binary constants &, ∨, and ⊃ [conjunction, disjunction, and implication respectively]). By the Hauptsatz [15], there is an apparently simple algorithm which breaks up the sequent, growing the proof tree until one reaches axioms (of the form Γ⇒ A where A is in Γ), or can make no further progress and must backtrack or even abandon the search. (Gentzen's argument in fact was to use the subformula property derived from the Hauptsatz to limit the size of the search tree. Došen [5] improves on this argument.)
Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
Authors: Krajíček Jan
Published: May 2006

A proof of the (propositional) Craig interpolation theorem for cut-free sequent calculus yields that a sequent with a cut-free proof (or with a proof with cut-formulas of restricted form; in particular, with only analytic cuts) withkinferences has an interpolant whose circuit-size is at mostk. We give a new proof of the interpolation theorem based on a communication complexity approach which allows a similar estimate for a larger class of proofs. We derive from it several corollaries:

(1)

Feasible interpolation theorems for the following proof systems:

(a)

resolution

(b)

a subsystem ofLKcorresponding to the bounded arithmetic theory(α)

(c)

linear equational calculus

(d)

cutting planes.

(2)

New proofs of the exponential lower bounds (for new formulas)

(a)

for resolution ([15])

(b)

for the cutting planes proof system with coefficients written in unary ([4]).

(3)

An alternative proof of the independence result of [43] concerning the provability of circuit-size lower bounds in the bounded arithmetic theory(α).

In the other direction we show that a depth 2 subsystem ofLKdoes not admit feasible monotone interpolation theorem (the so called Lyndon theorem), and that a feasible monotone interpolation theorem for the depth 1 subsystem ofLKwould yield new exponential lower bounds for resolution proofs of the weak pigeonhole principle.
Decidability of Scott's model as an ordered ℚ-vectorspace
Authors: Erdélyi-Szabó Miklós
Published: May 2006

Let L = 〈<, +, hq, 1〉q∈ℚ where ℚ is the set of rational numbers and hq is a one-place function symbol corresponding to multiplication by q. Then the L-theory of Scott's model for intuitionistic analysis is decidable.
The finite model property for various fragments of linear logic
Authors: Lafont Yves
Published: May 2006

To show that a formula A is not provable in propositional classical logic, it suffices to exhibit a finite boolean model which does not satisfy A. A similar property holds in the intuitionistic case, with Kripke models instead of boolean models (see for instance [11]). One says that the propositional classical logic and the propositional intuitionistic logic satisfy a finite model property. In particular, they are decidable: there is a semi-algorithm for provability (proof search) and a semi-algorithm for non provability (model search). For that reason, a logic which is undecidable, such as first order logic, cannot satisfy a finite model property.

The case of linear logic is more complicated. The full propositional fragment LL has a complete semantics in terms of phase spaces [2, 3], but it is undecidable [9]. The multiplicative additive fragment MALL is decidable, in fact PSPACE-complete [9], but the decidability of the multiplicative exponential fragment MELL is still an open problem. For affine logic, that is, linear logic with weakening, the situation is somewhat better: the full propositional fragment LLW is decidable [5].

Here, we show that the finite phase semantics is complete for MALL and for LLW, but not for MELL. In particular, this gives a new proof of the decidability of LLW. The noncommutative case is mentioned, but not handled in detail.
Splitting number at uncountable cardinals
Authors: Zapletal Jindřich
Published: May 2006

We study a generalization of the splitting number s to uncountable cardinals. We prove that 𝔰(κ) > κ+ for a regular uncountable cardinal κ implies the existence of inner models with measurables of high Mitchell order. We prove that the assumption 𝔰(ℵω) > ℵω+1 has a considerable large cardinal strength as well.
Cardinal functions on ultra products of Boolean algebras
Authors: Peterson Douglas
Published: May 2006

This article is concerned with functions k assigning a cardinal number to each infinite Boolean algebra (BA), and the behaviour of such functions under ultraproducts. For some common functions k we have

for others we have ≤ instead, under suitable assumptions. For the function π character we go into more detail. More specifically, ≥ holds when F is regular, for cellularity, length, irredundance, spread, and incomparability. ≤ holds for π. ≥ holds under GCH for F regular, for depth, π, πχ, χ, h-cof, tightness, hL, and hd. These results show that ≥ can consistently hold in ZFC since if V = L holds then all uniform ultrafilters are regular. For π-character we prove two more results: (1) If F is regular and ess , then

(2) It is relatively consistent to have , where A is the denumerable atomless BA.

A thorough analysis of what happens without the assumption that F is regular can be found in Rosłanowski, Shelah [8] and Magidor, Shelah [5]. Those papers also mention open problems concerning the above two possible inequalities.
Pretopologies and completeness proofs
Authors: Sambin Giovanni
Published: May 2006

Pretopologies were introduced in [S], and there shown to give a complete semantics for a propositional sequent calculus BL, here called basic linear logic, as well as for its extensions by structural rules,ex falso quodlibetor double negation. Immediately after Logic Colloquium '88, a conversation with Per Martin-Löf helped me to see how the pretopology semantics should be extended to predicate logic; the result now is a simple and fully constructive completeness proof for first order BL and virtually all its extensions, including the usual, or structured, intuitionistic and classical logic. Such a proof clearly illustrates the fact that stronger set-theoretic principles and classical metalogic are necessary only when completeness is sought with respect to a special class of models, such as the usual two-valued models.

To make the paper self-contained, I briefly review in §1 the definition of pretopologies; §2 deals with syntax and §3 with semantics. The completeness proof in §4, though similar in structure, is sensibly simpler than that in [S], and this is why it is given in detail. In §5 it is shown how little is needed to obtain completeness for extensions of BL in the same language. Finally, in §6 connections with proofs with respect to more traditional semantics are briefly investigated, and some open problems are put forward.
Pure-projective modules and positive constructibility
Authors: Kucera T. G. , Rothmaler Ph.
Published: May 2006

In modules many ‘positive’ versions of model-theoretic concepts turn out to be equivalent to concepts known in classical module theory—by ‘positive’ we mean that instead of allowing arbitrary first-order formulas in the model-theoretic definitions only positive primitive formulas are taken into consideration. (This feature is due to Baur's quantifier elimination for modules, cf. [Pr], however we will not make explicit use of it here.) Often this allows one to combine model-theoretic methods with algebraic ones. One instance of this is the result proved in [Rot1] (see also [Rot2]) that the Mittag-Leffler modules are exactly the positively atomic modules. This paper is parallel to the one just mentioned in that it is proved here, Theorem 3.1, that the pure-projective modules are exactly the positively constructible modules. The following parallel facts from module theory and from model theory led us to this result: every pure-projective module is Mittag-Leffler and the converse is true for countable (in fact even countably generated) modules, cf. [RG]; every constructible model is atomic and the converse is true for countable models, cf. [Pi].
Some applications of ordinal dimensions to the theory of differentially closed fields
Authors: Pong Wai Yan
Published: May 2006

Using the Lascar inequalities, we show that any finite rank δ-closed subset of a quasiprojective variety is definably isomorphic to an affine δ-closed set. Moreover, we show that if X is a finite rank subset of the projective space ℙn and a is a generic point of ℙn, then the projection from a is injective on X. Finally we prove that if RM = RC in DCF0, then RM = RU.
The model theory of differential fields with finitely many commuting derivations
Authors: McGrail Tracey
Published: May 2006

In this paper we set out the basic model theory of differential fields of characteristic 0, which have finitely many commuting derivations. We give axioms for the theory of differentially closed differential fields with m derivations and show that this theory is ω-stable, model complete, and quantifier-eliminable, and that it admits elimination of imaginaries. We give a characterization of forking and compute the rank of this theory to be ωm + 1.
A finite family weak square principle
Authors: Schimmerling Ernest
Published: May 2006

Definition 1.1. Suppose that λ ≤ κ are cardinals and Γ is a subset of (κ, κ+). By , we mean the principle asserting that there is a sequence 〈Fν | ν ∈ lim(Γ)〉 such that for every ν ∈ lim(Γ), the following hold.

(1) 1 ≤ card(Fν) < λ.

(2) The following hold for every C ∈ Fν.

(a) C ⊆ ν ∩ Γ,

(b) C is club in ν,

(c) o.t.(C) ≤ κ,

By we mean . If Γ = (κ, κ+), then we write for and for .

These weak square principles were introduced in [Sch2, 5.1]. They generalize Jensen's principles □κ and , which are equivalent to and respectively. Jensen's global □ principle implies □κ for all κ.

Theorem 1.2. Suppose that is a core model. Assume that every countable premouse M which elementarily embeds into a level of is (ω1 + 1)-iterable. Then, for every κ, holds in .

The minimal non-1-small mouse is essentially a sharp for an inner model with a Woodin cardinal. We originally proved Theorem 1.2 under the assumption that is 1-small, building on [MiSt] and [Sch2]. Some generalizations followed by combining our methods with those of [St2] and [SchSt2]. (For example, the tame countably certified core model Kc satisfies .) In order to eliminate the smallness assumption all together, one replaces our use of the Dodd-Jensen lemma in proofs of condensation properties for with the weak Dodd-Jensen lemma of [NSt].
On the role of implication in formal logic
Authors: Seldin Jonathan P.
Published: May 2006

Evidence is given that implication (and its special case, negation) carry the logical strength of a system of formal logic. This is done by proving normalization and cut elimination for a system based on combinatory logic or λ-calculus with logical constants for and, or, all, and exists, but with none for either implication or negation. The proof is strictly finitary, showing that this system is very weak. The results can be extended to a “classical” version of the system. They can also be extended to a system with a restricted set of rules for implication: the result is a system of intuitionistic higher-order BCK logic with unrestricted comprehension and without restriction on the rules for disjunction elimination and existential elimination. The result does not extend to the classical version of the BCK logic.
Formal topologies on the set of first-order formulae
Authors: Coquand Thierry , Sadocco Sara , Sambin Giovanni , Smith Jan M.
Published: May 2006

The completeness proof for first-order logic by Rasiowa and Sikorski [13] is a simplification of Henkin's proof [7] in that it avoids the addition of infinitely many new individual constants. Instead they show that each consistent set of formulae can be extended to a maximally consistent set, satisfying the following existence property: if it contains (∃x)ϕit also contains some substitutionϕ(y/x) of a variableyforx. In Feferman's review [5] of [13], an improvement, due to Tarski, is given by which the proof gets a simple algebraic form.

Sambin [16] used the same method in the setting of formal topology [15], thereby obtaining a constructive completeness proof. This proof is elementary and can be seen as a constructive and predicative version of the one in Feferman's review. It is a typical, and simple, example where the use of formal topology gives constructive sense to the existence of a generic object, satisfying some forcing conditions; in this case an ultrafilter satisfying the existence property.

In order to get a formal topology on the set of first-order formulae, Sambin used the Dedekind-MacNeille completion to define a covering relation ⊲DM. This method, by which an arbitrary poset can be extended to a complete poset, was introduced by MacNeille [9] and is a generalization of the construction of real numbers from rationals by Dedekind cuts. It is also possible to define an inductive cover, ⊲I, on the set of formulae, which can also be used to give canonical models, see Coquand and Smith [3].
Small fields
Authors: Wagner Frank O.
Published: May 2006

An infinite field with only countably many pure types is algebraically closed.
Computably categorical structures and expansions by constants
Authors: Cholak Peter , Goncharov Sergey , Khoussainov Bakhadyr , Shore Richard A.
Published: May 2006

Effective model theory is the subject that analyzes the typical notions and results of model theory to determine their effective content and counterparts. The subject has been developed both in the former Soviet Union and in the west with various names (recursive model theory, constructive model theory, etc.) and divergent terminology. (We use “effective model theory” as the most general and descriptive designation. Harizanov [6] is an excellent introduction to the subject as is Millar [13].) The basic subjects of model theory include languages, structures, theories, models and various types of maps between these objects. There are many ways to introduce considerations of effectiveness into the area. The two most prominent derive from starting, on the one hand, with the notion of a theory and its models or, on the other, with just structures.

If one begins with theories, then a natural version of effectiveness is to consider decidable theories (i.e., ones with a decidable (equivalently, computable or recursive) set of theorems). When one moves to models and wants them to be effective, one might start with the requirement that the model (of any theory) have a decidable theory (i.e., Th (), the set of sentences true in , is decidable). Typically, however, one wants to be able to talk about the elements of the model as well as its theory in the given language. Thus one naturally considers the model as a structure for the language expanded by adding a constant ai, for each element ai of . Of course, one requires that the mapping from the constants to the corresponding elements of be effective (computable). We are thus lead to the following basic definition:

A structure or model is decidable if there is a computable enumeration ai of A, the domain of , such that Th(, ai,) is decidable. (Of course, ai, is interpreted as ai, for each i Є ω.)
Lowness for the class of random sets
Authors: Kučera Antonín , Terwijn Sebastiaan A.
Published: May 2006

A positive answer to a question of M. van Lambalgen and D. Zambella whether there exist nonrecursive sets that are low for the class of random sets is obtained. Here a set A is low for the class RAND of random sets if RAND = RANDA.
Solving Pell equations locally in models of IΔ0
Authors: D'Aquino Paola
Published: May 2006

In [4] it is shown that only using exponentiation can one prove the existence of non trivial solutions of Pell equations in IΔ0. However, in this paper we will prove that any Pell equation has a non trivial solution modulo m for every m in IΔ0.
Paires de structures O-minimales
Authors: Baisalov Yerzhan , Poizat Bruno
Published: May 2006

Ni montras propecon de eljeteco de la kvantoro (∃y ∈ M) pri la (sufice) belaj paroj de modeloj de una O-plimalpova teorio. Gi havas korolaron ke, se ni aldonas malkavajn unarajn predikatojn a la lingvo de kelka O-plimalpova strukturo, ni ricevas malforte O-plimalpovan strukturon. Tui ci rezultato estis en speciala kaso pruvita de [5], kaj la gia generalizeco estis anoncita en [1].
Continuum cardinals generalized to Boolean algebras
Authors: Monk J. Donald
Published: May 2006

A number of specific cardinal numbers have been defined in terms of /fin or ωω. Some have been generalized to higher cardinals, and some even to arbitrary Boolean algebras. Here we study eight of these cardinals, defining their generalizations to higher cardinals, and then defining them for Boolean algebras. We then attempt to completely describe their relationships within each of several important classes of Boolean algebras.

The generalizations to higher cardinals might involve several cardinals instead of just one as in the case of ω, For example, the number a associated with maximal almost disjoint families of infinite sets of integers can be generalized to talk about maximal subsets of [κ]μ subject to the pairwise intersections having size less than ν. (For this multiple generalization of . see Monk [2001].) For brevity we do not consider such generalizations, restricting ourselves to just one cardinal. The set-theoretic generalizations then associate with each infinite cardinal κ some other cardinal λ, defined as the minimum of cardinals with a certain property.

The generalizations to Boolean algebras assign to each Boolean algebra some cardinal λ, also defined as the minimum of cardinals with a certain property.

For the theory of the original “continuum” cardinal numbers, see Douwen [1984]. Balcar and Simon [1989]. and Vaughan [1990].

I am grateful to Mati Rubin for some conversations concerning these functions for superatomic algebras, and to Bohuslav Balcar for information concerning the function h.

The notation for set theory is standard. For Boolean algebras we follow Koppelberg [1989], but recall at the appropriate place any somewhat unusual notation.
Some dichotomy theorems for isomorphism relations of countable models
Authors: Gao Su
Published: May 2006

Strengthening known instances of Vaught Conjecture, we prove the Glimm-Effros dichotomy theorems for countable linear orderings and for simple trees. Corollaries of the theorems answer some open questions of Friedman and Stanley in an Lω1ω-interpretability theory. We also give a survey of this theory.
Computable Boolean algebras
Authors: Knight Julia F. , Stob Michael
Published: May 2006

Feiner [F] showed that a Boolean algebra need not have a computable copy (see also [T2]). Downey and Jockusch [D-J] showed that every low Boolean algebra does have a computable copy. Thurber [T3], showed that every low2 Boolean algebra has a computable copy. Here we show that every Boolean algebra which is low3, or even low4, has a computable copy.

The results of [D-J] and [T3] were obtained by passing to linear orderings. In [D-J], there is an embedding theorem saying that any linear ordering which is with the successor relation as an added predicate can be embedded in a slightly larger linear ordering which is computable. An isomorphism theorem of Remmel [R] is used to show that the interval algebras of the two linear orderings are isomorphic (except in a trivial case). In [T3], there is an embedding theorem saying that any linear ordering which is with certain added predicates can be embedded in one which is with successor. Again the isomorphism theorem of Remmel is used to show that the interval algebras are isomorphic (except in a trivial case).

Here, instead of passing to linear orderings, we work directly with Boolean algebras. We begin with a review of the known results. We re-formulate the embedding theorems of Downey-Jockusch and Thurber in terms of Boolean algebras. We extract from Remmel's isomorphism theorem some information on complexity. In this way, we show that a low Boolean algebra is isomorphic to a computable one by an isomorphism which is , at worst, and the same is true for a low2 Boolean algebra.
Number of variables is equivalent to space
Authors: Immerman Neil , Buss Jonathan F. , Barrington David A. Mix
Published: May 2006

We prove that the set of properties describable by a uniform sequence of first-order sentences using at most k + 1 distinct variables is exactly equal to the set of properties checkable by a Turing machine in DSPACE[nk] (where n is the size of the universe). This set is also equal to the set of properties describable using an iterative definition for a finite set of relations of arity k. This is a refinement of the theorem PSPACE = VAR[O[1]] [8]. We suggest some directions for exploiting this result to derive trade-offs between the number of variables and the quantifier depth in descriptive complexity.
On computable automorphisms of the rational numbers
Authors: Morozov A. S. , Truss J. K.
Published: May 2006

The relationship between ideals I of Turing degrees and groups of I-recursive automorphisms of the ordering on rationals is studied. We discuss the differences between such groups and the group of all automorphisms, prove that the isomorphism type of such a group completely defines the ideal I, and outline a general correspondence between principal ideals of Turing degrees and the first-order properties of such groups.
The Escalation of Great Power Militarized Disputes: Testing Rational Deterrence Theory and Structural Realism
Authors: Huth Paul , Gelpi Christopher , Bennett D. Scott
Published: May 2006

Realism has been the dominant paradigm in the study of international conflict. Within this paradigm, two leading alternative approaches have been deterrence theory and structural realism. We test the relative explanatory power of these two theoretical approaches on the escalation of deterrence encounters among great powers from 1816 to 1984. We derive a set of hypotheses from each model, operationalize them for systematic empirical analysis, and test the hypotheses on 97 cases of great-power deterrence encounters by means of probit analysis. The results are that the hypotheses derived from deterrence theory receive considerable support, whereas none of the hypotheses derived from structural realism are supported.
The Destruction of Issue Monopolies in Congress
Authors: Jones Bryan D. , Baumgartner Frank R. , Talbert Jeffery C.
Published: May 2006

Scholars studying congressional committees have noted the potential for members to seek membership on particular committees, leading to bias. Underpinning this line of scholarship is what might be termed a theory of comparative committee statics, characterized by a cross-sectional empirical approach. We present a new approach that focuses on the dynamics of jurisdictional control. By following a series of issues through the committee hearing process, we show that there is indeed significant issue bias in particular committee venues. However, we also find that new committees often claim jurisdiction over issues as they are redefined in the political process. The degree of jurisdictional monopoly enjoyed by different committees has been overlooked in the literature on this topic in spite of its importance in determining the nature of representation of interests in Congress.
Scientific Research and State Government
Authors: White L. D.
Published: May 2006

The operation of the newly devised systems of centralized control in state government has naturally raised many questions of the relative duties and responsibilities of department and bureau officials on the one hand and of the supervising and controlling authorities on the other. The process of change from an established method of conducting public business to another, based on different principles and requiring new obligations on the part of officers expending money is bound to be a period of readjustment accompanied by a certain amount of friction. This will be the more certain as the new system differs more widely from the old and restricts more completely the freedom of action formerly reserved to heads of the various state services.

The establishment of the state board of public affairs in Wisconsin in 1911, the enactment of the Civil Code in Illinois in 1917, the enactment of the Ohio Civil Code in 1921, and the legislation of Massachusetts culminating in the creation of the board of administration and finance, all made wide departures from the system of administration hitherto in operation. The essential characteristic introduced in each case was the imposition of an agency of review, of supervision, and in many respects of control upon officers and commissions who had hitherto conducted the work of their respective offices for the most part subject only to the necessity of securing approval of their expenditures by the auditor or controller.
Incomplete Information and Ideological Explanations of Platform Divergence
Authors: Morton Rebecca B.
Published: May 2006

One of the paradoxes of formal spatial voting models is the robustness of the theoretical result that candidates will converge toward centrists positions and the empirical observation of persistent policy divergence of candidates. A solution is that candidates are ideological (have policy preferences). When candidates have policy preferences and incomplete information about voter preferences, then platform divergence is theoretically predicted. Experimental tests of the ideological model are presented. It is shown that platform divergence is significant when candidates are ideological and have incomplete information about voter preferences. However, candidate positions are more convergent, on average, than the theory predicts, suggesting that subjects value winning independently of the expected payment.
Public Sphere, Postmodernism and Polemic
Authors: Johnson James , Villa Dana R.
Published: May 2006

Theories of the public sphere, as standardly formulated, aim to specify the minimal, necessary conditions for a discursive realm free of coercion or manipulation. In his article in this Review in September 1992, Dana Villa urged us to reconsider this standard account. He argued that when read in light of postmodernist theory, Hannah Arendt provides the basis for a revised conception of the public sphere that privileges plurality and difference over consensus. Jim Johnson suggests that Villa's analysis is a thinly veiled polemic against critical theory. Johnson argues that, as critique, Villa's argument is neither decisive nor encompassing, and that as polemic it blinds Villa to potentially fruitful disagreements with critical theorists. Villa replies that Johnson misses the synthetic thrust of the original article because he identified public realm theory too narrowly with Habermas. Thus, he misconstrues the dialogue Villa sought to facilitate between Arendt and postmodernism.
Social Choice in a Representative Democracy
Authors: Benoît Jean-Pierre , Kornhauser Lewis A.
Published: May 2006

Citizens of a representative democracy are twice removed from legislation. First, they do not deliberate and vote directly on legislation. Rather they elect assemblies that enact such legislation in their stead. Second, and less commonly remarked, citizens do not vote directly for assemblies. Rather they vote for individual candidates, with the candidates receiving the most votes elected. We examine the efficiency properties of these voting systems.
The European Parliament as a Conditional Agenda Setter: What Are the Conditions? A Critique of Tsebelis (1994)
Authors: Moser Peter
Published: May 2006

Tsebelis (1994) argues in the American Political Science Review that the European Parliament has important power due to its right as a conditional agenda setter. I claim that Tsebelis' argument is based either on an incomplete analysis or on inaccurately specified decision rules. An accurate modeling of the cooperation procedure as stated in Article 189c of the Treaty of the European Community and as applied in practice changes the results considerably. Based on such a model, I provide an explanation of why the European Parliament sometimes can make successful amendments.
The Gains Debate: Framing State Choice
Authors: Berejekian Jeffrey
Published: May 2006

The theoretical bifurcation of international relations theory into (neo)realist and (neo)liberal camps has resulted in a “gains debate” that says little about an empirical world in which states exhibit both relative and absolute gains pursuit. This article deploys prospect theory in an attempt to move beyond the gains debate. The intent here is synthetic. By bringing the predictions of both perspectives under a single theoretical umbrella, we can model a broader set of state behavior. The thesis developed demonstrates that states in a gains frame pursue absolute gains and are risk averse, while states in a losses frame pursue relative gains and are risk acceptant. This hypothesis is assessed against the behavior of the European Community in the formation of the Montreal Protocol, a regime intended to protect the earth's protective ozone shield. The new model accurately predicts the timing and content of shifts in EC preferences, suggesting that a synthesis of realist and liberal approaches is possible.
Political Institutions and Satisfaction with Democracy: A Cross-National Analysis of Consensus and Majoritarian Systems
Authors: Anderson Christopher J. , Guillory Christine A.
Published: May 2006

Do political institutions affect citizen satisfaction with democracy? If so, how? Using cross-sectional survey data for eleven European democracies together with data on the type of democracy in which individuals live, we demonstrate that the nature of representative democratic institutions (measured by Arend Lijphart's consensus-majority index of democracies) mediates the relationship between a person's status as part of the political minority or majority and his or her satisfaction with the way the system works. Specifically, we find that (1) the losers of democratic competition show lower levels of satisfaction than do those in the majority and (2) losers in systems that are more consensual display higher levels of satisfaction with the way democracy works than do losers in systems with majoritarian characteristics. Conversely, winners tend to be more satisfied with democracy the more a country's political institutions approximate pure majoritarian government.