bluuebunny/crossref_metadata_2025 huggingface dataset:
Countable functionals and the projective hierarchy
Authors: Normann Dag
Published: May 2006

Kleene [7] and Kreisel [8] defined independently the countable (continuous) functionals. Kleene [7] defined the countable functionals of type k to be total functionals of type k acting in a continuous way when restricted to countable arguments of type k − 1. He also defined the associates for countable functionals. They are functions α: N → N containing information about how the functional acts on countable arguments. Kleene [7] showed that the countable functionals are closed under the computations derived from S1–S9 of his paper [6], and that every computable functional has a recursive associate.

Kreisel defined the continuous functionals to be equivalence-classes of associates. By his definition it is meaningless to let a continuous functional act upon anything but continuous arguments.

One disadvantage of Kleene's approach is that two different functionals may have the same associates We will later see that there may be two functionals φ1 and φ2 with the same associates but such that the relations

are not the same.

In more recent papers on the countable functionals it is normal to regard the hierarchy 〈Ct(k)〉kϵN of countable functionals as a type-structure such that the functionals in Ct(k + 1) are maps from Ct(k) to N(Ct(0) = N), see e.g. Bergstra [1] and Gandy and Hyland [3].

We will then enjoy the streamlined formalism of a type-structure in which S1–S9 have meaning, but avoid the ambiguities of Kleene's original approach.

We will presuppose a brief familiarity with the theory of the countable functionals.
Discontinuities of provably correct operators on the provably recursive real numbers
Authors: Collins William J. , Young Paul
Published: May 2006

In this paper we continue, from [2], the development of provably recursive analysis, that is, the study of real numbers defined by programs which can be proven to be correct in some fixed axiom systemS. In particular we develop the provable analogue of an effective operator on the setof recursive real numbers, namely, a provably correct operator on the setof provably recursive real numbers. In Theorems 1 and 2 we exhibit a provably correct operator onwhich is discontinuous at 0; we thus disprove the analogue of the Ceitin-Moschovakis theorem of recursive analysis, which states that every effective operator onis (effectively) continuous. Our final theorems show, however, that no provably correct operator oncan be proven (inS) to be discontinuous.
Algebraic semantics for quasi-classical modal logics
Authors: Blok W.J. , Köhler P.
Published: May 2006

A well-known result, going back to the twenties, states that, under some reasonable assumptions, any logic can be characterized as the set of formulas satisfied by a matrix 〈,F〉, whereis an algebra of the appropriate type, andFa subset of the domain of, called the set of designated elements. In particular, every quasi-classical modal logic—a set of modal formulas, containing the smallest classical modal logicE, which is closed under the inference rules of substitution and modus ponens—is characterized by such a matrix, wherenow is a modal algebra, andFis a filter of. If the modal logic is in fact normal, then we can do away with the filter; we can study normal modal logics in the setting of varieties of modal algebras. This point of view was adopted already quite explicitly in McKinsey and Tarski [8]. The observation that the lattice of normal modal logics is dually isomorphic to the lattice of subvarieties of a variety of modal algebras paved the road for an algebraic study of normal modal logics. The algebraic approach made available some general results from Universal Algebra, notably those obtained by Jónsson [6], and thereby was able to contribute new insights in the realm of normal modal logics [2], [3], [4], [10].

The requirement that a modal logic be normal is rather a severe one, however, and many of the systems which have been considered in the literature do not meet it. For instance, of the five celebrated modal systems, S1–S5, introduced by Lewis, S4 and S5 are the only normal ones, while only SI fails to be quasi-classical. The purpose of this paper is to generalize the algebraic approach so as to be applicable not just to normal modal logics, but to quasi-classical modal logics in general.
The relative expressive power of some logics extending first-order logic
Authors: Cowles John
Published: May 2006

In recent years there has been a proliferation of logics which extend first-order logic, e.g., logics with infinite sentences, logics with cardinal quantifiers such as “there exist infinitely many…” and “there exist uncountably many…”, and a weak second-order logic with variables and quantifiers for finite sets of individuals. It is well known that first-order logic has a limited ability to express many of the concepts studied by mathematicians, e.g., the concept of a wellordering. However, first-order logic, being among the simplest logics with applications to mathematics, does have an extensively developed and well understood model theory. On the other hand, full second-order logic has all the expressive power needed to do mathematics, but has an unworkable model theory. Indeed, the search for a logic with a semantics complex enough to say something, yet at the same time simple enough to say somethingabout, accounts for the proliferation of logics mentioned above. In this paper, a number of proposed strengthenings of first-order logic are examined with respect to their relative expressive power, i.e., given two logics, what concepts can be expressed in one but not the other?

For the most part, the notation is standard. Most of the notation is either explained in the text or can be found in the book [2] of Chang and Keisler. Some notational conventions used throughout the text are listed below: the empty set is denoted by ∅.
Twilight graphs
Authors: Dekker J. C. E.
Published: May 2006

This paper deals primarily with countable, simple, connected graphs and the following two conditions which are trivially satisfied if the graphs are finite:

(a) there is an edge-recognition algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to decide whether they are adjacent,

(b) there is a shortest path algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to find a minimal path joining them.

