September 29: Sunil Simon: Structured specification of strategies in games on graphs
16.00--17.00
Abstract:
In much of game theory, strategies (which are the core of game playing) are mostly treated as being atomic (unstructured). While this is adequate for reasoning "from above", where one is interested in the logical structure of the game itself, or that of removing dominated strategies, or existence of equilibria, it offers little help for how to play. When it comes to reasoning within the game, a player's choice of strategy depends not only on her knowledge of the game position but also her expectation of the strategies employed by other players of which she can only have partial knowledge. Moreover, strategies are completely known to players only in small games where a strategy amounts to picking a small number of moves; in games with rich structure, intricate reasoning about strategies can be called for. We discuss examples of strategies as they arise, say in Axelrod tournaments, their logical formalization, and some decidability results.

This is joint work with R. Ramanujam (IMSc., Chennai)

October 5: Shingo Saito: Knot points of typical continuous functions
16.00--17.00
Abstract:
Let $C([0,1])$ denote the Banach space of all real-valued continuous functions defined on the unit interval $[0,1]$. We say that a typical function $f\in C([0,1])$ has a property P if the set of all f with the property P is residual, i.e. contains a countable intersection of open dense sets. It is well known that a typical function $f\in C([0,1])$ is nowhere differentiable. Moreover, it turns out that a typical function $f\in C([0,1])$ has the property that at almost every point in $[0,1]$ the function f is the least differentiable from the viewpoint of Dini derivatives; such a point is called a knot point and the set of all knot points is denoted by K(f).

In this talk, we give a complete characterisation for a family S of subsets of $[0,1]$ to have the property that $K(f)\in S$ for a typical function $f\in C([0,1])$. The proof exploits the Banach-Mazur game and some results in descriptive set theory.

