bluuebunny/crossref_metadata_2025 huggingface dataset:
Decidability and ℵ0-categoricity of theories of partially ordered sets
Authors: Schmerl James H.
Published: May 2006

This paper is primarily concerned with ℵ0-categoricity of theories of partially ordered sets. It contains some general conjectures, a collection of known results and some new theorems on ℵ0-categoricity. Among the latter are the following.

Corollary 3.3. For every countable ℵ0-categoricalthere is a linear order of A such that (, <) is ℵ0-categorical.

Corollary 6.7. Every ℵ0-categorical theory of a partially ordered set of finite width has a decidable theory.

Theorem 7.7. Every ℵ0-categorical theory of reticles has a decidable theory.

There is a section dealing just with decidability of partially ordered sets, the main result of this section being

Theorem 8.2. If (P, <) is a finite partially ordered set and KP is the class of partially ordered sets which do not embed (P, <), then Th(KP) is decidable iff KP contains only reticles.
A selection theorem
Authors: Kirousis Lefteris Miltiades
Published: May 2006

In [1978] Harrington and MacQueen proved that if B is an (A, E)-semirecursive subset of A, such that the functions in BA can be coded as elements of A in an (A, E)-recursive way, then ENV(A, E) is closed under the existential quantifier ∃T ∈ B.

Later Moschovakis showed that if ENV(Vκ, ∈, E) is closed under the quantifier ∃t ∈ λ, where λ is the p-cofinality of κ, then

the p-cofinality of κ is the least ordinal λ for which there exists a (κ, <, E)-recursive partial function ƒ into κ, such that ƒ∣λ is total from λ onto an unbounded subset of κ.

