Every K-trivial set is computable from an incomplete Martin-Löf random set, i.e., a Martin-Löf random set that does not compute the halting problem.

The Löwenheim–Skolem theorem was published in Skolem's long paper of 1920, with the first section dedicated to the theorem. The second section of the paper contains a proof-theoretical analysis of derivations in lattice theory. The main result, otherwise believed to have been established in the late 1980s, was a polynomial-time decision algorithm for these derivations. Skolem did not develop any notation for the representation of derivations, which makes the proofs of his results hard to follow. Such a formal notation is given here by which these proofs become transparent. A third section of Skolem's paper gives an analysis for derivations in plane projective geometry. To clear a gap in Skolem's result, a new conservativity property is shown for projective geometry, to the effect that a proper use of the axiom that gives the uniqueness of connecting lines and intersection points requires a conclusion with proper cases (logically, a disjunction in a positive part) to be proved.

The forgotten parts of Skolem's first paper on the Löwenheim–Skolem theorem are the perhaps earliest combinatorial analyses of formal mathematical proofs, and at least the earliest analyses with profound results.

In this article, we study the prehistory of type theory up to 1910 and its development between Russell and Whitehead's Principia Mathematica ([71], 1910–1912) and Church's simply typed λ-calculus of 1940. We first argue that the concept of types has always been present in mathematics, though nobody was incorporating them explicitly as such, before the end of the 19th century. Then we proceed by describing how the logical paradoxes entered the formal systems of Frege, Cantor and Peano concentrating on Frege's Grundgesetze der Arithmetik for which Russell applied his famous paradox and this led him to introduce the first theory of types, the Ramified Type Theory (RTT). We present RTT formally using the modern notation for type theory and we discuss how Ramsey, Hilbert and Ackermann removed the orders from RTT leading to the simple theory of types STT. We present STT and Church's own simply typed λ-calculus (λ→C) and we finish by comparing RTT, STT and λ→C.

As initially envisioned, Gödel's Collected Works were to include transcriptions of material from his mathematical workbooks. In the end that material, as well as some other manuscript items from Gödel's Nachlass, had to be left out. This note describes some of the unpublished items in the Nachlass that are likely to attract the notice of scholars and surveys the extent of shorthand transcription efforts undertaken hitherto. Some examples of sources outside Gödel's Nachlass that may be of interest to Gödel scholars are also indicated.

Gödel has emphasized the important role that his philosophical views had played in his discoveries. Thus, in a letter to Hao Wang of December 7, 1967, explaining why Skolem and others had not obtained the completeness theorem for predicate calculus, Gödel wrote:

This blindness (or prejudice, or whatever you may call it) of logicians is indeed surprising. But I think the explanation is not hard to find. It lies in a widespread lack, at that time, of the required epistemological attitude toward metamathematics and toward non-finitary reasoning. …
I may add that my objectivist conception of mathematics and metamathematics in general, and of transfinite reasoning in particular, was fundamental also to my other work in logic.
How indeed could one think of expressing metamathematics in the mathematical systems themselves, if the latter are considered to consist of meaningless symbols which acquire some substitute of meaning only through metamathematics?
Or how could one give a consistency proof for the continuum hypothesis by means of my transfinite model Δ if consistency proofs have to be finitary?
In a similar vein, Gödel has maintained that the “realist” or “Platonist” position regarding sets and the transfinite with which he is identified was part of his belief system from his student days. This can be seen in Gödel's replies to the detailed questionnaire prepared by Burke Grandjean in 1974. Gödel prepared three tentative mutually consistent replies, but sent none of them.

We present here an approach to the fine structure of L based solely on elementary model theoretic ideas, and illustrate its use in a proof of Global Square in L. We thereby avoid the Lévy hierarchy of formulas and the subtleties of master codes and projecta, introduced by Jensen [3] in the original form of the theory. Our theory could appropriately be called ”Hyperfine Structure Theory”, as we make use of a hierarchy of structures and hull operations which refines the traditional Lα -or Jα-sequences with their Σn-hull operations.

