We observe that the classification problem for countable models of arithmetic is Borel complete. On the other hand, the classification problems for finitely generated models of arithmetic and for recursively saturated models of arithmetic are Borel; we investigate the precise complexity of each of these. Finally, we show that the classification problem for pairs of recursively saturated models and for automorphisms of a fixed recursively saturated model are Borel complete.

Abstract.

The problem of enumerating the types of Boolean functions under the group of variable permutations and complementations was first stated by Jevons in the 1870s, but not solved in a satisfactory way until the work of Pólya in 1940. This paper explains the details of Pólya's solution, and also the history of the problem from the 1870s to the 1970s.

About a month after his 83rd birthday Raphael Robinson was almost wholly incapacitated by a massive stroke, and 8 weeks later, on January 27, 1995, he died of ensuing complications. Mathematics was his life. He was always working on problems—those brought to him in journals or by colleagues, and others that he invented. Just three days before his death he received word that a paper of his, originating in a published problem, was accepted for publication. His 64 publications spanned a full 6 decades, and included significant papers on number theory, combinatorics, complex analysis, and geometry, in addition to logic and set theory.

Robinson was born on November 2, 1911, in National City, California. He came to Berkeley to study mathematics, obtaining an A.B. in 1932, an M.A. in 1933, and his Ph.D. in December, 1934. His dissertation was in complex analysis. He took 12 graduate courses in a variety of fields, but not one was close to logic or set theory—which was later the setting of about a quarter of his publications.

After completing his studies Robinson served as Instructor for two years at Brown University, then returned for good to Berkeley in 1937, reaching the rank of full Professor in 1949. He taught a great variety of courses and was known as an excellent teacher, but was most interested in problemsolving and research and in 1972, at age 61, he elected early retirement, at considerable financial sacrifice, in order to concentrate on these pursuits.

Almost all set theorists pay at least lip service to Cantor’s definition of a set as a collection of many things into one whole; but empty and singleton sets do not fit with it. Adapting Dana Scott’s axiomatization of the cumulative theory of types, we present a ‘Cantorian’ system which excludes these anomalous sets. We investigate the consequences of their omission, examining their claim to a place on grounds of convenience, and asking whether their absence is an obstacle to the theory’s ability to represent ordered pairs or to support the arithmetization of analysis or the development of the theory of cardinals and ordinals.

Due to Gödel’s incompleteness results, the categoricity of a sufficiently rich mathematical theory and the semantic completeness of its underlying logic are two mutually exclusive ideals. For first- and second-order logics we obtain one of them with the cost of losing the other. In addition, in both these logics the rules of deduction for their quantifiers are non-categorical. In this paper I examine two recent arguments—Warren [43] and Murzi and Topey [30]—for the idea that the natural deduction rules for the first-order universal quantifier are categorical, i.e., they uniquely determine its semantic intended meaning. Both of them make use of McGee’s open-endedness requirement and the second one uses in addition Garson’s [19] local models for defining the validity of these rules. I argue that the success of both these arguments is relative to their semantic or infinitary assumptions, which could be easily discharged if the introduction rule for the universal quantifier is taken to be an infinitary rule, i.e., non-compact. Consequently, I reconsider the use of the $\omega $-rule and I show that the addition of the $\omega $-rule to the standard formalizations of first-order logic is categorical. In addition, I argue that the open-endedness requirement does not make the first-order Peano Arithmetic categorical and I advance an argument for its categoricity based on the inferential conservativity requirement.

First-order logic has limited existential import: the universalized conditional ∀x [S(x) → P(x)] implies its corresponding existentialized conjunction ∃x [S(x) & P(x)] in some but not all cases. We prove the Existential-Import Equivalence:

∀x [S(x) → P(x)] implies ∃x [S(x) & P(x)] iff ∃x S(x) is logically true.

The antecedent S(x) of the universalized conditional alone determines whether the universalized conditional has existential import: implies its corresponding existentialized conjunction.

