bluuebunny/crossref_metadata_2025_split huggingface dataset:
One hundred and two problems in mathematical logic
Authors: Friedman Harvey 
Published: May 2006

This expository paper contains a list of 102 problems which, at the time of publication, are unsolved. These problems are distributed in four subdivisions of logic: model theory, proof theory and intuitionism, recursion theory, and set theory. They are written in the form of statements which we believe to be at least as likely as their negations. These should not be viewed as conjectures since, in some cases, we had no opinion as to which way the problem would go.In each case where we believe a problem did not originate with us, we made an effort to pinpoint a source. Often this was a difficult matter, based on subjective judgments. When we were unable to pinpoint a source, we left a question mark. No inference should be drawn concerning the beliefs of the originator of a problem as to which way it will go (lest the originator be us).The choice of these problems was based on five criteria. Firstly, we are only including problems which call for the truth value of a particular mathematical statement. A second criterion is the extent to which the concepts involved in the statements are concepts that are well known, well denned, and well understood, as well as having been extensively considered in the literature. A third criterion is the extent to which these problems have natural, simple and attractive formulations. A fourth criterion is the extent to which there is evidence that a real difficulty exists in finding a solution. Lastly and unavoidably, the extent to which these problems are connected with the author's research interests in mathematical logic.
Types of simple α-recursively enumerable sets
Authors: Leggett Anne , Shore Richard A. 
Published: May 2006

One general program of α-recursion theory is to determine as much as possible of the lattice structure of (α), the lattice of α-r.e. sets under inclusion. It is hoped that structure results will shed some light on whether or not the theory of (α) is decidable with respect to a suitable language for lattice theory. Fix such a language ℒ.Many of the basic results about the lattice structure involve various sorts of simple α-r.e. sets (we use definitions which are definable in ℒ over (α)). It is easy to see that simple sets exist for all admissible α. Chong and Lerman [1] have found some necessary and some sufficient conditions for the existence of hhsimple α-r.e. sets, although a complete determination of these conditions has not yet been made. Lerman and Simpson [9] have obtained some partial results concerning r-maximal α-r.e. sets. Lerman [6] has shown that maximal α-r.e. sets exist iff a is a certain sort of constructibly countable ordinal. Lerman [5] has also investigated the congruence relations, filters, and ideals of (α). Here various sorts of simple sets have also proved to be vital tools. The importance of simple α-r.e. sets to the study of the lattice structure of (α) is hence obvious.Lerman [6, Q22] has posed the following problem: Find an admissible α for which all simple α-r.e. sets have the same 1-type with respect to the language ℒ. The structure of (α) for such an α would be much less complicated than that of (ω). Lerman [7] showed that such an α could not be a regular cardinal of L. We show that there is no such admissible α.
Discernible elements in models for Peano arithmetic
Authors: Ehrenfeucht Andrzej 
Published: May 2006

Combinations of capital letters (e.g., G, EVEN) will be used as names of formulas of Peano arithmetic, x, y, z will be variables. Let be a model for Peano arithmetic. The names of formulas with a bar (e.g., G−, EVEN−(x)) will denote the relations defined by the formulas in . The elements of are called numbers.By a finite sequence of numbers 〈a0, …, an〉 we mean a number . Note that n Pi's and ai's can be nonstandard elements and therefore “finite,” and all concepts which will use it are not absolute but relative to .
Infinite exponent partition relations and well-ordered choice
Authors: Kleinberg E. M. , Seiferas J. I. 
Published: May 2006

