bluuebunny/crossref_metadata_2025 huggingface dataset:
On the quasi-ordering of Borel linear orders under embeddability
Authors: Louveau Alain , Saint-Raymond Jean
Published: May 2006

We provide partial answers to the following problem: Is the class of Borel linear orders well-quasi-ordered under embeddability? We show that it is indeed the case for those Borel orders which are embeddable in Rω, with the lexicographic ordering. For Borel orders embeddable in R2, our proof works in ZFC, but it uses projective determinacy for Borel orders embeddable in some Rn, n < ω, and hyperprojective determinacy for the general case.
Some results about Borel sets in descriptive set theory of hyperfinite sets
Authors: Živaljević Boško
Published: May 2006

A remarkable result of Henson and Ross [HR] states that if a function whose graph is Souslin in the product of two hyperfinite sets in an ℵ1 saturated nonstandard universe possesses a certain nice property (capacity) then there exists an internal subfunction of the given one possessing the same property. In particular, they prove that every 1-1 Souslin function preserves any internal counting measure, and show that every two internal sets A and B with ∣A∣/∣B∣ ≈ 1 are Borel bijective. As a supplement to the last-mentioned result of Henson and Ross, Keisler, Kunen, Miller and Leth showed [KKML] that two internal sets A and B are bijective by a countably determined bijection if and only if ∣A∣/∣B∣ is finite and not infinitesimal.

In this paper we first show that injective Borel functions map Borel sets into Borel sets, a fact well known in classical descriptive set theory. Then, we extend the result of Henson and Ross concerning the Borel bijectivity of internal sets whose quotient of cardinalities is infinitely closed to 1. We prove that two Borel sets, to which we may assign a counting measure not equal to 0 or ∞, are Borel bijective if and only if they have the same counting measure ≠0, ∞. This, together with the similar characterization for Souslin and measurable countably determined sets, extends the above-mentioned results from [HR] and [KKML].
Asymptotic probabilities of existential second-order Gödel sentences
Authors: Pacholski Leszek , Szwast WiesŁaw
Published: May 2006

In [9] and [10] P. Kolaitis and M. Vardi proved that the 0-1 law holds for the second-order existential sentences whose first-order parts are formulas of Bernays-Schonfinkel or Ackermann prefix classes. They also provided several examples of second-order formulas for which the 0-1 law does not hold, and noticed that the classification of second-order sentences for which the 0-1 law holds resembles the classification of decidable cases of first-order prenex sentences. The only cases they have not settled are the cases of Gödel classes with and without equality.

In this paper we confirm the conjecture of Kolaitis and Vardi that the 0-1 law does not hold for the existential second-order sentences whose first-order part is in Gödel prenex form with equality. The proof we give is based on a modification of the example employed by W. Goldfarb [5] in his proof that, contrary to the Gödel claim [6], the class of Gödel prenex formulas with equality is undecidable.
Indescribable cardinals and elementary embeddings
Authors: Hauser Kai
Published: May 2006

Indescribability is closely related to the reflection principles of Zermelo-Fränkel set theory. In this axiomatic setting the universe of all sets stratifies into a natural cumulative hierarchy (Vα: α ϵ On) such that any formula of the language for set theory that holds in the universe already holds in the restricted universe of all sets obtained by some stage.

The axioms of ZF prove the existence of many ordinals α such that this reflection scheme holds in the world Vα. Hanf and Scott noticed that one arrives at a large cardinal notion if the reflecting formulas are allowed to contain second order free variables to which one assigns subsets of Vα. For a given collection Ω of formulas in the ϵ language of set theory with higher type variables and a unary predicate symbol they define an ordinal α to be Ω indescribable if for all sentences Φ in Ω and A ⊆ Vα

Since a sufficient coding apparatus is available, this definition is (for the classes of formulas that we are going to consider) equivalent to the one that one obtains by allowing finite sequences of relations over Vα, some of which are possibly k-ary. We will be interested mainly in certain standardized classes of formulas: Let (, respectively) denote the class of all formulas in the language introduced above whose prenex normal form has n alternating blocks of quantifiers of type m (i.e. (m + 1)th order) starting with ∃ (∀, respectively) and no quantifiers of type greater than m. In Hanf and Scott [1961] it is shown that in ZFC, indescribability is equivalent to inaccessibility and indescribability coincides with weak compactness.
The logic of first order intuitionistic type theory with weak sigma-elimination
Authors: Swaen M. D. G.
Published: May 2006

Via the formulas-as-types embedding certain extensions of Heyting Arithmetic can be represented in intuitionistic type theories. In this paper we discuss the embedding of ω-sorted Heyting Arithmetic HAω into a type theory WL, that can be described as Troelstra's system with so-called weak Σ-elimination rules. By syntactical means it is proved that a formula is derivable in HAω if and only if its corresponding type in WL is inhabited. Analogous results are proved for Diller's so-called restricted system and for a type theory based on predicate logic instead of arithmetic.
Presburger arithmetic with unary predicates is Π11 complete
Authors: Halpern Joseph Y.
Published: May 2006

We give a simple proof characterizing the complexity of Presburger arithmetic augmented with additional predicates. We show that Presburger arithmetic with additional predicates is complete. Adding one unary predicate is enough to get hardness, while adding more predicates (of any arity) does not make the complexity any worse.
An independence result in quadratic form theory: Infinitary combinatorics applied to ε-Hermitian spaces
Authors: Appenzeller Fred
Published: May 2006

