Johan van Benthem

Title: Topology and Modal Logic: Space for Knowledge

Abstract: Topological logics have been used for modeling knowledge since Tarski's semantics for intuitionism in the 1930s. In this talk, we take up this line, showing how topological semantics for epistemic logic can model finer distinctions than graph semantics, in particular, new varieties of common knowledge. Our main tool are products of modal logics in topological semantics. This talk is based on joint work with Guram Bezhanishvili, Balder ten Cate, and Darko Sarenac.

Guram Bezhanishvili

Title: Completions and Compactifications

Abstract: I will discuss several completions that are useful in the study of modal and intermediate logics, and describe their dual spaces in terms of various compactifications.

Balder ten Cate

Title: Beth Definability in Modal Logic Revisited

Abstract: It is known already for a long time that the following analogue of Beth's definability theorem holds for the basic modal logic K:

Whenever a set of modal formulas T implicitly defines a proposition letter p (meaning, roughly, that, in models globally satisfying T, the interpretation of p is uniquely determined) then one can find an explicit definition of p relative to T (i.e., a formula with no occurrences of p, that is equivalent to p on models globally satisfying T).

In this talk I want to raise attention to an interesting open problem: how long is the shorted explicit definition? We restrict to the case where T is a finite set. I will discuss some partial results: (a) on the one hand, there are cases where the shortest explicit definition is exponentially longer than T; (b) on the other hand, one can always find an explicit definition whose length is at most doubly exponential in the size of T (in the case of uni-modal K) or triply exponential (in the case of a multi-modal K).

Mai Gehrke

Title: Complete congruences of up-set lattices

Abstract: It is a powerful result in Priestley duality that the congruences of a bounded distributive lattice are in one-to-one correspondence with the closed subsets of its Priestley space. On the other hand, the canonical extension functor σ lifts any DL quotient q:D→E to a complete quotient of up-set lattices q^σ:D^σ→E^σ. In the presence of canonicity it is typically the case that duality results may be obtained from the corresponding discrete duality result by the overlay of the obvious minimum topological condition.

In the restricted setting of Boolean algebras the congruence result fits this pattern: the complete congruences of a powerset lattice are in one-to-one correspondence with all the subsets of its dual and the lifted ones must correspond to closed subsets. However, for up-set lattices in general, there are MORE complete quotients than those given by subsets of the dual.

In joint work with Marcel Erne and Ales Pultr we investigate which posets have the property that all complete congruences of their up-set lattice are determined by subsets of their dual. This problem is related to the problem in point-free topology of characterizing those spaces for which all sublocales are spatial, and our work is set in that context.

Robin Hirsch

Title: Relation Algebra Reducts of Cylindric Algebras and Complete Representations

Abstract: The most commonly used algebras of relations are relation algebra and n-dimensional cylindric algebra, for various n. Relation algebras are closely related to fields of binary relations and n-dimensional cylindric algebras are based on fields of n-ary relations.

For any n-dimensional cylindric algebra C (n≥3) we can define the relation algebra reduct Ra(C) by taking the two dimensional elements of C and using the third dimension to define converse and composition. The relation algebra reduct is the key tool for connecting cylindric algebras to relation algebras. Quite a lot is known about the class of subalgebras of reducts of n-dimensional cylindric algebras: the class is a canonical variety, for example. The neat embedding theorem says that a relation algebra is representable if and only if it is a subalgebra of a relation algebra reduct of an ω-dimensional cylindric algebra.

Much less is known about the class of relation algebra reducts of n-dimensional cylindric algebras (here we do not take subalgebras). In this talk we will show that this class is not closed under subalgebras nor under elementary equivalence. On the other hand, the class is pseudo-elementary, even for infinite n, and hence the elementary theory of this class is recursively enumerable. We establish a complete version of the neat embedding theorem: a countable relation algebra has a complete representation if and only if it is a strong subalgebra of the relation algebra reduct of an ω-dimensional cylindric algebra.

Ian Hodkinson

Title: Modal Logics of Elementary Classes of Kripke Frames via Hybrid Logic

