MOSTOWSKI, ANDRZEJ

(b. Lvov, Poland, 1 November 1913; d. Vancouver, Canada, 22 August 1975)

set theory, mathematical logic.

Mostowski belonged to the first generation of mathematical logicians who investigated foundational questions from a purely mathematical (rather than a philosophical) view point and who also transformed axiomatic set theory into a branch of logic. For three decades after World War II he was the leader of mathematical logic in Poland. A man of considerable talent, energy, and charm, he was known for his personal and scientific generosity, Philosophically, he was a realist concerning the real numbers and, after Cohen’s 1963 independence results, a formalist concerning set theory.

His father, Stanislaw Mostowski, an assistant in the department of physical chemistry at the University of Lvov, joined the army in 1914 and died a year after his son was born. Mostowski’s mother, Zofia Mostowska, whose maiden name was Kramstyk, worked in a bank. During the winter of 1914 the family went to Zakopane for a vacation; World War I forced them to stay until 1920, when they moved to Warsaw. There, from 1923 to 1931, Mostowski attended the Stefan Batory Gymnasium. A good student, he was interested in both mathematics and physics. When he was sixteen, he fell seriously ill, and this later kept him from serving in the army.

In 1931 Mostowski entered the University of Warsaw, where he was attracted to logic, set theory, and the foundations of mathematics. His teachers in these subjects were eminent researchers—Kuratowski, Leśniewski, Lukasiewicz, Sierpiński, and the two who influenced him most: Lindenbaum and, above all, Tarski.

After Mostowski received a master’s degree in 1936 and wrote his doctoral dissertation, he went abroad to study. During the summer semester of 1937, at the University of Vienna, he attended Gödel’s course on constructible sets, where the relative consistency of the axiom of choice was first established. In Zurich, convinced that he needed a practical skill in order to find a job in Poland (where positions in mathematics were scarce), Mostowski studied statistics in order to become an actuary. Bored with that subject, he enjoyed lectures by Polya and by Hermann Weyl as well as a seminar by Bernays. He did research on recursion theory and on the axiom of choice.

In 1938 Mostowski returned to Warsaw, where, in February 1939, he defended his doctoral dissertation, showing that various definitions of finiteness are not provably equivalent in logic without the axiom of choice. Tarski, who was then a Privatdozent, directed the dissertation, but the official supervisor was Kuratowski. Unable to find a position at the University of Warsaw, Mostowski worked at the National Meteorological Institute.

A year after the Nazis invaded Poland in September 1939, Mostowski became an accountant in a small plant that manufactured roofing and remained there until 1944. From 1942 to 1944 he also taught analytic geometry and Galois theory at the Underground University of Warsaw. One of the students there was Maria Matuszewska, whom he married in September 1944; they had a daughter and two sons, one of whom became a mathematician, Sierpiński, a colleague at the Underground University, remarked in 1945 that Mostowski was very close to being habilitated there in July 1944. Then came the Warsaw uprising of August 1944, when the Nazis devastated the city. Afterward, as he was about to be sent to a concentration camp, some Polish nurses helped Mostowski to escape, spiriting him through the German lines to a hospital.

Many of Mostowski’s wartime results—on the hierarchy of projective sets, on arithmetically definable sets of natural numbers, and on consequences of the axiom of constructibility in descriptive set theory—were lost when his apartment was destroyed during the uprising. He had to choose whether to flee with a thick notebook containing those results or with bread. He chose bread.

Later Mostowski was able to reconstruct just a fraction of his discoveries, such as the decidability of the theory of well-ordering (a result obtained in 1941 but only announced, jointly with Tarski, in 1949 and only published in 1978).

In January 1945 the unemployed Mostowski tried to make a living by giving private lessons, then had to pawn his few possessions. For a few months shortly after the war he held a position as a research fellow at the Silesian Polytechnic (temporarily housed in Cracow). Then he taught briefly at the Jagellonian University in Cracow, where his Habilitationsschrift was approved in 1945. From January to September 1946 he was an acting professor at Lodz University.