There are shown to be many ε-Hermitian spaces, and an isometry criterion is stated which holds under MAℵ1 and is false under 2ℵ0< 2ℵ1.
Bad groups of finite Morley rank
Authors: Corredor Luis Jaime
Published: May 2006

We prove the following theorem. Let G be a connected simple bad group (i.e. of finite Morley rank, nonsolvable and with all the Borel subgroups nilpotent) of minimal Morley rank. Then the Borel subgroups of G are conjugate to each other, and if B is a Borel subgroup of G, then , NG(B) = B, and G has no involutions.
On the cofinality of the smallest covering of the real line by meager sets
Authors: Bartoszynski Tomek , Ihoda Jaime I.
Published: May 2006

We prove that the cofinality of the smallest covering of R by meager sets is bigger than the additivity of measure.
Non Σn axiomatizable almost strongly minimal theories
Authors: Marker David
Published: May 2006

Recall that a theory is said to be almost strongly minimal if in every model every element is in the algebraic closure of a strongly minimal set. In 1970 Hodges and Macintyre conjectured that there is a natural number n such that every ℵ0-categorical almost strongly minimal theory is Σn axiomatizable. Recently Ahlbrandt and Baldwin [A-B] proved that if T is ℵ0-categorical and almost strongly minimal, then T is Σn axiomatizable for some n. This result also follows from Ahlbrandt and Ziegler's results on quasifinite axiomatizability [A-Z]. In this paper we will refute Hodges and Macintyre's conjecture by showing that for each n there is an ℵ0-categorical almost strongly minimal theory which is not Σn axiomatizable.

Before we begin we should note that in all these examples the complexity of the theory arises from the complexity of the definition of the strongly minimal set. It is still open whether the conjecture is true if we allow a predicate symbol for the strongly minimal set.

We will prove the following result.

Theorem. For every n there is an almost strongly minimal ℵ0-categorical theory T with models M and N such that N is Σn elementary but not Σn + 1 elementary.

To show that these theories yield counterexamples to the conjecture we apply the following result of Chang [C].

Theorem. If T is a Σn axiomatizable theory categorical in some infinite power, M and N are models of T and N is a Σn elementary extension of M, then N is an elementary extension of M.
A jump class of noncappable degrees
Authors: Cooper S. B.
Published: May 2006

Friedberg [3] showed that every degree of unsolvability above 0′ is the jump of some degree, and Sacks [9] showed that the degrees above 0′ which are recursively enumerable (r.e.) in 0′ are the jumps of the r.e. degrees.

In this paper we examine the extent to which the Sacks jump theorem can be combined with the minimal pair theorem of Lachlan [4] and Yates [13]. We prove below that there is a degree c > 0′ which is r.e. in 0′ but which is not the jump of half a minimal pair of r.e. degrees.

This extends Yates' result [13] proving the existence of noncappable degrees (that is, r.e. degrees a < 0′ for which there is no corresponding r.e. b > 0 with a ∩ b = 0).

It also throws more light on the class PS of promptly simple degrees. It was shown by Ambos-Spies, Jockusch, Shore and Soare [1] that PS coincides with the class NC of noncappable degrees, and with the class LC of all low-cuppable degrees, and (using earlier work of Maass, Shore and Stob [5]) that PS splits every class Hn or Ln, n ≥ 0, in the high-low hierarchy of r.e. degrees.

If c > 0′, with c r.e. in 0′, let

and call c−1 the jump class for c. It is easy to see that every jump class contains members of PS (= NC = LC). By Sacks [8] there exists a low a ∈ LC, where of course [a, 0′] (= {br.e. ∣a ≤ b ≤ 0′}) ⊆ LC = PS. But by Robinson [7] [a, 0′] intersects with every jump class.
The structure of algebraically and existentially closed Stone and double Stone algebras
Authors: Clark David M.
Published: May 2006

In this paper we study the varieties of Stone algebras (S, ∧, ∨, *, 0, 1) and double Stone algebras (D, ∧, ∨, *, +, 0, 1). Our primary interest is to give a structural description of the algebraically and existentially closed members of both classes. Our technique is an application of the natural dualities of Davey [6] and Clark and Krauss [5]. This approach gives a description of the desired models as the algebras of all continuous structure-preserving maps from certain structured Boolean spaces into the generating algebra for the variety. In each case the resulting description can be converted in a natural way into a finite ∀∃-axiomatization for these models. For Stone algebras these axioms appeared earlier in Schmid [20], [21] and in Schmitt [22].

Since both cases we consider satisfy the amalgamation property, the existentially closed members form a model companion for the variety which is also its model completion. Moreover, it is also ℵ0 categorical and its countably infinite member is the unique countable homogeneous universal model for the variety. In the case of Stone algebras, explicit constructions for this model appear in Schmitt [22] and Weispfenning [23]. We give here an explicit construction for double Stone algebras of S. Hayes.

This work was motivated by a problem of Stanley Burris. In [4] Burris and Werner superseded many previous results by showing that for any finite algebra A, the universal Horn class ISP has a model companion. Weispfenning [24], [25] discovered that this model companion is always ℵ0 categorical and has a primitive recursive ∀∃-axiomatization. In spite of these very general theorems, there are few instances in which a structural description of the (any!) existentially closed members of ISP is available. Burris and Werner [4] solve this problem in a special setting.
Regressive partitions and Borel diagonalization
Authors: Kanamori Akihiro
Published: May 2006