Abstract: The modal logics of elementary classes of Kripke frames are precisely those logics that can be captured by sets of pure positive hybrid logic sentences with arbitrary existential and relativised universal quantification over nominals. Each such hybrid sentence H syntactically generates an infinite set of modal formulas called 'approximants', which together axiomatise the modal logic of the class of frames validating H. This generalises to sets of hybrid sentences. The proof is analogous to standard proofs of Sahlqvist's theorem, combined with results of van Benthem and Goldblatt on 'pseudo-equational' first-order sentences.

Roman Kontchakov

Title: On Dynamic Topological Logics

Abstract: We investigate computational properties of propositional logics for dynamic topological logics. We consider dynamic topological systems (T,f), where T is a topological space and f a continuous function on T. The logics come with `modal' operators interpreted by the topological closure and interior and `temporal' operators interpreted along the orbits {f(w),f²(w),...} of points w of T . First, we consider the case of homeomorphic mappings f and show that for various classes of topological spaces T the resulting logics are not recursively enumerable (this gives a negative solution to a conjecture of Kremer and Mints). Second, we present a new result and show that for a more general class of continuous functions f the resulting logics are still undecidable.

This is joint work with Boris Konev, Frank Wolter and Michael Zakharyaschev.

Alexander Kurz

Title: Relating Algebras on Ind and Pro Completions

Abstract: We prove a general representation theorem for algebras for a functor. In detail: Consider a small, finitely complete and cocomplete category C and functors H on the Ind-completion of C and K on the Pro-completion of C (where Ind-completion refers to the completion with filtered colimits, Pro-completion being defined dually). In this situation there are adjoint functors S: IndC→ProC and P: ProC→IndC. Theorem: If H preserves filtered colimits and K does so weakly, then any H-algebra can be embedded into the P-image of a K-algebra.

This is joint work with Jiri Rosicky.

Szabolcs Mikulas

Title: Axiomatizing Temporal Epistemic Logic

Abstract: We will look at temporal versions of epistemic logic with perfect recall. We distinguish between the uniform version, where the agents have the same linear flow of time, and non-uniform version, where different agents might live in different linear times. We show that the non-uniform version with future and past modalities has finite axiomatization, while the uniform version is not finitely axiomatizable in general.

This is joint work with Tim French and Mark Reynolds.

Mikhail Sheremet

Title: On the logic of comparative similarity

Abstract: We consider the logic of comparative similarity CSL with the binary closer operator ⇇ as the only 'modality.' The models for CSL are based on metric spaces and ⇇ is interpreted as follows: for subsets A and B of a metric space X, A⇇B is the set of all points in X that are located strictly closer to A than to B.

We are interested in investigating the computational complexity of CSL in various classes of models. We have a positive result in the general case.

THEOREM 1. The satisfiability problem for CSL is decidable in the class of models based on metric spaces.

However the precise complexity is still unknown in this case.

A metric space X is said to be a min-space if the distance between any nonempty subsets A and B of X is equal to a distance between some points a∈A and b∈B.

THEOREM 2. In the class of models based on min-spaces the following holds:

1. CSL has the finite model property,
2. the satisfiability problem is ExpTime-complete.

The situation changes if the 'dimension' of models is fixed. By a reduction of the solvability problem for Diophantine equations we prove

THEOREM 3. For each n≥1, the satisfiability problem for CSL is undecidable in the classes of all models based on:

• min-subspaces of ℝⁿ, or ℚⁿ, or ℤⁿ.
• finite subspaces of ℝⁿ, or ℚⁿ, or ℤⁿ.
• the spaces of ℝⁿ, or ℚⁿ, or ℤⁿ.

This is a join work with Dmitry Tishkovsky, Frank Wolter and Michael Zakharyaschev.

Yde Venema

Title: Topo-roots and monoliths

Abstract: We give a characterization of the simple, and of the subdirectly irreducible boolean algebras with operators (including modal algebras), in terms of the dual descriptive frame, or, topological relational structure. These characterizations involve a special binary topo-reachability relation on the dual structure; we call a point u a topo-root of the dual structure if every ultrafilter is topo-reachable from u. We prove that a boolean algebra with operators is simple iff every point in the dual structure is a topo-root; and that it is subdirectly irreducible iff the collection of topo-roots is open and non-empty in the Stone topology on the dual structure iff this collection has non-empty interior in that topology.