bluuebunny/crossref_metadata_2025 huggingface dataset:
Descriptive completeness and inductive methods
Authors: Lehrer Keith
Published: May 2006

In a recent paper Professor Wesley Salmon1 has shown that a certain class of c-functions, including the c-function c*. described by Rudolph Carnap2 yield incompatible results when applied to the same sentences in two languages systems which, though they have the same individual constants, do not have the same predicates. Each c-function of the class in question is characterized by a parameter λ which is a function of the number of Q-predicates in the language system in which the c-function is used.3 Taking c* as representative of this class of c-functions, I shall argue that Professor Salmon's results do not provide a reasonable basis for rejecting such c-functions in favor of others. More specifically, I shall argue (i) that such c-functions yield incompatible results in two languages because not both of the languages are sufficiently complete, (ii) that for any two languages in which such c-functions yield incompatible results there is a rule that will select either the more complete of the two languages or a language that is more complete than either of the two languages, and (iii) that it is impossible for such c-functions to yield incompatible results in two languages that are equally complete.
A note on modified abstraction principles
Authors: Lake John
Published: May 2006

The abstraction principle is

for K any formula not involving x. This is well known to be inconsistent and in [1] Hintikka proposed two modified versions of (0) which we briefly describe. First, he suggested

where K is any formula not involving x, and K+ is obtained from K by replacing subformulae of the form ∃zL by ∃z(z ≠ x ∧ L) and those of the form ∀zL by ∀z(z ≠ x → L), etc. The second version is

where K+ is a formula of the type described for (1) and z1 …, zk are all the free variables in (2).
Note on an induction axiom
Authors: Paris J. B.
Published: May 2006

Let θ(ν) be a formula in the first-order language of arithmetic and let

In this note we study the relationship between the schemas I′ and I+.

Our interest in I+ lies in the fact that it is ostensibly a more reasonable schema than I′. For, if we believe the hypothesis of I+(θ) then to verify θ(n) only requires at most 2log2(n) steps, whereas assuming the hypothesis of I′(θ) we require n steps to verify θ(n). In the physical world naturally occurring numbers n rarely exceed 10100. For such n applying 2log2(n) steps is quite feasible whereas applying n steps may well not be.

Of course this is very much an anthropomorphic argument so we would expect that it would be most likely to be valid when we restrict our attention to relatively simple formulas θ. We shall show that when restricted to open formulas I+ does not imply I′ but that this fails for the classes Σn, Πn, n ≥ 0.

We shall work in PA−, where PA− consists of Peano's Axioms less induction together with

∀u, w(u + w = w + u ∧ u · w = w · u),

∀u, w, t ((u + w) + t = u + (w + t) ∧ (u · w) · t = u · (w · t)),

∀u, w, t(u · (w + t) = u · w + u · t),

∀u, w(u ≤ w ↔ ∃t(u + t = w)),

∀u, w(u ≤ w ∨ w ≤ u),

∀u, w, t(u + w = u + t → w = t).

The reasons for working with PA− rather than Peano's Axioms less induction is that our additional axioms, whilst intuitively reasonable, will not necessarily follow from some of the weaker forms of I+ which we shall be considering. Of course PA− still contains those Peano Axioms which define + and

Notice that, trivially, PA− ⊦ I′(θ) → I+(θ) for any formula θ.
Undecidable properties of finite sets of equations
Authors: McNulty George F.
Published: May 2006

Though equations are among the simplest sentences available in a first order language, many of the most familiar notions from algebra can be expressed by sets of equations. It is the task of this paper to expose techniques and theorems that can be used to establish that many collections of finite sets of equations characterized by common algebraic or logical properties fail to be recursive. The following theorem is typical.

Theorem. In a language provided with an operation symbol of rank at least two, the collection of finite irredundant sets of equations is not recursive.

Theorems of this kind are part of a pattern of research into decision problems in equational logic. This pattern finds its origins in the works of Markov [8] and Post [20] and in Tarski's development of the theory of relation algebras; see Chin [1], Chin and Tarski [2], and Tarski [23]. The papers of Mal′cev [7] and Perkins [16] are more directly connected with the present paper, which includes generalization of much of Perkins' work as well as extensions of a theorem of D. Smith [22]. V. L. Murskii [14] contains some of the results below discovered independently. Not all known results concerning undecidable properties of finite sets of equations seem to be susceptible to the methods presented here. R. McKenzie, for example, shows in [9] that for a language with an operation symbol of rank at least two, the collection of finite sets of equations with nontrivial finite models is not recursive. D. Pigozzi has extended and elaborated the techniques of this paper in [17], [18], and [19] to obtain new results concerning undecidable properties, particularly those of algebraic character.
On the first-order logic of terms
Authors: Svenonius Lars
Published: May 2006

By an elementary condition in the variablesx1, …, xn, we mean a conjunction of the form x1 ≤ i < j ≤ naij where each aij is one of the formulas xi = xj or xi ≠ xj. (We should add that the formula x1 = x1 should be regarded as an elementary condition in the one variable x1.)

Clearly, according to this definition, some elementary conditions are inconsistent, some are consistent. For instance (in the variables x1, x2, x3) the conjunction x1 = x2 & x1 = x3 & x2 ≠ x3 is inconsistent.

By an elementary combinatorial function (ex. function) we mean any function which can be given a definition of the form