In this paper we prove that for any infinite ordinal κ if p-card(κ) = κ, then ENV(κ, <, E) is closed under ∃t ∈ μ, for μ < p-cf(κ); p-cf(κ) is the “boldface” analog of p-cf((κ) and p-card(κ) is defined similarly.

From this follows that for any infinite ordinal κ the following two statements are equivalent.

(i) ENV(κ, <, E) is closed under bounded existential quantification.

(ii) ENV(κ, <, E) = ENV(κ, <, E#) or p-cf(κ) = κ.

We also show that we cannot omit any of the hypotheses in the above theorem.

We follow mainly the notation of Kechris and Moschovakis [1977].
A second paper “On the interpolation theorem for the logic of constant domains”
Authors: López-Escobar E.G.K.
Published: May 2006

It was brought to our attention by M. Fitting that Beth's semantic tableau system using the intuitionistic propositional rules and the classical quantifier rules produces a correct but incomplete axiomatization of the logic CD of constant domains. The formula

where T is a truth constant, being an instance of a formula which is valid in all Kripke models with constant domains but which is not provable without cut.

From the Fitting formula one can immediately obtain that the sequent

although provable in the system GD outlined in [3], does not have a cut-free proof (in the system GD).

If the only problem with GD were the sequent S0, then we could extend GD to the system GD+ by adding the following (correct) rule:

Since the new rule still satisfies the subformula property a cut elimination theorem for GD+ would be a step in the right direction for a syntactical proof for the interpolation theorem for the logic of constant domains (cf. Gabbay [2]; see also §4). Unfortunately, one can show that the sequent

where P is a propositional parameter (or formula without x free) has a derivation in GD+, but does not have a cut-free derivation (in GD+). Of course, we could extend GD+ to GD++ by adding the following correct (and with the subformula property) rule:

But then we can find a sequent S2 which, although provable with cut in GD++, does not have a cut-free derivation in GD++.
Sets constructed from sequences of measures: Revisited
Authors: Mitchell William J.
Published: May 2006

Let U and U′ be measures on a cardinal κ: that is, normal κ-complete ultrafilters on κ. The partial ordering ⊲ was defined in [M74]: we say U ⊲ U′ if U ∈ Vκ/U′. A model L(ℱ) was constructed in which this ordering was a well ordering, and it was shown that under proper assumptions the length of this well ordering could be any ordinal up to κ++L(ℱ). In this paper we will revisit this material and show that the coherence required in the construction of ℱ can be greatly weakened. This change simplifies some proofs, weakens the assumption needed for the results stated above (Theorem 1, below), and proves one new result (Theorem 5, below) which is suggestive although its significance is not clear.

We have tried to make this paper self-contained and to that end have repeated some material from [M74]. We begin with some definitions before stating Theorem 1.

The ordering ⊲ is well founded. This may be seen by assuming that it is not and letting κ be least such that ⊲ is not well founded on measures on κ. If U is a measure on κ with an infinite descending chain below it, then the measures on κ in VκU are still not well founded by ⊲, contradicting the fact that iU(κ) is the least cardinal in Vκ/U such that ⊲ is not well founded. Since ⊲ is well founded, we can define O(U) to be the rank of U in the partial ordering ⊲ of measures on κ, and O(κ) to be the rank of this partial ordering.
Examples in the theory of existential completeness
Authors: Hirschfeld Joram
Published: May 2006

Since A. Robinson introduced the classes of existentially complete and generic models, conditions which were interesting for elementary classes were considered for these classes. In [6] H. Simmons showed that with the natural definitions there are prime and saturated existentially complete models and these are very similar to their elementary counterparts which were introduced by Vaught [2, 2.3]. As Example 6 will show, there is a limit to the similarity—there are theories which have exactly two existentially complete models.

In [6] H. Simmons considers the following list of properties, shows that each property implies the next one and asks whether any of them implies the previous one:

1.1. T is ℵ0-categorical.

1.2. T has an ℵ0-categorical model companion.

1.3. ∣E∣ = 1.

1.4. ∣E∣ < .

1.5. T has a countable ∃-saturated model.

1.6. T has a ∃-prime model.

1.7. Each universal formula is implied by a ∃-atomic existential formula.

[The reader is referred to [1], [3], [4] and [6] for the definitions and background.

We only mention that T is always a countable theory. All the models under discussion are countable. Thus E is the class of countable existentially complete models and F and G, respectively, are the classes of countable finite and infinite generic models. For every class C,∣C∣ is the number of (countable) models in C.]
On the compactness of ℵ1 and ℵ2
Authors: di Prisco C. A. , Henle J.
Published: May 2006

In recent years, the Axiom of Determinateness (AD) has yielded numerous results concerning the size and properties of the first ω-many uncountable cardinals. Briefly, these results began with Solovay's discovery that ℵ1 and ℵ2 are measurable [8], [3], continued with theorems of Solovay, Martin, and Kunen concerning infinite-exponent partition relations [6], [3], Martin's proof that ℵn has confinality ℵ2 for 1 < n < ω, and very recently, Kleinberg's proof that the ℵn are Jonsson cardinals [4].

This paper was inspired by a very recent result of Martin from AD that ℵ1 is ℵ2-super compact. It was known for some time that AD implies ℵ1 is α-strongly compact for all ℵ < θ (where θ is the least cardinal onto which 2ω cannot be mapped, quite a large cardinal under AD), and that ADR implies that ℵ1, is α-super compact for all α < θ. A key open question had been whether or not ℵ1 is super compact under AD alone.

This paper comments on the method of Martin in several different ways. In §2, we will prove that ℵ1 is ℵ2-super compact, and then generalize the method to show that ℵ2 is ℵ3-strongly compact. In addition, we will demonstrate a limitation in the method by showing that the possible measures obtained on are not normal, and that the method cannot be extended to show that ℵ2 is ℵ4-strongly compact.
The stability function of a theory
Authors: Keisler H. Jerome
Published: May 2006

Let T be a complete theory with infinite models in a countable language. The stability function gT(κ) is defined as the supremum of the number of types over models of T of power κ. It is proved that there are only six possible stability functions, namely κ, κ + 2ω, κω, ded κ, (ded κ)ω, 2κ.
The nonconstructive content of sentences of arithmetic
Authors: Goodman Nicolas D.
Published: May 2006

This note is concerned with the old topic, initiated by Kleene, of the connections between recursive function theory and provability in intuitionistic arithmetic. More specifically, we are interested in the relationship between the hierarchy of degrees of unsolvability and the interdeducibility of cases of excluded middle. The work described below was motivated by a counterexample, to be given presently, which shows that that relationship is more complicated than one might suppose.

Let HA be first-order intuitionistic arithmetic. Let the symbol ⊢ mean derivability in HA. For each natural number n, let n¯ be the corresponding numeral. Let Ω be the standard model of arithmetic. Say that a sentence ϕ is true iff Ω⊨ ϕ. Now suppose ϕ(x) and Ψ(x) are formulas with only the variable x free. Suppose

Then it is natural to conjecture that {n∣Ω⊨Ψ(n¯)} is recursive in {n∣Ω⊨ϕ(n¯)}.

However, this conjecture is false. Consider the formula is a formalization of Kleene's T-predicate.
Some useful preservation theorems
Authors: Compton Kevin J.
Published: May 2006

The study of preservation theorems for first order logic was the focus of much research by model theorists in the 1960's. These theorems, which came to form the foundation for classical model theory, characterize first order sentences and theories that are preserved under operations such as the taking of unions or submodels (see Chang and Keisler [5] for a discussion of preservation theorems for first order logic). In current model theoretic research, logics richer than first order logic and applications of logic to other parts of mathematics have assumed the central position. In the former area, preservation theorems are not so important; in the latter, especially in applications to algebra, many of the techniques developed for proving these theorems have been useful.

In this paper I prove several preservation theorems for first order logic which I discovered while investigating the asymptotic growth of classes of finite combinatorial structures. The significance of these theorems lies in their applications to problems in finite combinatorics. Since the applications require combinatorial and analytical techniques that are not pertinent to logical questions discussed here, I shall present them in another paper [7].
On the elementary theory of pairs of real closed fields. II
Authors: Baur Walter
Published: May 2006

Let ℒ be the first order language of field theory with an additional one place predicate symbol. In [B2] it was shown that the elementary theory T of the class of all pairs of real closed fields, i.e., ℒ-structures ‹K, L›, K a real closed field, L a real closed subfield of K, is undecidable.

The aim of this paper is to show that the elementary theory Ts of a nontrivial subclass of containing many naturally occurring pairs of real closed fields is decidable (Theorem 3, §5). This result was announced in [B2]. An explicit axiom system for Ts will be given later. At this point let us just mention that any model of Ts, is elementarily equivalent to a pair of power series fields ‹R0((TA)), R1((TB))› where R0 is the field of real numbers, R1 = R0 or the field of real algebraic numbers, and B ⊆ A are ordered divisible abelian groups. Conversely, all these pairs of power series fields are models of Ts.

Theorem 3 together with the undecidability result in [B2] answers some of the questions asked in Macintyre [M]. The proof of Theorem 3 uses the model theoretic techniques for valued fields introduced by Ax and Kochen [A-K] and Ershov [E] (see also [C-K]). The two main ingredients are

(i) the completeness of the elementary theory of real closed fields with a distinguished dense proper real closed subfield (due to Robinson [R]),

(ii) the decidability of the elementary theory of pairs of ordered divisible abelian groups (proved in §§1-4).

I would like to thank Angus Macintyre for fruitful discussions concerning the subject. The valuation theoretic method of classifying theories of pairs of real closed fields is taken from [M].
Model-complete theories of formally real fields and formally p-adic fields
Authors: Wheeler William H.
Published: May 2006

The complete, model-complete theories of pseudo-algebraically closed fields were characterized completely in [11]. That work constituted the first step towards determining all the model-complete theories of fields in the usual language of fields. In this paper the second step is taken. Namely, the methods of [11] are extended to characterize the complete, model-complete theories of pseudo-real closed fields and pseudo-p-adically closed fields.

In order to unify the treatment of these two types of fields, the relevant properties of real closed ordered fields and p-adically closed valued fields are abstracted. The subsequent investigation of model-complete theories of fields is based entirely on these properties. The properties were selected in order to solve three problems: (1) finding universal theories with the joint embedding property, (2) finding first order conditions in the usual language of fields which are necessary and sufficient for a polynomial over a field to have a zero in a formally real or formally p-adic extension of that field, and (3) finding subgroups of Galois groups whose fixed fields are formally real or formally p-adic.

This paper is related to, and uses in §1 but not in the other sections, parts of K. McKenna's work [8] on model-complete theories of ordered fields and p-valued fields. However, the results herein are not direct consequences of his work, both because these results apply to a more general situation and because they use a different formal language. Concerning the latter point, in some instances, such as real closed ordered fields and p-adically closed valued fields, model-complete theories in expanded languages do yield model-complete theories of ordinary fields other than theories of pseudo-algebraically closed fields. However, in other cases, such as differentially closed fields, this is not so.
On classes closed under unions of chains
Authors: Miller Douglas E.
Published: May 2006

We improve a general theorem of J. A. Makowsky which characterizes, for a wide class of languages, those sentences θ such that both Mod(θ) and Mod(¬θ) are closed under unions of chains.
Reduction to first degree in quantificational S5
Authors: Carroll Michael J.
Published: May 2006

It is shown that the modally first-degree formulas of quantificational S5 constitute a reduction class.
Busy beaver sets and the degrees of unsolvability
Authors: Daley Robert P.
Published: May 2006

In this paper we show how some of the finite injury priority arguments can be simplified by making explicit use of the primitive notions of axiomatic computational complexity theory. Phrases such as “perform n steps in the enumeration of Wi” certainly bear witness to the fact that many of these complexity notions have been used implicitly from the early days of recursive function theory. However, other complexity notions such as that of an “honest” function are not so apparent, neither explicitly nor implicitly. Accordingly, one of the main factors in our simplification of these diagonalization arguments is the replacement of the characteristic function χA of a set A by the function νA, which is the next-element function of the set A. Another important factor is the use of busy beaver sets (see [3]) to provide the basis for the required diagonalizations thereby permitting rather simple and explicit descriptions of the sets constructed. Although the differences between the priority method and our method of construction are subtle, they are nonetheless real and noteworthy.

In preparation for the results which follow we devote the remainder of this section to the requisite definitions and notions as well as some preliminary lemmas. A more comprehensive discussion of many of the notions in this section can be found in [3]. Since we will be dealing extensively with relative computations most of our notions here have been correspondingly relativized.
On the Rowbottom M-ultrafilters
Authors: Feng Qi
Published: May 2006

We show that M ⊨ κ is a completely Ramsey cardinal iff there is a Rowbottom M-ultrafilter on κ.
Properties of subtle cardinals
Authors: Henrion Claudia
Published: May 2006

Subtle cardinals were first introduced in a paper by Jensen and Kunen [JK]. They show that ifκis subtle then ◇κholds. Subtle cardinals also play an important role in [B1], where Baumgartner proposed that certain large cardinal properties should be considered as properties of their associated normal ideals. He shows that in the case of ineffables, the ideals are particularly useful, as can be seen by the following theorem,κis ineffable if and only ifκis subtle andΠ½-indescribableandthe subtle andΠ½-indescribable ideals cohere, i.e. they generate a proper, normal ideal (which in fact turns out to be the ineffable ideal).

In this paper we examine properties of subtle cardinals and consider methods of forcing that destroy the property of subtlety while maintaining other properties. The following is a list of results.

1) We relativize the following two facts about subtle cardinals:

i) ifκisn-subtle then {α<κ:αis notn-subtle} isn-subtle, and

