Logic Colloquium

A remarkable development in Set Theory is the discovery that if large cardinals exist, then, up to a certain level of logical complexity, what is true cannot be changed by set forcing. According to a celebrated theorem of Woodin, if the Continuum Hypothesis holds and there exist unboundedly many measurable Woodin cardinals, then an existential statement in third-order arithmetic having real parameters holds in a set generic extension that preserves the CH if and only if it already holds in V. Just beyond this level of logical complexity, not only is it impossible to complete the universe in this sense, but in ZFC there is not even a first- order characterization of the family of sentences that are false in all outer models. This is peculiar if one is accustomed to thinking of mathematics as governed by logical necessity.

The theorem is that if V satisfies ZFC^+ = ZFC + “every definable closed unbounded class of ordinals includes a Ramsey cardinal” and V is “sufficiently nonminimal”, then this anticharacterization phenomenon disappears.

But first, what are “outer models”? Talk of outer models is inherently second-order. The least restrictive way to understand claims about outermodel existence is to understand “V” as a countable set model in some larger ambient universe. The letter “V” is just intended to suggest a privileged role for this model as proxy for the real universe of sets—“real” at least in the sense that our discussion is formalizable in first-order ZFC. If V is a standard transitive model of ZFC, for the purpose of this abstract, say that W is an outer model of V if V is contained in W, the same ordinals are in W and V, and W is also a standard transitive model of ZFC.

THEOREM. There exists a parameter-free formula good(x) in the language of set theory as follows: Work inside a model V of ZFC^+. Let kappa be a regular uncountable cardinal. Let T in H_kappa be a set of first-order axioms in the language of set theory, extending ZFC and perhaps using parameters from H_kappa.

  1. If H_kappa satisfies good(T), then there exists an outer model of V that satisfies T.

  2. If H_kappa does not satisfy good(T) and V is sufficiently nonminimal, then T is not satisfiable in any outer model of V. The formula good(x) can be taken to be parameter-free Pi_2 or, if kappa is greater than omega–1, to be Pi_1 in the parameter omega–1.

If “V” is actually V_delta, where delta is an inaccessible cardinal in some longer model of ZFC, then V is sufficiently nonminimal. Some non-first-order hypothesis, like nonminimality, is necessary.

Consider the following problem, from the ethics literature: Ten miners are trapped either in shaft A or in shaft B, but we don’t know which. Flood waters threaten to flood the shafts. We have enough sandbags to block one shaft, but not both. If we block one shaft, all the water will go into the other shaft, killing any miners inside it. If we leave both shafts open, both shafts will fill halfway with water, and just one miner, the lowest in the shaft, will be killed.

In deliberating about what to do, it seems natural to accept:

  1. If the miners are in shaft A, we ought to block shaft A.
  2. If the miners are in shaft B, we ought to block shaft B.

We also accept:

  1. Either the miners are in shaft A or they are in shaft B.

But it seems we cannot conclude:

  1. Either we ought to block shaft A or we ought to block shaft B.

For this is incompatible with the correct prescription:

  1. We ought to block neither shaft.

In this talk, we consider four options for resolving the paradox:

  1. Distinguish objective and subjective senses of “ought”.
  2. Take “ought” in (1) and (2) to have wide scope over the conditional.
  3. Analyze (1) and (2) using a two-place conditional obligation operator.
  4. Reject modus ponens for the indicative conditional.

We argue that (d) is the best option. Rejecting modus ponens is not ad hoc, because it follows from independently-motivatable semantics for “ought” and the indicative conditional. (On this semantics, the counterexample to modus ponens above works for the same reasons as Vann McGee’s counterexamples involving nested conditionals.) Nor does it cripple reasoning, since we can give precise and broad conditions under which modus ponens can be used safely in reasoning.

This talk is based on joint work with Niko Kolodny (UC Berkeley, Philosophy).

