bluuebunny/crossref_metadata_2025_split huggingface dataset:
Toward model theory through recursive saturation
Authors: Schlipf John Stewart 
Published: May 2006

One of the most significant by-products of the study of admissible sets with urelements is the emphasis it has given to recursively saturated models. As suggested in [Schlipf, 1977], countable recursively saturated models (for finite languages) possess many of the desirable properties of saturated and special models. The notion of resplendency was introduced to isolate some of these desirable properties. In §§1 and 2 of this paper we study these parallels, showing how they can be exploited to give new proofs of some traditional model theoretic theorems. This yields both pedagogical and philosophical advantages: pedagogical since countable recursively saturated models are easier to build and manipulate than saturated and special models; philosophical since it shows that uncountable models — which the downward Lowenheim–Skolem theorem tells us are in some sense not basic in the study of countable theories — are not needed in model theoretic proofs of these theorems. In §3 we apply our local results to get results about resplendent models of ZF set theory and PA (Peano arithmetic). In §4 we shall examine certain analogous results for admissible languages, most similar to, and seemingly generally slightly weaker than, already known results. (The Chang–Makkai sort of result, however, is new.)Although this paper is an outgrowth of work with admissible sets with urelements, I have tried to keep it as accessible as possible to those with a background only in finitary model theory. Thus §§1,2, and 3 should not involve any work with admissible sets. §4, however, is concerned with some admissible analogues to results in §2 and necessarily uses certain technical results of §11 5 of [Schlipf, 1977].
A type-free Gödel interpretation
Authors: Beeson Michael 
Published: May 2006

In 1930, A. Heyting first specified a formal system for part of intuitionistic mathematics. Although his rules were presumably motivated by the “intended interpretation” or meaning of the logical symbols, over the years a number of other possible interpretations have been discovered for which the rules are also valid. In particular, one might mention the realizablity interpretation of Kleene, the (Dialectica) interpretation of Gödel, and various semantic interpretations, such as Kripke models. (Each of these has several variants or close relatives.) Each such interpretation can be regarded as defining precisely a certain “notion of constructivity”, the study of which may illuminate the still rather vague notions which underlie the intended interpretation; or, if one doubts that there is a single interpretation “intended” by all constructivist mathematicians, the study of precisely defined interpretations may help to delineate and distinguish the possibilities.In the last few years, Heyting's systems have been vastly extended, in order to encompass the large and growing body of constructive mathematics. Several kinds of new systems have been put forward and studied. The present author has extended the various realizability interpretations to several of these systems [B1], [B2] and drawn a number of interesting applications. The mathematical content of the present paper is an interpretation in the style of Godel's Dialectica interpretation, but applicable to the new systems put forward by Feferman [Fl]. The original motivation for this work was to obtain certain metamathematical applications: roughly speaking, Markov's rule and its variants.
Some anomalies in Fitch's system QD
Authors: Bunder M. W. , Seldin Jonathan P. 
Published: May 2006

This note shows that the argument used in the proof of the inconsistency of Curry's system (see [1]) can also be applied to Fitch's system QD (see [3, Chapter 6]). As one vital rule of is not present in QD this argument does not lead to an actual contradiction, but it does lead to a theorem which is not a proposition if the system is consistent.The method used below is that of [2], which is simpler than that of [1].The axioms and rules of QD that we require are also present in [1] and [2] provided that Fitch's D is replaced by H. These axioms and rules are the following:DD int: ⊦ D(Da),m p: If ⊦ a ⊃ b2 and ⊦ a then ⊦ b, andres imp int: If a ⊦ b then Da ⊦ a ⊃ b.Let a be arbitrary and let G be [x](Dx ⊃ (x ⊃ a)). Then let X be BWBG(BWBG). We then have the following proof:Thus, we have ⊦ X. Now suppose we also had ⊦ DX. Then by the method of the innermost subproof in the above proof, we would have ⊦ a, and since a isarbitrary the system would be inconsistent. Hence, if QD is consistent, we do not have ⊦ DX, and so X is a theorem which is not a proposition.
The ℵ1-categoricity of strictly upper triangular matrix rings over algebraically closed fields
Authors: Rose Bruce I. 
Published: May 2006

