What I am offering here is a reconsideration, and in the end a solution, of the ancient paradox of the Epimenides. What has provoked this new assault on so old a stronghold is L. Jonathan Cohen's [2], in which it is rightly pointed out that the Epimenidean as contrasted with the Eubulidean version of the Liar paradox is the one that threatens logicians who attempt to formalise the use of indirect rather than direct discourse. Among these he includes myself, referring to the system sketched on pp. 130–131 of my [4], and suggesting that I ought to have shown how a person interpreting this system in the obvious way can avoid semantic antinomies. Here too he is right, and my main purpose now is not to criticise his paper, but to fill in this lacuna in my own work to which he has drawn attention. I do want, however, to make one small criticism at the start, namely that Cohen fails to notice what it is that is really paradoxical about the Epimenides, and in consequence fails to perceive the same paradoxical character in a proposition which he is himself quite happy to accept as a ‘logical truth.’

The point about the Epimenides, as was noted by Church in [1], is not that when we examine the truth value of a Cretan's assertion that nothing true is ever asserted by a Cretan we are led to contradictory conclusions, for we are not; the paradox is rather that such examination makes it seem possible to settle an empirical question on logical grounds. If we treat the Cretan's assertion as true, and so assume that nothing true is ever asserted by a Cretan, it follows immediately that the Cretan's assertion is false. If, however, we treat it as false, there is no way of deducing from this assumption that it is true. We can, therefore, consistently suppose it to be false, and this is all that we can consistently suppose. But to suppose it false (considering what the assertion actually is) is to suppose that something asserted by a Cretan is true; and this of course can only be some other assertion than the one mentioned. We thus reach the peculiar conclusion that if any Cretan does assert that nothing asserted by a Cretan is true, then this cannot possibly be the only assertion made by a Cretan — there must also be, beside this false Cretan assertion, some true one.

We give several characterizations of Schnorr trivial sets, including a new lowness notion for Schnorr triviality based on truth-table reducibility. These characterizations allow us to see not only that some natural classes of sets, including maximal sets, are composed entirely of Schnorr trivials, but also that the Schnorr trivial sets form an ideal in the truth-table degrees but not the weak truth-table degrees. This answers a question of Downey. Griffiths and LaForte.

In this paper we study generic complexity of undecidable problems. It turns out that some classical undecidable problems are, in fact, strongly undecidable, i.e., they are undecidable on every strongly generic subset of inputs. For instance, the classical Halting Problem is strongly undecidable. Moreover, we prove an analog of the Rice theorem for strongly undecidable problems, which provides plenty of examples of strongly undecidable problems. Then we show that there are natural super-undecidable problems, i.e., problem which are undecidable on every generic (not only strongly generic) subset of inputs. In particular, there are finitely presented semigroups with super-undecidable word problem. To construct strongly- and super-undecidable problems we introduce a method of generic amplification (an analog of the amplification in complexity theory). Finally, we construct absolutely undecidable problems, which stay undecidable on every non-negligible set of inputs. Their construction rests on generic immune sets.

It is proved in this paper that the positive abstraction scheme is consistent with extensionality only if one drops equality out of the language. The theory obtained is then compared with GPK, a well-known set theory based on an extended positive comprehension scheme.

Working in Z + KP, we give a new proof that the class of hereditarily finite sets cannot be proved to be a set in Zermelo set theory, extend the method to establish other failures of replacement, and exhibit a formula Φ(λ, a) such that for any sequence ⟨Aλ ∣ λ a limit ordinal⟩ where for each λ. Aλ ⊆ λ2, there is a supertransitive inner model of Zermelo containing all ordinals in which for every λAλ = {a ∣ Φ(λ, a)}.

In this article we introduce systems for metapredicative Mahlo in explicit mathematics and admissible set theory. The exact upper proof-theoretic bounds of these systems are established.

The strong homogeneity conjecture asserts that, for any Turing degree, a, there is a jump preserving isomorphism from the upper semilattice of degrees to the upper semilattice of degrees above a. Rogers [3, p. 261] states that this problem is open and notes that its truth would simplify many proofs about degrees. It is, in fact, false. More precisely, let 0 be the smallest degree and let 0(n) be the nth iterated jump of 0, as defined in [3, pp. 254–256].

Kleene-Post [10], Spector [14] and Friedberg [3, 4], have given a number of examples of functions which have incomparable degrees of recursive unsolvability satisfying various additional conditions. Our present purpose is to determine to what extent some of these incomparability theorems can be generalized by substituting for “α. is recursive in β” other relations Q(α, β) such as “α is hyperarithmetical in β” (which we shall think of as “α ≦ β”), and to determine what restrictions, if any, need be imposed on Q. As a consequence of our investigation we shall show that there are incomparable hyperdegrees as defined in [9] and [13].

