bluuebunny/crossref_metadata_2025 huggingface dataset:
Structures elementarily closed relative to a model for arithmetic
Authors: Madison Eugene W.
Published: May 2006

The present paper is a sequel to [1]. It is our purpose to formulate a general theory derived from the methods used to obtain three results for the field of real algebraic numbers in [1]. As there, we shall concern ourselves almost exclusively with fields of characteristic zero; thus we assume a convenient formulation of first order logic with extralogical constants E(x, y), S(x, y, z), F(x, y, z), F(x, y), N(x) and 0, whose intended interpretations are equality, sum, product, y is the successor of x, x ∈ (where is a substructure satisfying all first order truths of the natural numbers) and zero, respectively. In addition, we shall use Q(x, y) for x ≤ y in those cases where our field is ordered, e.g. the field of real algebraic numbers.
An infinitistic rule of proof
Authors: Enderton H. B.
Published: May 2006

In this paper we consider a fonnal system of second-order Peano arithmetic with a rule of inference stronger than the ω-rule [3]. We also consider the relation to a class of models for analysis (i.e. second-order arithmetic) which lies between the class of ω-models and the class of β-models [5].

The notation used is largely that of [3] and [5]. We assume that the reader has some familiarity with at least the ideas of the former. The formal system (A) of Peano arithmetic employed in [3] includes the comprehension axioms and the second-order induction axiom.
A logic stronger than intuitionism
Authors: Görnemann Sabine
Published: May 2006

S. A. Kripke has given [6] a very simple notion of model for intuitionistic predicate logic. Kripke's models consist of a quasi-ordering (C, ≤) and a function ψ which assigns to every c ∈ C a model of classical logic such that, if c ≤ c′, ψ(c′) is greater or equal to ψ(c). Grzegorczyk [3] described a class of models which is still simpler: he takes, for every ψ(c), the same universe. Grzegorczyk's semantics is not adequate for intuitionistic logic, since the formula

where х is not free in α. holds in his models but is not intuitionistically provable. It is a conjecture of D. Klemke that intuitionistic predicate calculus, strengthened by the axiom scheme (D), is correct and complete with respect to Grzegorczyk's semantics. This has been proved independently by D. Klemke [5] by a Henkinlike method and me; another proof has been given by D. Gabbay [1]. Our proof uses lattice-theoretical methods.
Transfinite induction and bar induction of types zero and one, and the role of continuity in intuitionistic analysis
Authors: Howard W. A. , Kreisel G.
Published: May 2006

