In Team Semantics, a dependency notion is strongly first order if every sentence of the logic obtained by adding the corresponding atoms to First-Order Logic is equivalent to some first-order sentence. In this work it is shown that all nontrivial dependency atoms that are strongly first order, downwards closed, and relativizable (in the sense that the relativizations of the corresponding atoms with respect to some unary predicate are expressible in terms of them) are definable in terms of constancy atoms.

Additionally, it is shown that any strongly first-order dependency is safe for any family of downwards closed dependencies, in the sense that every sentence of the logic obtained by adding to First-Order Logic both the strongly first-order dependency and the downwards closed dependencies is equivalent to some sentence of the logic obtained by adding only the downwards closed dependencies.

We show that the 0-1 law does not hold for the class (∀∃∀ without = ) by finding a sentence in this class which almost surely expresses parity. We also show that every recursive real in the unit interval is the asymptotic probability of a sentence in this class. This expands a result by Lidia Tendera, who in 1994 proved that every rational number in the unit interval is the asymptotic probability of a sentence in the class ∀∃∀ with equality.

We give an example of a dense o-minimal structure in which there is a definable quotient that cannot be eliminated, even after naming parameters. Equivalently, there is an interpretable set which cannot be put in parametrically definable bijection with any definable set. This gives a negative answer to a question of Eleftheriou, Peterzil, and Ramakrishnan. Additionally, we show that interpretable sets in dense o-minimal structures admit definable topologies which are “tame” in several ways: (a) they are Hausdorff, (b) every point has a neighborhood which is definably homeomorphic to a definable set, (c) definable functions are piecewise continuous, (d) definable subsets have finitely many definably connected components, and (e) the frontier of a definable subset has lower dimension than the subset itself.

A Leibniz class is a class of logics closed under the formation of term-equivalent logics, compatible expansions, and non-indexed products of sets of logics. We study the complete lattice of all Leibniz classes, called the Leibniz hierarchy. In particular, it is proved that the classes of truth-equational and assertional logics are meet-prime in the Leibniz hierarchy, while the classes of protoalgebraic and equivalential logics are meet-reducible. However, the last two classes are shown to be determined by Leibniz conditions consisting of meet-prime logics only.

The language LA(Ⅎ) is formed by adding the quantifier Ⅎx, “few x”, to the infinitary logic LA on an admissible set A. A complete axiomatization is obtained for models whose universe is the set of ordinals of A and where Ⅎx is interpreted as there exist A-finitely many x. For well-behaved A, every consistent sentence has a model with an A-recursive diagram. A principal tool is forcing for LA(Ⅎ).

In his paper [7] Steel asked whether there can exist a normal measure U on a cardinal κ such that

We use Reverse Easton forcing to show that this is consistent from a P2κ hypermeasure; we also show that the result is sharp, using the core model for nonoverlapping coherent extender sequences.

The proof uses forcing technology due to Woodin.

In this section we collect some facts that are useful in the forcing constructions of the next section. None of them are due to us, and we are unsure to whom they should be attributed for the most part. We give sketchy proofs; the reader who wants to see more details is referred to [2].

In [10, §0, E), 5)] Shelah states using the proofs of 7.9 and 6.9 in [9] it is possible to prove that if a countable first-order theory T is ℵ0-stable (totally transcendental) and not ℵ1-categorical, then it has at least ∣1 + α∣ models of power ℵα.

In this note we will give a new proof of this theorem using the work of Baldwin and Lachlan [1]. Our original proof used the generalized continuum hypothesis (GCH). We are indebted to G. E. Sacks for suggesting that the notions of ℵ0-stability and ℵ1-categoricity are absolute, and that consequently our use of GCH was eliminable [8]. Routine results from model theory may be found, e.g. in [2].

Proof (with GCH). In the proof of Theorem 3 of [1] Baldwin and Lachlin show of power ℵα such that there is a countable definable subset in . Let B0 be such a subset. Say . We will give by transfinite induction an elementary chain of models of T of power ℵα such that B[i1 … in] has power ℵβ and such that every infinite definable subset of has power ≥ℵβ. This clearly suffices.