Introduction. In his monograph On Numbers and Games [7], J. H. Conway introduced a real-closed field containing the reals and the ordinals as well as a great many other numbers including ω, ω, /2, 1/ω, and ω − π to name only a few. Indeed, this particular real-closed field, which Conway calls No, is so remarkably inclusive that, subject to the proviso that numbers—construed here as members of ordered “number” fields—be individually definable in terms of sets of von Neumann-Bernays-Gödel set theory with Global Choice, henceforth NBG [cf. 21, Ch. 4], it may be said to contain “All Numbers Great and Small.” In this respect, No bears much the same relation to ordered fields that the system of real numbers bears to Archimedean ordered fields. This can be made precise by saying that whereas the ordered field of reals is (up to isomorphism) the unique homogeneous universal Archimedean ordered field, No is (up to isomorphism) the unique homogeneous universal orderedfield [14]; also see [10], [12], [13].

However, in addition to its distinguished structure as an ordered field, No has a rich hierarchical structure that (implicitly) emerges from the recursive clauses in terms of which it is defined. This algebraico-tree-theoretic structure, or simplicity hierarchy, as we have called it [15], depends upon No's (implicit) structure as a lexicographically ordered binary tree and arises from the fact that the sums and products of any two members of the tree are the simplest possible elements of the tree consistent with No's structure as an ordered group and an ordered field, respectively, it being understood that x is simpler than y just in case x is a predecessor of y in the tree.

We present a variation of the forcing as presented in Woodin [4], Our forcing is a ℙmax-style construction where each model condition selects one Souslin tree. In the extension there is a Souslin tree TG which is the direct limit of the selected Souslin trees in the models of the generic. In some sense, the generic extension is a maximal model of "there exists a minimal Souslin tree,” with TG being this minimal tree. In particular, in the extension this Souslin tree has the property that forcing with it gives a model of Souslin's Hypothesis.

The purpose of this paper is to present a very versatile family of logical systems of positional or topological logic. These systems—obtained by generalizing the existing systems of chronological logic—are to have a very general nature, capable of reflecting the characteristics of a wide range of logical systems, including not only chronological (also temporal or tense) logic, but also what we may call locative or place logic, and even a logic of “possible worlds”.

Let us recall that Raphael Robinson's Arithmetic Q is an axiom system that differs from Peano Arithmetic essentially by containing no Induction axioms [13], [18]. We will generalize the semantic-tableaux version of the Second Incompleteness Theorem almost to the level of System Q. We will prove that there exists a single rather long Π1 sentence, valid in the standard model of the Natural Numbers and denoted as V. such that if α is any finite consistent extension of Q + V then α will be unable to prove its Semantic Tableaux consistency. The same result will also apply to axiom systems α with infinite cardinality when these infinite-sized axiom systems satisfy a minor additional constraint, called the Conventional Encoding Property.

Our formalism will also imply that the semantic-tableaux version of the Second Incompleteness Theorem generalizes for the axiom system IΣ0, as well as for all its natural extensions. (This answers an open question raised twenty years ago by Paris and Wilkie [15].)

Fibring is recognized as one of the main mechanisms in combining logics, with great significance in the theory and applications of mathematical logic. However, an open challenge to fibring is posed by the collapsing problem: even when no symbols are shared, certain combinations of logics simply collapse to one of them, indicating that fibring imposes unwanted interconnections between the given logics. Modulated fibring allows a finer control of the combination, solving the collapsing problem both at the semantic and deductive levels. Main properties like soundness and completeness are shown to be preserved, comparison with fibring is discussed, and some important classes of examples are analyzed with respect to the collapsing problem.

We give a new, simplified and detailed account of the correspondence between levels of the Sherali–Adams relaxation of graph isomorphism and levels of pebble-game equivalence with counting (higher-dimensional Weisfeiler–Lehman colour refinement). The correspondence between basic colour refinement and fractional isomorphism, due to Tinhofer [22; 23] and Ramana, Scheinerman and Ullman [17], is re-interpreted as the base level of Sherali–Adams and generalised to higher levels in this sense by Atserias and Maneva [1] and Malkin [14], who prove that the two resulting hierarchies interleave. In carrying this analysis further, we here give (a) a precise characterisation of the level k Sherali–Adams relaxation in terms of a modified counting pebble game; (b) a variant of the Sherali–Adams levels that precisely match the k-pebble counting game; (c) a proof that the interleaving between these two hierarchies is strict. We also investigate the variation based on boolean arithmetic instead of real/rational arithmetic and obtain analogous correspondences and separations for plain k-pebble equivalence (without counting). Our results are driven by considerably simplified accounts of the underlying combinatorics and linear algebra.

Let M be an L-structure and A be an infinite subset of M. Two structures can be defined from A:

• The induced structure on A has a name Rφ for every ∅-definable relation φ(M) ∩ An on A. Its language is

A with its Lind-structure will be denoted by Aind.

• The pair (M, A) is an L(P)-structure, where P is a unary predicate for A and L(P) = L ∪{P}.