Nevertheless, Mostowski’s career was to be in Warsaw. In 1946 he returned to the University of Warsaw as an acting professor, becoming an extraordinary professor the following year and ordinary (full) professor in 1951. He occupied the chair of philosophy of mathematics, then the chair of algebra, and finally the chair of foundations of mathematics. In 1952 he served as dean of the Faculty of Mathematics and Physics. From 1948 to 1968 he was also head of the division of the foundations of mathematics at the National Institute of mathematics (which became the Mathematics Institute of the Polish Academy of Sciences). From 1968 until his death he headed the section on the foundations of mathematics at the University of Warsaw.

When he returned to Warsaw in 1946, Mostowski was the only logician there left from the vigorous group that before the war had included Leśniewski, Lukasiewicz, and Tarski. Although Mostowski had little previous experience as an organizer and disliked administrative duties, he threw himself into rebuilding Warsaw as a major center for mathematical logic. In this effort he was quite successful. He also considered it important to strengthen algebra as an adjunct to logic. In this spirit he wrote for a Polish audience a number of textbooks in algebra, logic, and set theory. As early as 1946 he attracted excellent graduate students, the first of whom (Andrzej Grzegorczyk and Helena Rasiowa) received doctorates in 1950. Among his students were also Henry Hiz, Antoni Janiczak, and Andrzej Ehrenfeucht. After 1965 the number of his students increased and he conducted a large seminar on the foundations of mathematics.

A variety of honors came to Mostowski, beginning with a Polish state prize in 1952 (and another in 1966). In 1956 he was elected an associate member of the Polish Academy of Sciences and became a full member seven years later. In 1972 he received a Jurzykowski Foundation prize and also became president of the division of logic, methodology, and philosophy of science of the International Union for the History and Philosophy of Science. Internationally he was highly respected by his fellow logicians.

Mostowski did much editorial work, serving on the editorial boards of Fundamenta Mathematicae and Journal of Symbolic Logic, as well as Annals of Mathematical Logic, which he helped to found. Moreover, he coedited the series for mathematics, physics, and astronomy of the Bulletin of the Polish Academy of Sciences. Beginning in 1966, he also served as an editor of the series “Studies in Logic and the Foundations of Mathematics” published by North-Holland.

Mostowski traveled abroad repeatedly, spending the academic years 1948–1949 at the Institute for Advanced Study in Princeton, 1958–1959 at the University of California at Berkeley, and 1969–1970 at All Souls College, Oxford. In addition, he participated in many congresses and conferences in Europe and America. After spending the summer of 1975 at Berkeley and Stanford, he was on his way to a conference in Ontario when he stopped at Simon Fraser University in Vancouver to deliver a lecture. There he died suddenly.

Mostowski’s earliest publications prior to World War II, on Boolean algebras and on Fraenkel-Mostowski (FM) models for set theory, illustrate two major themes of his work: algebra applied to logic, and the semantics of set theory. His early research on recursion theory and undecidability, a third theme, did not appear in print until after the war.

His work on FM models was stimulated in 1935 when Lindenbaum posed the problem of how to formulate Fraenkel’s independence results on the axiom of choice in a logically unobjectionable way. Lindenbaum and Mostowski did so, developing the theory of FM models and carefully distinguishing the object language and the metalanguage in the manner of Tarski. In 1939 Mostowski published a rigorous proof that the axiom of choice cannot be deduced from the ordering principle; Fraenkel’s earlier argument had not been adequate. He went beyond Fraenkel by showing that Tarski’s five notions of finiteness were nonequivalent, both in the theory of types and in Bernays-Gödel set theory with urelements. In 1948 Mostowski proved that the principle of dependent choices does not imply the axiom of choice. This result used an uncountable set of urelements, while all earlier independence results relied on a countable set. Mostowski’s Habilitationsschrift (1945) established necessary and sufficient conditions for the axiom of choice restricted to families of m-element sets to imply the axiom for n -element sets. His isomorphism theorem (1949) on transitive models was fundamental to later research on models of set theory. Finally, during the 1970’s he worked on Kelley-Morse set theory and its models.

