bluuebunny/crossref_metadata_2025 huggingface dataset:
The undecidability of intuitionistic theories of algebraically closed fields and real closed fields
Authors: Gabbay Dov M.
Published: May 2006

Let T be a set of axioms for a classical theory TC (e.g. abelian groups, linear order, unary function, algebraically closed fields, etc.). Suppose we regard T as a set of axioms for an intuitionistic theory TH (more precisely, we regard T as axioms in Heyting's predicate calculus HPC).

Question. Is TH decidable (or, more generally, if X is any intermediate logic, is TX decidable)? In [1] we gave sufficient conditions for the undecidability of TH. These conditions depend on the formulas of T (different axiomatization of the same TC may give rise to different TH) and on the classical model theoretic properties of TC (the method did not work for model complete theories, e.g. those of the title of the paper). For details see [1]. In [2] we gave some decidability results for some theories: The problem of the decidability of theories TH for a classically model complete TC remained open. An undecidability result in this direction, for dense linear order was obtained by Smorynski [4]. The cases of algebraically closed fields and real closed fields and divisible abelian groups are treated in this paper. Other various decidability results of the intuitionistic theories were obtained by several authors, see [1], [2], [4] for details.

One more remark before we start. There are several possible formulations for an intuitionistic theory of, e.g. fields, that correspond to several possible axiomatizations of the classical theory. Other formulations may be given in terms of the apartness relation, such as the one for fields given by Heyting [5]. The formulations that we consider here are of interest as these systems occur in intuitionistic mathematics. We hope that the present methods could be extended to the (more interesting) case of Heyting's systems [5].
Elementary intuitionistic theories
Authors: Smorynski C.
Published: May 2006

The present paper concerns itself primarily with the decision problem for formal elementary intuitionistic theories and the method is primarily model-theoretic. The chief tool is the Kripke model for which the reader may find sufficient background in Fitting's book Intuitionistic logic model theory and forcing (North-Holland, Amsterdam, 1969). Our notation is basically that of Fitting, the differences being to favor more standard notations in various places.

The author owes a great debt to many people and would particularly like to thank S. Feferman, D. Gabbay, W. Howard, G. Kreisel, G. Mints, and R. Statman for their valuable assistance.

The method of elimination of quantifiers, which has long since proven its use in classical logic, has also been applied to intuitionistic theories (i) to demonstrate decidability ([9], [15], [17]), (ii) to prove the coincidence of an intuitionistic theory with its classical extension ([9], [17]), and (iii), as we will see below, to establish relations between an intuitionistic theory and its classical extension. The most general of these results is to be obtained from the method of Lifshits' quantifier elimination for the intuitionistic theory of decidable equality.

Since the details of Lifshits' proof have not been published, and since the proof yields a more general result than that stated in his abstract [15], we include the proof and several corollaries.
On axiomatizing fragments
Authors: Smorynski C.
Published: May 2006

The main purpose of this note is to present new semi-model-theoretic proofs of some axiomatization results. Principally, we prove the result of [van Dalen and Statman] on the axiomatization of the equality fragment of the intuitionistic theory of apartness by ω-fold stability axioms. Further examples are also discussed.

The intuitionistic theories of equality and apartness are given by the following nonlogical axioms:

EQ .

AP .

In AP, one can define a notion of equality by means of the abbreviation:

.

The corresponding interpretation of E Q in AP is not faithful — since equality is a negation, we have stability of equality:

.

The equality fragment of AP is axiomatized by a suitable generalization of the stability of equality. To state it, one first defines a sequence of partial apartness relations:

.

A simple induction shows, for all n,

whence

.
The inadequacy of the neighbourhood semantics for modal logic
Authors: Gerson Martin
Published: May 2006

We present two finitely axiomatized modal propositional logics, one betweenTandS4 and the other an extension ofS4, which are incomplete with respect to the neighbourhood or Scott-Montague semantics.

Throughout this paper we are referring to logics which contain all the classical connectives and only one modal connective □ (unary), no propositional constants, all classical tautologies, and which are closed under the rules of modus ponens (MP), substitution, and the rule RE (fromA↔Binfer αA↔ □B). Such logics are calledclassicalby Segerberg [6]. Classical logics which contain the formula □p∧ □q→ □(p∧q) (denoted byK) and its “converse,” □{p∧q)→ □p∧ □q(denoted byR) are called regular;regularlogics which are closed under the rule of necessitation, RN (fromAinfer □A), are callednormal. The logics that we are particularly concerned with are all normal, although some of our results will be true for all regular or all classical logics. It is well known thatKandRand closure under RN imply closure under RE and also that normal logics are also those logics closed under RN and containing □{p→q) → {□p→ □q).
On spectra, and the negative solution of the decision problem for identities having a finite nontrivial model
Authors: Mckenzie Ralph
Published: May 2006

An algorithm has been described by S. Burris [3] which decides if a finite set of identities, whose function symbols are of rank at most 1, has a finite, nontrivial model. (By “nontrivial” it is meant that the universe of the model has at least two elements.) As a consequence of some results announced in the abstracts [2] and [8], it is clear that if the restriction on the ranks of function symbols is relaxed somewhat, then this finite model problem is no longer solvable by an algorithm, or at least not by a “recursive algorithm” as the term is used today.

In this paper we prove a sharp form of this negative result; showing, by the way, that Burris' result is in a sense the best possible result in the positive direction. Our main result is that in a first order language whose only function or relation symbol is a 2-place function symbol (the language of groupoids), the set of identities that have no nontrivial model, is recursively inseparable from the set of identities such that the sentence has a finite model. As a corollary, we have that each of the following problems, restricted to sentences defined in the language of groupoids, is algorithmically unsolvable: (1) to decide if an identity has a finite nontrivial model; (2) to decide if an identity has a nontrivial model; (3) to decide if a universal sentence has a finite model; (4) to decide if a universal sentence has a model. We note that the undecidability of (2) was proved earlier by McNulty [13, Theorem 3.6(i)], improving results obtained by Murskiǐ [14] and by Perkins [17]. The other parts of the corollary seem to be new.
Extending Gödel's negative interpretation to ZF
Authors: Powell William C.
Published: May 2006

In [5] Gödel interpreted Peano arithmetic in Heyting arithmetic. In [8, p. 153], and [7, p. 344, (iii)], Kreisel observed that Gödel's interpretation extended to second order arithmetic. In [11] (see [4, p. 92] for a correction) and [10] Myhill extended the interpretation to type theory. We will show that Gödel's negative interpretation can be extended to Zermelo-Fraenkel set theory. We consider a set theory T formulated in the minimal predicate calculus, which in the presence of the full law of excluded middle is the same as the classical theory of Zermelo and Fraenkel. Then, following Myhill, we define an inner model S in which the axioms of Zermelo-Fraenkel set theory are true.

More generally we show that any class X that is (i) transitive in the negative sense, ∀x ∈ X∀y ∈ x ¬ ¬ x ∈ X, (ii) contained in the class St = {x: ∀u(¬ ¬ u ∈ x→ u ∈ x)} of stable sets, and (iii) closed in the sense that ∀x(x ⊆ X ∼ ∼ x ∈ X), is a standard model of Zermelo-Fraenkel set theory. The class S is simply the ⊆-least such class, and, hence, could be defined by S = ⋂{X: ∀x(x ⊆ ∼ ∼ X→ ∼ ∼ x ∈ X)}. However, since we can only conservatively extend T to a class theory with

Δ01-comprehension, but not with Δ11-comprehension, we will give a Δ01-definition of S within T.
On the inconsistency of systems similar to
Authors: Bunder M. W. , Meyer R. K.
Published: May 2006

This note shows that the inconsistency proof of the system of illative combinatory logic given in [1] can be simplified as well as extended to the absolute inconsistency of a more general system.

One extension of the result in [1] lies in the fact that the following weakened form of the deduction theorem for implication will lead to the inconsistency:

Also the inconsistency follows almost as easily for

as it does for ⊢ H2X for arbitrary X, so we will consider the more general case.

The only properties we require other than (DT), (1) and Rule Eq for equality are modus ponens,

and

Let G = [x] Hn−1x⊃: . … H2x⊃ :Hx⊃ . x ⊃ A, where A is arbitrary. Then if Y is the paradoxical combinator and X = YG, X = GX.

Now X ⊂ X, i.e.,
Theories with models of prescribed cardinalities
Authors: Mekler Alan
Published: May 2006

The Löwenheim–Skolem theorem states that if a theory has an infinite model it has models of all cardinalities greater than or equal to the cardinality of the language in which the theory is defined. A natural question is what happens if there is a model whose cardinality is less than that of the language.

If κ is an infinite cardinal less than the first measurable cardinal and κ < κω, the Rabin–Keiler theorem [1, p. 139] gives an example of a theory which has a model of cardinality κ in which every element is the interpretation of a constant and all other models have cardinality μ ≥ κω. Keisler has also shown that if a theory has a model of cardinality κ it has models of all cardinalities μ ≥ κω. We will show that within the bounds of the above theorems anything can happen.

The main result is as follows.
Categories of frames for modal logic
Authors: Thomason S. K.
Published: May 2006

§1. A complete atomic modal algebra (CAMA) is a complete atomic Boolean algebra with an additional completely additive unary operator. A (Kripke) frame is just a binary relation on a nonempty set. If is a frame, then is a CAMA, where mX = {y ∣ (∃x)(y < x Є X)}; and if is a CAMA then is a frame, where is the set of atoms of and b1 < b2 ⇔ b1 ∩ mb2 ≠∅.

Now , and the validity of a modal formula on is equivalent to the satisfaction of a modal algebra polynomial identity by and conversely, so the validity-preserving constructions on frames ought to be in some sense equivalent to the identity-preserving constructions on CAMA's. The former are important for modal logic, and many of the results of universal algebra apply to the latter, so it is worthwhile to fix precisely the sense of the equivalence.

The most important identity-preserving constructions on CAMA's can be described in terms of homomorphisms and complete homomorphisms. Let and be the categories of CAMA's with homomorphisms and complete homomorphisms, respectively. We shall define categories and of frames with appropriate morphisms, and show them to be dual respectively to and . Then we shall consider certain identity-preserving constructions on CAMA's and attempt to describe the corresponding validity-preserving constructions on frames.

The proofs of duality involve some rather detailed calculations, which have been omitted. All the category theory a reader needs to know is in the first twenty pages of [7].
λ-scales, κ-Souslin sets and a new definition of analytic sets
Authors: Busch Douglas R.
Published: May 2006

The notions of sets of reals being κ-Souslin (κ a cardinal) and admitting a λ-scale (λ an ordinal) are due respectively to D. A. Martin and Y.N. Moschovakis. A set is ω-Souslin if and only if it is Σ11 (analytic). We show that a set is ω-Souslin if and only if it admits an (ω + l)-scale. Jointly with Martin and Solovay we show that if κ is uncountable and has cofinality ω, then being κ-Souslin is equivalent to admitting a κ-scale. Our results together with those of Kechris give a new simultaneous characterization of Σ11 and Δ11 (Borel) sets (a set is Σ11 if it admits an (ω + 1)-scale and Δ11 if it admits an ω-scale) and determine completely the relation between the κ-Souslin sets and the sets admitting λ-scales.
On partitions into stationary sets
Authors: Prikry Karel , Solovay Robert M.
Published: May 2006

We shall apply some of the results of Jensen [4] to deduce new combinatorial consequences of the axiom of constructibility, V = L. We shall show, among other things, that if V = L then for each cardinal λ there is a set A ⊆ λ such that neither A nor λ – A contain a closed set of type ω1. This is an extension of a result of Silver who proved it for λ = ω2, providing a partial answer to Problem 68 of Friedman [2].

The main results of this paper were obtained independently by both authors.

If λ is an ordinal, E is said to be Mahlo (or stationary) in λ, if λ – E does not contain a closed cofinal subset of λ.

Consider the statements:

(J1) There is a class E of limit ordinals and a sequence Cλ defined on singular limit ordinals λ such that

(i) E ⋂ μ is Mahlo in μ for all regular > ω;

(ii) Cλ is closed and unbounded in λ;

(iii) if γ < is a limit point of Cλ, then γ is singular, γ ∉ E and Cγ = γ ⋂ Cλ.

For each infinite cardinal κ:

(J2,κ) There is a set E ⊂ κ+ and a sequence Cλ(Lim(λ), λ < κ+) such that

(i) E is Mahlo in κ+;

(ii) Cλ is closed and unbounded in λ;

(iii) if cf(λ) < κ, then card Cλ < κ;

(iv) if γ < λ is a limit point of Cλ then γ ∉ E and Cγ = ϣ ⋂ Cλ.
Least upper bounds for minimal pairs of α-R.E. α-degrees
Authors: Lerman Manuel
Published: May 2006

The application of priority arguments to study the structure of the upper semilattice of α-r.e. α-degrees for all admissible ordinals α was first done successfully by Sacks and Simpson [5] who proved that there exist incomparable α-r.e. α-degrees. Lerman and Sacks [3] studied the existence of minimal pairs of α-r.e. α-degrees, and proved their existence for all admissible ordinals α which are not refractory. We continue the study of the α-r.e. α-degrees, and prove that no minimal pair of α-r.e. α-degrees can have as least upper bound the complete α-r.e. α-degree.

The above-mentioned theorem was first proven for α = ω by Lachlan [1]. Our proof for α = ω differs from Lachlan's in that we eliminate the use of the recursion theorem. The proofs are similar, however, and a knowledge of Lachlan's proof will be of considerable aid in reading this paper.

We assume that the reader is familiar with the basic notions or α-recursion theory, which can be found in [2] or [5].

Throughout the paper a will be an arbitrary admissible ordinal. We identify a set A ⊆ α with its characteristic function, A(x) = 1 if x ∈ A, and A(x) = 0 if x ∉ A.

If A ⊆ α and B ⊆ α, then A ⊕ B will denote the set defined by

A ⊕ B(x) = A(y) if x = λ + 2z, λ is a limit ordinal, z < ω and y = λ + z,

= B(y) if x = λ + 2z + 1, λ is a limit ordinal, z < ω, and y = λ + z.
The center of an orthologic
Authors: Jeffcott Barbara
Published: May 2006

Since 1933, when Kolmogorov laid the foundations for probability and statistics as we know them today [1], it has been recognized that propositions asserting that such and such an event occurred as a consequence of the execution of a particular random experiment tend to band together and form a Boolean algebra. In 1936, Birkhoff and von Neumann [2] suggested that the so-called logic of quantum mechanics should not be a Boolean algebra, but rather should form what is now called a modular ortholattice [3]. Presumably, the departure from Boolean algebras encountered in quantum mechanics can be attributed to the fact that in quantum mechanics, one must consider more than one physical experiment, e.g., an experiment measuring position, an experiment measuring charge, an experiment measuring momentum, etc., and, because of the uncertainty principle, these experiments need not admit a common refinement in terms of which the Kolmogorov theory is directly applicable.

Mackey's Axioms I–VI for quantum mechanics [4] imply that the logic of quantum mechanics should be a σ-orthocomplete orthomodular poset [5]. Most contemporary practitioners of quantum logic seem to agree that a quantum logic is (at least) an orthomodular poset [6], [7], [8], [9], [10] or some variation thereof [11]. P. D. Finch [12] has shown that every completely orthomodular poset is the logic arising from sets of Boolean logics, where these sets have a structure similar to the structures generally given to quantum logic. In all of these versions of quantum logic, a fundamental relation, the relation of compatibility or commutativity, plays a decisive role.
Almost strongly minimal theories. II
Authors: Baldwin John T.
Published: May 2006

The notion of an almost strongly minimal theory was introduced in [1]. Such a theory is a particularly simple sort of ℵ1-categorical theory. In [1] we characterized this simplicity in terms of the Stone space of models of T. Here, we characterize almost strongly minimal theories which are not ℵ0-categorical in terms of D. M. R. Park's notion [4] of a theory with the strong elementary intersection property. In addition we prove a useful sufficient condition for an elementary theory to be an almost strongly minimal theory. Our notation is from [1] but this paper is independent of the results proved there. We do assume familiarity with §1 and §2 of [2].

In [4], Park defines a theory T to have the strong elementary intersection property (s.e.i.p.) if for each model C of T and each pair of elementary submodels of C either is an elementary submodel of C. T has the nontrivial strong elementary intersection property (n.s.e.i.p.) if for each triple C, as above Park proves the following two statements equivalent:
Addition in nonstandard models of arithmetic
Authors: Phillips R.
Published: May 2006

In [3] Kemeny made the following conjecture: Suppose *Z is a nonstandard model of the ring of integers Z. Let

and let F be the subgroup of those cosets ā which contain an element of infinite height in *Z. Kemeny then asked if the ring R = {a: ā ∈ F} is also a nonstandard model of Z. If so then Goldbach's conjecture is false because Kemeny also shows in [3] that Goldbach's conjecture fails in R.

The papers [1] and [5] by Gandy and Mendelson show that R is not a nonstandard model of Z but we give here a simpler proof based on Mendelson's paper. Suppose R is a nonstandard model of Z. Then each positive number in R is a sum of four squares. Choose a in R so that a is a positive element of R of infinite height in *Z. Then since a is infinite in *Z, a − 1 is positive. Thus , xi ∈ R for i = 1, …, 4. Now each xi must be of the form ai + ni, where ai has infinite height in *Z and ni, ∈ Z.
Ideal models and some not so ideal problems in the model theory of L(Q)
Authors: Bruce Kim B.
Published: May 2006

It is the purpose of this paper to investigate the model theory of logic with a generalized quantifier; in particular the logic L(Q1) where Q1xφ(x) has the intended meaning “there exist uncountably many x such that φ(x)”. We do this from the point of view that the best way to study what happens in the so-called “ω1-standard” models of L(Q1) is to examine the countable ideal models of L(Q) that satisfy all of the axioms for L(Q1) (see definitions of ω1-standard and ideal models in §1). We believe that this study can be as fruitful for L(Q1) as the study of countable models of ZF has been for set theory.

A major problem is formulating an adequate definition of submodel for countable ideal models that is compatible with that for ω1-standard models. Thus we begin the paper by discussing several possible definitions of the notion of submodel. We then adopt a particular definition of submodel and investigate model-completeness in L(Q). We define model-completeness both for ω1-standard models and for countable ideal models and compare the two notions. We also examine elimination of quantifiers, as well as investigating formulas preserved under submodels, again both for ω1-standar d and countable ideal models.
Single premise Post canonical forms defined over one-letter alphabets
Authors: Hughes Charles E.
Published: May 2006

In this paper we investigate some families of decision problems associated with a restricted class of Post canonical forms, specifically, those defined over one-letter alphabets whose productions have single premises and contain only one variable. For brevity sake, we call any such form an RPCF (Restricted Post Canonical Form). Constructive proofs are given which show, for any prescribed nonrecursive r.e. many-one degree of unsolvability D, the existence of an RPCF whose word problem is of degree D and an RPCF with axiom whose-decision problem is also of degree D. Finally, we show that both of these results are best possible in that they do not hold for one-one degrees.
Note on the fan theorem
Authors: Troelstra A. S.
Published: May 2006

The principal aim of this paper is to establish a theorem stating, roughly, that the addition of the fan theorem and the. continuity schema to an intuitionistic system of elementary analysis results in a conservative extension with respect to arithmetical statements.

The result implies that the consistency of first order arithmetic cannot be proved by use of the fan theorem, in addition to standard elementary methods—although it was the opposite assumption which led Gentzen to withdraw the first version of his consistency proof for arithmetic (see [B]).

We must presuppose acquaintance with notation and principal results of [K, T], and with §1.6, Chapter II, and Chapter III, §4-6 of [T1]. In one respect we shall deviate from the notation in [K, T]: We shall use (n)x (instead of g(n, x)) to indicate the xth component of the sequence coded by n, if x < lth(n), 0 otherwise.

We also introduce abbreviations n ≤* m, a ≤ b which will be used frequently below:
Sufficient conditions for the undecidability of intuitionistic theories with applications
Authors: Gabbay Dov M.
Published: May 2006

Let Δ be a set of axioms of a theory Tc(Δ) of classical predicate calculus (CPC); Δ may also be considered as a set of axioms of a theory TH(Δ) of Heyting's predicate calculus (HPC). Our aim is to investigate the decision problem of TH(Δ) in HPC for various known theories Δ of CPC.

Theorem I(a) of §1 states that if Δ is a finitely axiomatizable and undecidable theory of CPC then TH(Δ) is undecidable in HPC. Furthermore, the relations between theorems of HPC are more complicated and so two CPC-equivalent axiomatizations of the same theory may give rise to two different HPC theories, in fact, one decidable and the other not.

Semantically, the Kripke models (for which HPC is complete) are partially ordered families of classical models. Thus a formula expresses a property of a family of classical models (i.e. of a Kripke model). A theory Θ expresses a set of such properties. It may happen that a class of Kripke models defined by a set of formulas Θ is also definable in CPC (in a possibly richer language) by a CPC-theory Θ′! This establishes a connection between the decision problem of Θ in HPC and that of Θ′ in CPC. In particular if Θ′ is undecidable, so is Θ. Theorems II and III of §1 give sufficient conditions on Θ to be such that the corresponding Θ′ is undecidable. Θ′ is shown undecidable by interpreting the CPC theory of a reflexive and symmetric relation in Θ′.
Preservation of elementary equivalence under scalar extension
Authors: Rose Bruce I.
Published: May 2006

In this note we show that taking a scalar extension of two elementarily equivalent finite-dimensional algebras over the same field preserves elementary equivalence. The general question of whether or not tensor product preserves elementary equivalence was originally raised in [4]. In [3] Feferman relates an example of Ersov which answers the question negatively. Eklof and Olin [7] also provide a counterexample to the general question in the context of two-sorted structures. Thus the result proved below is a partial positive answer to a general question whose status has been resolved negatively. From the viewpoint of applied model theory it seems desirable to find contexts in which positive statements of preservation can be obtained. Our result does have an application; a corollary to it increases our understanding of what it means for two division algebras to be elementarily equivalent.

All algebras are finite-dimensional algebras over fields. All algebras contain an identity element, but are not necessarily associative.

Recall that the center of a not necessarily associative algebra A is the set of elements which commute and “associate” with all elements of A. The notion of a scalar extension is an important one in algebra. If A is an algebra over F and G is an extension field of F, then the scalar extension of A by G is the algebra A ⊗F G.
On the role of Ramsey quantifiers in first order arithmetic
Authors: Schmerl James H. , Simpson Stephen G.
Published: May 2006

The purpose of this paper is to study a formal system PA(Q2) of first order Peano arithmetic, PA, augmented by a Ramsey quantifier Q2 which binds two free variables. The intended meaning of Q2xx′φ(x, x′) is that there exists an infinite set X of natural numbers such that φ(a, a′) holds for all a, a′ Є X such that a ≠ a′. Such an X is called a witness set for Q2xx′φ(x, x′). Our results would not be affected by the addition of further Ramsey quantifiers Q3, Q4, …, Here of course the intended meaning of Qkx1 … xkφ(x1,…xk) is that there exists an infinite set X such that φ(a1…, ak) holds for all k-element subsets {a1, … ak} of X.

Ramsey quantifiers were first introduced in a general model theoretic setting by Magidor and Malitz [13]. The system PA{Q2), or rather, a system essentially equivalent to it, was first defined and studied by Macintyre [12]. Some of Macintyre's results were obtained independently by Morgenstern [15]. The present paper is essentially self-contained, but all of our results have been directly inspired by those of Macintyre [12].

After some preliminaries in §1, we begin in §2 by giving a new completeness proof for PA(Q2). A by-product of our proof is that for every regular uncountable cardinal k, every consistent extension of PA(Q2) has a k-like model in which all classes are definable. (By a class we mean a subset of the universe of the model, every initial segment of which is finite in the sense of the model.)
Some theories associated with algebraically closed fields
Authors: Ash Chris , Rosenthal John
Published: May 2006

We consider the effect on decidability of adding, to the decidable theory of algebraically closed fields of characteristic zero, relation symbols for algebraic independence or function symbols for differentiation. Our results show that the corresponding theories are usually undeeidable.

Let k and K be algebraically closed fields of characteristic zero. Let K be an extension of k of transcendence degree n over k. Since k has characteristic 0, we may assume that the rational field, Q, is a subfield of k.

Let Indn be the n-ary relation on K which holds for exactly those n-tuples from K which are algebraically independent over k.

Let x1, …, xn be a transcendence base for K over k. For i = 1, 2, …, n, let Di: K → K be the partial differentiation function with respect to xi and this base.

Let KnInd = (K, +, ·, Indn), n ≤ 1 and let KnDiff = (K, +, ·, D1, …, Dn), n ≤ 1 where K has transcendence degree n over k.

We show that the theories of these structures are independent of k when k has infinite transcendence degree over Q, that KnDiff has undeeidable theory for n ≤ 1 and that KnInd has undeeidable theory for n ≤ 2. The theory of K1Ind is decidable.
Undecidable Lt theories of topological abelian groups
Authors: Cherlin Gregory L. , Schmitt Peter H.
Published: May 2006

We prove the hereditary undecidability of the Lt theories of:

(1) torsion-free Hausdorff topological abelian groups;

(2) locally pure Hausdorff topological abelian groups.
The model-theoretic significance of complemented existential formulas
Authors: Weispfenning Volker
Published: May 2006

Let T be an inductive, first-order theory in a language L, let E(L) denote the set of existential L-formulas, and let E(T) denote the distributive lattice of equivalence-classes φT of formulas φ ∈ E(L) with respect to equivalence in T. We consider three types of ‘complements’ in E(T): Let φT, ψT ∈ E(T) and suppose φT ∏ ψT = 0. Then ψT is a complement of φT, if φT ∐ ψT = 1; ψT is a pseudo-complement of φT, if for all μT ∈ E(T), (φT ∐ ψT) = 0 implies μT ≤ ψT; ψT is a “weak complement of φT, if for all μT ∈ E(T), (φT ⋰ ψT) ∐ μT = 0 implies μT = 0. The following facts are obvious: A complement of φT is also a pseudo-complement of φT and a pseudo-complement of φT is also a weak complement of φT. Any φT has at most one pseudo-complement; it is denoted by φT*. The relations ‘ψT is the complement of φT’ and ‘ψT is a weak complement of φT’ are symmetrical. We call φT (weakly, pseudo-) complemented if φT has a (weak, pseudo-) complement, and we call E(T) (weakly, pseudo-) complemented if every φT is (weakly, pseudo-) complemented.

The object of this note is to characterize (weakly, pseudo-) complemented existential formulas in model-theoretic terms, and conversely to characterize some classical notions of Robinson style model theory in terms of these formulas. The following theorems illustrate the second approach.
The consistency of system Q
Authors: Fitch Frederic B.
Published: May 2006

It will be shown that system Q of [1], with minor corrections, is free from contradiction and can be strengthened in various ways without destroying its consistency.

By the system C*A will be meant the system that results in place of CA if rule 3.4.10 is omitted in [2] from the rules 3.4 defining PA and RA for an arbitrary class A of equations. We let P*A be the theorems of C*A and R*A be the antitheorems of C*A, just as PA and RA are respectively the theorems and antitheorems of CA in [2]. Similarly Γ* is the class that is defined exactly like the class Γ in 4.18 of [2] except that systems of the form C*A replace those of the form CA. The terminology and conventions of [2] will be assumed in what follows.

Using the methods that were used to show in 5.9 of [2] that CΓ is free from contradiction, it is easy to show that C*A is free from contradiction for every class A of equations. (The fact that rule 3.4.10 is omitted causes the proof of consistency to work even for cases where A is not systematically closed in the sense of 4.11 of [2].)

Just as it was shown in 4.19 of [2] that Γ is systematically closed (in the sense of 4.11 of [2]), so also it clearly can be shown that Γ* is systematically closed. This means, in effect, that the rule of substitution of equals for equals holds in the system C*Γ*.
Some initial segments of the Rudin-Keisler ordering
Authors: Blass Andreas
Published: May 2006

A 2-affable ultrafilter has only finitely many predecessors in the Rudin-Keisler ordering of isomorphism classes of ultrafilters over the natural numbers. If the continuum hypothesis is true, then there is an ℵ1-sequence of ultrafilters Dα such that the strict Rudin-Keisler predecessors of Dα are precisely the isomorphs of the Dβ's for β < α.
Modest theory of short chains. I
Authors: Gurevich Yuri
Published: May 2006

This is the first part of a two part work on the monadic theory of short orders (embedding neither ω1 nor ω1*. This part provides the technical groundwork for decidability results. Other applications are possible.
Algebraically closed groups of large cardinality
Authors: Shelah Saharon , Ziegler Martin
Published: May 2006

Let M be a countable algebraically closed group, κ an uncountable cardinal. We will prove in this paper the following theorems.

Theorem 1. There is an algebraically closed group N of cardinality κ which is ∞ – ω-equivalent to M.

Theorem 2. There is an algebraically closed group N of cardinality κ which is ∞ – ω-equivalent to M, and contains a free abelian group of cardinality κ.

Theorem 3. There are 2κ nonisomorphic algebraically closed groups of cardinality κ which are ∞ – ω-equivalent to M.

Theorem 4. There is an algebraically closed group N of cardinality κ which is ∞ – ω-equivalent to M and satisfies: Every subgroup of N of uncountable reqular cardinality contains a free subgroup of the same cardinality.

Theorems 2 and 4 illustrate Theorem 3 by exhibiting two groups N ≡ ∞ωM of cardinality κ which are nonisomorphic by obvious reasons. We state and prove Theorem 1 separately in order to give an easy example of our principal tool: the use of automorphisms instead of indiscernibles (see §2).
operators and alternating sentences in arithmetic
Authors: Manevitz Larry , Stavi Jonathan
Published: May 2006

Determining the truth value of self-referential sentences is an interesting and often tricky problem. The Gödel sentence, asserting its own unprovability in P (Peano arithmetic), is clearly true in N(the standard model of P), and Löb showed that a sentence asserting its own provability in P is also true in N (see Smorynski [Sm, 4.1.1]). The problem is more difficult, and still unsolved, for sentences of the kind constructed by Kreisel [K1], which assert their own falsity in some model N* of P whose complete diagram is arithmetically defined. Such a sentence χ has the property that N ⊨ iff N* ⊭ χ (note that ¬χ has the same property).

We show in §1 that the truth value in N of such a sentence χ, after a certain normalization that breaks the symmetry between it and its negation, is determined by the parity of a natural number, called the rank of N, for the particular construction of N* used. The rank is the number of times the construction can be iterated starting from N and is finite for all the usual constructions. We also show that modifications of, e.g., Henkin's construction (in his completeness proof of predicate calculus) allow arbitrary finite values for the rank of N. Thus, on the one hand the truth value of χ in N, for a given “nice” construction of N*, is independent of the particular (normalized) choice of χ, and we shall see that χ is unique up to (provable) equivalence in P. On the other hand, the truth value in question is sensitive to minor changes in the definition of N* and its determination seems to be largely a combinatorial problem.
Completeness, invariance and λ-definability
Authors: Statman R.
Published: May 2006

In [4] Gordon Plotkin considers the problem of characterizing the λ-definable functionals in full type structures. A plausible, but, as we shall see, quite false, conjecture is that a functional is λ-definable ⇔ it is invariant in the sense of Fraenkel and Mostowski. A better guess might be that the set of λ-definable functionals of type σ has a uniform (in σ) definition in type theory over all full type structures (Plotkin explicitly considers a certain sort of definition by means of “logical relations”). More or less generally, one may ask if the following question is decidable.

Given: a functional F in a full type structure over a finite ground domain.

Question: is Fλ-definable?

We call the statement that this question is decidable Plotkin's λ-definability conjecture. We do not know if Plotkin's conjecture is true.

In this note we consider several questions which quickly arise from Plotkin's conjecture. In §1, we ask which type structures satisfy λ-definability = invariance. We construct for each consistent set of equations a model satisfying this equality. From consideration of these models we obtain a number of syntactic corollaries including a reduction of βη-conversion to βη-conversion at a single type (Theorem 3), an “ω-rule” for βη-conversion (Proposition 6) and consistency with βη-conversion (Proposition 8), definability and indefinability results for versions of Kronecker's δ (Propositions 10 and 11), and a decidability result for the problem of inter-definability among combinators.
Simplicity in effective topology
Authors: Kalantari Iraj , Leggett Anne
Published: May 2006

The recursion-theoretic study of mathematical structures other thanωis now a field of much activity. Analysis and algebra are two such structures which have been studied for their effective contents. Studies in analysis began with the work of Specker on nonconstructive proofs in analysis [16] and in Lacombe's inspiring notes on relevant notions of recursive analysis [8]. Studies in algebra originated in the work of Frolich and Shepherdson on effective extensions of explicit fields [1] and in Rabin's study of computable fields [15]. Equipped with the richness of modern techniques in recursion theory, Metakides and Nerode [11]–[13] began investigating the effective content of vector spaces and fields; these studies have been extended by Kalantari, Remmel, Retzlaff, Shore and others.

Kalantari and Retzlaff [5] began a foundational inquiry into effectiveness in topological spaces. They consider a topological spaceXwith a countable basis ⊿ for the topology. The space isfully effective, that is, the basis elements are coded intoωand the operation of intersection of basis elements and the relation of inclusion among them are both computable. Similar to, the lattice of recursively enumerable (r.e.) subsets ofω, the collection of r.e. open subsets ofXforms a latticeℒ(X)under the usual operations of union and intersection.
On generalized quantifiers in arithmetic
Authors: Morgenstern Carl
Published: May 2006

In this note we investigate an extension of Peano arithmetic which arises from adjoining generalized quantifiers to first-order logic. Markwald [2] first studied the definability properties of L1, the language of first-order arithmetic, L, with the additional quantifer Ux which denotes “there are infinitely many x such that…. Note that Ux is the same thing as the Keisler quantifier Qx in the ℵ0 interpretation.

We consider L2, which is L together with the ℵ0 interpretation of the Magidor-Malitz quantifier Q2xy which denotes “there is an infinite set X such that for distinct x, y ∈ X …”. In [1] Magidor and Malitz presented an axiom system for languages which arise from adding Q2 to a first-order language. They proved that the axioms are valid in every regular interpretation, and, assuming ◊ω1, that the axioms are complete in the ℵ1 interpretation.

If we let denote Peano arithmetic in L2 with induction for L2 formulas and the Magidor-Malitz axioms as logical axioms, we show that in we can give a truth definition for first-order Peano arithmetic, . Consequently we can prove in that is Πn sound for every n, thus in we can prove the Paris-Harrington combinatorial principle and the higher-order analogues due to Schlipf.
On forcing without the continuum hypothesis
Authors: Abraham Uri
Published: May 2006

ℵ2. One of the first examples of the forcing method is cardinal collapsing (A. Levy, see [5]), for example, collapsing ℵ2 to ℵ1: the poset P is the collection of all countable functions from a countable ordinal into ℵ2. As is well known, in VP, , and because P is closed under union of countable chains, remains a cardinal and, in fact, no new countable sets are added. But to prove that remains a cardinal we need to conclude ∣P∣ ≤ ℵ2 and hence ℵ3 is not collapsed. If it has been observed that is actually collapsed in VP. Hence the following theorem, which makes no assumptions on the continuum, is relevant.

1. Theorem. There is a poset R such that in VR ℵ2 becomes of cardinality ℵ1, but ℵ1 and the cardinals above ℵ2 are not collapsed.
Hauptsatz for higher-order modal logic
Authors: Nishimura Hirokazu
Published: May 2006

In spite of the philosophical significance of higher-order modal logic, the modal logician's main concern has been with sentential logic. In this paper we do not intend to go into philosophical details, but we only remark that higher-order modal logic has a close relationship with Montague's well-known idea of “universal grammar”, which is an ambitious attempt to build a logical theory of natural languages with exact syntax and semantics, comparable with the artificial languages of mathematical logic. For this matter, the reader can consult, e.g., Montague [8], [9] and Gallin [2].
κ-Suslin logic
Authors: Green Judy
Published: May 2006

An analogue of a theorem of Sierpinski about the classical operation () provides the motivation for studying κ-Suslin logic, an extension of Lκ+ω which is closed under a propositional connective based on (). This theorem is used to obtain a complete axiomatization for κ-Suslin logic and an upper bound on the κ-Suslin accessible ordinals (for κ = ω these results are due to Ellentuck [E]). It also yields a weak completeness theorem which we use to generalize a result of Barwise and Kunen [B-K] and show that the least ordinal not H(κ+) recursive is the least ordinal not κ-Suslin accessible.

We assume familiarity with lectures 3, 4 and 10 of Keisler's Model theory for infinitary logic [Ke]. We use standard notation and terminology including the following.

Lκ+ω is the logic closed under negation, finite quantification, and conjunction and disjunction over sets of formulas of cardinality at most κ. For κ singular, conjunctions and disjunctions over sets of cardinality κ can be replaced by conjunctions and disjunctions over sets of cardinality less than κ so that we can (and will in §2) assume the formation rules of Lκ+ω allow conjunctions and disjunctions only over sets of cardinality strictly less than κ whenever κ is singular.
Some independence results for Peano arithmetic
Authors: Paris J. B.
Published: May 2006

In this paper we shall outline a purely model theoretic method for obtaining independence results for Peano's first order axioms (P). The method is of interest in that it provides for the first time elementary combinatorial statements about the natural numbers which are not provable in P. We give several examples of such statements.

Central to this exposition will be the notion of an indicator. Indicators were introduced by L. Kirby and the author in [3] although they had occurred implicitly in earlier papers, for example Friedman [1]. The main result on indicators which we shall need (Lemma 1) was proved by Laurie Kirby and the author in the summer of 1976 but it was not until early in the following year that the author realised that this lemma could be used to give independence results.

The first combinatorial independence results obtained were essentially statements about certain finite games and consequently were not immediately meaningful (see Example 2). This shortcoming was remedied by Leo Harrington who, upon hearing an incorrect version of our results, noticed a beautifully simply independent combinatorial statement. We outline this result in Example 3. An alternative, more detailed, proof may be found in [5].

Clearly Laurie Kirby and Leo Harrington have made a very significant contribution to this paper and we wish to express our sincere thanks to them.
Set theory with a filter quantifier
Authors: Kaufmann Matt
Published: May 2006

The incompleteness of ZF set theory leads one to look for natural extensions of ZF in which one can prove statements independent of ZF which appear to be “true”. One approach has been to add large cardinal axioms. Or, one can investigate second-order expansions like Kelley-Morse class theory, KM. In this paper we look at a set theory ZF(aa), with an added quantifier aa which ranges over ordinals. The “aa” stands for “almost all”, and although we will consider interpretations in terms of the closed unbounded filter on a regular cardinal κ, we will consider other interpretations also.

We start in §1 by giving the axioms for the theory ZF(aa) and presenting a completeness theorem which gives a model-theoretic definition of ZF(aa). In §2 we investigate set theory with a satisfaction predicate and interpret it in a fragment of ZF(aa). In §3 we generalize the methods of §2 to obtain a hierarchy of satisfaction predicates. We use these predicates to prove reflection theorems, as well as to prove the consistency of certain fragments of ZF(aa). Next, in §4 we discuss expandability of models of ZF to models of fragments of ZF(aa) and of Kelley-Morse. We conclude in §5 with a discussion of an extension ZF(aa) + DET of ZF(aa) in which the quantifier aa is self-dual.
High and low Kleene degrees of coanalytic sets
Authors: Simpson Stephen G. , Weitkamp Galen
Published: May 2006

We say that a set A of reals is recursive in a real y together with a set B of reals if one can imagine a computing machine with an ability to perform a countably infinite sequence of program steps in finite time and with oracles for B and y so that decides membership in A for any real x input to by way of an oracle for x. We write A ≤ yB. A precise definition of this notion of recursion was first considered in Kleene [9]. In the notation of that paper, A ≤yB if there is an integer e so that χA(x) = {e}(x y, χB, 2E). Here χA is the characteristic function of A. Thus Kleene would say that A is recursive in (y, B, 2E), where 2E is the existential integer quantifier.

Gandy [5] observes that the halting problem for infinitary machines such as , as in the case of Turing machines, gives rise to a jump operator for higher type recursion. Thus given a set B of reals, the superjump B′ of B is defined to be the set of all triples 〈e, x, y〉 such that the eth machine with oracles for y and B eventually halts when given input x. A set A is said to be semirecursive in y together with B if for some integer e, A is the cross section {x: 〈e, x, y 〉 ∈ B′}. In Kleene [9] it is demonstrated that a set A is semirecursive in y alone if and only if it is
The countably based functionals
Authors: Hartley John P.
Published: May 2006

In [5], Kleene extended previous notions of computations to objects of higher finite type in the maximal type-structure of functionals given by:

Tp(0) = N = the natural numbers,

Tp(n + 1) = NTp(n) = the set of total maps from Tp(n) to N.

He gave nine schemata, S1–S9, for describing algorithms for computations from a finite list of functionals, and indices to denote these algorithms. It is generally agreed that S1-S9 give a natural concept of computations in higher types.

The type-structure of countable functions, Ct(n) for n ϵ N, was first developed by Kleene [6] and Kreisel [7]. It arises from the notions of ‘constructivity’, and has been extensively studied as a domain for higher type recursion theory. Each countable functional is globally described by a countable amount of information coded in its associate, and it is determined locally by a finite amount of information about its argument. The countable functionals are well summarised in Normann [9], and treated in detail in Normann [8].

The purpose of this paper is to discuss a generalisation of the countable functionals, which we shall call the countably based functions, Cb(n) for n ϵ N. It is suggested by the notions of ‘predicativity’, in which we view N as a completed totality, and build higher types on it in a constructive manner. So we shall allow quantification over N and include application of 2E in our schemata. Each functional is determined locally by a countable amount of information about its argument, and so is globally described by a continuum of information coded in its associate, which will now be a type-2 object. This generalisation, obtained via associates, was proposed by Wainer, and seems to reflect topological properties of the countable functionals.
On a combinatorial property of menas related to the partition property for measures on supercompact cardinals
Authors: Kunen Kenneth , Pelletier Donald H.
Published: May 2006

T.K. Menas [4, pp. 225–234] introduced a combinatorial property Χ(μ) of a measure μ on a supercompact cardinal κ and proved that measures with this property also have the partition property. We prove here that Menas' property is not equivalent to the partition property. We also show that if a is the least cardinal greater than κ such that Pκα bears a measure without the partition property, then α is inaccessible and -indescribable.