bluuebunny/crossref_metadata_2025 huggingface dataset:
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.
Some local definability results on countable topological structures
Authors: Eisenmenger Holger
Published: May 2006

L denotes a fixed finitary similarity type, B, respectively P a new relation symbol, an L-structure in the usual sense, and (, σ) a topological L-structure, where σ is a topology on A. (, σ) is countable if is countable and σ has a countable base. The formal language for our study of topological structures is . is the least fragment of the (monadic) second-order, infinitary language closed under negation (⇁), countable disjunction (∨), countable conjunction (∧), quantification over individual variables (∃ν, ∀ν), and quantification over set variables in the form ∃V(t ∈ V → φ) [respectively ∃V(t ∈ V → φ] where t is an L-term and each free occurrence of V in φ is negative [respectively positive]. We abbreviate ∃V(t ∈ V ∧ φ) and ∀V(t ∈ V → φ) by ∃V ∈ ν φ respectively ∀V ∈ ν φ. (For detailed information on we reIer to [1].)

i, j, … m, n range over ω. a, x, etc. denote finite tuples; a ∈ A means that all members of a are in A. IdA denotes the identity on A, Perm(A) the set of all permutations of A, and Aut() (respectively Aut(, σ)) the set of all automorphisms of (respectively (σ)). Let F ⊆ Perm(A), B ⊆ Am(m ≥ 1), and μ be a system of subsets of A. B (respectively μ) is called invariant under F if for all ƒ ∈ F, ƒ(B) = B (respectively ƒ(μ) = μ). denotes the least system of subsets of A which contains μ and which is closed under arbitrary union, .

For the rest of this paragraph let A be a countable nonempty set.
The perfect set theorem and definable wellorderings of the continuum
Authors: Kechris Alexander S.
Published: May 2006

Let Γ be a collection of relations on the reals and let M be a set of reals. We call M a perfect set basis for Γ if every set in Γ with parameters from M which is not totally included in M contains a perfect subset with code in M. A simple elementary proof is given of the following result (assuming mild regularity conditions on Γ and M): If M is a perfect set basis for Γ, the field of every wellordering in Γ is contained in M. An immediate corollary is Mansfield's Theorem that the existence of a Σ21 wellordering of the reals implies that every real is constructible. Other applications and extensions of the main result are also given.
A characterization of companionable, universal theories
Authors: Wheeler William H.
Published: May 2006

A first-order theory is companionable if it is mutually model-consistent with a model-complete theory. The latter theory is then called a model-companion for the former theory. For example, the theory of formally real fields is a companionable theory; its model-companion is the theory of real closed fields. If a companionable, inductive theory has the amalgamation property, then its model-companion is actually a model-completion. For example, the theory of fields is a companionable, inductive theory with the amalgamation property; its model-completion is the theory of algebraically closed fields.

The goal of this paper is the characterization, by “algebraic” or “structural” properties, of the companionable, universal theories which satisfy a certain finiteness condition. A theory is companionable precisely when the theory consisting of its universal consequences is companionable. Both theories have the same model-companion if either has one. Accordingly, nought is lost by the restriction to universal theories. The finiteness condition, finite presentation decompositions, is an analogue for an arbitrary theory of the decomposition of a radical ideal in a Noetherian, commutative ring into a finite intersection of prime ideals for the theory of integral domains. The companionable theories with finite presentation decompositions are characterized by two properties: a coherence property for finitely generated submodels of finitely presented models and a homomorphism lifting property for homomorphisms from submodels of finitely presented models.
On the number of minimal models
Authors: Shelah Saharon
Published: May 2006

Answering a problem of Fuhrken we prove that for every κ, 1 ≤ κ ≤ ℵ0, there is a (countable) complete theory T, with no prime model, and exactly κ minimal models (up to isomorphism).
A continuous functional with noncollapsing hierarchy
Authors: Normann Dag
Published: May 2006

In [5] S. S. Wainer introduces a hierarchy for arbitrary type-2-functionals. Given F, he defines a set of ordinal notations OF, and for each a ∈ OF, a function fa recursive in F and an ordinal ∣a∣F < For any f recursive in F there is an a ∈ OF such that f is primitive recursive in fa.

Let ρF be the least ordinal α such that for any f recursive in F there is an α ∈ OF with ∣a∣F ≤ α such that f is primitive recursive in fa. If ρF < the hierarchy breaks down. In Bergstra and Wainer [2] ρF is described as “the real ordinal of the 1-section of F”.

Using standard methods (originally due to Kleene) one may prove that if F is normal, then ρF = Feferman has proved that if F is recursive, then ρF = ω2.

Let 1-section (F) = l-sc(F) = {f; f is recursive in F} where f is a total object of type 1.

Grilliot [4] proved that F ↾ 1-sc(F) is continuous if and only if F is not normal.

Let h be an associate for a given functional F, and assume that h is recursive in the jump of an element of 1-sc(F).
Uniform upper bounds on ideals of turing degrees
Authors: Hodes Harold T.
Published: May 2006

Given I, a reasonable countable set of Turing degrees, can we find some sort of canonical strict upper bound on I? If I = {a ∣ a ≤ b}, the upper bound on I which springs to mind is b′. But what if I is closed under jump? This question arises naturally out of the question which motivates a large part of hierarchy theory: Is there a canonical increasing function from a countable ordinal, preferably a large one, into D, the set of Turing degrees? If d is to be such a function, it is natural to require that d(α + 1) = d(α)′; but how should d(λ) depend on d ↾ λ, where λ is a limit ordinal?

For any I ⊆ D, let MI, = ⋃I. Towards making the above questions precise, we introduce ideals of Turing degrees.

Definition 1. I ⊆ D is an ideal iff I is closed under jump and join, and I is downward-closed, i.e., if a ≤ b & b ϵ I then a ϵ I.

The following definition reflects the hierarchy-theoretic motivation for this paper.

Definition 2. For I ⊆ D and A ⊆ ω, I is an A-hierarchy ideal iff for some countable ordinal α, MI = Lα[A]∩ ωω.

All hierarchy ideals are ideals, but not conversely.

Early in the game Spector knocked out the best sort of canonicity for upper bounds on ideals, proving that no set of degrees closed under jump has a least upper bound.
On cofinal extensions of models of arithmetic
Authors: Kotlarski Henryk
Published: May 2006

We study cofinal extensions of models of arithmetic, in particular we show that some properties near to expandability are preserved under cofinal extensions.
Compactness of a supervaluational language
Authors: Bencivenga E.
Published: May 2006

Compactness of supervaluational semantics has long been an open problem. Recently, Peter Woodruff [2] showed that the full quantificational language is not compact. In the present note, I will show that the quantifier-free fragment of the language is compact. Since this result can be easily extended to the monadic quantificational language, and since Woodruff's result only requires the presence of one binary predicate, the two results combined give a complete solution of the problem.

My language L contains infinitely many individual constants, infinitely many n-ary predicates (for every n > 0), the usual connectives, the symbols E! and =, and parentheses. (Atomic) sentences are defined as usual, and Ab/a is the result of uniformly substituting b for a in the sentence A.

An interpretation of L is an ordered pair I = 〈D, φ〉, where D is a set (possibly empty) and φ is a unary function, total from the set of n-ary predicates into the power set of Dn, and partial from the set of constants into D.

A classical valuation for an interpretation I = 〈D, φ〉 is a total unary function V from the set of sentences into {T, F} such that

(a) if φ is defined for all of a1, …, am, then V(Pa1 … an) = T iff 〈φ(a1), …, φ(an)〉 ∈ φ(P);

(b) if φ(a) and φ(b) are both defined, then V(a = b) = T iff φ(a) = φ(b;

(c) if exactly one of φ(a) and φ(b) is defined, then V(a = b) = F;

(d) V(a = a) = T;

(e) if V(a = b) = T and A is atomic, then V(A) = V(Ab/a);

(f)V(E!a) = T iff φ(a) is defined;

(g) V(~ A) = T iff V(A) = F, and similarly for the other connectives.
State-strategies for games in Fσδ ∩ Gδσ
Authors: Büchi J. Richard
Published: May 2006

The Cantor-Bendixson theorem says: For every closed set , ∣∣ ≤ ω0 ∨ ⊇ perfect (and therefore is countable or has the power of the continuum). W. H. Young proved the alternative for Gδ-sets, and Hausdorff extended it to Souslin-sets. Cantor used his ordinals to prove the theorem (I like to think he invented them for this purpose). In Hausdorff's Mengenlehre ordinals do not officially enter in either of the three proofs. You should try to put them back. It is very important never to hide away ω1 when it actually is there, and it is there when the continuum problem is the subject.

In Davis [6] you find that Cantor's alternative is equivalent to another alternative: (I wins ) ∨ (J wins ). Here means a lopsided game in which one of the players makes long moves on the game tree. So, the classical theorems can be restated as determinacy results for lopsided games, and now I make this observation: The original CB-proof “actually presents” a winning strategy. The HD-proofs do no such thing; all you know at the end is existence of a winning strategy (and Davis' remark is needed to gain this knowledge).

You understand now why I like CB-proofs, particularly for determinacy of games. They do exist also for games in which both players make short moves. Many years ago I tried to publish such a proof for determinacy of Fσ-games. The referee said it was not worth the trouble. I say you should remake this proof (it is a special case of the one presented in this paper), because it is the ideal of a determinacy proof.
Corrigendum: “Rings which admit elimination of quantifiers”
Authors: Rose Bruce I.
Published: May 2006

Matatyahu Rubin pointed out that the proof of Lemma 6.1 [2] works only for rings of prime or zero characteristic. This invalidates the characterization of semiprime rings with the descending chain condition on right or left ideals which admit elimination of quantifiers given in [2] and cited in the abstract [1]. Although the correct characterization is easy to derive, it is complex to state.

Let be the class of finite fields. Let be the class of 2 × 2 matrix rings over a field with a prime number of elements. Let be the class of rings of the form GF(pn) ⊕ GF(pk) such that either n = k or g.c.d.(n, k) = 1 and p is a prime. Let ′ be the class of algebraically closed fields. Let P denote the set of all prime numbers together with zero. Let be the set of all ordered pairs (f, Q) where Q is a finite subset of P and f: Q → ⋃ ⋃ ⋃ such that the characteristic of the ring f(q) is q. Finally, let be the class of rings of the form ⊕q∈Qf(q) for some (f,Q) in .

A corrected version of Theorem 6.2 [2] is

Theorem 1. Let R be a ring with the descending chain condition on left or right ideals and without nonzero trivial ideals. Then R admits elimination of quantifiers if only if R belong to.
Concerning ultrafilters on ultrapowers
Authors: Henle J. M.
Published: May 2006

This paper concerns ultrafilters on a cardinal γ extending the filter of λ-closed, unbounded sets, λ < γ. The history of these ultrafilters is closely connected with that of the axiom of determinacy (AD). Solovay noticed first that, under AD, there was such an ultrafilter for γ = ℵ1; λ = ω. Later, Kleinberg found that the existence of such ultrafilters followed from the partition relation γ → (γ)λ+λ. Specific instances of this and more powerful relations on cardinals were then proved from AD by Martin, Kunen, Paris, and others. The axiom of determinacy was recently shown consistent with ZF relative to something less than a supercompact cardinal by Martin and Steel. Solovay's and Kleinberg's results were actually stronger, and we discuss this at the end of the paper. Good references for these results include [K2] and [KM].

We are interested here in the case where γ is the ultrapower of a strong partition cardinal κ (a cardinal satisfying for all α < κ). Such cardinals exist in great abundance assuming AD, and in fact, if sufficiently many cardinals are strong, then AD holds in L[R] [KKMW].
A constructive interpretation of the full set theory
Authors: Turchin Valentin F.
Published: May 2006

The interpretation of the ZF set theory reported in this paper is, actually, part of a wider effort, namely, a new approach to the foundation of mathematics, which is referred to as The Cybernetic Foundation. A detailed exposition of the Cybernetic Foundation will be published elsewhere. Our approach leads to a full acceptance of the formalism of the classical set theory, but interprets it using only the idea of potential, but not actual (completed) infinity, and dealing only with finite objects that can actually be constructed. Thus we have a finitist proof of the consistency of ZF. This becomes possible because we set forth a metatheory of mathematics which goes beyond the classical logic and set theory and, of course, cannot be formalized in ZF, yet yields proofs which are as convincing—at least, from the author's viewpoint—as any mathematical proof can be.

Our metatheory is based on the following two ideas. Firstly, we define the semantics of the mathematical language using the cybernetical concept of knowledge. According to this concept, to say that a cybernetic system (a human being, in particular) has some knowledge is to say that it has some models of reality. In the Cybernetic Foundation we consider mathematics as the art of constructing linguistic models of reality.
Saturation of homogeneous resplendent models
Authors: Knight Julia F.
Published: May 2006

The complete diagram of a structure , denoted by Dc(), is the set of all sentences true in the structure (, a)a∈. A structure is said to be resplendent if for every sentence θ involving a new relation symbol R in addition to symbols occurring in Dc(), if θ is consistent with Dc(), then there is a relation P on such that (see[1]).

Baldwin asked whether a homogeneous recursively saturated structure is necessarily resplendent. Here it is shown that this need not be the case. It is shown that if is an uncountable homogeneous resplendent model of an unstable theory, then must be saturated. The proof is related to the proof in [5] that an uncountable homogeneous recursively saturated model of first order Peano arithmetic must be saturated. The example for Baldwin's question is an uncountable homogeneous model for a particular unstable theory, such that is recursively saturated and omits some type. (The continuum hypothesis is needed to show the existence of such a model in power ℵ1.)

The proof of the main result requires two lemmas.
Epistemic set theory is a conservative extension of intuitionistic set theory
Authors: Flagg R. C.
Published: May 2006

In [6] Gödel observed that intuitionistic propositional logic can be interpreted in Lewis's modal logic (S4). The idea behind this interpretation is to regard the modal operator □ as expressing the epistemic notion of “informal provability”. With the work of Shapiro [12], Myhill [10], Goodman [7], [8], and Ščedrov [11] this simple idea has developed into a successful program of integrating classical and intuitionistic mathematics.

There is one question quite central to the above program that has remained open. Namely:

Does Ščedrov's extension of the Gödel translation to set theory provide a faithful interpretation of intuitionistic set theory into epistemic set theory?

In the present paper we give an affirmative answer to this question.

The main ingredient in our proof is the construction of an interpretation of epistemic set theory into intuitionistic set theory which is inverse to the Gödel translation. This is accomplished in two steps. First we observe that Funayama's theorem is constructively provable and apply it to the power set of 1. This provides an embedding of the set of propositions into a complete topological Boolean algebra . Second, in a fashion completely analogous to the construction of Boolean-valued models of classical set theory, we define the -valued universe V(). V() gives a model of epistemic set theory and, since we use a constructive metatheory, this provides an interpretation of epistemic set theory into intuitionistic set theory.
Small filter forcing
Authors: Canjar R. Michael
Published: May 2006

Qλ is the set of nonprincipal filters on ω which are generated by fewer than λ sets, for λ a fixed uncountable, regular cardinal ≤ c. We analyze forcing with Qλ, where Qλ is partially ordered in such a way that a filter F1 is more informative than F2 iff F1 includes F2. Qλ-forcing adjoins an ultrafilter on ω but adds no new reals. We analyze Qλ-forcing from a forcing-theoretic viewpoint. We also analyze the properties of Qλ-generic ultrafilters. These properties are independent of ZFC and depend very much on the ground model. In particular, we study Qλ-forcing over ground models which are Cohen real extensions, random real extensions, and models which satisfy Martin's Axiom.

In §2 we give notations and definitions, and review some of the basic facts about forcing and ultrafilters which we will use. In §3 we introduce Qλ-forcing and prove some basic lemmas about it. §4 studies Qc-forcing. §§5, 6, and 7 analyze Qλ-forcing over ground models of Martin's Axiom, ground models which are generated by Cohen reals, and ground models which are generated by random reals, respectively. Qλ-forcing over Cohen real and random real models is isomorphic to the notion of forcing which adjoins a Cohen generic subset of λ; this is proved in §8.
Lattice embeddings into the recursively enumerable degrees
Authors: Ambos-Spies K. , Lerman M.
Published: May 2006

The classification of algebraic structures which can be embedded into ℛ, the uppersemilattice of recursively enumerable degrees, is the key to answering certain questions about Th(ℛ), the elementary theory of ℛ. In particular, these classification problems are important for answering decidability questions about fragments of Th(ℛ). Thus the solutions of Fried berg [F] and Mučnik [M] to Post's problem were easily extended to show that all finite partially ordered sets are embeddable into ℛ, and hence that ∃1 ∩ Th(ℛ), the existential theory of ℛ, is decidable. (The language used is ℒ′, the pure predicate calculus together with a binary relation symbol ≤ to be interpreted as the ordering of ℛ) The problem of determining which finite lattices are embeddable into ℛ has been a long-standing open problem, and is one of the major obstacles to determining whether ∀2 ∩ Th(ℛ), the universal-existential theory of ℛ, is decidable. Shore has obtained some nice partial results in this direction. Embeddings also played a central role in showing that Th(ℛ) is not ℵ0-categorical (Lerman, Shore and Soare [LeShSo]), thus resolving a problem posed by Jockusch. Harrington and Shelah [HS] embedded all 0′-presentable partially ordered sets into ℛ in such a way that the partially ordered sets can be uniformly recovered from four parameters. They used these embeddings to show that Th(ℛ) is undecidable.

The first nontrivial extension of the embeddings of Friedberg and Mučnik to lattice embeddings was obtained independently by Lachlan [La1] and Yates [Y] who showed that the four-element Boolean algebra can be embedded into ℛ. Thomason [T] and Lerman independently extended this result to include all finite distributive lattices. The nondistributive case, however, was much more difficult. Lachlan [La2] embedded the two five-element nondistributive lattices M5 and N5 (see Figures 1 and 2) into ℛ, and his proof could easily have been extended to include a larger class of lattices.
Natural deduction based set theories: a new resolution of the old paradoxes
Authors: Gilmore Paul C.
Published: May 2006

The comprehension principle of set theory asserts that a set can be formed from the objects satisfying any given property. The principle leads to immediate contradictions if it is formalized as an axiom scheme within classical first order logic. A resolution of the set paradoxes results if the principle is formalized instead as two rules of deduction in a natural deduction presentation of logic. This presentation of the comprehension principle for sets as semantic rules, instead of as a comprehension axiom scheme, can be viewed as an extension of classical logic, in contrast to the assertion of extra-logical axioms expressing truths about a pre-existing or constructed universe of sets. The paradoxes are disarmed in the extended classical semantics because truth values are only assigned to those sentences that can be grounded in atomic sentences.
An interpolation theorem in many-valued logic
Authors: Hanazawa Masazumi , Takano Mitio
Published: May 2006

A many-valued logic version of the Craig-Lyndon interpolation theorem has been given by Gill [1] and Miyama [2]. The former dealt with three-valued logic and the latter generalized it to M-valued logic with M ≥ 3. The purpose of this paper is to improve the form of Miyama's version of the interpolation theorem. The system used in this paper is a many-valued analogue (Takahashi [4], Rousseau [3]) of Gentzen's logical calculus LK. Let T = {1,…, M} be the set of truth values. An M-tuple (Γ1,…, ΓM) of sets of formulas is called a sequent, which is regarded as valid if for any valuation (in canonical sense) there is a truth value μ Є T such that the set Γμ contains a formula of the value μ with respect to the valuation. (In the next section, and thereafter, we change the format of the sequent for typographical reasons.) Miyama's result is as follows (in representative form):

(I) If a sequent ({A}, ∅,…, ∅, {B}) is valid, then there is a formula D such that

(i) every predicate or propositional variable occurring in D occurs in A and B, and

(ii) the sequents {{A}, ∅,…, ∅, {D}) and (D}, ∅,…, ∅, {B}) are both valid.