where E1(x1, …, xn), …, Ek(x1, …, xn) is an enumeration of all consistent elementary conditions in x1, …, xn, and all the numbers d1, …, dk are among 1, …, n.

Examples. (1) The identity function is the only 1-ary e.c. function.

(2) A useful 3-ary e.c. function will be called J. The definition is
Observations concerning elementary extensions of ω-models. II
Authors: Marek W.
Published: May 2006

This paper contains some observations on models for A2-second-order arithmetics. It arose from unsuccessful attempts to prove the Conjecture 1 (see at the end of the paper). Two partial solutions are given in this paper. We also give a sketch of a new proof of a classical result of descriptive set-theory referred to in [3]. Unless otherwise specified the word “model” means “ω-model for second-order arithmetics with the axiom scheme of choice,” i.e., “ω-model of A2” in the terminology of [3]. We say that a model M1 is shorter than M2 iff there is in M2 a relation A which is a well-ordering in M2 such that every relation B which is a well-ordering in M1 is similar to an initial segment of A. We denote by M0 the principal model of A2, i.e., a model which has only standard integers and contains all sets of integers.
Minimal models
Authors: Deissler Rainer
Published: May 2006

A model is called minimal if it does not contain a proper elementary submodel. A class of models is called Σ11(Π11 resp. elementary) if it is axiomatized by a sentence with σ in and some string of predicate symbols. All languages considered are assumed to be countable. For each model we shall define in a natural way its rank, denoted by rk (), which is an ordinal or ∞. Intuitively speaking, rk () is the least upper bound for the number of steps needed to define the elements of by first order formulas; e.g. we shall have rk((ω, <)) = 1 (each element is f.o. definable), rk ((Z, <)) = 2 (no element is f.o. definable, each element is f.o. definable using any other element as a parameter), rk ((Q, <) ) = ∞ (no element is f.o. definable by any number of steps). This notion of rank leads to a useful game theoretic characterization of minimal models which we apply to show that the Π11 class of minimal models is not Σ11.
Compactness and transfer for a fragment of L2
Authors: Magidor M. , Malitz J.
Published: May 2006

The language Ln is obtained from the first order predicate calculus by adjoining the quantifier Qn which binds n variables. The formula Qnυ1 … υnΨ is given a κ-interpretation for each infinite cardinal κ, namely, “there is a set X of power κ such that Ψx1 … xn holds for all distinct x1 … xn ϵ X”. L<ω is the result of adjoining all the Qn quantifiers for each n ϵ ω to the first order predicate calculus.

In [4] we showed that under the assumption (cf. [3]) L<ω is countably compact under the ω1-interpretation, and that any sentence σ ϵ L<ω that has a model in some κ-interpretation where κ is a regular infinite cardinal has a model in the ω1 interpretation. However, compactness for L<ω in the κ-interpretation for κ an infinite successor cardinal other than ω1 and the transfer of satisfiability from ω1 to any higher power remain open questions under any set theoretic assumptions.

Here we restrict our attention to a small fragment L2− of L2 consisting of universal first order formulas along with formulas of the kind Q2υ1υ2∀υ3 … υnΨ and ¬Q2υ1υ2∀υ3 … υnφ where Ψ and φ are open and no function symbol of arity > 1 occurs in any formula. Assuming the existence of a κ-Souslin tree, this language is λ compact in the κ-interpretation when λ < κ.
Craig interpolation theorem for intuitionistic logic and extensions Part III
Authors: Gabbay Dov M.
Published: May 2006

This is a continuation of two previous papers by the same title [2] and examines mainly the interpolation property for the logic CD with constant domains, i.e., the extension of the intuitionistic predicate logic with the schema

It is known [3], [4] that this logic is complete for the class of all Kripke structures with constant domains.

Theorem 47. The strong Robinson consistency theorem is not true for CD.

Proof. Consider the following Kripke structure with constant domains. The set S of possible worlds is ω0, the set of positive integers. R is the natural ordering ≤. Let ω0 0 = , Bn, is a sequence of pairwise disjoint infinite sets. Let L0 be a language with the unary predicates P, P1 and consider the
following extensions for P,P1 at the world m.

(a) P is true on ⋃i≤2nBi, and P1 is true on ⋃i≤2n+1Bi for m = 2n.

(b) P is true on ⋃i≤2nBi, and P1 for ⋃i≤2n+1Bi for m = 2n.

Let (Δ,Θ) be the complete theory of this structure. Consider another unary predicate Q. Let L be the language with P, Q and let M be the language with P1, Q.
A lattice of interpretability types of theories
Authors: Mycielski Jan
Published: May 2006

We consider first-order logic only. A theory S will be called locally interpretable in a theory T if every theorem of S is interpretable in T. If S is locally interpretable in T and T is consistent then S is consistent. Most known relative consistency proofs can be viewed as local interpretations. The classic examples are the cartesian interpretation of the elementary theorems of Euclidean n-dimensional geometry into the first-order theory of real closed fields, the interpretation of the arithmetic of integers (rational numbers) into the arithmetic of positive integers, the interpretation of ZF + (V = L) into ZF, the interpretation of analysis into ZFC, relative consistency proofs by forcing, etc. Those interpretations are global. Under fairly general conditions local interpretability implies global interpretability; see Remarks (7), (8), and (9) below.

