bluuebunny/crossref_metadata_2025 huggingface dataset:
Successors of singular cardinals and measurability revisited
Authors: Apter Arthur W.
Published: May 2006

Before the remarkable theorem of Martin and Steel [6] showing that the existence of a supercompact cardinal κ implies L[R] ⊨ ZF + AD + DC, and the later theorem of Woodin [9] showing that Con(ZFC + There exists an ω sequence of Woodin cardinals) ⇔ Con(ZF + AD + DC), much set-theoretic research was focused upon showing that the consistency of fragments of AD + DC followed from more “reasonable” hypotheses such as versions of supercompactness. A good example of this is provided by the results of [1], in which the following theorems are proven.
Taxonomies of model-theoretically defined topological properties
Authors: Bankston Paul
Published: May 2006

Atopological classification schemeconsists of two ingredients: (1) an abstract classof topological spaces; and (2) a “taxonomy”, i.e. a list of first order sentences, together with a way of assigning an abstract class of spaces to each sentence of the list so that logically equivalent sentences are assigned the same class.is then endowed with an equivalence relation, two spaces belonging to the same equivalence class if and only if they lie in the same classes prescribed by the taxonomy. A spaceXinischaracterizedwithin the classification scheme if wheneverY∊andYis equivalent toX, thenYis homeomorphic toX. As prime example, theclosed set taxonomyassigns to each sentence in the first order language of bounded lattices the class of topological spaces whose lattices of closed sets satisfy that sentence. It turns out that every compact two-complex is characterized via this taxonomy in the class of metrizable spaces, but that no infinite discrete space is so characterized. We investigate various natural classification schemes, compare them, and look into the question of which spaces can and cannot be characterized within them.
Definitions of compact
Authors: Howard Paul E.
Published: May 2006

Several definitions of “compact” for topological spaces have appeared in the literature (see [5]). We will consider the following:

Definition. A topological space X is

1. Compact(1) if every open cover of X has a finite subcover.

2. Compact(2) if every infinite subset E of X has a complete accumulation point (i.e., a point x0 ∈ X such that for every neighborhood U of x0, |E ∩ U| = |E|).

3. Compact(3) if there is a subbase S for the topology on X such that every cover of X by members of S has a finite subcover.

4. Compact(4) if each nest of closed, nonempty sets has a nonempty intersection.

5. Compact(5) if every family of closed sets in X which has the finite intersection property (every finite subfamily has a nonempty intersection) has a nonempty intersection.

6. Compact(6) if each net in X has a cluster point.

7. Compact(7) if each net in X has a convergent subnet.

This work was motivated primarily by consideration of various proofs that the Tychonoff theorem, T (“the product of compact topological spaces is compact”) is equivalent to the Axiom of Choice, AC. Tychonoff's original proof that AC implies T used Definition 2 [13]. Other proofs have used Definitions 3 and 5; see [5]. The proof by Kelley that T implies AC uses Definition 5 [6].
Some improvements to Turner's algorithm for bracket abstraction
Authors: Bunder M. W.
Published: May 2006

A computer handles λ-terms more easily if these are translated into combinatory terms. This translation process is called bracket abstraction. The simplest abstraction algorithm—the (fab) algorithm of Curry (see Curry and Feys [6])—is lengthy to implement and produces combinatory terms that increase rapidly in length as the number of variables to be abstracted increases.

There are several ways in which these problems can be alleviated:

(1) A change in order of the clauses in the algorithm so that (f) is performed as a last resort.

(2) The use of an extra clause (c), appropriate to βη reduction.

(3) The introduction of a finite number of extra combinators.

The original 1924 form of bracket abstraction of Schönfinkel [17], which in fact predates λ-calculus, uses all three of these techniques; all are also mentioned in Curry and Feys [6].

A technique employed by many computing scientists (Turner [20], Peyton Jones [16], Oberhauser [15]) is to use the (fab) algorithm followed by certain “optimizations” or simplifications involving extra combinators and sometimes special cases of (c).

Another is either to allow a fixed infinite set of (super-) combinators (Abdali [1], Kennaway and Sleep [10], Krishnamurthy [12], Tonino [19]) or to allow new combinators to be defined one by one during the abstraction process (Hughes [7] and [8]).

A final method encodes the variables to be abstracted as an n-tuple—this requires only a finite number of combinators (Curien [5], Statman [18]).
Proof theory in the USSR 1925–1969
Authors: Mints Grigori
Published: May 2006

We present a survey of proof theory in the USSR beginning with the paper by Kolmogorov [1925] and ending (mostly) in 1969; the last two sections deal with work done by A. A. Markov and N. A. Shanin in the early seventies, providing a kind of effective interpretation of negative arithmetic formulas. The material is arranged in chronological order and subdivided according to topics of investigation. The exposition is more detailed when the work is little known in the West or the original presentation can be improved using notions or results which appeared later. This includes such topics as Novikov's cut-elimination method (regular formulas) and Maslov's inverse method for the predicate logic.
A construction for recursive linear orderings
Authors: Ash C. J.
Published: May 2006

We re-express a previous general result in a way which seems easier to remember, using the terminology of infinite games. We show how this can be applied to construct recursive linear orderings, showing, for example, that if there is a linear ordering of type τ, then there is a recursive ordering of type ωβ · τ.
Π11 Borel sets
Authors: Kechris Alexander S. , Marker David , Sami Ramez L.
Published: May 2006