What shall be proved in this paper is the following (in representative form):

(II) If a sequent ({A1}, {A2}, …, {AM}) is valid, then there is a formula D such that

(i) every predicate or propositional variable occurring in D occurs in at least two of the formulas A1,…, AM, and

(ii) the following M sequents are valid:

({A1},{D},…,{D}),({D},{A2},…,{D}),…,({D},{D},…,{AM}).

Clearly the former can be obtained as a corollary of the latter.
Stepping up lemmas in definable partitions
Authors: Kranakis Evangelos
Published: May 2006

Several stepping up lemmas are proved which are then used to investigate the connection between definable partition relations and admissible ordinals.
On nonstandard models in higher order logic
Authors: Hort Christian , Osswald Horst
Published: May 2006

There are two concepts of standard/nonstandard models in simple type theory.

The first concept—we might call it the pragmatical one—interprets type theory as a first order logic with countably many sorts of variables: the variables for the urelements of type 0,…, the n-ary relational variables of type (τ1, …, τn) with arguments of type (τ1,…,τn), respectively. If A ≠ ∅ then 〈Aτ〉 is called a model of type logic, if A0 = A and . 〈Aτ〉 is called full if, for every τ = (τ1,…,τn), . The variables for the urelements range over the elements of A and the variables of type (τ1,…, τn) range over those subsets of which are elements of . The theory Th(〈Aτ〉) is the set of all closed formulas in the language which hold in 〈Aτ〉 under natural interpretation of the constants. If 〈Bτ〉 is a model of Th(〈Aτ〉), then there exists a sequence 〈fτ〉 of functions fτ: Aτ → Bτ such that 〈fτ〉 is an elementary embedding from 〈Aτ〉 into 〈Bτ〉. 〈Bτ〉 is called a nonstandard model of 〈Aτ〉, if f0 is not surjective. Otherwise 〈Bτ〉 is called a standard model of 〈Aτ〉.

