bluuebunny/crossref_metadata_2025 huggingface dataset:
A sheaf representation and duality for finitely presented Heyting algebras
Authors: Ghilardi Silvio , Zawadowski Marek
Published: May 2006

A. M.Pitts in [Pi] proved that is a bi-Heyting category satisfying the Lawvere condition. We show that the embedding Φ: → Sh(P0, J0) into the topos of sheaves, (P0 is the category of finite rooted posets and open maps, J0 the canonical topology on P0) given by H ↦ HA(H, (−)) : P0 → Set preserves the structure mentioned above, finite coproducts, and subobject classifier; it is also conservative. This whole structure on can be derived from that of Sh(P0, J0) via the embedding Φ. We also show that the equivalence relations in are not effective in general. On the way to these results we establish a new kind of duality between and a category of sheaves equipped with certain structure defined in terms of Ehrenfeucht games. Our methods are model-theoretic and combinatorial as opposed to proof-theoretic as in [Pi].
A model in which every Boolean algebra has many subalgebras
Authors: Cummings James , Shelah Saharon
Published: May 2006

We show that it is consistent with ZFC (relative to large cardinals) that every infinite Boolean algebraBhas an irredundant subsetAsuch that 2∣A∣= 2∣B∣. This implies in particular thatBhas 2∣B∣subalgebras. We also discuss some more general problems about subalgebras and free subsets of an algebra.

The result on the number of subalgebras in a Boolean algebra solves a question of Monk from [6]. The paper is intended to be accessible as far as possible to a general audience, in particular we have confined the more technical material to a “black box” at the end. The proof involves a variation on Foreman and Woodin's model in which GCH fails everywhere.
The hierarchy theorem for generalized quantifiers
Authors: Hella Lauri , Luosto Kerkko , Väänänen Jouko
Published: May 2006

The concept of a generalized quantifier of a given similarity type was defined in [12]. Our main result says that on finite structures different similarity types give rise to different classes of generalized quantifiers. More exactly, for every similarity typetthere is a generalized quantifier of typetwhich is not definable in the extension of first order logic by all generalized quantifiers of type smaller thant. This was proved for unary similarity types by Per Lindström [17] with a counting argument. We extend his method to arbitrary similarity types.
Fibred semantics and the weaving of logics. Part 1: Modal and intuitionistic logics
Authors: Gabbay D. M.
Published: May 2006

This is Part 1 of a paper on fibred semantics and combination of logics. It aims to present a methodology for combining arbitrary logical systemsLi,i∈I, to form a new systemLI. The methodology ‘fibres’ the semanticsiofLiinto a semantics forLI, and ‘weaves’ the proof theory (axiomatics) ofLiinto a proof system ofLI. There are various ways of doing this, we distinguish by different names such as ‘fibring’, ‘dovetailing’ etc, yielding different systems, denoted byetc. Once the logics are ‘weaved’, further ‘interaction’ axioms can be geometrically motivated and added, and then systematically studied. The methodology is general and is applied to modal and intuitionistic logics as well as to general algebraic logics. We obtain general results on bulk, in the sense that we develop standard combining techniques and refinements which can be applied to any family of initial logics to obtain further combined logics.

The main results of this paper is a construction for combining arbitrary, (possibly not normal) modal or intermediate logics, each complete for a class of (not necessarily frame) Kripke models. We show transfer of recursive axiomatisability, decidability and finite model property.

Some results on combining logics (normal modal extensions ofK) have recently been introduced by Kracht and Wolter, Goranko and Passy and by Fine and Schurz as well as a multitude of special combined systems existing in the literature of the past 20–30 years. We hope our methodology will help organise the field systematically.
Uniformization, choice functions and well orders in the class of trees
Authors: Lifsches Shmuel , Shelah Saharon
Published: May 2006

The monadic second-order theory of trees allows quantification over elements and over arbitrary subsets. We classify the class of trees with respect to the question: does a tree T have a definable choice function (by a monadic formula with parameters)? A natural dichotomy arises where the trees that fall in the first class don't have a definable choice function and the trees in the second class have even a definable well ordering of their elements. This has a close connection to the uniformization problem.
A geometric proof of the completeness of the Łukasiewicz calculus
Authors: Panti Giovanni
Published: May 2006

We give a self-contained geometric proof of the completeness theorem for the infinite-valued sentential calculus of Łukasiewicz.
A star-free semantics for R
Authors: Mares Edwin D.
Published: May 2006

The purpose of this paper is to show that semantics for relevance logic, based on the Routley-Meyer semantics, can be given without using the Routley star operator to treat negation. In the resulting semantics, negation is treated implicationally. It is shown that, by the use of restrictions on the ternary accessibility relation, simplified by the use of some definitions, a semantics can be stipulated over which R is complete.
The undecidability of the Π4-theory for the r.e. wtt and Turing degrees
Authors: Lempp Steffen , Nies André
Published: May 2006

We show that the Π4-theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters.
More about relatively lawless sequences
Authors: Moschovakis Joan Rand
Published: May 2006