ii) ifκis (n+ 1)-subtle then {α<κ:αisn-subtle} is in the (n+ 1)-subtle filter to subsets ofκ:

i′) ifAis ann-subtle subset ofκthen {α ϵ A:A∩αis notn-subtle} isn-subtle, and

ii′) ifAis an (n+ 1)-subtle subset ofκthen {α ϵ A:A∩αisn-subtle} is (n+ 1)-subtle.

2) We show that although a stationary limit of subtles is subtle, a subtle limit of subtles is not necessarily 2-subtle.

3) In §3 we use the technique of forcing to turn a subtle cardinal into aκ-Mahlo cardinal that is no longer subtle.

4) In §4 we extend the results of §3 by showing how to turn an (n+ 1)-subtle cardinal into ann-subtle cardinal that is no longer (n+ 1)-subtle.
Relative lawlessness in intuitionistic analysis
Authors: Moschovakis Joan Rand
Published: May 2006

This paper introduces, as an alternative to the (absolutely) lawless sequences of Kreisel and Troelstra, a notion of choice sequence lawless with respect to a given class of lawlike sequences. For countable , the class of -lawless sequences is comeager in the sense of Baire. If a particular well-ordered class of sequences, generated by iterating definability over the continuum, is countable then the -lawless sequences satisfy the axiom of open data and the continuity principle for functions from lawless to lawlike sequences, but fail to satisfy Troelstra's extension principle. Classical reasoning is used.
Elimination of quantifiers for ordered valuation rings
Authors: Dickmann M. A.
Published: May 2006