The study of partition relations for cardinal numbers introduced by Erdös and his school in the 1950's has, for the past several years, had a profound impact in logic. Unfortunately, quite early in their development, it was noticed by Rado [1] that the potentially most fruitful class of such relations, infinite exponent partition relations, were always in contradiction with the axiom of choice (AC). As a result, such relations were overlooked. This turned out to be a mistake; for, as has been noticed recently, a close study of infinite exponent partition relations is both interesting and rewarding. For example, there are weakened versions of such relations which are provable in ZF and which have valuable applications in recursion theory and set theory. In addition, the pure theory of these relations, like that of the axiom of determinateness, is fruitful as well as elegant. For more background here one should refer to [3].At any rate, with a more detailed look at infinite exponent partition relations came a more refined version of Rado's original theorem. Specifically, Rado used the full axiom of choice to carefully construct partitions to violate any desired relation—a more sophisticated look at the actual theory of such relations indicated how one could put together some desired partitions using only well-ordered choice [3].The distinction between well-ordered choice and full choice is by no means vacuous in this context. For Mathias has shown [4] that the simplest infinite exponent partition relation, ω → (ω)ω, is consistent with countable choice (well-ordered choice of length ℵ0) and, in fact, is consistent with dependent choice.
Bounds for the closure ordinals of replete monotonic increasing functions
Authors: Schmidt Diana 
Published: May 2006

Whenever particular ordinals are used as tools in a proof or a definition, it is necessary to find a way of representing them. If the ordinals are sufficiently small, there is a standard way (e.g. Cantor normal forms for ordinals less than ε0); in general, representations are often found by using functions on initial segments of the ordinals: Each term which can be obtained from by applications of a function symbol is regarded as a notation for the ordinal obtained by the same applications of the function f to the ordinal 0. In this way, f provides representations for all the ordinals in Clf(0), the closure set of f (se e §1). (For an introduction to and development of this principle, see Feferman [F1]; and for a discussion of the significance of such representations in proof theory, see Kreisel [K1, pp. 22–34].) Thus it is natural to ask whether there are connections between frequently encountered properties of ordinal functions and the size of the ordinals for which they can provide representations.The purpose of this paper is to show that, for any integer n, the ordinal (see §2) is a bound for the closure ordinals of replete monotonic increasing n-place functions. This result is optimal for n > 2 (the bound is attained by where θα = 1 + α) but not for n < 2. D. H. de Jongh has recently proved, using a completely different method, that the (least possible) bound for n = 2 is ε0. (Trivially, that for n = 1 is φ.)
The nonderivability in intuitionistic formal systems of theorems on the continuity of effective operations
Authors: Beeson Michael J. 
Published: May 2006