AbstractLet n ≥ 3. The following theorems are proved.Theorem. The theory of the class of strictly upper triangular n × n matrix rings over fields is finitely axiomatizable.Theorem. If R is a strictly upper triangular n × n matrix ring over a field K, then there is a recursive map σ from sentences in the language of rings with constants for K into sentences in the language of rings with constants for R such that K ⊨ φ if and only if R φ σ(φ).Theorem. The theory of a strictly upper triangular n × n matrix ring over an algebraically closed field is ℵ1-categorical.
An ideal game
Authors: Galvin F. , Jech T. , Magidor M. 
Published: May 2006

Let us consider the following infinite game between two players, Empty and Nonempty. We are given a large set S. Empty opens the game by choosing a large subset S0 of S; then Nonempty chooses a large set S1 ⊆ S0; then Empty chooses large S2 ⊆ S, etc. The game is over after ω moves. If ⋂n=0xSn is empty then Empty wins, and if ⋂n=0∞Sn is nonempty then Nonempty wins.If “large” means “infinite”, then Empty can beat Nonempty rather easily: he chooses So countable, S0 = {a0, a1,…, an,…}, and then he chooses S2 such that a0 ∉ S2, S4 such that a1, ∉ S4 and so on.Next we assume that S is a set of uncountable cardinality, and that “large” means “of cardinality ∣S∣”. Then still Empty can win, but his winning strategy is somewhat more sophisticated: Let us identify S with a cardinal number κ. Thus each subset of S of size κ is a set of ordinals below κ. For each X ⊆ κ of size κ, let fx be the unique order-preserving mapping of X onto κ, and let F(X) = {x ϵ X: f(x) is a successor ordinal}. Empty's strategy is to play S0 = F(K), and when Nonempty plays S2k − 1, let S2k = F(S2k − 1).
Minimal pairs and high recursively enumerable degrees
Authors: Cooper S. B. 
Published: May 2006

A. H. Lachlan [2] and C. E. M. Yates [4] independently showed that minimal pairs of recursively enumerable (r.e.) degrees exist. Lachlan and Richard Ladner have shown (unpublished) that there is no uniform method for producing a minimal pair of r.e. degrees below a given nonzero r.e. degree. It is not known whether every nonzero r.e. degree bounds a r.e. minimal pair, but in the present paper it is shown (uniformly) that every high r.e. degree bounds a r.e. minimal pair. (A r.e. degree is said to be high if it contains a high set in the sense of Robert W. Robinson [3].)Theorem. Let a be a recursively enumerable degree for which a′ = 0″. Then there are recursively enumerable degrees b0 and b1 such that0 < bi < a for each i ≤ 1, and b0 ⋂ b1 = 0.The proof is based on the Lachlan minimal r.e. pair construction. For notation see Lachlan [2] or S. B. Cooper [1].By Robinson [3] we can choose a r.e. representative A of the degree a, with uniformly recursive tower {As, ∣ s ≥ 0} of finite approximations to A, such that CA dominates every recursive function whereWe define, stage by stage, finite sets Bi,s, i ≤ 1, s ≥ 0, in such a way that Bi, s + 1 ⊇ Bi,s for each i, s, and {Bi,s ∣ i ≤ 1, s ≥ 0} is uniformly recursive.
The isomorphism property in nonstandard analysis and its use in the theory of Banach spaces
Authors: Henson C. Ward 
Published: May 2006

The basic setting of nonstandard analysis consists of a set-theoretical structure together with a map * from into another structure * of the same sort. The function * is taken to be an elementary embedding (in an appropriate sense) and is generally assumed to make * into an enlargement of [13]. The structures and * may be type-hierarchies as in [11] and [13] or they may be cumulative structures with ω levels as in [14]. The assumption that * is an enlargement of has been found to be the weakest hypothesis which allows for the familiar applications of nonstandard analysis in calculus, elementary topology, etc. Indeed, practice has shown that a smooth and useful theory can be achieved only by assuming also that * has some stronger properties such as the saturation properties first introduced in nonstandard analysis by Luxemburg [11].This paper concerns an entirely new family of properties, stronger than the saturation properties. For each cardinal number κ, * satisfies the κ-isomorphism property (as an enlargement of ) if the following condition holds:For each first order language L with fewer than κ nonlogical symbols, if and are elementarily equivalent structures for L whose domains, relations and functions are all internal (relative to * and ), then and are isomorphic.
The finite controllability of the Maslov case
Authors: Aanderaa Stål , Goldfarb Warren D. 
Published: May 2006

