September 17: Mehrnoosh Sadrzadeh: What is the vector space content of what we say? A compact categorical approach to meaning
16.00--17.00
Abstract:
Words are building blocks of sentences, yet the meaning of a sentence goes well beyond meanings of its words. Formalizing the process of meaning assignment has been a foundational quest for computational and mathematical linguistics, but two most successful approaches there each miss on a key aspect: the 'logical' one misses on the meanings of words, the vector space one on the grammar. I will present a setting where we can have both! This is based on recent advances in grammar by Lambek pregroups and in vector spaces of physics by Abramsky and Coecke, both using compact categories! I will work through a concrete application built from document corpora, where for the first time in the field we are able to compute and compare meanings of transitive sentences compositionally. The fun part is the use of diagrammatic calculus of compact categories, which visualizes and simplifies the computations to a great extent. This is collaborative work with many people, among which are C. Clark, B. Coecke, M. Fernandez, E. Greffenstete, A. Preller, S. Pulman.
To main page

October 15: Jouko Väänänen: Dependence logic - recent developments and open problems
17.00--18.00
Abstract:
After a brief introduction to the logic of the concept "variable x depends only on variables y_1,...,y_n", or in other words to the logic of functional dependence, also known as "Dependence Logic" (Dependence Logic, J.Vaananen, Cambridge University Press, 2007), I propose a logic the fundamental concept of which is independence rather than dependence. (By the way, independence is here not merely the negation of dependence!) I discuss the basic properties of this "Independence Logic" as well as some illuminating examples.
To main page

November 15: Rod Downey: Yet More on Algorithmic Dimension
17.00--18.00
Abstract:
Dimensions such as Hausdorff and packing dimensions seek to refine classical Lebesgue measure. Effective randomness seeks to quantify what it means for an individual sequence to be random. In the same spirit, effective notions of dimensions seek to give meaning to the notion of a sequence being "partially random". I will look at some recent results in algorithmic dimen- sion, particularly to extraction and relationship to algorithmic computational power.
To main page

November 26: Marek Zawadowski: The Opetopic Approach to Higher Dimensional Categories
16.00--17.00
Abstract:
The opetopes, the opetopic sets, and the opetopic categories were introduced by J.Baez and J.Dolan in 1997. At that time the opetopic approach to the higher dimensional categories seemed to be one of the most promising. Since then several authors contributed to the development of this theory. However the theory, in spite of its advantages, is developing slowly. In my talk I will explain why I think it is important to develop this theory, what is the main difficulty of the theory, what have being achieved so far, and what are the prospects.
To main page

November 26: Andy Lewis: The search for natural definability in the Turing degrees
17.00--18.00
Abstract:
While it is known that the jump and the jump classes other than low are definable, there remains a conspicuous lack of natural definability results for the Turing degrees. I shall outline a programme of research which aims to find natural definability results by methodically establishing the order theoretic properties satisfied by the degrees in each jump class, starting with very simple properties and then moving gradually to consider properties which are more complex.
To main page

December 17: Tom Sterkenburg: The number of K-trivial sets
16.00--17.00
Abstract:
We call a set (seen as an infinite binary string) K-trivial if it has a very low descriptive complexity. To be more precise, all its initial segments have a description not more than some constant longer than the description of their length. In this talk, we investigate the arithmetical complexity of the function that computes the exact number of sets that are K-trivial via a given constant. This we do by representing them as infinite paths of binary trees, and manipulating these trees to make it easier to count their paths.
To main page

May 9: Jouko Väänänen: Second Order Logic or Set Theory?
16.00--17.00
Abstract:
The question whether second order logic is a better foundation for mathematics than set theory is addressed. The main difference between second order logic and set theory is that set theory builds up a transfinite cumulative hierarchy while second order logic stays within one application of the power sets. It is argued that in many ways this difference is illusory. More importantly, it is argued that the often stated difference, that second order logic has categorical characterizations of relevant mathematical structures, while set theory has non-standard models, amounts to no difference at all. Second order logic and set theory permit quite similar categoricity results on one hand, and similar non-standard models on the other hand. We also give some results which seem to suggest that there are serious problems in trying to use second (or higher) order logic to understand second order truth without recourse to set theory.
To main page

May 16: Juliette Kennedy: On Inner Models from Extended Logics
16.00--17.00
Abstract:
Gödel's L, the hierarchy of constructible sets, is defined by reference to first order definability. We investigate to what extent it is essential that first order definability is used. Preliminary results show that there is a great variability in the choice of the logic generating L, and the same is true of the hereditarily definable sets. We also discuss some new, intermediate inner models arising from generalized quantifiers.
This is joint work with Menachem Magidor and Jouko Väänänen.
To main page

June 23: Andreas Weiermann: Provably recursive functions for PA
16.00--17.00
Abstract:
We give a streamlined version of the following classical result about first order Peano arithmetic PA:
If f is a recursive function such that PA can prove the totality of f then f can be obtained by a suitable recursion along an ordinal smaller than the first fixed point of the ordinal exponentiation function with respect to base omega.
The talk is in principle intended for beginners in proof theory but some basis knowledge of ordinals is presupposed (Cantor normal forms and the like). Knowledge of cut elimination for predicate logic might be helpful but is not required.
The talk will be given on a blackboard and active feedback from the audience is encouraged.
To main page

July 7: Takayuki Kihara: Mass Problems, Constructivism, and Learnability
16.00--17.00
Abstract:
Mass problems were introduced by Medvedev (1955) in order to provide a semantics of the intuitionistic propositional calculus (IPC). In his interpretation,
(*) each proof is interpreted as a sequence of natural numbers;
(*) each proposition Q is interpreted as a set [[Q]] of sequences of natural numbers (this is called a mass problem);
(*) Q is true iff [[Q]] has a computable proof.

Though his interpretation is not exactly IPC, it is exactly Jankov's Logic consisting of IPC plus the weak law of excluded middle, not phi or not not phi. To prove various theorems on the Medvedev lattice, some researchers introduced a powerful method. This method gives rise to a kind of "disjunction" under the limit---BHK interpretation of Limit Computable Mathematics (abbreviated LCM), a kind of constructive mathematics based on Learning Theory. This allows us to define various disjunctions as operations on the power set of Baire space. When disjunctive notions are represented as operations on subsets of Baire space, this enables us to compare "degrees of difficulty" of disjunctive notions. This allows us to formalize the intuition that the intuitionistic disjunction is somehow more difficult than the classical one. We then introduce the notion of learnability for subsets of Baire space. In this way, we can obtain a better understanding of the behavior of degrees of difficulty of disjunctive notions.
To main page

July 29: Eduardo Giovannini: Hilbert's Early View on Completeness and Categoricity
16.00--17.00
Abstract:
The aim of the presentation is to examine the connections between Hilbert's axiom of completeness and his early notion of completeness of an axiomatic system. The historical and conceptual origin of the axiom will be analyzed, mainly on the basis of Hilbert's notes for lecture courses on geometry and arithmetic between 1894 and 1905. I shall argue that, in the case of the axiomatic system for Euclidean geometry, the axiom of completeness does not have directly anything to do with the completeness of the axiomatic system in a syntactic or semantic sense. Instead, it is explicitly designated to introduce into geometry the usual continuity conditions, but in such a way that it facilitates the "meta-geometrical" investigations.
To main page