Cherlin and Dickmann [2] proved that the theory RCVR of real closed (valuation) rings admits quantifier-elimination (q.e.) in the language ℒ = {+, −, ·, 0, 1, <, ∣} for ordered rings augmented by the divisibility relation “∣”. The purpose of this paper is to prove a form of converse of this result:

Theorem. Let T be a theory of ordered commutative domains (which are not fields), formulated in the language ℒ. In addition we assume that:

(1) The symbol “∣” is interpreted as the honest divisibility relation:

(2) The following divisibility property holds in T:

If T admits q.e. in ℒ, then T = RCVR.

We do not know at present whether the restriction imposed by condition (2) can be weakened.

The divisibility property (DP) has been considered in the context of ordered valued fields; see [4] for example. It also appears in [2], and has been further studied in Becker [1] from the point of view of model theory. Ordered domains in which (DP) holds are called in [1] convexly ordered valuation rings, for reasons which the proposition below makes clear. The following summarizes the basic properties of these rings:

Proposition I [2, Lemma 4]. (1) Let A be a linearly ordered commutative domain. The following are equivalent:

(a) A is a convexly ordered valuation ring.

(b) Every ideal (or, equivalently, principal ideal) is convex in A.

(c) A is a valuation ring convex in its field of fractions quot(A).

(d) A is a valuation ring and its maximal ideal MA is convex (in A or, equivalently, in quot (A)).

(e) A is a valuation ring and its maximal ideal is bounded by ± 1.
Simple r. e. degree structures
Authors: Lubarsky Robert S.
Published: May 2006

Much of recursion theory centers on the structures of different kinds of degrees. Classically there are the Turing degrees and r. e. Turing degrees. More recently, people have studied α-degrees for α an ordinal, and degrees over E-closed sets and admissible sets. In most contexts, deg(0) is the bottom degree and there is a jump operator' such that d' is the largest degree r. e. in d and d' > d. Both the degrees and the r. e. degrees usually have a rich structure, including a relativization to the cone above a given degree.

A natural exception to this pattern was discovered by S. Friedman [F], who showed that for certain admissible ordinals β the β-degrees ≥ 0′ are well-ordered, with successor provided by the jump.

For r. e. degrees, natural counterexamples are harder to come by. This is because the constructions are priority arguments, which require only mild restrictions on the ground model. For instance, if an admissible set has a well-behaved pair of recursive well-orderings then the priority construction of an intermediate r. e. degree (i.e., 0 < d < 0′) goes through [S]. It is of interest to see just what priority proofs need by building (necessarily pathological) admissible sets with few r. e. degrees.

Harrington [C] provides an admissible set with two r. e. degrees, via forcing. A limitation of his example is that it needs ω1 (more accurately, a local version thereof) as a parameter. In this paper, we find locally countable admissible sets, some with three r. e. degrees and some with four.
A note on a proof of Hilbert's second ε-theorem
Authors: Ferrari Pier Luigi
Published: May 2006

The aim of this short note is to correct an error in the proof in [1], more precisely in Remark 1 on page 395, where it is stated that any improper word has rank ≥2. This claim is false; and, consequently, Remark 2, asserting that any 1,0-deduction does not contain improper Q-terms, also fails immediately. In fact, let us consider the word

It is easily seen that the rank of W is 1, but W is obviously improper. We remark that it is possible, in the same way, to give examples of improper words of rank 1 containing (without subordination) ε-subterms of arbitrarily high rank. In the following section we sketch a corrected version of the proof in order to eliminate all improper ε-terms.

We refer to the notation and definitions of [1]. A more extended description of the theories involved can be found in [2].
Completeness of transfinite evaluation in an extension of the lambda calculus
Authors: Sanchis Luis E.
Published: May 2006

The lambda calculus was conceived by Church, and to some extent by Curry (see [1] and [2]), as a general theory of functions, more precisely as a formalization of two basic functional concepts: application and abstraction. This claim to universality was impossible to maintain, for it soon became apparent that functions in the calculus are required to have properties which are by no means universal. Self-application is certainly a very special feature, but more relevant from our point of view is the existence of fixed points, which is definitely a nonuniversal property of functions. This situation was not ignored, but was considered rather as a form of inconsistency very much related to the paradoxes of set theory (for example, see the discussion of the paradoxical combinator in [2]).