§1. Introduction. In 1938, K. Gödel defined the model L of set theory to show the relative consistency of Cantor's Continuum Hypothesis. L is defined as a union

of initial segments which satisfy: L0 = ∅, Lλ = ∪α<λLα for limit ordinals λ, and, crucially, Lα + 1 = the collection of 1st order definable subsets of Lα. Since every transitive model of set theory must be closed under 1st order definability, L turns out to be the smallest inner model of set theory. Thus it occupies the central place in the set theoretic spectrum of models.

The proof of the continuum hypothesis in L is based on the very uniform hierarchical definition of the L-hierarchy. The Condensation Lemma states that if π : M → Lα is an elementary embedding, M transitive, then some ; the lemma can be proved by induction on α. If a real, i.e., a subset of ω, is definable over some Lα,then by a Löwenheim-Skolem argument it is definable over some countable M as above, and hence over some , < ω1. This allows one to list the reals in L in length ω1 and therefore proves the Continuum Hypothesis in L.

Two thoughts about the concept of number are incompatible: that any zero or more things have a (cardinal) number, and that any zero or more things have a number (if and) only if they are the members of some one set. It is Russell's paradox that shows the thoughts incompatible: the sets that are not members of themselves cannot be the members of any one set. The thought that any (zero or more) things have a number is Frege's; the thought that things have a number only if they are the members of a set may be Cantor's and is in any case a commonplace of the usual contemporary presentations of the set theory that originated with Cantor and has become ZFC.

In recent years a number of authors have examined Frege's accounts of arithmetic with a view to extracting an interesting subtheory from Frege's formal system, whose inconsistency, as is well known, was demonstrated by Russell. These accounts are contained in Frege's formal treatise Grundgesetze der Arithmetik and his earlier exoteric book Die Grundlagen der Arithmetik. We may describe the two central results of the recent re-evaluation of his work in the following way: Let Frege arithmetic be the result of adjoining to full axiomatic second-order logic a suitable formalization of the statement that the Fs and the Gs have the same number if and only if the F sand the Gs are equinumerous.

We classify actions of groups of finite Morley rank on abelian groups of Morley rank 2: there are essentially two, namely the natural actions of SL(V) and GL(V) with V a vector space of dimension 2. We also prove an identification theorem for the natural module of SL2 in the finite Morley rank category.

The study of propositional realizability logic was initiated in the 50th of the last century. Some interesting results were obtained in the 60-70th, but many important problems in this area are still open. Now interest to these problems from new generation of researchers is observed. This survey contains an exposition of the results on propositional realizability logic and corresponding techniques. Thus reading this paper can be the start point in exploring and development of constructive logic.

This brief article is intended to introduce the reader to the field of algebraic set theory, in which models of set theory of a new and fascinating kind are determined algebraically. The method is quite robust, applying to various classical, intuitionistic, and constructive set theories. Under this scheme some familiar set theoretic properties are related to algebraic ones, while others result from logical constraints. Conventional elementary set theories are complete with respect to algebraic models, which arise in a variety of ways, such as topologically, type-theoretically, and through variation. Many previous results from topos theory involving realizability, permutation, and sheaf models of set theory are subsumed, and the prospects for further such unification seem bright.

We show how to interpret the language of first-order set theory in an elementary topos endowed with, as extra structure, a directed structural system of inclusions (dssi). As our main result, we obtain a complete axiomatization of the intuitionistic set theory validated by all such interpretations. Since every elementary topos is equivalent to one carrying a dssi, we thus obtain a first-order set theory whose associated categories of sets are exactly the elementary toposes. In addition, we show that the full axiom of Separation is validated whenever the dssi is superdirected. This gives a uniform explanation for the known facts that cocomplete and realizability toposes provide models for Intuitionistic Zermelo–Fraenkel set theory (IZF).