We prove that if μ is a regular cardinal and ℙ is a μ-centered forcing poset, then ℙ forces that (I[μ++[)V generates I[μ++] modulo clubs. Using this result, we construct models in which the approachability property fails at the successor of a singular cardinal. We also construct models in which the properties of being internally club and internally approachable are distinct for sets of size the successor of a singular cardinal.

The algebras studied in this paper were suggested to the author by William Craig as a possible substitute for cylindric algebras. Both kinds of algebras may be considered as algebraic versions of first-order logic. Cylindric algebras can be introduced as follows. Let ℒ be a first-order language, and let be an ℒ-structure. We assume that ℒ has a simple infinite sequence ν 0, ν 1, … of individual variables, and we take as known what it means for a sequence ν 0, ν 1, … of individual variables, and we take as known what it means for a sequence x = 〈x 0, x 1, …〉 of elements of to satisfy a formula ϕ of ℒ in . Let ϕ be the collection of all sequences x which satisfy ϕ in . We can perform certain natural operations on the sets ϕ , of basic model-theoretic significance: Boolean operations = cylindrifications diagonal elements (0-ary operations) . In this way we make the class of all sets ϕ into an algebra; a natural abstraction gives the class of all cylindric set algebras (of dimension ω). Thus this method of constructing an algebraic counterpart of first-order logic is based upon the notion of satisfaction of a formula by an infinite sequence of elements. Since, however, a formula has only finitely many variables occurring in it, it may seem more natural to consider satisfaction by a finite sequence of elements; then ϕ becomes a collection of finite sequences of varying ranks (cf. Tarski [10]). In forming an algebra of sets of finite sequences it turns out to be possible to get by with only finitely many operations instead of the infinitely many ci 's and dij 's of cylindric algebras. Let be the class of all algebras of sets of finite sequences (an exact definition is given in §1).

The main result of this paper is to show that for every recursive ordinal α ≠ 0 and for every nonrecursive r.e. degree d there is a r.e. set of rank α and degree d.

The paper uses the formalism of indexed categories to recover the proof of a standard final coalgebra theorem, thus showing existence of final coalgebras for a special class of functors on finitely complete and cocomplete categories. As an instance of this result, we build the final coalgebra for the powerclass functor, in the context of a Heyting pretopos with a class of small maps. This is then proved to provide models for various non-well-founded set theories, depending on the chosen axiomatisation for the class of small maps.

The two statements “Two different objects cannot occupy the same place at the same time” and “An object cannot be in two different places at the same time” are axioms of our everyday understanding of objects, space and time. We develop a first-order theory OST (Objects, Space and Time) in which formal equivalents of these two statements are taken as axioms. Using the theory OST, we uncover other fundamental principles of objects, space and time. We attempt to understand the logical nature of these principles, to investigate their formal consequences, and to identify logical alternatives to them. For easy reference, all of the nonlogical axioms of OST are listed together at the end of §2. In §3, we introduce two possible extensions of OST.

The most basic construction of an r.e. nonrecursive set—e.g. of the halting problem—proceeds by taking the diagonal of a recursive enumeration of all r.e. sets. We will answer the question of which r.e. sets can be constructed in this manner.

If ψ is a computable numbering of some class of partial recursive functions, we define the diagonal of ψ to be the set K ψ ≔ {i ∈ ω ∣ ψi (i)↓}- It is well known that K φ is creative if φ is a Gödelnumbering, and that for each creative set K there exists a Gödelnumbering φ such that K = K φ. That is to say, the class of diagonals of Gödelnumberings is characterized as the class of creative sets. This class was shown to be elementary lattice theoretic (e.l.t.) by Harrington (see [So87, XV. 1.1]).

We give a characterization of diagonals of arbitrary computable numberings of the class P 1 of all partial recursive functions. To this end we introduce the notion of a semihyperhypersimple (shhs) set, which generalizes the notion of hyperhypersimplicity to nonsimple sets. It is shown that the diagonals of numberings of P 1 are exactly the non-shhs sets. Then, properties of shhs sets are discussed. For example, for each nonrecursive r.e. set A there exists a nonrecursive shhs set B ≤T A, but not every r.e. T-degree contains a shhs set. These results build upon previous work by Downey and Stob [DSta].

The question whether the property “shhs” is (elementary) lattice theoretic remains open. A positive answer would give both an analog of Harrington's result mentioned above, and a generalization of the well-known fact, due to Lachlan [La68], that hyperhypersimplicity is e.l.t. Therefore, we suspect that shhs sets turn out to be useful in the study of the lattice of r.e. sets.

Previously, for several constructions from recursion theory the role of the underlying numbering of P 1 was investigated; see Martin ([Ma66a] or [So87, V.4.1]) and Lachlan ([La75] or [Od89, III.9.2]) for Post's simple set, and Jockusch and Soare ([JS73]; cf. also [So87, XII.3.6, 3.7]) for Post's hypersimple set. However, only Gödelnumberings were considered. An explanation for the greater variety which arises when arbitrary numberings of P 1 are admitted is provided by the fact that the index set of Gödelnumberings is less complex than the index set of all numberings of P 1. The former is Σ1-complete; the latter is Π4-complete.

Sometimes it is said that mathematics talks only about truths that are invariant under isomorphisms. Thus, a syntactical characterization of sentences preserved under isomorphisms seems to be important to understand what mathematics is.

The importance of such sentences is underlined, for instance, by Bourbaki's requirement in [1, Chapter IV] that all axioms for mathematical structures satisfy the condition of being what they call transportable, that is, preserved under isomorphisms. In [2, §1], a formalization of Bourbaki's notion of mathematical structure and of the notion of transportable sentence was given and discussed. We adopt here, as in [2], Bourbaki's terminology, and call a sentence φ transportable if φ is true in a structure E if and only if φ is true in any structure F isomorphic to E.

An alternative formulation for Bourbaki's notion of structure is offered in [2, §3], which is also intended as a formalization of Suppes' notion of set-theoretical predicate, as formulated, for instance, in [3]. It is this alternative formulation that we adopt here.

In [2, p. 106], it was conjectured that a set-theoretical sentence is transportable if and only if it is equivalent to a sentence of type theory. One direction of the conjecture is obvious, namely, that any sentence of type theory is transportable. It is also clear that there are sentences of set theory which are not transportable. The main purpose of the present paper is to prove the rest of the conjecture. That is, we prove here that any transportable set-theoretical sentence is equivalent to a sentence of type theory.

The aim of this paper is to introduce a formal system STW of self-referential truth, which extends the classical first-order theory of pure combinators with a truth predicate and certain approximation axioms. STW naturally embodies the mechanisms of general predicate application/abstractionon a par with function application/abstraction; in addition, it allows non-trivial constructions, inspired by generalized recursion theory. As a consequence, STW provides a smooth inner model for Myhill's systems with levels of implication.

Mathematics is a natural science whose great generality makes many philosophers think of it as a supernatural science, consisting of truths derived independently of experience about objects not given in experience. Some mathematicians, like Simpson [16], try to defend mathematics from the resulting objection that it is merely a mental game by first conceding that most of it is meaningless and then trying to save what is left by some technical tour de force. Some physicists, like Wigner [20], admit that mathematics is applicable to the world, but declare themselves unable to understand what makes its applications possible. Both Simpson's worries and Wigner's puzzlement can be relieved if we assimilate mathematics more closely to the other natural sciences.

One of the most fundamental results of higher-type recursion theory was first proved by Thomas Grilliot [3]. He showed that the functional embodying number quantification, 2E, is computable from a type-2 object F if and only if F has an effective discontinuity. For the background to this work we recommend Normann's book [9] or his summary [10], and for an example of its many applications Normann-Wainer [11].

The purpose of §1 of this paper is to give an effective proof of the “only if” part of this result: i.e. a construction of a discontinuity of F from the information 2E = {e}F. This contrasts with Grilliot's argument which is topological and nonconstructive, and shows that “Grilliot's trick” for computing 2E from a discontinuity of F is essentially the only method.

We then apply the method to two more general situations in which it gives new results. In §2 we treat type-3 objects in which 3E is computable (assuming AC and CH), and obtain a strengthening of the result of Hartley [5, §5]. In §3 we consider the superjump and characterise it as the least among a class of functionals with a particular sort of family of discontinuities.

This paper is concerned with the hyderdegrees of elements of uncountable Borel subsets of ωω. The Borel subsets of ωω are the so-called Δ11 subsets of ωω, which are the subsets of ωω that are Δ11 in some parameter f: ω → ω.

The results of this paper were inspired by two earlier results about the hyperdegrees of elements of Σ11 subsets of ωω. The first is known as the Gandy basis theorem, and asserts that the collection of functions of strictly lower hyperdegree than the hyperjump form a basis for the Σ11 subsets of ωω (see Rogers [3, p. 421]). The second is that there exists an uncountable Σ11 subset of ωω no element of which is hyperarithmetic in any other. The latter is credited to Feferman in Harrison [1], and appears there as Corollary 2.7, p. 537.

Two questions arise. Can we find other basis theorems if we replace Σ11 by Δ11 in Gandy's result? Can we replace Σ11 by Δ11 in Feferman's result?

We simultaneously answer the first positively, and the second negatively by proving that any hyperdegree, in which the hyperjump is hyperarithmetic, forms a basis for the Δ11 subsets of ωω with no hyperarithmetic elements. We conjecture that this holds also for uncountable Δ11 subsets of ωω. This conjecture is open despite the recent claim in Notices of the American Mathematical Society, vol. 19 (1972), p. A616, Abstract 696-02-10.

A 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.