Logic Colloquium

Denis R. Hirschfeldt
Professor of Mathematics, University of Chicago
will speak
on
Lowness Properties and Cost Functions
on
Friday, November 20, 2009
in
60 Evans Hall
at
4:10 p.m.
The biweekly LOGIC TEA will be held in the Alfred Tarski Room (727 Evans Hall) immediately following the Colloquium (with support from the Graduate Assembly).

One of the byproduts of recent developments in the theory of algorithmic randomness is an increased interest in notions of computability-theoretic lowness. We will focus on two such notions: K-triviality, which is a natural notion of “randomness-theoretic weakness” with a number of interesting characterizations, and strong jump traceability, which has a more combinatorial definition but is also strongly connected to algorithmic randomness. In particular, we will see how these notions can be characterized in terms of two other powerful ideas arising from the theory of algorithmic randomness: cost functions and diamond classes.

We will use these themes to explain some of the issues of current interest in the rapidly developing area of algorithmic randomness, including a discussion of some major open questions.

MARTIN DAVIS
Professor Emeritus of Mathematics and of Computer Science
Courant Institute, New York University
Visiting Scholar in Mathematics, University of California, Berkeley
will speak on
Reflections on Hilbert’s 10th Problem with a New Conjecture
on
Friday, November 6, 2009
in
60 Evans Hall
at
4:10 p.m.
The biweekly LOGIC TEA will be held in the Alfred Tarski Room (727 Evans Hall) immediately following the Colloquium (with support from the Graduate Assembly).

Hilbert’s 10th Problem asked for an algorithm to determine whether a given polynomial equation with integer coefficients has an integer solution. In this talk I will discuss the negative solution to the problem as well as various extensions.

LARA BUCHAK
Assistant Professor of Philosophy
University of California, Berkeley
will speak
on
Different Decision or Different Decision Theory?: Modeling Risk Aversion
on
Friday, October 23, 2009
in
60 Evans Hall
at
4:10 p.m.
The biweekly LOGIC TEA will be held in the Alfred Tarski Room (727 Evans Hall) immediately following the Colloquium (with support from the Graduate Assembly).

Decision theory is supposed to accommodate any preferences that a rational decision maker might have. I show that standard decision theory -– expected utility theory -– cannot accommodate common preferences that stem from the way apparently rational decision makers account for risk. I propose a generalization of expected utility theory that can accommodate these preferences, and show that it has all the theoretical power of the standard theory: in particular, it has a representation theorem that allows us to derive an agent’s beliefs, desires, and attitudes towards risk from his preferences. I then explore a classic strategy for responding to counterexamples of the type I present: re-characterizing the choice problem facing an agent, by individuating outcomes more finely. This introduces an important question in the methodology of decision theory: under what circumstances should we interpret the agent as facing a different choice problem rather than adopt a different theory to describe his behavior? I approach this question formally, and show that we cannot individuate the outcomes to make his behavior compatible with expected utility theory without also making his behavior compatible with many other opposing theories: thus, I suggest, we cannot save the standard theory.

NATE ACKERMAN
Visiting Scholar in Mathematics
University of California, Berkeley
will speak
on
Trees, Sheaves, and Definition by Recursion
on
Friday, October 9, 2009
in
60 Evans Hall
at
4:10 p.m.
The biweekly LOGIC TEA will be held in the Alfred Tarski Room (727 Evans Hall) immediately following the Colloquium. (with support from the Graduate Assembly).

We will show there is a topological space for which presheaves are the same thing as trees. We will further show that there is a sheaf on this topological space which has an important relationship with Baire space.

We will then use these connections to show how a definition by transfinite recursion can be thought of as an operation on sheaves, and how the well-definedness of such a definition can be thought of as a property of the sheaf we are working on. This will then allow us to define a second-order tree as a sheaf on a tree and to expand our notion of definition by transfinite recursion to all well-founded second-order trees (even those which are ill-founded as normal trees).

We will then mention how these techniques can be used to prove a variant of the Suslin-Kleene Separation theorem.

