bluuebunny/crossref_metadata_2025 huggingface dataset:
Normal functions and constructive ordinal notations
Authors: Miller Larry W.
Published: May 2006

An r-normal function is a strictly increasing continuous function from r to r where r is a regular ordinal > ω (identify an ordinal with the set of smaller ordinals). Given an r-normal function f one can form a sequence {f(x, −)}x 0, f(x, −) enumerates in order {z ∣ f(y, z) = z for all y < x}, the common fixed points of the f(y, −)'s for y < x. In this paper we give as readable an exposition as we can of Veblen hierarchies and of Bachmann's and Isles's techniques in [3] and [15] of using higher finite number classes for forming sequences {f(x, −)}x r of r-normal functions which extend the Veblen hierarchy on f. We will show how these sequences—Bachmann hierarchies—yield extremely natural constructive notations for ordinals in various initial segments of the second number class. We will also consider various other techniques for obtaining constructive ordinal notations and relate them to the notations obtained by Bachmann's and Isles's techniques. In particular, we will use these notations to characterize as directly and as usefully as we can various of Takeuti's systems of constructive ordinal notations, which he calls ordinal diagrams ([31], [32]).
Relative consistency of an extension of Ackermann's set theory
Authors: Lake John
Published: May 2006

The set theory AFC was introduced by Perlis in [2] and he noted that it both includes and is stronger than Ackermann's set theory. We shall give a relative consistency result for AFC.

AFC is obtained from Ackermann's set theory (see [2]) by replacing Ackermann's set existence schema with the schema

(where ϕ, ψ, are ∈-formulae, x is not in ψ, w is not in ϕ, y is y1, …, yn, z is z1, …, zm and all free variables are shown) and adding the axiom of choice for sets. Following [1], we say that λ is invisible in Rκ if λ < κ and we have

holding for every ∈-formula θ which has exactly two free variables and does not involve u or υ. The existence of a Ramsey cardinal implies the existence of cardinals λ and κ with λ invisible in Rκ, and Theorem 1.13 of [1] gives some further indications about the relative strength of the notion of invisibility.

Theorem. If there are cardinals λ and κ with λ invisible in Rκ, then AFC is consistent.

Proof. Suppose that λ is invisible in Rκ and we will show that 〈Rκ, Rλ, ∈〉 ⊧ AFC (Rλ being the interpretation of V, of course).
Effective coloration
Authors: Bean Dwight R.
Published: May 2006

We are concerned here with recursive function theory analogs of certain problems in chromatic graph theory. The motivating question for our work is: Does there exist a recursive (countably infinite) planar graph with no recursive 4-coloring? We obtain the following results: There is a 3-colorable, recursive planar graph which, for all k, has no recursive k-coloring; every decidable graph of genus p ≥ 0 has a recursive 2(x(p) − 1)-coloring, where x(p) is the least number of colors which will suffice to color any graph of genus p; for every k ≥ 3 there is a k-colorable, decidable graph with no recursive k-coloring, and if k = 3 or if k = 4 and the 4-color conjecture fails the graph is planar; there are degree preserving correspondences between k-colorings of graphs and paths through special types of trees which yield information about the degrees of unsolvability of k-colorings of graphs.
Adding a closed unbounded set
Authors: Baumgartner J. E. , Harrington L. A. , Kleinberg E. M.
Published: May 2006

The extreme interest of set theorists in the notion of “closed unbounded set” is epitomized in the following well-known theorem:

Theorem A. For any regular cardinal κ > ω, the intersection of any two closed unbounded subsets of κ is closed and unbounded.

The proof of this theorem is easy and in fact yields a stronger result, namely that for any uncountable regular cardinal κ the intersection of fewer than κ many closed unbounded sets is closed and unbounded. Thus, if, for κ a regular uncountable cardinal, we let denote {A ⊆ κ ∣ A contains a closed unbounded subset}, then, for any such κ, is a κ-additive nonprincipal filter on κ.

Now what about the possibility of being an ultrafilterκ It is routine to see that this is impossible for κ > ℵ1. However, for κ = ℵ1 the situation is different. If were an ultrafilter, ℵ1 would be a measurable cardinal. As is well-known this is impossible if we assume the axiom of choice; however if ZF + “there exists a measurable cardinal” is consistent, then so is ZF + “ℵ1 is a measurable cardinal” [2]. Furthermore, under the assumption of certain set theoretic axioms (such as the axiom of determinateness or various infinite exponent partition relations) can be proven to be an ultrafilter. (See [3] and [5].)
Model Theoretic Algebra
Authors: Cherlin G. L.
Published: May 2006

Since the late 1940's model theory has found numerous applications to algebra. I would like to indicate some of the points of contact between model theoretic methods and strictly algebraic concerns by means of a few concrete examples and typical applications.

§1. The Lefschetz principle. Algebraic geometry has proved to be a fruitful source of model theoretic ideas. What exactly is algebraic geometry? We consider a field K, and let Kn be the set of n-tuples (a1 … an) with coordinates ai in K. Kn is called affine n-space over K. Fix polynomials p1 …, pk in K[x1, …, xn] and define

that is V(p1 …, pk) is the locus of common zeroes of the pi in Kn. We call V(Pi …, Pk) the algebraic variety determined by p1, …, pk. With this terminology we may say:

Algebraic geometry is the study of algebraic varieties defined over an arbitrary field K. This definition lacks both rigor and accuracy, and we will indicate below how it may be improved.

