bluuebunny/crossref_metadata_2025_split huggingface dataset:
An inelastic model with indiscernibles
Authors: Knight Julia F. 
Published: May 2006

Let L be a countable language including the unary relation symbol U. Let and be L-structures such that is a proper elementary U-extension of ; i.e., , and . Under what conditions will have a proper elementary U-extension? In [2], it was shown that this is not always the case, even if and are countable. However, the examples given are completely artificial, and it still seems that in most cases will have a proper elementary U-extension.Lascar asked whether will necessarily have a proper elementary U-extension whenever it contains an infinite set of indiscernibles over . This paper gives a counterexample for Lascar's question. The example is produced by modifying one of the examples in [2], using an idea of Marcus [5].Models containing an infinite set of indiscernibles can often be “stretched” to produce larger models that share some desired nonelementary property with the original [1], [6]. However, the mere presence of indiscernibles in a model does not guarantee that it can be used in this way.If the model is not completely determined by the indiscernibles, the nonelementary property may not carry over to larger models. An example of this is given in [3]. The example for Lascar's question is further evidence that models with indiscernibles need not be “elastic”.
Three universal representations of recursively enumerable sets
Authors: Jones James P. 
Published: May 2006

In his celebrated paper of 1931 [7], Kurt Gödel proved the existence of sentences undecidable in the axiomatized theory of numbers. Gödel's proof is constructive and such a sentence may actually be written out. Of course, if we follow Gödel's original procedure the formula will be of enormous length.Forty-five years have passed since the appearance of Gödel's pioneering work. During this time enormous progress has been made in mathematical logic and recursive function theory. Many different mathematical problems have been proved recursively unsolvable. Theoretically each such result is capable of producing an explicit undecidable number theoretic predicate. We have only to carry out a suitable arithmetization. Until recently, however, techniques were not available for carrying out these arithmetizations with sufficient efficiency.In this article we construct an explicit undecidable arithmetical formula,F(x, n), in prenex normal form. The formula is explicit in the sense that it is written out in its entirety with no abbreviations. The formula is undecidable in the recursive sense that there exists no algorithm to decide, for given values ofn, whether or notF(n, n)is true or false. MoreoverF(n, n)is undecidable in the formal (axiomatic) sense of Gödel [7]. Given any of the usual axiomatic theories to which Gödel's Incompleteness Theorem applies, there exists a value ofnsuch thatF(n, n)is unprovable and irrefutable. Thus Gödel's Incompleteness Theorem can be “focused” into the formulaF(n, n). Thus some substitution instance ofF(n, n)is undecidable in Peano arithmetic, ZF set theory, etc.
Generalized quantifiers and elementary extensions of countable models
Authors: Dubiel Małgorzata 
Published: May 2006

Let L be a countable first-order language and L(Q) be obtained by adjoining an additional quantifier Q. Q is a generalization of the quantifier “there exists uncountably many x such that…” which was introduced by Mostowski in [4]. The logic of this latter quantifier was formalized by Keisler in [2]. Krivine and McAloon [3] considered quantifiers satisfying some but not all of Keisler's axioms. They called a formula φ(x) countable-like iffor every ψ. In Keisler's logic, φ(x) being countable-like is the same as ℳ⊨┐Qxφ(x). The main theorem of [3] states that any countable model ℳ of L[Q] has an elementary extension N, which preserves countable-like formulas but no others, such that the only sets definable in both N and M are those defined by formulas countable-like in M. Suppose C(x) in M is linearly ordered and noncountable-like but with countable-like proper segments. Then in N, C will have new elements greater than all “old” elements but no least new element — otherwise it will be definable in both models. The natural question is whether it is possible to use generalized quantifiers to extend models elementarily in such a way that a noncountable-like formula C will have a minimal new element. There are models and formulas for which it is not possible. For example let M be obtained from a minimal transitive model of ZFC by letting Qxφ(x) mean “there are arbitrarily large ordinals satisfying φ”.
Modal operators and functional completeness, II
Authors: Thomason S. K. 
Published: May 2006