DANA S. SCOTT
University Professor, Emeritus, Carnegie Mellon University
Visiting Scholar, University of California, Berkeley
will speak
on
Mixing Modality and Probability
on
Friday, September 25, 2009
in
60 Evans Hall
at
4:10 p.m.
The biweekly LOGIC TEA will be held in the Alfred Tarski Room (727 Evans Hall) immediately following the Colloquium (with support from the Graduate Assembly).

Orlov first [1928] and Gödel later [1933] pointed out the connection between the Lewis System S4 and Intuitionistic Logic. McKinsey and Tarski gave an algebraic formulation and proved completeness theorems for propositional systems using as models topological spaces with the interior operator corresponding to the necessitation modality. Earlier, Tarski and Stone had each shown that the lattice of open subsets of a topological space models intuitionistic propositional logic. Expanding on a suggestion of Mostowski about interpreting quantifiers, Rasiowa and Sikorski used the topological models to model many first-order logics. After the advent of Solovay’s recasting of Cohen’s independence proofs as using Boolean-valued models, topological models for modal higher- order logic were studied by Gallin and others. For Boolean-valued logic, the complete Boolean algebra M = Meas([0,1])/Null of measurable subsets of the unit interval modulo sets of measure zero gives every proposition a probability. Perhaps not as well known is the observation that the measure algebra also carries a nontrivial S4 modality defined with the aid of the sublattice Open([0,1])/Null of open sets modulo null sets. This sublattice is closed under arbitrary joins and finite meets in the measure algebra, but it is not the whole of the measure algebra. By working by analogy to the construction of Boolean-valued models for ZF, we can construct over M a model for a modal ZF (MZF) where membership and equality predicates have interesting and natural modal properties. In such a universe the real numbers correspond to random variables, and — following a suggestion of Alex Simpson (Edinburgh) — there is also a well-motivated modeling of random reals. A modal set theory, however, requires a reexamination of comprehension principles, and much work remains to be done to organize methods of proof to take account of the new distinctions encountered. It is also possible to recast well-known theorems of Ergodic Theory as principles about this modal universe, and the question to be considered is whether the new perspective can lead to some new results.

THEODORE A. SLAMAN
Professor and Chair of Mathematics
University of California, Berkeley
will speak
on
Degree Invariant Functions
on
Friday, September 11, 2009
in
60 Evans Hall
at
4:10 p.m.
The biweekly LOGIC TEA will be held in the Alfred Tarski Room (727 Evans Hall) immediately following the Colloquium (with support from the Graduate Assembly).

We will discuss the issues surrounding Martin’s conjectured characterization of the functions on reals which are invariant with respect to Turing degree. We will give a recent application, obtained jointly with Montalban and Reimann, to the question of whether Turing equivalence is universal among countable Borel equivalence relations.

PAOLO MANCOSU
Professor of Philosophy
University of California, Berkeley
will speak on
Measuring the size of infinite collections of natural numbers: Was Cantor’s theory of infinite number inevitable?
on
Friday, August 28, 2009 - in
60 Evans Hall
at
4:10 p.m.
The biweekly LOGIC TEA will be held in the Alfred Tarski Room (727 Evans Hall) (with support from the Graduate Assembly).

Cantor’s theory of cardinal numbers offers a way to generalize arithmetic from finite sets to infinite sets using the notion of one-to-one correspondence between two sets. As is well known, all countably infinite sets have the same ‘size’ in this account, namely that of the cardinality of the natural numbers. However, throughout the history of reflections on infinity another powerful intuition has played a major role: if a collection A is properly included in a collection B than the ‘size’ of A should be less than the ‘size’ of B (part-whole principle). This second intuition was not developed mathematically in a satisfactory way until quite recently. In this talk I begin by reviewing the contributions of some thinkers who argued in favor of the assignment of different sizes to infinite collections of natural numbers. Then, I present some recent mathematical developments that generalize the part-whole principle to infinite sets in a coherent fashion. Finally, I show how these new developments are important for a proper evaluation of a number of positions in philosophy of mathematics which argue either for the inevitability of the Cantorian notion of infinite number (Gödel) or for the rational nature of the Cantorian generalization as opposed to that, offered by Bolzano, based on the part-whole principle (Kitcher).