\documentstyle[12pt]{article}

\oddsidemargin  -2mm
\evensidemargin     4mm
\marginparwidth    0pt
\marginparsep   0pt

\topmargin    8mm
\headheight   0pt
\headsep   0pt
\topskip   0pt


\footheight   0pt
%\footskip   0pt
\textheight   225mm
\textwidth    152mm

\newcommand{\m}{mathematics}

\renewcommand{\baselinestretch}{1.1}


\title{E.L. Post and the development\\ of mathematical logic and recursion
theory }

\begin{document}

\author{Roman Murawski \\
%\thanks{The author was supported by the Committee for
%Scientific Research, grant no. 1 H01A 023 13.} \\
{\small Adam Mickiewicz University}\\
{\small Faculty of Mathematics and Computer Science}\\
{\small ul.  Matejki 48/49}\\
{\small 60--769 Pozna\'n, Poland}\\
{\small E-mail: {\tt rmur@math.amu.edu.pl}}}

\date{}

\maketitle

\begin{abstract}
In the paper the contribution of Emil L. Post (1897--1954) to mathematical
logic and recursion theory will be considered. In particular we shall study: 
(1) the meaning of results of his doctoral dissertation to the development of
the metamathematical studies of propositional calculus, (2) the significance of
his studies on canonical systems for the theory of formal languages as well
as for the foundations of computation theory, (3) his anticipation of G\"odel's
and Church's results on incompleteness and undecidability, (4) his results on
the undecidabiity of various algebraic formal systems and finally (5) his
contribution to establishing and to the development of recursion theory as an
independent domain of the foundations of mathematics. At the end some remarks
on the philosophical and methodological background of his results will be
made. 
\end{abstract}


\section{Post's doctoral dissertation}


Most of scientific papers by Emil Leon Post were devoted to mathematical logic
and to the foundations of \m.\footnote{Post published 14 papers and 19
abstracts 
(one 
of the papers was published after his death): 4 papers and 8 abstracts were
devoted to algebra and analysis and 10 papers and 11 abstracts to mathematical
logic and foundations of \m.}

His first paper in logic was the  doctoral dissertation from 1920 published in
1921 in {\it American Journal of Mathematics} under the title ,,Introduction to
a general theory of elementary propositions'' (cf. \cite{post21}). It was
written under the influence of A.N.~Whitehead's and B.~Russell's {\it Principia
Mathematica} (cf. \cite{white}) on the one hand (Post participated in a seminar
led by Keyser at 
Columbia University devoted to {\it Principia\/}) and {\it A Survey of Symboic
Logic} by C.I.~Lewis (cf. \cite{lewis}). Post's doctoral dissertation contained
the first 
metamathematical results concerning a system of logic. In particular Post
isolated the part of {\it Principia} called today the propositional calculus,
introduced the truth table method and showed that the system of axioms for the
propositional calculus given by Whitehead and Russell is complete, consistent
and decidable (in fact Post spoke about the finiteness problem instead of
decidability). He also proved that this system is complete in the sense called
today after him, i.e., that if one adds to this system an unprovable formula as
a new axiom then the extended system will be inconsistent. It is worth
mentioning here that  the completeness, the consistency and the independence of
the axioms of the propositional calculus of {\it Prinicipia} was proved by Paul
Bernays in 
his {\it Habilitationsschrift} in 1918 but this result has not been published
untill 1926 (cf. \cite{bern26}) and Post did not know it. 

In Post's dissertation one finds also an idea of many-valued logics obtained by
generalizing the 2-valued truth table to $m$-valued truth tables  ($m \geq 2)$.
Post 
proposed also a general method of studying systems of logic (treated as systems
for inferences) by finitary symbol manipulations (later he called such systems
canonical systems of the type $A$) --- hence he considered formal logical
systems as combinatorial systems.

In doctoral dissertation Post mentioned also his studies of systems of 2-valued
truth functions closed under superposition. In particular he showed that every
truth function is definable in terms of negation and disjunction. 

Those latter considerations were developed in the monograph {\it The Two-Valued
Iterative Systems of Mathematical Logic} from 1941 (cf. \cite{post41}). One
finds there among others the result called today Post's Functional Completeness
Theorem. It gives a sufficient and necessary condition for a set of 2-valued
truth functions to be complete, i.e., to have he property that any 2-valued
truth function is definable in terms of it. Post distinguished five properties
of truth functions. His theorem says that a given set $X$ of truth functions is
complete if and only if for every of those five properties  there  exists in
$X$ a truth function which does not have it. Did Post prove this theorem? In
\cite{post41} one finds no proof satisfying the standards accepted
today. The reason for that was Post's baroque notation (it was in fact an
unprecise adaptation of the imprecise notation of Jevons from his {\it Pure
Logic}, cf. \cite{jev64}), other reason was the fact that Post seemed to
be  simultaneously pursuing several different topics. The proof of Post's 
theorem 
satisfying today's standards can be found in the paper by Pelletier and Martin
\cite{pel90}. 


\section{Canonical systems}

During a year stay at Princeton University 1920--21 (he was awarded the
post-doctoral Procter Fellowship) Post studied mainly canonical systems. Those
systems founded the theory of formal languages. Post's results in this field
were 
the anticipation  of famous results by G\"odel and Church on the incompleteness
and undecidability of first order logic.

The investigations mentioned above were connected with the following ideas: the
whole {\it Principia Mathematica} can be considered as a canonical system of
type $A$, i.e., as a system of signs in an alphabet which can be manipulated
according to a given set of rules. Post wanted to solve the decision problem
(in his terminology: the finiteness problem) for canonical systems of type $A$.
In his way he wanted to find a method which would decide for any given formula
of the system of {\it Principia} whether it is formally provable in it or not.
Since {\it Principia} are a formalization of the whole of \m, this method would
give a decision procedure for the whole of \m.

Besides canonical systems of type $A$ Post introduced  systems of type $B$ and
$C$. Just the latter are known today as Post's production systems. Let us
define them using the contemporary terminology and notation.

Let $\Sigma$ be a finite alphabet. Its elements are called terminals. One uses
also non-terminal symbols $P_{.}$. A canonical production  has the form:
$$
\begin{array}{cccccccc}
g_{11} & P_{i_{1}^{'}} & g_{12} & P_{i_{2}^{'}} & \ldots & g_{1m_{1}} & 
P_{i_{m_{1}}^{'}} & g_{1(m_{1} + 1)} \\
g_{21} & P_{i_{1}^{''}} & g_{22} & P_{i_{2}^{''}} & & \ldots g_{2m_{2}} & 
P_{i_{m_{2}}^{''}} & g_{2(m_{2} + 1)} \\
\ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\
g_{k1} & P_{i_{1}^{(k)}} & g_{k2} & P_{i_{2}^{(k)}} & \ldots & g_{km_{k}} & 
P_{i_{m_{k}}^{(k)}} & g_{k(m_{k} + 1)} \\
& & & & \Downarrow & & &  \\
g_{1} & P_{i_{1}} & g_{2} & P_{i_{2}} & \ldots &  g_{m} &
P_{i_{m}} & g_{m + 1} 
\end{array}
$$
where $g_{k}$ are strings on the alphabet $\Sigma$, $P_{k}$ are variable
strings (non-terminals) and each of the $P$'s in the line following the
$\Downarrow$ also occurs as one of the $P$'s above $\Downarrow$. A system in
canonical form of type $C$ consists of a finite set of strings (Post called
them initial assertions) together with a finite set of canonical productions.
It generates of course a subset of $\Sigma^{\ast}$ (= the set of all finite
strings over $\Sigma$) which can be obtained from the initial assertions  by
the iterations of canonical productions. Today it is known that such sets are
exactly recursively enumerable languages. 


Post proved the equivalence of canonical systems of type $A$, $B$ and $C$. He
also showed that this part of {\it Principia} which corresponds to the
first-order predicate calculus  can be formalized as a canonical system of type
$B$ and consequently also of type $C$. Moreover the set of all provable
formulas of the system of {\it Principia} can be regarded as a set of strings
of 
symbols which can be generated by certain canonical system of type $C$.

Post proved also the important  Normal Form Theorem for canonical systems of
type $C$. Let us say that a canonical system of type $C$  is normal if and only
if it has exactly one initial assertion  and each of its productions has the
form 
$$
gP \Longrightarrow P \overline{g}.
$$
A set of strings $U \subseteq \Sigma^{\ast}$ is said to be normal if and only
if there exists a normal system on an alphabet $\Delta$ containing $\Sigma$ and
generating a set ${\cal N}$ such that $U = {\cal N} \cap \Sigma^{\ast}$. 
Post's Normal Form Theorem says now that if $U \subseteq \Sigma^{\ast}$ is a
set of strings generated by some canonical system of type $C$ then $U$ is
normal (a proof can be found in \cite{post43} and \cite{post65}).

One of the consequences of Normal Form Theorem is that a decision procedure
for canonical systems of type $C$ would induce a decision procedure for the
whole system of {\it Principia}. 

Post started his reasearches in this direction by considering normal systems of
a special 
form,  so-called tag systems. Tag systems are normal systems in which
all $g$'s in production rules are of the same length (but not necessarily the
$\overline{g}$'s) and $\overline{g}$'s depend only on the first symbol of the
appropriate string $g$. In particular Post started by studying  the following
simple system:
$$
agP \Longrightarrow Paa,
$$
$$
bgP \Longrightarrow Pbbab,
$$
where $g \in \{a,b\}^{\ast}$ and $|g| = 2$. This case turned out to be difficult
(the question whether such systems are decidable is open till today).

Post supposed that tag systems are recursively undecidabe. This was proved by
M.~Minsky in 1961 (cf. \cite{min}).


Note that the procedure of generating expressions by a canonical system of
type $C$ is similar to the process of generating computable functions from
certain given initial functions by iterations of certain given operations on
functions.\footnote{It was shown later that the definition of effective
computability by Post's canonical systems is equivalent to the definitions in
the language of $\lambda$-definability, of recursive functions or by Turing
machines.} 
 Hence those systems can be regarded as a formalism making precise
the intuitive notion of effective computability. Consequently one can formulate
a thesis analogous to Church's thesis and called Post's thesis which says that
any finitely given language is generated by rules of some canonical normal
system. 

An application of Cantor's diagonal method led Post to the conclusion that the
decision problem for normal systems has a negative solution. In 1921 Post
sketched a formal proof of this. He wrote in \cite{post65} (pp. 421--422): 
\begin{quote}
We (\ldots) conclude that the finiteness problem for the class of all normal
systems is unsolvable, that is, there is no finite method which would uniformly
enable us to tell of an arbitrary normal system and arbitrary sequence on the
letters thereof whether that sequence is or is not generated by the operations
 of the system from the primitive sequence of the system.
\end{quote}
Those considerations led him also to the conclusion about the incompleteness,
i.e., to the conclusion that:
\begin{quote}
{\it not only was every (finitary) symbolic logic incomplete relative to a
certain 
fixed class of propositions (\ldots) but that every such logic was extendable
relative to that class of propositions}
\end{quote}
(cf. \cite{post43}). In \cite{post43} he also wrote:
\begin{quote}
{\it No normal-deductive-system is equivalent to the complete logical system (if
such there be); better, given any normal-deductive-system there exists another
which second proves more theorems (to put it roughly) than the first}
\end{quote}
and he added
\begin{quote}
{\it A complete symbolic logic is impossible}.
\end{quote}

Those results anticipated results by G\"odel and Church on the incompleteness
and undecidability of systems of first-order logic (cf. \cite{god31}, 
\cite{church1} and \cite{church2}). Post knew of course that 
his results are, as he wrote, ``fragmentary''. He never published them (though
in 1941, hence already after the publication of G\"odel's and Church's results)
he tried to publish results of his investigations from 1920--1921). 


What was his reaction to the appearance  of the G\"odel's paper
\cite{god31}? On the one hand he was disappointed that not his name will be
connected with results he anticipated and on the other he admired the genius
and contribution of G\"odel. In a postcard to G\"odel sent on 19th October 1938
 Post wrote:
\begin{quote}
I am afraid that I took advantage of you on this, I hope but our first meeting.
But for fifteen years I had  carried around the thought of astounding the
mathematical world with my unorthodox ideas, and meeting the man chiefly
responsible for the vanishing of that dream rather carried me away.

\vspace{0.5em}

Since you seemed interested in my way of arriving at these new developments
perhaps Church can show you a long letter I wrote to him about them. As for any
claims I might make perhaps the best I can say is that I would have {\it
proved} G\"odel's Theorem in 1921 --- had I been G\"odel.
\end{quote}

And in the letter to G\"odel from 30th October 1938 he wrote:
\begin{quote}
\ldots after all it is not ideas but the execution of ideas that constitute a
mark of greatness.
\end{quote}


Considering decidability problem one should mention Post's contribution to
making precise the notion of effective computability. Post was of the opinion
that Herbrand-G\"odel's and Church-Kleene's definitions were both lacking in
that neither constituted a ``fundamental'' analysis of the notion of algorithmic
process. In 1936 (cf. \cite{post36}) he proposed a definition based on the
operations of marking an empty box and erasing the mark in  a marked box. Note
the similarity with the definition given at the same time by A.~Turing (cf.
\cite{tur36}).  The difference between both approaches consists is that Turing
formulated his definition in terms of an idealized computer while Post in terms
of a program (a list of instructions written in a given language).

At the beginning of the 40's Post wrote a paper in which he tried to describe
his studies on the incompleteness and undecidability from 1920--1921
anticipating G\"odel's and Church's results. It is the paper ``Absolutely
unsolvable problems and relatively undecidable propositons --- account of an
anticipation''. It was submitted in 1941 to {\it American Journal of
Mathematics}. In a letter to H.~Weyl accompanying the manuscript Post explained
why he did not publish his results twenty years earlier and wants to do it now,
i.e., after the publications by G\"odel and Church. Among reasons he mentions
problems he had with publishing his earlier papers (in particular of
\cite{post21} and \cite{post41}) which did not find a recognition and
appreciation by mathematicians as well as the problems with the health which
delayed the preparation of full detailed proofs.
 Though the editors appreciated the significance of Post's
investigations and results, the paper has been rejected. Communicating this
decision H.~Weyl wrote in a letter to Post from 2nd March 1942:
\begin{quote}
\ldots I have little doubt that twenty years ago your work, partly because of
its then revolutionary character, did not find its due recognition. However,
we cannot turn the clock back; in the meantime G\"odel, Church and others have
done what they have done, and the American Journal is no place for historical
accounts; \ldots (Personally, you may be comforted by the certainty that most
of the leading logicians, at least in this country, know in a general way of
your anticipation.)
\end{quote}

Only a small part of Post's paper has been published, i.e., the part containg
his Normal Form Theorem (cf. \cite{post43}). The full version of the paper
``Absolutely unsolvable problems and relatively
undecidable 
propositions --- account of an anticipation'' was published posthumously in
1965 in Davis' book {\it 
The Undecidable}.


\section{Recursion theory}

Main Post's results which found the recognition and appreciation  belong to 
the 
recursion theory. They were of course connected with his investigations
described above.

Considering Post's results in the recursion theory one must tell first of all
about 
his paper ``Recursively enumerable sets of positive integers and their
decision problems'' (cf. \cite{post44}). It turned out to be  the most
influential of his publications and foundamental for
the whole recursion theory.
Recursion theory was for the first time presented in it as an autonomous branch
of mathematics. 

One finds there:
\begin{itemize}
\item   a theorem called today Post's Theorem and stating that a set $X$ is
recursive if and only if the set $X$ and its complement $\neg X$ are
recursively enumerable,\footnote{Recall that a set $X$ is recursively
enumerable if 
and only if there exists a recursive function $f$ such that $X$ is the image of
$f$ if and only if there exists a recursive relation $R$ such that 
$
x \in X \equiv \exists y R(x,y).
$}
\item  a theorem stating that (a) any infinite recursively enumerable set
has an infinite recursive subset and (b) there exists a recursively enumerable
set 
which is not recursive.
\end{itemize}

Main subject of the considered paper is the mutual reducibility of 
recursively enumerable sets. Recall that a set $X$ is said to be many-one
reducible to a 
set $Y$ if and only if there exists a recursive function $f$ such that
$$
x \in X \equiv f(x) \in Y.
$$
If the function $f$ is one-one then we say about one-one reducibility.

Post proved the existence of a recursively enumerable set $K$ which is complete
with respect to many-one (one-one) reducibility, i.e., such that any
recursively enumerable set $X$ is many-one (one-one) reducible to $K$. Hence
$K$ has a maximal  degree of unsolvability with respect to many-one (one-one)
reducibility. Post constructed also a recursively enumerable set which is
simple, i.e., has the property that there exists no infinite recursively
enumerable  subset of its complement. Such a set cannot be of a maximal degree
with respect to one-one reducibility. This led Post to the formulation of the
following problem called today Post's problem: does there exist a recursively
enumerable but not recursive set of a degree lower than the degree of the
complete set $K$ with respect to a given type of reducibility?

Post did not succeed in solving this problem. Though he proved in 1948 (cf.
\cite{post48}) the existence of sets of a degree lower than the degree of the
set $K$ but those sets were not recursively enumerable.

Post's problem was solved independently by A.A.~Muchnik (cf. \cite{much}) and
R.~Friedberg (cf. \cite{frie}) by a new method 
introduced by them --- and called the priority method. This method proved later
to be really fruitful --- many 
results in the recursion theory, in particular in the theory  of degrees, have
been obtained by it. They showed that there exist two recursively enumerable
sets $A$ and $B$ such that $A$ is not recursive in $B$ and $B$ is not recursive
in $A$.

As a consequence  one obtains that degrees of unsolvability (even the degrees
of recursively enumerable sets) are not lineary ordered and that there are
recursively enumerable degrees other than the degree of recursive sets and the
degree of the complete set (sets $A$ and $B$ constructed by Friednerg and
Muchnik are examples of such sets). 

Discussing here Post's paper ``Recursively enumerable sets of positive integers
and their decision problems'' one should mention the way in which Post
presented his results in it. This way became a norm and a standard in the
recursion theory. It consisted in giving rather informal proofs with a
description of intuitions. Post saw the need of providing formal proofs but on
the other hand he wrote:
\begin{quote}
\ldots the real mathematics involved must lie in the informal development. For
in every instance the informal ``proof'' was first obtained; and once gotten,
tranforming it into the formal proof turned out to be a routine chore.
\end{quote}

The considered paper had important long term effects. It was the beginning of
extensive studies of 
recursively enumerable sets, in particular of various types of reducibility.
Here one can also see the source of such important notion as polynomial time
reducibility or of studies connected with NP--completeness.


Post continued his studies of degrees of unsolvability in the paper ``Degrees
of recursive unsolvability (preliminary report)'' (cf. \cite{post48}) where he
generalized the notion of a degree to the case of any sets (not necessarily
recursively enumerable) and proved the existence of a pair of incomparable
degrees (both were lower than the degree of the complete recursively enumerable
set $K$). He announced also a theorem (called today Post's theorem) stating
that a set $X$ is recursive in a set $A \in \Sigma^{0}_{n}
(\Pi^{0}_{n})$ if and only if $X$ is a $\Delta^{0}_{n+1}$ set.

One should also mention here the joint paper by Post with S.C.~Kleene ``The
upper semi-lattice of degrees of recursive unsolvability'' (cf. \cite{post54}).
One finds there among others a theorem stating that the ordered set of degrees
of unsolvability contains a densely ordered subset.

\section{Undecidability of algebraic combinatorial systems}

Discussing Post's contribution to the recursion theory one should say about his
results on undecidability of algebraic combinatorial  systems. They provided
``mathematical'' examples of undecidable problems.

Let us start with the correspondence problem. It can be formulated as follows.
A correspondence system is a finite set of ordered pairs $(g_{1},h_{1})$,
$(g_{2},h_{2})$, \ldots, $(g_{n},h_{n})$ such that $g_{i}, h_{i} \in
\Sigma^{\ast}$, $\Sigma$ a given finite alphabet. Such a system is said to be
solvable if there exists a sequence $i_{1}, i_{2}, \ldots, i_{k}$ such that $1
\leq i_{1}, i_{2}, \ldots, i_{k} \leq n$ and 
$$
g_{i_{1}}g_{i_{2}} \ldots g_{i_{k}} = h_{i_{1}}h_{i_{2}} \ldots h_{i_{k}}.
$$
The corrspondence problem is to provide an algorithm for determining of a given
correspondence system whether it is solvable or not. Post proved in the paper
``A variant of a recursively unsolvable problem'' (cf. \cite{post46}) that such
an algorithm does not exist, hence the correspondence  problem is not
recursively solvable. This result plays an important role in the theory of
formal languages. 

Church suggested to Post to study also the  decidability problem for Thue's
systems known also as the word problem for monoids or semi-groups. It was
formulated by the Norwegian mathematician Axel Thue in 1914 and can be
formulated as follows: Let $\Sigma$ be a finite alphabet. Define an equivalence
relation $\approx$ in $\Sigma^{\ast}$ by giving a finite set of pairs of words
for which this equivalence holds, i.e., by putting
$$
u_{1} \approx v_{1}, u_{2} \approx v_{2}, \ldots, u_{n} \approx v_{n},
$$
and closing this under the substitution of $v_{i}$ for $u_{i}$ ($i = 1, \ldots,
n)$. The problem consists now in providing an algorithm for determining of an
arbitrary pair $(u,v) \in \Sigma^{\ast} \times \Sigma^{\ast}$ of strings
whether or not $u \approx v$.  In the paper ``Recursive unsolvability of a
problem of Thue'' (cf. \cite{post47}) Post gave an example of a set of initial
pairs defining an equivalence relation $\approx$ for which  the word problem is
unsolvable. In the proof Post used Turing machines (in fact he showed that the
theory of Turing machines can be interpreted in terms of the word problem in
such a way that an algorithm for the latter could be tranformed into an
algorithm for a problem concerning Turing machines known to be unsolvable).
Post 
also gave a very careful technical critique of Turing's paper \cite{tur36}.


It is worth adding that the recursive unsolvability of the word problem was
established independently by A.A.~Markov in 1947 (cf. \cite{mark}) who based
his proof on Post's normal systems.


\section{Post's philosophical and methodological ideas}

Discussing the works and results of Post in the field of mathemtaical logic and
recursion theory one should consider their philosophical and methodological
background. 

Post --- similarly as G\"odel --- emphasized the significance of the
absolutness and the fundamental character of the notion of recursive
solvability. 
He attempted also to explain the notion of provability --- more exactly, he
wanted to find a precise notion which would explain the intuitive notion of
provability in arithmetic in such a way as the notion of recursiveness explains
the notion of effective computability and solvability. He hoped that this will
enable us to find absolutely undecidable arithmetical propositions. Later
(before the death) he added to this also the problem of providing an
absolute 
explication and explanation of the general mathematical notion of definability
(he was convinced that this should be done even before giving the absolute
explication of the notion of provability). 

Post emphasized (cf. \cite{post65}, p. 64): 
\begin{quote}
I study Mathematics as a product of the human mind and not
as absolute.
\end{quote}
 He was convinced that mathematical
thinking 
is in fact creative. He wrote in \cite{post65}, p.~4: 
\begin{quote}
\ldots mathematical
thinking 
is, and must be, essentially creative.
\end{quote}
 He thought also that the human
capacity to know cannot be closed and reduced to a formal system. And added
(cf. \cite{post65}, p. 4):
\begin{quote}
\ldots creativeness of human mathematics has a counterpart inescapable
limitations thereof --- witness the absolutely unsolvable (combinatory)
problems. 
\end{quote}

On the other hand he was convinced that the results on the undecidability and
incompleteness indicate that human capacity to know with respect to mathematics
are in fact bounded in spite of the creativeness of the mathematical thinking.
He wrote in \cite{post65}, p. 56:
\begin{quote}
The unsolvability of the finiteness problem  for all normal systems, and the
essential incompleteness of all symbolic logics, are evidences of limitations
in  man's mathematical powers, creative though these be.
\end{quote}

Post claimed that there exist absolutely undecidable (i.e., unsolvable by no
methods and means) propositions and that there is no complete system of
logic.\footnote{In \cite{post65}, p. 54, he wrote: ``{\it A complete symbolic
logic is 
impossible}''.}  A consequence of this was in his opinion the fact that (cf.
\cite{post65}, p. 55): 
\begin{quote}
logic must not only in some parts of its description (as in the operations),
but in its very operation be informal. Better still, we may write
\begin{center}
{\it The Logical Process is Essentially Creative.}
\end{center}
\end{quote}
Consequently the human mind can never be replaced by a machine. He wrote in
\cite{post65}, p. 55: 
\begin{quote}
We see that a {\it machine} would never give a complete logic; for once the
machine is made {\it we} could prove a theorem it does not prove.
\end{quote}


\section{The significance of Post's results for the development of the
mathematical logic and the 
foundations of mathematics}

The above considerations lead us to the conclusion that Post's works and
results contributed very much to the development of mathematical logic and the
foundations of mathematics. His works (together with works of J.~\L ukasiewicz)
initiated the investigations on many-valued logics and on the Post algebras
connected with them. His studies of the propositional calculus (the results of
which were included in his doctoral dissertation) were the first
metamathematical studies of a system of logic. Most significant were probably
his works and results in the recursion theory. They contributed very much to
establishing this field as an
autonomous branch of the foundations of mathematics. They began intensive
studies  on degrees of unsolvability, in particular of recursively enumerable
degrees, investigations on the (un)decidability of various systems, in
particular combinatorial systems in algebra and on the various types of
recursive reducibility. They influenced also the researches in the computer
science (though Post showed no interest in computers). They were also very
important 
for the theory of formal languages.

Post's investigations and results were in a sense ahead of his time, were
precursory (compare his anticipation of G\"odel's and Church's results
described above). This had of course negative consequences as the fear of being
not understood properly and the delay of publication of the
results. Problems with health, in particular the
illness under which he 
suffered almost the whole life, also hindered him from publishing the results
at proper time. Many of Post's results were left in an incomplete form.  He
tried the whole time to improve his results and to find the most general form
which also caused some delay. Nevertheless his contributio to the mathemtaical
logic and to the foundations of mathematics was really significant.


\thebibliography{99}

\bibitem{bern26} Bernays P., Axiomatische Untersuchungen des Aussagenkalk\"uls
der {\it Principia Mathematica}, {\it Mathematische Zeitschrift} 25 (1926),
305--320. 


\bibitem{church1} Church A., An unsolvable problem of elementary number theory,
{\it American Journal 
of Mathematics} 58 (1936), 345--363. 

\bibitem{church2} Church A., A note on the Entscheidungsproblem, {\it Journal
of Symbolic Logic} 1 
(1936), 40--41. Correction, {\it ibid,}, 101--102. 
 

\bibitem{zebr} Davis M. (Ed.), {\it Solvability, Provability, Definability: The
Collected Works of Emil L.~Post}, Birkh\"auser, Boston-Basel-Berlin 1994.

\bibitem{frie} Friedberg R., Two recursively enumerable sets of incomparable
degress of 
unsolvability (solution of Post's problem), {\it Proceedings of the National
Academy 
of Sciences (USA)} 43 (1957), 236--238.  

\bibitem{god31} G\"odel K., \"Uber formal unentscheidbare S\"atze der {\it
Principia 
Mathematica} und verwandter Systeme. I, {\it Monatshefte f\"ur Mathematik und
Physik }
38 (1931), 173--198. 


\bibitem{jev64} Jevons W.S., {\it Pure Logic, or the Logic of Quality apart
from Quantity with remarks on Boole's System and the Relation of Logic and
Mathematics}, E.~Stanford, London-New York 1864. 

\bibitem{post54} Kleene S.C. and Post E.L.,  The upper semi-lattice  of degrees
of  recursive 
unsolvability, {\it Annals of Mathematics} 59 (1954), 379--407; reprinted in
\cite{zebr}, pp. 514--542. 

\bibitem{lewis} Lewis C.I., {\it A Survey of Symbolic Logic}, University of
California Press, Berkeley 1918. 

\bibitem{mark} Markov A.A.,  Nievazmoznost' niekatorych algoritmov v teorii
asotiativnych sistem (On the impossibility of certain algorithms in the
theory of 
associative systems), {\it Doklady Akademii Nauk SSSR} 55 (1947), 587--590;
English 
translation in: {\it Comptes rendus de l'academie des Sciences de l'URSS} 55
(1947), 583--586. 

\bibitem{min} Minsky M., Recursive unsolvability of Post's problem  of tag and
other topics 
in the theory of Turing machines, {\it Annals of Mathematics} 74 (1961),
437--455.  

\bibitem{much} Muchnik A..A., Nerazreshimost' problemy svodimosti algoritmov
(Negative answer 
to the problem of  reducibility of the theory of algorithms), {\it Doklady
Akademii Nauk SSSR} 108 (1956), 194--197. 

\bibitem{pel90} Pelletier F.J., Martin N.M, Post's functional completeness
theorem, {\it Notre Dame Journal of Formal Logic} 31 (1990), 462--475.

\bibitem{post21} Post E.L., Introduction to a general theory of elementary
propositions, {\it American Mathematical Journal} 43 (1921), 163--185;
reprinted in J.~van Heijenoort, {\it From Frege to G\"odel. A Source Book in
Mathematical Logic 1879--1931}, Harvard University Press, Cambridge, Mass.,
1967, pp. 264--283, ; also in \cite{zebr}, pp. 21--43.


\bibitem{post36} Post E.L.,  Finite combinatory processes --- Formulation I,
{\it Journal of Symbolic
Logic} 1 (1936), 103--105; reprinted in \cite{zebr}, pp. 103--105.  

\bibitem{post41}  Post E.L., {\it The Two-Valued Iterative Systems of
Mathematical 
Logic}, Princeton University Press, Princeton 1941; reprinted in \cite{zebr},
pp. 249--374.  


\bibitem{post43} Post E.L., Formal reductions of the general combinatorial
decision problem, 
{\it American Journal of Mathematics} 65 (1943), 197--215; reprinted in
\cite{zebr}, pp. 442--460. 

\bibitem{post44}  Post E.L., Recursively enumerable sets of positive integers
and their decision 
problems, {\it Bulletin of the American Mathematical Society} 50 (1944),
284--316; 
reprinted in \cite{zebr}, pp. 461--494.  


\bibitem{post46} Post E.L.,  A variant of a recursively  unsolvable problem,
{\it Bulletin of the 
American Mathematical Society} 52 (1946), 264--268; reprinted in \cite{zebr},
pp. 495--500. 

\bibitem{post47}  Post E.L., Recursive unsolvability of a problem of Thue,
{\it Journal of Symbolic 
Logic} 12 (1947), 1--11; reprinted in \cite{zebr}, pp. 503--513.  

\bibitem{post48} Post E.L.,  Degrees of recursive unsolvability (preliminary
report), {\it Bulletin of 
the American Mathematical Society} 54 (1948), 641--642; reprinted in
\cite{zebr}, pp. 549--550. 


\bibitem{post65} Post E.L., Absolutely unsolvable problems and relatively
undecidable 
propositions --- account of an anticipation, first published in Davis M. (Ed.),
{\it The Undecidable},  Raven Press, New York 1965, pp. 340--433; reprinted in
\cite{zebr}, pp. 375--441.

\bibitem{tur36} Turing A., On computable numbers with an application to the
Entscheidungsproblem, {\it Proceedings of London Mathematical Society}, ser. 2,
42 
(1936--37), 230--265. Correction, {\it ibid.}, 43 (1937), 544--546. 

\bibitem{white} Whitehead A.N. and Russell B., {\it Principia Mathematica},
Cambridge University 
Press, Cambridge, vol. I 1910, vol. II 1912, vol. III 1913.  


\end{document}