A graph G = ‹ν, η› with ν as set of vertices and η as set of edges is an α-graph if it satisfies (a); it is an ω-graph if it satisfies (b). G is called r.e. (isolic) if the sets ν and η are r.e. (isolated). While every ω-graph is an α-graph, the converse is false, even if G is r.e. or isolic. Several basic properties of finite graphs do not generalize to ω-graphs. For example, an ω-tree with more than one vertex need not have two pendant vertices, but may have only one or none, since it may be a 1-way or 2-way infinite path. Nevertheless, some elementary propositions for finite graphs G = ‹ν, η› with n = card(ν), e = card(η), do generalize to isolic ω-graphs, e.g., n − 1 ≤ e ≤ n(n − 1)/2. Let N and E be the recursive equivalence types of ν and η respectively. Then we have for an isolic α-tree G = ‹ν, η›: N = E + 1 iff G is an ω-tree. The theorem that every finite graph has a spanning tree has a natural, effective analogue for ω-graphs.

The structural difference between isolic α-graphs and isolic ω-graphs will be illustrated by: (i) every infinite graph is isomorphic to some isolic α-graph; (ii) there is an infinite graph which is not isomorphic to any isolic ω-graph.

An isolic α-graph is also called a twilight graph. There are c such graphs, c denoting the cardinality of the continuum.
Analysis without actual infinity
Authors: Mycielski Jan
Published: May 2006

We define a first-order theory FIN which has a recursive axiomatization and has the following two properties. Each finite part of FIN has finite models. FIN is strong enough to develop that part of mathematics which is used or has potential applications in natural science. This work can also be regarded as a consistency proof of this hitherto informal part of mathematics. In FIN one can count every set; this permits one to prove some new probabilistic theorems.
A consistent prepositional logic without any finite models
Authors: McKay C. G.
Published: May 2006

Some propositional logics (e.g. the classical system) can be characterized by a finite model, while others (e.g. Heyting's) which have the finite model property (FMP) can be characterized by an infinite set of finite models. Still others (e.g. certain extensions of Heyting's logic) which lack the FMP can only be characterized by a set of models, at least one of which is infinite. Yet all these logics admit finite models even though they may not be characterized by them. (For example, they all admit the 2-element Boolean algebra as a model in the sense that all their theorems are valid on that algebra when the propositional connectives are interpreted in the usual manner.) The object of the present paper is to give a (not too artificial) example of a propositional logic which is consistent and which admits only infinite models. It therefore lacks the FMP in a very strong sense. Such a propositional logic, I shall call hyperinfinite. The existence of hyperinfinite logics was already plausible from a result in abstract algebra which says that there are varieties of algebras of which the only finite element is the trivial algebra (see [3]).

I wish to thank Professor A. S. Troelstra, Amsterdam, for comments on an early version of this paper. The constructive criticism of two anonymous referees has also been useful.

The hyperinfinite propositional logic to be described is obtained from Positive Logic—the negative-free part of Heyting's logic—by adjoining certain axioms which govern the use of a unary modal connective.
Minimality in the Δ⅓-degrees
Authors: Welch Philip
Published: May 2006

We show in ZFC, assuming all reals have sharps, that a countable collection of Δ⅓-degrees without a minimal upper bound implies the existence of inner models with measurable cardinals.
Prikry forcing at κ+ and beyond
Authors: Mitchell William
Published: May 2006

If U is a normal measure on κ then we can add indiscernibles for U either by Prikry forcing [P] or by taking an iterated ultrapower which will add a sequence of indiscernibles for over M. These constructions are equivalent: the set C of indiscernibles for added by the iterated ultrapower is Prikry generic for [Mat]. Prikry forcing has been extended for sequences of measures of length by Magidor [Mag], and his method readily extends to . In this case the measure U is replaced by a sequence of measures and the set C of indiscernibles is replaced by a system of indiscernibles for : is a function such that (κ, β) is a set of indiscernibles for (κ, β) for each . The equivalence between forcing and iterated ultra-powers still holds true for such sequences: there is an interated ultrapower j: V → M (which is defined in detail later in this paper) such that the system of indiscernibles for j() constructed by j is Magidor generic over M.