So far we have placed no restrictions on the base field K. Following Weil [4] it is convenient to start with a so-called “universal domain”; in other words take K to be algebraically closed and of infinite transcendence degree over the prime field. Any particular field can of course be embedded in such a universal domain.
A complete infinitary logic
Authors: Slonneger Kenneth
Published: May 2006

This paper is concerned with the proof theoretic development of certain infinite languages. These languages contain the usual infinite conjunctions and disjunctions, but in addition to homogeneous quantifiers such as ∀x0x1x2 … and ∃y0y1y2 …, we shall investigate particular subclasses of the dependent quantifiers described by Henkin [1]. The dependent quantifiers of Henkin can be thought of as partially ordered quantifiers defined by a function from one set to the power set of another set. This function assigns to each existentially bound variable, the set of universally bound variables on which it depends.

The natural extension of Gentzen's first order predicate calculus to an infinite language with homogeneous quantifiers results in a system that is both valid and complete, and in which a cut elimination theorem can be proved [2]. The problem then arises of devising, if possible, a logical system dealing with general dependent quantifiers that is valid and complete. In this paper a system is presented that is valid and complete for an infinite language with homogeneous quantifiers and dependent quantifiers that are anti-well-ordered, for example, … ∀x2∃y2∀x1∃y1∀x0∃y0.

Certain notational conventions will be employed in this paper. Greek letters will be used for ordinal numbers. The ordinal ω is the set of all natural numbers, and 2ω is the set of all ω -sequences of elements of 2 = {0,1}. The power set of S is denoted by P(S). μα[A(α)] stands for the smallest ordinal α such that A (α) holds.
Comparison of Russell's resolution of the semantical antinomies with that of Tarski
Authors: Church Alonzo
Published: May 2006

In this paper we treat the ramified type theory of Russell [6], afterwards adopted by Whitehead and Russell inPrincipia mathematica[12], so that we may compare Russell's resolution of the semantical antinomies by ramified type theory with the now widely accepted resolution of them by the method of Tarski in [7], [8], [9].

To avoid impredicativity the essential restriction is that quantification over any domain (type) must not be allowed to add new members to the domain, as it is held that adding new members changes the meaning of quantification over the domain in such a way that a vicious circle results. As Whitehead and Russell point out, there is no one particular form of the doctrine of types that is indispensable to accomplishing this restriction, and they have themselves offered two different versions of the ramified hierarchy in the first edition ofPrincipia(seePreface, p. vii). The version in §§58–59 of the writer's [1], which will be followed in this paper, is still slightly different.

To distinguish Russellian types or types in the sense of the ramified hierarchy from types in the sense of the simple theory of types, let us call the formerr-types.

There is an r-typeito which the individual variables belong. Ifβ1,β2, …,βmare any given r-types,m≧ 0, there is an r-type (β1,β2, …,βm)/nto which there belongm-ary functional variables of leveln,n≧ 1. The r-type (α1,α2, …,αm)/kis said to bedirectly lowerthan the r-type (β1,β2, …,βm)/nifα1=β1,α2=β2, …,αm=βm,k<n.
The intersection of nonstandard models of arithmetic
Authors: Blass Andreas
Published: May 2006