In the Kripke semantics for propositional modal logic, a frame W = (W, ≺) represents a set of “possible worlds” and a relation of “accessibility” between possible worlds. With respect to a fixed frame W, a proposition is represented by a subset of W (regarded as the set of worlds in which the proposition is true), and an n-ary connective (i.e. a way of forming a new proposition from an ordered n-tuple of given propositions) is represented by a function fw: (P(W))n → P(W). Finally a state of affairs (i.e. a consistent specification whether or not each proposition obtains) is represented by an ultrafilter over W. {To avoid possible confusion, the reader should forget that some people prefer the term “states of affairs” for our “possible worlds”.}In a broader sense, an n-ary connective is represented by an n-ary operatorf = {fw∣ W ∈ Fr}, where Fr is the class of all frames and each fw: (P(W))n → P(W). A connective is modal if it corresponds to a formula of propositional modal logic. A connective C is coherent if whether C(P1,…, Pn) is true in a possible world depends only upon which modal combinations of P1,…,Pn are true in that world. (A modal combination of P1,…,Pn is the result of applying a modal connective to P1,…, Pn.) A connective C is strongly coherent if whether C(P1, …, Pn) obtains in a state of affairs depends only upon which modal combinations of P1,…, Pn obtain in that state of affairs.
The unprovability in intuitionistic formal systems of the continuity of effective operations on the reals
Authors: Beeson Michael 
Published: May 2006

The question of continuity of functions defined on Baire space NN or on the reals has been of great interest to constructivists. We have little hope of answering the question without a fundamental philosophical analysis of the notion of constructive function. However, one can ask whether the continuity of functions can be derived in known intuitionistic formal systems, and answer these questions by mathematical means.The constructivist does not generally wish to restrict himself to reals (or members of NN) given by a recursive law; therefore the most natural formal systems have variables for reals, sequences and functions. The axioms of these systems turn out to be compatible with the assumption that every real or sequence is given by a recursive law, and every function by an effective operation. An underivability result, therefore, is only strengthened if this assumption is taken as an axiom; and once this is done, we may as well work with (indices of) effective operations, within arithmetic.By KLS is meant the assertion that each effective operation on Baire space NN is continuous. In [B1] it is shown that this statement cannot be proved in various intuitionistic formal systems. The continuity of functions on the reals has been of even greater interest to constructivists than the continuity of functions on NN; by KLS(R) is meant the assertion that each effective operation from the real numbers R to R is continuous. It is the purpose of the present note to show that KLS(R) is also underivable in intuitionistic formal systems.
Infinitary compactness without strong inaccessibility
Authors: Boos William 
Published: May 2006

In this article, unpublished methods of Solovay and Kunen are applied to describe conditions under which an uncountable regular κ can satisfy weak (κ, λ)-compactness (see 1.1(3) below), yet lie below 2μ for some μ < κ. The argumentation is in informal ZFC, and general set-theoretic notation is standard. The lower-case Greek letters κ, λ, μ, ν are reserved for cardinals in the sense of some transitive or inner model of a reasonable set theory, φ, Ψ, θ, are (arithmetizations of) formulas in some extension of the first-order language of set theory, and other lower-case Greek letters except Є are metavariables for arbitrary ordinals. If M is transitive, M ⊨ φ abbreviates 〈M, Є 〉 ⊨ φ. [2], [3], [9] and [1] provide more information about large-cardinal theory for those who wish it.1.1. Definitions. (1) κ is inaccessible iff κ is regular and ℵκ = κ; strongly inaccessible iff κ is regular and ℶκ = κ, i.e., λ < κ for all λ < κ; weakly inaccessible iff κ is inaccessible but not strongly inaccessible.(2) Lκλ is the infinitary language with conjunctions and disjunctions of length < κ and quantification over sequences of length < λ, and PLκ the prepositional language with κ letters and conjunctions and disjunctions of length < κ.
Probabilities on finite models
Authors: Fagin Ronald 
Published: May 2006

