bluuebunny/crossref_metadata_2025_split huggingface dataset:
Substance and first-order quantification over individual-concepts
Authors: Bacon John 
Published: May 2006

An individual-concept, hereinafter “individuation”, is a function from possible worlds to individuals. Constant individuations I will call “subsistents” (the notion will presently be generalized). A “substance”, after Thomason [35], is a subsistent whose value exists for the world at hand. In the systems of quantified modal logic developed over the past twenty years, the tendency has been to restrict the range of quantifiers to substances (often represented technically by the simple individuals that would be the values of the constant individuations), while allowing constant terms (particularly descriptions) to express arbitrary individuations. One result is to invalidate unrestricted universal instantiation (and existential generalization), rather as in free logic. Such systems approximate some features of ordinary usage rather nicely, e.g. the behavior of quantifiers and definite descriptions in tensed discourse. Stalnaker and Thomason's Q3r [34], based on the latter's Q3 [35], [36], is exemplary of this approach.The suggestion has repeatedly been considered to quantify over individuations in general (Kanger [14], Kaplan [17], Hughes and Cresswell [12, p. 196], Thomason [35, p. 136], Pollock [30]).
Constructible models of subsystems of ZF
Authors: Gostanian Richard 
Published: May 2006

AbstractOne of the main results of Gödel [4] and [5] is that, if M is a transitive set such that 〈M, Є 〉 is a model of ZF (Zermelo-Fraenkel set theory) and α is the least ordinal not in M, then 〈Lα, Є 〉 is also a model of ZF.In this note we shall use the Jensen uniformisation theorem to show that results analogous to the above hold for certain subsystems of ZF. The subsystems we have in mind are those that are formed by restricting the formulas in the separation and replacement axioms to various levels of the Levy hierarchy.This is all done in §1. In §2 we proceed to establish the exact order relationships which hold among the ordinals of the minimal models of some of the systems discussed in §1. Although the proofs of these latter results will not require any use of the uniformisation theorem, we will find it convenient to use some of the more elementary results and techniques from Jensen's fine-structural theory of L. We thus provide a brief review of the pertinent parts of Jensen's works in §0, where a list of general preliminaries is also furnished.We remark that some of the techniques which we use in the present paper have been used by us previously in [6] to prove various results about β-models of analysis. Since β-models for analysis are analogous to transitive models for set theory, this is not surprising.
On the ordering of certain large cardinals
Authors: Morgenstern Carl F. 
Published: May 2006

It is well known that the first strongly inaccessible cardinal is strictly less than the first weakly compact cardinal which in turn is strictly less than the first Ramsey cardinal, etc. However, once one passes the first measurable cardinal the inequalities are no longer strict. Magidor [3] has shown that the first strongly compact cardinal may be equal to the first measurable cardinal or equal to the first super-compact cardinal (the first supercompact cardinal is strictly larger than the first measurable cardinal). In this note we will indicate how Magidor's methods can be used to show that it is undecidable whether one cardinal (the first strongly compact) is greater than or less than another large cardinal (the first huge cardinal). We assume that the reader is familiar with the ultrapower construction of Scott, as presented in Drake [1] or Kanamori, Reinhardt and Solovay [2].Definition. A cardinal κ is huge (or 1-huge) if there is an elementary embedding j of the universe V into a transitive class M such that M contains the ordinals, is closed under j(κ) sequences, j(κ) > κ and j ↾ Rκ = id. Let κ denote the first huge cardinal, and let λ = j(κ).One can see from easy reflection arguments that κ and λ are inaccessible in V and, in fact, that κ is measurable in V.
An introduction to ω-extensions of ω-groups
Authors: Applebaum C. H. 
Published: May 2006

Let ε stand for the set of nonnegative integers (numbers), V for the class of all subcollections of ε(sets), Λ for the set of isols, ΛR for the set of regressive isols, and for the set of mappings from a subset of ε into ε (functions). If ƒ is a function we write δƒ and ρƒ for its domain and range, respectively. We denote the inclusion relation by ⊃ and proper inclusion by ⊊. The sets α and β are recursively equivalent [written: α ≃ β], if δƒ = α and ρƒ = β for some function ƒ with a one-to-one partial recursive extension. We denote the recursive equivalence type of a set α, {σ ∈ V ∣ σ ≃ α} by Req(α). The reader is assumed to be familiar with the contents of [1], [2], [3], and [6].The concept of an ω-group was introduced in [6], and that of an ω-homomorphism in [1]. However, except for a few examples, very little is known about the structure of ω-groups. If G is an ω-group and Π is an ω-homomorphism, then it follows that K = Ker Π and H = Π(G) are ω-groups. The question arises that if we know the structure of K and H, then what can we say about the structure of G? In this paper we will begin the study of ω-extensions, which will give us a partial answer to this question.
Conservative reduction classes of Krom formulas
Authors: Aanderaa Stål O. , Börger Egon , Lewis Harry R. 
Published: May 2006