I will try to make the talk accessible to as many people as possible, so that people who know `first-year analysis' and the rudiments of topological spaces will be able to understand the statement of the main theorem.
To main page

October 12: Valery Plisko: Primitive recursive realizabilities
16.00--17.00
Abstract:
The notions of primitive recursive realizability introduced by Z.Damnjanovics (1994) and S.Salehi (2000) are considered. The main results:
1) these two notions are essentially different;
2) intuitionistic predicate logic is not correct relative to the Damnjanovics realizability.
To main page

November 2: Denis Bonnay: Invariance, Definability and Monoids
16.00--17.00
Abstract:
I will present a generalization of an (old) result by Marc Krasner on definability in infinitary logic and groups of automorphisms. Krasner showed that, given a set M, there is a one-one correspondence between sets of operations on M which are closed under definability in $L_{\infty,\infty}$ and groups of permutations on M. Independently, Solomon Feferman recently asked in which logical language operations invariants under strong homomorphisms were definable (I will define precisely what a strong homomorphism is). I will show that Feferman's question can be answered by generalizing Krasner's theorem, so as to get a one-one correspondence between sets of operations closed under definability in $L_{\infty,\infty}$ without equality and monoids of homomorphisms.
To main page

November 16: Tatiana Yavorskaya: Interacting explicit evidence systems
16.00--17.00
Abstract:
The logic of proofs LP, introduced by S. Artemov, originally designed for describing properties of formal proofs, became a basis for the theory of knowledge with justification (an agent knows F for the reason t). So far, in epistemic systems with justification the corresponding evidence part, even for multi-agent systems, consisted of a single explicit evidence logic.
In this talk I will speak about logics describing two interacting explicit evidence systems. These results are contained in:
Tatiana Yavorskaya (Sidon), Multi-agent Explicit Knowledge, Lecture Notes in Computer Science 3967 (2006), pp. 369-380.
To main page

November 23: Valentin Shehtman: More on completeness in first-order modal and intuitionistic logic
16.00--17.00
Abstract:
This is a continuation of the talk at this seminar in 2006. The situation in this field is quite complicated, because many simply formulated logics are incomplete in standard semantics. We shall recall the main definitions of Kripke-type and algebraic-type semantics and then concentrate on the recent advance in their investigation.
To main page

November 30: Sonja Smets: An Abstract Dynamic-Logical Setting for Quantum Mechanics
16.00--17.00
Abstract:
I present two (equivalent) abstract qualitative axiomatic settings for a dynamic logic of quantum actions: one in terms of Quantum Transition Systems, and the other in terms of Quantum Dynamic Algebras. I give a Representation Theorem showing that these axiomatizations are complete with respect to the concrete semantics given by (infinite-dimensional) Hilbert spaces. This means that they capture all the essential features of Quantum Mechanics. The proof uses known Representation results for standard quantum logic, due to Soler, Mayet and others.
However, I argue that the dynamic-logic setting gives a new view of quantum structures in terms of their underlying logical dynamics. This setting has a number of important advantages: 1) it provides a clear and intuitive dynamic-operational meaning to the usual quantum logic connectives (e.g. quantum negation, quantum implication etc) and to key quantum-logic postulates (e.g. Orthomodularity, Covering Law); 2) it reduces the complexity of the Soler-Mayet axiomatization by replacing key higher-order concepts (e.g. "automorphisms of the ortholattice") by first-order objects ("actions"); 3) it provides a link between traditional quantum logic and the needs of quantum computation.
This talk is based on my joint work with A. Baltag.
To main page

January 11: Ali Enayat: Nonstandard Omega-standard Models of Finite Set Theory
10.00--11.00
Abstract:
Finite set theory, here denoted FST, is the theory obtained by replacing the axiom of infinity by its negation in the usual axiomatization of Zermelo-Fraenkel set theory. An omega -model of FST is a model in which every set has at most finitely many elements (as viewed externally). Mancini and Zambella (2001) employed the Rieger-Bernays method of permutations to construct a recursive omega-model of ZF that is nonstandard ( i.e., not isomorphic to the hereditarily finite sets ). In this talk we focus on the metamathematical investigation of omega-model of FST. In particular, we (a) present a perspicuous construction of a recursive nonstandard omega-model of FST without the use of permutations; (b) use forcing to show that for each cardinal kappa between aleph_0 and the continuum (inclusive) there are 2^kappa nonisomorphic omega-models of FST of cardinality kappa; and (c) establish a completeness theorem for uncountable models by showing that there is a scheme S in the usual language of set theory such that the omega -models of FST + S are precisely those that are elementarily equivalent to an uncountable omega-model of FST.
This is joint work with Albert Visser.
To main page

February 15: Samson Abramsky: Full Completeness
16.00--17.00
Abstract:
Full Completeness results aim to characterize the `space of proofs' of a logical system, as a mathematical structure in its own right. Two styles of such characterization have been prominent: geometric, closely aligned with giving a diagrammatic notion of proof (e.g. proof-nets); and interactive, aligned with game semantics and `geometry of interaction'. One then seeks to show that the two kinds of characterization coincide. There are also interesting connections with various notions of `uniformity', such as (di)naturality, or invariance under logical relations.
We shall give an introduction to these ideas, and describe full completeness results for the multiplicative and multiplicative- additive fragments of linear logic.
To main page

February 22: Dag Westerstahl: Quantifiers, Freezing, Possessives, and Compositionality
16.00--17.00
Abstract:
Noun phrases in general denote type (1) (generalized) quantifiers (sets of sets). These are often, but not always, obtained from type (1,1) quantifiers (binary relations between sets) by freezing the first argument: the restriction. I discuss some questions related to decomposability (expressibility as frozen type (1,1) quantifiers) of type (1) quantifiers. Answers to these questions are relevant to certain semantic issues, notably the semantics of possessives. In particular, they point to a problem for the compositionality of possessive constructions.
To main page

March 28: Michael Rathjen: "Models" for intuitionistic set theories
14.00--15.00
Abstract:
There are central questions that have shaped the research activities in classical Cantorian set theory over the last 120 years.
Roughly speaking, these are questions addressing the independence of set-theoretic principles (e.g. via Gödel's L and forcing), the role of large set axioms, and the impact of the set-theoretic universe at large on the lower levels of the cumulative hierarchy (e.g. the real line).
Similar questions can be asked for set theories were the underlying logic is intuitionistic rather than classical. There is a widespread impression that the prize for relinquishing classical logic is high. However, the loss of certain comforting theorems of classical mathematics can also bring forth profits. Intuitionistic logic allows for axiomatic freedom in that one can adopt new axioms that are true in certain models (e.g. realizability models) but outrageously false classically.
The talk will survey some model constructions for intuitionistic set theories with an eye towards determining the proof-theoretic strengths of various systems.
To main page

April 4: Michiel van Lambalgen: Lawlessness, randomness and the axiom of choice
16.00--17.00
Abstract:
In the early 20th century two mathematicians coming from very different backgrounds proposed to allow infinite but incomplete objects in mathematics.
L.E.J. Brouwer allowed `free choice sequences', sequences of natural numbers which are constructed by freely choosing the next item in the sequence; and he proposed reasoning principles governing these objects. These principles entail that classical logic does not hold for freely chosen sequences.
The mathematician R. von Mises introduced very similar objects for a very different purpose: the foundations of probability. He claimed that a frequency interpretation of probability required so called `random sequences', an intuitive model of which is provided by the sequence of outcomes of tosses of a coin, and hwich von Mises thought were related to choice sequences.
Von Mises gave axioms for this notion and proceeded to develop probability theory on this basis. The axioms were soon criticised as being inconsistent, and von Mises' foundation for probability theory was abandoned in favour of Kolmogorov's axiomatisation in terms of measure theory.
However, it is possible to reformulate von Mises' axioms consistently as expressing the determinacy of a game, in which player I attempts to generate a random infinite binary sequence x and player II attempts to select an infinite subsequence of x whose statistical properties are different from x. Consistency of this form of determinacy is proven via a forcing argument; the earlier suspicion that the setup is inconsistent is actually due to inconsistency with the axiom of choice. Von Mises' observation that random sequences are related to choice sequences turns out to be correct, via an application of the double negation translation.
To main page

April 18: Patrick Dehornoy: RECENT PROGRESS ON THE CONTINUUM HYPOTHESIS, AFTER H.WOODIN
16.00--17.00
Abstract:
The recent work of H. Woodin significantly renewed Set Theory by restoring its global unity and making it more understandable. For the first time, there exists a reasonable hope of solving the Continuum Problem, and it is very interesting to discuss what this means in view of the classical undecidability results by Gödel and Cohen. At the very least, the results by Woodin show that the Continuum Problem is not just a meaningless scholastic question.
To main page

May 23: Mirna Dzamonja: Combinatorics of trees
16.00--17.00
Abstract:
We are interested in trees of size $\kappa$ with no $\kappa$ branches, and especially in their behaviour under the notion of tree embedding. A tree embedding is function between trees which preserves the strict tree order. This type of research has a long history, especially when $\kappa=\aleph_1$. We shall review some of the known results and then show some newer results with Väänänen in which we study the situation when $\kappa$ is singular of countable cofinality. At the end we shall show some of the insights we obtained with Thompson on the problem of finding a tree of size $\aleph_1$ with no uncountable branches into which all such trees tree-embed.
To main page

May 29: Sakaé Fuchino: Axiomatization of generic extensions by homogeneous partial orderings
16.00--17.00
Abstract:
In this talk we review some results on combinatorial principles introduced in [1] and [3]. These principles hold in the models of ZFC obtained e.g. as the generic extension of a ground model of CH by a ccc partial ordering which is a finite product of the copies of a partial ordering which is small enough compared to the size of the index set of the product. The principles seem to capture many properties of the generic extensions by partial orderings as above and thus can be seen as axiomatization of (some/many features of) such generic extensions.
The (measure theoretic) ``side by side'' product of (copies of) random algebra also has the homogeneity similar to the partial orderings as above in the sense that a bijection on the support of the product induces an automorphism of the partial ordering. Nevertheless, by a result of Kunen, we can show that the principles introduced in [1] do not hold in the generic extension by side by side product of random algebra (the random model). In contrast, the Fremlin-Miller Covering Property in [2] and its generalization considered in [3] can be shown to hold in a random model for adding more than aleph 3 random reals over a model of CH.

[1] Jörg Brendle and Sakaé Fuchino: Coloring ordinals by reals, Fundamenta Mathematicae, 196, No.2 (2007), 151-195.
[2] Arnold Miller, Infinite Combinatorics and Definability, Annals of Pure and Applied Logic, 41 (1989), 179-203.
[3] Sakaé Fuchino: A generalization of a problem of Fremlin, RIMS Kôkyûroku, No.1595 (2008), 6-13.
To main page

May 30: Kohei Kishida: Topological Completeness of First-Order Modal Logic
14.45--15.45
Abstract:
As McKinsey and Tarski [1] showed, the Stone representation theorem for Boolean algebras extends to algebras with operators (topo-Boolean algebras). This result gives topological semantics for (classical) propositional modal logic, in which the ``necessity'' operation is modeled by taking the interior of an arbitrary subset of a topological space. The topological interpretation was extended by Awodey and Kishida [2] in a natural way to full first-order logic (i.e., with function and constant symbols). This paper proves the resulting system of first-order S4 modal logic to be complete with respect to such topological semantics.
Joint work with Steve Awodey.

[1] J. C. C. McKinsey and A. Tarski, ``The Algebra of Topology,'' Annals of Mathematics 45 (1944), 141-91.
[2] S. Awodey and K. Kishida, ``Topology and Modality: The Topological Interpretation of First-Order Modal Logic,'' forthcoming in Review of Symbolic Logic.

June 13: Bart Kastermans: Stability and Posets
14.45--15.45
Abstract:
I'll talk about a paper (with Jockusch, Lempp, Lerman, and Solomon) about reverse math and recursion theoretic results related to the principle CAC: every infinite poset has an infinite chain or an infinite antichain.
To main page