In this paper we show the finite controllability of the Maslov class of formulas of pure quantification theory (specified immediately below). That is, we show that every formula in the class has a finite model if it has a model at all. A signed atomic formula is an atomic formula or the negation of one; a binary disjunction is a disjunction of the form A1 ⋁ A2, where A1 and A2 are signed atomic formulas; and a formula is Krom if it is a conjunction of binary disjunctions. Finally, a prenex formula is Maslov if its prefix is ∃···∃∀···∀∃···∃ and its matrix is Krom.A number of decidability results have been obtained for formulas classified along these lines. It is a consequence of Theorems 1.7 and 2.5 of [4] that the following are reduction classes (for satisfiability): the class of Skolem formulas, that is, prenex formulas with prefixes ∀···∀∃···∃, whose matrices are conjunctions one conjunct of which is a ternary disjunction and the rest of which are binary disjunctions; and the class of Skolem formulas containing identity whose matrices are Krom. Moreover, the following results (for pure quantification theory, that is, without identity) are derived in [1] and [2]: the classes of prenex formulas with Krom matrices and prefixes ∃∀∃∀, or prefixes ∀∃∃∀, or prefixes ∀∃∀∀ are all reduction classes, while formulas with Krom matrices and prefixes ∀∃∀ comprise a decidable class. The latter class, however, is not finitely controllable, for it contains formulas satisfiable only over infinite universes. The Maslov class was shown decidable by Maslov in [11].
Completeness properties of heyting's predicate calculus with respect to re models
Authors: Gabbay Dov M. 
Published: May 2006

Validity in recursive structures was investigated by several authors. Kreisel [10] has shown that there exists a consistent sentence of classical predicate calculus (CPC) that does not possess a recursive model. The sentence is a conjunction of the axioms of a variant of Bernays set theory, including the axiom of infinity. The language contains additional constants besides ϵ. Later Kreisel [2] and Mostowski [3] presented a sentence (not possessing recursive models) which was a conjunction of axioms of a variant of Bernays set theory without the axiom of infinity but still with additional constants besides ϵ. Later Mostowski [4] improved the result by giving a sentence which can be demonstrated in Heyting arithmetic to be consistent and to have no recursive models. Rabin [6] obtained a simple proof that some sentence of set theory with the single nonlogical constant ϵ does not have any recursively enumerable models.More generally, Mostowski [5] has shown that the set of all sentences valid in all RE models is not arithmetical and Vaught [1] improved this result by showing that it holds for a language of one binary relation. In fact, Vaught gives· a way of translating n-place relations to 2-place ones that preserves the RE characteristic of the model. For further results pertaining to recursive models see Vaught [1].
Negative-existentially complete structures and definability in free extensions
Authors: Weispfenning Volker 
Published: May 2006

Let R be a commutative ring with 1 and R[X1, …, Xn] the polynomial ring in n variables over R. Then for any relation f(X) = 0 in R[X] there exists a conjunction of equations φf such that f(X) = 0 holds in R[X] iff φf holds in R; φf is of course the formula saying that all the coefficients of f(X) vanish. Moreover, φf is independent of R and formed uniformly for all polynomials f up to a given formal degree. In this paper we investigate first order theories T for which a similar phenomenon holds. More precisely, we let TAH be the universal Horn part of a theory T and look at free extensions of models of T in the class of models of TAH. We ask whether an atomic relation t1(X, a) = t2(X, a) or R(t1(X, a), …, tn(X, a)) in can be equivalently expressed by a finite or infinitary formula φ(a) in , such that φ(y) depends only on ti{X, y) and not on or a1, …, am ∈ A.We will show that for a wide class of theories T “defining formulas” φ(y) in this sense exist and can be taken as infinite disjunctions of positive existential formulas.
Uniform inductive definability and infinitary languages
Authors: Nyberg Anders M. 
Published: May 2006