Hypersequent calculus (HC), developed by A. Avron, is one of the most interesting proof systems suitable for nonclassical logics. Although HC has rather simple form, it increases significantly the expressive power of standard sequent calculi (SC). In particular, HC proved to be very useful in the field of proof theory of various nonclassical logics. It may seem surprising that it was not applied to temporal logics so far. In what follows, we discuss different approaches to formalization of logics of linear frames and provide a cut-free HC formalization of Kt4.3, the minimal temporal logic of linear frames, and some of its extensions. The novelty of our approach is that hypersequents are defined not as finite (multi)sets but as finite lists of ordinary sequents. Such a solution allows both linearity of time flow, and symmetry of past and future, to be incorporated by means of six temporal rules (three for future-necessity and three dual rules for past-necessity). Extensions of the basic calculus with simple structural rules cover logics of serial and dense frames. Completeness is proved by Schütte/Hintikka-style argument using models built from saturated hypersequents.

§1. Introduction. Asymptotic cones of metric spaces were first invented by Gromov. They are metric spaces which capture the ‘large-scale structure’ of the underlying metric space. Later, van den Dries and Wilkie gave a more general construction of asymptotic cones using ultrapowers. Certain facts about asymptotic cones, like the completeness of the metric space, now follow rather easily from saturation properties of ultrapowers, and in this survey, we want to present two applications of the van den Dries-Wilkie approach. Using ultrapowers we obtain an explicit description of the asymptotic cone of a semisimple Lie group. From this description, using semi-algebraic groups and non-standard methods, we can give a short proof of the Margulis Conjecture. In a second application, we use set theory to answer a question of Gromov.

§2. Definitions. The intuitive idea behind Gromov's concept of an asymptotic cone was to look at a given metric space from an ‘infinite distance’, so that large-scale patterns should become visible. In his original definition this was done by gradually scaling down the metric by factors 1/n for n ϵ ℕ. In the approach by van den Dries and Wilkie, this idea was captured by ultrapowers. Their construction is more general in the sense that the asymptotic cone exists for any metric space, whereas in Gromov's original definition, the asymptotic cone existed only for a rather restricted class of spaces.

In this paper we give probably an exhaustive analysis of the geometry of solids which was sketched by Tarski in his short paper [20, 21]. We show that in order to prove theorems stated in [20, 21] one must enrich Tarski's theory with a new postulate asserting that the universe of discourse of the geometry of solids coincides with arbitrary mereological sums of balls, i.e., with solids. We show that once having adopted such a solution Tarski's Postulate 4 can be omitted, together with its versions 4′ and 4″. We also prove that the equivalence of postulates 4, 4′ and 4″ is not provable in any theory whose domain contains objects other than solids. Moreover, we show that the concentricity relation as defined by Tarski must be transitive in the largest class of structures satisfying Tarski's axioms.

We build a model (in three-dimensional Euclidean space) of the theory of so called T*-structures and present the proof of the fact that this is the only (up to isomorphism) model of this theory.

Moreover, we propose different categorical axiomatizations of the geometry of solids. In the final part of the paper we answer the question concerning the logical status (within the theory of T*-structures) of the definition of the concentricity relation given by Tarski.

Euclidean geometry, as presented by Euclid, consists of straightedge-and-compass constructions and rigorous reasoning about the results of those constructions. We show that Euclidean geometry can be developed using only intuitionistic logic. This involves finding “uniform” constructions where normally a case distinction is used. For example, in finding a perpendicular to line L through point p, one usually uses two different constructions, “erecting” a perpendicular when p is on L, and “dropping” a perpendicular when p is not on L, but in constructive geometry, it must be done without a case distinction. Classically, the models of Euclidean (straightedge-and-compass) geometry are planes over Euclidean fields. We prove a similar theorem for constructive Euclidean geometry, by showing how to define addition and multiplication without a case distinction about the sign of the arguments. With intuitionistic logic, there are two possible definitions of Euclidean fields, which turn out to correspond to different versions of the parallel postulate.

We consider three versions of Euclid’s parallel postulate. The two most important are Euclid’s own formulation in his Postulate 5, which says that under certain conditions two lines meet, and Playfair’s axiom (dating from 1795), which says there cannot be two distinct parallels to line L through the same point p. These differ in that Euclid 5 makes an existence assertion, while Playfair’s axiom does not. The third variant, which we call the strong parallel postulate, isolates the existence assertion from the geometry: it amounts to Playfair’s axiom plus the principle that two distinct lines that are not parallel do intersect. The first main result of this paper is that Euclid 5 suffices to define coordinates, addition, multiplication, and square roots geometrically.