AbstractA Krom formula of pure quantification theory is a formula in conjunctive normal form such that each conjunct is a disjunction of at most two atomic formulas or negations of atomic formulas. Every class of Krom formulas that is determined by the form of their quantifier prefixes and which is known to have an unsolvable decision problem for satisfiability is here shown to be a conservative reduction class. Therefore both the general satisfiability problem, and the problem of satisfiability in finite models, can be effectively reduced from arbitrary formulas to Krom formulas of these several prefix types.
Implicational logics in natural deduction systems
Authors: López-Escobar E.G.K. 
Published: May 2006

In 1959 M. Dummett [3] introduced the logic LC obtained by adding the axiom ACpqCqp to the formalization of the intuitionistic prepositional calculus having modus ponens and substitution as its rules of inference. Later on R. A. Bull [1] showed, by quite a roundabout way, that the implicational theses of LC were precisely the theses of the implicational calculus obtained by adding the axiom CCCpqrCCCqprr to the system of positive implication. In 1964 Bull [2] gave another proof, this time using results of Birkhoff concerning subdirectly reducible algebras.The aim of this short note is to emphasize that the use of Gentzen's natural deduction systems (see Prawitz [4]) allows us to give a much more direct proof.
Ordinal analysis of terms of finite type
Authors: Howard W. A. 
Published: May 2006

Sanchis [Sa] and Diller [Di] have introduced an interesting relation between terms for primitive recursive functionals of finite type in order to obtain a computability proof. The method is as follows. First the relation is shown to be well-founded. Then computability of each term is obtained by transfinite induction over the relation.Their relation is given by various clauses which define the (immediate) successors of a term. Hence, starting with a term H and repeatedly applying the successor relation one generates the tree of H (say). The problem is to prove that the trees are well-founded. In their proofs Sanchis and Diller use the axiom of bar induction. Diller also gives a proof using transfinite induction: each tree is shown to have a length b < φω(0) (the first ω-critical number) and the induction is over ordinals less than or equal to b.For proof-theoretic purposes it would be desirable to employ a method of proof which is more elementary than the axiom of bar induction and also to obtain a smaller ordinal bound. The purpose of the following is to provide such a method. We show that for a primitive recursive term H of finite type the tree generated by the relation of Sanchis and Diller has length less than ε0. Our method is similar to that used by Tait [Ta] in his theory of infinite terms. The immediately natural metamathematics is elementary intuitionistic analysis with the axiom of choice and transfinite induction over the relevant ordinal notations. We give several versions of the basic list of successor clauses, and for one version we show how to carry out the treatment in Skolem arithmetic (with primitive recursion of lowest type).
On a problem of MacDowell and Specker
Authors: Nadel Mark 
Published: May 2006

