bluuebunny/crossref_metadata_2025_split huggingface dataset:
Effective aspects of profinite groups
Authors: Smith Rick L. 
Published: May 2006

Profinite groups are Galois groups. The effective study of infinite Galois groups was initiated by Metakides and Nerode [8] and further developed by LaRoche [5]. In this paper we study profinite groups without considering Galois extensions of fields. The Artin method of representing a finite group as a Galois group has been generalized (effectively!) by Waterhouse [14] to profinite groups. Thus, there is no loss of relevance in our approach.The fundamental notions of a co-r.e. profinite group, recursively profinite group, and the degree of a co-r.e. profinite group are defined in §1. In this section we prove that every co-r.e. profinite group can be effectively represented as an inverse limit of finite groups. The degree invariant is shown to behave very well with respect to open subgroups and quotients. The work done in this section is basic to the rest of the paper.The commutator subgroup, the Frattini subgroup, thep-Sylow subgroups, and the center of a profinite group are essential in the study of profinite groups. It is only natural to ask if these subgroups are effective. The following question exemplifies our approach to this problem: Is the center a co-r.e. profinite group? Theorem 2 provides a general method for answering this type of question negatively. Examples 3,4 and 5 are all applications of this theorem.
The theory of all substructures of a structure: Characterisation and decision problems
Authors: Manders Kenneth L. 
Published: May 2006

AbstractAn infinitary characterisation of the first-order sentences true in all substructures of a structure M is used to obtain partial reduction of the decision problem for such sentences to that for Th(M). For the relational structure 〈R, ≤, + 〉 this gives a decision procedure for the ∃x∀y-part of the theory of all substructures, yet we show that the ∃x1x2∀y-part, and the entire theory, is Π11-complete. The theory of all ordered subsemigroups of 〈R, ≤, + 〉 is also shown Π11-complete. Applications in the philosophy of science are mentioned.
A note on finitely generated models
Authors: Pillay Anand 
Published: May 2006

A model M (of a countable first order language) is said to be finitely generated if it is prime over a finite set, namely if there is a finite tuple ā in M such that (M, ā) is a prime model of its own theory. Similarly, if A ⊂ M, then M is said to be finitely generated overA if there is finite ā in M such that M is prime over A ⋃ ā. (Note that if Th(M) has Skolem functions, then M being prime over A is equivalent to M being generated by A in the usual sense, that is, M is the closure of A under functions of the language.) We show here that if N is ā model of an ω-stable theory, M ≺ N, M is finitely generated, and N is finitely generated over M, then N is finitely generated. A corollary is that any countable model of an ω-stable theory is the union of an elementary chain of finitely generated models. Note again that all this is trivial if the theory has Skolem functions.The result here strengthens the results in [3], where we show the same thing but assuming in addition that the theory is either nonmultidimensional or with finite αT. However the proof in [3] for the case αT finite actually shows the following which does not assume ω-stability): Let A be atomic over a finite set, tp(ā / A) have finite Cantor-Bendixson rank, and B be atomic over A ⋃ ā. Then B is atomic over a finite set.
Models and reality
Authors: Putnam Hilary 
Published: May 2006

In 1922 Skolem delivered an address before the Fifth Congress of Scandinavian Mathematicians in which he pointed out what he called a “relativity of set-theoretic notions”. This “relativity” has frequently been regarded as paradoxical; but today, although one hears the expression “the Löwenheim-Skolem Paradox”, it seems to be thought of as only an apparent paradox, something the cognoscenti enjoy but are not seriously troubled by. Thus van Heijenoort writes, “The existence of such a ‘relativity’ is sometimes referred to as the Löwenheim-Skolem Paradox. But, of course, it is not a paradox in the sense of an antinomy; it is a novel and unexpected feature of formal systems.” In this address I want to take up Skolem's arguments, not with the aim of refuting them but with the aim of extending them in somewhat the direction he seemed to be indicating. It is not my claim that the “Löwenheim-Skolem Paradox” is an antinomy in formal logic; but I shall argue that it is an antinomy, or something close to it, in philosophy of language. Moreover, I shall argue that the resolution of the antinomy—the only resolution that I myself can see as making sense—has profound implications for the great metaphysical dispute about realism which has always been the central dispute in the philosophy of language.The structure of my argument will be as follows: I shall point out that in many different areas there are three main positions on reference and truth: there is the extreme Platonist position, which posits nonnatural mental powers of directly “grasping” forms (it is characteristic of this position that “understanding” or “grasping” is itself an irreducible and unexplicated notion); there is the verificationist position which replaces the classical notion of truth with the notion of verification or proof, at least when it comes to describing how the language is understood; and there is the moderate realist position which seeks to preserve the centrality of the classical notions of truth and reference without postulating nonnatural mental powers.
Independence results
Authors: Shelah Saharon 
Published: May 2006