The construction of the system of indiscernibles works equally well for o(κ) ≧ κ+. Radin has defined a variant of Prikry forcing which also works for o(κ) > κ+ ([R]; see also [Mi82] where Radin forcing is applied specifically to sequences of measures, rather than to hypermeasures as in Radin's paper), but Radin's forcing is weaker than Magidor's extension of Prikry forcing in the sense that the system of indiscernibles generated by the interated ultrapower is not Radin generic for j(), but only the set . That is, an indiscernible does not belong to a specific measure, but only to the whole sequence of measures on the cardinal κ.
Some consistency proofs and a characterization of inconsistency proofs in illative combinatory logic
Authors: Bunder M. W.
Published: May 2006

It is well known that combinatory logic with unrestricted introduction and elimination rules for implication is inconsistent in the strong sense that an arbitrary term Y is provable. The simplest proof of this, now usually called Curry's paradox, involves for an arbitrary term Y, a term X defined by X = Y(CPy).

The fact that X = PXY = X ⊃ Y is an essential part of the proof.

The paradox can be avoided by placing restrictions on the implication introduction rule or on the axioms from which it can be proved.

In this paper we determine the forms that must be taken by inconsistency proofs of systems of propositional calculus based on combinatory logic, with arbitrary restrictions on both the introduction and elimination rules for the connectives. Generally such a proof will involve terms without normal form and cut formulas, i.e. formulas formed by an introduction rule that are immediately removed by an elimination with at most some equality steps intervening. (Such a sequence of steps we call a “cut”.)

The above applies not only to the strong form of inconsistency defined above, but also to the weak form of inconsistency defined by: all propositions are provable, if this can be represented in the system.

Any inconsistency proof of this kind of system can be reduced to one where the major premise of the elimination rule involved in the cut and its deduction must also appear in the deduction of the minor premise involved in the cut.

We can, using this characterization of inconsistency proofs, put appropriate restrictions on certain introduction rules so that the systems, including a full classical propositional one, become provably consistent.
The contributions of Alfred Tarski to general algebra
Authors: Jónsson Bjarni
Published: May 2006

A distinctive feature of modern mathematics is the interaction between its various branches and the blurring of the boundaries between different areas. This is strikingly illustrated in the work of Alfred Tarski. He was a logician first and an algebraist second. His contributions to algebra can be divided into three (ill-defined and overlapping) categories, general algebra, the study of various algebraic structures arising from problems outside algebra, mostly in logic and set theory, and the use of concepts and techniques from logic in the study of algebraic structures. Even more roughly, these three categories could be labeled as pure algebra, applications of algebra to logic, and applications of logic to algebra.

Before Tarski came to the United States in 1939, he had written a series of papers on both the axiomatic and the structural aspects of Boolean algebras, and his inclination to algebraize mathematical problems is well illustrated by his paper [38g], Algebraische Fassung des Massproblems. Many of his later investigations of various types of algebraic structures are inspired by work done in this earlier period. However, beginning around 1940 there is a much greater emphasis on the study of algebra in its various aspects.

The paper [41], On the calculus of relations, is a landmark event in this respect. The object here was to find an axiomatic basis for the arithmetic of binary relations. The axioms that he chose are simple and natural (see Monk [1986]).
0# and some forcing principles
Authors: Foreman Matthew , Magidor Menachem , Shelah Saharon
Published: May 2006

It has been considered desirable by many set theorists to find maximality properties which state that the universe has in some sense “many sets”. The properties isolated thus far have tended to be consistent with each other (as far as we know). For example it is a widely held view that the existence of a supercompact cardinal is consistent with the axiom of determinacy holding in L(R). This consistency has been held to be evidence for the truth of these properties. It is with this in mind that the first author suggested the following:

Maximality Principle If P is a partial ordering and G ⊆ P is a V-generic ultrafilter then either

a) there is a real number r ∈ V [G] with r ∉ V, or

b) there is an ordinal α such that α is a cardinal in V but not in V[G].

This maximality principle applied to garden variety partial orderings has startling results for the structure of V.

For example, if for some , then P = 〈{p: p ⊆ κ, ∣p∣ < κ}, ⊆〉 neither adds a real nor collapses a cardinal. Thus from the maximality principle we can deduce that the G. C. H. fails everywhere and there are no inaccessible cardinals. (Hence this principle contradicts large cardinals.) Similarly one can show that there are no Suslin trees on any cardinal κ. These consequences help justify the title “maximality principle”.

Since the maximality principle implies that the G. C. H. fails at strong singular limit cardinals it has consistency strength at least that of “many large cardinals”. (See [M].) On the other hand it is not known to be consistent, relative to any assumptions.
Pairs without infimum in the recursively enumerable weak truth table degrees
Authors: Fischer Paul
Published: May 2006

wtt-reducibility has become of some importance in the last years through the works of Ladner and Sasso [1975], Stob [1983] and Ambos-Spies [1984]. It differs from Turing reducibility by a recursive bound on the use of the reduction. This makes some proofs easier in the wtt degrees than in the Turing degrees. Certain proofs carry over directly from the Turing to the wtt degrees, especially those based on permitting. But the converse is also possible. There are some r.e. Turing degrees which consist of a single r.e. wtt degree (the so-called contiguous degrees; see Ladner and Sasso [1975]). Thus it suffices to prove a result about contiguous wtt degrees using an easier construction, and it carries over to the corresponding Turing degrees.

In this work we prove some results on pairs of r.e. wtt degrees which have no infimum. The existence of such a pair has been shown by Ladner and Sasso. Here we use a different technique of Jockusch [1981] to prove this result (Theorem 1) together with some stronger ones. We show that a pair without infimum exists above a given incomplete wtt degree (Theorem 5) and below any promptly simple wtt degree (Theorem 12). In Theorem 17 we prove, however, that there are r.e. wtt degrees such that any pair below them has an infimum. This shows that certain initial segments of the wtt degrees are lattices. Thus there is a structural difference between the wtt and Turing degrees where the pairs without infimum are dense (Ambos-Spies [1984]).
On the number of generators of cylindric algebras
Authors: Andréka H. , Németi I.
Published: May 2006