During World War II, Mostowski began investigating recursion theory and undecidability. He developed the analytical hierarchy of sets of integers, as Kleene did independently. In 1939 Mostowski, working with Tarski, reduced Gödel’s incompleteness theorems to a form that depended only on finitely many first-order arithmetic axioms, thus enabling many theories to be proved undecidable. They prepared their results for publication a decade later with R. M. Robinson. At that time Mostowski also developed an algebraic method for proving nondeducibility results in intuitionistic logic. In 1959 he introduced β-models for second-order arithmetic (models that make well-orderings absolute). He showed that some ω-models are not β-models and was one of those to establish the existence of a minimal β-model.

Much of Mostowski’s postwar work in logic concerned extensions of first-order logic. Thus, in a 1957 paper he introduced the notion of generalized quantifiers and, in particular, quantifiers such as “there exist uncountably many.” He showed that many logics with generalized quantifiers do not have a recursively enumerable set of valid sentences and posed the completeness problem for the remaining such logics: Does there exist a recursively enumerable set of axioms and rules of inference such that a sentence is provable if and only if it is valid? In the same paper he also established that in any logic with a generalized quantifier not definable from “for all” and “there exists,” the Löwenheim-Skolem-Tarski theorem fails; this result helped lead to Lindstrom’s characterization of first-order logic in terms of the Löwenheim-Skolem theorem and the compactness theorem. With Grzegorczyk and Ryll-Nardzewski, Mostowski extended Gödel’s incompleteness results to second-order arithmetic supplemented by the ω-rule. In 1961, solving a problem of Tarski’s, he showed that hte theory of real numbers cannot be axiomatized in weak second-order logic. Finally, in 1962 he proved that the completeness problem has a positive solution for some very general kinds of many-valued first-order logic.

Several of Mostowski’s papers from the 1950’s involve model theory. In 1952 he studied the conditions under which the truth of a sentence is preserved by a finite direct product of models, thereby stimulating more general work by Vaught and by Feferman. Three years later he exhibited a first-order theory (a form of set theory) with no recursively enumerable models. But Mostowski’s most important model-theoretic research, done jointly with Ehrenfeucht (1956), introduced the notion of indiscernible elements and of models generated by such elements, giving conditions under which a theory has a model with many such elements. These ideas proved very fruitful in model theory and set theory.

BIBLIOGRAPHY

I. Original Works. A bibliography of Mostowski’s works is in Foundational Studies: Selected Works, Kazimierz Kuratowski et al., eds., 2 vols. (Amsterdam, 1979), containing about half of his published and unpublished works (translated into English when originally in another language, since Mostowski published in English, French, German, and Polish). His monograph Thirty Years of Foundational Studies (New York, 1966) remains the best historical introduction to logic during the seminal years 1930 to 1964.

II. Secondary Literature. The best biography is Stanislaw Krajewski and Marian Srebrny, in Wiadomości matematyczne, 22 (1979), 53–64. Foundational Studies contains a short biography by Wiktor Marek as well as essays on Mostowski’s contributions to recursion theory (by Andrzej Grzegorczyk), model theory (by Leszek Pacholski), logical calculi (by Cecylia Rauszer), second-order arithmetic (by Pawel Zbierski), and set theory (by Wojciech Guzicki and Wiktor Marek). A biography by Helena Rasiowa appears in Robin O. Gandy and J M. E. Hyland, eds., Logic Colloquium 76 (Amsterdam, 1977), 139–144. See also Wiktor Marek et al., eds., Set Theory and Hierarchy Theory: A Memorial Tribute to Andrzek Mostowski, Springer Lecture Notes, no. 537 (Berlin, 1976), for a brief biography, bibliography, and an unpublished paper. Fragmentary autobiographical reminiscences are in John N. Crossely, ed., Algebra and Logic. Springer Lecture Notes, no. 450 (Berlin, 1975), 7–47.

Gregory H. Moore