# Mostowski [38] and the Analogies

Mostowski’s starts with the classical notions of Descriptive Set Theory. Briefly, in modern notation and (for simplicity) only for N:

• (1) A a-algebra is any collection F c P (N) which is closed under complements and countable unions;
• (2) the class B of Borel sets is the smallest a-algebra which contains all the open sets;
• (3) a relation P c Nm is E1 if P = {a : (3ft)F(а,в)} with F closed;
• (4) P is E j+1 if P = {a : (3fi)-Q(а,в)} with Q in E j;
• (5) П1 = {Nm P : P e E j} and A j = E j П П(.

The projective classes E j, П A j were introduced by Luzin and Sierpinski in 1925 and they fall into a hierarchy that looks exactly like the arithmetical hierarchy in Fig.5T with boldface letters and superscript 1. But the most fundamental result about them is older and concerns only the first level of this hierarchy:

Theorem 5.1.1 (Suslin [52]) A set A c N is A j if and only if it is Borel.

This was rightfully viewed as a “construction principle” which reduces a complementary pair of quantifications over the complex set N to a countable iteration of taking countable unions and complements, starting with the simple neighborhoods of N. Mostowski had not read Kleene [15] but he knew Post [42] and saw a similarity between Suslin’s Theorem and Post’s in the form

which similarly reduces A definitions to “computations”. He postulated the natural “analogies”

and using these as motivation he defined the arithmetical hierarchy and established for it basically all the results in Kleene [15], so that the analogies extend to all the levels of the two hierarchies. He knew that these are not perfect: not every injective, recursive image of N is recursive, while by a basic, classical result, every injective, continuous image of N is Borel. This, however, might be just a technical wrinkle, as every increasing, recursive image of N is recursive. Later, after writing this paper, he thought of another fundamental property of Y J sets which could test the analogy, the following generalization of Suslin’s Theorem due to Lusin:

Theorem 5.1.2 (Y J Separation) For any two disjoint Y J sets A, B c N, there is a Borel set C which separates them, i.e.,

So is it true that any two disjoint r.e. sets can be separated by a recursive set? At some time between 1947 and 1950 he mentioned the problem to Kleene who (it turned out) had already answered it but not published his result:

Theorem 5.1.3 (Kleene [16]) There exist two disjoint, r.e. sets A, B c N such that no recursive set C satisfies (5.8).

So the simple minded analogies (5.7) fail, but they did not go away: they motivated a great deal of research in the twenty years that followed and ultimately, as we will see, a corrected version of them turned out to be an important part of the story of HYP.