This first concept of model theory in type logic seems to be preferable for applications in model theory, for example in nonstandard analysis, since all nice properties of first order model theory (completeness, compactness, and so on) are preserved.
Two theorems on degrees of models of true arithmetic
Authors: Knight Julia , Lachlan Alistair H. , Soare Robert I.
Published: May 2006

Let PA be the theory of first order Peano arithmetic, in the language L with binary operation symbols + and ·. Let N be the theory of the standard model of PA. We consider countable models M of PA such that the universe ∣M∣ is ω. The degree of such a model M, denoted by deg(M), is the (Turing) degree of the atomic diagram of M. The results of this paper concern the degrees of models of N, but here in the Introduction, we shall give a brief survey of results about degrees of models of PA.

Let D0 denote the set of degrees d such that there is a nonstandard model of M of PA with deg(M) = d. Here are some of the more easily stated results about D0.

(1) There is no recursive nonstandard model of PA; i.e., 0 ∈ D0.

This is a result of Tennenbaum [T].

(2) There existsd ∈ D0such thatd ≤ 0′.

This follows from the standard Henkin argument.

(3) There existsd ∈ D0such thatd < 0′.

Shoenfield [Sh1] proved this, using the Kreisel-Shoenfield basis theorem.

(4) There existsd ∈ D0such thatd′ = 0′.

