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

To main page