Introduction. Propositional calculi are usually defined by systems of axioms schemes and rules of inference. Natural problems arising in general study of logical calculi, for example, the problemof equivalence or the problem of determining for arbitrary calculus whether it is consistent or not, are, in general, undecidable. The first undecidability results for propositional calculi were found by S. Linial and E. Post in 1949 [16]. In particular, it was proved that the property “to be an axiomatization of the classical propositional logic” is undecidable. In 1963 A. V. Kuznetsov [13] found an essential extension of this result. He proved that for every superintuitionistic logic L the property “to be an axiomatization of L” is undecidable. In particular, consistency andmany other properties of calculi are, in general, undecidable. In [3] A. V. Chagrov has given a survey of results on undecidable properties of propositional calculi. Here we concentrate on decidable properties.

When we restrict ourself by considering particular families of calculi, for instance, propositional calculi extending intuitionistic or some modal logic, many important properties of calculi appear to be decidable (see a survey in [4]). When the rules of inference are fixed, for any given finite system of additional axioms, one can effectively decide consistency problem for normal modal logics, tabularity and interpolation problems for extensions of the intuitionistic logic or of the modal system S4 and some other problems.

Introduction. Since the originalworks [39, 40] by AbrahamRobinson,many different presentations to the methods of nonstandard analysis have been proposed over the last forty years. The task of combining in a satisfactory manner rigorous theoretical foundations with an easily accessible exposition soon revealed very difficult to be accomplished. The first pioneering work in this direction was W.A.J. Luxemburg's lecture notes [36]. Based on a direct use of the ultrapower construction, those notes were very popular in the “nonstandard” community in the sixties. Also Robinson himself gave a contribution to the sake of simplification, by reformulating his initial typetheoretic approach in a more familiar set-theoretic framework. Precisely, in his joint work with E. Zakon [42], he introduced the superstructure approach, by now the most used foundational framework.

To the authors’ knowledge, the first relevant contribution aimed to make the “hyper-methods” available even at a freshman level, is Keisler's book [33], which is a college textbook for a first course of elementary calculus. There, the principles of nonstandard analysis are presented axiomatically in a nice and elementary form (see the accompanying book [32] for the foundational aspects). Among the more recent works, there are the “gentle” introduction by W.C. Henson [26], R. Goldblatt's lectures on the hyperreals [25], and K.D. Stroyan's textbook [44].

Recently the authors investigated several different frameworks in algebra, topology, and set theory, that turn out to incorporate explicitly or implicitly the “hyper-methods”. These approaches show that nonstandard extensions naturally arise in several quite different contexts of mathematics. An interesting phenomenon is that some of those approaches lead in a straightforward manner to ultrafilter properties that are independent of the axioms of Zermelo-Fraenkel set theory ZFC.

We are pleased to present the proceedings volume of the invited and contributed talks delivered at the Workshop and Conference on Logic, Algebra, and Arithmetic that took place October 18-22, 2003 at the Institute for Studies in Theoretical Physics and Mathematics (IPM) in Tehran, Iran. The meeting provided a unique occasion for the exchange of ideas and methods in various frontiers of research in mathematical logic, and further strengthened the existing bonds of scientific cooperation between Iranian scholars and their colleagues abroad.

The meeting was made possible through the visionary leadership of the director of IPM, Professor M. J. A. Larijani, and the inspiring support of the head of the mathematics division at IPM, Professor G. B. Khosrovshahi. On behalf of all the participants, we also wish to acknowledge the industry and dedication of the staff at IPM, particularly Mr. M. Rahpeyma, Mr. M. Ashtiani, Mrs. N. Ramezani, and Ms. T. Parsa.

The papers that appear herein are in most cases revised and expanded versions of those that were originally presented at the meeting. We are grateful to the authors for their valuable contributions, patience, and cooperation during the refereeing and revision process. Furthermore, we offer a special note of gratitude to the numerous referees who assisted the authors and the editors in improving this volume.

Finally, we would like to extend our appreciation to the ASL for publishing this volume in the LNL series.

Introduction. ClassicalFiniteModelTheory andDescriptiveComplexity Theory [25, 17] give results about the expressiveness and complexity of logics over finite relational structures. This paper surveys work generalizing finite model theory to the situation where there is some infinite interpreted structure M where the finite relations live. We want to talk about logics that can access both the finite structure and the infinite background model; what classes are definable within such a logic, and what can we say about them with respect to computability and complexity? Answering these questions requires a suitable model of definability in the presence of built-in structure, as well as a notion of complexity appropriate when one works in an abstract setting, possibly over noneffective domains. There are several candidate approaches to logics over finite models “with a background structure”, and for each of these there are multiple complexity models one could compare against.

The 2003 European Summer Meeting of the Association for Symbolic Logic was held in Helsinki, Finland, August 14–20, 2003. The meeting was called Logic Colloquium 2003 and it took place in the Main Building of the University of Helsinki. It was attended by 224 participants and 27 accompanying persons from 32 different countries. The organizing body was the Department of Mathematics of the University of Helsinki. Financial support was provided by the the European Commission, Association for Symbolic Logic, the Academy of Finland, the Finnish Cultural Foundation, the Finnish Academy of Science and Letters, the Rolf Nevanlinna-Institute Research Foundation, and Nokia.

The Organizing Committee consisted of Åsa Ekman, Aapo Halko, Alex Hellsten, Taneli Huuskonen, Juliette Kennedy, Juha Kontinen, Kerkko Luosto, Maria Luosto, Hannu Niemistö, Juha Oikkonen, Matti Pauna, Juha Ruokolainen, Jouko Väänänen (Chair), and Meeri Viljanen, all from the University of Helsinki.

The Program Committee consisted of Peter Aczel (Manchester), Zofia Adamowicz (Warsaw), John Baldwin (Chicago), Elizabeth Bouscaren (Paris), Michael Detlefsen (Notre Dame), Moti Gitik (Tel Aviv), Lauri Hella (Tampere), Thomas Jech (Prague), Rohit Parikh (Brooklyn), Helmut Schwichtenberg (Munich), Ted Slaman (Berkeley), Viggo Stoltenberg-Hansen (Chair, Uppsala), and Jouko Väänänen (Helsinki).

The program of the meeting is listed on the following pages. Not all invited speakers submitted a paper to the proceedings. One invited plenary speaker could not attend and her talk was replaced by a plenary talk by Ludomir Newelski. Steve Jackson was not able to give his lecture but provided his paper for the proceedings. The submissions were all refereed and the editors are indebted to the referees for their work.

Introduction.There are three classical approaches to general topology : Fréchet's abstract spaces, Hausdorff's neighborhood classes andKuratowski's closure classes. The fundamental objects with which one works in all these approaches are points. But a point can be viewed as a limit of a sequence of other points or the sole member of an intersection of a nested sequence of open intervals. These approaches to points are often useful.