We call A small if there is a pair (N, B) elementarily equivalent to (M, A) and such that for every finite subset b of N every L–type over Bb is realized in N.

A formula φ(x, y) has the finite cover property (f.c.p) in M if for all natural numbers k there is a set of φ–formulas

which is k–consistent but not consistent in M. M has the f.c.p if some formula has the f.c.p in M. It is well known that unstable structures have the f.c.p. (see [6].) We will prove the following two theorems.

Theorem A. Let A be a small subset of M. If M does not have the finite cover property then, for every λ ≥ ∣L∣, if both M andAindare λ–stable then (M, A) is λ–stable.

Corollary 1.1 (Poizat [5]). If M does not have the finite cover property and N ≺ M is a small elementary substructure, then (M, N) is stable.

Corollary 1.2 (Zilber [7]). If U is the group of wots of unity in the field ℂ of complex numbers the pair (ℂ, U) isω–stable.

Proof. (See [4].) As a strongly minimal set ℂ is ω–stable and does not have the f.c.p. By the subspace theorem of Schmidt [3] every algebraic set intersects U in a finite union of translates of subgroups definable in the group structure of U alone. Whence Uind is nothing more than a (divisible) abelian group, which is ω–stable.

In this paper we shall repair some errors and fill some gaps in the inner model theory of [2]. The problems we shall address affect some quite basic definitions and proofs.

We shall be concerned with condensation properties of canonical inner models constructed from coherent sequences of extenders as in [2]. Condensation results have the general form: if x is definable in a certain way over a level , then either x ∈ , or else from x we can reconstruct in a simple way.

The first condensation property considered in [2] is the initial segment condition, or ISC. In section 1 we show that the version of this condition described in [2] is too strong, in that no coherent in which the extenders are indexed in the manner of [2], and which is such that L[] satisfies the mild large cardinal hypothesis that there is a cardinal which is strong past a measurable, can satisfy the full ISC of [2]. It follows that the coherent sequences constructed in [2] do not satisfy the ISC of [2]. We shall describe the weaker ISC which these sequences do satisfy, and indicate the small changes in the arguments of [2] this new condition requires.

In treatises or advanced textbooks on theoretical physics, it is apparent that the way mathematics is used is very different from what is to be found in books of mathematics. There is, for example, no close connection between books on analysis, on the one hand, and any classical textbook in quantum mechanics, for example, Schiff, [11], or quite recent books, for example Ryder, [10], on quantum field theory. The differences run a good deal deeper than the fact that the books on theoretical physics are not written in the definition-theorem-proof style characteristic of pure mathematics. Although a good many propositions are proved in the books on physics, there are almost with exception no existential proofs, and consequently there is no really serious systematic use of quantifiers. Another important characteristic is the free use of infinitesimals. In fact, most results would not lose anything, from a physicist's point of view, by leaving them in approximate form, i.e., instead of strict equalities or inequalities, using equalities or inequalities only up to an infinitesimal.

The discrepancy between the way mathematics is ordinarily done in theoretical physics and the way it is built up from a foundational standpoint in any of the standard modern views raises the question of whether it might be possible to construct quite directly a rigorous foundation that reflects a significant part of this standard practice in theoretical physics. Other parts of standard practice in physics, for example, the use of physically intuitive but nonrigorous arguments, are not present in our system.

We construct the set of the title, answering a question of Cholak, Jockusch. and Slaman [1], and discuss its connections with the study of the proof-theoretic strength and effective content of versions of Ramsey's Theorem. In particular, our result implies that every ω-model of must contain a nonlow set.

One of the preeminent problems confronting logicians is that of constructing a system of logic which will be adequate for mathematics. By a system's being adequate for mathematics, we mean that all mathematical theorems in general use can be deduced within the system. Several distinct logical systems, all having this end in view, have been proposed. Among these perhaps the best known are the systems referred to as “Principia Mathematica” and “set theory.” In both of these systems (we refer to the revised and simplified versions) there is a nucleus of propositions which can be derived by using only the axioms and rules of the restricted predicate calculus. However, if anything like adequacy for mathematics is to be expected, additional primitives and axioms must be added to the restricted predicate calculus. It is in their treatment of the additional primitive ε, denoting class or set membership, that the above-mentioned systems differ.

In addition to these two, a third and a stronger system has been proposed by W. V. Quine in his paper New foundations for mathematical logic. It is with this system of Quine's that our work is concerned and of which we now give a brief description.

In this paper it will be shown that the ordering of the recursively enumerable (r.e.) sets under inclusion modulo finite differences (m.f.d.), the ordering of the II111 sets under inclusion m.f.d., and the ordering of the metarecursively enumerable (meta-r.e.) sets under inclusion m.f.d. are all distinct. In fact, it will be shown that the three orderings are pairwise elementarily inequivalent when interpreted in the obvious way in a first order language with one binary relation “≥.” Our result answers a question of Hartley Rogers, Jr. [3, p. 203]. All necessary background material may be found in [2] and [4].