The primary purpose of this work is to analyze the constructive interpretations of classical theorems concerning the continuity of effective operations. These theorems are the “recursivizations” of the statements that all functions (on various spaces) are continuous. To discuss the question whether these statements are constructively valid, it would be necessary to analyze the notion of “constructively valid,” which is beyond the scope of this paper. We now proceed to describe our results. We deal with two kinds of effective operations: (i) partial operations on indices of partial functions, and (ii) total operations on indices of total functions. The two principal theorems of the subject assert that each such operation is continuous; for (i) this is due to Myhill-Shepherdson [7] and called MS here; for (ii) it is due to Kreisel, Lacombe, and Shoenfield [5] and called KLS. (Explicit formulations of these and other principles mentioned in the introduction will be given in §1 below.)Several interpretations (of, e.g., Heyting's arithmetic HA) in the literature satisfy Markov's principle MP, and for these MS and KLS are valid, since a close inspection of the classical proofs of MS and KLS shows that they are derivable in HA + MP. But we also find an interpretation in the literature under which MS and KLS are valid while MP is not (hence MS and KLS do not imply MP in systems for which this interpretation is sound). This work is in §2.
Modal formulas are either elementary or not ΣΔ-elementary
Authors: van Benthem J. F. A. K. 
Published: May 2006

In this paper we prove that if L is a set of modal propositional formulas then FR(L) (the class of all frames in which every formula of L holds) is elementary, Δ-elementary or not ΣΔ-elementary. For single modal formulas the second of these cases does not occur.The model theoretic terminology and results used here are from [1]. (The underlying first order language contains only one, binary, predicate letter in addition to the identity symbol.) We presuppose familiarity with the usual notions and notations of propositional modal logic. A structure for our first order language is called a frame. (So a frame is an ordered couple 〈W, R〉 with domain W and R a binary predicate on W, i.e. a subset of W × W.) A valuation V on F is a function from the set of proposition letters to the power set of W. Using the well-known Kripke truth definition V can be extended to a function from the set of all modal propositional formulas to the power set of W. A modal propositional formula φ holds in a frame F (= 〈W, R〉) if, for all V on F, V(φ) = W. Notation: FR(φ) for the class of all frames in which φ holds. For a set L of modal propositional formulas we define FR(L) as ⋂φ∈LFR(φ). Obviously both FR(L) and cFR(L) (the complement of FR(L)) are closed under isomorphisms.
A counterexample in the theory of model companions
Authors: Saracino D. 
Published: May 2006

In [7] we proved that (I) if T is a countable ℵ0-categorical theory without finite models then T has a model companion; and several people have observed that (II) if T is a countable theory without finite models which is ℵ1-categorical and forcingcomplete for infinite forcing (i.e., T= TF) then T is model-complete. It is natural to ask (1) whether in (I) we can replace ℵ0 by ℵ1; (2) whether in (II) we can replace TF by Tf; and (3) in connection with (II), whether the categoricity of the class of infinitely generic structures for a theory K in some or all infinite powers implies the existence of a model companion for K. The purpose of this note is to provide negative answers to (1), (2), and (3). Specifically, we will prove:Theorem. There exists a countable theory T such that(i) T has no finite models and is ℵ-categorical;(ii) T is forcing-complete for finite forcing, i.e., T = Tf;(iii) T has no model companion (i.e., in light of (ii), T is not model-complete);(iv) the class of infinitely generic structures for T is categorical in every infinite power;(v) every uncountable existentially complete structure for T is infinitely generic;(vi) there is, up to isomorphism, precisely one countable existentially complete model of Tf, and there are no uncountable e.c. models of Tf (in particular, there is just one countable finitely generic structure and there are no uncountable ones);(vii) there are precisely ℵ0isomorphism types of countable existentially complete structures for T.
First-order definability in modal logic
Authors: Goldblatt R. I. 
Published: May 2006

In the early days of the development of Kripke-style semantics for modal logic a great deal of effort was devoted to showing that particular axiom systems were characterised by a class of models describable by a first-order condition on a binary relation. For a time the approach seemed all encompassing, but recent work by Thomason [6] and Fine [2] has shown it to be somewhat limited—there are logics not determined by any class of Kripke models at all. In fact it now seems that modal logic is basically second-order in nature, in that any system may be analysed in terms of structures having a nominated class of second-order individuals (subsets) that serve as interpretations of propositional variables (cf. [7]). The question has thus arisen as to how much of modal logic can be handled in a first-order way, and precisely which modal sentences are determined by first-order conditions on their models. In this paper we present a model-theoretic characterisation of this class of sentences, and show that it does not include the much discussed LMp → MLp.Definition 1. A modal frame ℱ = 〈W, R〉 consists of a set W on which a binary relation R is defined. A valuation V on ℱ is a function that associates with each propositional variable p a subset V(p) of W (the set of points at which p is “true”).
The word problem for free fields: a correction and an addendum
Authors: Cohn P. M. 
Published: May 2006

In [1] it was claimed that the word problem for free fields with infinite centre can be solved. In fact it was asserted that if K is a skew field with infinite central subfield C, then the word problem in the free field on a set X over K can be solved, relative to the word problem in K.As G. M. Bergman has pointed out (in a letter to the author), it is necessary to specify rather more precisely what type of problem we assume to be soluble for K: We must be able to decide whether or not a given finite set in K is linearly dependent over its centre. This makes it desirable to prove that the free field has a corresponding property (and not merely a soluble word problem). This is done in §2; interestingly enough it depends only on the solubility of the word problem in the free field (cf. Lemma 2 and Theorem 1′ below).Bergman also notes that the proof given in [1] does not apply when K is finite-dimensional over its centre; this oversight is rectified in §4, while §3 lifts the restriction on C (to be infinite). However, we have to assume C to be the precise centre of K, and not merely a central subfield, as claimed in [1].I am grateful to G. M. Bergman for pointing out the various inaccuracies as well as suggesting remedies.
Embedding first order predicate logic in fragments of intuitionistic logic
Authors: Löb M. H. 
Published: May 2006

Some syntactically simple fragments of intuitionistic logic possess considerable expressive power compared with their classical counterparts.In particular, we consider in this paper intuitionistic second order propositional logic (ISPL) a formalisation of which may be obtained by adding to the intuitionistic propositional calculus quantifiers binding propositional variables together with the usual quantifier rules and the axiom scheme (Ex), where is a formula not containing x.The main purpose of this paper is to show that the classical first order predicate calculus with identity can be (isomorphically) embedded in ISPL.It turns out an immediate consequence of this that the classical first order predicate calculus with identity can also be embedded in the fragment (PLA) of the intuitionistic first order predicate calculus whose only logical symbols are → and (.) (universal quantifier) and the only nonlogical symbol (apart from individual variables and parentheses) a single monadic predicate letter.Another consequence is that the classical first order predicate calculus can be embedded in the theory of Heyting algebras.The undecidability of the formal systems under consideration evidently follows immediately from the present results.We shall indicate how the methods employed may be extended to show also that the intuitionistic first order predicate calculus with identity can be embedded in both ISPL and PLA.For the purpose of the present paper it will be convenient to use the following formalisation (S) of ISPL based on [3], rather than the one given above.
Weak compactness and square bracket partition relations
Authors: Kleinberg E. M. , Shore R. A. 
Published: May 2006

Although there are many characterizations of weakly compact cardinals (e.g. in terms of indescnbability and tree properties as well as compactness) the most interesting set-theoretic (combinatorial) one is in terms of partition relations. To be more precise we define for κ and α cardinals and n an integer the partition relation of Erdös, Hajnal and Rado [2] as follows:For every function F: [κ]n→ α (called a partition of [κ]n, the n-element subsets of κ, into α pieces), there exists a set C⊆ κ (called homogeneous for F) such that card C = κ and F″[C]n≠ α, i.e. some element of the range is omitted when F is restricted to the n-element subsets of C. It is the simplest (nontrivial) of these relations, i.e. , that is the well-known equivalent of weak compactness.1Two directions of inquiry immediately suggest themselves when weak compactness is described in terms of these partition relations: (a) Trying to strengthen the relation by increasing the superscript—e.g., —and (b) trying to weaken the relation by increasing the subscript—e.g., . As it turns out, the strengthening to is only illusory for using the equivalence of to the tree property one quickly sees that implies (and so is equivalent to) for every n. Thus is the strongest of these partition relations. The second question seems much more difficult.
α-degrees of α-theories
Authors: Metakides George 
Published: May 2006

Let α be a limit ordinal with the property that any “recursive” function whose domain is a proper initial segment of α has its range bounded by α. α is then called admissible (in a sense to be made precise later) and a recursion theory can be developed on it (α-recursion theory) by providing the generalized notions of α-recursively enumerable, α-recursive and α-finite. Takeuti [12] was the first to study recursive functions of ordinals, the subject owing its further development to Kripke [7], Platek [8], Kreisel [6], and Sacks [9].Infinitary logic on the other hand (i.e., the study of languages which allow expressions of infinite length) was quite extensively studied by Scott [11], Tarski, Kreisel, Karp [5] and others. Kreisel suggested in the late '50's that these languages (even which allows countable expressions but only finite quantification) were too large and that one should only allow expressions which are, in some generalized sense, finite. This made the application of generalized recursion theory to the logic of infinitary languages appear natural. In 1967 Barwise [1] was the first to present a complete formalization of the restriction of to an admissible fragment (A a countable admissible set) and to prove that completeness and compactness hold for it. [2] is an excellent reference for a detailed exposition of admissible languages.
Simplifications of the recursion scheme
Authors: Gladstone M. D. 
Published: May 2006

This paper resolves 3 problems left open by R. M. Robinson in [3].We recall that the set of primitive recursive functions is the closure under (i) substitution (or “composition”), and (ii) recursion, of the set P consisting of the zero, successor and projection functions (see any textbook, for instance p. 120 of [2]).
Semantics for relevant logics
Authors: Urquhart Alasdair 
Published: May 2006

In what follows there is presented a unified semantic treatment of certain “paradox-free” systems of entailment, including Church's weak theory of implication (Church [7]) and logics akin to the systems E and R of Anderson and Belnap (Anderson [3], Belnap [6]). We shall refer to these systems generally as relevant logics.The leading idea of the semantics is that just as in modal logic validity may be defined in terms of certain valuations on a binary relational structure so in relevant logics validity may be defined in terms of certain valuations on a semilattice—interpreted informally as the semilattice of possible pieces of information. Completeness theorems can be given relative to these semantics for the implicational fragments of relevant logics. The semantical viewpoint affords some insights into the structure of the systems—in particular light is thrown upon admissible modes of negation and on the assumptions underlying rejection of the “paradoxes of material implication”.The systems discussed are formulated in fragments of a first-order language with → (entailment), &, ⋁, ¬,(x) and (∃x) primitive, omitting identity but including a denumerable list of propositional variables (p, q, r, p1,…etc.), and (for each n > 0), a denumerable list of n-ary predicate letters. The schematic letters A, B, C, D, A1,… are used on the meta-level as variables ranging over formulas. The conventions of Church [9] are followed in abbreviating formulas. The semantics of the systems are given in informal terms; it is an easy matter to turn the informal descriptions into formal set-theoretical definitions.
Nonrecursive tilings of the plane. II
Authors: Myers Dale 
Published: May 2006

We show that there is a finite set of tiles which can tile the plane but not in any recursive way. This answers a natural sequel to Hao Wang's problem of the existence of a finite set of tiles which can tile the plane but not in any periodic way. In the proof, an elaboration of Robinson's method of transforming origin-constrained problems into unconstrained problems is applied to Hanf's origin-constrained tiling of Part I. We will assume familiarity with §§2, 3, and 7 of [3].Following Robinson, we will mark the edges of our tiles with symbols and configurations of arrow heads and tails as well as with colors. The matching condition for abutting tiles will be that the symbols on adjacent edges must be identical, every arrow head must match with a tail, every tail with a head, and the colors must be the same. This is, of course, mathematically equivalent to the original condition which involved only colors. A tiling of the plane by a set of tiles is a covering of the plane with translated copies of the tiles such that adjacent edges of abutting tiles satisfy the above matching condition. A set of tiles is consistent if the plane can be tiled by the set. A set of tiles with a designated origin tile is origin-consistent if there is a tiling of the plane with the origin tile at the center.A square block of tiles is a tiling if every pair of abutting tiles satisfies the above matching condition. If an origin tile has been designated, a block of tiles is an origin-constrained tiling if it is a tiling with the origin tile at the center. Two blocks have the “same” center row if the blocks are of the same size and have identical center rows or if the smaller block's center row is a centered segment of the larger block's center row.
The λ-calculus is ω-incomplete
Authors: Plotkin G. D. 
Published: May 2006

The ω-rule in the λ-calculus (or, more exactly, the λK-β, η calculus) isIn [1] it was shown that this rule is consistent with the other rules of the λ-calculus. We will show the rule cannot be derived from the other rules; that is, we will give closed terms M and N such that MZ = NZ can be proved without using the ω-rule, for each closed term Z, but M = N cannot be so proved. This strengthens a result in [4] and answers a question of Barendregt.The language of the λ-calculus has an alphabet containing denumerably many variables a, b, c, … (which have a standard listing e1, e2, …), improper symbolsλ, ( , ) and a single predicate symbol = for equality.Terms are defined inductively by the following:(1) A variable is a term.(2) If M and N are terms, so is (MN); it is called a combination.(3) If M is a term and x is a variable, (λx M) is a term; it is called an abstraction.We use ≡ for syntactic identity of terms.If M and N are terms, M = N is a formula.BV(M), the set of bound variables in M, and FV(M), its free variables, are defined inductively byA term M is closed iff FV(M) = ∅.