The results in this paper were motivated by the following question of Sacks. Suppose T is a recursive theory with countably many countable models. What can you say about the least ordinal α such that all models of T have Scott rank below α? If Martin's conjecture is true for T then α ≤ ω · 2.

Our goal was to look at this problem in a more abstract setting. Let E be a equivalence relation on ωω with countably many classes each of which is Borel. What can you say about the least α such that each equivalence class is ? This problem is closely related to the following question. Suppose X ⊆ ωω is and Borel. What can you say about the least α such that X is ?

In §1 we answer these questions in ZFC. In §2 we give more informative answers under the added assumptions V = L or -determinacy. The final section contains related results on the separation of sets by Borel sets.

Our notation is standard. The reader may consult Moschovakis [5] for undefined terms.

Some of these results were proved first by Sami and rediscovered by Kechris and Marker.
Nonstandard set theory
Authors: Fletcher Peter
Published: May 2006

Nonstandard set theory is an attempt to generalise nonstandard analysis to cover the whole of classical mathematics. Existing versions (Nelson, Hrbáček, Kawai) are unsatisfactory in that the unlimited idealisation principle conflicts with the wish to have a full theory of external sets.

I re-analyse the underlying requirements of nonstandard set theory and give a new formal system, stratified nonstandard set theory, which seems to meet them better than the other versions.
On the strength of the interpretation method
Authors: Gurevich Yuri , Shelah Saharon
Published: May 2006

In spite of the fact that true arithmetic reduces to the monadic second-order theory of the real line, Peano arithmetic cannot be interpreted in the monadic second-order theory of the real line.
The undecidability of the DA-unification problem
Authors: Siekmann J. , Szabó P.
Published: May 2006

We show that the DA-uniflcation problem is undecidable. That is, given two binary function symbols ⊕ and ⊗, variables and constants, it is undecidable if two terms built from these symbols can be unified provided the following DA-axioms hold:

Two terms are DA-unifiable (i.e. an equation is solvable in DA) if there exist terms to be substituted for their variables such that the resulting terms are equal in the equational theory DA.

This is the smallest currently known axiomatic subset of Hilbert's tenth problem for which an undecidability result has been obtained.
Definability via enumerations
Authors: Soskov Ivan N.
Published: May 2006

The notion of ∀-recursiviness, introduced by Lacombe [1], is intended to describe the effectively definable functions and predicates in abstract structures with equality and denumerable domains. The fact that on every such structure ∀-recursiviness and search computability are equivalent is proved by Moschovakis in [2].

The definition of search computability [3] does not require the presence of the equality among the basic predicates of the structure. There exist abstract structures where the equality is not search-computable and even not semicomputable. On the other hand, in some structures the equality is not an “effective” predicate. Consider, for example, a structure whose domain consists of all partial recursive functions.

A notion of relative computability in abstract structures with denumerable domains, which we shall call here ∀-admissibility, was introduced by D. Skordev in 1977. The notion of ∀-admissibility is a generalization of Lacombe's ∀-recursiviness and does not require the presence of the equality among the basic predicates. In 1977 Skordev conjectured that, in every partial structure with denumerable domain, ∀-admissibility and search computability are equivalent.

Since 1977 some attempts have been made to establish Skordev's conjecture. It is proved in [4] for structures with total basic functions and without basic predicates, and in [5] for structures with finite domains. The proofs in [4] and [5] make use of the priority method and are very complicated.
On models of the elementary theory of (Z, +, 1)
Authors: Nadel Mark , Stavi Jonathan
Published: May 2006

Let T1 be the complete first-order theory of the additive group of the integers with 1 as distinguished element (in symbols, T1 = Th(Z, +, 1)). In this paper we prove that all models of T1 are ℵ0-homogeneous (§2), classify them (and lists of elements in them) up to isomorphism or L∞κ-equivalence (§§3 and 4) and show that they may be as complex as arbitrary sets of real numbers from the point of view of admissible set theory (§5). The results of §§2 and 5 together show that while the Scott heights of all models of T1 are ≤ ω (by ℵ0-homogeneity) their HYP-heights form an unbounded subset of the cardinal .

In addition to providing this unusual example of the relation between Scott heights and HYP-heights, the theory T1 has served (using the homogeneity results of §2) as an example for certain combinations of properties that people had looked for in stability theory (see end of §4). In §6 it is shown that not all models of T = Th(Z, +) are ℵ0-homogeneous, so that the availability of the constant for 1 is essential for the result of §2.

The two main results of this paper (2.2 and essentially Theorem 5.3) were obtained in the summer of 1979. Later we learnt from Victor Harnik and Julia Knight that T1 is of some interest for stability theory, and were encouraged to write up our proofs.

During 1982/3 we improved the proofs and added some results.
An introduction to γ-recursion theory (or what to do in KP – Foundation)
Authors: Lubarsky Robert S.
Published: May 2006

The program of reverse mathematics has usually been to find which parts of set theory, often used as a base for other mathematics, are actually necessary for some particular mathematical theory. In recent years, Slaman, Groszek, et al, have given the approach a new twist. The priority arguments of recursion theory do not naturally or necessarily lead to a foundation involving any set theory; rather, Peano Arithmetic (PA) in the language of arithmetic suffices. From this point, the appropriate subsystems to consider are fragments of PA with limited induction. A theorem in this area would then have the form that certain induction axioms are independent of, necessary for, or even equivalent to a theorem about the Turing degrees. (See, for examples, [C], [GS], [M], [MS], and [SW].)