Jockusch and Soare [JS] improved the Kreisel-Shoenfield basis theorem and obtained (4).

(5) D0 = Dc = De, where Dc denotes the set of degrees of completions of PA and De the set of degrees d such that d separates a pair of effectively inseparable r.e. sets.

Solovay noted (5) in a letter to Soare in which in answer to a question posed in [JS] he showed that Dc is upward closed.
The definability of E(α)
Authors: Griffor E. R. , Normann D.
Published: May 2006

The question of the limits of recursive enumerability was first formulated by Sacks (1980) and investigated further in Sacks (198?). E-recursion or “set recursion”, as a natural generalization of Kleene recursion in normal objects of finite type, was introduced by Normann (1978) in order to facilitate the study of the degrees of functionals. We shall extend the work of Sacks on the question of how definable is the E-closure of an ordinal α (written E(α)). We write gc(κ) to denote the largest τ < κ such that Lκ ⊨ “τ is a cardinal” and cf (τ) for τ ∈ ON to denote the cofinality of τ.

In §1 we give the basic definitions and state the results of Silver and Friedman (1980) used by Sacks to show that if E(α) = Lκ and is not Σ1-admissible and

then P(gc(κ)) ∩ Lκ is indexical on Lκ and hence RE. We show in this case first that P(gc(κ)) ∩ Lκ indexical implies that Lκ is indexical (and hence RE).