Let be a finite set of (nonlogical) predicate symbols. By an -structure, we mean a relational structure appropriate for . Let be the set of all -structures with universe {1, …, n}. For each first-order -sentence σ (with equality), let μn(σ) be the fraction of members of for which σ is true. We show that μn(σ) always converges to 0 or 1 as n → ∞, and that the rate of convergence is geometrically fast. In fact, if T is a certain complete, consistent set of first-order -sentences introduced by H. Gaifman [6], then we show that, for each first-order -sentence σ, μn(σ) →n 1 iff T ⊩ ω. A surprising corollary is that each finite subset of T has a finite model. Following H. Scholz [8], we define the spectrum of a sentence σ to be the set of cardinalities of finite models of σ. Another corollary is that for each first-order -sentence a, either σ or ˜σ has a cofinite spectrum (in fact, either σ or ˜σ is “nearly always“ true).Let be a subset of which contains for each in exactly one structure isomorphic to . For each first-order -sentence σ, let νn(σ) be the fraction of members of which a is true. By making use of an asymptotic estimate [3] of the cardinality of and by our previously mentioned results, we show that vn(σ) converges as n → ∞, and that limn νn(σ) = limn μn(σ).If contains at least one predicate symbol which is not unary, then the rate of convergence is geometrically fast.
Applications of vaught sentences and the covering theorem
Authors: Harnik Victor , Makkai Michael 
Published: May 2006

AbstractWe use a fundamental theorem of Vaught, called the covering theorem in [V] (cf. theorem 0.1 below) as well as a generalization of it (cf. Theorem 0.1* below) to derive several known and a few new results related to the logic . Among others, we prove that if every countable model in a PCφ1ω class has only countably many automorphisms, then the class has either ≤ℵ0 or exactly nonisomorphic countable members (cf. Theorem 4.3*) and that the class of countable saturated structures of a sufficiently large countable similarity type is not among countable structures (cf. Theorem 5.2). We also give a simple proof of the Lachlan-Sacks theorem on bounds of Morley ranks (§7).
A Boolean ultrapower which is not an ultrapower
Authors: Koppelberg Bernd , Koppelberg Sabine 
Published: May 2006

Several people have independently been studying Boolean ultrapowers recently; see for example [2], [3], [4], [6]. Boolean ultrapowers are a quite natural generalization of the well-known usual ultrapowers, but it seemed to be unknown whether every Boolean ultrapower is isomorphic to an ultrapower. We give a negative answer to that question. We further show that a Boolean ultrapower by an ℵ1-regular ultrafilter need not be ℵ2-universal, i.e. that Theorem 4.3.12 of [1] does not hold for Boolean ultrapowers.Let B be a complete Boolean algebra (we identify the algebra with its underlying set), whose operations are denoted by +, ·, −, 0, 1, Σ, Π Let be a structure for some language ℒ.
Minimal upper bounds for ascending sequences of α-recursively enumerable degrees
Authors: Chong C. T. 
Published: May 2006

Let a be an admissible ordinal and let ∧ ≤ α be a limit ordinal. A sequence of a-r.e. degrees is said to be ascending, simultaneous and of length ∧ if (i) there is an α-recursive function t: α × ∧ → α such that, for all ϒ < ∧, Aϒ = {t(σ, ϒ)∣ σ < α} is of degree aϒ; (ii) if ϒ < ⊤ < ∧, then aϒ ≤αaτ and (iii) for all ϒ < ∧, there is a ⊤ > ϒ with aϒ, >αaϒ. Lerman [4] showed that such an exists for every ∧ ≤ α. An upper bound a of is an α-r.e. degree in which every element of is α-recursive. a is minimal if there is no α-r.e. degree b <αa which is also an upper bound of . Sacks [6] proved that every ascending sequence of simultaneously ω-r.e. degrees of length ω cannot have 0ω′, the complete ω-r.e. degree, as a minimal upper bound. In contrast, Cooper [2] showed that there exists an ascending sequence of simultaneously ω-r.e. degrees of length to having a minimal upper bound which is an ω-r.e. degree. In this paper we investigate the behavior of ascending sequences of simultaneously α-r.e. degrees for admissible ordinals α > ω. Call α Σ∞-admissibIe if it is Σn-nadmissible for all n. Let Φ(∧) say: No ascending sequence of simultaneously α-r.e. degrees of length ∧ can have 0α′, the complete α-r.e. degree, as a minimal upper bound. Our main result in this paper is:Let α be either a constructible cardinal with σ2ci(α) < α or Σ∞-admissible. Then σ2cf(α) is the least ordinal ν for which every ∧ ≤ α of cofinality ν (over Lα) can satisfy Φ(∧).
On models with power-like orderings
Authors: Shelah Saharon 
Published: May 2006