As go the integers so go the ordinals. One motivation of α-recursion theory (recursion on admissible ordinals) is to generalize classical recursion theory. Since induction in arithmetic is meant to capture the well-foundedness of ω, the corresponding axiom in set theory is foundation. So reverse mathematics, even in the context of a set theory (admissibility), can be changed by the influence of reverse recursion theory. We ask not which set existence axioms, but which foundation axioms, are necessary for the theorems of α-recursion theory.

When working in the theory KP – Foundation Schema (hereinafter called KP−), one should really not call it α-recursion theory, which refers implicitly to the full set of axioms KP. Just as the name β-recursion theory refers to what would be α-recursion theory only it includes also inadmissible ordinals, we call the subject of study here γ-recursion theory. This answers a question by Sacks and S. Friedman, “What is γ-recursion theory?”
UFA fails in the Bell-Kunen model
Authors: Merrill John W. L.
Published: May 2006

In [vDF], van Douwen and Fleissner introduce a number of axioms which hold in models constructed by iteratively forcing MA in a nontrivial extension of the set-theoretic universe. One such model is the Bell-Kunen model, obtained by starting with a model of ZFC + GCH, then forcing “MA + ϲ = ω2” by the standard means, then forcing “MA + ϲ = ω3”, and so on. The Bell-Kunen model is the result of an ω1 sequence of extensions of this form, with direct limits taken at limit ordinals. (See [BK] for a more complete description.) Van Douwen and Fleissner observed that many of the properties of this model could be distilled into a “Definable Forcing Axiom”, which states that “If P is a c.c.c. partial order which is definable from a real, then there is a sequence of filters through , such that if is any dense subset of P, then all but countably many of the ℱα's meet in a nonempty set.” (They call such a sequence ω1-generic.) Van Douwen and Fleissner ask whether one can eliminate the restriction on the c.c.c. order entirely; the resulting axiom (“If P is any c.c.c. partial order of cardinality at most ϲ, then there is a sequence of filters…”) is called the Undefinable Forcing Axiom (UFA).
Martin's axioms, measurability and equiconsistency results
Authors: Ihoda Jaime I. , Shelah Saharon
Published: May 2006

We deal with the consistency strength of ZFC + variants of MA + suitable sets of reals are measurable (and/or Baire, and/or Ramsey). We improve the theorem of Harrington and Shelah [2] repairing the asymmetry between measure and category, obtaining also the same result for Ramsey. We then prove parallel theorems with weaker versions of Martin's axiom (MA(σ-centered), (MA(σ-linked)), , MA(K)), getting Mahlo, inaccessible and weakly compact cardinals respectively. We prove that if there exists r ∈ R such that and MA holds, then there exists a -selective filter on ω, and from the consistency of ZFC we build a model for ZFC + MA(I) + every -set of reals is Lebesgue measurable, has the property of Baire and is Ramsey.
A construction of type: type in Martin-Löf's partial type theory with one universe
Authors: Palmgren Erik
Published: May 2006

In this note we construct Martin-Löf's inconsistent type theory, Type: Type (Martin-Löf [1971]), inside partial type theory with one universe. Thus adding a fixed point operator to type theory with one predicative universe gives impredicativity.

We may describe the theory Type:Type as follows. It contains the rules for the product construction (II) of Martin-Löf [1984] except the η-rule and it contains the usual rules for definitional equality (=). Moreover it contains the following strongly impredicative universe

This theory is inconsistent (i.e. every set is inhabited), and this is seen by proving a variant of the Burali—Forti paradox—Girard's paradox—cf. Troelstra and van Dalen [1988]. Coquand [199?] has shown that by adding the well-order type and the strong dependent sum to the universe, the fixed point operator becomes definable. It is an open problem whether it is definable without the well-order type. The present result could be seen as a converse, namely by adding the fixed point operator to type theory with one universe, Type:Type becomes definable and, as is already known, so does the well-order type.
Thin equivalence relations and effective decompositions
Authors: Hjorth Greg
Published: May 2006

Let E be a equivalence relation for which there does not exist a perfect set of inequivalent reals. If 0* exists or if V is a forcing extension of L, then there is a good well-ordering of the equivalence classes.
Strong measure zero sets without Cohen reals
Authors: Goldstern Martin , Judah Haim , Shelah Saharon
Published: May 2006

If ZFC is consistent, then each of the following is consistent with :

(1) X ⊆ ℝ is of strong measure zero iff ∣X∣ ≤ ℵ1 + there is a generalized Sierpinski set.

(2) The union of ℵ many strong measure zero sets is a strong measure zero set + there is a strong measure zero set of size ℵ2 + there is no Cohen real over L.
Functions and functional on finite systems
Authors: Lo Libo
Published: May 2006

The global function on finite systems is a new concept defined by Gurevich in [1] and discussed in [2] and [3]. In the last ten years this concept has become more and more useful in computer science and logic. Gurevich also pointed out the importance of global functionals on finite systems. In this paper we will give a brief introduction to the concepts of global functions and global functionals on finite systems.