In §2 we introduce the notion of a “nonstandard stage comparison” and use it to extend the definability result of §1 to show that this Lκ is in fact REC. Finally we remark that E(α) is indexical if and only if E(α) is RE.
Algebraic theories with definable Skolem functions
Authors: van den Dries Lou
Published: May 2006

(1.1) A well-known example of a theory with built-in Skolem functions is (first-order) Peano arithmetic (or rather a certain definitional extension of it). See [C-K, pp. 143, 162] for the notion of a theory with built-in Skolem functions, and for a treatment of the example just mentioned. This property of Peano arithmetic obviously comes from the fact that in each nonempty definable subset of a model we can definably choose an element, namely, its least member.

(1.2) Consider now a real closed field R and a nonempty subset D of R which is definable (with parameters) in R. Again we can definably choose an element of D, as follows: D is a union of finitely many singletons and intervals (a, b) where – ∞ ≤ a < b ≤ + ∞; if D has a least element we choose that element; if not, D contains an interval (a, b) for which a ∈ R ∪ { − ∞}is minimal; for this a we choose b ∈ R ∪ {∞} maximal such that (a, b) ⊂ D. Four cases have to be distinguished:

(i) a = − ∞ and b = + ∞; then we choose 0;

(ii) a = − ∞ and b ∈ R; then we choose b − 1;