In the author's Relative lawlessness in intuitionistic analysis [this Journal, vol. 52 (1987), pp. 68–88] and An intuitionistic theory of lawlike, choice and lawless sequences [Logic Colloquium ’90, Springer-Verlag, Berlin, 1993, pp. 191–209] a notion of lawlessness relative to a countable information base was developed for classical and intuitionistic analysis. Here we simplify the predictability property characterizing relatively lawless sequences and derive it from the new axiom of closed data (classically equivalent to open data) together with a natural principle of invariance under finite translation. We characterize relative lawlessness in terms of a notion of forcing. Finally, we study relative lawlessness on an arbitrary fan and show that the collection of lawless binary sequences (which is comeager in the sense of Baire) has probability measure zero. The reasoning is predominantly constructive.
Finitely axiomatizable ℵ1categorical theories
Authors: Hrushovski Ehud
Published: May 2006

Finitely axiomatizable ℵ1categorical theories are locally modular.
Chains and antichains in interval algebras
Authors: Bekkali M.
Published: May 2006

Let κ be a regular cardinal, and let B be a subalgebra of an interval algebra of size κ. The existence of a chain or an antichain of size κ in ℬ is due to M. Rubin (see [7]). We show that if the density of B is countable, then the same conclusion holds without this assumption on κ. Next we also show that this is the best possible result by showing that it is consistent with 2ℵ0 = ℵω1 that there is a boolean algebra B of size ℵω1 such that length(B) = ℵω1 is not attained and the incomparability of B is less than ℵω1. Notice that B is a subalgebra of an interval algebra. For more on chains and antichains in boolean algebras see. e.g., [1] and [2].
Almost weakly 2-generic sets
Authors: Fenner Stephen A.
Published: May 2006

There is a family of questions in relativized complexity theory—weak analogs of the Friedberg Jump-Inversion Theorem—that are resolved by 1-generic sets but which cannot be resolved by essentially any weaker notion of genericity. This paper defines aw2-generic sets, i.e., sets which meet every dense set of strings that is re. in some incomplete r.e. set. Aw2-generic sets are very close to 1-generic sets in strength, but are too weak to resolve these questions. In particular, it is shown that for any set X there is an aw2-generic set G such that NPG ∩ co-NPG ⊈ PG⊕x. (On the other hand, if G is 1-generic, then NPG ∩ co-NPG ⊆ PG⊕SAT, where SAT is the NP-complete satisfiability problem [6].) This result runs counter to the fact that most finite extension constructions in complexity theory can be made effective. These results imply that any finite extension construction that ensures any of the Friedberg analogs must be noneffective, even relative to an arbitrary incomplete r.e. set. It is then shown that the recursion theoretic properties of aw2-generic sets differ radically from those of 1-generic sets: every degree above 0′ contains an aw2-generic set: no aw2-generic set exists below any incomplete r.e. set: there is an aw2-generic set which is the join of two Turing equivalent aw2-generic sets. Finally, a result of Shore is presented [30] which states that every degree above 0′ is the jump of an aw2-generic degree.
Undecidable relativizations of algebras of relations
Authors: Mikulás Szabolcs , Marx Maarten
Published: May 2006

In this paper we show that relativized versions of relation set algebras and cylindric set algebras have undecidable equational theories if we include coordinatewise versions of the counting operations into the similarity type. We apply these results to the guarded fragment of first-order logic.
Stabilité polynômiale des corps différentiels
Authors: Portier Natacha
Published: May 2006

A notion of complexity for an arbitrary structure was defined in the book of Poizat Les petits cailloux (1995): we can define P and NP problems over a differential field K. Using the Witness Theorem of Blum et al., we prove the P-stability of the theory of differential fields: a P problem over a differential field K is still P when restricts to a sub-differential field k of K. As a consequence, if P = NP over some differentially closed field K, then P = NP over any differentially closed field and over any algebraically closed field.
The complexity of ODDnA
Authors: Beigel Richard , Gasarch William , Kummer Martin , Martin Georgia , Mcnicholl Timothy , Stephan Frank
Published: May 2006

For a fixed set A. the number of queries to A needed in order to decide a set S is a measure of S's complexity. We consider the complexity of certain sets defined in terms of A:

and, for m > 2,

where #nA. (x1….. xn) = A(x1) + A(xn)(We identify with , where χA is the characteristic function of A.)

If A is a nonrecursive semirecursive set or if A is a jump, we give tight bounds on the number of queries needed in order to decide ODDnA and MODmnA:

• ODDnA can be decided with n parallel queries to A, but not with n − 1.

• ODDnA can be decided with ⌈log(n + 1)⌉ sequential queries to A but not with ⌈log(n + 1)⌉ − 1.

• MODmnA can be decided with ⌈n/m⌉ + ⌊n/m⌋ parallel queries to A but not with ⌈n/m⌉ + ⌊n/m⌋ − 1.

• MODmnA can be decided with ⌈log(⌈n/m⌉ + ⌊n/m⌋ + 1)⌉ sequential queries to A but not with ⌈log(⌈n/m⌉ + ⌊n/m⌋ + 1)⌉ − 1.

The lower bounds above hold for nonrecursive recursively enumerable sets A as well. (Interestingly, the lower bounds for recursively enumerable sets follow by a general result from the lower bounds for semirecursive sets.)

In particular, every nonzero truth-table degree contains a set A such that ODDnA cannot be decided with n − 1 parallel queries to A. Since every truth-table degree also contains a set B such that ODDnB can be decided with one query to B, a set's query complexity depends more on its structure than on its degree.

For a fixed set A,

Q(n, A) = {S: S can be decided with n sequential queries to A}.