In studying the natural number system N = 〈N, +,0〉 we often refer to its functions and functionals. There are a lot of books and papers in this area. Kleene in [4] gave a detailed introduction to the recursive functions of N. The functionals of N are normally very difficult to compute because here we need to tell the machine what the input function is, which is not very easy to do. In developing the theory of finite systems the functions and functionals are also very useful. For computing the functionals in finite systems we can take the entire graph of a function as the input, which is not possible in N. We will discuss recursive functions and functionals for finite systems. The definitions of recursive functions are very similar to the case in N, but we will have a very different situation. In N the number of elements is infinite. The number of all possible functions from N to N is the continuum. In a finite system the number of all possible functions is finite. It seems that there is no necessity to define the global functions.
Lusin-Sierpiński index for the internal sets
Authors: Živaljević Boško
Published: May 2006

We prove that there exists a function f which reduces a given subset P of an internal set X of an ω1 saturated nonstandard universe to the set WF of well-founded trees possessing properties similar to those possessed by the standard part map. We use f to define the Lusin-Sierpiński index of points in X, and prove the basic properties of that index using the classical properties of the Lusin-Sierpiński index. An example of a but not set is given.
Modules with regular generic types part iv
Authors: Herzog Ivo , Rothmaler Philipp
Published: May 2006

In this paper, we continue the line of investigation undertaken in [HR], with which we assume familiarity. For a comprehensive reference we refer the reader to [P]. The authors would like to thank each other for their light spirit and good humor.

Pillay and Prest [PP, Proposition 7.10] have shown that a module M of U-rank 1 which is not totally transcendental may be decomposed as M = Ml ⊕ Mu, where Ml, ⊨ Th(M) omits the unlimited type and Mu imbeds purely into a model of the unlimited part Tu, of T = Th(M). We devote the first section of this paper to a generalization of this result to the case when T has a regular generic and m-dim(M) = 1. (Note that m-dim(M) = 0 implies M is totally transcendental, in which case a general decomposition theorem was proved by Garavaglia [G].)
Diagonals and -maximal sets
Authors: Herrmann Eberhard , Kummer Martin
Published: May 2006

In analogy to the definition of the halting problem K, an r.e. set A is called a diagonal iff there is a computable numbering ψ of the class of all partial recursive functions such that A = {i ∈ ω: ψi(i)↓} (in that case we say that A is the diagonal of ψ). This notion has been introduced in [10]. It captures all r.e. sets that can be constructed by diagonalization.

It was shown that any nonrecursive r.e. T-degree contains a diagonal, that for any diagonal A there is an r.e. nonrecursive nondiagonal B ≤TA, and that there are r.e. degrees a such that any r.e. set from a is a diagonal.

In §2 of the present paper we show that the property “A is a diagonal” is elementary lattice theoretic (e.l.t.). This result complements and generalizes previous results of Harrington and Lachlan, respectively. Harrington (see [16, XV. 1]) proved that the property of being the diagonal of some Gödelnumbering (i.e., of being creative) is e.l.t., and Lachlan [12] proved that the property of being a simple diagonal (i.e., of being simple and not hh-simple [10]) is e.l.t.

In §§3 and 4 we study the position of diagonals and nondiagonals inside the lattice of r.e. sets. We concentrate on an important class of nondiagonals, generalizing the maximal and hemimaximal sets: the -maximal sets. Using the results from [6] we are able to classify the -maximal sets that can be obtained as halfs of splittings of hh-simple sets.
Stationary reflection and ideals
Authors: Zhang Shu-Guo
Published: May 2006

In this paper we show that if there is a weakly normal ideal on κ then for each fails. This greatly improves a theorem of C. A. Johnson.
Kolmogorov and mathematical logic
Authors: Uspensky Vladimir A.
Published: May 2006

There are human beings whose intellectual power exceeds that of ordinary men. In my life, in my personal experience, there were three such men, and one of them was Andrei Nikolaevich Kolmogorov. I was lucky enough to be his immediate pupil. He invited me to be his pupil at the third year of my being student at the Moscow University. This talk is my tribute, my homage to my great teacher.

Andrei Nikolaevich Kolmogorov was born on April 25, 1903. He graduated from Moscow University in 1925, finished his post-graduate education at the same University in 1929, and since then without any interruption worked at Moscow University till his death on October 20, 1987, at the age 84½.

Kolmogorov was not only one of the greatest mathematicians of the twentieth century. By the width of his scientific interests and results he reminds one of the titans of the Renaissance. Indeed, he made prominent contributions to various fields from the theory of shooting to the theory of versification, from hydrodynamics to set theory. In this talk I should like to expound his contributions to mathematical logic.

Here the term “mathematical logic” is understood in a broad sense. In this sense it, like Gallia in Caesarian times, is divided into three parts:

(1) mathematical logic in the strict sense, i.e. the theory of formalized languages including deduction theory,

(2) the foundations of mathematics, and

(3) the theory of algorithms.
Descriptive set theory and harmonic analysis
Authors: Kechris A. S. , Louveau A.
Published: May 2006

During the 1989 European ASL Summer Meeting in Berlin, the authors gave a series of eight lectures (short course) on the topic of the title. This survey article consists basically of the lecture notes for that course distributed to the participants of that conference. We have purposely tried in this printed version to preserve the informal style of the original notes.

Let us say first a few things aboui the content of these lectures. Our aim has been to present some recent work in descriptive set theory and its applications to an area of harmonic analysis. Typical uses of descriptive set theory in analysis are most often through regularity properties of definable sets, like measurability, the property of Baire, capacitability, etc., which are used to show that certain problems have solutions that behave nicely. In the theory we will present, definability itself, in fact the precise analysis of the “definable complexity” of certain sets, will be the main concern. It will be through such knowledge that we will be able to infer important structural properties of various objects which will then be used to solve analysis problems.