(iii) a ∈ R and b ∈ = + ∞; then we choose a + 1;

(iv) a ∈ R and b ∈ R; then we choose the midpoint (a + b)/2.

It follows as in the case of Peano arithmetic that the theory RCF of real closed fields has a definitional extension with built-in Skolem functions.
On the structure of Ext(A,Z) in ZFC+
Authors: Sageev G. , Shelah S.
Published: May 2006

A fundamental problem in the theory of abelian groups is to determine the structure of Ext(A, Z) for arbitrary abelian groups A. This problem was raised by L. Fuchs in 1958, and since then has been the center of considerable activity and progress.

We briefly summarize the present state of this problem. It is a well-known fact that

where tA denotes the torsion subgroup of A. Thus the structure problem for Ext(A, Z) breakdown to the two distinct cases, torsion and torsion free groups. For a torsion group T,

which is compact and reduced, and its structure is known explicitly [12].

For torsion free A, Ext(A, Z) is divisible; hence it has a unique representation

Thus Ext(A, Z) is characterized by countably many cardinal numbers, which we denote as follows: ν0(A) is the rank of the torsion free part of Ext(A, Z), and νp(A) are the ranks of the p-primary parts of Ext(A, Z), Extp(A, Z).

If A is free it is an elementary fact that Ext(A, Z) = 0. The second named author has shown [16] that in the presence of V = L the converse is also true. For countable torsion free, nonfree A, C. Jensen [13] has shown that νp(A) is either finite or and νp(A) ≤ ν0(A). Therefore, the case for uncountable, nonfree, torsion free groups A remains to be studied.
Cuts, consistency statements and interpretations
Authors: Pudlák Pavel
Published: May 2006