If two nonstandard models of complete arithmetic are elementarily embedded in a third, then their intersection may be considerably smaller than either of them; indeed, the intersection may be only the standard model. For example, if D and E are nonprincipal ultrafilters on ω, then the nonstandard models D-prod and E-prod (where is the standard model) have canonical elementary embeddings into D-prod (E-prod , and the intersection of their images is easily seen to be the (canonical image of the) standard model. In this paper, we shall prove that, under certain conditions, this phenomenon will not occur. Our main result (Theorem 3) is that the intersection of countably many pairwise cofinal models is itself cofinal with these models, provided that at least one of them is generated by a single element. (Precise definitions will be given below.)

The theorems in this paper were first formulated in terms of ultrafilters, then rephrased (using the methods of Chapter III of [1]) as statements about ultra-powers of , and finally generalized to their present form. Since the theorems and their proofs are now entirely model-theoretic, they are presented here separately from the study of ultrafilters in which they originated. That study, including applications of the present results, will appear in [2].

Let L be the first-order language whose n-place relation symbols are all the relations R ⊆; ωn and whose n-place function symbols are all the functions f: ωn → ω. Let be the standard model for L; its universe is ω and every nonlogical symbol of L denotes itself. Let be an elementary extension of . The relation (or function) denoted by R (or f) in will be called *R (or *f).
Semantic analysis of tense logics
Authors: Thomason S. K.
Published: May 2006

Although we believe the results reported below to have direct philosophical import, we shall for the most part confine our remarks to the realm of mathematics. The reader is referred to [4] for a philosophically oriented discussion, comprehensible to mathematicians, of tense logic.

The “minimal” tense logicT0is the system having connectives ∼, →,F(“at some future time”), andP(“at some past time”); the following axioms:

(whereGandHabbreviate ∼F∼ and ∼P∼ respectively); and the following rules:

(8) fromαandα → β, inferβ,

(9) fromα, infer any substitution instance ofα,

(10) fromα, inferGα,

(11) fromα, inferHα.

A tense logic is a systemTwhose language is that ofT0and whose axioms and rules include (1)–(11). The axioms and rules ofTother than (1)–(11) are calledproperaxioms and rules.

We shall investigate three systems of semantics for tense logics, i.e. three notions ofstructureand three relations ⊧ which stand between structures and formulas. One reads⊧αas “αis valid in.” A structureis amodelof a tense logicTif every formula provable inTis valid in. A semantics isadequateforTif the set of models ofTin the semantics is characteristic forT, i.e. if wheneverT ∀ αthen there is a modelofTin the semantics such that∀ α. Two structuresand, possibly from different semantics, are calledequivalent(∼) if exactly the same formulas are valid inas in.
Σn sets which are Δn-incomparable (uniformly)
Authors: Shore Richard A.
Published: May 2006

In this paper we will present an application of generalized recursion theory to (noncombinatorial) set theory. More precisely we will combine a priority argument in α-recursion theory with a forcing construction to prove a theorem about the interdefinability of certain subsets of admissible ordinals.

Our investigation was prompted by G. Sacks and S. Simpson asking [6] if it is obvious that there are, for each Σn-admissible α, Σn (over Lα) subsets of α which are Δn-incomparable. If one understands “B is Δn in C” to mean that there are Σn/Lα reduction procedures which put out B and when one feeds in C, then the answer is an unqualified “yes.” In this sense “Δn in” is a direct generalization of “α-recursive in” (replace Σ1 by Σn in the definition) and so amenable to the methods of [7, §§3, 5]. Indeed one simply chooses a complete Σn−1 set A and mimics the construction of [6] as modified in [7, §5] to produce two α-A-r.e. sets B and C neither of which is α-A-recursive in the other. By the remarks on translation [7, §3] this will immediately give the desired result for this definition of “Δn in.”

There is, however, the more obvious and natural notion of “Δn in” to be considered: B is Δn in C iff there are Σn and Πn formulas of ⟨Lα, C⟩ which define B.
On power-like models for hyperinaccessible cardinals
Authors: Schmerl James H. , Shelah Saharon
Published: May 2006

The main result of this paper is the following transfer theorem: If T is an elementary theory which has a κ-like model where κ is hyperinaccessible of type ω, then T has a λ-like model for each λ > card(T). Helling [3] obtained the same conclusion under the stronger hypothesis that κ is weakly compact. Fuhrken conjectured in [1] that the same conclusion would result if κ were merely inaccessible. (He also showed there the connection with a problem about generalized quantifiers.) Thus, our theorem lies properly between Helling's theorem and Fuhrken's conjecture. In [9] it is shown that this theorem is actually the best possible. This theorem and the other results of this paper were announced by the authors in [10].

In §1 we prove as Theorem 1 a slightly stronger form of the above theorem. This theorem is generalized in §2 to Theorem 2 which concerns theories which permit the omitting of types. The methods used in §§1 and 2 are also applicable to problems regarding Hanf numbers as well as to two-cardinal problems.
On the undecidability of finite planar cubic graphs
Authors: Garfunkel Solomon , Shank Herbert
Published: May 2006

In the March, 1971 issue of this Journal [1] a paper of ours was published purporting to prove the hereditary undecidability of the first-order theory of finite planar graphs. The proof presented there contains an error which is unfortunately “unfixable” by the methods of that paper. The theorem however is true and we demonstrate here a generalization to finite cubic (exactly three edges at each vertex) planar graphs. The method involves coding the halting problem for a Turing machine into the theory of these graphs by considering special printouts of computations. Let us first consider a discussion of the aforementioned mistake and see what can be learned from it.

By a graph we will mean a nonempty set V of points together with a set I of unordered pairs of points of V. Each point i = {u, v) ∈ I is an edge of A graph is called finite if ∣V∣ is finite. A graph is said to be planar iff it can be embedded in the plane (i.e., drawn in the plane so that no two edges intersect).

In the earlier paper the method of proof was a semantic embedding of certain binary relations into finite planar graphs. The essential idea was, for a given relation, to let the vertices of the graph interpret the field of the relation and the edges represent the related pairs. This method works for arbitrary graphs, but in the planar case has two main difficulties.
Ordinals connected with formal theories for transfinitely iterated inductive definitions
Authors: Pohlers W.
Published: May 2006

Let Th be a formal theory extending number theory. Call an ordinal ξ provable in Th if there is a primitive recursive ordering which can be proved in Th to be a wellordering and whose order type is > ξ. One may define the ordinal ∣ Th ∣ of Th to be the least ordinal which is not provable in Th. By [3] and [12] we get , where IDN is the formal theory for N-times iterated inductive definitions. We will generalize this result not only to the case of transfinite iterations but also to a more general notion of ‘the ordinal of a theory’.

For an X-positive arithmetic formula [X,x] there is a natural norm ∣x∣: = μξ (x ∈ Iξ), where Iξ is defined as {x: [∪μ<ξIμ, x]} by recursion on ξ (cf. [7], [17]). By P we denote the least fixed point of [X,x]. Then P = ∪ξξ holds. If Th allows the formation of P, we get the canonical definitions ∥Th()∥ = sup{∣x∣ + 1: Th ⊢ x ∈ P} and ∥Th∥ = sup{∥Th()∥: P is definable in Th} (cf. [17]). If ≺ is any primitive recursive ordering define Q≺[X,x] as the formula ∀y(y ≺ x → y ∈ X) and ∣x∣≺:= ∣x∣O≺. Then ∣x∣≺ turns out to be the order type of the ≺ -predecessors of x and P is the accessible part of ≺. So Th ⊢ x ∈ P implies the provability of ∣x∣≺ in Th.
An inelastic model with indiscernibles
Authors: Knight Julia F.
Published: May 2006

Let L be a countable language including the unary relation symbol U. Let and be L-structures such that is a proper elementary U-extension of ; i.e., , and . Under what conditions will have a proper elementary U-extension? In [2], it was shown that this is not always the case, even if and are countable. However, the examples given are completely artificial, and it still seems that in most cases will have a proper elementary U-extension.

Lascar asked whether will necessarily have a proper elementary U-extension whenever it contains an infinite set of indiscernibles over . This paper gives a counterexample for Lascar's question. The example is produced by modifying one of the examples in [2], using an idea of Marcus [5].

Models containing an infinite set of indiscernibles can often be “stretched” to produce larger models that share some desired nonelementary property with the original [1], [6]. However, the mere presence of indiscernibles in a model does not guarantee that it can be used in this way.

If the model is not completely determined by the indiscernibles, the nonelementary property may not carry over to larger models. An example of this is given in [3]. The example for Lascar's question is further evidence that models with indiscernibles need not be “elastic”.
Three universal representations of recursively enumerable sets
Authors: Jones James P.
Published: May 2006

In his celebrated paper of 1931 [7], Kurt Gödel proved the existence of sentences undecidable in the axiomatized theory of numbers. Gödel's proof is constructive and such a sentence may actually be written out. Of course, if we follow Gödel's original procedure the formula will be of enormous length.

Forty-five years have passed since the appearance of Gödel's pioneering work. During this time enormous progress has been made in mathematical logic and recursive function theory. Many different mathematical problems have been proved recursively unsolvable. Theoretically each such result is capable of producing an explicit undecidable number theoretic predicate. We have only to carry out a suitable arithmetization. Until recently, however, techniques were not available for carrying out these arithmetizations with sufficient efficiency.

In this article we construct an explicit undecidable arithmetical formula,F(x, n), in prenex normal form. The formula is explicit in the sense that it is written out in its entirety with no abbreviations. The formula is undecidable in the recursive sense that there exists no algorithm to decide, for given values ofn, whether or notF(n, n)is true or false. MoreoverF(n, n)is undecidable in the formal (axiomatic) sense of Gödel [7]. Given any of the usual axiomatic theories to which Gödel's Incompleteness Theorem applies, there exists a value ofnsuch thatF(n, n)is unprovable and irrefutable. Thus Gödel's Incompleteness Theorem can be “focused” into the formulaF(n, n). Thus some substitution instance ofF(n, n)is undecidable in Peano arithmetic, ZF set theory, etc.
The ω-consistency of number theory via Herbrand's theorem
Authors: Goldfarb W. D. , Scanlon T. M.
Published: May 2006

In this sequel to [7] the method of the consistency proof presented there is extended to provide a proof of the ω-consistency of the systems of number theory which were there shown consistent. This proof yields sharp bounds on the ordinal recursions required to establish the κ-consistency of these systems. The main technical innovation of this proof is the extension of what are essentially the methods of Ackermann [1] for handling finite sets of critical formulae of the first and second kinds to apply as well to sets of critical formulae in which the rank ordering is transfinite. The notation, definitions, and results of [7] will be presupposed throughout; we suggest the reader keep a copy of that paper at hand.
Generalized quantifiers and elementary extensions of countable models
Authors: Dubiel Małgorzata
Published: May 2006

Let L be a countable first-order language and L(Q) be obtained by adjoining an additional quantifier Q. Q is a generalization of the quantifier “there exists uncountably many x such that…” which was introduced by Mostowski in [4]. The logic of this latter quantifier was formalized by Keisler in [2]. Krivine and McAloon [3] considered quantifiers satisfying some but not all of Keisler's axioms. They called a formula φ(x) countable-like if

for every ψ. In Keisler's logic, φ(x) being countable-like is the same as ℳ⊨┐Qxφ(x). The main theorem of [3] states that any countable model ℳ of L[Q] has an elementary extension N, which preserves countable-like formulas but no others, such that the only sets definable in both N and M are those defined by formulas countable-like in M. Suppose C(x) in M is linearly ordered and noncountable-like but with countable-like proper segments. Then in N, C will have new elements greater than all “old” elements but no least new element — otherwise it will be definable in both models. The natural question is whether it is possible to use generalized quantifiers to extend models elementarily in such a way that a noncountable-like formula C will have a minimal new element. There are models and formulas for which it is not possible. For example let M be obtained from a minimal transitive model of ZFC by letting Qxφ(x) mean “there are arbitrarily large ordinals satisfying φ”.
Modal operators and functional completeness, II
Authors: Thomason S. K.
Published: May 2006

In the Kripke semantics for propositional modal logic, a frame W = (W, ≺) represents a set of “possible worlds” and a relation of “accessibility” between possible worlds. With respect to a fixed frame W, a proposition is represented by a subset of W (regarded as the set of worlds in which the proposition is true), and an n-ary connective (i.e. a way of forming a new proposition from an ordered n-tuple of given propositions) is represented by a function fw: (P(W))n → P(W). Finally a state of affairs (i.e. a consistent specification whether or not each proposition obtains) is represented by an ultrafilter over W. {To avoid possible confusion, the reader should forget that some people prefer the term “states of affairs” for our “possible worlds”.}

In a broader sense, an n-ary connective is represented by an n-ary operatorf = {fw∣ W ∈ Fr}, where Fr is the class of all frames and each fw: (P(W))n → P(W). A connective is modal if it corresponds to a formula of propositional modal logic. A connective C is coherent if whether C(P1,…, Pn) is true in a possible world depends only upon which modal combinations of P1,…,Pn are true in that world. (A modal combination of P1,…,Pn is the result of applying a modal connective to P1,…, Pn.) A connective C is strongly coherent if whether C(P1, …, Pn) obtains in a state of affairs depends only upon which modal combinations of P1,…, Pn obtain in that state of affairs.
The unprovability in intuitionistic formal systems of the continuity of effective operations on the reals
Authors: Beeson Michael
Published: May 2006

The question of continuity of functions defined on Baire space NN or on the reals has been of great interest to constructivists. We have little hope of answering the question without a fundamental philosophical analysis of the notion of constructive function. However, one can ask whether the continuity of functions can be derived in known intuitionistic formal systems, and answer these questions by mathematical means.

The constructivist does not generally wish to restrict himself to reals (or members of NN) given by a recursive law; therefore the most natural formal systems have variables for reals, sequences and functions. The axioms of these systems turn out to be compatible with the assumption that every real or sequence is given by a recursive law, and every function by an effective operation. An underivability result, therefore, is only strengthened if this assumption is taken as an axiom; and once this is done, we may as well work with (indices of) effective operations, within arithmetic.

By KLS is meant the assertion that each effective operation on Baire space NN is continuous. In [B1] it is shown that this statement cannot be proved in various intuitionistic formal systems. The continuity of functions on the reals has been of even greater interest to constructivists than the continuity of functions on NN; by KLS(R) is meant the assertion that each effective operation from the real numbers R to R is continuous. It is the purpose of the present note to show that KLS(R) is also underivable in intuitionistic formal systems.
Infinitary compactness without strong inaccessibility
Authors: Boos William
Published: May 2006

In this article, unpublished methods of Solovay and Kunen are applied to describe conditions under which an uncountable regular κ can satisfy weak (κ, λ)-compactness (see 1.1(3) below), yet lie below 2μ for some μ < κ. The argumentation is in informal ZFC, and general set-theoretic notation is standard. The lower-case Greek letters κ, λ, μ, ν are reserved for cardinals in the sense of some transitive or inner model of a reasonable set theory, φ, Ψ, θ, are (arithmetizations of) formulas in some extension of the first-order language of set theory, and other lower-case Greek letters except Є are metavariables for arbitrary ordinals. If M is transitive, M ⊨ φ abbreviates 〈M, Є 〉 ⊨ φ. [2], [3], [9] and [1] provide more information about large-cardinal theory for those who wish it.

1.1. Definitions. (1) κ is inaccessible iff κ is regular and ℵκ = κ; strongly inaccessible iff κ is regular and ℶκ = κ, i.e., λ < κ for all λ < κ; weakly inaccessible iff κ is inaccessible but not strongly inaccessible.

(2) Lκλ is the infinitary language with conjunctions and disjunctions of length < κ and quantification over sequences of length < λ, and PLκ the prepositional language with κ letters and conjunctions and disjunctions of length < κ.
Probabilities on finite models
Authors: Fagin Ronald
Published: May 2006

Let be a finite set of (nonlogical) predicate symbols. By an -structure, we mean a relational structure appropriate for . Let be the set of all -structures with universe {1, …, n}. For each first-order -sentence σ (with equality), let μn(σ) be the fraction of members of for which σ is true. We show that μn(σ) always converges to 0 or 1 as n → ∞, and that the rate of convergence is geometrically fast. In fact, if T is a certain complete, consistent set of first-order -sentences introduced by H. Gaifman [6], then we show that, for each first-order -sentence σ, μn(σ) →n 1 iff T ⊩ ω. A surprising corollary is that each finite subset of T has a finite model. Following H. Scholz [8], we define the spectrum of a sentence σ to be the set of cardinalities of finite models of σ. Another corollary is that for each first-order -sentence a, either σ or ˜σ has a cofinite spectrum (in fact, either σ or ˜σ is “nearly always“ true).

Let be a subset of which contains for each in exactly one structure isomorphic to . For each first-order -sentence σ, let νn(σ) be the fraction of members of which a is true. By making use of an asymptotic estimate [3] of the cardinality of and by our previously mentioned results, we show that vn(σ) converges as n → ∞, and that limn νn(σ) = limn μn(σ).If contains at least one predicate symbol which is not unary, then the rate of convergence is geometrically fast.
Applications of vaught sentences and the covering theorem
Authors: Harnik Victor , Makkai Michael
Published: May 2006

We use a fundamental theorem of Vaught, called the covering theorem in [V] (cf. theorem 0.1 below) as well as a generalization of it (cf. Theorem 0.1* below) to derive several known and a few new results related to the logic . Among others, we prove that if every countable model in a PCφ1ω class has only countably many automorphisms, then the class has either ≤ℵ0 or exactly nonisomorphic countable members (cf. Theorem 4.3*) and that the class of countable saturated structures of a sufficiently large countable similarity type is not among countable structures (cf. Theorem 5.2). We also give a simple proof of the Lachlan-Sacks theorem on bounds of Morley ranks (§7).
Boolean combinations of r.e. open sets
Authors: Hay Louise
Published: May 2006

In [2], [3], J. Grassin characterized those classes of sets which are expressible as a Boolean combination of open sets in the Baire topology on the power set of the natural numbers. From this characterization he deduced that if is a Boolean combination of recursive open sets, then the minimum length for any Boolean combination representing can be realized using recursive open sets.
A Boolean ultrapower which is not an ultrapower
Authors: Koppelberg Bernd , Koppelberg Sabine
Published: May 2006

Several people have independently been studying Boolean ultrapowers recently; see for example [2], [3], [4], [6]. Boolean ultrapowers are a quite natural generalization of the well-known usual ultrapowers, but it seemed to be unknown whether every Boolean ultrapower is isomorphic to an ultrapower. We give a negative answer to that question. We further show that a Boolean ultrapower by an ℵ1-regular ultrafilter need not be ℵ2-universal, i.e. that Theorem 4.3.12 of [1] does not hold for Boolean ultrapowers.

Let B be a complete Boolean algebra (we identify the algebra with its underlying set), whose operations are denoted by +, ·, −, 0, 1, Σ, Π Let be a structure for some language ℒ.
Minimal upper bounds for ascending sequences of α-recursively enumerable degrees
Authors: Chong C. T.
Published: May 2006

Let a be an admissible ordinal and let ∧ ≤ α be a limit ordinal. A sequence of a-r.e. degrees is said to be ascending, simultaneous and of length ∧ if (i) there is an α-recursive function t: α × ∧ → α such that, for all ϒ < ∧, Aϒ = {t(σ, ϒ)∣ σ < α} is of degree aϒ; (ii) if ϒ < ⊤ < ∧, then aϒ ≤αaτ and (iii) for all ϒ < ∧, there is a ⊤ > ϒ with aϒ, >αaϒ. Lerman [4] showed that such an exists for every ∧ ≤ α. An upper bound a of is an α-r.e. degree in which every element of is α-recursive. a is minimal if there is no α-r.e. degree b <αa which is also an upper bound of . Sacks [6] proved that every ascending sequence of simultaneously ω-r.e. degrees of length ω cannot have 0ω′, the complete ω-r.e. degree, as a minimal upper bound. In contrast, Cooper [2] showed that there exists an ascending sequence of simultaneously ω-r.e. degrees of length to having a minimal upper bound which is an ω-r.e. degree. In this paper we investigate the behavior of ascending sequences of simultaneously α-r.e. degrees for admissible ordinals α > ω. Call α Σ∞-admissibIe if it is Σn-nadmissible for all n. Let Φ(∧) say: No ascending sequence of simultaneously α-r.e. degrees of length ∧ can have 0α′, the complete α-r.e. degree, as a minimal upper bound. Our main result in this paper is:

Let α be either a constructible cardinal with σ2ci(α) < α or Σ∞-admissible. Then σ2cf(α) is the least ordinal ν for which every ∧ ≤ α of cofinality ν (over Lα) can satisfy Φ(∧).
On models with power-like orderings
Authors: Shelah Saharon
Published: May 2006

We prove here theorems of the form: if T has a model M in which P1(M) is κ1-like ordered, P2(M) is κ2-like ordered …, and Q1(M) is of power λ1, …, then T has a model N in which P1(M) is κ1′-like ordered …, Q1(N) is of power λ1′, …. (In this article κ is a strong-limit singular cardinal, and κ′ is a singular cardinal.)

We also sometimes add the condition that M, N omits some types. The results are seemingly the best possible, i.e. according to our knowledge about n-cardinal problems (or, more precisely, a certain variant of them).
A reduction theorem for predicate logic
Authors: Löb M. H.
Published: May 2006

It is well known that in prepositional logic not every propositional connective is definable in terms of equivalence nor indeed in terms of equivalence together with negation. It is the purpose of this note to show that in a certain sense this is, however, possible within predicate logic.

Let F1 be the class of predicate logical formulae containing only the logical connectives ¬ (not), ∨ (or), E (exists), and F2 the class of predicate logical formulae containing only the logical connectives ≡ (if and only if) and E.

Our object will be to find a method for reducing any formulae ϕ of F1 to a formula ψ of F2 such that ϕ is valid if and only if ψ is valid.

Note first that for every domain D containing at least two individuals we can for every n-place relation R defined over D find an n + 1-place relation S defined over D such that for all x1, …, xn ∈ D,

holds. For instance, let S(y, x1, …, xn) be the relation y = x1 & R(x1, …, xn).

Now let ϕ be an arbitrary formula of F1 and A1, …, A3 a complete list of predicate letters occurring in ϕ of degree g1, …, gi, respectively. Let ϕ′ be the formula obtained from ϕ by replacing every prime formula Ai(x1, …, xgi) by

Then it follows immediately from the previous observation that (a) ϕ is satisfiable in D if and only if ϕ′ is satisfiable in D.
Noninitial segments of the α-degrees
Authors: Macintyre John M.
Published: May 2006

Let α be an admissible ordinal and let L be the first order language with equality and a single binary relation ≤. The elementary theory of the α-degrees is the set of all sentences of L which are true in the universe of the α-degrees when ≤ is interpreted as the partial ordering of the α-degrees. Lachlan [6] showed that the elementary theory of the ω-degrees is nonaxiomatizable by proving that any countable distributive lattice with greatest and least members can be imbedded as an initial segment of the degrees of unsolvability. This paper deals with the extension of these results to α-recursion theory for an arbitrary countable admissible α > ω. Given α, we construct a set A with α-degree a such that every countable distributive lattice with greatest and least member is order isomorphic to a segment of α-degrees {d ∣ a ≤αd≤αb} for some α-degree b. As in [6] this implies that the elementary theory of the α-degrees is nonaxiomatizable and hence undecidable.

A is constructed in §2. A is a set of integers which is generic with respect to a suitable notion of forcing. Additional applications of such sets are summarized at the end of the section. In §3 we define the notion of a tree and construct a particular tree T0 which is weakly α-recursive in A. Using T0 we can apply the techniques of [6] and [2] to α-recursion theory. In §4 we reduce our main results to three technical lemmas concerning systems of trees. These lemmas are proved in §5.
Rowbottom cardinals and Jonsson cardinals are almost the same
Authors: Kleinberg E. M.
Published: May 2006

Each of the various “large cardinal” axioms currently studied in set theory owes its inspiration to concrete phenomena in various fields. For example, the statement of the well-known compactness theorem for first-order logic can be generalized in various ways to infinitary languages to yield definitions of compact cardinals, and the reflection principles provable in ZF, when modified in the appropriate way, yields indescribable cardinals.

In this paper we concern ourselves with two kinds of large cardinals which are probably the two best known of those whose origins lie in model theory. They are the Rowbottom cardinals and the Jonsson cardinals.

Let us be more specific. A cardinal κ is said to be a Jonsson cardinal if every structure of cardinality κ has a proper elementary substructure of cardinality κ. (It is routine to see that only uncountable cardinals can be Jonsson. Erdös and Hajnal have shown [2] that for n < ω no ℵn is Jonsson. (In fact, they showed that if κ is not Jonsson then neither is the successor cardinal of κ and that, assuming GCH, no successor cardinal can be Jonsson.) Keisler and Rowbottom first showed that the existence of a Jonsson cardinal contradicts V = L.) The definition of a Rowbottom cardinal is only slightly more intricate. We assume for the moment that our similarity type has a designated one-place relation.
Solution to the P − W problem
Authors: Martin E.P. , Meyer R.K.
Published: May 2006

Anderson and Belnap asked in §8.11 of their treatise Entailment [1] whether a certain pure implicational calculus, which we will call P − W, is minimal in the sense that no two distinct formulas coentail each other in this calculus. We provide a positive solution to this question, variously known as The P − W problem, or Belnap's conjecture.

We will be concerned with two systems of pure implication, formulated in a language constructed in the usual way from a set of propositional variables, with a single binary connective →. We use A, B,…, A1, B1, …, as variables ranging over formulas. Formulas are written using the bracketing conventions of Church [3].

The first system, which we call S (in honour of its evident incorporation of syllogistic principles of reasoning), has as axioms all instances of

(B) B → C →. A → B →. A → C (prefixing),

(B) A → B →. B → C →. A → C (suffixing),

and rules

(BX) from B → C infer A → B →. A → C (rule prefixing),

(B’X) from A → B infer B → C →. A → C (rule suffixing),

(BXY) from A → B and B → C infer A → C (rule transitivity).

The second system, P − W, has in addition to the axioms and rules of S the axiom scheme

(I) A → A

of identity.

We write ⊢SA (⊣SA) to mean that A is (resp. is not) a theorem of S, and similarly for P − W.
An introduction to forking
Authors: Lascar Daniel , Poizat Bruno
Published: May 2006

The notion of forking has been introduced by Shelah, and a full treatment of it will appear in his book on stability [S1]. The principal aim of this paper is to show that it is an easy and natural notion.

Consider some well-known examples of ℵ0-stable theories: vector spaces over Q, algebraically closed fields, differentially closed fields of characteristic 0; in each of these cases, we have a natural notion of independence: linear, algebraic and differential independence respectively. Forking gives a generalization of these notions. More precisely, if are subsets of some model and c a point of this model, the fact that the type of c over does not fork over means that there are no more relations of dependence between c and than there already existed between c and . In the case of the vector spaces, this means that c is in the space generated by only if it is already in the space generated by . In the case of differentially closed fields, this means that the minimal differential equations of c with coefficient respectively in and have the same order. Of course, these notions of dependence are essential for the study of the above mentioned structures. Forking is no less important for stable theories. A glance at Shelah's book will convince the reader that this is the case.

What we have to do is the following. Assuming T stable and given and p a type on , we want to distinguish among the extensions of p to some of
them that we shall call the nonforking extensions of p.
On the category of models of a complete theory
Authors: Lascar Daniel
Published: May 2006

Let T be a countable complete theory and C(T) the category whose objects are the models of T and morphisms are the elementary maps. The main object of this paper will be the study of C(T). The idea that a better understanding of the category may give us model theoretic information about T is quite natural: The (semi) group of automorphisms (endomorphisms) of a given structure is often a powerful tool for studying this structure. But certainly, one of the very first questions to be answered is: “to what extent does this category C(T) determine T?”

There is some obvious limitation: for example let T0 be the theory of infinite sets (in a language containing only =) and T1 the theory, in the language ( =, U(ν0),f(ν0)) stating that:

(1) U is infinite.

(2)f is a bijective map from U onto its complement.

It is quite easy to see that C(T0) is equivalent to C(T1). But, in this case, T0 and T1 can be “interpreted” each in the other. To make this notion of interpretation precise, we shall associate with each theory T a category, loosely denoted by T, defined as follows:

(1) The objects are the formulas in the given language.

(2) The morphisms from into are the formulas such that

(i.e. f defines a map from ϕ into ϕ; two morphisms defining the same map in all models of T should be identified).
Substance and first-order quantification over individual-concepts
Authors: Bacon John
Published: May 2006

An individual-concept, hereinafter “individuation”, is a function from possible worlds to individuals. Constant individuations I will call “subsistents” (the notion will presently be generalized). A “substance”, after Thomason [35], is a subsistent whose value exists for the world at hand. In the systems of quantified modal logic developed over the past twenty years, the tendency has been to restrict the range of quantifiers to substances (often represented technically by the simple individuals that would be the values of the constant individuations), while allowing constant terms (particularly descriptions) to express arbitrary individuations. One result is to invalidate unrestricted universal instantiation (and existential generalization), rather as in free logic. Such systems approximate some features of ordinary usage rather nicely, e.g. the behavior of quantifiers and definite descriptions in tensed discourse. Stalnaker and Thomason's Q3r [34], based on the latter's Q3 [35], [36], is exemplary of this approach.

The suggestion has repeatedly been considered to quantify over individuations in general (Kanger [14], Kaplan [17], Hughes and Cresswell [12, p. 196], Thomason [35, p. 136], Pollock [30]).
Constructible models of subsystems of ZF
Authors: Gostanian Richard
Published: May 2006

One of the main results of Gödel [4] and [5] is that, if M is a transitive set such that 〈M, Є 〉 is a model of ZF (Zermelo-Fraenkel set theory) and α is the least ordinal not in M, then 〈Lα, Є 〉 is also a model of ZF.

In this note we shall use the Jensen uniformisation theorem to show that results analogous to the above hold for certain subsystems of ZF. The subsystems we have in mind are those that are formed by restricting the formulas in the separation and replacement axioms to various levels of the Levy hierarchy.

This is all done in §1. In §2 we proceed to establish the exact order relationships which hold among the ordinals of the minimal models of some of the systems discussed in §1. Although the proofs of these latter results will not require any use of the uniformisation theorem, we will find it convenient to use some of the more elementary results and techniques from Jensen's fine-structural theory of L. We thus provide a brief review of the pertinent parts of Jensen's works in §0, where a list of general preliminaries is also furnished.

We remark that some of the techniques which we use in the present paper have been used by us previously in [6] to prove various results about β-models of analysis. Since β-models for analysis are analogous to transitive models for set theory, this is not surprising.
On the ordering of certain large cardinals
Authors: Morgenstern Carl F.
Published: May 2006

It is well known that the first strongly inaccessible cardinal is strictly less than the first weakly compact cardinal which in turn is strictly less than the first Ramsey cardinal, etc. However, once one passes the first measurable cardinal the inequalities are no longer strict. Magidor [3] has shown that the first strongly compact cardinal may be equal to the first measurable cardinal or equal to the first super-compact cardinal (the first supercompact cardinal is strictly larger than the first measurable cardinal). In this note we will indicate how Magidor's methods can be used to show that it is undecidable whether one cardinal (the first strongly compact) is greater than or less than another large cardinal (the first huge cardinal). We assume that the reader is familiar with the ultrapower construction of Scott, as presented in Drake [1] or Kanamori, Reinhardt and Solovay [2].

Definition. A cardinal κ is huge (or 1-huge) if there is an elementary embedding j of the universe V into a transitive class M such that M contains the ordinals, is closed under j(κ) sequences, j(κ) > κ and j ↾ Rκ = id. Let κ denote the first huge cardinal, and let λ = j(κ).

One can see from easy reflection arguments that κ and λ are inaccessible in V and, in fact, that κ is measurable in V.
On homogeneity and definability in the first-order theory of the Turing degrees
Authors: Shore Richard A.
Published: May 2006

Relativization—the principle that says one can carry over proofs and theorems about partial recursive functions and Turing degrees to functions partial recursive in any given set A and the Turing degrees of sets in which A is recursive—is a pervasive phenomenon in recursion theory. It led H. Rogers, Jr. [15] to ask if, for every degree d, (≥ d), the partial ordering of Turing degrees above d, is isomorphic to all the degrees . We showed in Shore [17] that this homogeneity conjecture is false. More specifically we proved that if, for some n, the degree of Kleene's (the complete set) is recursive in d(n) then ≇ (≤ d). The key ingredient of the proof was a new version of a result from Nerode and Shore [13] (hereafter NS I) that any isomorphism φ: → (≥ d) must be the identity on some cone, i.e., there is an a called the base of the cone such that b ≥ a ⇒ φ(b) = b. This result was combined with information about minimal covers from Jockusch and Soare [8] and Harrington and Kechris [3] to derive a contradiction from the existence of such an isomorphism if deg() ≤ d(n).
An introduction to ω-extensions of ω-groups
Authors: Applebaum C. H.
Published: May 2006

Let ε stand for the set of nonnegative integers (numbers), V for the class of all subcollections of ε(sets), Λ for the set of isols, ΛR for the set of regressive isols, and for the set of mappings from a subset of ε into ε (functions). If ƒ is a function we write δƒ and ρƒ for its domain and range, respectively. We denote the inclusion relation by ⊃ and proper inclusion by ⊊. The sets α and β are recursively equivalent [written: α ≃ β], if δƒ = α and ρƒ = β for some function ƒ with a one-to-one partial recursive extension. We denote the recursive equivalence type of a set α, {σ ∈ V ∣ σ ≃ α} by Req(α). The reader is assumed to be familiar with the contents of [1], [2], [3], and [6].

The concept of an ω-group was introduced in [6], and that of an ω-homomorphism in [1]. However, except for a few examples, very little is known about the structure of ω-groups. If G is an ω-group and Π is an ω-homomorphism, then it follows that K = Ker Π and H = Π(G) are ω-groups. The question arises that if we know the structure of K and H, then what can we say about the structure of G? In this paper we will begin the study of ω-extensions, which will give us a partial answer to this question.