A predicate is a formula having only x free. An existential-import predicate Q(x) is one whose existentialization, ∃x Q(x), is logically true; otherwise, Q(x) is existential-import-free or simply import-free. Existential-import predicates are also said to be import-carrying.

How widespread is existential import? How widespread are import-carrying predicates in themselves or in comparison to import-free predicates? To answer, let L be any first-order language with any interpretation INT in any [sc. nonempty] universe U. A subset S of U is definable in L under INT iff for some predicate Q(x) in L, S is the truth-set of Q(x) under INT. S is import-carrying definable iff S is the truth-set of an import-carrying predicate. S is import-free definable iff S is the truth-set of an import-free predicate.

Existential-Importance Theorem: Let L, INT, and U be arbitrary. Every nonempty definable subset of U is both import-carrying definable and import-free definable.

Import-carrying predicates are quite abundant, and no less so than import-free predicates. Existential-import implications hold as widely as they fail.

A particular conclusion cannot be validly drawn from a universal premise, or from any number of universal premises.—Lewis-Langford, 1932, p. 62.

This is a short expository account of the regularity lemma for stable graphs proved by the authors, with some comments on the model theoretic context, written for a general logical audience.

In recent work, the authors have established the group configuration theorem for simple theories, as well as some of its main applications from geometric stability theory, such as the binding group theorem, or, in the ω-categorical case, the characterization of the forking geometry of a finitely based non-trivial locally modular regular type as projective geometry over a finite field and the equivalence of pseudolinearity and local modularity.

The proof necessitated an extension of the model-theoretic framework to include almost hyperimaginaries, and the study of polygroups.

Paul Erdős (26 March 1913—20 September 1996) was a mathematician par excellence whose results and initiatives have had a large impact and made a strong imprint on the doing of and thinking about mathematics. A mathematician of alacrity, detail, and collaboration, Erdős in his six decades of work moved and thought quickly, entertained increasingly many parameters, and wrote over 1500 articles, the majority with others. His modus operandi was to drive mathematics through cycles of problem, proof, and conjecture, ceaselessly progressing and ever reaching, and his modus vivendi was to be itinerant in the world, stimulating and interacting about mathematics at every port and capital.

Every countable structure has a sentence of the infinitary logic $\mathcal {L}_{\omega _1 \omega }$ which characterizes that structure up to isomorphism among countable structures. Such a sentence is called a Scott sentence, and can be thought of as a description of the structure. The least complexity of a Scott sentence for a structure can be thought of as a measurement of the complexity of describing the structure. We begin with an introduction to the area, with short and simple proofs where possible, followed by a survey of recent advances.

In this talk I will introduce two spaces: the first space is the usual n-dimensional vector space with the unusual feature that n is a non-integer; the second space is composed of the linear matrices acting on the previous space (physicists are particularly interested in studying the limit as n goes to zero). These two spaces are not known to most mathematicians, but they are widely used by physicists. It is possible that, by extending the notion of space, they can become well defined mathematical objects.

We discuss the close relationship between structural theorems in (generalized) stability theory, and graph regularity theorems.

Following our [6], though with somewhat different methods here, further variants of Goodstein sequences are introduced in terms of parameterized Ackermann–Péter functions. Each of the sequences is shown to terminate, and the proof-theoretic strengths of these facts are calibrated by means of ordinal assignments, yielding independence results for a range of theories: PRA, PA, $\Sigma ^1_1$ -DC $_0$ , ATR $_0$ , up to ID $_1$ . The key is the so-called “Hardy hierarchy” of proof-theoretic bounding finctions, providing a uniform method for associating Goodstein-type sequences with parameterized normal form representations of positive integers.

We give an exposition of the compactness of $L({Q^{\mathrm{\,cf}}\!\!\!\!\!\!}_{C})$ , for any set C of regular cardinals.