We define the type (interpretability type) of a theory S to be the class of all theories T such that S is locally interpretable in T and vice versa. There happen to be such types and they are partially ordered by the relation of local interpretability. This partial ordering is of lattice type and has the following form:

The lattice is distributive and complete and satisfies the infinite distributivity law of Brouwerian lattices:

We do not know if the dual law

is true. We will show that the lattice is algebraic and that its compact elements form a sublattice and are precisely the types of finitely axiomatizable theories, and several other facts.
Semi-minimal theories and categoricity
Authors: Andler Daniel
Published: May 2006

The study of countable theories categorical in some uncountable power was initiated by Łoś and Vaught and developed in two stages. First, Morley proved (1962) that a countable theory categorical in some uncountable power is categorical in every uncountable power, a conjecture of Łoś. Second, Baldwin and Lachlan confirmed (1969) Vaught's conjecture that a countable theory categorical in some uncountable power has either one or countably many isomorphism types of countable models. That result was obtained by pursuing a line of research developed by Marsh (1966). For certain well-behaved theories, which he called strongly minimal, Marsh's method yielded a simple proof of Łoś's conjecture and settled Vaught's conjecture.

In recent years efforts have been made to extend these results to uncountable theories. The generalized Łoś conjecture states that a theory T categorical in some power greater than ∣T∣ is categorical in every such power. It was settled by Shelah (1970). Shelah then raised the question of the models in power ∣T∣ = ℵα of a theory T categorical in ∣T∣+, conjecturing in [S3] that there are exactly ∣α∣ + ℵ0 such models, up to isomorphism. This conjecture provided the initial motivation for the present work. We define and study semi-minimal theories analogous in some ways to Marsh's strongly minimal (countable) theories. We describe the models of a semi-minimal theory T which contain an infinite indiscernible set. Besides throwing some light on Shelah's conjecture, our method gives simple proofs of the Łoś conjecture and of the Morley conjecture on categoricity in ∣T∣, in the case of a semi-minimal theory T. Other results as well as some examples are provided.
Gödel's Second incompleteness theorem for Q
Authors: Bezboruah A. , Shepherdson J. C.
Published: May 2006

For the first Gödel incompleteness theorem, the existence in a formal system of arithmetic L of a sentence which is neither provable nor refutable, all that is required of the formula Th(x) of L used to express the notion ‘x is the g.n. (gödel number) of a theorem of L’ is mere numeralwise correctness, i.e. that for a numeral n, Th(n) is provable in L iff n is the g.n. of a theorem of L. It is well known that much more is needed for the second Gödel incompleteness theorem, the unprovability in L of the formula Con =df ¬(∃y, z)(Th(y) ∧ Th(z) ∧ neg(z, y)), which (if neg expresses negation) expresses the consistency of L. Conditions sufficient for this second theorem, more or less as stated by Hilbert-Bernays [1, p. 286] and elegantly formulated by Löb [2] may with a cavalier disregard for the distinction between use and mention be stated thus: The result of the first incompleteness theorem: there is a sentence G such that ⊢G ↔ ¬Th G), together with, if ⊢A then ⊢Th A, if ⊢(A → B) then ⊢(Th A → Th B), ⊢(Th A → Th Th A). On the other hand Feferman [3], Kreisel [4, p. 154] and Jeroslow [9] have given examples of systems and consistency formulae, based on numeralwise correct formulae Th(x), which are provable within the system.
On characterizing Spector classes
Authors: Harrington Leo A. , Kechris Alexander. S.
Published: May 2006

We study in this paper characterizations of various interesting classes of relations arising in recursion theory. We first determine which Spector classes on the structure of arithmetic arise from recursion in normal type 2 objects, giving a partial answer to a problem raised by Moschovakis [8], where the notion of Spector class was first essentially introduced. Our result here was independently discovered by S. G. Simpson (see [3]). We conclude our study of Spector classes by examining two simple relations between them and a natural hierarchy to which they give rise.

The second part of our paper is concerned with finding structural characterizations of classes of relations on the reals in the spirit of Moschovakis [7]. Our main result provides a single abstract characterization for the class of relations on the reals and the 2-envelope of 3E, the first one being valid if projective determinacy is true, the second if V = L is true.
Omitting models
Authors: Snapper Ernest
Published: May 2006

The purpose of this paper is to introduce the notion of “omitting models” and to derive a very natural theorem concerning it (Theorem 1). A corollary of this theorem is the remarkable theorem of Vaught [3] which states that a countable complete theory cannot have precisely two nonisomorphic countable models. In fact, we show that our theorem implies Rosenstein's theorem [2] which, in turn, implies Vaught's theorem.

T stands for a countable complete theory whose (countable) language is denoted by L. Following [1], a countably homogeneous model of T is a countable model of T with the property that, for any two n-tuples a1, …, an and b1,…,bn of the universe of whose types are the same, there is an automorphism of which maps ai, on bi, for i = 1, …, n [1, p. 129 and Proposition 3.2.9, p. 131]. “Homogeneous model” always means “countably homogeneous model.” “Type of T” always stands for “n-type of T” where n ≥ s 0, i.e., for the type of some n-tuple of individuals of the universe of some model of T. We often use that two homogeneous models which realize the same types are isomorphic [1, Proposition 3.2.9, p. 131].

It is well known that every type of T is realized by at least one countable model of T. The main definition of this paper is:

Definition 1. A set of countable models of T is omissible or “may be omitted” if every type of T is realized by at least one countable model of T which is not isomorphic to a model in the set.