Q∥ (n, A) = {S : S can be decided with n parallel queries to A}.

We show that if A is semirecursive or recursively enumerable, but is not recursive, then these classes form non-collapsing hierarchies:

• Q(0,A) ⊂ Q (1, A) ⊂ Q(2, A) ⊂ …

Q∥ (0, A) ⊂ Q∥ (1, A) ⊂ Q∥ (2, A) ⊂ …

The same is true if A is a jump.
Vaught's conjecture for modules over a serial ring
Authors: Puninskaya Vera
Published: May 2006

It is proved that Vaught's conjecture is true for modules over an arbitrary countable serial ring. It follows from the structural result that every module with few models over a (countable) serial ring is ω-stable.
A note onCM-triviality and the geometry of forking
Authors: Pillay Anand
Published: May 2006

CM-triviality of a stable theory is a notion introduced by Hrushovski [1]. The importance of this property is first that it holds of Hrushovski's new non 1-based strongly minimal sets, and second that it is still quite a restrictive property, and forbids the existence of definable fields or simple groups (see [2]). In [5], Frank Wagner posed some questions aboutCM-triviality, asking in particular whether a structure of finite rank, which is “coordinatized” byCM-trivial types of rank 1, is itselfCM-trivial. (Actually Wagner worked in a slightly more general context, adapting the definitions to a certain “local” framework, in which algebraic closure is replaced byP-closure, forPsome family of types. We will, however, remain in the standard context, and will just remark here that it is routine to translate our results into Wagner's framework, as well as to generalise to the superstable theory/regular type context.) In any case we answer Wagner's question positively. Also in an attempt to put forward some concrete conjectures about the possible geometries of strongly minimal sets (or stable theories) we tentatively suggest a hierarchy of geometric properties of forking, the first two levels of which correspond to 1-basedness andCM-triviality respectively. We do not know whether this is a strict hierarchy (or even whether these are the “right” notions), but we conjecture that it is, and moreover that a counterexample to Cherlin's conjecture can be found at level three in the hierarchy.
Infinite time Turing machines
Authors: Hamkins Joel David , Lewis Andy
Published: May 2006

We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. Everyset. for example, is decidable by such machines, and the semi-decidable sets form a portion of thesets. Our oracle concept leads to a notion of relative computability for sets of reals and a rich degree structure, stratified by two natural jump operators.
A note on the model theory of generalized polygons
Authors: Tent Katrin
Published: May 2006

Using projectivity groups, we classify some polygons with strongly minimal point rows and show in particular that no infinite quadrangle can have sharply 2-transitive projectivity groups in which the point stabilizers are abelian. In fact, we characterize the finite orthogonal quadranglesQ(4,2).Q−(5.2) andQ(4,3) by this property. Finally we show that the sets of points, lines and flags of any ℵ1-categorical polygon have Morley degree 1.
On fixed-point logic with counting
Authors: Flum Jörg , Grohe Martin
Published: May 2006

One of the fundamental results of descriptive complexity theory, due to Immerman [13] and Vardi [18], says that a class of ordered finite structures is definable in fixed-point logic if, and only if, it is computable in polynomial time. Much effort has been spent on the problem of capturing polynomial time, that is, describing all polynomial time computable classes of not necessarily ordered finite structures by a logic in a similar way.

The most obvious shortcoming of fixed-point logic itself on unordered structures is that it cannot count. Immerman [14] responded to this by adding counting constructs to fixed-point logic. Although it has been proved by Cai, Fürer, and Immerman [1] that the resulting fixed-point logic with counting, denoted by IFP+C, still does not capture all of polynomial time, it does capture polynomial time on several important classes of structures (on trees, planar graphs, structures of bounded tree-width [15, 9, 10]).

The main motivation for such capturing results is that they may give a better understanding of polynomial time. But of course this requires that the logical side is well understood. We hope that our analysis of IFP+C-formulas will help to clarify the expressive power of IFP+C; in particular, we derive a normal form. Moreover, we obtain a problem complete for IFP+C under first-order reductions.
Jónsson cardinals, Erdős cardinals, and the core model
Authors: Mitchell W. J.
Published: May 2006

We show that if there is no inner model with a Woodin cardinal and the Steel core model K exists, then every Jónsson cardinal is Ramsey in K, and every δ-Jónsson cardinal is δ5-Erdős in K.

In the absence of the Steel core model K we prove the same conclusion for any model L[] such that either V = L[] is the minimal model for a Woodin cardinal, or there is no inner model with a Woodin cardinal and V is a generic extension of L[].

The proof includes one lemma of independent interest: If V = L[A], where A ⊂ κ and κ is regular, then Lκ[A] is a Jónsson algebra. The proof of this result. Lemma 2.5, is very short and entirely elementary.
Forking and fundamental order in simple theories
Authors: Lascar Daniel , Pillay Anand
Published: May 2006

We give a characterisation of forking in the context of simple theories in terms of the fundamental order.
How is it that infinitary methods can be applied to finitary mathematics? Gödel's T: a case study
Authors: Weiermann Andreas
Published: May 2006