In the Tarski archive at Berkeley there is a lecture entitled “On the Completeness and Categoricity of Deductive Systems” that Tarski had intended to publish but never did. The lecture is an important historical document for the development of abstract notions of semantics, such as semantical completeness and categoricity. Versions of these notions had played an important role in the logical investigations of the twenties and thirties (most notably in Fraenkel, Carnap, and Gödel) but in this lecture Tarski has at his disposal the tools of semantics he had recently developed. In addition, the lecture provides welcome information on a topic of central interest to Tarski and to contemporary philosophy of logic, e.g. the Tarskian notion of logical consequence. Finally, some of the technical problems raised in the lecture, concerning semantical completeness and categoricity in higher order logic, are still open and have very recently been the object of renewed attention.

In my talk I will spell out the key elements in the lecture and provide extensive commentary with the aim of clarifying the conceptual background of the lecture and to point to the relevance of some of the issues discussed by Tarski to contemporary philosophical and logical discussions.

I will address some topics concerning algorithms and bounds for polynomial rings over Noetherian coefficient rings. These issues essentially go back to Kronecker’s ideology of constructive mathematics. I’ll explain some of the history, state a natural conjecture on degree bounds for Groebner bases, and provide evidence for its truth. I’ll also give a characterization (proved using elementary nonstandard analysis) of those Noetherian commutative rings for which there exist uniform degree bounds for Groebner bases of ideals of polynomial rings over these rings.

During the last 20 years (though building upon pioneering ideas of G. Kreisel going back to the 50’s) a new applied form of proof theory emerged that sometimes is referred to as “proof mining”. Here the emphasis is on applications of so-called proof interpretations to concrete mathematical proofs with the aim of extracting effective bounds as well as new uniformity results from prima facie ineffective proofs. This has led to new results in number theory, approximation theory, nonlinear analysis, geodesic geometry, and ergodic theory, as well as the development of logical metatheorems that explain these results as instances of general logical phenomena. Specialized to the examples discussed in T. Tao’s recent essay “Soft analysis, hard analysis, and the finite convergence principle” the logical machinery yields very much the type of quantitative finitary versions of analytical theorems as considered by Tao. We will argue that these logical methods provide a systematic approach to Tao’s program of “hard analysis” and at the same time shed new light on some issues in the philosophy of mathematics.

A logical formula F(X,P) can be treated as an equation to be satisfied by the solutions X(P). John McCarthy considers the parameterization of the models of formulas, gives the general solution in the case of propositional logic, and states the problem for other logics. We find the general solution for the formulas in the first-order language with monadic predicates and equality. The solutions are obtained via quantifier elimination and parametrized by epsilon terms. This talk is based on joint work of the speaker and T. Hoshi.

Reference: John McCarthy, “Parameterizing the set of models of a propositional theory”.

We will elaborate on the question, “For which reals x does there exist a measure m such that x is effectively random relative to m?” which Jan Reimann discussed in the Logic Colloquium last semester. We will review what is known about the general question. We give several conditions on x equivalent to there being a continuous measure which makes x random. We show that for all but countably many reals x these conditions apply, so there is a continuous measure which makes x random. There is a metamathematical aspect of this investigation. As one requires higher arithmetic levels in the degree of randomness, one must make use of more iterates of the power set of the continuum. We will then focus on questions of 1-randomness and those x’s which are recursive in 0’.

Category theory deals in a mathematically natural way with certain kinds of algebraic structures on possibly very large collections of structures, such as the category Grp of all groups and the category Top of all topological spaces, in terms of the structure preserving maps (morphisms) between such objects. From this point of view, the category Cat of all categories is itself such a structure whose morphisms are the so-called functors between categories. Grp, Top, and Cat are examples of objects in Cat. Even more, if A and B are two categories, no matter how large. there is a still larger category whose objects are all the functors from A to B, and whose morphisms are the so-called natural transformations between functors. Existing set-theoretical foundations accounts for these kinds of constructions only in terms of certain kinds of restrictions, e.g. by making a distinction between small categories and large categories in a theory of sets and classes. Nevertheless, it is plausible that the foundation of an unrestricted category theory can be established without invoking such distinctions. I shall present several criteria for such a theory and show how they can be met to a considerable extent in a strong consistent extension of NFU (Quine’s system NF with urelements). However, a full foundation is blocked in stratified systems (with or without urelements) as presently treated. The talk will go over the article “Enriched stratified systems for the foundations of category theory” to be found at http://math.stanford.edu/~feferman/papers/ess.pdf.

