Investigations in Intuitionistic Hierarchy Theory
Wim Veldman

Abstract:
Investigations in Intuitionistic Hierarchy Theory
Wim Veldman

This thesis is concerned with constructive reasoning in descriptive set theory.

The venerable subject of descriptive set theory was developed in the early decades of this century, mainly by French and Russian mathematicians.
It started from the following observation:
once the class of continuous real functions has been established, one naturally comes to think of the class of real Functions which are limits of everywhere convergent sequences of continuous functions.
This wider class can be extended in its turn, by the same operation of forming limits of everywhere convergent sequences.
This goes on and on, even into the transfinite.
Thus a splendid structure arises, called Baire’s hierarchy.

The same story may be told in terms of sets.
Looking at the subsets oF Baire space ^\omega\omega which are forced into existence when we allow for the clopen (= closed-and-open) neighbourhoods and then apply the operations of countable union and intersection again and again, we may wonder once more, because there is no end of it.
One after another, the classes of Borel's hierarchy present themselves, each containing subsets of ^\omega\omega not heard of before,

No Borel class  exhausts  the possible subsets  of ^\omega\omega.
This can be proved in a few lines; one shows that each class contains at universal element and diagonalizes (cf. chapter 6, esp. 6.14).

However, the very ease of the proof arouses suspicion.
People like Borel, Baire, Lebesgue, who were the first to raise and answer many questions  in this subject, spent much thought on the plausibility of their arguments.
Diagonalizing was Felt as cheap reasoning, especially by Baire.
Avoiding the diagonal argument, only relying on methods "from practice", one succeeded in showing up members of the first three or four classes of Baire.

Diagonalizing of course was not the worst of evils. In Lusin's catalogue, to be found on page 55 of Lusin 1930, it comes immediately after "normal constructive argument" before such horrible things as: the use of \aleph_1 as a well-defined, completed mathematical set, or, even worse, the essentially incomprehensible argument by, which Zermelo established a well-ordering of any set, from the axiom of choice.

Now, For heaven’s sake, what might be wrong with the diagonal argument?
From a classical point of view, one cannot bring up much against it.
In fact, as soon as we agree upon the meaning of negation (P and \not P cannot hold together, whatever be the proposition P) we have to accept it.
But in intuitionism we may find an explanation for our uneasiness.

Let us remark that, classically, we may build up the Borel sets in ^\omega\omega from the closed-and-open neighbourhoods, using only countable union and intersection.
Complementationcan be missed as an operation for making new sets out of already existing ones: as the complement of any closed—and-open set is closed-and-open, the complement of any set built from the closed-and-open sets by countable union and intersection, is such a set again.
This certainty is given by such wonderful guardians of classical symmetry as are de Morgan's laws.

De Morgan's laws are not acceptable, intuitionistically, apart From some very simple situations, From which they were derived by a crude generalization.
We cannot explain away complementation, or, more qenerally, the analogue of logical implication, as methods of constructing sets.
But we might try to do without them.

We will do so in this treatise.
When negation and implication are put aside, the possibility of diagonalizing is taken from our hands, and the hierarchy problem is open again.
A solution is given in chapters 6-9.

