Unless otherwise indicated, all meetings take place on Tuesdays at 4:15PM at 380-381T
The seminar is led by Professors Solomon Feferman and Grigori Mints.
Spring
- Apr 8: Flash Sheridan, Fixing Frege's Set Theory: Platonism and Church's Set Theory with a Universal Set
Materials: slides
Abstract (+/-):I discuss Alonzo Church's Set Theory with a Universal Set, together with my variant of it, and what I believe to be the philosophical motivation behind—and problems with—the theory. It allows the definition of some cardinal numbers by abstraction from the concept of equinumerosity, since it proves the existence of the Frege-Russell cardinal for every well-founded set. This is still, I maintain, the most satisfying answer to the question, "What is a number?", and is still the best available (albeit partial) explanation of the unreasonable effectiveness of mathematics. It brings the Neo-Fregean program somewhat closer to Frege's original intent, by avoiding the postulation of Hume's Principal.
Church's concluding remark, and his later unpublished and abandoned work, attempted to unify his approach with Quine's New Foundations. I maintain that Quine's comprehension schema is Platonistically unacceptable, and that the theory of cardinalities in New Foundations is mathematically regrettable, due in part to the apparently arbitrary denial of the existence of the singleton function.
My variant of Church's theory proves the existence of the singleton function, via a modification of Church's generalization of equinumerosity to a sequence of equivalence relations. A natural extension of my theory, with an eye to Feferman's desiderata for the foundations of category theory, leads to a variant of the Russell paradox.
Church sketched a construction to prove the equiconsistency of his theory with ZFC, though he apparently abandoned the actual proof. I discuss my simplification of his technique, and present a picture of my variant of his sequence of equivalence relations.
- Apr 15: Michael Beeson (San Jose State), Tarskian geometry and ruler-compass constructions
Materials: slides
Abstract (+/-):Tarski gave a beautiful axiom system of eleven axioms for Euclidean geometry. However, the connection of these axioms with ruler-and-compass constructions is not immediately clear, as not all the existential quantifiers correspond to ruler-and-compass constructions. A revision of Tarski's axioms that has nice relations with Euclid will be presented. Some stories from the interesting history of Tarski's axioms will be told, and a two-minute long, purely logical proof that Euclid's first four axioms do not imply Euclid 5 (the "parallel postulate"), will be presented. That result previously required the construction of models of non-Euclidean geometry.
- Apr 22: Vien Nguyen (Stanford), Ultraproducts. Preparatory material for the next talk and May 6
- April 29: Boris Zilber (Oxford), Schemes: Structures duality in geometry and logic
Abstract (+/-):The well-known duality of classical algebraic geometry between affine varieties and their co-ordinate rings has a perfect analogue in the theory of commutative C^*-algebras, which can be seen by the Gel'fand-Naimark theorem as the algebras of continuous complex-valued functions on a compact Hausdorff space. We interpret this as the Syntax-Semantics duality. In modern geometry and physics one deals with much more advanced generalisations of co-ordinate algebras, such as schemes, stacks and non-commutative C^*-algebras, where a geometric counterpart is no longer readily available and in many cases is believed impossible. I will discuss a model-theoretic project which challenges this point of view.
- May 6: Maryanthe Malliaris (Chicago), An ultrapower characterization of simple theories
paper
Abstract (+/-):Keisler's order is a large scale classification program which compares the complexity of first-order theories via saturation of ultrapowers. Recent joint work of Malliaris and Shelah on this order has led to a characterization of the so-called simple theories via saturation of ultrapowers, the first such characterization of an unstable class. The talk will present this theorem and explain its significance. I will assume familiarity with the definition of ultraproduct, but will plan to give all other relevant definitions.
- May 13: Johan van Benthem (Stanford/Amsterdam), Generalized Models: Opportunism, or Courage?
Materials: handout
Abstract (+/-):Henkin's generalized models for higher-order logic are a widely used technique in logic, but their status and reach remains a matter of dispute. I will present some main themes from a paper under construction for a Henkin Centennial Volume with co-authors Hajnal Andréka, Nick Bezhanishvili, and Ístvan Németi, on the scope and justification of the method. We look at general models in terms of 'the right intended models', calibrating proof strength, algebraic representation, lowering core complexity of logics, and set-theoretic absoluteness. Our systematic aim is finding general perspectives on how to design natural generalized models, and where possible, finding connections between these. We will state some new results along these lines, while also extending the scope from classical examples to a more recent candidate for a Henkin- style generalized semantics: fixed-point logics of computation.
- May 20: Aran Nayebi (Stanford), Lower bounds for advised quantum computations
Materials: slides
Abstract (+/-):A quantum query lower bound is the fundamental means of measuring the cost, or resources, needed by any quantum algorithm to carry out a task. Query lower bounds offer formal insights into the limitations of quantum computations. However, these techniques are well-established for computations that do not take advice. “Advice” is supplementary pre-computed information that is supplied along with the original input, such as a bit string or a look-up table, that allows the computation to carry out a given task faster than without it. While advice is well established in the classical setting (since Karp and Lipton), query lower bounds for non-trivial quantum computations that take advice have not yet been reported. This talk will discuss an application (obtained in collaboration with Trevisan, Belov, and Aaronson) of a little used lower bound technique, known as the “hybrid argument” (that has since been superseded by more modern techniques), to obtaining quantum query lower bounds for two related problems that take advice: Yao’s box problem and inverting a random permutation with advice. The former is a simpler version of the latter problem, which has important applications to cryptography.
- May 27: Solomon Feferman (Stanford), A rationale for admissible analogues of indescribable cardinals
Abstract (+/-):In the early 1970s Peter Aczel and Wayne Richter proposed certain analogues of indescribable cardinals for admissible ordinals, without offering a clear rationale; moreover, they only gave details for one case. What is offered is a rationale that yields the analogues via the lifting of notions of hereditarily continuous functionals from ordinary recursion theory to admissible recursion theory. This is work in progress, partly with Aczel and Richter.
- Jun 3: Lou van den Dries (Berkeley/Illinois), Transseries
Abstract (+/-):Transseries originated some 25 years ago, mainly in Ecalle's work on plane analytic vector fields, and also, independently, in connection with Tarski's problem on the real exponential field. Some 20 years ago I formulated some conjectures about the differential field of transseries, and started work on it, first joint with Matthias Aschenbrenner, and a few years later also in collaboration with Joris van der Hoeven. Around 2011 we finally saw a clear path towards a proof, sharpening the conjectures in the mean time. Two months ago we finished the job. I will explain transseries. motivate these conjectures, and try to give an inkling of the proofs, assuming only basic knowledge of mathematics and (first-order) logic and model theory.
Winter
This quarter, the primary focus is a reading group on a draft of Constructive Set Theory by Peter Aczel and Michael Rathjen. Meetings for that will be on Fridays, at 12-115PM in 380-380F. Research talks will still be on Tuedsays at 4:15PM in the same room.
Autumn
This quarter, the primary focus is a reading group on Topoi by Robert Goldblatt. Meetings for that will be on Fridays, at 12-115PM in 380-381U. Research talks will still be on Tuedsays at 4:15PM in the same room.
- Sept 27: Organizational Meeting
- Oct 4: chs. 1-2, Peter Hawke
- Oct 11: ch. 3, Tania Rojas-Esponada
- Oct 18: ch. 4, Vien Nguyen
- Tues, Oct 22: Rohit Parikh (CUNY, Computer Science), Knowledge is Power, and so is Communication
Abstract (+/-):The BDI theory says that people's actions are influenced by two factors, what they believe and what they want. Thus we can influence people's actions by what we choose to tell them or by the knowledge that we withhold. Shakespeare's Beatrice-Benedick case in Much Ado about Nothing is an old example.
Currently we often use Kripke structures to represent knowledge (and belief). So we will address the following issues:
a) How can we bring about a state of knowledge, represented by a Kripke structure, not only about facts, but also about the knowledge of others, among a group of agents?
b) What kind of a theory of action under uncertainty can we use to predict how people will act under various states of knowledge?
c) How can A say something credible to B when their interests (their payoff matrices) are in partial conflict?
- Oct 25: no seminar (Stanford School of Philosophy of Science conference)
- Tues, Oct 29: Gerhard Jäger and Thomas Strahm (Bern), Stratified Inductive Definitions
Abstract (+ / -):We consider subsystems of the well-known theory ID_1 in which fixed point induction is stratified in the sense that the $\alpha$th approximation of the fixed point only refers to approximations of levels less than $\alpha$. A complete proof-theoretic analysis of the finite and transfinite cases will be given. In our context we work over Peano arithmetic and deal wih generalized inductive definitions. Our approach has been motivated by work of Leivant who introduced the idea of stratified complete induction.
- Nov 1: chs. 5-6, Shane Steinert-Threlkeld
- Nov 8: Sam Saunders (Ghent)
- Nov 15: chs. 7-8
- Tues, Nov 19: Michael Rathjen (Leeds)
- Nov 22: chs. 9-10
- Nov 29: no meeting (Thanksgiving break)
Last modified