We completely settle the questions about implications between the three versions of the parallel postulate. The strong parallel postulate easily implies Euclid 5, and Euclid 5 also implies the strong parallel postulate, as a corollary of coordinatization and definability of arithmetic. We show that Playfair does not imply Euclid 5, and we also give some other independence results. Our independence proofs are given without discussing the exact choice of the other axioms of geometry; all we need is that one can interpret the geometric axioms in Euclidean field theory. The independence proofs use Kripke models of Euclidean field theories based on carefully constructed rings of real-valued functions. “Field elements” in these models are real-valued functions.

For every finite n ≥ 4 there is a logically valid sentence φn with the following properties: φn contains only 3 variables (each of which occurs many times); φn contains exactly one nonlogical binary relation symbol (no function symbols, no constants, and no equality symbol); φn has a proof in first-order logic with equality that contains exactly n variables, but no proof containing only n − 1 variables. This result was first proved using the machinery of algebraic logic developed in several research monographs and papers. Here we replicate the result and its proof entirely within the realm of (elementary) first-order binary predicate logic with equality. We need the usual syntax, axioms, and rules of inference to show that φn has a proof with only n variables. To show that φn has no proof with only n − 1 variables we use alternative semantics in place of the usual, standard, set-theoretical semantics of first-order logic.

This talk surveys a range of positions on the fundamental metaphysical and epistemological questions about elementary logic, for example, as a starting point: what is the subject matter of logic—what makes its truths true? how do we come to know the truths of logic? A taxonomy is approached by beginning from well-known schools of thought in the philosophy of mathematics—Logicism, Intuitionism, Formalism, Realism—and sketching roughly corresponding views in the philosophy of logic. Kant, Mill, Frege, Wittgenstein, Carnap, Ayer, Quine, and Putnam are among the philosophers considered along the way.

Set theory deals with the most fundamental existence questions in mathematics-questions which affect other areas of mathematics, from the real numbers to structures of all kinds, but which are posed as dealing with the existence of sets. Especially noteworthy are principles establishing the existence of some infinite sets, the so-called “arbitrary sets.” This paper is devoted to an analysis of the motivating goal of studying arbitrary sets, usually referred to under the labels of quasi-combinatorialism or combinatorial maximality. After explaining what is meant by definability and by “arbitrariness,” a first historical part discusses the strong motives why set theory was conceived as a theory of arbitrary sets, emphasizing connections with analysis and particularly with the continuum of real numbers. Judged from this perspective, the axiom of choice stands out as a most central and natural set-theoretic principle (in the sense of quasi-combinatorialism). A second part starts by considering the potential mismatch between the formal systems of mathematics and their motivating conceptions, and proceeds to offer an elementary discussion of how far the Zermelo–Fraenkel system goes in laying out principles that capture the idea of “arbitrary sets”. We argue that the theory is rather poor in this respect.

§1. The origins of recursion theory. In dedicating a book to Steve Kleene, I referred to him as the person who made recursion theory into a theory. Recursion theory was begun by Kleene's teacher at Princeton, Alonzo Church, who first defined the class of recursive functions; first maintained that this class was the class of computable functions (a claim which has come to be known as Church's Thesis); and first used this fact to solve negatively some classical problems on the existence of algorithms. However, it was Kleene who, in his thesis and in his subsequent attempts to convince himself of Church's Thesis, developed a general theory of the behavior of the recursive functions. He continued to develop this theory and extend it to new situations throughout his mathematical career. Indeed, all of the research which he did had a close relationship to recursive functions.

Church's Thesis arose in an accidental way. In his investigations of a system of logic which he had invented, Church became interested in a class of functions which he called the λ-definable functions. Initially, Church knew that the successor function and the addition function were λ-definable, but not much else. During 1932, Kleene gradually showed1 that this class of functions was quite extensive; and these results became an important part of his thesis 1935a (completed in June of 1933).