Several rather concrete propositions about Borel measurable functions of several variables on the Hilbert cube (countable sequences of reals in the unit interval) were formulated by Harvey Friedman [F1] and correlated with strong set-theoretic hypotheses. Most notably, he established that a “Borel diagonalization” proposition P is equivalent to: for any a ⊆ co and n ⊆ ω there is an ω-model of ZFC + ∃κ(κ is n-Mahlo) containing a. In later work (see the expository Stanley [St] and Friedman [F2]), Friedman was to carry his investigations further into propositions about spaces of groups and the like, and finite propositions. He discovered and analyzed mathematical propositions which turned out to have remarkably strong consistency strength in terms of large cardinal hypotheses in set theory.

In this paper, we refine and extend Friedman's work on the Borel diagonalization proposition P. First, we provide more combinatorics about regressive partitions and n-Mahlo cardinals and extend the approach to the context of the Erdös cardinals In passing, a combinatorial proof of a well-known result of Silver about these cardinals is given. Incorporating this work and sharpening Friedman's proof, we then show that there is a level-by-level analysis of P which provides for each n ⊆ ω a proposition almost equivalent to: for any a ⊆ co there is an ω-model of ZFC + ∃κ(κ is n-Mahlo) containing a. Finally, we use the combinatorics to bracket a natural generalization Sω of P between two large cardinal hypotheses.
Recursively enumerable m- and tt-degrees. I: The quantity of m-degrees
Authors: Downey R. G.
Published: May 2006

In [1], Degtëv constructed a nonzero r.e. tt-degree containing a single r.e. m-degree. It is not difficult to construct an r.e. tt-degree containing infinitely many r.e. m-degrees (Fischer [6]); indeed, in [3], the author constructed an r.e. tt-degree with no greatest r.e. m-degree. Odifreddi [12, Problem 10] asked if every r.e. tt-degree contains either one or infinitely many r.e. m-degrees. The goal of this paper is to solve Odifreddi's question by showing:

Theorem. There exists a nonzero r.e. tt-degree containing exactly 3 r.e. m-degrees.

This theorem can be extended to show that there exist r.e. tt-degrees with arbitrarily large finite numbers of r.e. m-degrees.

We remark that save for the aforementioned results, very little is known about the structures that can be realized as the collection of r.e. m-degrees within an r.e. tt-degree. It seems conceivable that the methods of the present paper may be useful in, for example, embedding distributive (semi) lattices into such structures.

In part II of this paper [4], we continue our analysis of r.e. m- and tt-degrees. We define an r.e. tt-degree to be singular if it contains a single r.e. m-degree, and an r.e. T-degree a to be singular if a contains a singular r.e. tt-degree.

In [4] we study the distribution (in the r.e. T-degrees) of singular tt-degrees. We show that 0′T is singular (solving a question of Odifreddi [11]), and that the singular T-degrees are dense, but also we construct a nonsingular T-degree. The techniques used for the first results extend those of §2 of the present paper.
Indiscernible sequences in a model which fails to have the order property
Authors: Grossberg Rami
Published: May 2006

Basic results on the model theory of substructures of a fixed model are presented. The main point is to avoid the use of the compactness theorem, so this work can easily be applied to the model theory of Lω1,ω and its relatives. Among other things we prove the following theorem:

Let M be a model, and let λ be a cardinal satisfying λ∣L(M)∣ = λ. If M does not have the ω-order property, then for every A ⊆ M, ∣A∣ ≤ λ, and every I ⊆ M of cardinality λ+ there exists J ⊆ I cardinality λ+ which is an indiscernible set over A.

This is an improvement of a result of S. Shelah.
Stratification and cut-elimination
Authors: Crabbé Marcel
Published: May 2006