Inspired by Pohlers' local predicativity approach to Pure Proof Theory and Howard's ordinal analysis of bar recursion of type zero we present a short, technically smooth and constructive strong normalization proof for Gödel's system T of primitive recursive functionals of finite types by constructing an ε0-recursive function []0: T → ω so that a reduces to b implies [a]0 > [b]0. The construction of [ ]0 is based on a careful analysis of the Howard-Schütte treatment of Gödel's T and utilizes the collapsing function ψ: ε0 → ω which has been developed by the author for a local predicativity style proof-theoretic analysis of PA. The construction of [ ]0 is also crucially based on ideas developed in the 1995 paper “A proof of strongly uniform termination for Gödel's T by the method of local predicativity” by the author. The results on complexity bounds for the fragments of T which are obtained in this paper strengthen considerably the results of the 1995 paper.

Indeed, for given n let Tn be the subsystem of T in which the recursors have type level less than or equal to n + 2. (By definition, case distinction functionals for every type are also contained in Tn.) As a corollary of the main theorem of this paper we obtain (reobtain?) optimal bounds for the Tn-derivation lengths in terms of ω+2-descent recursive functions. The derivation lengths of type one functionals from Tn (hence also their computational complexities) are classified optimally in terms of <ωn+2 -descent recursive functions.

In particular we obtain (reobtain?) that the derivation lengths function of a type one functional a ∈ T0 is primitive recursive, thus any type one functional a in T0 defines a primitive recursive function. Similarly we also obtain (reobtain?) a full classification of T1 in terms of multiple recursion.

As proof-theoretic corollaries we reobtain the classification of the IΣn+1-provably recursive functions. Taking advantage from our finitistic and constructive treatment of the terms of Gödel's T we reobtain additionally (without employing continuous cut elimination techniques) that PRA + PRWO(ε0) ⊢ Π20 − Refl(PA) and PRA + PRWO(ωn+2) ⊢ Π20 − Refl(IΣn+1), hence PRA + PRWO(ε0) ⊢ Con(PA) and PRA + PRWO(ωn+2) ⊢ Con(IΣn+1).

For programmatic reasons we outline in the introduction a vision of how to apply a certain type of infinitary methods to questions of finitary mathematics and recursion theory. We also indicate some connections between ordinals, term rewriting, recursion theory and computational complexity.
Basic logic: reflection, symmetry, visibility
Authors: Sambin Giovanni , Battilotti Giulia , Faggian Claudia
Published: May 2006

We introduce a sequent calculusBfor a new logic, named basic logic. The aim of basic logic is to find a structure in the space of logics. Classical, intuitionistic. quantum and non-modal linear logics, are all obtained as extensions in a uniform way and in a single framework. We isolate three properties, which characterizeBpositively: reflection, symmetry and visibility.

A logical constant obeys to the principle of reflection if it is characterized semantically by an equation binding it with a metalinguistic link between assertions, and if its syntactic inference rules are obtained by solving that equation. All connectives of basic logic satisfy reflection.

To the control of weakening and contraction of linear logic, basic logic adds a strict control of contexts, by requiring that all active formulae in all rules are isolated, that is visible. From visibility, cut-elimination follows. The full, geometric symmetry of basic logic induces known symmetries of its extensions, and adds a symmetry among them, producing the structure of a cube.
Hierarchies of monadic generalized quantifiers
Authors: Luosto Kerkko
Published: May 2006

A combinatorial criterium is given when a monadic quantifier is expressible by means of universe-independent monadic quantifiers of width n. It is proved that the corresponding hierarchy does not collapse. As an application, it is shown that the second resumption (or vectorization) of the Härtig quantifier is not definable by monadic quantifiers. The techniques rely on Ramsey theory.
On central extensions of algebraic groups
Authors: Altinel Tuna , Cherlin Gregory
Published: May 2006

In this paper the following theorem is proved regarding groups of finite Morley rank which are perfect central extensions of quasisimple algebraic groups.

Theorem1.Let G be a perfect group of finite Morley rank and let C0be a definable central subgroup of G such that G/C0is a universal linear algebraic group over an algebraically closed field; that is G is a perfect central extension of finite Morley rank of a universal linear algebraic group. Then C0= 1.

Contrary to an impression which exists in some circles, the center of the universal extension of a simple algebraic group, as an abstract group, is not finite in general. Thus the finite Morley rank assumption cannot be omitted.

Corollary1.Let G be a perfect group of finite Morley rank such that G/Z(G) is a quasisimple algebraic group. Then G is an algebraic group. In particular, Z(G) is finite([4],Section27.5).

An understanding of central extensions of quasisimple linear algebraic groups which are groups of finite Morley rank is necessary for the classification oftamesimpleK*-groupsof finite Morley rank, which constitutes an approach to the Cherlin-Zil’ber conjecture. For this reason the theorem above and its corollary were proven in [1] (Theorems 4.1 and 4.2) under the assumption oftameness, which simplifies the argument considerably. The result of the present paper shows that this assumption can be dropped. The main line of argument is parallel to that in [1]; the absence of the tameness assumption will be countered by a model-theoretic result and results fromK-theory. The model-theoretic result places limitations on definability in stable fields, and may possibly be relevant to eliminating certain other uses of tameness.
Successive weakly compact or singular cardinals
Authors: Schindler Ralf-Dieter
Published: May 2006

It is shown in ZF that if δ < δ+ < Ω are such that δ and δ+ are either both weakly compact or singular cardinals and Ω is large enough for putting the core model apparatus into action then there is an inner model with a Woodin cardinal.
Similar but not the same: various versions of ♣ do not coincide
Authors: Džamonja Mirna , Shelah Saharon
Published: May 2006