More recently, the lambda calculus has been studied by people in computer science, and as a result the algorithmic nature of the system has been more explicitly recognized. Eventually, the right approach was taken by D. Scott (see [4] and [5]) who restricted the objects of the calculus to continuous functionals over complete lattices, which can be combined in structures where application and abstraction are properly interpreted. It soon became clear that complete lattices were not necessary, and more general structures were introduced. On the other hand the requirement of continuity was essential for the construction, and has remained a basic feature. It is one of the purposes of this paper to show that in the general situation continuity can be replaced by monotonicity.

The work of Scott was extended by Wadsworth [6], who gave a precise formulation of the operational semantics, and proved the equivalence to Scott's interpretation.
The contributions of Alfred Tarski to algebraic logic
Authors: Monk J. Donald
Published: May 2006

One of the most extensive parts of Tarski's contributions to logic is his work on the algebraization of the subject. His work here involves Boolean algebras, relation algebras, cylindric algebras, Boolean algebras with operators, Brouwerian algebras, and closure algebras. The last two are less developed in his work, although his contributions are basic to other work in those subjects. At any rate, not being conversant with the latest developments in those fields, we shall concentrate on an exposition of Tarski's work in the first four areas, trying to put them in the perspective of present-day developments.

For useful comments, criticisms, and suggestions, the author is indebted to Steven Givant, Leon Henkin, Wilfrid Hodges, Bjarni Jónsson, Roger Lyndon, and Robert Vaught.
Why Solovay real produces Cohen real
Authors: Pawlikowski Janusz
Published: May 2006

An explanation is given of why, after adding to a model M of ZFC first a Solovay real r and next a Cohen real c, in M[r] [c] a Cohen real over M[c] is produced. It is also shown that a Solovay algebra iterated with a Cohen algebra can be embedded into a Cohen algebra iterated with a Solovay algebra.
The ideal structure of existentially closed algebras
Authors: Eklof Paul C. , Mez Hans-Christian
Published: May 2006

Throughout this paper, ⊿ will denote a commutative ring with multiplicative identity, 1. The algebras we consider will be associative ⊿-algebras which are not necessarily commutative and do not necessarily contain a multiplicative identity. By standard methods, every ⊿-algebra can be embedded in an existentially closed (e.c.) Δ-algebra—and even in one which is existentially universal (e.u.). (See §0 for more details.)

We shall be studying the ideals of e.c. ⊿-algebras. Since every ideal is a sum of principal ideals, a natural place to begin is with principal ideals. In §1 we show that for an algebraically closed (a.c.) ⊿-algebra A, and elements a, b in A, whether or not b belongs to the principal ideal (a)A generated by a, depends only on the underlying ⊿-module structure of A; more precisely, for b to belong to (a)A it is necessary and sufficient that b satisfies every positive existential formula θ(ν) in the language of ⊿-modules which is satisfied by a (cf. Corollary 1.8). For special classes of rings ⊿ this condition can be simplified (Proposition 1.10): e.g. for Prüfer rings it is enough to consider formulas of the form ∃x(λx = μν); and for regular rings it is enough to consider formulas μν = 0 (where λ, μ ∈ ⊿).

In §2 we use the results of §1 to study e.c. and e.u. algebras over a principal ideal domain (p.i.d.) ⊿ (Note that for ⊿ = Z this includes the case of e.c. rings.) We obtain a necessary and sufficient condition for an a.c. ⊿-algebra to be e.c. (Theorem 2.4). We also show (Theorem 2.2) that in an a.c. ⊿-algebra A every element that is divisible by all nonzero elements of ⊿ belongs to the divisible part D(A) of A. (It should be noted that, while a.c. ⊿-modules are always divisible [ES], an e.c. ⊿-algebra is never divisible: see the end of §0. Moreover, an e.c. ⊿-algebra always contains torsion-free elements: see Remark 2.3.) We prove that every bounded ideal in an a.c. ⊿-algebra is principal (2.7).
The independence relation in separably closed fields
Authors: Srour G.
Published: May 2006

We give an alternative proof of the stability of separably closed fields of fixed Éršov invariant to the one given in [W]. We show that in case the Éršov invariant is finite, the theory is in fact equational. We also characterize the independence relation in those theories.
An interpretation of Martin-Löf's type theory in a type-free theory of propositions
Authors: Smith Jan
Published: May 2006

We present a formal theory of propositions and combinator terms, and in this theory we give an interpretation of Martin-Löf's type theory. The construction of the interpretation is inspired by the semantics for type theory, but it can also be viewed as a formalized realizability interpretation.
Complexity of κ-ultrafilters and inner models with measurable cardinals
Authors: Sureson Claude
Published: May 2006

The purpose of this paper is to establish a connection between the complexity of κ-ultrafilters over a measurable cardinal κ, and the existence of ascending Rudin-Keisler chains of κ-ultrafilters and of inner models with several measurable cardinals.

If V is a model of ZFC + “There exists a measurable cardinal κ”, then V satisfies “There exists a normal κ-ultrafilter”, that is to say a “simple” κ-ultrafilter. The only known examples of “complex” κ-ultrafilters have been constructed by Kanamori [2], Ketonen [4] and Kunen (cf. [2]) with stronger hypotheses than measurability: compactness or supercompactness. Using the notions of skies and constellations defined by Kanamori [2] for the measurable case, and which witness the complexity of a κ-ultrafilter, we shall show the necessity of such assumptions, namely:

Theorem 1. If λ < κ is a strongly inaccessible cardinal, the existence of a κ-ultrafilter with more than λ constellations implies that there is an inner model with two measurable cardinals if λ = ω and λ + 1 measurable cardinals otherwise.