Interpretability in reflexive theories, especially in PA, has been studied in many papers; see e.g. [3], [6], [7], [10], [11], [15], [26]. It has been shown that reflexive theories exhibit many nice properties, e.g. (1) if T, S are recursively enumerable reflexive, then T is interpretable in S iff every Π1 sentence provable in T is provable in S; and (2) if S is reflexive, T is recursively enumerable and locally interpretable in S (i.e. every finite part of T is interpretable in S), then T is globally interpretable in S (Orey's theorem, cf. [3]).

In this paper we want to study such statements for nonreflexive theories, especially for finitely axiomatizable theories (which are never reflexive). These theories behave differently, although they may be quite close to reflexive theories, as e.g. GB to ZF. An important fact is that in such theories one can define proper cuts. By a cut we mean a formula with one free variable which defines a nonempty initial segment of natural numbers closed under the successor function. The importance of cuts for interpretations in GB was realized already by Vopěnka and Hájek in [30]. Pioneering work was done by Solovay in [24]. There he developed the method of “shortening of cuts”. Using this method it is possible to replace any cut by a cut which is contained in it and has some desirable additional properties; in particular it can be closed under + and ·. This introduces ambiguity in the concept of arithmetic in theories which admit proper cuts, namely, which cut (closed under + and ·) should be called the arithmetic of the theory? Cuts played the crucial role also in [20].
Weakly compact cardinals in models of set theory
Authors: Enayat Ali
Published: May 2006

The central notion of this paper is that of a κ-elementary end extension of a model of set theory. A model is said to be a κ-elementary end extension of a model of set theory if > and κ, which is a cardinal of , is end extended in the passage from to , i.e., enlarges κ without enlarging any of its members (see §0 for more detail). This notion was implicitly introduced by Scott in [Sco] and further studied by Keisler and Morley in [KM], Hutchinson in [H] and recently by the author in [E]. It is not hard to see that if has a κ-elementary end extension then κ must be regular in . Keisler and Morley [KM] noticed that this has a converse if is countable, i.e., if κ is a regular cardinal of a countable model then has a κ-elementary end extension. Later Hutchinson [H] refined this result by constructing κ-elementary end extensions 1 and 2 of an arbitrary countable model in which κ is a regular uncountable cardinal, such that 1 adds a least new element to κ while 2 adds no least new ordinal to κ. It is a folklore fact of model theory that the Keisler-Morley result gives soft and short proofs of countable compactness and abstract completeness (i.e. recursive enumera-bility of validities) of the logic L(Q), studied extensively in Keisler's [K2]; and Hutchinson's refinement does the same for stationary logic L(aa), studied by Barwise et al. in [BKM]. The proof of Keisler-Morley and that of Hutchinson make essential use of the countability of since they both rely on the Henkin-Orey omitting types theorem. As pointed out in [E, Theorem 2.12], one can prove these theorems using “generic” ultrapowers just utilizing the assumption of countability of the -power set of κ. The following result, appearing as Theorem 2.14 in [E], links the notion of κ-elementary end extension to that of measurability of κ. The proof using (b) is due to Matti Rubin.
Decidable properties of finite sets of equations in trivial languages
Authors: Kalfa Cornelia
Published: May 2006

In [4] I proved that in any nontrivial algebraic language there are no algorithms which enable us to decide whether a given finite set of equations Σ has each of the following properties except P2 (for which the problem is open):

P0(Σ) = the equational theory of Σ is equationally complete.

P1(Σ) = the first-order theory of Σ is complete.

P2(Σ) = the first-order theory of Σ is model-complete.

P3(Σ) = the first-order theory of the infinite models of Σ is complete.

P4(Σ) = the first-order theory of the infinite models of Σ is model-complete.

P5(Σ) = Σ has the joint embedding property.

In this paper I prove that, in any finite trivial algebraic language, such algorithms exist for all the above Pi's. I make use of Ehrenfeucht's result [2]: The first-order theory generated by the logical axioms of any trivial algebraic language is decidable. The results proved here are part of my Ph.D. thesis [3]. I thank Wilfrid Hodges, who supervised it.

Throughout the paper is a finite trivial algebraic language, i.e. a first-order language with equality, with one operation symbol f of rank 1 and at most finitely many constant symbols.
Well-behaved modal logics
Authors: Hodes Harold T.
Published: May 2006

Much of the literature on the model theory of modal logics suffers from two weaknesses. Firstly, there is a lack of generality; theorems are proved piecemeal about this or that modal logic, or at best small classes of logics. Much of the literature, e.g. [1], [2], and [3], confines attention to structures with the expanding domain property (i.e., if wRu then Ā(w) ⊆ Ā(u)); the syntactic counterpart of this restriction is assumption of the converse Barcan scheme, a move which offers (in Russell's phrase) “all the advantages of theft over honest toil”. Secondly, I think there has been a failure to hit on the best ways of extending classical model theoretic notions to modal contexts. This weakness makes the literature boring, since a large part of the interest of modal model theory resides in the way in which classical model theoretic notions extend, and in some cases divide, in the modal setting. (The relation between α-recursion theory and classical recursion theory is analogous to that between modal model theory and classical model theory. Much of the work in α-recursion theory involved finding the right definitions (e.g., of recursive-in) and separating concepts which collapse in the classical case (e.g. of finiteness and boundedness).)

The notion of a well-behaved modal logic is introduced in §3 to make possible rather general results; of course our attention will not be restricted to structures with the expanding domain property. Rather than prove piecemeal that familiar modal logics are well-behaved, in §4 we shall consider a class of “special” modal logics, which obviously includes many familiar logics and which is included in the class of well-behaved modal logics.
Priority arguments in the continuous r.e. degrees
Authors: Thompson Simon
Published: May 2006

We show that at each type κ ≥ 2, there exist c-irreducible functionals of c-r.e. degree, as defined in [Nor 1]. Our proofs are based on arguments due to Hinman, [Hin 1], and Dvornikov, [Dvo 1].
Monadic binary relations and the monad systems at near-standard points
Authors: Vakil Nader
Published: May 2006

Let (*X, *T) be the nonstandard extension of a Hausdorff space (X, T). After Wattenberg [6], the monad m(x) of a near-standard point x in *X is defined as m{x) = μT(st(x)). Consider the relation

Frank Wattenberg in [6] and [7] investigated the possibilities of extending the domain of Rns to the whole of *X. Wattenberg's extensions of Rns were required to be equivalence relations, among other things. Because the nontrivial ways of constructing such extensions usually produce monadic relations, the said condition practically limits (to completely regular spaces) the class of spaces for which such extensions are possible. Since symmetry and transitivity are not, after all, characteristics of the kind of nearness that is obtained in a general topological space, it may be expected that if these two requirements are relaxed, then a monadic extension of Rns to *X should be possible in any topological space. A study of such extensions of Rns is the purpose of the present paper. We call a binary relation W ⊆ *X × *X an infinitesimal on *X if it is monadic and reflexive on *X. We prove, among other things, that the existence of an infinitesimal on *X that extends Rns is equivalent to the condition that the space (X, T) be regular.
Modal sequents and definability
Authors: Kapron Bruce M.
Published: May 2006

The language of propositional modal logic is extended by the introduction of sequents. Validity of a modal sequent on a frame is defined, and modal sequent-axiomatic classes of frames are introduced. Through the use of modal algebras and general frames, a study of the properties of such classes is begun.
On partitions of the real line into compact sets
Authors: Newelski Ludomir
Published: May 2006

The problem mentioned in the title has already been investigated by J. Baumgartner, J. Stern, A. Miller and many others (see [2] and [5]). We prove here some generalizations of theorems of Miller and Stern from [2] and [5]. We use standard set-theoretical notation. Let

One can check that in the above definition we can replace “compact subset of ωω” by “closed nowhere dense subset of ω2” or “Fσ and meager subset of ω2” (as any Fσ subset of ω2 can be presented as a disjoint countable union of compact sets).

For functions f, g ϵ ωω we define f ≼ g if for all but finitely many n ϵ ω we have f(n) ≤ g(n). Let denote the least cardinality of a family A ⊆ ωω such that for any f ϵ ωω there is g ϵ A for which f ≼ g. It is easy to see that ≤ κω ≤ κ1. If f ϵ ωω then let ≼(f) = {h ϵωω: h ≼ f}.

We find an axiom which implies = ω1 → κ1 = ω1, and which can be preserved by any ccc notion of forcing of “small cardinality”. We construct also in a generic model many partitions of ωω into compact sets preserved not only by any random real extension, but also by Sacks' notion of forcing. This shows that from some point of view Miller's modification of Sacks' forcing (from [2]) is the “minimal” one able to destroy a partition of ωω into compact sets.
A hierarchy of filters on regular uncountable cardinals
Authors: Jech Thomas
Published: May 2006

We introduce a well-founded relation < between filters on the space of descending sequences of ordinals. For each regular uncountable cardinal κ, the length of the relation is an ordinal o(κ) ≤ (2κ)+.
Systematization of finite many-valued logics through the method of tableaux
Authors: Carnielli Walter A.
Published: May 2006

This paper presents a unified treatment of the propositional and first-order many-valued logics through the method of tableaux. It is shown that several important results on the proof theory and model theory of those logics can be obtained in a general way.

We obtain, in this direction, abstract versions of the completeness theorem, model existence theorem (using a generalization of the classical analytic consistency properties), compactness theorem and Löwenheim-Skolem theorem.

The paper is completely self-contained and includes examples of application to particular many-valued formal systems.
Definability in reducts of algebraically closed fields
Authors: Martin Gary A.
Published: May 2006

LetKbe an algebraically closed field and letLbe itscanonical language; that is,Lconsists of all relations onKwhich are definable from addition, multiplication, and parameters fromK. Two sublanguagesL1andL2ofLaredefinably equivalentif each relation inL1can be defined by anL2-formula with parameters inK, and vice versa. The equivalence classes of sublanguages ofLform a quotient lattice of the power set ofLabout which very little is known. We will not distinguish between a sublanguage and its equivalence class.

LetLmdenote the language of multiplication alone, and letLadenote the language of addition alone. Letf∈K[X, Y] and consider thealgebraic functiondefined byf(x, y) = 0 forx, y∈K. LetLfdenote the language consisting of the relation defined byf. The possibilities forLm∨Lfare examined in §2, and the possibilities forLa∨Lfare examined in §3. In fact the only comprehensive results known are under the additional hypothesis thatfactually defines a rational function (i.e., whenfis linear in one of the variables), and in positive characteristic, only expansions of addition by polynomials (i.e., whenfis linear and monic in one of the variables) are understood. It is hoped that these hypotheses will turn out to be unnecessary, so that reasonable generalizations of the theorems described below to algebraic functions will be true. The conjecture is thatLcoversLmand that the only languages betweenLaandLare expansions ofLaby scalar multiplications.
Decidable fragments of field theories
Authors: Tung Shih-Ping
Published: May 2006

We say φ is an ∀∃ sentence if and only if φ is logically equivalent to a sentence of the form ∀x∃yψ(x, y), where ψ(x, y) is a quantifier-free formula containing no variables except x and y. In this paper we show that there are algorithms to decide whether or not a given ∀∃ sentence is true in (1) an algebraic number field K, (2) a purely transcendental extension of an algebraic number field K, (3) every field with characteristic 0, (4) every algebraic number field, (5) every cyclic (abelian, radical) extension field over Q, and (6) every field.