MODERN LOGIC: FROM FREGE TO GÖDEL: POST

Besides provoking reactions in the form of rival philosophies of mathematics, the work of Whitehead and Russell stimulated new technical developments. For example, although Whitehead and Russell made free use, in Principia Mathematica, of the notions of truth-value and truth-function, they failed to incorporate these notions into a systematic technique for evaluating formulas of the propositional calculus. Such a technique, the method of truth tables, was presented by Emil Post (1897–1954) in his dissertation of 1920, published as "Introduction to a General Theory of Elementary Propositions" in the American Journal of Mathematics (43: 163–185) in 1921, the year in which Wittgenstein independently presented the same method in his Tractatus Logico-Philosophicus. The method dates back, in fact, to Peirce, but Post considered truth tables in their application not only to classical logic but also to systems in which any number of values are allowed, the primitive connectives of Principia Mathematica, "∼" and "∨," having in these systems the generalized analogues "∼_m " and "∨_m ," where ∼_m P takes the values t ₂, t ₃, · · ·, t _m , t ₁ as P takes the values t ₁, t ₂, · · ·, t _m , and P ∨_m Q takes that of the two values assigned to P and Q which bears the lesser subscript. Classical two-valued logic is accordingly a particular case of the many-valued logics so constructed. Post provided definitions of consistency and completeness, and for the first time a formulation of the propositional calculus was proved to have these properties, the method of truth tables providing a basis for the proofs.

In his 1920 dissertation Post showed how both truth tables for classical logic and associated postulate sets may be generalized. These postulate sets were treated as uninterpreted formal systems, an approach which Post maintained and extended in the direction of even greater generality in later works, where the derivation of theorems from axioms is represented as the production of strings—that is, finite sequences of symbols—from certain other strings of specified form. Most mathematical theories can be transcribed into the canonical forms admitted by Post, and he was able to show that the rules of any theory so expressed can be reduced to productions of a particularly simple type, a reduction that greatly simplifies investigations into the syntax of formal systems.

This approach leads directly to a formulation of recursive enumerability (a set is recursively enumerable if its members can be generated as the values of an effectively calculable function) and thence to one of recursiveness (a set is recursive if both it and its complement are recursively enumerable); Post provided illuminating proofs of results concerning decidability and related topics and introduced and developed a number of important concepts in this field. In 1947 he showed the recursive unsolvability of the word problem for semigroups. That is, he proved that it is impossible to determine whether or not two arbitrarily given strings are equivalent (where A and B are equivalent if B can be obtained from A by starting with A and applying a finite sequence of specified operations prescribing the production of one string from another). This result, published independently and in the same year by A. A. Markov, is an interesting example of the resolution, by techniques of mathematical logic, of an outstanding problem in the field of mathematics proper.

See also Russell, Bertrand Arthur William; Whitehead, Alfred North; Wittgenstein, Ludwig Josef Johann.

Bede Rundle (1967)