bluuebunny/crossref_metadata_2025_split huggingface dataset:
Characterization of recursively enumerable sets
Authors: Wright Jesse B. 
Published: May 2006

AbstractLet 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.
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

AbstractWe 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 ofwhere 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 ofwhere 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

AbstractLet 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

AbstractIt 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.
On r.e. and co-r.e. vector spaces with nonextendible bases
Authors: Remmel J. 
Published: May 2006

The concern of this paper is with recursively enumerable and co-recursively enumerable subspaces of a recursively presented vector spaceV∞ over a (finite or infinite) recursive field F which is defined in [6] to consist of a recursive subset U of the natural numbers N and operations of vector addition and scalar multiplication which are partial recursive and under which V∞ becomes a vector space. Throughout this paper, we will identify V∞ with N, say via some fixed Gödel numbering, and assume V∞ is infinite dimensional and has a dependence algorithm, i.e., there is a uniform effective procedure which determines whether or not any given n-tuple v0, …, vn−1 from V∞ is linearly dependent. Various properties of V∞ and its sub-spaces have been studied by Dekker [1], Guhl [3], Metakides and Nerode [6], Kalantari and Retzlaff [4], and the author [7].Given a subspace W of V∞, we say W is r.e. (co-r.e.) if W(V∞ − W) is an r.e. subset of N and write dim(V) for the dimension of V. Given subspaces V, W of V∞, V + W will denote the weak sum of V and W and if V ⋂ M = {0} (where 0 is the zero vector of V∞), we write V ⊕ Winstead of V + W. If W ⊇ V, we write Wmod V for the quotient space. An independent set A ⊆ V∞ is extendible if there is an r.e. independent set I ⊇ A such that I − A is infinite and A is nonextendible if it is not the case An is extendible. A r.e. subspace M ⊇ V∞ is maximal if dim(V∞ mod M) = ∞ and for any r.e. subspace W ⊇ Meither dim(W mod M) < ∞ or dim(V∞ mod W) < ∞.
A measure representation theorem for strong partition cardinals
Authors: Kleinberg E. M. 
Published: May 2006

There are two main axiomatic extensions of Zermelo-Fraenkel set theory without the axiom of choice, that associated with the axiom of determinateness, and that associated with infinite exponent partition relations. Initially, the axiom of determinateness, henceforth AD, was the sole tool available. Using it, set theorists in the late 1960s produced many remarkable results in pure set theory (e.g. the measurability of ℵ1) as well as in projective set theory (e.g. reduction principles for ). Infinite exponent partition relations were first studied successfully soon after these early consequences of AD. They too produced measurable cardinals and not only were the constructions here easier than those from AD—the results gave a far clearer picture of the measures involved than had been offered by AD. In general, the techniques offered by infinite exponent partition relations became so attractive that a great deal of the subsequent work from AD involved an initial derivation from AD of the appropriate infinite exponent partition relation and then the derivation from the partition relation of the desired result.Since the early 1970s work on choiceless extensions of ZF + DC has split mainly between AD and its applications to projective set theory, and infinite exponent partition relations and their applications to pure set theory. There has certainly been a fair amount of interplay between the two, but for the most part the theories have been pursued independently.Unlike AD, infinite exponent partition relations have shown themselves amenable to nontrivial forcing arguments. For example, Spector has constructed models for interesting partition relations, consequences of AD, in which AD is false. Thus AD is a strictly stronger assumption than are various infinite exponent partition relations. Furthermore, Woodin has recently proved the consistency of infinite exponent partition relations relative to assumptions consistent with the axiom of choice, in particular, relative to the existence of a supercompact cardinal. The notion of doing this for AD is not even considered.
Model constructions in stationary logic. Part I. Forcing
Authors: Bruce Kim B. 
Published: May 2006

In this series of two papers we wish to discuss two new methods of constructing models for an arbitrary theory T of stationary logic, L(aa). The original work in constructing models for this logic appears in Barwise-Kaufmann-Makkai [BKM] (which we shall refer to as BKM for brevity). In that paper the authors prove completeness, compactness, and omitting types theorems for L(aa) by a technique similar to that used by Keisler [1970] in constructing models of L(Q1), logic with the generalized quantifier “there exist uncountably many”. In this paper we give an alternative method of constructing models using a method of model-theoretic forcing similar to that of Bruce [1978]. In a succeeding paper we will give yet another method of constructing models using definable ultrapowers.As applications of this new forcing construction we give new proofs of the completeness and omitting types theorems for LB(aa), where LB(aa) is any countable fragment of Lω1ω(aa). We also give new proofs of versions of the Barwise completeness and compactness theorems for LA(aa) where A is a countable admissible set. In proofs of these theorems the model constructions via forcing are used in a way very similar to that of consistency properties in Lω1ω.Aside from the ease in handling the model theory of Lω1ω(aa) we see two other advantages in this sort of model construction. The first is in the ability to prove versions of theorems relativized to formulas of low complexity (e.g. relativized omitting types theorems). The second is that we have a high degree of control over the construction of standard models and hence have a better knowledge of the structure of the model (see the remarks following the proof of Lemma 3.3), something that should prove useful in constructing more complicated models.