Let T extend the theory P of Peano arithmetic, and suppose . Form from a model , in analogy to the way in which the ordered ring of integers is formed from the standard model of arithmetic. Let P′ and T′ be the corresponding analogues of P and T respectively. Now consider the group . In [5] MacDowell and Specker set out to determine the structure of such groups. (The precise statement in [5] refers to the ring of integers rather than the ordered ring. However, as pointed out to us by J. Knight, since Lagrange's Theorem that a positive integer is the sum of four squares is provable in the analogue of P′ for rings (see, for example, the proof in [7, p. 102]), the set of positive elements is definable in the ring, and consequently, so is the ordering. Thus, for the present purpose it makes no difference which of the two structures is used. Of course, one needs the ordering to discuss end extensions, as considered in [5]. On the other hand, one should be aware that in Pr′ one cannot define an ordering, where the theory Pr′ is the theory of the group of integers with distinguished element 1, 〈Z, +, 1〉. The constant 1 is needed so that divisibility mod n can be expressed. We will return to this point later.) In §1 we shall outline the results in this direction obtained in [5].Lipshitz and Nadel, unaware that a similar question had been posed and investigated in [5] (though, of course aware that [5] contained the celebrated results on end extensions) set out to characterize those models 〈A, +〉 of Pr = Presburger Arithmetic (the complete theory of 〈ω, +〉) which can be expanded to models 〈A, +, ·, 0, 1, ≤〉 of P. They were able to give a complete characterization for countable models 〈A, +〉 in [4], which we describe in §2.
Kleene index sets and functional m-degrees
Authors: Mohrherr Jeanleah 
Published: May 2006

AbstractA many-one degree is functional if it contains the index set of some class of partial recursive functions but does not contain an index set of a class of r.e. sets. We give a natural embedding of the r.e. m-degrees into the functional degrees of 0′. There are many functional degrees in 0′ in the sense that every partial-order can be embedded. By generalizing, we show there are many functional degrees in every complete Turing degree.There is a natural tie between the studies of index sets and partial-many-one reducibility. Every partial-many-one degree contains one or two index sets.
Independence results for class forms of the axiom of choice
Authors: Howard Paul E. , Rubin Arthur L. , Rubin Jean E. 
Published: May 2006

AbstractLet NBG be von Neumann-Bemays-Gödel set theory without the axiom of choice and let NBGA be the modification which allows atoms. In this paper we consider some of the well-known class or global forms of the wellordering theorem, the axiom of choice, and maximal principles which are known to be equivalent in NBG and show they are not equivalent in NBGA.
α-Degrees of maximal α-r.e. sets
Authors: Leggett Anne 
Published: May 2006

Martin [10] has computed the degrees of several classes of ω-r.e. sets. Lachlan [3] and Shoenfield [14] have obtained some additional results. For most of the examples, a class of r.e. sets is given by a property that is first-order definable over the lattice of ω-r.e. sets. Then the set of degrees of sets in this class is computed. The only sets of nonzero degrees which arise from the known examples are the following: ϕ, {a∣a is ω-r.e. and a ≠ 0}, {a∣a is ω-r.e. and a′ = 0″}, and {a∣a is ω-r.e. and a″ > 0″} (see [14]).There have been some results in this direction for α an arbitrary admissible ordinal. Sacks [13] has shown that every nonzero α-r.e. α-degree contains a regular α-r.e. set. Thus regularity does not separate the α-r.e. α-degrees. Simpson [18] has several theorems which give information about the kinds of α-r.e. sets a given α-degree can contain. The classes of α-r.e. sets considered do separate the α-r.e. α-degrees into two nonempty pieces for some α's, but they are not necessarily given by properties which are definable over the lattice of α-r.e. sets. Using some definability results of Lerman [6], we shall make some comments about the definability of these classes of sets.
Recursively saturated nonstandard models of arithmetic
Authors: Smoryński C. 
Published: May 2006

Through the ability of arithmetic to partially define truth and the ability of infinite integers to simulate limit processes, nonstandard models of arithmetic automatically have a certain amount of saturation: Any encodable partial type whose formulae all fall into the domain of applicability of a truth definition must, by finite satisfiability and Overspill, be nonstandard-finitely satisfiable—whence realized. This fact was first exploited by A. Robinson, who in Robinson [1963] cited the unrealizability in a given model of a certain encodable partial type to prove Tarski's Theorem on the Undefinability of Truth. A decade later, H. Friedman brought this phenomenon to the public's attention by using it to establish impressive embeddability criteria for countable nonstandard models of arithmetic. Subsequently, Wilkie considered models expandable to “strong theories” and, among such models, complemented Friedman's embeddability criteria with elementary embeddability and isomorphism criteria. Oddly enough, the fact that some kind of saturation property was being employed was not explicitly acknowledged in any of this work.It is in the unpublished dissertation of Wilmers that these submerged saturation properties first surfaced. [As I have only seen accounts of it (most notably Murawski [1976/1977]) and not the dissertation itself, what I have to say about it will not quite be accurate. (Indeed, the referee has refuted, without providing alternate information, every conjecture I have made about the contents of this thesis.)
Patterns of projecta
Authors: Krawczyk Adam 
Published: May 2006

AbstractRoughly speaking, a pattern is a finite sequence coding the set of natural numbers n for which the Σn+1 projectum is less than the Σn projectum for a given admissible ordinal. We prove that for each pattern there exists an ordinal realizing it. Several results on the orderings of patterns are given. We conclude the paper with remarks on Δn projecta. The main technique, used throughout the paper, is Jensen's Uniformisation Theorem.
An example concerning Scott heights
Authors: Makkai M. 
Published: May 2006

Unless otherwise stated, every structure in this paper is countable in a countable, actually recursive language and every formula is one of .The definition of the so-called canonical Scott-sentence of a structure M, CSS(M) (compare Nadel [8]), is based on the ordinal invariant called the Scott-height of M, denoted SH(M) (compare Makkai [5]). To describe SH(M), let “b ≡αα”, for finite tuples of equal lengths b and a of elements of M and any ordinal α, stand for “b and a satisfy (in M) the same formulas of quantifier-rank ≤ α” (for the quantifier rank of a formula, see e.g., Barwise [1]); also, let “b ∼ a” mean that there is an automorphism of M mapping b to a. With a fixed M, and a in M, sh(a) (or shM(a)) denotes the least ordinal α such that for all b in M, b ≡αa implies b ∼ a. SH(M) is the least ordinal α such that for all a and b in M, b ≡αa implies b ∼ a; hence SH(M) = sup{sh(a): a in M}.
Algebraic independence
Authors: Knight Julia F. 
Published: May 2006

This paper is concerned with algebraic independence in structures that are relatively simple for their size. It is shown that for κ a limit cardinal, if a structure of power at least κ is ∞ω-equivalent to a structure of power less than κ, then must contain an infinite set of algebraically independent elements. The same method of proof yields the fact that if σ is an Lω1ω-sentence (not necessarily complete) and σ has a model of power ℵω then some model of σ contains an infinite algebraically independent set.All structures are assumed to be of countable similarity type. Letters , etc. will be used to denote either a structure or the universe of the structure. If X ⊆ , the algebraic closure of X (in ), denoted by Cl(X), is the union of all finite sets that are weakly definable (in ) by Lωω-formulas with parameters from X. A set S is algebraically independent if for each a in S, a ∉ Cl(S – {a}). An algebraically independent set is sometimes called a “free” set (in [3] and [4], for example).It is known (see [5]) that any structure of power ℵn must have a set of n algebraically independent elements, and there are structures of power ℵn with no independent set of size n + 1. In power ℵω every structure will have arbitrarily large finite algebraically independent sets. However, it is consistent with ZFC that some models of power ℵω do not have any infinite algebraically independent set. Devlin [4] showed that if V = L, then for any cardinal κ, if every structure of power κ has an infinite algebraically independent set, then κ has a certain large cardinal property that ℵω can never possess.
Wtt-degrees and T-degrees of r.e. sets
Authors: Stob Michael 
Published: May 2006

AbstractWe use some simple facts about the wtt-degrees of r.e. sets together with a construction to answer some questions concerning the join and meet operators in the r.e. degrees. The construction is that of an r.e. Turing degree a with just one wtt-degree in a such that a is the join of a minimal pair of r.e. degrees. We hope to illustrate the usefulness of studying the stronger reducibility orderings of r.e. sets for providing information about Turing reducibility.
A remark on Africk's paper on Scott's interpolation theorem for Lω1ω
Authors: Motohashi Nobuyoshi 
Published: May 2006

In order to prove that the Scott's interpolation theorem fails in Lω1ω, H. Africk proved the following lemma in [1]. (See [1] for notations.)Africk's Lemma. Suppose that and . Then every -sentence in Lω1ω is equivalent to a sentence of the form and a sentence of the form , where Ai,j, Bi,j, are Fj-sentences and there are only countable distinct Ai,j or Bi,j together.But this lemma is false as is shown in the following: Suppose that Z = {0,1}, Fj = {Pk,j}k⊂ω and . Let A be the sentence ⋀k⊂ω(∀xPk,0(x) ∨ ∀xPk,1(x)). If Africk's Lemma is true, then there are countably many Fj-sentences , such that A is equivalent to Since is countable, there are only countably many distinct pairs (Ai,0, Ai,1). So, we get a countable set {(Bi,0, Bi,1)}i⊂ω, such that A is equivalent to ⋁ik⊂ω(Bk,0 ∧ Bk,1). Since Bk,0 ∧ Bk,1 → ∀xPk,0(x) ∨ ∀xPk,1 is l-valid(i.e. valid in all first-order structures of cardinality 1) for every k ϵ ω, we have that either Bk,0 → ∀xPk,0(x) is 1-valid or Bk,0 → ∀xPk,1(x) is 1-valid. Let I be the set of all the k ϵ ω such that Bk,0 → ∀xPk,0(x) is 1-valid and the first-order structure defined by , , if k ϵ I and , if k ∉ I.
Some facts about Kurt Gödel
Authors: Wang Hao 
Published: May 2006

The text of this article was done together with Gödel in 1976 to 1977 and was approved by him at that time. The footnotes and section headings have been added much later.Gödel was born on April 28, 1906 at Brno (or Brünn in German), Czechoslovakia (at that time part of the Austro-Hungarian Monarchy). After completing secondary school there, he went, in 1924, to Vienna to study physics at the University. His interest in precision led him from physics to mathematics and to mathematical logic. He enjoyed much the lectures by Furtwangler on number theory and developed an interest in this subject which was, for example, relevant to his application of the Chinese remainder theorem in expressing primitive recursive functions in terms of addition and multiplication. In 1926 he transferred to mathematics and coincidentally became a member of the M. Schlick circle. However, he has never been a positivist, but accepted only some of their theses even at that time. Later on, he moved further and further away from them. He completed his formal studies at the University before the summer of 1929. He also attended during this period philosophical lectures by Heinrich Gomperz whose father was famous in Greek philosophy.At about this time he read the first edition of Hilbert-Ackermann (1928) in which the completeness of the (restricted) predicate calculus was formulated and posed as an open problem. Gödel settled this problem and wrote up the result as his doctoral dissertation which was finished and approved in the autumn of 1929. The degree was granted on February 6, 1930. A somewhat revised version of the dissertation was published in 1930 in the Monatshefte.
On a combinatorial principle of Hajnal and Komjáth
Authors: Velleman Dan 
Published: May 2006

In their paper [3], Hajnal and Komjáth define the following combinatorial principle:Definition 1.1. Suppose κ is an infinite cardinal and n < ω. Then Hn(κ) is the statement: There is a function F: [κ]n → [[κ]ω]≤ω such that(a) ∀A ∈[κ]n ∀Y ∈ F(A)(Y ⊆ min (A)), and(b) .Hn(κ) is related to a more general principle introduced by Hajnal and Nagy in [4]. For applications of these principles to free sets for set mappings and Ramsey games we refer the reader to [3] and [4].In [3] Hajnal and Komjáth prove the consistency of ZFC + GCH + ∀n ∈ ω(Hn + 1(ωn + 1)), relative to an ω-Mahlo cardinal. They conjecture that L is a model of this theory, and suggest that the proof might require higher gap morasses. The first few cases of this conjecture are known to be true; it is easy to see that if CH holds then H1 (ω1) is true, and Laver proved that V = L implies H2(ω2). In this paper we go one step further and prove V = L → H3(ω3). Unfortunately our methods do not appear to give Hn (ωn) for n ≥ 4.Most of our notation is standard. If X is any set and κ is a cardinal number then [X]κ is the set of subsets of X with cardinality κ, and [X]≤κ is the set of subsets of X with cardinality ≤ κ. If X is a set of ordinals then tp(X) is the order type of X.
Recursion in Kolmogorov's R-operator and the ordinal σ3
Authors: John Thomas 
Published: May 2006

The theory of objects recursive in functions of higher types was developed originally by Kleene [Kl 1,2]. The sets of objects of finite types are defined by Kleene as follows:T0 = ω = the set of nonnegative integers,and, for all i ∈ ω,Ti+1 = Tiω = the set of total functions from Ti to ω.In order to study and classify the functions recursive in Kolmogorov's R-operator, it is necessary to discuss recursion in partial functions of higher types. Accordingly, we define the partial objects of higher finite types byand, for all i ∈ ω, = the set of partial functions from Ti to ω.In addition to considering the partial functions from Ti to ω, the “hereditary partial” functions also have to be considered. For example, Hinman has studied objects of type 2 which act on partial functions from ω to ω. In case of dealing with a function F which has partial functions in its domain, we usually require that F be consistent, i.e. if F(f) is defined and g is an object of the same type as f, defined at least at all points where f is defined (in short, g extends f—notation: g ⊇ f), then F(g) is defined and is equal to F(f). Now we can define the higher type partial objects which are consistent byand, for all i ∈ ω, = the set of consistent partial functions from to ω.