Theorem 2. Let θ < κ be an arbitrary ordinal. If there is a κ-ultrafilter such that the order-type of its skies is greater than ωθ, then there exists an inner model with θ + 1 measurable cardinals.

And as a corollary, we obtain:

Theorem 3. Let μ < κ be a regular cardinal. If there exists a κ-ultrafilter containing the closed-unbounded subsets of κ and {α < κ: cf(α) = μ}, then there is an inner model with two measurable cardinals if μ = ω, and μ + 1 measurable cardinals otherwise.
Banach games
Authors: Freiling Chris
Published: May 2006

Abstract.

Banach introduced the following two-person, perfect information, infinite game on the real numbers and asked the question: For which sets A ⊆ R is the game determined?

Rules: The two players alternate moves starting with player I. Each move an is legal iff it is a real number and 0 < an, and for n > 1, an < an−1. The first player to make an illegal move loses. Otherwise all moves are legal and I wins iff exists and .

We will look at this game and some variations of it, called Banach games. In each case we attempt to find the relationship between Banach determinacy and the determinacy of other well-known and much-studied games.
There are not exactly five objects
Authors: Blass Andreas
Published: May 2006

We exhibit a Horn sentence expressing the statement of the title; the construction generalizes to arbitrary primes in place of five.
Expansions of models of ω-stable theories
Authors: Buechler Steven
Published: May 2006

We prove that every relation-universal model of an ω-stable theory is saturated. We also show there is a large class of ω-stable theories for which every resplendent model is homogeneous.
Heine-Borel does not imply the Fan Theorem
Authors: Moerdijk Ieke
Published: May 2006

This paper deals with locales and their spaces of points in intuitionistic analysis or, if you like, in (Grothendieck) toposes. One of the important aspects of the problem whether a certain locale has enough points is that it is directly related to the (constructive) completeness of a geometric theory. A useful exposition of this relationship may be found in [1], and we will assume that the reader is familiar with the general framework described in that paper.

We will consider four formal spaces, or locales, namely formal Cantor space C, formal Baire space B, the formal real line R, and the formal function space RR being the exponential in the category of locales (cf. [3]). The corresponding spaces of points will be denoted by pt(C), pt(B), pt(R) and pt(RR). Classically, these locales all have enough points, of course, but constructively or in sheaves this may fail in each case. Let us recall some facts from [1]: the assertion that C has enough points is equivalent to the compactness of the space of points pt(C), and is traditionally known in intuitionistic analysis as the Fan Theorem (FT). Similarly, the assertion that B has enough points is equivalent to the principle of (monotone) Bar Induction (BI). The locale R has enough points iff its space of points pt(R) is locally compact, i.e. the unit interval pt[0, 1] ⊂ pt(R) is compact, which is of course known as the Heine-Borel Theorem (HB). The statement that RR has enough points, i.e. that there are “enough” continuous functions from R to itself, does not have a well-established name. We will refer to it (not very imaginatively, I admit) as the principle (EF) of Enough Functions.
A note on interpretations of many-sorted theories
Authors: Hook Julian L.
Published: May 2006

Whenever many-sorted theories are discussed in logic texts (e.g., [3, pp. 483–485]), it is fashionable to observe that every many-sorted theory can be effectively replaced by an equally powerful one-sorted theory *. The theory * contains for each sort σ of a unary predicate symbol Sσ used to indicate that an individual is of sort σ; the nonlogical axioms of * are the “translations” of those of together with axioms asserting that there is at least one individual of each sort and that all function symbols behave properly with respect to sorts. This observation suggests that perhaps many-sorted theories are no more useful than one-sorted theories. That this is not always the case has been pointed out previously [1, p. 13]. The content of this note is that can be interpretable in without * being interpretable in *.

If a function symbol f in a many-sorted theory takes as its arguments n terms a1,…, an of sorts σ1, …, σn, respectively and produces a term fa1 … an of sort σ, then f is said to be of type (σ1, …, σn;σ). Likewise, a predicate symbol is of type (σ1, …, σn) if it takes as its arguments n terms of sorts σ1, …, σn. We assume that for each sort σ there is a predicate symbol = σ of type (σ, σ).
Disturbing arithmetic
Authors: Grilliot Thomas J.
Published: May 2006

One long-range objective of logic is to find models of arithmetic with noteworthy properties, perhaps properties that imply some long-standing number theoretic conjectures. In areas of mathematics such as algebra or set theory, new models are often made by extending old models, that is, by adjoining new elements to already existing models. Usually the extension retains most of the characteristics of the old model with at least one exception that makes the new model interesting. However, such a scheme is difficult in the area of arithmetic. Many interesting properties of the fine structure of arithmetic are diophantine and hence unchangeable in extensions. For instance, one cannot change a prime number into a composite one by adjoining new elements.

One could possibly get around this diophantine difficulty in one of two ways. One way is to change the usual language of addition and multiplication to an equivalent language that does not transmit so much information to extensions. For instance, multiplication is definable from the squaring function, as one sees from the identity 2xy = (x + y)2 − x2 − y2, and the squaring function in turn is definable either from the unary square predicate (as one sees from the fact that n = m2 if n and n + 2m + 1 are successive squares) or from the divisor relation (as one sees from the fact that n = m2 if n is the smallest number such that m divides n and m + 1 divides n + m). Either of these two alternatives to multiplication might make for interesting extensions.
A new proof for Craig's theorem
Authors: Bellot P.
Published: May 2006