Introduction. The purpose of this paper is to show how results from the theory of inductive definitions can be used to obtain new compactness theorems for uncountable admissible languages. These will include improvements of the compactness theorem by J. Green [9].In [2] Barwise studies admissible sets satisfying the Σ1-compactness theorem. Our approach is to consider admissible sets satisfying what could be called the abstract extended completeness theorem, that is, sets where the consequence relation of the admissible fragment LA is Σ1-definable over A. We will call such sets Σ1-complete. For countable admissible sets, Σ1-completeness follows from the completeness theorem for LA.Having restricted our attention to Σ1-complete sets we are led to a stronger notion also true on countable admissible sets, namely what we shall call uniform Σ1-completeness. We will see that this notion can be viewed as extending to uncountable admissible sets, properties related to both the “recursion theory” and “proof theory” of countable admissible sets.By following Barwise's recent approach to admissible sets allowing “urelements,” we show that there is a natural connection between certain structures arising from the theory of inductive definability, and uniformly Σ1-complete admissible sets . The structures we have in mind are called uniform Kleene structures.
Ramsey's theorem and recursion theory
Authors: Jockusch Carl G. 
Published: May 2006

Let N be the set of natural numbers. If A ⊆ N, let [A]n denote the class of all n-element subsets of A. If P is a partition of [N]n into finitely many classes C1, …, Cp, let H(P) denote the class of those infinite sets A ⊆ N such that [A]n ⊆ Ci for some i. Ramsey's theorem [8, Theorem A] asserts that H(P) is nonempty for any such partition P. Our purpose here is to study what can be said about H(P) when P is recursive, i.e. each Ci, is recursive under a suitable coding of [N]n. We show that if P is such a recursive partition of [N]n, then H(P) contains a set which is Πn0 in the arithmetical hierarchy. In the other direction we prove that for each n ≥ 2 there is a recursive partition P of [N]n into two classes such that H(P) contains no Σn0 set. These results answer a question raised by Specker [12].A basic partition is a partition of [N]2 into two classes. In §§2, 3, and 4 we concentrate on basic partitions and in so doing prepare the way for the general results mentioned above. These are proved in §5. Our “positive” results are obtained by effectivizing proofs of Ramsey's theorem which differ from the original proof in [8]. We present these proofs (of which one is a generalization of the other) in §§4 and 5 in order to clarify the motivation of the effective versions.
Which number theoretic problems can be solved in recursive progressions on Π11-paths through O?
Authors: Kreisel G. 
Published: May 2006

This note is an addendum to an incompleteness result of Feferman and Spector [1]: for any such progression satisfying the (natural) conditions listed in [1] there is a true Π10-formula which cannot be derived in the progression. The idea of their proof yields a stronger result.If each numerical instance A[x/n] of the formula A (with the free numerical variable x) is decided in a recursive progression along a Π11-path then the set {n: ⊦ A[x/n]} is recursive.In other words, only recursively solvable problems are decidable in such progressions. This yields the incompleteness result of [1] when specialized to some Π10 formula A which defines a nonrecursive set, since then some instance A[x/n] must be undecided and A[x/n] is a closed Π10 formula. The stronger result is needed to extend Church's thesis for total functions reckonable in formal systems to (total) functions reckonable in recursive progressions on Π11-paths. A partially reckonable function always has a Π11 graph (and if its graph is Δ11 then it is by C. Jockusch, r.e.; so some Π11 sets are not partially reckonable). The relevance of these facts for the model of mathematical reasoning provided by (variants of) Turing's ordinal logics is analyzed in (b) (ii) of Part II, which goes into our current knowledge about Church's thesis.
Redundancies in the Hilbert-Bernays derivability conditions for Gödel's second incompleteness theorem
Authors: Jeroslow R. G. 
Published: May 2006