The following is a self-contained proof theoretic treatment of two of the principal axiom schemata of current intuitionistic analysis: the axiom of bar induction (Brouwer's bar theorem) and the axiom of continuity. The results are formulated in terms of formal derivability in elementary intuitionistic analysis H(§ 1), so the positive (i.e., derivability) results also apply to elementary classical analysis Z1 (Appendix 1). Both schemata contain the combination of quantifiers νfΛn, where f, g, … are intended to range over free choice sequences of suitable kinds of objects x, y, …; for example, natural numbers or sequences of natural numbers, and n, m, p, r, … over natural numbers (non-negative integers).
Transcendence of cardinals
Authors: Takeuti Gaisi
Published: May 2006

In this paper, by a function of ordinals we understand a function which is defined for all ordinals and each of whose value is an ordinal. In [7] (also cf. [8] or [9]) we defined recursive functions and predicates of ordinals, following Kleene's definition on natural numbers. A predicate will be called arithmetical, if it is obtained from a recursive predicate by prefixing a sequence of alternating quantifiers. A function will be called arithmetical, if its representing predicate is arithmetical.

The cardinals are identified with those ordinals a which have larger power than all smaller ordinals than a. For any given ordinal a, we denote by the cardinal of a and by 2a the cardinal which is of the same power as the power set of a. Let χ be the function such that χ(a) is the least cardinal which is greater than a.

Now there are functions of ordinals such that they are easily defined in set theory, but it seems impossible to define them as arithmetical ones; χ is such a function. If we define χ in making use of only the language on ordinals, it seems necessary to use the notion of all the functions from ordinals, e.g., as in [6].
On the indexing of classes of recursively enumerable sets
Authors: Lachlan A. H.
Published: May 2006

In this paper we follow up our work in [2] on standard classes of recursively enumerable sets, and it will be supposed that the reader is familiar with [2]. One of the main problems left open in [2], that of determining whether or not every standard class has a least member is resolved by the construction of a standard class all of whose members are non-empty, and two of whose members are disjoint. This shows that there is a standard class which is not p.r. in the sense of [2] and we now prefer the adjective sequential for those standard classes which were called p.r. in [2]. Otherwise our terminology will be the same as in [2]. We shall also prove the theorem only stated in [2] that any standard class all of whose members have cardinality < 3 is sequential. Further, we give an example of a standard class which is not sequential and all of whose members have cardinality < 4.
The decidability of the Kreisel-Putnam system
Authors: Gabbay Dov M.
Published: May 2006

The intuitionistic propositional logic I has the following disjunction property

This property does not characterize intuitionistic logic. For example Kreisel and Putnam [5] showed that the extension of I with the axiom

has the disjunction property. Another known system with this propery is due to Scott [5], and is obtained by adding to I the following axiom:

In the present paper we shall prove, using methods originally introduced by Segerberg [10], that the Kreisel-Putnam logic is decidable. In fact we shall show that it has the finite model property, and since it is finitely axiomatizable, it is decidable by [4]. The decidability of Scott's system was proved by J. G. Anderson in his thesis in 1966.
Logic with truth values in A linearly ordered heyting algebra
Authors: Horn Alfred
Published: May 2006

It is known that the theorems of the intuitionist predicate calculus are exactly those formulas which are valid in every Heyting algebra (that is, pseudo-Boolean algebra). The simplest kind of Heyting algebra is a linearly ordered set. This paper concerns the question of determining all formulas which are valid in every linearly ordered Heyting algebra. The question is of interest because it is a particularly simple case intermediate between the intuitionist and classical logics. Also the interpretation of implication is such that in general there exists no nondiscrete Hausdorff topology for which this operation is continuous.
Applications of Strict Π11 predicates to infinitary logic
Authors: Barwise Jon
Published: May 2006

Consider the predicate of natural numbers defined by:

where R is recursive. If, as usual, the variable ƒ ranges over ωω (the set of functions from natural numbers to natural numbers) then this is just the usual normal form for Π11 sets. If, however, ƒ ranges over 2ω (the set of functions from ω into {0, 1}) then every such predicate is recursively enumerable.3 Thus the second type of formula is generally ignored. However, the reduction just mentioned requires proof, and the proof uses some form of the Brower-König Infinity Lemma.
Recursive equivalence types and groups
Authors: Hassett Matthew J.
Published: May 2006

Let ε and Λ denote the sets of all nonnegative integers and isols respectively. Let σ be any subset of ε. Following [6], we shall denote the recursive equivalence type of a by Req(σ) and write σ≃τ when Req(σ) = Req(τ).
A problem in the theory of constructive order types
Authors: Gandy Robin O. , Soare Robert I.
Published: May 2006

J. N. Crossley [1] raised the question of whether the implication 2 + A = A ⇒ 1 + A = A is true for constructive order types (C.O.T.'s). Using an earlier definition of constructive order type, A. G. Hamilton [2] presented a counterexample. Hamilton left open the general question, however, since he pointed out that Crossley considers only orderings which can be embedded in a standard dense r.e. ordering by a partial recursive function, and that his counterexample fails to meet this requirement. We resolve the question by finding a C.O.T. A which meets Crossley's requirement and such that 2 + A = A but 1 + A ≠ A. At the suggestion of A. B. Manaster and A. G. Hamilton we easily extend this construction to show that for any n ≧ 2, there is a C.O.T. A such that n + A = A but m + A ≠ A for 0 < m < n. Hence, Theorem 3 of [2] and all of its corollaries hold with the new definition of C.O.T. The construction is not difficult and requires no priority argument. The techniques are similar to those developed in [3], but no outside results are needed here.
Addendum to early history of the Association for Symbolic Logic
Authors: Ducasse C. J. , Curry Haskell B.
Published: May 2006

Since publication of our account of the early history of the Association for Symbolic Logic in the September 1962 issue of its Journal, the fact has been called to our attention that — because much of the correspondence at that time is no longer available and we had therefore to depend on our memory — we failed to mention an important item of that early history.

This was a letter from Professor Paul Weiss to the Editor of Philosophy of Science, which appeared in the April, 1934, issue of that periodical. This letter, entitled “A Home for Logic,” called attention to the fact that papers on logic were scattered in heterogeneous periodicals, and suggested that the Philosophy of Science Association take under its wing the establishment of a Logical Association.
Recursive real numbers
Authors: Lachlan A. H.
Published: May 2006

The present work was inspired by Mostowski's paper [3] in which he considers classes of sequences of real numbers, and associated sets of primitive recursive real numbers. The present treatment will differ from that of [3] in that we consider the real numbers in (0, ∞), instead of just those in (0, 1), but this will make little difference. In §1 we develop a general theory, and in §2 we show the relation of this theory to the results contained in [3], and to those of other authors.
The next admissible set
Authors: Barwise K. J. , Gandy R. O. , Moschovakis Y. N.
Published: May 2006

In this paper we describe generalizations of several approaches to the hyperarithmetic hierarchy, show how they are related to the Kripke-Platek theory of admissible ordinals and sets, and study conditions under which the various approaches remain equivalent.

To put matters in some perspective, let us first review various approaches to the theory of hyperarithmetic sets. For most purposes, it is convenient to first define the semi-hyperarithmetic (semi-HA) subsets of N. A set is then said to be hyperarithmetic (HA) if both it and its complement are semi-HA. A total number-theoretic function is HA if its graph is HA.
A logical analysis of some value concepts
Authors: Fitch Frederic B.
Published: May 2006

The purpose of this paper is to provide a partial logical analysis of a few concepts that may be classified as value concepts or as concepts that are closely related to value concepts. Among the concepts that will be considered are striving for, doing, believing, knowing, desiring, ability to do, obligation to do, and value for. Familiarity will be assumed with the concepts of logical necessity, logical possibility, and strict implication as formalized in standard systems of modal logic (such as S4), and with the concepts of obligation and permission as formalized in systems of deontic logic. It will also be assumed that quantifiers over propositions have been included in extensions of these systems.
Minimal α-recursion theoretic degrees
Authors: MacIntyre John M.
Published: May 2006

This paper investigates the problem of extending the recursion theoretic construction of a minimal degree to the Kripke [2]-Platek [5] recursion theory on the ordinals less than an admissible ordinal α, a theory derived from the Takeuti [11] notion of a recursive function on the ordinal numbers. As noted in Sacks [7] when one generalizes the recursion theoretic definition of relative recursiveness to α-recursion theory for α > ω the two usual definitions give rise to two different notions of reducibility. We will show that whenever α is either a countable admissible or a regular cardinal of the constructible universe there is a subset of α whose degree is minimal for both notions of reducibility. The result is an excellent example of a theorem of ordinary recursion theory obtainable via two different constructions, one of which generalizes, the other of which does not. The construction which cannot be lifted to α-recursion theory is that of Spector [10]. We sketch the reasons for this in §3.
Consistency notions in illative combinatory logic
Authors: Bunder M. W.
Published: May 2006

In this paper we show that certain notions of consistency currently in use in illative combinatory logic are not always necessary nor always sufficient for the acceptability of the system.

The three notions of consistency we will consider are:

(A) Not all terms of the system are assertible.

(B) Not all propositions of the system are assertible.

(C) The system is Q-consistent, i.e. if Q (for equality) is in or is added to the system as a primitive with axioms such as

Post defined a system of propositional calculus to be inconsistent if all propositions were assertible. In a more general system where there may be terms which are not propositions (although all propositions are terms), we need to distinguish notions (A) and (B) as two possible consistency notions “in the sense of Post”.

In [3] Curry and Feys assume that Q is in the system defined as λxλy.Ξ(C*x)(C*y) or as a primitive, but Seldin in [5] also talks about Q-consistency of a system (F22) to which Q has to be added. We therefore consider the definition of Q-consistency that includes all three possibilities.

In [3] Curry and Feys state that Q-consistency is essential for acceptability. This is because there the purpose was to have an assertional system of illative combinatory logic in which combinatory equality was represented by the assertion of QXY. However if Q is to represent some other form of equality, Q-consistency may become inessential for acceptability or even incompatible with it.
Computational complexity, speedable and levelable sets
Authors: Soare Robert I.
Published: May 2006

One of the most interesting aspects of the theory of computational complexity is the speed-up phenomenon such as the theorem of Blum [6, p. 326] which asserts the existence of a 0, 1-valued total recursive function with arbitrarily large speed-up. Blum and Marques [10] extended the speed-up definitions from total to partial recursive functions, or equivalently, to recursively enumerable (r.e.) sets, and introduced speedable and levelable sets. They classified the effectively speedable sets as the subcreative sets but remarked that “the characterizations we provided for speedable and levelable sets do not seem to bear a close relationship to any already well-studied class of recursively enumerable sets.” The purpose of this paper is to give an “information theoretic” characterization of speedable and levelable sets in terms of index sets resembling the jump operator. From these characterizations we derive numerous consequences about the degrees and structure of speedable and levelable sets.
An intuitionistically plausible interpretation of intuitionistic logic
Authors: de Swart H. C. M.
Published: May 2006

Let IPC be the intuitionistic first-order predicate calculus. From the definition of derivability in IPC the following is clear:

(1) If A is derivable in IPC, denoted by “⊦IPCA”, then A is intuitively true, that means, true according to the intuitionistic interpretation of the logical symbols. To be able to settle the converse question: “if A is intuitively true, then ⊦IPCA”, one should make the notion of intuitionistic truth more easily amenable to mathematical treatment. So we have to look then for a definition of “A is valid”, denoted by “⊨A”, such that the following holds:

(2) If A is intuitively true, then ⊨ A.

Then one might hope to be able to prove

(3) If ⊨ A, then ⊦IPCA.

If one would succeed in finding a notion of “⊨ A”, such that all the conditions (1), (2) and (3) are satisfied, then the chain would be closed, i.e. all the arrows in the scheme below would hold.

Several suggestions for ⊨ A have been made in the past: Topological and algebraic interpretations, see Rasiowa and Sikorski [1]; the intuitionistic models of Beth, see [2] and [3]; the interpretation of Grzegorczyk, see [4] and [5]; the models of Kripke, see [6] and [7]. In Thirty years of foundational studies, A. Mostowski [8] gives a review of the interpretations, proposed for intuitionistic logic, on pp. 90–98.
Provable wellorderings of formal theories for transfinitely iterated inductive definitions
Authors: Buchholz W. , Pohlers W.
Published: May 2006

By [12] we know that transfinite induction up to ΘεΩN+10 is not provable in IDN, the theory of N-times iterated inductive definitions. In this paper we will show that conversely transfinite induction up to any ordinal less than ΘεΩN+10 is provable in IDNi, the intuitionistic version of IDN, and extend this result to theories for transfinitely iterated inductive definitions.

In [14] Schütte proves the wellordering of his notational systems using predicates is wellordered) with Mκ ≔ {x ∈ and 0 ≤ κ ≤ N. Obviously the predicates are definable in IDNi with the defining axioms:

where Prog [Mκ, X] means that X is progressive with respect to Mκ, i.e.

The crucial point in Schütte's wellordering proof is Lemma 19 [14, p. 130] which can be modified to

where TI[Mκ + 1, a] is the scheme of transfinite induction over Mκ + 1 up to a.
On complexity properties of recursively enumerable sets
Authors: Blum M. , Marques I.
Published: May 2006

An important goal of complexity theory, as we see it, is to characterize those partial recursive functions and recursively enumerable sets having some given complexity properties, and to do so in terms which do not involve the notion of complexity.

As a contribution to this goal, we provide characterizations of the effectively speedable, speedable and levelable [2] sets in purely recursive theoretic terms. We introduce the notion of subcreativeness and show that every program for computing a partial recursive function f can be effectively speeded up on infinitely many integers if and only if the graph of f is subcreative.

In addition, in order to cast some light on the concepts of effectively speedable, speedable and levelable sets we show that all maximal sets are levelable (and hence speedable) but not effectively speedable and we exhibit a set which is not levelable in a very strong sense but yet is effectively speedable.
On definable subsets of p-adic fields
Authors: MacIntyre Angus
Published: May 2006

The brilliant work of Ax-Kochen [1], [2], [3] and Ersov [6], and later work by Kochen [7] have made clear very striking resemblances between real closed fields and p-adically closed fields, from the model-theoretical point of view. Cohen [5], from a standpoint less model-theoretic, also contributed much to this analogy.

In this paper we shall point out a feature of all the above treatments which obscures one important resemblance between real and p-adic fields. We shall outline a new treatment of the p-adic case (not far removed from the classical treatments cited above), and establish an new analogy between real closed and p-adically closed fields.

We want to describe the definable subsets of p-adically closed fields. Tarski [9] in his pioneering work described the first-order definable subsets of real closed fields. Namely, if K is a real-closed field and X is a subset of K first-order definable on K using parameters from K then X is a finite union of nonoverlapping intervals (open, closed, half-open, empty or all of K). In particular, if X is infinite, X has nonempty interior.

Now, there is an analogous question for p-adically closed fields. If K is p-adically closed, what are the definable subsets of K? To the best of our knowledge, this question has not been answered until now.

What is the difference between the two cases? Tarski's analysis rests on elimination of quantifiers for real closed fields. Elimination of quantifiers for p-adically closed fields has been achieved [3], but only when we take a cross-section π as part of our basic data. The problem is that in the presence of π it becomes very difficult to figure out what sort of set is definable by a quantifier free formula. We shall see later that use of the cross-section increases the class of definable sets.
Definability of measures and ultrafilters
Authors: Pincus David , Solovay Robert M.
Published: May 2006

Nonprincipal ultrafilters are harder to define in ZFC, and harder to obtain in ZF + DC, than nonprincipal measures.

The function μ from P(X) to the closed interval [0, 1] is a measure on X if μ. is finitely additive on disjoint sets and μ(X) = 1. (P is the power set.) μ is nonprincipal if μ ({x}) = 0 for each x Є X. μ is an ultrafilter if Range μ= {0, 1}. The existence of nonprincipal measures and ultrafilters on any infinite X follows from the axiom of choice.

Nonprincipal measures cannot necessarily be defined in ZFC. (ZF is Zermelo–Fraenkel set theory. ZFC is ZF with choice.) In ZF alone they cannot even be proved to exist. This was first established by Solovay [14] using an inaccessible cardinal. In the model of [14] no nonprincipal measure on ω is even ODR (definable from ordinal and real parameters). The HODR (hereditarily ODR) sets of this model form a model of ZF + DC (dependent choice) in which no nonprincipal measure on ω exists. Pincus [8] gave a model with the same properties making no use of an inaccessible. (This model was also known to Solovay.) The second model can be combined with ideas of A. Blass [1] to give a model of ZF + DC in which no nonprincipal measures exist on any set. Using this model one obtains a model of ZFC in which no nonprincipal measure on the set of real numbers is ODR. H. Friedman, in private communication, previously obtained such a model of ZFC by a different method. Our construction will be sketched in 4.1.
Definability in well quasi-ordered sets of structures
Authors: Landraitis Charles K.
Published: May 2006

The theorem introduced here provides a sufficient condition for an axiomatic class to be elementary. It resulted from consideration of a definability problem in , but is introduced in a less specific context and accompanied by applications to .

As in [La, 1], [La, 2], a reflexive, transitive binary relation R on a nonempty set S will be called a quasi-ordering or q.o. of S. A set of pairwise incomparable elements of S is an antichain and a subset of S linearly ordered by R is a chain. A chain {Si: i ∈ ω} with i > j if and only if (siRsj ∧ ¬ sjRSi) will be called an infinite descending chain. If S has no infinite antichains nor any infinite descending chains, S is well quasi-ordered by R, and is called a well quasi-ordering or w.q.o. Any subset of a w.q.o. is a w.q.o. An element s of a q.o. S is minimal in S if ∀t ∈ S(tRs → sRt). A subset S′ of S is a foundation for S if ∀t ∈ S∃s ∈ S′(sRt).
Uniform enumeration operations
Authors: Lachlan A. H.
Published: May 2006

Sacks [2] has asked whether there exists a uniform solution to Post's problem, i.e. an enumeration operation W such that d < W(d) < d′ for every degree d. It is shown here that if such an operation W exists it cannot itself in a particular technical sense be uniform. In fact, the jump operation is characterized amongst such uniform enumeration operations by the condition: d < W(d) for all d. In addition, it is proved that the only other uniform enumeration operations such that d ≤ W(d) for all d are those which equal the identity operation above some fixed degree.
A completeness theorem for Zermelo-Fraenkel set theory
Authors: Powell William C.
Published: May 2006

We provide a semantics for Zermelo-Fraenkel set theory. The semantics was essentially given by W. Ackermann [1], and the proof of completeness follows from a lemma of Levy [4]. Furthermore, a close relationship between Ackermann's set theory and Zermelo-Fraenkel set theory has been established by Levy [4] and Reinhardt [6]. Thus, any interest in this paper must consist solely in the explicit formulation of the completeness result and the consequential evidence of the fundamental character of Ackermann's principle and the ad hoc character of the full law of excluded middle and the strong transitivity of Ackermann's unary relation
Krom formulas with one dyadic predicate letter
Authors: Lewis Harry R.
Published: May 2006

Let Kr be the class of all those quantificational formulas whose matrices are conjunctions of binary disjunctions of signed atomic formulas. Decision problems for subclasses of Kr do not invariably coincide with those for the corresponding classes of quantificational formulas with unrestricted matrices; for example, the ∀∃∀ prefix subclass of Kr is solvable, but the full ∀∃∀ class is not ([AaLe],- [KMW]). Moreover, the straightforward encodings of automata which have been used to show the unsolvability of various subclasses of Kr ([Aa], [Bö], [AaLe]) yield but little information about signature subclasses, i.e. subclasses determined by the number and degrees of the predicate letters occurring in a formula. By a new and highly complex construction Theorem 1 establishes the best possible result on classification by signature.

Theorem 1. Let C be the class of all formulas in Kr with a single predicate letter, which is dyadic; then C is a reduction class for satisfiability.

Thus a signature subclass of Kr is solvable just in case the corresponding class of unrestricted quantificational formulas is solvable, to wit, just in case no predicate letter of degree exceeding one may occur. To obtain a richer classification by signature we consider further restrictions on the matrix. Let Or be the class of formulas in Kr having disjunctive normal forms with only two disjuncts. Theorem 2 sharpens Orevkov's proof of the unsolvability of Or ([Or]; see also [LeGo]).

Theorem 2. Let D be the class of formulas in Or with just two predicate letters, both pentadic; then D is a reduction class for satisfiability.
Congruence relations, filters, ideals, and definability in lattices of α-recursively enumerable sets
Authors: Lerman Manuel
Published: May 2006

Throughout this paper, α will denote an admissible ordinal. Let (α) denote the lattice of α-r.e. sets, i.e., the lattice whose elements are the α-r.e. sets, and whose ordering is given by set inclusion. Call a set A ∈ (α)α*-finite if it is α-finite and has ordertype < α* (the Σ1-projectum of α). The α*-finite sets form an ideal of (α), and factoring (α) by this ideal, we obtain the quotient lattice *(α).

We will fix a language ℒ suitable for lattice theory, and discuss decidability in terms of this language. Two approaches have succeeded in making some progress towards determining the decidability of the elementary theory of (α). Each approach was first used by Lachlan for α = ω. The first approach is to relate the decidability of the elementary theory of (α) to that of a suitable quotient lattice of (α) by a congruence relation definable in ℒ. This technique was used by Lachlan [4, §1] to obtain the equidecidability of the elementary theories of (ω) and *(ω), and was generalized by us [6, Corollary 1.2] to yield the equidecidability of the elementary theories of (α) and *(α) for all α. Lachlan [3] then adopted a different approach.
The decision problem for standard classes
Authors: Gurevich Yuri
Published: May 2006

The standard classes of a first-order theory T are certain classes of prenex T-sentences defined by restrictions on prefix, number of monadic, dyadic, etc. predicate variables, and number of monadic, dyadic, etc. operation variables. In [3] it is shown that, for any theory T, (1) the decision problem for any class of prenex T-sentences specified by such restrictions reduces to that for the standard classes, and (2) there are finitely many standard classes K1, …, Kn such that any undecidable standard class contains one of K1, …, Kn. These results give direction to the study of the decision problem.

Below T is predicate logic with identity and operation variables. The Main Theorem solves the decision problem for the standard classes admitting at least one operation variable.
An introduction to recursively saturated and resplendent models
Authors: Barwise Jon , Schlipf John
Published: May 2006

The notions of recursively saturated and resplendent models grew out of the study of admissible sets with urelements and admissible fragments of Lω1ω, but, when applied to ordinary first order model theory, give us new tools for research and exposition. We will discuss their history in §3.

The notion of saturated model has proven to be important in model theory. Its most important property for applications is that if , are saturated and of the same cardinality then = iff ≅ . See, e.g., Chang-Keisler [3]. The main drawback is that saturated models exist only under unusual assumptions of set theory. For example, if 2κ = κ+ then every theory T of L has a saturated model of power κ+. (Similarly, if κ is strongly inaccessible, then every T has a saturated model of power κ.) On the other hand, a theory T like Peano arithmetic, with types, cannot have a saturated model in any power κ with ω ≤ κ ≤ .

One method for circumventing these problems of existence (or rather non-existence) is the use of “special” models (cf. [3]). If κ = Σλ<κ2λ, κ < ω, then every theory T of L has a special model of power κ. Such cardinals are large and, themselves, rather special. There are definite aesthetic objections to the use of these large, singular models to prove results about first order logic.
A complete Lω1ω-sentence characterizing ℵ1
Authors: Knight Julia F.
Published: May 2006

Here an example will be given of a complete Lω1ω-sentence with a model of power ℵ1 but with no model of higher power. The continuum hypothesis is not assumed. The question of whether such an example exists was brought to the author's attention by Professor M. Makkai.

An Lω1ω-sentence is said to be complete if its models all satisfy the same Lω1ω-sentences, or, equivalently, if all of the countable L-structures satisfying the sentence are isomorphic. Scott [5] showed that any countable L -structure (where L is countable) must satisfy a complete Lω1ω-sentence. Such a sentence is called a Scott sentence for the structure. An uncountable L-structure need not satisfy any complete Lω1ω -sentence.

A complete Lω1ω-sentence σ is said to characterize the infinite cardinal k if σ has a model of power k but not of any higher power. The set of cardinals characterized by complete Lω1ω -sentences will be denoted by CC. By a result of Lopez-Escobar [3], if k ∈ CC, k <⊐ω1.

Assuming GCH (so that ⊐α = ℵα, ), Malitz [4] showed that CC = {ℵα: α < ω1}.

Without assuming GCH, Baumgartner [1] showed that ⊐α ∈ CC for all α < ω1.

Without GCH, it is unknown whether ℵn ∈ CC for n ≥ 2. Now it will be shown that ℵ1, ∈ CC.
Σ1-compactness and ultraproducts
Authors: Cutland Nigel
Published: May 2006

This paper is devoted to a description of the way in which ultraproducts can be used in proofs of various well-known Σ1-compactness theorems for infinitary languages ℒA associated with admissible sets A; the method generalises the ultra-product proof of compactness for finitary languages.

The compactness theorems we consider are (§2) the Barwise Compactness Theorem for ℒA when A is countable admissible [1], and (§3) the Cofinality (ω) Compactness Theorem of Barwise and Karp [2] and [4]. Our proof of the Barwise theorem unfortunately has the defect that it relies heavily on the Completeness Theorem for ℒA. This defect has, however, been avoided in the case of the Cf(ω) Compactness Theorem, so we have a purely model-theoretic proof.
Omitting types: application to recursion theory
Authors: Grilliot Thomas J.
Published: May 2006

Omitting-types theorems have been useful in model theory to construct models with special characteristics. For instance, one method of proving the ω-completeness theorem of Henkin [10] and Orey [20] involves constructing a model that omits the type {x ≠ 0, x ≠ 1, x ≠ 2,···} (i.e., {x ≠ 0, x ≠ 1, x ≠ 2,···} is not satisfiable in the model). Our purpose in this paper is to illustrate uses of omitting-types theorems in recursion theory. The Gandy-Kreisel-Tait Theorem [7] is the most well-known example. This theorem characterizes the class of hyperarithmetical sets as the intersection of all ω-models of analysis (the so-called hard core of analysis). The usual way to prove that a nonhyperarithmetical set does not belong to the hard core is to construct an ω-model of analysis that omits the type representing the set (Application 1). We will find basis results for and s — sets that are stronger than results previously known (Applications 2 and 3). The question of how far the natural hierarchy of hyperjumps extends was first settled by a forcing argument (Sacks) and subsequently by a compactness argument (Kripke, Richter). Another problem solved by a forcing argument (Sacks) and then by a compactness argument (Friedman-Jensen) was the characterization of the countable admissible ordinals as the relativized ω1's. Using omitting-types technique, we will supply a third kind of proof of these results (Applications 4 and 5). S. Simpson made a significant contribution in simplifying the proof of the latter result, with the interesting side effect that Friedman's result on ordinals in models of set theory is immediate (Application 6). One approach to abstract recursiveness and hyperarithmeticity on a countable set is to tenuously identify the set with the natural numbers. This approach is equivalent to other approaches to abstract recursion (Application 7). This last result may also be proved by a forcing method.
Sets of theorems with short proofs
Authors: Richardson Daniel
Published: May 2006

R. Parikh has shown that in the predicate calculus without function symbols it is possible to decide whether or not a given formula A is provable in a Hilbert-style proof of k lines. He has also shown that for any formula A(x1, …, xn) of arithmetic in which addition and multiplication are represented by three-place predicates, {(a1, …, an): A(a1, …, an) is provable from the axioms of arithmetic in k lines} is definable in (N,′, +,0). See [2].

In §1 of this paper it is shown that if S is a definable set of n-tuples in (N,′, +, 0), then there is a formula A(x1, …, xn) and a number k so that (a1 …, an) ∈ S if and only if A(a1 …, an) can be proved in a proof of complexity k from the axioms of arithmetic. The result does not depend on which formalization of arithmetic is used or which (reasonable) measure of proof complexity. In particular, this gives a converse to Parikh's result.

In §II, a measure of proof complexity is given which is based on counting the quantifier steps in semantic tableaux. The idea behind this measure is that A is k provable if in the attempt to construct a counterexample one meets insurmountable difficulties in the definition of the appropriate Skolem functions over sets of cardinality ≤ k. A method is given for deciding whether or not a sentence A in the full predicate calculus is k provable. The question for the full predicate calculus and Hilbert-style systems of proof remains open.
Boolean extensions which efface the Mahlo property
Authors: Boos William
Published: May 2006

The results that follow are intended to be understood as informal counterparts to formal theorems of Zermelo-Fraenkel set theory with choice. Basic notation not explained here can usually be found in [5]. It will also be necessary to assume a knowledge of the fundamentals of boolean and generic extensions, in the style of Jech's monograph [3]. Consistency results will be stated as assertions about the existence of certain complete boolean algebras, B, C, etc., either outright or in the sense of a countable standard transitive model M of ZFC augmented by hypotheses about the existence of various large cardinals. Proofs will usually be phrased in terms of the forcing relation ⊩ over such an M, especially when they make heavy use of genericity. They are then assertions about Shoenfield-style P-generic extensions M(G), in which the ‘names’ are required without loss of generality to be elements of MB = (VB)M, B is the boolean completion of P in M (cf. [3, p. 50]: the notation there is RO(P)), the generic G is named by Ĝ ∈ MB such that (⟦p ∈ Ĝ⟧B = p and (cf. [11, p. 361] and [3, pp. 58–59]), and for p ∈ P and c1, …, cn ∈ MB, p ⊩ φ(c1, …, cn) iff ⟦φ(c1, …, cn)⟧B ≥ p (cf. [3, pp. 61–62]).

Some prior acquaintance with large cardinal theory is also needed. At this writing no comprehensive introductory survey is yet in print, though [1], [10], [12]and [13] provide partial coverage. The scheme of definitions which follows is intended to fix notation and serve as a glossary for reference, and it is followed in turn by a description of the results of the paper. We adopt the convention that κ, λ, μ, ν, ρ and σ vary over infinite cardinals, and all other lower case Greek letters (except χ, φ, ψ, ϵ) over arbitrary ordinals.
Nowhere simple sets and the lattice of recursively enumerable sets
Authors: Shore Richard A.
Published: May 2006

Ever since Post [4] the structure of recursively enumerable sets and their classification has been an important area in recursion theory. It is also intimately connected with the study of the lattices and of r.e. sets and r.e. sets modulo finite sets respectively. (This lattice theoretic viewpoint was introduced by Myhill [3].) Key roles in both areas have been played by the lattice of r.e. supersets, , of an r.e. set A (along with the corresponding modulo finite sets) and more recently by the group of automorphisms of and . Thus for example we have Lachlan's deep result [1] that Post's notion of A being hyperhypersimple is equivalent to (or ) being a Boolean algebra. Indeed Lachlan even tells us which Boolean algebras appear as —precisely those with Σ3 representations. There are also many other simpler but still illuminating connections between the older typology of r.e. sets and their roles in the lattice . (r-maximal sets for example are just those with completely uncomplemented.) On the other hand, work on automorphisms by Martin and by Soare [8], [9] has shown that most other Post type conditions on r.e. sets such as hypersimplicity or creativeness which are not obviously lattice theoretic are in fact not invariant properties of .

In general the program of analyzing and classifying r.e. sets has been directed at the simple sets. Thus the subtypes of simple sets studied abound — between ten and fifteen are mentioned in [5] and there are others — but there seems to be much less known about the nonsimple sets. The typologies introduced for the nonsimple sets begin with Post's notion of creativeness and add on a few variations. (See [5, §8.7] and the related exercises for some examples.) Although there is a classification scheme for r.e. sets along the simple to creative line (see [5, §8.7]) it is admitted to be somewhat artificial and arbitrary. Moreover there does not seem to have been much recent work on the nonsimple sets.
Relation of Leśniewski's mereology to Boolean algebra
Authors: Clay Robert E.
Published: May 2006

It has been stated by Tarski [5] and “proved” by Grzegorczyk [3] that:

(A) The models of mereology and the models of complete Boolean algebra with zero deleted are identical.

Proved has been put in quotes, not because Grzegorczyk's proof is faulty but because the system he describes as mereology is in fact not Leśniewski's mereology.

Leśniewski's first attempt at describing the collective class, i.e. mereology, was done in ordinary language with no rigorous logical foundation. In describing the collective class, he needed to use the notion of distributive class. So as to clearly distinguish and expose the interplay between the two notions of class, he introduced his calculus of name (name being the distributive notion), which is also called ontology, since he used the primitive term “is.” At this stage, mereology included ontology. Then, in order to have a logically rigorous system, he developed as a basis, a propositional calculus with quantifiers and semantical categories (types), called protothetic. At this final stage, what is properly called mereology includes both protothetic and ontology.

What Grzegorczyk describes as mereology is even weaker than Leśniewski's initial version. To quote from [3]:

“In order to emphasize these formal relations let us consider the systems of axioms of mereology for another of its primitive terms, namely for the term “ingr” defined as follows:

A ingr B.≡.A is a part B ∨ A is identical to B.

The proposition “A ingr B” can be read “A is contained in B” or after Leśniewski, “A is ingredient of B”.”
One more aspect of forcing and omitting types
Authors: Adamowicz Zofia
Published: May 2006

As has been shown by the investigations of some mathematicians, there are numerous analogies between forcing and omitting types. Evidence of that can also be found in the application of forcing to model theory. Both methods use the Rasiowa-Sikorski lemma on the existence in a Boolean algebra of an ultrafilter intersecting every dense set from a given denumerable family.

In this paper we will not use the terms Cohen forcing and omitting types in their original sense. We shall deal mainly with the Scott-Boolean kind of forcing as a transformation of Cohen's idea and with methods used in logic that consist in finding a suitable ultrafilter in the Lindenbaum-Tarski algebra for a given theory and defining canonical models—under the name of omitting types.

The two methods will be confronted to show that Cohen's forcing stems from logical methods. Attention will also be drawn to some differences between forcing in set theory and the general methods of logic.

In logic we construct a model by defining relations in a set of constants. In particular when defining a model for set theory we define a certain relation E in a set of constants. It is usually immaterial what E is, in particular whether it is the true relation of membership up to isomorphism.
Semantics of the infinitistic rules of proof
Authors: Apt Krzysztof Rafal
Published: May 2006

This paper is devoted to the study of the infinitistic rules of proof i.e. those which admit an infinite number of premises. The best known of these rules is the ω-rule. Some properties of the ω-rule and its connection with the ω-models on the basis of the ω-completeness theorem gave impulse to the development of the theory of models for admissible fragments of the language . On the other hand the study of representability in second order arithmetic with the ω-rule added revealed for the first time an analogy between the notions of re-cursivity and hyperarithmeticity which had an important influence on the further development of generalized recursion theory.

The consideration of the subject of infinitistic rules in complete generality seems to be reasonable for several reasons. It is not completely clear which properties of the ω-rule were essential for the development of the above-mentioned topics. It is also worthwhile to examine the proof power of infinitistic rules of proof and what distinguishes them from finitistic rules of proof.

What seemed to us the appropriate point of view on this problem was the examination of the connection between the semantics and the syntax of the first order language equipped with an additional rule of proof.
Elementary extensions of countable models of set theory
Authors: Hutchinson John E.
Published: May 2006

We prove the following extension of a result of Keisler and Morley. Suppose is a countable model of ZFC and c is an uncountable regular cardinal in . Then there exists an elementary extension of which fixes all ordinals below c, enlarges c, and either (i) contains or (ii) does not contain a least new ordinal.

Related results are discussed.
Complete types and the natural numbers
Authors: Knight Julia F.
Published: May 2006

In this paper it is shown that, for any complete type Σ omitted in the structure , or in any expansion of having only countably many relations and operations, there is a proper elementary extension of (or of ) which omits Σ. This result (which was announced in [2]) is used to answer a question of Malitz on complete -sentences. The result holds also for countable families of types.

A type is a countable set of formulas with just the variable υ free. A structure is said to omit a type Σ if no element of satisfies all of the formulas of Σ. For example, omits the type Σω = {υ ≠ n: n ∈ ω}, since n fails to satisfy υ ≠ n. (Here n is the constant symbol standing for n.)

A type Σ is said to be complete with respect to a theory T if the set of sentences T ∪ Σ(e) generates a complete theory, where Σ(e) is the result of replacing υ by the new constant e in all of the formulas of Σ. The type Σω is clearly not complete with respect to Th(). (For any structure Th(), Th() is the set of all sentences true in .)
Théories d'arbres
Authors: Parigot Michel
Published: May 2006

Les arbres sont les ordres partiels qui vérifient l'axiome supplémental ∀x∀y∀z(y ≤x ∧z ≤ x → y ≤ z ∨ z ≤ y), i.e. l'ensemble des minorants de chaque élément est totalement ordonné.

Le principal résultat de cet article concerne l'instabilité des arbres: nous prouvons (§2) qu'aucune théorie d'arbre n'a la propriété d'indépendance, ce qui généralise un theoreme de Poizat [3] sur les ordres totaux. II s'en suit au moyen d'un resultat d'interprétation [4] qu'aucune théorie de structure arborescente n'a la propriété d'indépendance; en particulier ceci vaut pour les arbres colorés.

Le §3 est consacré aux arbres stables. II est prouvé qu'un arbre est stable ssi il est superstable ssi il est de hauteur bornée. Sous l'hypothèse de stabilité, les arbres premiers, minimaux, et strictement minimaux sont caractérisés en termes d'al-gébricité.
Refinements of Vaught's normal from theorem
Authors: Harnik Victor
Published: May 2006

The central notion of this paper is that of a (conjunctive) game-sentence, i.e., a sentence of the form

where the indices ki, ji range over given countable sets and the matrix conjuncts are, say, open -formulas. Such game sentences were first considered, independently, by Svenonius [19], Moschovakis [13]—[15] and Vaught [20]. Other references are [1], [3]—[5], [10]—[12]. The following normal form theorem was proved by Vaught (and, in less general forms, by his predecessors).

Theorem 0.1. Let L = L0(R). For every -sentence ϕ there is an L0-game sentence Θ such that ⊨′ ∃Rϕ ↔ Θ.

(A word about the notations: L0(R) denotes the language obtained from L0 by adding to it the sequence R of logical symbols which do not belong to L0; “⊨′α” means that α is true in all countable models.)

0.1 can be restated as follows.

Theorem 0.1′. For every-sentence ϕ there is an L0-game sentence Θ such that ⊨ϕ → Θ and for any-sentence ϕ if ⊨ϕ → ϕ and L′ ⋂ L ⊆ L0, then ⊨ Θ → ϕ.

(We sketch the proof of the equivalence between 0.1 and 0.1′.

0.1 implies 0.1′. This is obvious once we realize that game sentences and their negations satisfy the downward Löwenheim-Skolem theorem and hence, ⊨′α is equivalent to ⊨α whenever α is a boolean combination of and game sentences.