The first lecture provides a short historical introduction to the subject of uniqueness for trigonometric series, which is the area of harmonic analysis whose problems are the origin of this work. As is well known, it was Cantor who proved the first major result in this subject in 1870, and it was his subsequent work here that led him to the creation of set theory.
Cuts in hyperfinite time lines
Authors: Jin Renling
Published: May 2006

In an ω1-saturated nonstandard universe a cut is an initial segment of the hyperinlegers which is closed under addition. Keisler and Leth in [KL] introduced, for each given cut U, a corresponding U-topology on the hyperintegers by letting O be U-open if for any x ϵ O there is a y greater than all the elements in U such that the interval [x − y, x + y] ⊆ O. Let U be a cut in a hyperfinite time line , which is a hyperfinite initial segment of the hyperintegers. U is called a good cut if there exists a U-meager subset of of Loeb measure one. Otherwise U is bad. In this paper we discuss the questions of Keisler and Leth about the existence of bad cuts and related cuts. We show that assuming b > ω1, every hyperfinite time line has a cut with both cofinality and coinitiality uncountable. We construct bad cuts in a nonstandard universe under ZFC. We also give two results about the existence of other kinds of cuts.
Continuity properties in constructive mathematics
Authors: Ishihara Hajime
Published: May 2006

The purpose of this paper is an axiomatic study of the interrelations between certain continuity properties. We deal with principles which are equivalent to the statements “every mapping is sequentially nondiscontinuous”, “every sequentially nondiscontinuous mapping is sequentially continuous”, and “every sequentially continuous mapping is continuous”. As corollaries, we show that every mapping of a complete separable space is continuous in constructive recursive mathematics (the Kreisel-Lacombe-Schoenfield-Tsejtin theorem) and in intuitionism.
The density of the meet-inaccessible r. e. degrees
Authors: Qinglong Zhang
Published: May 2006

In this paper it is shown that the meet-inaccessible degrees are dense in R. The construction uses an 0′-priority argument. As a consequence, the meet-inaccessible degrees and the meet-accessible degrees give a partition of R into two sets, either of which is a nontrivial dense subset of R and generates R − {0} under joins (thus an automorphism base of R).
A sharp version of the bounded Matijasevich conjecture and the end-extension problem
Authors: Adamowicz Zofia
Published: May 2006

Under a sharp version of the assumption I∆0 ⊢ ¬ ∆0H we characterize models of I∆0 + BΣ1 having a proper end extension to a model of I∆0.

In [WP] Wilkie and Paris study the relationship between the existence of a proper end extension of a model and its “fullness”, which is related to a certain weak overspill principle (we recall the definition of fullness in §3). Let M be a countable nonstandard model of I∆0 + BΣ1. Under the hypothesis I∆0 ⊢ ¬ ∆0H they prove the following (Corollaries 7 and 8):

The following are equivalent:

1) M has a proper end extension to a model of I∆0 + BΣ1.

2) M is (I∆0 + BΣ1)-full.

Moreover, assuming that there is no t ∈ M such that for v ∈ M, 2[t/v]exists if and only if v < N, the following are equivalent:

1) M has a proper end extension to a model of I∆0.

2) M is I∆0-full.

Wilkie and Paris ask whether the assumption on the structure of the model can be eliminated from the second equivalence.

We eliminate it, but we sharpen the assumption I∆0 ⊢ ¬ ∆0H. So we partially answer their question.
Nonmonotonic consequence based on intuitionistic logic
Authors: Servi Gisèle Fischer
Published: May 2006

Research in AI has recently begun to address the problems of nondeductive reasoning, i.e., the problems that arise when, on the basis of approximate or incomplete evidence, we form well-reasoned but possibly false judgments. Attempts to stimulate such reasoning fall into two main categories: the numerical approach is based on probabilities and the nonnumerical one tries to reconstruct nondeductive reasoning as a special type of deductive process. In this paper, we are concerned with the latter usually known as nonmonotonic deduction, because the set of theorems does not increase monotonically with the set of axioms.

It is generally acknowledged that nonmonotonic (n.m.) formalisms (e.g., [C], [MC1], [MC2] [MD], [MD-D], [Rl], [R2], [S]) are plagued by a number of difficulties. A key issue concerns the fact that most systems do not produce an axiomatizable set of validities. Thus, the chief objective of this paper is to develop an alternative approach in which the set of n.m. inferences, which somehow qualify as being deductively sound, is r.e.

The basic idea here is to reproduce the situation in First Order Logic where the metalogical concept of deduction translates into the logical notion of material implication. Since n.m. deductions are no longer truth preserving, our way to deal with a change in the metaconcept is to extend the standard logic apparatus so that it can reflect the new metaconcept. In other words, the intent is to study a concept of nonmonotonic implication that goes hand in hand with a notion of n.m. deduction. And in our case, it is convenient that the former be characterized within the more tractable context of monotonic logic.
There is no sharp transitivity on q6 when q is a type of Morley rank 2
Authors: Gropp Ursula
Published: May 2006