We consider various versions of the ♣ principle. This principle is a known consequence of ◊. It is well known that ◊ is not sensitive to minor changes in its definition, e.g., changing the guessing requirement form “guessing exactly” to “guessing modulo a finite set”. We show however, that this is not true for ♣. We consider some other variants of ♣ as well.
Separation and Weak König's Lemma
Authors: Humphreys A. James , Simpson Stephen G.
Published: May 2006

We continue the work of [14, 3, 1, 19, 16, 4, 12, 11, 20] investigating the strength of set existence axioms needed for separable Banach space theory. We show that the separation theorem for open convex sets is equivalent to WKL0 over RCA0. We show that the separation theorem for separably closed convex sets is equivalent to ACA0 over RCA0. Our strategy for proving these geometrical Hahn–Banach theorems is to reduce to the finite-dimensional case by means of a compactness argument.
Intuitionistic completeness for first order classical logic
Authors: Berardi Stefano
Published: May 2006

In the past sixty years or so, a real forest of intuitionistic models for classical theories has grown. In this paper we will compare intuitionistic models of first order classical theories according to relevant issues, like completeness (w.r.t. first order classical provability), consistency, and relationship between a connective and its interpretation in a model. We briefly consider also intuitionistic models for classical ω-logic.

All results included here, but a part of the proposition (a) below, are new. This work is, ideally, a continuation of a paper by McCarty, who considered intuitionistic completeness mostly for first order intuitionistic logic.
A model with no magic set
Authors: Ciesielski Krzysztof , Shelah Saharon
Published: May 2006

We will prove that there exists a model of ZFC+“c =” in which every M ⊆ ℝ of cardinality less than continuum c is meager, and such that for every X ⊆ ℝ of cardinality c there exists a continuous function f : ℝ → ℝ with f[X] = [0, 1].

In particular in this model there is no magic set, i.e., a set M ⊆ ℝ such that the equation f[M] = g[M] implies f = g for every continuous nowhere constant functions f,g: ℝ → ℝ.
Some two-cardinal results for O-minimal theories
Authors: Bays Timothy
Published: May 2006

We examine two-cardinal problems for the class of O-minimal theories. We prove that an O-minimal theory which admits some (κ, λ) must admit every (κ′, λ′). We also prove that every “reasonable” variant of Chang's Conjecture is true for O-minimal structures. Finally, we generalize these results from the two-cardinal case to the δ-cardinal case for arbitrary ordinals δ.
A strong version of Herbrand's theorem for introvert sentences
Authors: Langholm Tore
Published: May 2006

A version of Herbrand's theorem tells us that a universal sentence of a first-order language with at least one constant is satisfiable if and only if the conjunction of all its ground instances is. In general the set of such instances is infinite, and arbitrarily large finite subsets may have to be inspected in order to detect inconsistency. Essentially, the reason that every member of such an infinite set may potentially matter, can be traced back to sentences like

(1)

Loosely put, such sentences effectively sabotage any attempt to build a model from below in a finite number of steps, since new members of the Herbrand universe are constantly brought to attention. Since they cause an indefinite expansion of the relevant part of the Herbrand universe, such sentences could quite appropriately be called expanding.

When such sentences are banned, stronger versions of Herbrand's theorem can be stated. Define a clause (disjunction of literals) to be non-expanding if every non-ground term occurring in a positive literal also occurs (possibly as an embedded subterm) in a negative literal of the same clause. Written as a disjunction of literals, the matrix of (1) clearly fails this criterion. Moreover, say that a sentence is non-expanding if it is a universal sentence with a quantifier-free matrix that is a conjunction of non-expanding clauses. Such sentences do in a sense never reach out beyond themselves, and the relevant part of the Herbrand universe is therefore drastically reduced.
A many permutation group result for unstable theories
Authors: Schlatter Mark D.
Published: May 2006

We extend Shelah's first many model result to show that an unstable theory has 2κmany non-permutation group isomorphic models of size κ, where κ is an uncountable regular cardinal.
Minimal but not strongly minimal structures with arbitrary finite dimensions
Authors: Ikeda Koichiro
Published: May 2006

An infinite structure is said to be minimal if each of its definable subset is finite or cofinite. Modifying Hrushovski's method we construct minimal, non strongly minimal structures with arbitrary finite dimensions. This answers negatively to a problem posed by B. I Zilber.
Syntactical truth predicates for second order arithmetic
Authors: Colson Loïc , Grigorieff Serge
Published: May 2006

We introduce a notion ofsyntactical truth predicate(s.t.p.) for the second order arithmeticPA2. An s.t.p. is a setTof closed formulas such that:

(i)T(t=u) if and only if the closed first order termstanduare convertible, i.e., have the same value in the standard interpretation

(ii)T(A→B) if and only if (T(A) ⇒T(B))

(iii)T(∀xA) if and only if (T(A[x←t]) for any closed first order termt)

(iv)T(∀X A) if and only if (T(A[X← ∆]) for any closed set definition ∆ = {x∣D(x)}).

S.t.p.'s can be seen as a counterpart to Tarski's notion of (model-theoretical)validityand have main model properties. In particular, their existence is equivalent to the existence of anω-model ofPA2, this fact being provable inPA2with arithmetical comprehension only.
Modules with few types over a hereditary noetherian prime ring
Authors: Puninskaya Vera
Published: May 2006