Craig's theorem is a result about the cardinality of a proper basis for the theory of combinators. Its proof given in [3] was shown to be incomplete by André Chauvin [2]. By using a different approach, we give a very short proof of this theorem. We use the notation of [1].

Definition 1. A combinator Q is proper if there exists a natural number n such that for arbitrary variables x1,…,xn we have the following contraction rule:

where C is a pure combination of the variables x1,…,xn. Q is to be understood as an abstract symbol, not as a combination of S and K's. Therefore Q comes with a contraction rule.

Definition 2. A set (Q1,…, Qm} of combinators is a basis for combinatory logic if for every finite set {x1,…, xk} of variables and every pure combination C of these variables, there exists a pure combination Q of Q1,…, Qm such that Qx1 … xk ↠ C.

Craig's Theorem. Every basis for combinatory logic containing only proper combinators contains at least two elements.

Proof. Let {Q} be a singleton basis for combinatory logic, and let us show that we cannot have combinatory completeness. This is an easy consequence of the next two lemmas.

Lemma 1. Q is a projection. That is, Qx1 … xn ↠ xj, for some j.

Proof. Let I be a proper combination of Q such that Ix ↠ x for a variable x, and let M be a term such that Ix ↠ M → x and M → x is a nontrivial contraction.
Subgroups of a free group and the axiom of choice
Authors: Howard Paul E.
Published: May 2006

Nielsen [7] has proved that every subgroup of a free group of finite rank is free. The theorem was later strengthened by Schreier [8] by eliminating the finiteness restriction on the rank. Several proofs of this theorem (known as the Nielsen-Schreier theorem, henceforth denoted by NS) have appeared since Schreier's 1927 paper (see [1] and [2]). All proofs of NS use the axiom of choice (AC) and it is natural to ask whether NS is equivalent to AC. Läuchli has given a partial answer to this question by proving [6] that the negation of NS is consistent with ZFA (Zermelo-Fraenkel set theory weakened to permit the existence of atoms). By the Jech-Sochor embedding theorem (see [3] and [4]) ZFA can be replaced by ZF. Some form of AC, therefore, is needed to prove NS. The main purpose of this paper is to give a further answer to this question.

In §2 we prove that NS implies ACffin (the axiom of choice for sets of finite sets). In §3 we show that a strengthened version of NS implies AC and in §4 we give a partial list of open problems.

Let y be a set; ∣y∣ denotes the cardinal number of y and (y) is the power set of y. If p is a permutation of y and t ∈ y, the p-orbit of t is the set {pn(t): n is an integer}. If

we call p a cyclic permutation of y. If f is a function with domain y and x ⊆ y, f″x denotes the set {f(t):t ∈ x}. If A is a subset of a group (G, °) (sometimes (G, °) will be denoted by G) then A−1 = {x−1:x ∈ A} and [A] denotes the subgroup of G generated by A.
Decidable regularly closed fields of algebraic numbers
Authors: Dries Lou van den , Smith Rick L.
Published: May 2006

A field K is regularly closed if every absolutely irreducible affine variety defined over K has K-rational points. This notion was first isolated by Ax [A] in his work on the elementary theory of finite fields. Later Jarden [J2] and Jarden and Kiehne [JK] extended this in different directions. One of the primary results in this area is that the elementary properties of a regularly closed field K with a free Galois group (on either finitely or countably many generators) are determined by the set of integer polynomials in one indeterminate with a zero in K. The method of proof employed in [J1], [J2] and [JK] is unusual for algebra since it is a measure-theoretic argument. In this brief summary we have not made any attempt at completeness. We refer the reader to the recent paper of Cherlin, van den Dries, and Macintyre [CDM] and to the forthcoming book by Fried and Jarden [FJ] for a more thorough discussion of the latest results. We would like to thank Moshe Jarden, Angus Macintyre, and Zoe Chatzidakis for their comments on an earlier version of this paper.

A countable field K is ω-free if the absolute Galois group , where is the algebraic closure of K and is the free profinite group on ℵ0 generators.
The universal complementation property
Authors: Downey R.G. , Remmel J.B.
Published: May 2006

Let V∞ be a fully effective infinite dimensional vector space over a recursive field F. That is, we assume that the universe of V∞ is a recursive set, the operations of addition and scalar multiplication are recursive, and there is a uniform effective procedure to decide whether any finite set {υ0, …, υn} of vectors from V∞ is independent. The lattice of recursively enumerable subspaces has been extensively studied since its introduction by Metakides and Nerode [MN1] (see for example, [Do2], [Gu], [KR], [Re1], [Re2], and [Sh]). For those unfamiliar with the literature on , we shall give a list of basic definitions required for this paper in §0.

It is well known that complements in V∞ are not unique. For example, in [Re2] Remmel constructed r.e. spaces M1 and M2 and co-r.e. spaces Q1 and Q2 such that for all i, j ∈ {1, 2}, Mi ⊕ Qj = V∞ and M1 is supermaximal, M2 is not maximal, Q1 has a fully extendible basis, and Q2 has no extendible basis. We say a subspace Q of V∞ is fully co-r.e. if Q is generated by a co-r.e. subset of some recursive basis of V∞. Downey [Do2] has shown that every r.e. subspace of V∞ has a complement which is a fully co-r.e. subspace. Moreover suppose Q is any fully co-r.e. subspace, say Q = (C)* where C is a co-r.e. subset of a recursive basis B of V∞; if C is nonrecursive, then it is shown in [Do2] that Q has a decidable complement as well as a nondecidable nowhere simple complement.
Church-Rosser theorem for typed functional systems
Authors: Koletsos George
Published: May 2006