We prove here theorems of the form: if T has a model M in which P1(M) is κ1-like ordered, P2(M) is κ2-like ordered …, and Q1(M) is of power λ1, …, then T has a model N in which P1(M) is κ1′-like ordered …, Q1(N) is of power λ1′, …. (In this article κ is a strong-limit singular cardinal, and κ′ is a singular cardinal.)We also sometimes add the condition that M, N omits some types. The results are seemingly the best possible, i.e. according to our knowledge about n-cardinal problems (or, more precisely, a certain variant of them).
A reduction theorem for predicate logic
Authors: Löb M. H. 
Published: May 2006

It is well known that in prepositional logic not every propositional connective is definable in terms of equivalence nor indeed in terms of equivalence together with negation. It is the purpose of this note to show that in a certain sense this is, however, possible within predicate logic.Let F1 be the class of predicate logical formulae containing only the logical connectives ¬ (not), ∨ (or), E (exists), and F2 the class of predicate logical formulae containing only the logical connectives ≡ (if and only if) and E.Our object will be to find a method for reducing any formulae ϕ of F1 to a formula ψ of F2 such that ϕ is valid if and only if ψ is valid.Note first that for every domain D containing at least two individuals we can for every n-place relation R defined over D find an n + 1-place relation S defined over D such that for all x1, …, xn ∈ D,holds. For instance, let S(y, x1, …, xn) be the relation y = x1 & R(x1, …, xn).Now let ϕ be an arbitrary formula of F1 and A1, …, A3 a complete list of predicate letters occurring in ϕ of degree g1, …, gi, respectively. Let ϕ′ be the formula obtained from ϕ by replacing every prime formula Ai(x1, …, xgi) byThen it follows immediately from the previous observation that (a) ϕ is satisfiable in D if and only if ϕ′ is satisfiable in D.
Noninitial segments of the α-degrees
Authors: Macintyre John M. 
Published: May 2006

Let α be an admissible ordinal and let L be the first order language with equality and a single binary relation ≤. The elementary theory of the α-degrees is the set of all sentences of L which are true in the universe of the α-degrees when ≤ is interpreted as the partial ordering of the α-degrees. Lachlan [6] showed that the elementary theory of the ω-degrees is nonaxiomatizable by proving that any countable distributive lattice with greatest and least members can be imbedded as an initial segment of the degrees of unsolvability. This paper deals with the extension of these results to α-recursion theory for an arbitrary countable admissible α > ω. Given α, we construct a set A with α-degree a such that every countable distributive lattice with greatest and least member is order isomorphic to a segment of α-degrees {d ∣ a ≤αd≤αb} for some α-degree b. As in [6] this implies that the elementary theory of the α-degrees is nonaxiomatizable and hence undecidable.A is constructed in §2. A is a set of integers which is generic with respect to a suitable notion of forcing. Additional applications of such sets are summarized at the end of the section. In §3 we define the notion of a tree and construct a particular tree T0 which is weakly α-recursive in A. Using T0 we can apply the techniques of [6] and [2] to α-recursion theory. In §4 we reduce our main results to three technical lemmas concerning systems of trees. These lemmas are proved in §5.
Rowbottom cardinals and Jonsson cardinals are almost the same
Authors: Kleinberg E. M. 
Published: May 2006