In this paper we study transitive group actions.:G × X → X, definable in an ω-stable theory, where G is a connected group and X a set of Morley rank 2, with respect to sharp transitivity on qα. Here q is the generic type of X (X is of degree 1 by Proposition (1)), for ordinals α > 0, qα is the αth power of q, i.e. (aβ)β < α, ⊨ qα iff (aβ)β < α is an independent sequence (in the sense of forking) of realizations of q, and G is defined to be sharply transitive on qα iff for all (aβ)β < α, (bβ)β < α ⊨ qα there is one and only one g ∈ G with g.aβ = bβ for all β < α. The question studied here is: For which powers α of q are there group actions subject to the above conditions with G sharply transitive on qα?

In §1 we will see that for group actions satisfying the above conditions, G can be sharply transitive only on finite powers of q. Moreover, if G is sharply transitive on qn for some n ≥ 2, then the action of the stabilizer Ga on a certain subset Y of X satisfies the conditions above with Ga being sharply transitive on qm−1, where q′ is the generic type of Y (Proposition (8)). Thus, there would be a complete answer to the question if one could find some n < ω such that there is no group action as above with G sharply transitive on qn, but for n – 1 there is. In this paper we prove that such n exists and that it is either 5 or 6. More precisely, in §2 we prove that there is no group action satisfying the above conditions with G sharply transitive on q6. This is the main result of this paper. It is not known to the author whether the same also holds for q5 instead of q6. However, it does not hold for q4, as is seen in §3. There we give an example provided from projective geometry, for a group action satisfying the above conditions with G sharply transitive on q4; for G we choose PGL(3, K) and for X the projective plane over K, where K is some algebraically closed field.
Full reflection at a measurable cardinal
Authors: Jech Thomas , Witzany Jiří
Published: May 2006

A stationary subset S of a regular uncountable cardinal κreflects fully at regular cardinals if for every stationary set T ⊆ κ of higher order consisting of regular cardinals there exists an α Є T such that S ∩ α is a stationary subset of α. Full Reflection states that every stationary set reflects fully at regular cardinals. We will prove that under a slightly weaker assumption than κ having the Mitchell order κ++ it is consistent that Full Reflection holds at every λ ≤ κ and κ is measurable.
Nonexistence of universal orders in many cardinals
Authors: Kojman Menachem , Shelah Saharon
Published: May 2006

Our theme is that not every interesting question in set theory is independent of ZFC. We give an example of a first order theoryTwith countableD(T)which cannot have a universal model at ℵ1; without CH; we prove in ZFC a covering theorem from the hypothesis of the existence of a universal model for some theory; and we prove—again in ZFC—that for a large class of cardinals there is no universal linear order (e.g. in every regular). In fact, what we show is that if there is a universal linear order at a regularλand its existence is not a result of a trivial cardinal arithmetical reason, thenλ“resembles” ℵ1—a cardinal for which the consistency of having a universal order is known. As for singular cardinals, we show that for many singular cardinals, if they are not strong limits then they have no universal linear order. As a result of the nonexistence of a universal linear order, we show the nonexistence of universal models for all theories possessing the strict order property (for example, ordered fields and groups, Boolean algebras,p-adic rings and fields, partial orders, models of PA and so on).
A characterization of ML in many-sorted arithmetic with conditional application
Authors: Swaen M. D. G.
Published: May 2006

In this paper we discuss an interpretation of intuitionistic type theory in many-sorted arithmetic with so-called conditional application. Via the formulas-as-types correspondence the arithmetical system in turn can be embedded inML, resulting in a characterization of strong Σ-elimination by an axiom of conditional choice.
A theorem on the isomorphism property
Authors: Jin Renling
Published: May 2006

An -structure is called internally presented in a nonstandard universe if its base set and interpretation of every symbol in are internal. A nonstandard universe is said to satisfy the κ-isomorphism property if for any two internally presented -structures and , where has less than κ many symbols, is elementarily equivalent to implies that is isomorphic to . In this paper we prove that the ℵ1-isomorphism property is equivalent to the ℵ0-isomorphism property plus ℵ1-saturation.
Building iteration trees
Authors: Andretta Alessandro
Published: May 2006

It is shown, assuming the existence of a Woodin cardinal δ, that every tree ordering on some limit ordinal λ < δ with a cofinal branch is the tree ordering of some iteration tree on V.
A combinatorial forcing for coding the universe by a real when there are no sharps
Authors: Shelah Saharon , Stanley Lee J.
Published: May 2006

Assuming 0#does not exist, we present a combinatorial approach to Jensen's method of coding by a real. The forcing uses combinatorial consequences of fine structure (including the Covering Lemma, in various guises), but makes no direct appeal to fine structure itself.
Delineating classes of computational complexity via second order theories with weak set existence principles. I
Authors: Ignjatović Aleksandar
Published: May 2006

In this paper we characterize the well-known computational complexity classes of the polynomial time hierarchy as classes of provably recursive functions (with graphs of suitable bounded complexity) of some second order theories with weak comprehension axiom schemas but without any induction schemas (Theorem 6). We also find a natural relationship between our theories and the theories of bounded arithmetic (Lemmas 4 and 5). Our proofs use a technique which enables us to “speed up” induction without increasing the bounded complexity of the induction formulas. This technique is also used to obtain an interpretability result for the theories of bounded arithmetic (Theorem 4).
The dense linear ordering principle
Authors: Pincus David
Published: May 2006