Introduction. This paper contains a new proof of the Church-Rosser theorem for the typed λ-calculus, which also applies to systems with infinitely long terms.

The ordinary proof of the Church-Rosser theorem for the general untyped calculus goes as follows (see [1]). If is the binary reduction relation between the terms we define the one-step reduction 1 in such a way that the following lemma is valid.

Lemma. For all terms a and b we have: ab if and only if there is a sequence a = a0, …, an = b, n ≥ 0, such that aiiai + 1for 0 ≤ i < n.

We then prove the Church-Rosser property for the relation 1 by induction on the length of the reductions. And by combining this result with the above lemma we obtain the Church-Rosser theorem for the relation .

Unfortunately when we come to infinite terms the above lemma is not valid anymore. The difficulty is that, assuming the hypothesis for the infinitely many premises of the infinite rule, there may not exist an upper bound for the lengths n of the sequences ai = a0, …, an = bi (i < α); cf. the infinite rule (iv) in §6.

A completely new idea in the case of the typed λ-calculus would be to exploit the type structure in the way Tait did in order to prove the normalization theorem. In this we succeed by defining a suitable predicate, the monovaluedness predicate, defined over the type structure and having some nice properties. The key notion permitting to define this predicate is the notion of I-form term (see below). This Tait-type proof has a merit, namely that it can be extended immediately to the case of infinite terms.
On the number of independent partitions
Authors: Tsuboi Akito
Published: May 2006

In [3], Shelah defined the cardinals κn(T) and , for each theory T and n < ω. κn(T) is the least cardinal κ without a sequence (pi)i<κ of complete n-types such that pi is a forking extension of pj for all i < j < κ. It is essential in computing the stability spectrum of a stable theory. On the other hand is called the number of independent partitions of T. (See Definition 1.2 below.) Unfortunately this invariant has not been investigated deeply. In the author's opinion, this unfortunate situation of is partially due to the fact that its definition is complicated in expression. In this paper, we shall give equivalents of which can be easily handled.

In §1 we shall state the definitions of κn(T) and . Some basic properties of forking will be stated in this section. We shall also show that if = ∞ then T has the independence property.

In §2 we shall give some conditions on κ, n, and T which are equivalent to the statement . (See Theorem 2.1 below.) We shall show that does not depend on n. We introduce the cardinal ı(T), which is essential in computing the number of types over a set which is independent over some set, and show that ı(T) is closely related to . (See Theorems 2.5 and 2.6 below.) The author expects the reader will discover the importance of via these theorems.

Some of our results are motivated by exercises and questions in [3, Chapter III, §7]. The author wishes to express his heartfelt thanks to the referee for a number of helpful suggestions.
Pas d'imaginaires dans l'infini!
Authors: Pillay Anand , Poizat Bruno
Published: May 2006

Dans Poizat [1981], le second auteur a montré qu'un sous-groupe infiniment définissable d'un groupe stable était intersection de sous-groupes définissables; il a posé la question de savoir si une relation d'équivalence E, infiniment définissable dans un modèle M d'une théorie stable T, était conjonction de relations d'équivalence définissables. Nous allons voir ici que c'est presque exact: c'est vrai si T est totalement transcendante, et, dans le cas général de stabilité E a toujours un raffinement E1 (plus précisément, E1 est la conjonction de E et de la relation “x et y ont même type”) qui a cette propriété; cela montre que cette relation E n'introduit pas d'imaginaires d'une nature vraiment différente de celle des imaginaires de Shelah: dans une théorie stable, un imaginaire infinitaire n'est rien d'autre qu'un ensemble d'imaginaires finis.

La démonstration du théorème principal de cette note s'appuie lourdement sur la construction Meq de Shelah, la machinerie de la déviation, les paramètres imaginaires canoniques pour la définition d'un type stable, etc…. Pour tout cela, les références adéquates sont Shelah [1978], Pillay [1983], et Poizat [1985, Chapitre 16].

Nouscommençons par préciser ce que nous entendons par “relation d'équivalence infiniment définissable”: une collection de formules e(, ȳ), et ȳ étant de longueur n, telle que, pour tout modèle M de T, les couples (, ȳ) qui les satisfont toutes forment une rélation d'équivalence E.
Intermediate predicate logics determined by ordinals
Authors: Minari Pierluigi , Takano Mitio , Ono Hiroakira
Published: May 2006

For each ordinal α > 0, L(α) is the intermediate predicate logic characterized by the class of all Kripke frames with the poset α and with constant domain. This paper will be devoted to a study of logics of the form L(α). It will be shown that for each uncountable ordinal of the form α + η with a finite or a countable η(> 0), there exists a countable ordinal of the form β + η such that L(α + η) = L(β + η). On the other hand, such a reduction of ordinals to countable ones is impossible for a logic L(α) if α is an uncountable regular ordinal. Moreover, it will be proved that the mapping L is injective if it is restricted to ordinals less than ωω, i.e. α ≠ β implies L(α) ≠ L(β) for each ordinal α, β ≤ ωω.