It is proved that Vaught's conjecture is true for modules over an arbitrary countable hereditary noetherian prime ring.
The Jensen Covering Property
Authors: Schimmerling E. , Woodin W. H.
Published: May 2006

The Jensen covering lemma says that either L has a club class of indiscernibles, or else, for every uncountable set A of ordinals, there is a set B ∈ L with A ⊆ B and card (B) = card(A). One might hope to extend Jensen's covering lemma to richer core models, which for us will mean to inner models of the form L[] where is a coherent sequence of extenders of the kind studied in Mitchell-Steel [8], The papers [8], [12], [10] and [1] show how to construct core models with Woodin cardinals and more. But, as Prikry forcing shows, one cannot expect too direct a generalization of Jensen's covering lemma to core models with measurable cardinals.

Recall from [8] that if L[] is a core model and α is an ordinal, then either Eα = ∅, or else Eα is an extender over As in [8], we assume here that if Eα is an extender, then Eα is below superstrong type in the sense that the set of generators of Eα is bounded in (crit(Eα)). Let us say that L[] is a lower-part core model iff for every ordinal α, Eα is not a total extender over L[]. In other words, if L[] is a lower-part core model, then no cardinal in L[] is measurable as witnessed by an extender on . Other than the “below superstrong” hypothesis, we impose no bounds on the large cardinal axioms true in the levels of a lower-part core model.
Embedding finite lattices into the ideals of computably enumerable turing degrees
Authors: Calhoun William C. , Lerman Manuel
Published: May 2006

We show that the lattice L20 is not embeddable into the lattice of ideals of computably enumerable Turing degrees (ℐ), We define a structure called a pseudolattice that generalizes the notion of a lattice, and show that there is a Π2 necessary and sufficient condition for embedding a finite pseudolattice into ℐ.
Sequent calculus in natural deduction style
Authors: Negri Sara , von Plato Jan
Published: May 2006

A sequent calculus is given in which the management of weakening and contraction is organized as in natural deduction. The latter has no explicit weakening or contraction, but vacuous and multiple discharges in rules that discharge assumptions. A comparison to natural deduction is given through translation of derivations between the two systems. It is proved that if a cut formula is never principal in a derivation leading to the right premiss of cut, it is a subformula of the conclusion. Therefore it is sufficient to eliminate those cuts that correspond to detour and permutation conversions in natural deduction.
Definable sets in Boolean-ordered o-minimal structures. I
Authors: Newelski Ludomir , Wencel Roman
Published: May 2006

We prove weak elimination of imaginary elements for Boolean orderings with finitely many atoms. As a consequence we obtain equivalence of the two notions of o-minimality for Boolean ordered structures, introduced by C. Toffalori. We investigate atoms in Boolean algebras induced by algebraically closed subsets of Boolean ordered structures. We prove uniqueness of prime models in strongly o-minimal theories of Boolean ordered structures.
The classification of small types of rankω, Part I
Authors: Buechler Steven , Hoover Colleen
Published: May 2006

Certain basic concepts of geometrical stability theory are generalized to a class of closure operators containing algebraic closure. A specific case of a generalized closure operator is developed which is relevant to Vaught's conjecture. As an application of the methods, we prove

Theorem A.Let G be a superstate group of U-rankωsuch that the generics of G are locally modular andTh(G)has few countable models. Let G−be the group of nongeneric elements of G.G+=Go+G−.LetΠ = {q∈S(∅):U(q)<ω}.For any countable model M ofTh(G)there is a finite A⊂M such thai M is almost atomic over A∪ (G+∩M) ∪ ⋃p∈Πp(M).
Disquotational truth and analyticity
Authors: Halbach Volker
Published: May 2006

The uniform reflection principle for the theory of uniform T-sentences is added to PA. The resulting system is justified on the basis of a disquotationalist theory of truth where the provability predicate is conceived as a special kind of analyticity. The system is equivalent to the system ACA of arithmetical comprehension. If the truth predicate is also allowed to occur in the sentences that are inserted in the T-sentences. yet not in the scope of negation, the system with the reflection schema for these T-sentences assumes the strength of the Kripke-Feferman theory KF. and thus of ramified analysis up to ε0.
Some combinatorics of imperfect information
Authors: Cameron Peter , Hodges Wilfrid
Published: May 2006

We can use the compositional semantics of Hodges [9] to show that any compositional semantics for logics of imperfect information must obey certain constraints on the number of semantically inequivalent formulas. As a corollary, there is no compositional semantics for the ‘independence-friendly’ logic of Hintikka and Sandu (henceforth IF) in which the interpretation in a structure A of each 1 -ary formula is a subset of the domain of A (Corollary 6.2 below proves this and more). After a fashion, this rescues a claim of Hintikka and provides the proof which he lacked:

… there is no realistic hope of formulating compositional truth-conditions for [sentences of IF], even though I have not given a strict impossibility proof to that effect.

(Hintikka [6] page 110ff.) One curious spinoff is that there is a structure of cardinality 6 on which the logic of Hintikka and Sandu gives nearly eight million inequivalent formulas in one free variable (which is more than the population of Finland).

We thank the referee for a sensible change of notation, and Joel Berman and Stan Burris for bringing us up to date with the computation of Dedekind's function (see section 4). Our own calculations, utterly trivial by comparison, were done with Maple V.