The main theorem of the paper is:

Theorem 1. If a countable complete theory is not ω-categorical, every finite set of its homogeneous models may be omitted.

The theorem is proved in §1 and in §2 it is shown how Vaught's and Rosenstein's theorems follow from it. §3 discusses some general aspects of omitting models.
Primitive recursive ordinal functions with added constants
Authors: Stahl Stanley H.
Published: May 2006

One of the basic differences between the primitive recursive functions on the natural numbers and the primitive recursive ordinal functions (PR) is the nearly complete absence of constant functions in PR. Since ω is closed under all of the functions in PR, if α is any infinite ordinal, then λξ·α is not in PR. It is easily seen, however, that if one adds to the initial functions of PR the constant function λξ·ω, then all of the ordinals up to ω#, the next largest PR-closed ordinal, have their constant functions in this class. Since, however, such collections of functions are always countable, it is also the case that if one adds to the initial functions of PR the function λξ. α for uncountable α, then there are ordinals β < α whose constant functions are not in this collection. Because of this, the following objects are of interest:

Definition. For all α,

(i)PR(α) is the collection of functions obtained by adding to the initial primitive recursive ordinal functions, the function λξ· α;

(ii) PRsp(α), the primitive recursive spectrum of α, is the set {β < α ∣ λξβ ∈ PR(α);

(iii) Λ (α)= μρ(ρ∉ PRsp(α)).
Logics containing K4. Part I
Authors: Fine Kit
Published: May 2006

There are two main lacunae in recent work on modal logic: a lack of general results and a lack of negative results. This or that logic is shown to have such and such a desirable property, but very little is known about the scope or bounds of the property. Thus there are numerous particular results on completeness, decidability, finite model property, compactness, etc., but very few general or negative results.

In these papers I hope to help fill these lacunae. This first part contains a very general completeness result. Let In be the axiom that says there are at most n incomparable points related to a given point. Then the result is that any logic containing K4 and In is complete.

The first three sections provide background material for the rest of the papers. The fourth section shows that certain models contain no infinite ascending chains, and the fifth section shows how certain elements can be dropped from the canonical model. The sixth section brings the previous results together to establish completeness, and the seventh and last section establishes compactness, though of a weak kind. All of the results apply to the corresponding intermediate logics.
Sets constructible from sequences of ultrafilters
Authors: Mitchell William J.
Published: May 2006

In [4], Kunen used iterated ultrapowers to show that ifUis a normalκ-complete nontrivial ultrafilter on a cardinalκthenL[U], the class of sets constructive fromU, has only the ultrafilterU∩L[U] and this ultrafilter depends only onκ. In this paper we extend Kunen's methods to arbitrary sequencesUof ultrafilters (provided that they fulfill a coherency condition) and obtain generalizations of these results (§3). In particular we answer Problem 1 of Kunen and Paris [5] which asks whether the number of ultrafilters onκcan be intermediate between 1 and 22κ. If there is a normalκ-complete ultrafilterUonκsuch that {α <κ: α is measurable} ∈Uthen there is an inner model with exactly two normal ultrafilters onκ, and ifκis super-compact then there are inner models havingκ+ +,κ+or any cardinal less than or equal toκnormal ultrafilters (§4).

These methods also show that several properties ofLwhich had been shown to hold forL[U] also hold forL[U]: using an idea of Silver we show that inL[U] the generalized continuum hypothesis is true, there is a Souslin tree, and there is awell-ordering of the reals. In addition we generalize a result of Kunen to characterize the countaby complete ultrafilters ofL[U].
Honest bounds for complexity classes of recursive functions
Authors: Moll R. , Meyer A. R.
Published: May 2006

Let be the set of recursive functions computable by machines using at most t(x) computation steps on argument x, for all but finitely many inputs x. We call t a name for the complexity class . Suppose we allow our machines to run longer, say h(x, t(x)) steps on argument x, where h is some fixed recursive function. One might expect that, for large enough h, permitting our machines to run longer by an amount h will always allow us to compute new functions, i.e., is a proper subset of . This turns out not to be the case: The “gap theorem” ([2], [3]) implies that for every recursive h there exists a recursive t such that . However, if we restrict our attention to names from a certain subclass of the recursive functions, then we can indeed uniformly increase the size of our -classes. Informally, we call a recursive function t “honest” if some machine computes t(x) in roughly t(x) steps for each argument x. (A precise definition is given in Definition 1 below.) Then according to the “compression theorem” [1], there exists a single recursive function h such that, for every honest t, is a proper subset of . Thus the phenomenon of the gap theorem is avoided by restricting attention to honest functions. It is a surprising consequence of the “honesty theorem” of McCreight and Meyer ([4], [5]) that there is no loss of generality in this restriction. Namely, for any recursive function t there is an honest recursive function t′ such that .
On deciding the truth of certain statements involving the notion of consistency
Authors: Boolos George
Published: May 2006

Friedman has posed (see [F, p. 117]) the following problem: “35. Define the set E of expressions by (i) Con is an expression; (ii) if A, B are expressions so are (~ A), (A&B), and Con(A). Each expression ϕ in E determines a sentence ϕ in PA [classical first-order arithmetic] by taking Con* to be “PA is consistent,” ( ~ A) * to be ~ (A*), (A&B)* to be A*&B*, and Con(A)* to be “PA + ‘A*’ is consistent.” The set of expressions ϕ ∈ E such that ϕ* is true is recursive.

The formalized second incompleteness theorem reads

In order to simplify notation, we will reformulate Friedman's problem slightly. Let Con be the usual sentence of PA expressing the consistency of PA, ~ A the negation of A, (A&B) the conjunction of A and B, etc., and Bew(A) the result of substituting the numeral for the Gödel number of A for the free variable in the usual provability predicate for PA. Let Con(A) = ~ Bew(~ A). (Con(A) is equivalent in PA to the usual sentence expressing the consistency of PA + A.) And let the class of F-sentences be the smallest class which contains Con and which also contains ~ A, (A&B) and Con(A) whenever it contains A and B. Since ⊦PA Bew(A) ↔ Bew(B) if ⊦PAA ↔ B, Friedman's problem is then the question whether the class of true F-sentences is recursive.

The answer is that it is recursive. To see why, we need a definition and a theorem.

Definition. An atom is a sentence Conn for some n ≥ 1, where Cont = Con and Conn + 1 = Con(Conn).
An extension of Ackermann's set theory
Authors: Perlis Donald
Published: May 2006

Ackermann's set theory [1], called here A, involves a schema

where φ is an ∈-formula with free variables among y1, …, yn and w does not appear in φ. Variables are thought of as ranging over classes and V is intended as the class of all sets.

S is a kind of comprehension principle, perhaps most simply motivated by the following idea: The familiar paradoxes seem to arise when the class CP of all P-sets is claimed to be a set, while there exists some P-object x not in CP such that x would have to be a set if CP were. Clearly this cannot happen if all P-objects are sets.

Now, Levy [2] and Reinhardt [3] showed that A* (A with regularity) is in some sense equivalent to ZF. But the strong replacement axiom of Gödel-Bernays set theory intuitively ought to be a theorem of A* although in fact it is not (Levy's work shows this). Strong replacement can be formulated as

This lack of A* can be remedied by replacing S above by

where ψ and φ are ∈-formulas and x is not in ψ and w is not in φ. ψv is ψ with quantifiers relativized to V, and y and z stand for y1, …, yn and z1, …, zm.
Correction to ‘A model theoretic characterisation of effective operations’
Authors: Löb M. H.
Published: May 2006

With the definition of effective operations as stated in the paper cited above (this Journal, vol. 35 (1970), p. 217), the last step of Lemma 1 does not appear to extend to types ≥ 3. This may be rectified by altering the second clause of the definition of effective operation (loc. cit. p. 217) to read:

ℱ is an effective operation of type i + 2 with Gödel number f∈Ei+2, if for every g∈Ei+1 there is an effective operation of type i + 1 (not depending on ℱ and f) with Gödel number g such that ℱ() = p(f, g).

With this definition the proofs go through without alteration.

There are two other variants for representing an effective operation by higher type objects.

I. We adopt the definition of effective as given in the text, and require the terms to satisfy the additional condition

II. Here we add to the definition of effective operations given in the text the condition:

If ℱ and ℱ1 are effective operations of type i + 2 and for all effective operations of type i + 1, then ℱ = ℱ1.

We now require terms s, t ∈ fi to satisfy the additional condition

The proof of Lemmas 1 and 2 are easily modified to establish I and II.

Perhaps II may be regarded as giving the most natural characterisation since in this case all terms represent continuous functionals.
Combinator realizability of a constructive Morse set theory
Authors: Staples John
Published: May 2006

A constructive version of Morse set theory is given, based on Heyting's predicate calculus and with countable rather than full choice. An elaboration of the method of [5] is used to show that the theory is combinator-realizable in the sense defined there. The proof depends on the assumption of the syntactic consistency of the theory.

The method is introduced by first treating a subtheory without countable choice of foundation.

It is intended that the work can be read either classically or constructively, though whether the word constructive is correctly used as a description of either the theory or the metatheory is of course a matter of opinion.
Characterization of recursively enumerable sets
Authors: Wright Jesse B.
Published: May 2006

Let N, O and S denote the set of nonnegative integers, the graph of the constant 0 function and the graph of the successor function respectively. For sets P, Q, R ⊆ N2 operations of transposition, composition, and bracketing are defined as follows: P∪ = {〈x, y〉 ∣ 〈y, x〉 ∈ P}, PQ = {〈x, z〉 ∣ ∃y〈x, y〉 ∈ P & 〈y, z〉 ∈ Q}, and [P, Q, R] = ⋃n ∈ M(Pn Q Rn).

Theorem. The class of recursively enumerable subsets of N2 is the smallest class of sets with O and S as members and closed under transposition, composition, and bracketing.

This result is derived from a characterization by Julia Robinson of the class of general recursive functions of one variable in terms of function composition and “definition by general recursion.” A key step in the proof is to show that if a function F is defined by general recursion from functions A, M, P and R then F = [P∪, A∪M, R].

The above definitions of the transposition, composition, and bracketing operations on subsets of N2 can be generalized to subsets of X2 for an arbitrary set X. In this abstract setting it is possible to show that the bracket operation can be defined in terms of K, L, transposition, composition, intersection, and reflexive transitive closure where K: X → X and L: X → X are functions for decoding pairs.
The inconsistency of a certain axiom system for set theory
Authors: Davis James D.
Published: May 2006

We prove in this paper that the -system, an axiom system for set theory suggested for investigation by Takeuti in [2], is inconsistent. We also show that this system without the ω-rule is consistent if Zermelo-Fraenkel set theory with the axiom of choice and an axiom due to Reinhardt and Silver is consistent. The -system is an effort to strengthen Bernays-Gödel set theory by adding a reflection principle.

In addition to the standard notation of set theory, we write X″{x) to mean {y∣〈x, y〉 Є X}.
Theories without countable models
Authors: Blass Andreas
Published: May 2006

Consider the Löwenheim-Skolem theorem in the form: If a theory in a countable first-order language has a model, then it has a countable model. As is well known, this theorem becomes false if one omits the hypothesis that the language be countable, for one then has the following trivial counterexample.

Example 1. Let the language have uncountably many constants, and let the theory say that they are unequal.

To motivate some of our future definitions and to introduce some notation, we present another, less trivial, counterexample.

Example 2. Let L0 be the language whose n-place predicate (resp. function) symbols are all the n-place predicates (resp. functions) on the set ω of natural numbers. Let be the standard model for L0; we use the usual notation Th() for its complete theory. Add to L0 a new constant e, and add to Th() an axiom schema saying that e is infinite. By the compactness theorem, the resulting theory T has models. However, none of its models are countable. Although this fact is well known, we sketch a proof in order to refer to it later.

By [5, p. 81], there is a family {Aα ∣ < α < c} of infinite subsets of ω, the intersection of any two of which is finite.
The uniform regular set theorem in α-recursion theory
Authors: Maass Wolfgang
Published: May 2006

Several new features arise in the generalization of recursion theory on ω to recursion theory on admissible ordinals α, thus making α-recursion theory an interesting theory. One of these is the appearance of irregular sets. A subset A of α is called regular (over α), if we have for all β < α that A ∩ B ∈ Lα, otherwise A is called irregular (over α). So in the special case of ordinary recursion theory (α = ω) every subset of α is regular, but if α is not a cardinal of L we find constructible sets A ⊆ α which are irregular. The notion of regularity becomes essential, if we deal with α-recursively enumerable (α-r.e.) sets in priority constructions (α-r.e. is defined as Σ1 over Lα). The typical situation occurring there is that an α-r.e. set A is enumerated during some construction in which one tries to satisfy certain requirements. Often this construction succeeds only if we can insure that every initial segment A ∩ β of A is completely enumerated at some stage before α. This calls for making sure that A is regular because due to the admissibility of α an α-r.e. set A is regular iff for every (or equivalently for one) enumeration f of A (f is an enumeration of A iff f: α → A is α-recursive, total, 1-1 and onto) we have that is the image of the set σ under f).
Maximal and Cohesive vector spaces
Authors: Remmel J. B.
Published: May 2006

Let N denote the natural numbers. If A ⊆ N, we write Ā for the complement of A in N. A set A ⊆ N is cohesive if (i) A is infinite and (ii) for any recursively enumerable set W either W ∩ A or ∩ A is finite. A r.e. set M ⊆ N is maximal if is cohesive.

A recursively presented vector space (r.p.v.s.) U over a recursive field F consists of a recursive set U ⊆ N and operations of vector addition and scalar multiplication which are partial recursive and under which U becomes a vector space. A r.p.v.s. U has a dependence algorithm if there is a uniform effective procedure which applied to any n-tuple ν0, ν1, …, νn−1 of elements of U determines whether or not ν0, ν1 …, νn−1 are linearly dependent. Throughout this paper we assume that if U is a r.p.v.s. over a recursive field F then U is infinite dimensional and U = N. If W ⊆ U, then we say W is recursive (r.e., etc.) iff W is a recursive (r.e., etc.) subset of N. If S ⊆ U, we write (S)* for the subspace generated by S. If V1 and V2 are subspaces of U such that V1 ∩ V2 ={} (where is the zero vector of U), then we write V1 ⊕ V2 for (V1 ∪ V2)*. If V1 ⊆ V2⊆U are subspaces, we write V2/V1 for the quotient space.
Monotone inductive definitions over the continuum
Authors: Cenzer Douglas
Published: May 2006

Monotone inductive definitions occur frequently throughout mathematical logic. The set of formulas in a given language and the set of consequences of a given axiom system are examples of (monotone) inductively defined sets. The class of Borel subsets of the continuum can be given by a monotone inductive definition. Kleene's inductive definition of recursion in a higher type functional (see [6]) is fundamental to modern recursion theory; we make use of it in §2.

Inductive definitions over the natural numbers have been studied extensively, beginning with Spector [11]. We list some of the results of that study in §1 for comparison with our new results on inductive definitions over the continuum. Note that for our purposes the continuum is identified with the Baire space ωω.

It is possible to obtain simple inductive definitions over the continuum by introducing real parameters into inductive definitions over N—as in the definition of recursion in [5]. This is itself an interesting concept and is discussed further in [4]. These parametric inductive definitions, however, are in general weaker than the unrestricted set of inductive definitions, as is indicated below.

In this paper we outline, for several classes of monotone inductive definitions over the continuum, solutions to the following characterization problems:

(1) What is the class of sets which may be given by such inductive definitions ?

(2) What is the class of ordinals which are the lengths of such inductive definitions ?

These questions are made more precise below. Most of the results of this paper were announced in [2].
Weak definability in infinitary languages
Authors: Shelah Saharon
Published: May 2006

We shall prove that if a model of cardinality κ can be expanded to a model of a sentence ψ of by adding a suitable predicate in more than κ ways, then, it has a submodel of power μ which can be expanded to a model of ψ in > μ ways provided that λ, κ, μ satisfy suitable conditions.
On an Ackermann-type set theory
Authors: Lake John
Published: May 2006

Ackermann's set theory A* is usually formulated in the first order predicate calculus with identity, ∈ for membership and V, an individual constant, for the class of all sets. We use small Greek letters to represent formulae which do not contain V and large Greek letters to represent any formulae. The axioms of A* are the universal closures of

where all free variables are shown in A4 and z does not occur in the Θ of A2.

A+ is a generalisation of A* which Reinhardt introduced in [3] as an attempt to provide an elaboration of Ackermann's idea of “sharply delimited” collections. The language of A+ is that of A*'s augmented by a new constant V′, and its axioms are A1–A3, A5, V ⊆ V′ and the universal closure of

where all free variables are shown.

Using a schema of indescribability, Reinhardt states in [3] that if ZF + ‘there exists a measurable cardinal’ is consistent then so is A+, and using [4] this result can be improved to a weaker large cardinal axiom. It seemed plausible that A+ was stronger than ZF, but our main result, which is contained in Theorem 5, shows that if ZF is consistent then so is A+, giving an improvement on the above results.
On decomposition of Gödelnumberings into Friedbergnumberings
Authors: Schinzel Britta
Published: May 2006

The category of enumerations over P1 is investigated. Objects are the enumerations of the set of partial recursive functions in one variable φ: N → P1 where φ is a total effective function from the natural numbers N onto P1.

To each a ∈ P1 we call φ−1(a) the set of all indices for a, the fibre over a.

Morphisms from one enumeration φ to another one ψ are (partial) recursive functions f, for which φ(n) = ψ(f(n)) holds for all n where f is denned, i.e. f is fibrepreserving. They are also called translators if f is total. The existence of a translator induces a partial ordering on the enumerations:

Let φ ≤ ψ, iff there exists a translator f with φ = ψ·f; φ ≡ ψ iff φ ≤ ψ and ψ ≤ φ. Two enumerations are called incomparable iff φ ≰,ψ and ψ ≰ φ.

Given a recursively enumerable family of enumerations {φi}i∈ω then their direct sum = π is defined by a bijective recursive pairing function g(i, n) (e.g. g(i, n) = (i + n)(i + n + 1)/2 + i) summing up the φi by φi(n) = = πg(i, n) into π. We also say π decomposes into .

Direct sums satisfy the universal property of sums in categories.

We want to operate decompositiontheory on special kinds of objects in our category, the Gödelnumberings and the Friedbergnumberings.

A Gödelnumbering φ is defined by (a) enumeration theorem (i.e. φ is object of our category) and (b) -theorem, which means that each m + n-place p.r. function can be effectively replaced by an enumeration of n-place p.r. functions given by means of the total -function (see Rogers [3]).
On the complexity of models of arithmetic
Authors: McAloon Kenneth
Published: May 2006

Let P0 be the subsystem of Peano arithmetic obtained by restricting induction to bounded quantifier formulas. Let M be a countable, nonstandard model of P0 whose domain we suppose to be the standard integers. Let T be a recursively enumerable extension of Peano arithmetic all of whose existential consequences are satisfied in the standard model. Then there is an initial segment M′ of M which is a model of T such that the complete diagram of M′ is Turing reducible to the atomic diagram of M. Moreover, neither the addition nor the multiplication of M is recursive.
The equational theory of CA3 is undecidable
Authors: Maddux Roger
Published: May 2006

There is no algorithm for determining whether or not an equation is true in every 3-dimensional cylindric algebra. This theorem completes the solution to the problem of finding those values of α and β for which the equational theories of CAα and RCAβ are undecidable. (CAα and RCAβ are the classes of α-dimensional cylindric algebras and representable β-dimensional cylindric algebras. See [4] for definitions.) This problem was considered in [3]. It was known that RCA0 = CA0 and RCA1 = CA1 and that the equational theories of these classes are decidable. Tarski had shown that the equational theory of relation algebras is undecidable and, by utilizing connections between relation algebras and cylindric algebras, had also shown that the equational theories of CAα and RCAβ are undecidable whenever 4 ≤ α and 3 ≤ β. (Tarski's argument also applies to some varieties K ⊆ RCAβ with 3 ≤ β and to any variety K such that RCAα ⊆ K ⊆ CAα and 4 ≤ α.)

Thus the only cases left open in 1961 were CA2, RCA2 and CA3. Shortly there-after Henkin proved, in one of Tarski's seminars at Berkeley, that the equational theory of CA2 is decidable, and Scott proved that the set of valid sentences in a first-order language with only two variables is recursive [11]. (For a more model-theoretic proof of Scott's theorem see [9].) Scott's result is equivalent to the decidability of the equational theory of RCA2, so the only case left open was CA3.
Degrees of Structures
Authors: Richter Linda Jean
Published: May 2006

Consider those structures that consist of a countable universe and a finite number of predicates and functions. Let = ‹∣∣, P1, …, Pn, f1, …, fm› be such a structure. We will restrict our consideration to structures, , whose universe, ∣∣, is a set of natural numbers, and thus we will be able to apply the notions of recursion theory to structures. Using deg(S) to refer to the degree of unsolvability of a set S, we can assign a degree of unsolvability to the structure by defining deg() to be the least upper bound of the degrees of the universe, predicates, and functions of . If we view as a presentation of the class of all structures which are isomorphic to (in the usual sense), then the deg() can be called the degree of the presentation.

While deg() is a natural degree to assign to the structure , it is not the only possibility. Indeed since a structure may have isomorphic presentations with different degrees, deg() has the deficiency of not being isomorphically invariant. We can assign degrees to some (but not all) structures in an isomorphically invariant fashion by looking at the class of the degrees of all presentations isomorphic to . If this class of degrees has a least element, we define it to be the degree of the isomorphism class of which we write deg([]).
Partial orderings of fixed finite dimension: Model companions and density
Authors: Manaster Alfred B. , Remmel Jeffrey B.
Published: May 2006

The model companions of the theories of n-dimensional partial orderings and n-dimensional distributive lattices are found for each finite n. Each model companion is given as the theory of a structure which is specified. The model companions are model completions only for n = 1. The structure of the model companion of the theory of n-dimensional partial orderings is a lattice only for n = 1. Each of the model companions is seen to be finitely axiomatizable, and a set of basic formulas, each of which is existential, is specified for each model companion. Finally a topolo-gically natural notion of dense n-dimensional partial ordering is introduced and shown to have a finitely axiomatizable undecidable theory.

In this paragraph we shall define the notion of model companion (cf. [4]) and indicate the way in which we shall demonstrate that one theory is the model companion of another in this paper. For T and T* theories in a common language, T* is called a model companion of T if and only if the following two conditions are satisfied: first, Tand T* are mutually model consistent, which means that every model of either is embeddable in some model of the other; secondly, T* is model complete, which means that if and are both models of T* and is a substructure of , then is an elementary substructure of . A definition of model completion may be obtained by strengthening the notion of model companion to also require that T* admit elimination of quantifiers. In all of our examples the model companion will have only one countable model. Although the ℵ0-categoricity of the model companions follows from Saracino [8], we give specific proofs since these proofs fit so naturally in our analyses.
Logic of reduced power structures
Authors: Nelson G.C.
Published: May 2006

We start with the framework upon which this paper is based. The most useful reference for these notions is [2]. For any nonempty index set I and any proper filter D on S(I) (the power set of I), we denote by I/D the reduced power of modulo D as defined in [2, pp. 167–169]. The first-order language associated with I/D will always be the same language as associated with . We denote the 2-element Boolean algebra 〈{0, 1}, ⋂, ⋃, c, 0, 1〉 by 2 and 2I/D denotes the reduced power of it modulo D. We point out the intimate connection between the structures I/D and 2I/D given in [2, pp. 341–345]. Moreover, we assume as known the definition of Horn formula and Horn sentence as given in [2, p. 328] along with the fundamental theorem that φ is a reduced product sentence iff φ is provably equivalent to a Horn sentence [2, Theorem 6.2.5/ (iff φ is a 2-direct product sentence and a reduced power sentence [2, Proposition 6.2.6(ii)]). For a theory T(any set of sentences), ⊨ T denotes that is a model of T.

In addition to the above we assume as known the elementary characteristics (due to Tarski) associated with a complete theory of a Boolean algebra, and we adopt the notation 〈n, p, q〉 of [3], [10], or [6] to denote such an elementary characteristic or the corresponding complete theory. We frequently will use Ershov's theorem which asserts that for each 〈n, p, q〉 there exist an index set I and filter D such that 2I/D ⊨ 〈n, p, q〉 [3] or [2, Lemma 6.3.21].
Decision problem for separated distributive lattices
Authors: Gurevich Yuri
Published: May 2006

It is well known that for all recursively enumerable sets X1, X2 there are disjoint recursively enumerable sets Y1 ⊆ Y2 such that Y ⊆ X1, Y2 ⊆ X2 and Y1, ⋃ Y2 = X1 ⋃ X2. Alistair Lachlan called distributive lattices satisfying this property separated. He proved that the first-order theory of finite separated distributive lattices is decidable. We prove here that the first-order theory of all separated distributive lattices is undecidable.
Precipitous ideals
Authors: Jech T. , Magidor M. , Mitchell W. , Prikry K.
Published: May 2006

The properties of small cardinals such as ℵ1 tend to be much more complex than those of large cardinals, so that properties of ℵ1 may often be better understood by viewing them as large cardinal properties. In this paper we show that the existence of a precipitous ideal on ℵ1 is essentially the same as measurability.

If I is an ideal on P(κ) then R(I) is the notion of forcing whose conditions are sets x ∈ P(κ)/I, with x ≤ x′ if x ⊆ x′. Thus a set D R(I)-generic over the ground model V is an ultrafilter on P(κ) ⋂ V extending the filter dual to I. The ideal I is said to be precipitous if κ ⊨R(I)(Vκ/D is wellfounded).

One example of a precipitous ideal is the ideal dual to a κ-complete ultrafilter U on κ. This example is trivial since the generic ultrafilter D is equal to U and is already in the ground model. A generic set may be viewed as one that can be worked with in the ground model even though it is not actually in the ground model, so we might expect that cardinals such as ℵ1 that cannot be measurable still might have precipitous ideals, and such ideals might correspond closely to measures.