Each of the various “large cardinal” axioms currently studied in set theory owes its inspiration to concrete phenomena in various fields. For example, the statement of the well-known compactness theorem for first-order logic can be generalized in various ways to infinitary languages to yield definitions of compact cardinals, and the reflection principles provable in ZF, when modified in the appropriate way, yields indescribable cardinals.In this paper we concern ourselves with two kinds of large cardinals which are probably the two best known of those whose origins lie in model theory. They are the Rowbottom cardinals and the Jonsson cardinals.Let us be more specific. A cardinal κ is said to be a Jonsson cardinal if every structure of cardinality κ has a proper elementary substructure of cardinality κ. (It is routine to see that only uncountable cardinals can be Jonsson. Erdös and Hajnal have shown [2] that for n < ω no ℵn is Jonsson. (In fact, they showed that if κ is not Jonsson then neither is the successor cardinal of κ and that, assuming GCH, no successor cardinal can be Jonsson.) Keisler and Rowbottom first showed that the existence of a Jonsson cardinal contradicts V = L.) The definition of a Rowbottom cardinal is only slightly more intricate. We assume for the moment that our similarity type has a designated one-place relation.
Solution to the P − W problem
Authors: Martin E.P. , Meyer R.K. 
Published: May 2006

Anderson and Belnap asked in §8.11 of their treatise Entailment [1] whether a certain pure implicational calculus, which we will call P − W, is minimal in the sense that no two distinct formulas coentail each other in this calculus. We provide a positive solution to this question, variously known as The P − W problem, or Belnap's conjecture.We will be concerned with two systems of pure implication, formulated in a language constructed in the usual way from a set of propositional variables, with a single binary connective →. We use A, B,…, A1, B1, …, as variables ranging over formulas. Formulas are written using the bracketing conventions of Church [3].The first system, which we call S (in honour of its evident incorporation of syllogistic principles of reasoning), has as axioms all instances of
(B) B → C →. A → B →. A → C (prefixing),(B) A → B →. B → C →. A → C (suffixing),
and rules
(BX) from B → C infer A → B →. A → C (rule prefixing),(B’X) from A → B infer B → C →. A → C (rule suffixing),(BXY) from A → B and B → C infer A → C (rule transitivity).The second system, P − W, has in addition to the axioms and rules of S the axiom scheme
(I) A → A
of identity.We write ⊢SA (⊣SA) to mean that A is (resp. is not) a theorem of S, and similarly for P − W.
An introduction to forking
Authors: Lascar Daniel , Poizat Bruno 
Published: May 2006

The notion of forking has been introduced by Shelah, and a full treatment of it will appear in his book on stability [S1]. The principal aim of this paper is to show that it is an easy and natural notion.Consider some well-known examples of ℵ0-stable theories: vector spaces over Q, algebraically closed fields, differentially closed fields of characteristic 0; in each of these cases, we have a natural notion of independence: linear, algebraic and differential independence respectively. Forking gives a generalization of these notions. More precisely, if are subsets of some model and c a point of this model, the fact that the type of c over does not fork over means that there are no more relations of dependence between c and than there already existed between c and . In the case of the vector spaces, this means that c is in the space generated by only if it is already in the space generated by . In the case of differentially closed fields, this means that the minimal differential equations of c with coefficient respectively in and have the same order. Of course, these notions of dependence are essential for the study of the above mentioned structures. Forking is no less important for stable theories. A glance at Shelah's book will convince the reader that this is the case.What we have to do is the following. Assuming T stable and given and p a type on , we want to distinguish among the extensions of p to some of
them that we shall call the nonforking extensions of p.
On the category of models of a complete theory
Authors: Lascar Daniel 
Published: May 2006

Let T be a countable complete theory and C(T) the category whose objects are the models of T and morphisms are the elementary maps. The main object of this paper will be the study of C(T). The idea that a better understanding of the category may give us model theoretic information about T is quite natural: The (semi) group of automorphisms (endomorphisms) of a given structure is often a powerful tool for studying this structure. But certainly, one of the very first questions to be answered is: “to what extent does this category C(T) determine T?”There is some obvious limitation: for example let T0 be the theory of infinite sets (in a language containing only =) and T1 the theory, in the language ( =, U(ν0),f(ν0)) stating that:(1) U is infinite.(2)f is a bijective map from U onto its complement.It is quite easy to see that C(T0) is equivalent to C(T1). But, in this case, T0 and T1 can be “interpreted” each in the other. To make this notion of interpretation precise, we shall associate with each theory T a category, loosely denoted by T, defined as follows:(1) The objects are the formulas in the given language.(2) The morphisms from into are the formulas such that(i.e. f defines a map from ϕ into ϕ; two morphisms defining the same map in all models of T should be identified).