The paper Hodges [9] (cf. [10]) gave a compositional semantics for a language with some devices of imperfect information. The language was complicated, because it allowed imperfect information both at quantifiers and at conjunctions and disjunctions.
Two variable first-order logic over ordered domains
Authors: Otto Martin
Published: May 2006

The satisfiability problem for the two-variable fragment of first-order logic is investigated over finite and infinite linearly ordered, respectively wellordered domains, as well as over finite and infinite domains in which one or several designated binary predicates are interpreted as arbitrary wellfounded relations.

It is shown that FO2 over ordered, respectively wellordered. domains or in the presence of one well-founded relation, is decidable for satisfiability as well as for finite satisfiability. Actually the complexity of these decision problems is essentially the same as for plain unconstrained FO2. namely non-deterministic exponential time.

In contrast FO2 becomes undecidable for satisfiability and for finite satisfiability, if a sufficiently large number of predicates are required to be interpreted as orderings. wellorderings. or as arbitrary wellfounded relations. This undecidability result also entails the undecidability of the natural common extension of FO2 and computation tree logic CTL.
The covering numbers of Mycielski ideals are all equal
Authors: Shelah Saharon , Steprāns Juris
Published: May 2006

The Mycielski idealis defined to consist of all setsA⊆ℕksuch that {f↾X:f∈A} ≠Xkfor all. It will be shown that the covering numbers for these ideals are all equal. However, the covering numbers of the closely associated Rosłanowski ideals will be shown to be consistently different.
Upper bounds for metapredicative Mahlo in explicit mathematics and admissible set theory
Authors: Jäger Gerhard , Strahm Thomas
Published: May 2006

In this article we introduce systems for metapredicative Mahlo in explicit mathematics and admissible set theory. The exact upper proof-theoretic bounds of these systems are established.
Existence of some sparse sets of nonstandard natural numbers
Authors: Jin Renling
Published: May 2006

Answers are given to two questions concerning the existence of some sparse subsets of ℋ = {0, 1 … ., H – 1} ⊆ *ℕ. where H is a hyperfinite integer. In §1. we answer a question of Kanovei by showing that for a given cut U in ℋ, there exists a countably determined set X ⊆ ℋ which contains exactly one element in each U-monad, if and only if U = a · ℕ for some a Є ℋ ∖ {0}. In §2, we deal with a question of Keisler and Leth in [6]. We show that there is a cut V ⊆ ℋ such that for any cut U, (i) there exists a U-discrete set X ⊆ ℋ with X + X = ℋ (mod H) provided , (ii) there does not exist any U-discrete set X ⊆ ℋ with X + X = ℋ (mod H) provided . We obtain some partial results for the case U = V.
Inconsistent models of arithmetic Part II: the general case
Authors: Priest Graham
Published: May 2006

The paper establishes the general structure of the inconsistent models of arithmetic of [7]. It is shown that such models are constituted by a sequence of nuclei. The nuclei fall into three segments: the first contains improper nuclei: the second contains proper nuclei with linear chromosomes: the third contains proper nuclei with cyclical chromosomes. The nuclei have periods which are inherited up the ordering. It is also shown that the improper nuclei can have the order type of any ordinal, of the rationals, or of any other order type that can be embedded in the rationals in a certain way.
All intermediate logics with extra axioms in one variable, except eight, are not strongly ω-complete
Authors: Fiorentini Camillo
Published: May 2006

In [8] it is proved that all the intermediate logics axiomatizable by formulas in one variable, except four of them, are not strongly complete. We considerably improve this result by showing that all the intermediate logics axiomatizable by formulas in one variable, except eight of them, are not strongly ω-complete. Thus, a definitive classification of such logics with respect to the notions of canonicity, strong completeness, ω-canonicity and strong ω-completeness is given.
Le problème des grandes puissances et celui des grandes racines
Authors: Portier Natacha
Published: May 2006

Soit f une fonction de N dans N qui ne soit pas calculable en temps polynomial, et a un élément d'un corps differentiel K de caractéristique nulle. Nous appelons probleme des grandes puissances l'ensembledes uples = (x1…..xn) de K telsque x1 = af(n) et problème des grandes racines l'ensemble des uples de K tels que . Ce sont deux exemples de problèmes que l'utilisation de la dérivée ne permet pas de résoudre plus rapidement. Nous montrons que le problème des grandes racines n'est pas polynomial au sens des corps differentiels, même si nous autorisons un nombre polynomial de paramètres. et que le problème des grandes puissances n'est pas polynomial au sens des corps differentiels. même au niveau non uniforme. Les démonstrations utilisent la stabilité polynomial de la théorie des corps de caractéristique nulle. montrée par L. Blum, F. dicker. M. Shub et S. Smale, ainsi que le lemme de réduction qui permet de ramener un polynôme differentiel des variables a un polynôme des variables et de leurs dérivées.
More on entangled orders
Authors: Shafir Ofer , Shelah Saharon
Published: May 2006

This paper grew as a continuation of [Sh462] but in the present form it can serve as a motivation for it as well. We deal with the same notions, all defined in 1.1, and use just one simple lemma from there whose statement and proof we repeat as 2.1. Originally entangledness was introduced, in [BoSh210] for example, in order to get narrow boolean algebras and examples of the nonmultiplicativity of c.c-ness. These applications became marginal when other methods were found and successfully applied (especially Todorčevic walks) but after the pcf constructions which made their début in [Sh-g] and were continued in [Sh462] it seems that this notion gained independence.