In this paper, we show the normalization of proofs of NF (Quine's New Foundations; see [15]) minus extensionality. This system, called SF (Stratified Foundations) differs in many respects from the associated system of simple type theory. It is written in a first order language and not in a multi-sorted one, and the formulas need not be stratifiable, except in the instances of the comprehension scheme. There is a universal set, but, for a similar reason as in type theory, the paradoxical sets cannot be formed.

It is not immediately apparent, however, that SF is essentially richer than type theory. But it follows from Specker's celebrated result (see [16] and [4]) that the stratifiable formula (extensionality → the universe is not well-orderable) is a theorem of SF.

It is known (see [11]) that this set theory is consistent, though the consistency of NF is still an open problem.

The connections between consistency and cut-elimination are rather loose. Cut-elimination generally implies consistency. But the converse is not true. In the case of set theory, for example, ZF-like systems, though consistent, cannot be freed of cuts because the separation axioms allow the formation of sets from unstratifiable formulas. There are nevertheless interesting partial results obtained when restrictions are imposed on the removable cuts (see [1] and [9]). The systems with stratifiable comprehension are the only known set-theoretic systems that enjoy full cut-elimination.
Quantales and (noncommutative) linear logic
Authors: Yetter David N.
Published: May 2006

It is the purpose of this paper to make explicit the connection between J.-Y. Girard's “linear logic” [4], and certain models for the logic of quantum mechanics, namely Mulvey's “quantales” [9]. This will be done not only in the case of commutative linear logic, but also in the case of a version of noncommutative linear logic suggested, but not fully formalized, by Girard in lectures given at McGill University in the fall of 1987 [5], and which for reasons which will become clear later we call “cyclic linear logic”.

For many of our results on quantales, we rely on the work of Niefield and Rosenthal [10].

The reader should note that by “the logic of quantum mechanics” we do not mean the lattice theoretic “quantum logics” of Birkhoff and von Neumann [1], but rather a logic involving an associative (in general noncommutative) operation “and then”. Logical validity is intended to embody empirical verification (whether a physical experiment, or running a program), and the validity of A & B (in Mulvey's notation) is to be regarded as “we have verified A, and then we have verified B”. (See M. D. Srinivas [11] for another exposition of this idea.)

This of course is precisely the view of the “multiplicative conjunction”, ⊗, in the phase semantics for Girard's linear logic [4], [5]. Indeed the quantale semantics for linear logic may be regarded as an element-free version of the phase semantics.
Two incomplete anti-realist modal epistemic logics
Authors: Williamson Timothy
Published: May 2006

Many phrases have been used to express what are sometimes called anti-realist conceptions of truth: ‘verifiability’, ‘knowability’, ‘rational acceptability’, ‘warranted assertability’. In spite of their obvious differences, all four of these phrases have a common form; each is a cognitive attitude modified by ‘-ability’. They speak of the possibility of verification, knowledge, rational acceptance or warranted assertion. Schematically, it seems to be claimed that it is true that A if and only if it is possible that it is E'd that A, where ‘E’ is to be replaced by some cognitive verb and ‘A’ by any indicative sentence of the class to which the anti-realist conception is being claimed to apply. Since truth is redundant as a sentential operator, this boils down to the following thesis, where ‘p’ is a propositional variable and ‘M’ expresses the appropriate kind of possibility:

(*) also formalizes views such as Putnam's: ‘To claim a statement is true is to claim it could be justified’ [11, p. 56]. It is no doubt a crude model for anti-realism, but one has to start somewhere; by seeing how and why more sophisticated versions of anti-realism differ from (*) one should be able to understand them better too. Moreover, if an anti-realist rejects the equation of truth with, say, warranted assertibility, arguing that truth is rather to be identified with the possibility of getting into a position in which one's warrant to assert somehow cannot be overturned, the form of (*) is preserved, for truth is still being identified with the possibility of something.
Théories complètes de paires de corps valués henseliens
Authors: Leloup Gérard
Published: May 2006

Un prolongement de l'étude d'une théorie T, dans le langage , consiste à s'intéresser à la théorie T* des paires de modèles de T, c'est-à-dire les structures de la forme (K ⊊ L) où K ⊨ T, L ⊨ T, K ≺ L, dans le langage où E est un prédicat pour la sous-structure. Les propriétés de la théorie T ne se transmettent pas toujours à T*, particulièrement en ce qui concerne la complétude et la décidabilité. On trouve des illustrations de cas opposés dans les théories de corps:

—si T est la théorie des corps algébriquement clos de caractéristique fixée, T* est complète et décidable;

—si T est la théorie des corps réels clos, T est complète et décidable, mais T* est indécidable, et admet complétions différentes.

Nous allons nous intéresser ici aux paires de corps valués henseliens, et plus particulièrement au cas de caractéristique résiduelle nulle, de la forme (K ⊊ L, υ) où (K, υ) n'est pas nécessairement une sous-structure élémentaire de (L, υ). Ax, Kochen et Ershov ont montré que la théorie d'un corps valué henselien de caractéristique résiduelle nulle est entièrement déterminée par la théorie de son corps de restes et par la théorie de son groupe de valuation; par ailleurs, de résultats analogues existent pour certains corps de caractéristique résiduelle non nulle.
Finite injury and Σ1-induction
Authors: Mytilinaios Michael
Published: May 2006

Working in the language of first-order arithmetic we consider models of the base theory P−. Suppose M is a model of P− and let M satisfy induction for Σ1-formulas. First it is shown that the Friedberg-Muchnik finite injury argument can be performed inside M, and then, using a blocking method for the requirements, we prove that the Sacks splitting construction can be done in M. So, the “amount” of induction needed to perform the known finite injury priority arguments is Σ1-induction.
Finitely based theories
Authors: Hrushovski Ehud
Published: May 2006

A stable theory is finitely based if every set of indiscernibles is based on a finite subset. This is a common generalization of superstability and 1-basedness. We show that if such theories have more than one model they must have infinitely many, and prove some other conjectures.
The well-foundedness of the Mitchell order
Authors: Steel J. R.
Published: May 2006

Let E ⊲ F iff E and F are extenders and E ∈ Ult(V, F). Intuitively, E ⊲ F implies that E is weaker—embodies less reflection—than F. The relation ⊲ was first considered by W. Mitchell in [M74], where it arises naturally in connection with inner models and coherent sequences. Mitchell showed in [M74] that the restriction of ⊲ to normal ultrafilters is well-founded.

The relation ⊲ is now known as the Mitchell order, although it is not actually an order. It is irreflexive, and its restriction to normal ultrafilters is transitive, but under mild large cardinal hypotheses, it is not transitive on all extenders. Here is a counterexample. Let κ be (λ + 2)-strong, where λ > κ and λ is measurable. Let E be an extender with critical point κ and let U be a normal ultrafilter with critical point λ such that U ∈ Ult(V, E). Let i: V → Ult(V, U) be the canonical embedding. Then i(E) ⊲ U and U ⊲ E, but by 3.11 of [MS2], it is not the case that i(E) ⊲ E. (The referee pointed out the following elementary proof of this fact. Notice that i ↾ Vλ+2 ∈ Ult(V, E) and X ∈ Ea ⇔ X ∈ i(E)i(a). Moreover, we may assume without loss of generality that = support(E). Thus, if i(E) ∈ Ult(V, E), then E ∈ Ult(V, E), a contradiction.)

By going to much stronger extenders, one can show the Mitchell order is not well-founded. The following example is well known. Let j: V → M be elementary, with Vλ ⊆ M for λ = joω(crit(j)). (By Kunen, Vλ+1 ∉ M.) Let E0 be the (crit(j), λ) extender derived from j, and let En+1 = i(En), where i: V → Ult(V, En) is the canonical embedding. One can show inductively that En is an extender over V, and thereby, that En+1 ⊲ En for all n < ω. (There is a little work in showing that Ult(V, En+1) is well-founded.)
Reducts of some structures over the reals
Authors: Peterzil Ya′acov
Published: May 2006

We consider reducts of the structure ℛ = 〈ℝ, +, ·, <〉 and other real closed fields. We compete the proof that there exists a unique reduct between 〈ℝ, +, <,λa〉a ∈ ℝ and ℛ, and we demonstrate how to recover the definition of multiplication in more general contexts than the semialgebraic one. We then conclude a similar result for reducts between 〈ℝ, ·, <〉 and ℛ and for general real closed fields.
On closed P-sets with ccc in the space ω*
Authors: Frankiewicz Rvszard , Shelah Saharon , Zbierski Paweł
Published: May 2006

It is proved that—consistently — there can be no ccc closed P-sets in the remainder space ω*.
A note on Mathematics of infinity
Authors: Palmgren Erik
Published: May 2006

In the paper Mathematics of infinity, Martin-Löf extends his intuitionistic type theory with fixed “choice sequences”. The simplest, and most important instance, is given by adding the axioms

to the type of natural numbers. Martin-Löf's type theory can be regarded as an extension of Heyting arithmetic (HA). In this note we state and prove Martin-Löf's main result for this choice sequence, in the simpler setting of HA and other arithmetical theories based on intuitionistic logic (Theorem A). We also record some remarkable properties of the resulting systems; in general, these lack the disjunction property and may or may not have the explicit definability property. Moreover, they represent all recursive functions by terms.
Addendum to “A structure theorem for strongly abelian varieties”
Authors: Hart Bradd , Starchenko Sergei
Published: May 2006

By a variety we mean a class of algebras in a language , containing only function symbols, which is closed under homomorphisms, submodels, and products. A variety is said to be strongly abelian if for any term in , the quasi-identity

holds in .

In [1] it was proved that if a strongly abelian variety has less than the maximal possible uncountable spectrum, then it is equivalent to a multisorted unary variety. Using Shelah's Main Gap theorem one can conclude that if is a classifiable (superstable without DOP or OTOP and shallow) strongly abelian variety then is a multisorted unary variety. In fact, it was known that this conclusion followed from the assumption of superstable without DOP alone.

This paper is devoted to the proof that the superstability assumption is enough to obtain the same structure result. This fulfills a promise made in [2]. Namely, we will prove the following

Theorem 0.1. If is a superstable strongly abelian variety, then it is multisorted unary.
An inside view of EXP; or, The closed fragment of the provability logic of IΔ0 + Ω1 with a prepositional constant for EXP
Authors: Visser Albert
Published: May 2006

In this paper I give a characterization of the closed fragment of the provability logic of I Δ0 + EXP with a propositional constant for EXP. In three appendices many details on arithmetization are provided.
Lambek's categorical proof theory and Läuchli's abstract realizability
Authors: Harnik Victor , Makkai Michael
Published: May 2006

In this paper we give an introduction to categorical proof theory, and reinterpret, with improvements, Läuchli's work on abstract realizability restricted to propositional logic (but see [M1] for predicate logic). Partly to make some points of a foundational nature, we have included a substantial amount of background material. As a result, the paper is (we hope) readable with a knowledge of just the rudiments of category theory, the notions of category, functor, natural transformation, and the like. We start with an extended introduction giving the background, and stating what we do with a minimum of technicalities.

In three publications [L1, 2, 3] published in the years 1968, 1969 and 1972, J. Lambek gave a categorical formulation of the notion of formal proof in deductive systems in certain propositional calculi. The theory is also described in the recent book [LS]. See also [Sz].

The basic motivation behind Lambek's theory was to place proof theory in the framework of modern abstract mathematics. The spirit of the latter, at least for the purposes of the present discussion, is to organize mathematical objects into mathematical structures. The specific kind of structure we will be concerned with is category.

In Lambek's theory, one starts with an arbitrary theory in any one of several propositional calculi. One has the (formal) proofs (deductions) in the given theory of entailments A ⇒ B, with A and B arbitrary formulas. One introduces an equivalence relation on proofs under which, in particular, equivalent proofs are proofs of the same entailment; equivalence of proofs is intended to capture the idea of the proofs being only inessentially different. One forms a category whose objects are the formulas of the underlying language of the theory, and whose arrows from A to B, with the latter arbitrary formulas, are the equivalence classes of formal proofs of A ⇒ B.
The Baire category theorem in weak subsystems of second-order arithmetic
Authors: Brown Douglas K. , Simpson Stephen G.
Published: May 2006

Working within weak subsystems of second-order arithmetic Z2 we consider two versions of the Baire Category theorem which are not equivalent over the base system RCA0. We show that one version (B.C.T.I) is provable in RCA0 while the second version (B.C.T.II) requires a stronger system. We introduce two new subsystems of Z2, which we call and , and , show that suffices to prove B.C.T.II. Some model theory of and its importance in view of Hilbert's program is discussed, as well as applications of our results to functional analysis.
On the Cantor-Bendixon rank of recursively enumerable sets
Authors: Cholak Peter , Downey Rod
Published: May 2006

The main result of this paper is to show that for every recursive ordinal α ≠ 0 and for every nonrecursive r.e. degree d there is a r.e. set of rank α and degree d.
Consequences of arithmetic for set theory
Authors: Halbeisen Lorenz , Shelah Saharon
Published: May 2006

In this paper, we consider certain cardinals in ZF (set theory without AC, the axiom of choice). In ZFC (set theory with AC), given any cardinals and , either ≤ or ≤ . However, in ZF this is no longer so. For a given infinite set A consider seq1-1(A), the set of all sequences of A without repetition. We compare |seq1-1(A)|, the cardinality of this set, to ||, the cardinality of the power set of A. What is provable about these two cardinals in ZF? The main result of this paper is that ZF ⊢ ∀A(| seq1-1(A)| ≠ ||), and we show that this is the best possible result. Furthermore, it is provable in ZF that if B is an infinite set, then | fin(B)| < | (B*)| even though the existence for some infinite set B* of a function ƒ from fin(B*) onto (B*) is consistent with ZF.
Indécidabilité des corps de courbe réelle
Authors: Bélair Luc , Duret Jean-Louis
Published: May 2006

Nous dirons qu'un corps (commutatif) K est un corps de courbe réelle sur le corps k si et seulement si c'est une extension de k, ordonnable, finiment engendrée et de degré de transcendance 1 sur k, telle que k soit relativement algébriquement clos dans K. Un tel corps est le corps d'une courbe (plane) définie sur k. De plus si k est réel-clos, toute courbe définie sur k dont K est le corps, a un point régulier rationnel sur k; en effet soit I ⊂ k[X0,…, Xn] l'idéal d'une telle courbe Γ; on a donc: K = k[x0,…, xn] où x0,…, xn sont les classes d'équivalence de X0,…, Xn; (x0,…, xn) est un point régulier de Γ dans la clôture réelle de K, et par modèle-complétude, Γ a un point régulier rationnel sur k.

Notre but est d'étendre les résultats de Raphael Robinson [6] sur l'indécidabilité des corps de fractions rationnelles sur un corps ordonnable (dans le langage des corps). Comme lui, nous donnerons une méthode qui ne s'applique que lorsque le corps de base k est réel-clos, et une seconde méthode générate.
Accessible telephone directories
Authors: Goode John B.
Published: May 2006

We reduce to a standard circuit-size complexity problem a relativisation of the P=NP question that we believe to be connected with the same question in the model for computation over the reals defined by L. Blum. M. Shub, and S. Smale. On this occasion, we set the foundations of a general theory for computation over an arbitrary structure, extending what these three authors did in the case of rings.
Some remarks on nonmultidimensional superstable theories
Authors: Pillay Anand
Published: May 2006

In this paper we study nonmultidimensional superstable theories T, possibly in an uncountable language, and develop some techniques permitting the generalisation of certain results from the finite rank (and/or countable language) context to the general case.

We prove, among other things, the following: there is a set A0 of parameters, which has cardinality at most ∣T∣, and in the finite-dimensional case is finite, such that over any B ⊇ A0 there is a locally atomic model. One of the consequences of this is that if C is the monster model of T, φ(x) is a formula over A0, φC ⊇ X and (X, φC) satisfies the Tarski-Vaught condition after adding names for A0, then there is an elementary substructure M of C containing A0 such that φM = X. Applications to the spectrum problem will appear in [Ch-P].

In fact, all the components of the machinery we develop are already present in the general theory. One such component involves a stratification of the regular types of T using a generalized notion of weakly minimal formula. This appears in [Sh, Chapter V and the proof of IX.2.4] and also in [P2]. A second component involves definable groups which arise as ‘binding” groups. The existence of such groups, under certain hypotheses on the behavior of nonorthogonality, is due to Hrushovski [Hr1], and our use of them to help obtain “j-constructible” models is similar to their use in [Bu-Sh].
A quantitative analysis of modal logic
Authors: Fagin Ronald
Published: May 2006

We do a quantitative analysis of modal logic. For example, for each Kripke structure M, we study the least ordinal μ such that for each state of M, the beliefs up to level μ characterize the agents' beliefs (that is, there is only one way to extend these beliefs to higher levels). As another example, we show the equivalence of three conditions, that on the face of it look quite different, for what it means to say that the agents' beliefs have a countable description, or putting it another way, have a “countable amount of information”. The first condition says that the beliefs of the agents are those at a state of a countable Kripke structure. The second condition says that the beliefs of the agents can be described in an infinitary language, where conjunctions of arbitrary countable sets of formulas are allowed. The third condition says that countably many levels of belief are sufficient to capture all of the uncertainty of the agents (along with a technical condition). The fact that all of these conditions are equivalent shows the robustness of the concept of the agents' beliefs having a “countable description”.
On the degrees of unsolvability of modal predicate logics of provability
Authors: McGee Vann
Published: May 2006

The modal predicate logic of provability identifies the “□” of modal logic with the “Bew” of proof theory, so that, where “Bew” is a formula representing, in the usual way, provability in a consistent, recursively axiomatized theory Γ extending Peano arithmetic (PA), an interpretation of a language for the modal predicate calculus is a map * which associates with each modal formula an arithmetical formula with the same free variables which commutes with the Boolean connectives and the quantifiers and which sets (□ϕ)* equal to Bew(⌈ϕ*⌉). Where Δ is an extension of PA (all the theories we discuss will be extensions of PA), MPL(Δ) will be the set of modal formulas ϕ such that, for every interpretation *, ϕ* is a theorem of Δ. Most of what is currently known about the modal predicate logic of provability consists in demonstrations that MPL(Δ) must be computationally highly complex. Thus Vardanyan [11] shows that, provided that Δ is 1-consistent and recursively axiomatizable, MPL(Δ) will be complete , and Boolos and McGee [5] show that MPL({true arithmetical sentences}) is complete in {true arithmetical sentences}. All of these results take as their starting point Artemov's demonstration in [1] that {true arithmetical sentences} is 1-reducible to MPL({true arithmetical sentences}).

The aim here is to consolidate these results by providing a general theorem which yields all the other results as special cases. These results provide a striking contrast with the situation in modal sentential logic (MSL); according to fundamental results of Solovay [8], provided Γ does not entail any falsehoods, MSL({true arithmetical sentences}) and MSL(PA) (which is the same as MSL(Γ)) are both decidable.
Some remarks on openly generated Boolean algebras
Authors: Fuchino Sakaé
Published: May 2006

A Boolean algebra B is said to be openly generated if {A : A ≤rcB, ∣A∣ = ℵ0} includes a club subset of . We show:

(V = L). For any cardinal κ there exists an L∞κ-free Boolean algebra which is not openly generated (Proposition 4.1).

(MA+(σ-closed)). Every -free Boolean algebra is openly generated (Theorem 4.2).

The last assertion follows from a characterization of openly generated Boolean algebras under MA+(σ-closed) (Theorem 3.1). Using this characterization we also prove the independence of problem 7 in Ščepin [15] (Proposition 4.3 and Theorem 4.4).
Failure of Cartesian closedness in NF
Authors: McLarty Colin
Published: May 2006

On any reasonable definition of functions, neither the category of sets nor the category of small categories is cartesian closed in New Foundations (NF). The latter category is sometimes proposed as a foundation for category theory since it is among its own objects. Our result shows it is a poor one.

In NF, as in other set theories, a "function" f from a set A to a set B is defined to be a set f of ordered pairs 〈x, y〉 with x in A and y in B, such that (a) if 〈x, y〉 ∈ f and 〈x, y′〉 ∈ f then y = y′, and (b) for every x in A there is some y in B with 〈x, y〉 ∈ f. But in NF different definitions of ordered pairs give significantly different functions. I say a reasonable definition must give:

1. The formula z = 〈x, y〉 is stratifiable.

2. For every set S there is a set {〈x, x〉 ∣ x ∈ S}.

3. If f is a function from A to B, and g one from B to C, there is a set {〈x, z〉∣(∃y)〈x, y〉∈ f & 〈y, z〉∈ g}.

Principles 2 and 3 are needed for identity functions and composites. By principle 1, any sets A and B have a set A × B of all ordered pairs 〈x, y〉 with x in A and y in B, but it does not follow that functions exist making A × B a categorical product of A and B.
Zero-one laws with variable probability
Authors: Spencer Joel
Published: May 2006

One of this author's favorite theorems has long been the Zero-One law discovered independently by Glebskii et al. [12] and Ron Fagin [10]. Let A be any first-order property of graphs and let µn(A) be the proportion of labelled graphs on n vertices for which A holds. Then

This result has inspired much work by logicians, generally in the direction of showing (1) for some powerful languages. Thus it is known [5] that (1) holds when A is a sentence in fixed point logic and it is known [13] that (1) does not always hold when A is a sentence in second-order monadic logic. Here, however, we explore recent work in a totally different direction. Let G(n, p) denote the random graph on n vertices with edge probability p. (In §2 we define the random structures we will deal with.) A property A is an event in the probability space and Pr[G(n, p) ╞ A] is well defined. When p = 1/2, each labelled graph on n vertices has equal weight so that (1) may be rewritten

Fagin's proof actually gives that (2) holds for any constant 0 < p < 1.
On coherent families of finite-to-one functions
Authors: Koszmider Piotr
Published: May 2006

We consider the existence of coherent families of finite-to-one functions on countable subsets of an uncountable cardinal κ. The existence of such families for κ implies the existence of a winning 2-tactic for player TWO in the countable-finite game on κ. We prove that coherent families exist on κ = ωn, where n ∈ ω, and that they consistently exist for every cardinal κ. We also prove that iterations of Axiom A forcings with countable supports are Axiom A.
Canonical formulas for K4. Part I: Basic results
Authors: Zakharyaschev Michael
Published: May 2006

This paper presents a new technique for handling modal logics with transitive frames, i.e. extensions of the modal system K4. In effect, the technique is based on the following fundamental result, to be obtained below in §3.

Given a formula φ, we can effectively construct finite frames 1, …, n which completely characterize the set of all transitive general frames refuting φ. More exactly, an arbitrary general frame refutes φ iff contains a (not necessarily generated) subframe such that (1) i, for some i ϵ {1, …, n}, is a p-morphic image of (after Fine [1985] we say is subreducible to i), (2) is cofinal in , and (3) every point in that is not in does not get into “closed domains” which are uniquely determined in i, by φ.

This purely technical result has, as it turns out, rather unexpected and profound consequences. For instance, it follows at once that if φ determines no closed domains in the frames 1, …, n associated with it, then the normal extension of K4 generated by φ has the finite model property and so is decidable. Moreover, every normal logic axiomatizable by any (even infinite) set of such formulas φ also has the finite model property. This observation would not possibly merit any special attention, were it not for the fact that the class of such logics contains almost all the standard systems within the field of K4 (at least all those mentioned by Segerberg [1971] or Bull and Segerberg [1984]), all logics containing S4.3, all subframe logics of Fine [1985], and a continuum of other logics as well.
The isomorphism property versus the special model axiom
Authors: Jin Renling
Published: May 2006

This paper answers some questions of D. Ross in [R]. In §1, we show that some consequences of the ℵ1- or ℵ1-special model axiom in [R] cannot be proved by the κ-isomorphism property for any cardinal κ. In §2, we show that with one exception, the ℵ0-isomorphism property does imply the remaining consequences of the special model axiom in [R]. In §3, we improve a result in [R] by showing that the κ-special model axiom is equivalent to the ℵ0-special model axiom plus κ-saturation.
On decidable varieties of Heyting algebras
Authors: Dubhashi Devdatt P.
Published: May 2006

In this paper we present a new proof of a decidability result for the firstorder theories of certain subvarieties of Heyting algebras. By a famous result of Grzegorczyk, the full first-order theory of Heyting algebras is undecidable. In contrast, the first-order theory of Boolean algebras and of many interesting subvarieties of Boolean algebras is decidable by a result of Tarski [8]. In fact, Kozen [6] gives a comprehensive quantitative classification of the complexities of the first-order theories of various subclasses of Boolean algebras (including the full variety).

This stark contrast may be reconciled from the standpoint of universal algebra as arising out of the byplay between structure and decidability: A good structure theory entails positive decidability results. Boolean algebras have a well-developed structure theory [5], while the corresponding theory for Heyting algebras is quite meagre. Viewed in this way, we may hope to obtain decidability results if we focus attention on subclasses of Heyting algebras with good structural properties.

K. Idziak and P. M. Idziak [4] have considered an interesting subvariety of Heyting algebras, , which is the variety generated by all linearly-ordered Heyting algebras. This variety is shown to be the largest subvariety of Heyting algebras with a decidable theory of its finite members. However their proof is rather indirect, proceeding via semantic interpretation into the monadic second order theory of trees. The latter is a powerful theory—it interprets many other theories—but is computationally highly infeasible. In fact, by a celebrated theorem of Rabin, its complexity is not bounded by any elementary recursive function. Consequently, the proof of [4], besides being indirect, also gives no information on the quantitative computational complexity of the theory of .

Here we pursue the theme of structure and decidability. We isolate the indecomposable algebras in and use this to prove a theorem on the structure of if -algebras. This theorem relates the -algebras structurally to Boolean algebras. This enables us to bootstrap the known decidability results for Boolean algebras to the variety if .
Pseudoprojective strongly minimal sets are locally projective
Authors: Buechler Steven
Published: May 2006

Let D be a strongly minimal set in the language L, and D′ ⊃ D an elementary extension with infinite dimension over D. Add to L a unary predicate symbol D and let T′ be the theory of the structure (D′, D), where D interprets the predicate D. It is known that T′ is ω-stable. We prove

Theorem A. If D is not locally modular, then T′ has Morley rank ω.

We say that a strongly minimal set D is pseudoprojective if it is nontrivial and there is a k < ω such that, for all a, b ∈ D and closed X ⊂ D, a ∈ cl(Xb) ⇒ there is a Y ⊂ X with a ∈ cl(Yb) and ∣Y∣ ≤ k. Using Theorem A, we prove

Theorem B. If a strongly minimal set D is pseudoprojective, then D is locally projective.

The following result of Hrushovski's (proved in §4) plays a part in the proof of Theorem B.

Theorem C. Suppose that D is strongly minimal, and there is some proper elementary extension D1 of D such that the theory of the pair (D1, D) is ω1-categorical. Then D is locally modular.
Expressing infinity without foundation
Authors: Parlamento Franco , Policriti Alberto
Published: May 2006

The axiom of infinity can be expressed by stating the existence of sets satisfying a formula which involves restricted universal quantifiers only, even if the axiom of foundation is not assumed.
Countable structures, Ehrenfeucht strategies, and Wadge reductions
Authors: Linton Tom
Published: May 2006

For countable structures and , let abbreviate the statement that every sentence true in also holds in . One can define a back and forth game between the structures and that determines whether . We verify that if θ is an Lω,ω sentence that is not equivalent to any Lω,ω sentence, then there are countably infinite models and such that ⊨ θ, ⊨ ¬θ, and . For countable languages ℒ there is a natural way to view ℒ structúres with universe ω as a topological space, Xℒ. Let [] = { ∊ Xℒ∣ ≅ } denote the isomorphism class of . Let and be countably infinite nonisomorphic ℒ structures, and let C ⊆ ωω be any subset. Our main result states that if , then there is a continuous function f: ωω → Xℒ with the property that x ∊ C ⇒ f(x) ∊ [] and x ∉ C ⇒ f(x) ∊ f(x) ∈ []. In fact, for α ≤ 3, the continuous function f can be defined from the relation.
Uniqueness, collection, and external collapse of cardinals in IST and models of Peano arithmetic
Authors: Kanovei V.
Published: May 2006

We prove that in IST, Nelson's internal set theory, the Uniqueness and Collection principles, hold for all (including external) formulas. A corollary of the Collection theorem shows that in IST there are no definable mappings of a set X onto a set Y of greater (not equal) cardinality unless both sets are finite and #(Y) ≤ n #(X) for some standard n. Proofs are based on a rather general technique which may be applied to other nonstandard structures. In particular we prove that in a nonstandard model of PA, Peano arithmetic, every hyperinteger uniquely definable by a formula of the PA language extended by the predicate of standardness, can be defined also by a pure PA formula.