This paper presents three generalizations of the Second Incompleteness Theorem of Gödel (see [2]) which apply to a broader class of formal systems than previous generalizations (as, e.g., the generalization in [1]).The content of all three of our results is that it is versions of the third derivability condition of Hilbert and Bernays (see p. 286 of [3]) which are crucial to Gödel's theorem. The second derivability condition plays some role in certain logics, but even there, only in the far weaker form of a definability condition (see Theorem 2).The elimination of the first derivability condition allows the application of the Consistency Theorem to cut-free logics which cannot prove that they are closed under cut.It is Theorem 1 which will probably have primary interest for readers who are not concerned with technical proof theory or with foundations, for it treats logics with quantifiers, and in that case one can dispose entirely of the first and second derivability conditions. The derivation of this result requires a “new twist” on old arguments. Specifically, we use a new variation on the standard self-referential lemma (this is Lemma 5.1 of [l]) to obtain a somewhat different self-referential construction than has previously been employed (this is our lemma in §2 below). With this new construction, we consider the sentence φ which “expresses” the fact: “My negation is provable.” Then, using hypotheses associated with Gödel's First Incompleteness Theorem, one shows that ⊢¬φ is impossible in a consistent logic. Finally, using only a version of the third Hilbert-Bernays derivability condition, one shows that the provability of the consistency statement implies ⊢¬φ, and hence that consistency is unprovable.
Post's problem and his hypersimple set
Authors: Jockusch Carl G. , Soare Robert I. 
Published: May 2006

A standard enumeration of the recursively enumerable (r.e.) sets is an acceptable numbering {Wn}n∈N of the r.e. sets in the sense of Rogers [5, p. 41], together with a 1:1 recursive function f with range In his quest for nonrecursive incomplete r.e. sets Post [4] constructed a hypersimple set Hf, relative to a fixed but unspecified standard enumeration f. Although it was later shown that hyper-simplicity does not guarantee incompleteness, the ironic possibility remained that Post's own particular hypersimple set might be incomplete. We settle the question by proving that H, may be either complete or incomplete depending upon which standard enumeration f is used. In contrast, D. A. Martin has shown [3] that Post's simple set S [4, p. 298] is complete for any standard enumeration. Furthermore, what most modern recursion theorists would regard as the “natural” construction of a hypersimple set (which we give in §1) is also complete for any standard enumeration.There are two conclusions to be drawn from these results. First, they substantiate the often repeated remark among recursion theorists that Post's hypersimple set construction is a precursor of priority constructions because priorities play a strong role, and because there is a great deal of “restraint” which tends to keep elements out of the set. Secondly, the results warn recursion theorists that more properties than might have been supposed depend upon which standard enumeration is chosen at the beginning of the construction of some r.e. set.
Reflecting stationary sets
Authors: Magidor Menachem 
Published: May 2006

AbstractWe prove that the statement “For every pair A, B, stationary subsets of ω2, composed of points of cofinality ω, there exists an ordinal α such that both A ∩ α and B ∩ α are stationary subsets of α is equiconsistent with the existence of weakly compact cardinal. (This completes results of Baumgartner and Harrington and Shelah.)We also prove, assuming the existence of infinitely many supercompact cardinals, the statement “Every stationary subset of ωω+1 has a stationary initial segment.”
A transfer principle in harmonic analysis
Authors: Takeuti Gaisi 
Published: May 2006

Let G be a locally compact abelian group, Γ its dual group, and μ its Haar measure. For a function f: G → C, the Fourier transform of f is defined byfor every γ ∈ Γ.We extend this definition for a function f on G, whose values are pairwise commutable normal operators in a Hilbert space. Then we study harmonic analysis for this extended Fourier transform.Our method is Boolean valued analysis as introduced in [11] and [12]. Instead of developing the theory in a step-by-step manner, we shall develop a general machinery showing how to transform classical theorems to theorems in our situation.In Chapter 1, we summarize the basic knowledge on Hilbert space, on Boolean valued model of set theory, and on Boolean valued analysis. In Chapter 2, we develop the theory of integration. Since we deal with unbounded operators as well as bounded operators, we need a new theory of integration. For a separable Hilbert space, the value of our integration coincides with the value of the usual integration with an adequate generalization for unbounded operators.In Chapter 3, we establish machinery for our transfer principle and carry out the transformation of many classical theorems to theorems for our case.
The Baire category theorem and cardinals of countable cofinality
Authors: Miller Arnold W. 
Published: May 2006

AbstractLet κB be the least cardinal for which the Baire category theorem fails for the real line R. Thus κB is the least κ such that the real line can be covered by κ many nowhere dense sets. It is shown that κB cannot have countable cofinality. On the other hand it is consistent that the corresponding cardinal for 2ω1 be ℵω. Similar questions are considered for the ideal of measure zero sets, other ω1, saturated ideals, and the ideal of zero-dimensional subsets of Rω1.