Generally we aim at characterizing the existence of strong and weak entangled orders in cardinal arithmetic terms. In [Sh462, §6] necessary conditions were shown for strong entangledness which in a previous version was erroneously proved to be equivalent to plain entangledness. In §1 we give a forcing counterexample to this equivalence and in §2 we get those results for entangledness (certainly the most interesting case). A new construction of an entangled order ends this section. In §3 we get weaker results for positively entangledness, especially when supplemented with the existence of a separating point (Definition 2.2). An antipodal case is defined in 3.10 and completely characterized in 3.11. Lastly we outline in 3.12 a forcing example showing that these two subcases of positive entangledness comprise no dichotomy. The work was done during the fall of 1994 and the winter of 1995. The second author proved Theorems 1.2, 2.14, the result that is mentioned in Remark 2.11 and what appears in this version as Theorem 2.10(a) with the further assumptionden(I)θ< μ. The first author is responsible for waving off this assumption (actually by showing that it holds in the general case), for Theorems 2.12 and 2.13 in Section 2 and for the work which is presented in Section 3.
The rise and fall of typed sentences
Authors: Crabbé Marcel
Published: May 2006

We characterize the 3-stratiflable theorems ofNFas a 3-stratifiable extension ofNF3: and show thatNFis equiconsistent withTTplus raising type axioms for sentences asserting the existence of some predicate over an atomic Boolean algebra.
Computational randomness and lowness
Authors: Terwijn Sebastiaan A. , Zambella Domenico
Published: May 2006

We prove that there are uncountably many sets that are low for the class of Schnorr random reals. We give a purely recursion theoretic characterization of these sets and show that they all have Turing degree incomparable to 0′. This contrasts with a result of Kučera and Terwijn [5] on sets that are low for the class of Martin-Löf random reals.
Government Partisanship, Labor Organization, and Macroeconomic Performance: A Corrigendum
Authors: Beck Nathaniel , Katz Jonathan N. , Alvarez R. Michael , Garrett Geoffrey , Lange Peter
Published: May 2006

Alvarez, Garrett and Lange (1991) used cross-national panel data on the Organization for Economic Coordination and Development nations to show that countries with left governments and encompassing labor movements enjoyed superior economic performance. Here we show that the standard errors reported in that article are incorrect. Reestimation of the model using ordinary least squares and robust standard errors upholds the major finding of Alvarez, Garrett and Lange, regarding the political and institutional causes of economic growth but leaves the findings for unemployment and inflation open to question. We show that the model used by Alvarez, Garrett and Lange, feasible generalized least squares, cannot produce standard errors when the number of countries analyzed exceeds the length of the time period under analysis. Also, we argue that ordinary least squares with robust standard errors is superior to feasible generalized least squares for typical cross-national panel studies.
Limitations on National Sovereignty in International Relations
Authors: Garner James W.
Published: May 2006

Among the traditional political conceptions which in recent years have become the object of almost irreverent attack, is that which ascribes the quality of absolutism to that often elusive, but ever present, double-faced creation of the jurists which bears the name of sovereignty. Text-writers, sometimes in unqualified terms, still persist in claiming for it the unrestricted supremacy which was attributed to it in an age when its wielders everywhere were absolute monarchs; but an increasing number, less influenced by legal theories than by realities, see in it only the “ghost of personal monarchy,” as Hobbes characterized it, “sitting crowned on the grave thereof.”

On the one side the attack is directed by a new school of political writers, who deny its very existence or maintain that it is not an essential constituent attribute of the state. According to them, the notion is useless if not fallacious; the theory is discredited by the facts of modern state life and the term should be abandoned and expunged from the literature of political science.
Central and Eastern Europe in 1924
Authors: Graham Malbone W.
Published: May 2006

A study of the political events of 1924 in Central and Eastern Europe reveals such a variety of topics lending themselves to extensive treatment that for convenience of treatment, the material has been grouped under the four main heads of (1) financial reconstruction, (2) constitutional, legislative, and administrative developments, (3) parties and politics, and (4) foreign relations.
The Doctrine of Power and Party Conflict
Authors: Catlin G. E. G.
Published: May 2006

The fundamental problem in politics is that of the balance of power. It is a balance which has to be struck not only in foreign affairs but, quite as much, in the domestic management of states. Only, it may be suggested, when real equilibrium has been secured, is that efficient, smooth and healthy working of the social system possible which finds external expression in a normal and resilient form of conservatism as distinct from the tetanus of the morbid and hysterical form. But it is futile to speak of striking a balance of social interests unless we are justified in supposing that the units have a certain constancy of characteristics and persistence of activity.

Now the units of social force are, in the last analysis, the so-called ‘free wills’ of the individuals necessarily brought into contact as component members of a society. The contact is necessary: civilization admits of no ‘wild ass freedom.’ To assert that these ‘persons with a will of their own’ behave in accordance not only with an ‘altruistic’ gregarious tendency but also with a differentiating, assertive tendency, is to make a psychological assumption. To affirm that this self-assertive tendency may perhaps be religiously sublimated but that it is under all circumstances inextinguishable, is to make another psychological assumption.