Ebook: Andrzej Mostowski and Foundational Studies

This year 2013 marks the centenary of Professor Andrzej Mostowski (1913–1975), one of the leading logicians of the 20th century. A student and collaborator of both Kurt Gödel and Alfred Tarski, Mostowski contributed significantly to all areas of Foundations of Mathematics, with the most spectacular achievements in Set Theory, Model Theory, Abstract Model Theory, Recursion Theory, and investigations of the Incompleteness phenomena in Mathematics.

Professor Mostowski built a significant center of foundational investigations in Warsaw, Poland, after WWII. In the realities of an ideologically divided European continent, he was able to create a unique enclave where the logicians of the East and the West met, communicated, and collaborated towards the common goal of furthering foundational research.

The passage of time did not bury his work; a number of techniques taught in the courses of Logic, Set Theory and, more generally, Foundations of Mathematics carry his name, recognizing his contributions. These include: the Fraenkel-Mostowski permutation models technique for independence proofs in Set Theory, the Mostowski Contraction Lemma, the Ehrenfeucht-Mostowski models with indiscernibles, Mostowski's generalized quantifiers, the Kleene-Mostowski descriptive hierarchy of sets, and many other, more specialized results.

The centenaries of Kurt Gödel, Alfred Tarski and Alan Turing were celebrated during the past decade. To commemorate and honor the centenary of Andrzej Mostowski, and reflect on his contributions and on the past and future of Foundations of Mathematics, logicians of many countries will meet in Warsaw, Poland, in October 2013. Here we would like to express our sincere thanks to all those individuals and organizations involved in organizing, cosponsoring, or contributing to this meeting.

The editors of the present volume, as well as the publisher, all directly owing their education and first steps in foundational research to Professor Mostowski, hope that this first reprint of the volume forms a well-deserved tribute commemorating his manifold contributions to Logic and Foundations and will engage researchers and students in a consideration about the current state-of-the-art and the importance of problems and directions pioneered by Mostowski. The work in Mostowski's tradition continues. We hope that this volume will remind the reader of the person and work of a great mathematician of the 20th century.

A. Ehrenfeucht, E.H. Fredriksson, V.W. Marek and M. Srebrny

June 2013

This paper is a survey of the interaction between the three-valued propositional calculus of Łukasiewicz-Post and the axiomatic versions of quadratic form theory over (semi-real) rings known as abstract real spectra and real semigroups.

We consider the problem stated by Andrzej Grzegorczyk in “Undecidability without arithmetization” (Studia Logica 79 (2005)) whether certain weak theory of concatenation is essentially undecidable. We give a positive answer for this problem.

We consider the problem of 0-1 law for logics with additional quantifiers which do not meet the Mostowski definition of generalized quantifier.

“The problem of understanding of intelligence is said to be

the greatest problem in science today and “the” problem for

this century – as deciphering the genetic code was for the

second half of the latest one.

Arguably, the problem of learning represents a gateway to

understanding intelligence in brains and machines, to

discovering how the human brain works and to making

intelligent machines that learn from experience and improve

their competence…"

THE MATHEMATICS OF LEARNING:

DEALING WITH DATA

T. Poggio, S. Smale, Notices AMS, Vol. 50, May 2003 [185]

The Rasiowa–Pawlak school was established during the second half of the twentieth century. The school concentrates on studies in logics, foundations of computer science and artificial intelligence (AI). Its formation has been greatly influenced by the logician Andrzej Mostowski, a professor at Warsaw University [110,111], who, in particular, directed the doctoral dissertation of Helena Rasiowa. Nowadays, the disciples of the Rasiowa–Pawlak school are active in many research-development centres worldwide. The school founded its own journal, Fundamenta Informaticae. In this paper, we present selected trends in the studies of the school concerning applications of logic in AI. At the beginning, we briefly describe the genesis of the Rasiowa–Pawlak school. We then present the understanding, currently dominating within the school, on such basic concepts as AI and logic. Since the beginning of the 1950's, the focus of the research by Helena Rasiowa and her associates has been the application of algebraic and topological methods to the investigation of crucial problems of logic from an AI perspective. Amongst them are the completeness theorem, construction of deduction systems, construction of models, especially models for constructive mathematics [136,241,67] and related logics such as intuitionistic, intermediate, modal, and approximation logics. In the paper, we discuss the fundamental, in our opinion, ideas underlying these roots of the Rasiowa–Pawlak school. A great importance in the studies of the school is assigned to the search for optimal tools for reasoning about complex vague concepts, construction of knowledge representation systems, reasoning about knowledge as well as for the application of logics in learning, communication, perception, planning, action, cooperation, and competition.

 It should be noted that as is the case with many other research centers, the Rasiowa– school studies pertaining to the application of logics in AI have also undergone an evolution which we present in this paper. We include extensive references to the literature on the approach presented in this paper.

We investigate complete Boolean algebras that carry a continuous submeasure.

The standard definition of lim _z→∞F(z)=∞ is an ∀∃∀ sentence. Mostowski showed that in the standard model of arithmetic, these quantifiers cannot be eliminated. But Abraham Robinson showed that in the nonstandard setting, this limit property for a standard function F is equivalent to the one quantifier statement that F(z) is infinite for all infinite z. In general, the number of quantifier blocks needed to define the limit depends on the underlying structure [Mscr ] in which one is working. Given a structure [Mscr ] with an ordering, we add a new function symbol F to the vocabulary of [Mscr ] and ask for the minimum number of quantifier blocks needed to define the class of structures ([Mscr ],F) in which lim _z→∞F(z)=∞ holds.

We show that the limit cannot be defined with fewer than three quantifier blocks when the underlying structure [Mscr ] is either countable, special, or an o-minimal expansion of the real ordered field. But there are structures [Mscr ] which are so powerful that the limit property for arbitrary functions can be defined in both two-quantifier forms.

I review Ratajczyk's version of model theoretic approach to proof theory for arithmetic. I develop the idea of the Hardy hierarchy and its application to construction of initial segments satisfying PA. As a sample of applications of these ideas I give a version of the Paris–Harrington theorem and a sketch of independence of Goodstein theorem.

We trace our encounters with Prof. A. Mostowski, in person and in his papers. It turns out that he and his papers left a continuous mark on my own work, from its very beginning, and till today.

Pseudorecursive varieties [16] strongly express a lack of recursive uniformity related to equational logic. This article suggests an abstraction of the notion and its integration with algebraic and computational studies—steps that may support or at least explicate Tarski's claim that the nonrecursive pseudorecursive equational theories are nonetheless decidable.