There is good reason to consider negation and implication with some caution.
Many unsettled questions in Intuitionistic loqic are connected with them.
(Compare the discussion in the appendix, chapter l7 We are not able to decide how far the divergence between classical and intuitionistic logic goes.
Also, at curious role is played. by negation in the recent discussion of the intuitionistic completeness of intuitionistic predicate logic, cf. de Swart  l9'2‘6, Veldman I976)

The intuitionistic hierarchy has a very delicate structure.
The class of the closed subsets of Baire space, for instance, is no longer closed under the operation of finite union. One has to distinguish between closed sets, binary unions of closed. sets, ternary unions of closed sets, and so on.
This phenomenon is discussed in chapter 4.
The productive force of disjunction and conjunction is explored further in chapter 11.2.0-26 and chapter 12.0-7.
lmplication, although absent from chapters 6-9, is not completely forgotten, and, we will see, in chapter 5 and chapter 12.8-9 that it shares in some of the properties established for disjunction and conjunction.

Distrust of diaqonalization is one of many points on which early descriptive set theorists and intuitionists have similar views.
Their common basic concern might be described as: exploring the constructive continuum.
Brouwer’s rejection of classical logic is, of course, a major point of difference.

But one is tempted to ask not the main theorem of this essay, which establishes the intuitionistic hierarchy (chapter 9, theorems 9.7 and 9.9) might have delivered Baire From his scruples.

Since Addison 1955 it has become customary among logicians to consider descriptive set theory for its connection with recursion theory.
We will bypass this development.
From an intuitionistic point of view, recursion theory is an ambiguous branch on the tree of constructive mathematics.
The deep results of this theory depend on very serious applications of classical logic,
And the classical continuum, which is a rather obscure thing, is accepted without any comment, as a suitable domain of definition for effective operations.

Nevertheless, there is an analogy between recursion theory and the theory to be developed here:
Many paradoxical results of elementary recursion theory are due to the fact that functions and functionals are finite objects, and, therefore, of the same type as natural numbers.
Now, functions from Baire space ^\omega\omega to ^\omega\omega, being necessarily continuous, are determined by a sequence of neighbourhood functions, and thus may be seen to be themselves members of ^\omega\omega.
Once more, we are in a situation  where functions do not differ in type from their arguments and values.

We also have to admit that, if there is any elegance in these pages, it partly is due to modern recursion theory.
For instance, the following concept of many-one reducibility between subsets of ^\omega\omega is starring
 A \preceq B := \exists f [ f is a continuous function from ^\omega\omega to ^\omega\omega and \forall \alpha [ \alpha \in A \iff f(\alpha) \in B ] ]

This so—called "Wadge-reducibility" was made the subject of classical study by some students of Addison's (cf. Kechris and Moschovakis 1978, Wadge 198?).
Their methods, however, are very far from constructive.
We introduce this concept in chapter 2, after a short exposition of the principles of intuitionistic analysis.

In the second part of this thesis (chapters 10-l4) we turn to analytical sets, and the projective hierarchy. (cf. Note 3 on page 216).
Analytical sets, being close relatives of good old "spreads", get a chapter of their own. It will be seen that the classical duality between analytical and co-analytical sets is severely damaged (chapter 10).
Some famous results of Souslin’s are partly rescued by Brouwer's bar theorem, which we will present here under the name of Brouwer’s thesis.
(This expression means to suggest an analogy to Church's thesis in recursive function theory, that all calculable functions from \omega to \omega are general recursive) (chapter 13).
If we persist in excluding negation and implication, the projective hierarchy does not exceed its second |evel (chapter 14).
This is a consequence of the axiom AC_{11}, which has been introduced and advocated in chapter 1.

In chapter 11 we study the typically intuitionistic subject of "quantifying over small spreads."
Rather surprisingly, quantifying over the very simple spread \sigma_{2mon} already lead to sets which are not hyperarithmetical.
Like some sets in chapter 4, these sets turn into more complex ones when they are given a treatment by means of disjunction, conjunction or implication.
In chapter 12 we find many other sets which have similar properties.

The proper place of the last three chapters (15-17) is the margin.

In chapter 15 we ask ourselves what is the domain of validity of the principle of reasoning which we get from the axiom AC_{01}, introduced, in chapter 1, by “constructive contraposition".
This principle is vital to many a classical discourse.
It may be Seen as a simple case of the axiom of determinacy.
Chapter 16 pursues this line of thought a little further.

In chapter 17 we mention an annoying problem which we could not solve, and some quasi—solutions.

The synopsis is an analytical table of contents.

On the scene of contemporary mathematical logic a family reunion is being held, at which the different branches of the discipline cooperate in seeking for a new understanding  of the beautiful problems which occupied our grandfathers.
Recent books like Hinman 1978 and  Moschovakis 1980 report  about it.
Up to now, intwitionism has been absent.
Here it comes, at last, ignoring the question whether it has been missed, or was invited, and raises its voice, somewhat timidly, in the company of so much learning.