Introduction. We start by briefly describing the strong colouring problem for permutation groups that was investigated in [13] and [12]; this problem has its origins in the classification of maximal partial clones over a finite non-empty set [14, 15, 16]. We shall immediately reformulate this decision problem as a Constraint Satisfaction Problem (CSP) in order to exploit various universal algebraic tools to study its algorithmic complexity.

Introduction. For f ∈ ωω and an ultrafilter U on ω define f(U) = {X ⊆ ω: f−1(X) ∈ U}, and for f, g ∈ ωω we say that f = g mod U if there is X ∈ U such that f(n) = g(n) for n ∈ X.

We say that U is Hausdorff if for any two functions f, g ∈ ωω, if f(U) = g(U) then f = g mod U.

Let FtO be the collection of all finite-to-one functions f ∈ ωω. Recall that an ultrafilter U is a p-point if for every function f ∈ ωω either there is n such that f−1({n}) ∈ U or there exists g ∈ FtO such that f = g mod U. Similarly, U is Ramsey if for every function f ∈ ωω either there is n such that f−1({n}) ∈ U or there exists a one-to-one function g ∈ ωω such that f = g mod U.

In this paper we will assume that all ultrafilters U, and their images f(U) are non-principal.

It is worth mentioning that the following appears as an exercise in [7]. If f(U) = U then f = id mod U. Therefore, if U is not Hausdorff, then this is witnessed by two functions, both not one-to-one mod U. It follows from it that Ramsey ultrafilters are Hausdorff.

From congruence varieties to tolerance identities. In the present section we briefly describe how two seemingly unrelated notions used in universal algebra came in touch in an unexpected way. We first recall some basic notions and terminology. Introductory textbooks to universal algebra are, among others, [1, 9, 26]. For a reader not familiar with universal algebra, a preliminary reading of the survey [16] would probably be of great help.

The Logic Colloquium 2004, the European Summer Meeting of the Association for Symbolic Logic, was held in Torino, Italy, 25–31 July 2004.

With more than 280 participants from all over the world, ten one-hour plenary lectures, four tutorials (three hours each), a panel discussion, three special sessions (with 20 speakers), and more than 200 contributed talks, the Logic Colloquium 2004 managed to present a broad spectrum of ideas, results, techniques, and problems in current research in logic.

The Program Committee consisted of: Toshiyasu Arai, Warren Goldfarb, Greg Hjorth, Dick de Jongh, Steffen Lempp, Gabriele Lolli, David Marker, Tony Martin, Ralph McKenzie, Wolfram Pohlers (Chair), Wilfried Sieg, Andrea Sorbi, and Alex Wilkie.

The Local Organizing Committee consisted of: Alessandro Andretta (Chair), Stefano Berardi, Riccardo Camerlo, Ugo de'Liguoro, Mariangiola Dezani, Alberto Marcone, Nicola Olivetti, and Domenico Zambella.

The meeting was organized by the logicians at the Dipartimento di Matematica and Dipartimento di Informatica of the University of Torino and was held at the Centro Congressi dell'Unione Industriale.

Sponsors. We would like to express our sincerest thanks to the following institutions, which, with their generous financial support, made this meeting possible. First and foremost, the Association for Symbolic Logic, which gave us the opportunity to organize the meeting and supported many students and post-docs with travel grants.

Introduction. This article presents some results of a research program with the goal of formulating extensions of Martin-Löf type theory (MLTT) that are proof-theoretically as strong as possible while remaining predicatively justified, and of determining their precise proof theoretic strength. We see three main reasons for following this research program:

1. The goal is to develop type theoretic analogues of the theories analysed in proof theory. In this way we hope to make the rather abstract and technically difficult results from proof theory more accessible to the general audience, and we hope as well to give some computational meaning to those results. This will be particularly important in case of the Π3-reflecting universe (to be presented in the follow-up article [37]), which was developed from Rathjen's ordinal notation system [26] for KP + (Π3− refl) (Kripke-Platek set theory extended by the principle of Π3-reflection).

The name of Paul Bernays (1888-1977) is familiar probably first of all for his contributions to mathematical logic. Many of those were in the context of his position as David Hilbert's junior collaborator in his proof-theoretic program inaugurated after the first World War. For those of us starting out in logic in the mid-twentieth century, the monumental Grundlagen der Mathematik of Hilbert and Bernays was one of the basic works in mathematical logic that we were obliged to study. That was the more true for those like me who aspired to work in proof theory.

Bernays' collaboration with Hilbert ended with the publication in 1939 of volume II of that work. Because the Nazis had forced his removal from his position in Göttingen in 1933, the collaboration ceased to be face-to-face in 1934, when Bernays moved to Zürich, where he lived for the rest of his life.

Bernays is also known, though less well known, as a philosophical writer. The fact that he had some philosophical training was apparently a reason why Hilbert chose him as his collaborator. Constance Reid tells the story that when Hilbert visited Zürich in 1917, he went for a walk with two local mathematicians, Bernays and Georg Pólya. The conversation turned to philosophy, and although Pólya was usually rather voluble and Bernays was not, this time Bernays did most of the talking. On the spot Hilbert invited Bernays to Göttingen to work with him, and Bernays accepted.