Game-theoretic methods have proven to be an important tool in logic. In this talk, I will present a different perspective on the interface between logic and game theory: how logic can be used to reason about social interactive situations. This will be a survey talk focusing on:

  1. how logical methods provide interesting new perspectives on traditional game-theoretic questions, and
  2. new questions that arise of interest to both game-theorists and logicians.

I survey some (recent) results in finite combinatorics inspired by considerations from mathematical logic. These include a formula for Goodstein’s function, the rate of growth of the regressive Ramsey numbers, and the size of intersecting families of finite sets that are minimal under definability.

The duality between measures and the sets they “charge” is a central theme in modern analysis. An effective analogue of this question is: Given a real x, does there exist a (probability) measure relative to which x is effectively random (so that x is not an atom of the measure)? And if such a measure exists, can we ensure that it has certain properties (nonatomic, of a certain minimum capacity, etc.)? While every noncomputable real is random with respect to some measure, there exists a nested sequence of countable Pi-one-one sets of reals that are not n-random with respect to any continuous measure. This sequence exhibits a number of interesting properties. For instance, the proof that all of the sets are countable requires the existence of infinitely many iterates of the power set of omega, similar to Borel determinacy. Furthermore, it seems quite hard to find a natural notion of rank for such reals.

I will first survey the basic results on continuous randomness, before discussing more recent results on 1-randomness. Techniques are drawn from various areas of logic and analysis, such as Turing degrees, Pi-zero-one classes, determinacy, fine structure theory, or Hausdorff measures and capacities.

This is an ongoing joint project with Theodore Slaman.

In the late nineteen twenties and early nineteen thirties Arend Heyting, following Oskar Becker, identified proofs with fulfillments of mathematical intentions (in the sense of intentionality). The idea of proofs as fulfillment of intentions was then used by Heyting and Becker to interpret the intutionistic logical constants, and in this use it played an important historical role in the formulation of what is now called the BHK interpretation of the intuitionistic logical constants. The idea was that proofs in the sense of intuitionistic constructions are just forms of intuition, where intuitions are understood as fulfillments of mathematical intentions. A variant of this interpretation was formulated by Kolmogorov at around the same time, in terms of problems (in place of intentions) and solutions (in place of fulfillments). In recent times, Martin-Löf has again used the language of intention and fulfillment in some presentations of his work on intutionistic type theory. By association, there are also relationships to the Curry-Howard idea of formulae-as-types, and to other technical developments.

In my talk I will examine the idea of proofs as fulfillments of intentions, propose a related account of mathematical intuition, and consider the question whether the ideas of intentionality and proof as fulfillment (= intuition) in mathematics have applications that extend beyond constructive foundations. Can proofs in classical mathematics (e.g., set theory) be viewed as fulfillments of mathematical intentions?

Forcing axioms state that under favorable conditions objects which may be forced to exist in fact do exist. Forcing axioms answer many questions which ZFC alone does not provide answers for; one reason for this is that most of them yield large cardinals. We’ll survey answered and unanswered questions from this area.

Among Post’s achievements were:

  1. the first published proof of the completeness of propositional calculus,
  2. the first unsolvability proof for a mathematical problem outside of logic,
  3. being among the principal founders of modern recursion theory
  4. providing the formalism for the formal theory of languages.

This talk will provide a survey of this work in the context of his time.