Let DO denote the principle: Every infinite set has a dense linear ordering. DO is compared to other ordering principles such as O, the Linear Ordering principle, KW, the Kinna-Wagner Principle, and PI, the Prime Ideal Theorem, in ZF, Zermelo-Fraenkel set theory without AC, the Axiom of Choice.

The main result is:

Theorem. AC ⇒ KW ⇒ DO ⇒ O, and none of the implications is reversible in ZF + PI.

The first and third implications and their irreversibilities were known. The middle one is new. Along the way other results of interest are established. O, while not quite implying DO, does imply that every set differs finitely from a densely ordered set. The independence result for ZF is reduced to one for Fraenkel-Mostowski models by showing that DO falls into two of the known classes of statements automatically transferable from Fraenkel-Mostowski to ZF models. Finally, the proof of PI in the Fraenkel-Mostowski model leads naturally to versions of the Ramsey and Ehrenfeucht-Mostowski theorems involving sets that are both ordered and colored.
Undefinability of κ-well-orderings in L∞κ
Authors: Oikkonen Juha
Published: May 2006

We prove that the class of trees with no branches of cardinality ≤ κ is not RPC definable in L∞κ when κ is regular. Earlier such a result was known for under the assumption κ<κ = κ. Our main result is actually proved in a stronger form which covers also L∞κ (and makes sense there) for every strong limit cardinal λ < κ of cofinality κ.
An addition to Rosser's theorem
Authors: Kotlarski Henryk
Published: May 2006

For a primitive recursive consistent and strong enough theoryTwe construct an independent statement which has some clear metamathematical meaning.
Non-constructive Galois-Tukey connections
Authors: Mildenberger Heike
Published: May 2006

There are inequalities between cardinal characteristics of the continuum that are true in any model of ZFC, but without a Borel morphism proving the inequality. We answer some questions from Blass [1].
Contiguity and distributivity in the enumerable Turing degrees
Authors: Downey Rodney G. , Lempp Steffen
Published: May 2006

We prove that a (recursively) enumerable degree is contiguous iff it is locally distributive. This settles a twenty-year old question going back to Ladner and Sasso. We also prove that strong contiguity and contiguity coincide, settling a question of the first author, and prove that no m-topped degree is contiguous, settling a question of the first author and Carl Jockusch [11]. Finally, we prove some results concerning local distributivity and relativized weak truth table reducibility.
Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem
Authors: Bès Alexis
Published: May 2006

Letkandlbe two multiplicatively independent integers, and letL⊆ ℕnbe al-recognizable set which is not definable in 〈ℕ; +〉. We prove that the elementary theory of 〈ℕ; +,Vk, L〉, whereVk(x)denotes the greatest power ofkdividingx, is undecidable. This result leads to a new proof of the Cobham-Semënov theorem.
Minimal models of Heyting arithmetic
Authors: Moerdijk Ieke , Palmgren Erik
Published: May 2006

In this paper, we give a constructive nonstandard model of intuitionistic arithmetic (Heyting arithmetic). We present two axiomatisations of the model: one finitary and one infinitary variant. Using the model these axiomatisations are proven to be conservative over ordinary intuitionistic arithmetic. The definition of the model along with the proofs of its properties may be carried out within a constructive and predicative metatheory (such as Martin-Löf's type theory). This paper gives an illustration of the use of sheaf semantics to obtain effective proof-theoretic results.

The axiomatisations of nonstandard intuitionistic arithmetic (to be calledHAIandHAIωrespectively) as well as their model are based on the construction in [5] of a sheaf model for arithmetic using a site of filters. In this paper we present a “minimal” version of this model, built instead on a suitable site of provable filter bases. The construction of this site can be viewed as an extension of the well-known construction of the classifying topos for a geometric theory which uses “syntactic sites”. (Such sites can in fact be used to prove semantical completeness of first order logic in a strictly constructive framework, see [6].)

We should mention that for classical nonstandard arithmetics there are several nonconstructive methods of proving conservativity over arithmetic, e.g. the compactness theorem, Mac Dowell–Specker's theorem [3].
Canonical formulas for K4. Part II: Cofinal subframe logics
Authors: Zakharyaschev Michael
Published: May 2006

This paper is a continuation of Zakharyaschev [25], where the following basic results on modal logics with transitive frames were obtained:

• With every finite rooted transitive frame and every set of antichains (which were called closed domains) in two formulas α (, , ⊥) and α(, ) were associated. We called them the canonical and negation free canonical formulas, respectively, and proved the Refutability Criterion characterizing the constitution of their refutation general frames in terms of subreduction (alias partial p-morphism), the cofinality condition and the closed domain condition.

• We proved also the Completeness Theorem for the canonical formulas providing us with an algorithm which, given a modal formula φ, returns canonical formulas α(i, i), ⊥), for i = 1,…, n, such that

if φ is negation free then the algorithm instead of α(i, i, ⊥) can use the negation free canonical formulas α(i, i). Thus, every normal modal logic containing K4 can be axiomatized by a set of canonical formulas.

In this Part we apply the apparatus of the canonical formulas for establishing a number of results on the decidability, finite model property, elementarity and some other properties of modal logics within the field of K4.

Our attention will be focused on the class of logics which can be axiomatized by canonical formulas without closed domains, i.e., on the logics of the form

Adapting the terminology of Fine [11], we call them the cofinal subframe logics and denote this class by . As was shown in Part I, almost all standard modal logics are in .
Boolean algebras, Stone spaces, and the iterated Turing jump
Authors: Jockusch Carl G. , Soare Robert I.
Published: May 2006