The theory of cylindric algebras (CA's) is the algebraic theory of first order logics. Several ideas about logic are easier to formulate in the frame of CA-theory. Such are e.g. some concepts of abstract model theory (cf. [1] and [10]–[12]) as well as ideas about relationships between several axiomatic theories of different similarity types (cf. [4] and [10]). In contrast with the relationship between Boolean algebras and classical propositional logic, CA's correspond not only to classical first order logic but also to several other ones. Hence CA-theoretic results contain more information than their counterparts in first order logic. For more about this see [1], [3], [5], [9], [10] and [12].

Here we shall use the notation and concepts of the monographs Henkin-Monk-Tarski [7] and [8]. ω denotes the set of natural numbers. CAα denotes the class of all cylindric algebras of dimension α; by “a CAα” we shall understand an element of the class CAα. The class Dcα ⊆ CAα was defined in [7]. Note that Dcα = 0 for α ∈ ω. The classes Wsα, and Csα were defined in 1.1.1 of [8], p. 4. They are called the classes of all weak cylindric set algebras, regular cylindric set algebras and cylindric set algebras respectively. It is proved in [8] (I.7.13, I.1.9) that ⊆ CAα. (These inclusions are proper by 7.3.7, 1.4.3 and 1.5.3 of [8].)

It was proved in 2.3.22 and 2.3.23 of [7] that every simple, finitely generated Dcα is generated by a single element. This is the algebraic counterpart of a property of first order logics (cf. 2.3.23 of [7]). The question arose: for which simple CAα's does “finitely generated” imply “generated by a single element” (see p. 291 and Problem 2.3 in [7]). In terms of abstract model theory this amounts to asking the question: For which logics does the property described in 2.3.23 of [7] hold? This property is roughly the following. In any maximal theory any finite set of concepts is definable in terms of a single concept. The connection with CA-theory is that maximal theories correspond to simple CA's (the elements of which are the concepts of the original logic) and definability corresponds to generation.
The ⊲-ordering on normal ultrafilters
Authors: Baldwin Stewart
Published: May 2006

Ifκis a measurable cardinal, then it is a well-known fact that there is at least one normal ultrafilter overκ. In [K-1], Kunen showed that one cannot say more without further assumptions, for ifUis a normal ultrafilter overκ, thenL[U] is an inner model of ZFC in whichκhas exactly one normal measure. On the other hand, Kunen and Paris showed [K-P] that ifκis measurable in the ground model, then there is a forcing extension in whichκhasnormal ultrafilters, so it is consistent thatκhas the maximum possible number of normal ultrafilters. Starting with assumptions stronger than measurability, Mitchell [Mi-1] filled in the gap by constructing models of ZFC + GCH satisfying “there are exactlyλnormal ultrafilters overκ”, whereλcould beκ+orκ++(measured in the model), or anything ≤κ. Whether or not Mitchell's results can be obtained by starting only with a measurable cardinal in the ground model and defining a forcing extension is unknown.

There are substantial differences between the Mitchell models and the Kunen-Paris models. In the Kunen-Paris modelsκcan be the only measurable cardinal. However, in the Mitchell model in whichκhas exactly 2 normal ultrafilters, one of them contains the set {α<κ:αis measurable} while the other does not. Thus it is natural to ask if it is possible to get a modelMof ZFC in whichκis the only measurable cardinal andκhas exactly 2 normal ultrafilters. In this paper we will show that, using appropriate large cardinal assumptions, the answer is yes.
An algorithm to determine, for any prime p, a polynomial-sized Horn sentence which expresses “The cardinality is not p”
Authors: Tulipani Sauro
Published: May 2006

Given a prime p, we exhibit a Horn sentence Hp which expresses “the cardinality is not p” and has size O(p5 log p).
Large cardinal structures below ℵω
Authors: Apter Arthur W. , Henle James M.
Published: May 2006

The theory of large cardinals in the absence of the axiom of choice (AC) has been examined extensively by set theorists. A particular motivation has been the study of large cardinals and their interrelationships with the axiom of determinacy (AD). Many important and beautiful theorems have been proven in this area, especially by Woodin, who has shown how to obtain, from hypermeasurability, models for the theories “ZF + DC + ∀α < ℵ1(ℵ1 → (ℵ1)α)” and . Thus, consequences of AD whose consistency strength appeared to be beyond that of the more standard large cardinal hypotheses were shown to have suprisingly weak consistency strength.

In this paper, we continue the study of large cardinals in the absence of AC and their interrelationships with AD by examining what large cardinal structures are possible on cardinals below ℵω in the absence of AC. Specifically, we prove the following theorems.

Theorem 1. Con(ZFC + κ1 < κ2are supercompact cardinals) ⇒ Con(ZF + DC + The club filter on ℵ1is a normal measure + ℵ1and ℵ2are supercompact cardinals).

Theorem 2. Con(ZF + AD) ⇒ Con(ZF + ℵ1, ℵ2and ℵ3are measurable cardinals which carry normal measures + μωis not a measure on any of these cardinals).
On precipitousness of the nonstationary ideal over a supercompact
Authors: Gitik Moti
Published: May 2006

Namba [N] proved that the nonstationary ideal over a measurable (NSκ) cannot be κ+-saturated. Baumgartner, Taylor and Wagon [BTW] asked if it is possible for NSκ to be precipitous over a measurable κ. A model with this property was constructed by the author, and shortly after Foreman, Magidor and Shelah [FMS] proved a general theorem that after collapsing of a supercompact or even a superstrong to the successor of κ, NSκ became precipitous. This theorem implies that it is possible to have the nonstationary ideal precipitous over even a supercompact cardinal. Just start with a supercompact κ and a superstrong λ > κ. Make supercompactness of κ indistractible as in [L] and then collapse λ to be κ+.

The aim of our paper is to show that the existence of a supercompact cardinal alone already implies the consistency of the nonstationary ideal precipitous over a supercompact. The proof gives also the following: if κ is a λ-supercompact for λ ≥ (2κ)+, then there exists a generic extension in which κ is λ-supercompact and NSκ is precipitous. Thus, for a model with NSκ precipitous over a measurable we need a (2κ)+-supercompact cardinal κ. Jech [J] proved that the precipitous of NSκ over a measurable κ implies the existence of an inner model with o(κ) = κ+ + 1. In §3 we improve this result a little by showing that the above assumption implies an inner model with a repeat point.

The paper is organized as follows. In §1 some preliminary facts are proved. The model with NSκ precipitous over a supercompact is constructed in §2.
Equality and lyndon's interpolation theorem
Authors: Motohashi Nobuyoshi
Published: May 2006

In this paper, we remark on some properties of equality that tend to be neglected and use them to give a proof of an extension of Lyndon's interpolation theorem. Let LK be a first order classical predicate calculus and LK= a first order classical predicate calculus with equality. We assume that LK and LK= have the propositional constant Τ (truth). For each formula F in LK=, let Rel+ (F), Rel− (F), Rel(F), and Fun(F) be the set of all the predicate symbols which occur in F positively, the set of all the predicate symbols which occur in F negatively, the set of all the predicate symbols which occur in F, and the set of all the function symbols which occur in F.

Theorem A (Lyndon [5]). Suppose that A and B are sentences in LK such that A ⊃ B is provable in LK. Then there is a sentence C in LK such that:

(i) A ⊃ C and C ⊃ B are provable in LK;

(ii) and

(iii) .

The sentence C which satisfies (i), (ii), (iii) in Theorem A is said to be an interpolant for A ⊃ B in Theorem A. Note that condition (iii) is not included in the original form of Lyndon's interpolation theorem (cf. [5]), but we can easily add this condition. Also, there is some obscurity in the original formulation with regard to the equality symbol. For example, Lyndon writes: “The theorem takes the same form whether or not we admit a predicate denoting identity, with suitable axioms, to the predicate calculus” [5, p. 129].
Strongly compact cardinals, elementary embeddings and fixed points
Authors: Abe Yoshihiro
Published: May 2006

J. Barbanel [1] characterized the class of cardinals fixed by an elementary embedding induced by a normal ultrafilter on Pκλ assuming that κ is supercompact. In this paper we shall prove the same results from the weaker hypothesis that κ is strongly compact and the ultrafilter is fine.

We work in ZFC throughout. Our set-theoretic notation is quite standard. In particular, if X is a set, ∣X∣ denotes the cardinality of X and P(X) denotes the power set of X. Greek letters will denote ordinals. In particular γ, κ, η and γ will denote cardinals. If κ and λ are cardinals, then λ<κ is defined to be supγ<κγγ. Cardinal exponentiation is always associated from the top. Thus, for example, 2λ<κ means 2(λ<κ). V denotes the universe of all sets. If M is an inner model of ZFC, ∣X∣M and P(X)M denote the cardinality of X in M and the power set of X in M respectively.

We review the basic facts on fine ultrafilters and the corresponding elementary embeddings. (For detail, see [2].)

Definition. Assume κ and λ are cardinals with κ ≤ λ. Then, Pκλ = {X ⊂ λ∣∣X∣ < κ}.

It is important to note that ∣Pκλ∣ = λ< κ.
Regular types in nonmultidimensional ω-stable theories
Authors: Pillay Anand
Published: May 2006

We define a hierarchy on the regular types of an ω-stable nonmultidimensional theory, using generalised notions of algebraic and strongly minimal formulae. As an application we show that any resplendent model of an ω-stable finite-dimensional theory is saturated.
Inconsistent models for relevant arithmetics
Authors: Meyer Robert K. , Mortensen Chris
Published: May 2006

This paper develops in certain directions the work of Meyer in [3], [4], [5] and [6] (see also Routley [10] and Asenjo [11]). In those works, Peano's axioms for arithmetic were formulated with a logical base of the relevant logic R, and it was proved finitistically that the resulting arithmetic, called R#, was absolutely consistent. It was pointed out that such a result escapes incautious formulations of Gödel's second incompleteness theorem, and provides a basis for a revived Hilbert programme. The absolute consistency result used as a model arithmetic modulo two. Modulo arithmetics are not ordinarily thought of as an extension of Peano arithmetic, since some of the propositions of the latter, such as that zero is the successor of no number, fail in the former. Consequently a logical base which, unlike classical logic, tolerates contradictory theories was used for the model. The logical base for the model was the three-valued logic RM3 (see e.g. [1] or [8]), which has the advantage that while it is an extension of R, it is finite valued and so easier to handle.

The resulting model-theoretic structure (called in this paper RM32) is interesting in its own right in that the set of sentences true therein constitutes a negation inconsistent but absolutely consistent arithmetic which is an extension of R#. In fact, in the light of the result of [6], it is an extension of Peano arithmetic with a base of a classical logic, P#. A generalisation of the structure is to modulo arithmetics with the same logical base RM3, but with varying moduli (called RM3i here).
Expressive power in first order topology
Authors: Bankston Paul
Published: May 2006

Afirst order representation(f.o.r.) in topology is an assignment of finitary relational structures of the same type to topological spaces in such a way that homeomorphic spaces get sent to isomorphic structures. We first define the notions “one f.o.r. is at least as expressive as another relative to a class of spaces” and “one class of spaces is definable in another relative to an f.o.r.”, and prove some general statements. Following this we compare some well-known classes of spaces and first order representations. A principal result is that ifXandYare two Tichonov spaces whose posets of zero-sets are elementarily equivalent then their respective rings of bounded continuous real-valued functions satisfy the same positive-universal sentences. The proof of this uses the technique of constructing ultraproducts as direct limits of products in a category theoretic setting.
QE commutative nilrings
Authors: Saracino D. , Wood C.
Published: May 2006

If L is a first-order language, then an L-structure A is called quantifier-eliminable (QE) if every L-formula is equivalent in A to a formula without quantifiers.

The classification problem for QE groups and rings has received attention in work by Berline, Boffa, Cherlin, Feigner, Macintyre, Point, Rose, the present authors, and others. In [1], Berline and Cherlin reduced the problem for rings of prime characteristic p to that for nilrings, but also constructed countable QE nilrings of characteristic p. Likewise, in [3], we constructed countable QE nil-2 groups. Both results can be viewed as “nonstructure theorems”, in that they provide negative evidence for any attempt at classification. In the present paper we show that the situation is equally bad (or rich, depending on one's point of view) for commutative rings:

Theorem 1. For any odd prime p, there existcountable QE commutative nilrings of characteristic p.

This solves a problem posed in [1]. We remark that the examples we produce are uniformly locally finite, hence ℵ0-categorical. A more algebraic description is that each of our rings R is uniformly locally finite (in fact, R3 = 0) and homogeneous, in the sense that any isomorphism of finitely generated subrings extends to an automorphism of R.

Theorem 1 does not cover the case p = 2, and we show that for commutative rings this case is in fact exceptional:

Theorem 2. There exist exactly two nonisomorphic countably infinite QE commutative nilrings of characteristic 2.
3088 varieties: A solution to the Ackermann constant problem
Authors: Slaney John K.
Published: May 2006

It is shown that there are exactly six normal DeMorgan monoids generated by the idntity element alone. The free DeMorgan monoid with no generators but the identity is characterised and shown to have exactly three thousand and eighty-eight elements. This result solves the “Ackermann constant problem” of describing the structure of sentential constants in the logic R.
A hierarchy of families of recursively enumerable degrees
Authors: Welch Lawrence V.
Published: May 2006

Certain investigations have been made concerning the nature of classes of recursively enumerable sets, and the relation of such classes to the recursively enumerable indices of their sets. For instance, a theorem of Rice [3, Theorem XIV(a), p. 324] states that if A is the complete set of indices for a class of recursively enumerable sets (that is, if there is a class of recursively enumerable sets such that and if A is recursive, then either A = ⌀ or A = ω. A relate theorem by Rice and Shapiro [3, Theorem XIV(b), p. 324] can be stated as follows:

Let be a class of recursively enumerable sets, and let A be the complete set of indices for . Then A is r.e. if and only if there is an r.e. set D of canonical indices of finite sets Du, u ∈ D, such that

A somewhat similar theorem of Yates is the following: Let be a class of recursively enumerable sets which contains all finite sets. Let A be the complete set of indices for . Then there is a uniform recursive enumeration of the sets in if and only if A is recursively enumerable in 0(2)—that is, if and only if A is Σ3. A corollary of this is that if C is any r.e. set such that C(2)≡T⌀(2), there is a uniform recursive enumeration of all sets We such that We ≤TC [9, Theorem 9, p. 265].
Linear reasoning in modal logic
Authors: Fitting Melvin
Published: May 2006

In [1] Craig introduced a proof procedure for first order classical logic called linear reasoning. In it, a proof of P ⊃ Q consists of a sequence of formulas, each of which implies the next, beginning with P and ending with Q. And one of the formulas in the sequence will be an interpolation formula for P ⊃ Q. Indeed, this was the first proof of the Craig interpolation theorem, some of whose important consequences were demonstrated in a companion paper [2]. In this paper we present systems of linear reasoning for several standard modal logics: K, T, K4, S4, D, D4, and GL. Similar systems can be constructed for several regular, nonnormal modal logics too, though we do not do so here. And just as in the classical case, interpolation theorems are easy consequences. Such theorems are well known for the logics considered here. There is a model theoretic argument in [6], an argument using Gentzen systems in [8], an argument using consistency properties in [4] and [5], and an argument using symmetric Gentzen systems in [5]. This paper presents what seems to be the first modal proof that follows Craig's original methods. We note that if the modal rules given here are dropped, a classical linear reasoning system results, which is related to, but not the same as those in [1] and [10].

Since the basic linear reasoning ideas are fully illustrated by the propositional case, we present that first, to keep the clutter down. Later we show how the techniques can generally be extended to encompass quantifiers. We do not follow [1] in making heavy use of prenex form, since it is not generally available in modal logics. Fortunately, it plays no essential role.
The decision problem for branching time logic
Authors: Gurevich Yuri , Shelah Saharon
Published: May 2006

The theory of trees with additional unary predicates and quantification over nodes and branches embraces a rich branching time logic. This theory was reduced in the companion paper to the first-order theory of binary, bounded, well-founded trees with additional unary predicates. Here we prove the decidability of the latter theory.
On theories having a finite number of nonisomorphic countable models
Authors: Tsuboi Akito
Published: May 2006

In this paper we shall state some interesting facts concerning non-ω-categorical theories which have only finitely many countable models. Although many examples of such theories are known, almost all of them are essentially the same in the following sense: they are obtained from ω-categorical theories, called base theories below, by adding axioms for infinitely many constant symbols. Moreover all known base theories have the (strict) order property in the sense of [6], and so they are unstable. For example, Ehrenfeucht's well-known example which has three countable models has the theory of dense linear order as its base theory.

Many papers including [4] and [5] are motivated by the conjecture that every non-ω-categorical theory with a finite number of countable models has the (strict) order property, but this conjecture still remains open. (Of course there are partial positive solutions. For example, in [4], Pillay showed that if such a theory has few links (see [1]), then it has the strict order property.) In this paper we prove the instability of the base theory T0 of such a theory T rather that T itself. Our main theorem is a strengthening of the following which is also our result: if a theory T0 is stable and ω-categorical, then T0 cannot be extended to a theory T which has n countable models (1 < n < ω) by adding axioms for constant symbols.
Inconsistent nonstandard arithmetic
Authors: Mortensen Chris
Published: May 2006

This paper continues the investigation of inconsistent arithmetical structures. In §2 the basic notion of a model with identity is defined, and results needed from elsewhere are cited. In §3 several nonisomorphic inconsistent models with identity which extend the (=, <) theory of the usual classical denumerable nonstandard model of arithmetic are exhibited. In §4 inconsistent nonstandard models of the classical theory of finite rings and fields modulo m, i.e. Zm, are briefly considered. In §5 two models modulo an infinite nonstandard number are considered. In the first, it is shown how to model inconsistently the arithmetic of the rationals with all names included, a strengthening of earlier results. In the second, all inconsistency is confined to the nonstandard integers, and the effects on Fermat's Last Theorem are considered. It is concluded that the prospects for a good inconsistent theory of fields may be limited.
The Complexity of intrinsically r.e. subsets of existentially decidable models
Authors: Chisholm John
Published: May 2006

Recursive model theory involves the study of relationships between recursion theory and model theory. One direction this often takes is to study the effectiveness of various aspects of model theory. This paper examines such questions by examining some properties of recursive models; that is, models whose basic relations, functions, and constants are all uniformly recursive (and whose universe is the set of natural numbers). Somewhat more precisely:

Let be a model whose universe is N, and let (θ())i be an effective enumeration of all quantifier-free formulas of the language of . Then is recursive if {〈, i〉: satisfies (θ())i, in } is a recursive subset of N. (Here and throughout the paper, 〈 〉 denotes an effective pairing function, or an effective coding of sequences, as required.) Similarly, let (ϕ())i be an effective enumeration of all existential formulas of the language of . Then is existentially decidable if {〈, i〉: satisfies (ϕ())i in } is a recursive subset of N.

It is clear that if is recursive and is a model isomorphic to , then may lose many of the recursive properties of . In the simplest example, could easily fail to be a recursive model. But even if we require that be a recursive model, it could still fail to retain other recursive properties of . An example of the sort of property which can be studied in this vein is the following notion, introduced by Ash and Nerode in [2].
Splitting Pκλ into stationary subsets
Authors: Matsubara Yo
Published: May 2006

We show that if κ is an inaccessible cardinal then Pκλ splits into λ<κ many disjoint stationary subsets. We also show that if Pκλ carries a strongly saturated ideal then the nonstationary ideal cannot be λ+-saturated.
Extensions séparées et immédiates de corps valués
Authors: Delon Françoise
Published: May 2006

Baur a défini la notion d'extension séparée de corps valués et montré que toute extension d'un corps maximal est séparée. Nous prouvons que, si (K, υ) est henselien et de caractéristique résiduelle nulle, alors (K, υ) ⊂ (L, w) est séparée ssi L est linéairement disjoint sur K de toute extension immédiate de K.

Separated and immediate extensions of valued fields. The notion of separated extension of valued fields was introduced by Baur. He showed that extensions of maximal fields are separated. We prove that, when (K, υ) is Henselian with residual characteristic 0, then (K, υ) ⊂ (L, w) is separated iff L is linearly disjoint over K from each immediate extension of K.
Uniqueness, definability and interpolation
Authors: Došen Kosta , Schroeder-Heister Peter
Published: May 2006

This paper is meant to be a comment on Beth's definability theorem. In it we shall make the following points.

Implicit definability as mentioned in Beth's theorem for first-order logic is a special case of a more general notion of uniqueness. If α is a nonlogical constant, Tα a set of sentences, α* an additional constant of the same syntactical category as α and Tα, a copy of Tα with α* instead of α, then for implicit definability of α in Tα one has, in the case of predicate constants, to derive α(x1,…,xn) ↔ α*(x1,…,xn) from Tα ∪ Tα*, and similarly for constants of other syntactical categories. For uniqueness one considers sets of schemata Sα and derivability from instances of Sα ∪ Sα* in the language with both α and α*, thus allowing mixing of α and α* not only in logical axioms and rules, but also in nonlogical assumptions. In the first case, but not necessarily in the second one, explicit definability follows. It is crucial for Beth's theorem that mixing of α and α* is allowed only inside logic, not outside. This topic will be treated in §1.

Let the structural part of logic be understood roughly in the sense of Gentzen-style proof theory, i.e. as comprising only those rules which do not specifically involve logical constants. If we restrict mixing of α and α* to the structural part of logic which we shall specify precisely, we obtain a different notion of implicit definability for which we can demonstrate a general definability theorem, where a is not confined to the syntactical categories of nonlogical expressions of first-order logic. This definability theorem is a consequence of an equally general interpolation theorem. This topic will be treated in §§2, 3, and 4.
Σ½-sets of reals
Authors: Ihoda Jaime I.
Published: May 2006

We prove that the only implications between four notions for Σ½-sets of reals are
A characterization of jump operators
Authors: Becker Howard
Published: May 2006

The topic of this paper is jump operators, a subject which originated with some questions of Martin and a partial answer to them obtained by Steel [18]. The topic of jump operators is a part of the general study of the structure of the Turing degrees, but it is concerned with an aspect of that structure which is different from the usual concerns of classical recursion theory. Specifically, it is concerned with studying functions on the degrees, such as the Turing jump operator, the hyperjump operator, and the sharp operator.

Roughly speaking, a jump operator is a definable ≤T-increasing function on the Turing degrees. The purpose of this paper is to characterize the jump operators, in terms of concepts from descriptive set theory. Again roughly speaking, the main theorem states that all jump operators (other than the identity function) are obtained from pointclasses by the same process by which the hyperjump operator is obtained from the pointclass Π11; that is, if Γ is the pointclass, then the operator maps the real x to the universal Γ(x) subset of ω. This characterization theorem has some corollaries, one of which answers a question of Steel [18]. In §1 we give a brief introduction to this general topic, followed by a brief (and still somewhat imprecise) description of the results contained in this paper.
Believing the axioms. II
Authors: Maddy Penelope
Published: May 2006

This is a continuation of Believing the axioms. I, in which nondemonstrative arguments for and against the axioms of ZFC, the continuum hypothesis, small large cardinals and measurable cardinals were discussed. I turn now to determinacy hypotheses and large large cardinals, and conclude with some philosophical remarks.

Determinacy is a property of sets of reals. If A is such a set, we imagine an infinite game G(A) between two players I and II. The players take turns choosing natural numbers. In the end, they have generated a real number r (actually a member of the Baire space ωω). If r is in A, I wins; otherwise, II wins. The set A is said to be determined if one player or the other has a winning strategy (that is, a function from finite sequences of natural numbers to natural numbers that guarantees the player a win if he uses it to decide his moves).

Determinacy is a “regularity” property (see Martin [1977, p. 807]), a property of well-behaved sets, that implies the more familiar regularity properties like Lebesgue measurability, the Baire property (see Mycielski [1964] and [1966], and Mycielski and Swierczkowski [1964]), and the perfect subset property (Davis [1964]). Infinitary games were first considered by the Polish descriptive set theorists Mazur and Banach in the mid-30s; Gale and Stewart [1953] introduced them into the literature, proving that open sets are determined and that the axiom of choice can be used to construct an undetermined set.
More on definable sets of p-adic numbers
Authors: Scowcroft Philip
Published: May 2006

To eliminate quantifiers in the first-order theory of the p-adic field Qp, Ax and Kochen use a language containing a symbol for a cross-section map n → pn from the value group Z into Qp [1, pp. 48–49]. The primitive-recursive quantifier eliminations given by Cohen [2] and Weispfenning [10] also apply to a language mentioning the cross-section, but none of these authors seems entirely happy with his results. As Cohen says, “all the operations… introduced for our simple functions seem natural, with the possible exception of the map n → pn” [2, p. 146]. So all three authors show that various consequences of quantifier elimination—completeness, decidability, model-completeness—also hold for a theory of Qp not employing the cross-section [1, p. 453; 2, p. 146; 10, §4]. Macintyre directs a more specific complaint against the cross-section [5, p. 605]. Elementary formulae which use it can define infinite discrete subsets of Qp; yet infinite discrete subsets of R are not definable in the language of ordered fields, and so certain analogies between Qp and R suggested by previous model-theoretic work seem to break down.

To avoid this problem, Macintyre gives up the cross-section and eliminates quantifiers in a theory of Qp written just in the usual language of fields supplemented by a predicate V for Qp's valuation ring and by predicates Pn for the sets of nth powers in Qp (for all n ≥ 2).
Universal structures in power ℵ1
Authors: Mekler Alan H.
Published: May 2006

It is consistent with ¬ CH that every universal theory of relational structures with the joint embedding property and amalgamation for -(3)-diagrams has a universal model of cardinality ℵ1. For classes with amalgamation for -(4)-diagrams it is consistent that and there is a universal model of cardinality ℵ2.