AbstractWe prove independence results concerning the number of nonisomorphic models (using the S-chain condition and S-properness) and the consistency of “ there is a universal linear order of power ℵ1”. Most of these results were announced in [Sh 4], [Sh 5].In subsequent papers we shall prove an analog f MA for forcing which does not destroy stationary subsets of ω1 investigate -properness for various filters and prove the consistency with G.C.H. of an axiom implying SH (for ℵ1), and connected results.
A sequent calculus formulation of type assignment with equality rules for the λβ-calculus
Authors: Seldin Jonathan P. 
Published: May 2006

In [1, §14E], a sequent calculus formulation (L.-formulation) of type assignment (theory of functionality) is given for a system based either on a system of combinators with strong reduction or on a system of λη-calculus provided that the rule for subject conversion (which says that if X has type α and X cnv Y then Y has type α) is postulated for the system. This sequent calculus formulation does not work for a system based on the λβ-calculus. In [2] I introduced a sequent calculus formulation for a system without the rule of subject conversion based on any of the three systems mentioned above. Further, in [2, §5] I pointed out that if proper inclusions of the form of the statement that λx·x is a function from α to β are postulated, then functions are identified with their restrictions in the λη-calculus but not in the λβ-calculus, and that therefore there is some interest in having a sequent calculus formulation of type assignment with the rule of subject conversion for systems based on the λβ-calculus. In this paper, such a system is presented, the elimination theorem (Gentzen's Hauptsatz) is proved for it, and it is proved equivalent to the natural deduction formulation of [1, §14D].I shall assume familiarity with the λβ-calculus, and shall use (with minor modifications) the notational conventions of [1]. Hence, the theory of type assignment (theory of functionality) will be based on an atomic constant F such that if α and β are types then Fαβ represents roughly the type of functions from α to β (more exactly it represents the type of functions whose domain includes α and under which the image of α is included in β).
Minimal upper bounds for sequences of -degrees
Authors: Kechris Alexander S. 
Published: May 2006

It is proved here, assuming Projective Determinacy, that every ascending sequence of -degrees has a minimal strict upper bound but no least strict upper bound. This generalizes a result of Friedman for n = 1.Our general notation and terminology will be that of [Ke1] and [Mo1]. Letters i,j, k,… denote members of ω and α, β, ϒ,… members of ωω i.e. reals. Projective Determinacy (PD) is the hypothesis that every projective set of reals in determined, while in general for a collection of sets of reals Γ, Determinacy (Γ) abbreviates the statement that every set in Γ is determined.§1. -degrees. For each m ≥ 1 and α, β Є ωω let α ≤mβ ⇔ α Є (β), α <mβ ⇔ α ≤mβ ∧ β ≰mα, and α ≡mβ ⇔ α ≤mβ ∧ β ≤mα.Clearly ≡m is an equivalence relation on ωω. The ≡m -equivalence class of α Є ωω is called its -degree, in symbolsIf d = [α]m, e = [β]m then we define
An addendum to “The work of Kurt Gödel”
Authors: Kleene Stephen C. 
Published: May 2006

Gödel has called to my attention that p. 773 is misleading in regard to the discovery of the finite axiomatization and its place in his proof of the consistency of GCH. For the version in [1940], as he says on p. 1, “The system Σ of axioms for set theory which we adopt [a finite one] … is essentially due to P. Bernays …”. However, it is not at all necessary to use a finite axiom system. Gödel considers the more suggestive proof to be the one in [1939], which uses infinitely many axioms.His main achievement regarding the consistency of GCH, he says, really is that he first introduced the concept of constructible sets into set theory defining it as in [1939], proved that the axioms of set theory (including the axiom of choice) hold for it, and conjectured that the continuum hypothesis also will hold. He told these things to von Neumann during his stay at Princeton in 1935. The discovery of the proof of this conjecture On the basis of his definition is not too difficult. Gödel gave the proof (also for GCH) not until three years later because he had fallen ill in the meantime. This proof was using a submodel of the constructible sets in the lowest case countable, similar to the one commonly given today.
The slow-growing and the Graegorczyk hierarchies
Authors: Cichon E.A. , Wainer S.S. 
Published: May 2006

We give here an elementary proof of a recent result of Girard [4] comparing the rates of growth of the two principal (and extreme) examples of a spectrum of “majorization hierarchies”—i.e. hierarchies of increasing number-theoretic functions, indexed by (systems of notations for) initial segments I of the countable ordinals so that if α < β ∈ I then the βth function dominates the αth one at all but finitely-many positive integers x.Hardy [5] was perhaps the first to make use of a majorization hierarchy—the Hα's below—in “exhibiting” a set of reals with cardinality ℵ1. More recently such hierarchies have played important roles in mathematical logic because they provide natural classifications of recursive functions according to their computational complexity. (All the functions considered here are “honest” in the sense that the size of their values gives a measure of the number of steps needed to compute them.)The hierarchies we are concerned with fall into three main classes depending on their mode of generation at successor stages, the other crucial parameter being the initial choice of a particular (standard) fundamental sequence λ0 < λ1 < λ2 < … to each limit ordinal λ under consideration which, by a suitable diagonalization, will then determine the generation at stage λ.Our later comparisons will require the use of a “large” initial segment I of proof-theoretic ordinals, extending as far as the “Howard ordinal”. However we will postpone a precise description of these ordinals and their associated fundamental sequences until later.
Completeness in the theory of properties, relations, and propositions
Authors: Bealer George 
Published: May 2006

Higher-order theories of properties, relations, and propositions (PRPs) are known to be essentially incomplete relative to their standard notions of validity. There is, however, a first-order theory of PRPs that results when standard first-order logic is supplemented with an operation of intensional abstraction. It turns out that this first-order theory of PRPs is provably complete with respect to its standard notions of validity. The construction involves the development of a new algebraic semantic method. Unlike most other methods used in contemporary intensional logic, this method does not appeal to possible worlds as a heuristic; the heuristic used is that of PRPs taken as primitive entities. This is important, for even though the possible-worlds approach is useful in treating modal logic, it seems to be of little help in treating the logic for psychological matters. The present approach, by contrast, appears to make a step in the direction of a satisfactory treatment of both modal and intentional logic. For, by taking PRPs as primitive entities, we remain free to tailor the statement of their identity conditions so that it agrees with the logical data—modal, psychological, etc. In this way, the present approach suggests a strategy for developing a comprehensive treatment of intensional logic.In [1] and [2] I explore this prospect philosophically. The purpose of the present paper is to lay out the technical details of the approach and to present the completeness results.
The decidability of normal K5 logics
Authors: Nagle Michael C. 
Published: May 2006

The literature on modal logic includes a number of general completeness and decidability results. The work of Schiller Joe Scroggs [5], R.A. Bull [1], Kit Fine [2], and Krister Segerberg [6] provide examples.Scroggs showed that the proper extensions of S5 have the finite model property and are axiomatizable. (Harrop [3] then argued that logics having these properties are decidable.) Bull extended Scroggs' result by showing that the normal extensions of S4.3 have the finite model property. Fine subsequently provided a model-theoretic proof of Bull's result and also proved the axiomatizability of these logics. In a different direction Segerberg proved that every normal logic containing the characteristic axioms of Lewis' systems S4 and S5 is decidable.The present paper is in this tradition. We extend the results of Scroggs and Segerberg by showing that every normal modal logic containing the S5 axiom has the finite model property, is axiomatizable, and thus is decidable.
Effective Galois theory
Authors: Roche Peter La 
Published: May 2006

Krull [4] extended Galois theory to arbitrary normal extensions, in which the Galois groups are precisely the profinite groups (i.e. totally disconnected, compact, Hausdorff groups). Metakides and Nerode [7] produced two recursively presented algebraic extensionsK⊂Fof the rationals such thatFis abelian,Fis of infinite degree overK, and the Galois group ofFoverK, although of cardinalityc, has only one recursive element (viz. the identity). This indicated the limits of effectiveness for Krull's theory. (The Galois theory offiniteextensions is completely effective.) Nerode suggested developing a natural effective version of Krull's theory (done here in §1).It is evident from the classical literature that the free profinite group on denumerably many generators can be obtained effectively as the Galois group of a recursive extension of the rationals over a subfield. Nerode conjectured that it could be obtained effectively as the Galois group of the algebraic numbers over a suitable subfield (done here in §2). The case of finitely many generators was done non-effectively by Jarden [3]. The author believes that the denumerable case, as presented in §2, is also new classically. Using this result and the effective Krull theory, every “co-recursively enumerable” profinite group is effectively the Galois group of a recursively enumerable field of algebraic numbers over a recursive subfield.
Model-complete theories of e-free Ax fields
Authors: Jarden Moshe , Wheeler William H. 
Published: May 2006

This paper's goal is to determine which complete theories of perfect, e-free Ax fields are model-complete. A field K is e-free for a positive integer e if the Galois group g(KS∣K), where Ks is the separable closure of K, is an e-free, profinite group. A perfect field K is pseudo-algebraically closed if each nonvoid, absolutely irreducible variety defined over K has a K-rational point. A perfect, pseudo-algebraically closed field is called an Ax field. The main theorem isA complete theory of e-free Ax fields is model-complete if and only if its field of absolute numbers is e-free.The sufficiency of the latter condition is an easy consequence of a result of Moshe Jarden and Ursel Kiehne [10] and has been noted independently by A. Macintyre and K. McKenna and undoubtedly by others as well. Consequently the necessity of the latter condition is the interesting part of this paper.James Ax [3] initiated the investigation of 1-free Ax fields. He proved that these fields, which he called pseudo-finite fields, are precisely the infinite models of the theory of finite fields. He [3] also presented examples of perfect, 1-free fields which are not pseudo-algebraically closed and an example of a 1-free Ax field whose complete theory is not model-complete. Moshe Jarden [5] showed that the first examples are isolated cases in that almost all, perfect, 1-free, algebraic extensions of a denumerable, Hilbertian field are pseudo-algebraically closed. The results in this paper show that the second example is also an isolated case in that almost all complete theories of 1-free Ax fields are model-complete.
Predicate functors revisited
Authors: Quine W. V. 
Published: May 2006

Quantification theory, or first-order predicate logic, can be formulated in terms purely of predicate letters and a few predicate functors which attach to predicates to form further predicates. Apart from the predicate letters, which are schematic, there are no variables. On this score the plan is reminiscent of the combinatory logic of Schönfinkel and Curry. Theirs, however, had the whole of higher set theory as its domain; the present scheme stays within the bounds of predicate logic.In 1960 I published an apparatus to this effect, and an improved version in 1971. In both versions I assumed two inversion functors, major and minor; also a cropping functor and the obvious complement functor. The effects of these functors, when applied to an n-place predicate, are as follows:The variables here are explanatory only and no part of the final notation. Ultimately the predicate letters need exponents showing the number of places, but I omit them in these pages.A further functor-to continue now with the 1971 version-was padding:Finally there was a zero-place predicate functor, which is to say simply a constant predicate, namely the predicate ‘I’ of identity, and there was a two-place predicate functor ‘∩’ of intersection. The intersection ‘F ∩ G’ received a generalized interpretation, allowing ‘F’ and ‘G’ to be predicates with unlike numbers of places. However, Steven T. Kuhn has lately shown me that the generalization is unnecessary and reducible to the homogeneous case.
The extensions of the modal logic K5
Authors: Nagle Michael C. , Thomason S. K. 
Published: May 2006

Our purpose is to delineate the extensions (normal and otherwise) of the propositional modal logic K5. We associate with each logic extending K5 a finitary index, in such a way that properties of the logics (for example, inclusion, normality, and tabularity) become effectively decidable properties of the indices. In addition we obtain explicit finite axiomatizations of all the extensions of K5 and an abstract characterization of the lattice of such extensions.This paper refines and extends the Ph.D. thesis [2] of the first-named author, who wishes to acknowledge his debt to Brian F. Chellas for his considerable efforts in directing the research culminating in [2] and [3]. We also thank W. J. Blok and Gregory Cherlin for observations which greatly simplified the proofs of Theorem 3 and Corollary 10.By a logic we mean a set of formulas in the countably infinite set Var of propositional variables and the connectives ⊥, →, and □ (other connectives being used abbreviatively) which contains all the classical tautologies and is closed under detachment and substitution. A logic is classical if it is also closed under RE (from A↔B infer □A ↔□B) and normal if it is classical and contains □ ⊤ and □ (P → q) → (□p → □q). A logic is quasi-classical if it contains a classical logic and quasi-normal if it contains a normal logic. Thus a quasi-normal logic is normal if and only if it is classical, and if and only if it is closed under RN (from A infer □A).
Gap-2 morasses of height ω
Authors: Velleman Dan 
Published: May 2006

In [3] we have shown how the simplification of gap-1 morasses introduced in [4] can be extended to gap-2 morasses. As in the gap-1 case, the definition of simplified (κ, 2)-morasses (gap-2 morasses of height κ) makes sense for κ = ω, although the smallest size for Jensen's original gap-2 morasses was κ = ω1. The existence of simplified gap-1 morasses of height ω is provable in ZFC (see [2]), but the same cannot be true for gap-2 morasses, since the top level of a simplified (ω, 2)-morass is a simplified (ω1, 1)-morass, and the existence of simplified (ω1, 1)-morasses is not provable in ZFC. In this paper we prove the best existence theorem for simplified (ω, 2)-morasses that we can hope for:Theorem 1.1. There is a simplified (ω, 2)-morass iff there is a simplified (ω1, 1)-morass.Before giving the proof we briefly summarize the definition of simplified (ω, 2)-morasses. For a more thorough treatment, and proofs of some of the basic properties of simplified gap-2 morasses which will be used below, we refer the reader to [3]. Suppose ‹‹φζ ∣ ζ ≤ ω1›, ‹ℊζξ ∣ ξ < ξ ≤ ω1›› is a simplified (ω1, 1)-morass. (We are using the “expanded” version of the definition.) We assume the morass is neat (see [4]). For each ζ < ω1 let σζ be the split point of ℊζ, ζ + 1; i.e., ℊζ, ζ + 1 is a pair {id, b}, where id is the identity function, b ↾ σζ = id and b(σζ) = φζ. A simplified (ω, 2)-morass will describe the construction of this simplified (ω, 1)-morass from finite pieces. The finite pieces will be the initial segments of the morass picked out by an increasing sequence of natural numbers ‹ni ∣ i < ω ›. We call this piece level i of the (ω, 2)-morass, and we call the full simplified (ω1, 1)-morass level ω. To make sure the pieces are really finite, we require that φx and ℊxy are finite for x < y < ω.
Monadic second order definable relations on the binary tree
Authors: Läuchli Hans , Savioz Christian 
Published: May 2006

AbstractLet S2S [WS2S] respectively be the strong [weak] monadic second order theory of the binary tree T in the language of two successor functions. An S2S-formula whose free variables are just individual variables defines a relation on T (rather than on the power set of T). We show that S2S and WS2S define the same relations on T, and we give a simple characterization of these relations.