We show, roughly speaking, that it requires ω iterations of the Turing jump to decode nontrivial information from Boolean algebras in an isomorphism invariant fashion. More precisely, if α is a recursive ordinal, is a countable structure with finite signature, and d is a degree, we say that has αth-jump degreed if d is the least degree which is the αth jump of some degree c such there is an isomorphic copy of with universe ω in which the functions and relations have degree at most c. We show that every degree d ≥ 0(ω) is the ωth jump degree of a Boolean algebra, but that for n < ω no Boolean algebra has nth-jump degree d < 0(n). The former result follows easily from work of L. Feiner. The proof of the latter result uses the forcing methods of J. Knight together with an analysis of various equivalences between Boolean algebras based on a study of their Stone spaces. A byproduct of the proof is a method for constructing Stone spaces with various prescribed properties.
The critical number of a variable in a function
Authors: Takeuti Gaisi
Published: May 2006

LetL0be a language on ℕ consisting of 0, 1, +, ∸, ·, ⌊½a⌋, ∣a∣, #, ∧(a,b), ∨(a,b), ¬(a), ≤ (a,b), andμx≤ ∣s∣t(x). Hereμx≤ ∣s∣t(x) is the smallest numberx≤ ∣s∣ satisfyingt(x) > 0 and 0 if there exist no suchxand we stipulate that ifsandt(a) are terms inLo, thenμx≤ ∣s∣t(x) is also a term inLo. The defining axioms of functions ∧(a,b), ∨(a,b), ¬(a), ≤ (a,b) are as follows:

LetLa language on ℕ with only predicate constant = andL0⊆L. Letf(b,a1,…,am) be a function for ℕm+1into ℕ. We say “fis weakly expressed by termst1(b,a1,…,am),…,tr(b,a1,…,am) inL” if for everyb,a1,…,am∈ ℕ,f(b,a1,…,am) is equal to one ofti(b,a1, …,am). The critical number ofbinfwith respect toLis the minimum numbernsuch that wheneverf(b,a1,…,an) is weakly expressed by termst1(b,a1, …,an),…, the number of occurrences ofbin someti(b,a1,…,an) is at leastn.

As is defined in [1], a functionfis defined by a limited iteration fromgandhwith respect toLiff the following holds: Letτbe defined as

with the condition; andis defined by

whereandare terms inL. We say “fis defined by a short limited iteration fromgandh” ifis defined by

whereτ,s, tare the same as above satisfying the condition.
Initial segments of the lattice of ideals of r.e. degrees
Authors: Weber Frank P.
Published: May 2006

Embeddings into initial segments of (the lattice of ideals of r.e. degrees) are relevant for the investigation of decidability of (fragments of) the theory of (with constant-symbols denoting principal ideals). Interest in this investigation stems from open problems concerning decidability of fragments of the theory of R (the usl of r.e. degrees) and embeddings into R. Ambos-Spies and Lerman established comprehensive nonembeddability [AS/LR1] and embeddability [AS/LR2] conditions, but their complementarity is open. (For background on embeddings and decidability consult Lerman [LR1] and Lerman and Shore [LR/SH].) The first systematic investigation of embeddings into is in Calhoun [CL], where the existence of uniform bounds, in the case of embeddings into , on the number of “join traces” arising with nondistributive lattices is shown to remove “obstructions” to lattice-embeddings into R (such as typified in the nonembeddable lattice S8, see [LA/SR], [AS/LR1/). The analysis to follow extends this, by showing that it also removes the “obstruction” to lattice-embeddings into initial segments of R, arising with Lachlan's M5, which embeds into R, but not into every nontrivial initial segment R[0, a], by a result of Downey [DW]. The techniques are Lachlan's [LA], as adapted in Lerman's “pinball machine model” [LR1, LR2], combined with Fejer's “meet-trick” [FJ] as used by Downey [DW] in the proof that every distributive lattice is embeddable into every nontrivial initial segment of r.e. degrees R[0, a], a > 0. We present a sufficient condition, “allowing evasion” [Definition 4.2] for lattice embeddability into every [0, a], a > 0.
Undecidability in diagonalizable algebras
Authors: Shavrukov V. Yu.
Published: May 2006

If a formal theory T is able to reason about its own syntax, then the diagonalizable algebra of T is defined as its Lindenbaum sentence algebra endowed with a unary operator □ which sends a sentence φ to the sentence □φ asserting the provability of φ in T. We prove that the first order theories of diagonalizable algebras of a wide class of theories are undecidable and establish some related results.
A special class of almost disjoint families
Authors: Leathrum Thomas E.
Published: May 2006

The collection of branches (maximal linearly ordered sets of nodes) of the tree <ωω (ordered by inclusion) forms an almost disjoint family (of sets of nodes). This family is not maximal — for example, any level of the tree is almost disjoint from all of the branches. How many sets must be added to the family of branches to make it maximal? This question leads to a series of definitions and results: a set of nodes is off-branch if it is almost disjoint from every branch in the tree; an off-branch family is an almost disjoint family of off-branch sets; and is the minimum cardinality of a maximal off-branch family.

Results concerning include: (in ZFC) , and (consistent with ZFC) is not equal to any of the standard small cardinal invariants or = 2ω. Most of these consistency results use standard forcing notions—for example, in the Cohen model.

Many interesting open questions remain, though—for example, whether .