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)

To main page

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.

To main page

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

To main page