Coding Borel Sets

In this chapter, we take a further look at Borel subsets of $\Baire$. As is common in this setting, we call the elements of $\Baire$ reals. This is motivated by the fact that, via the continued fration expansion, $\Baire$ is homeomorphic to the set of irrational real numbers. Suppose $U \subseteq \Baire$ is open. Then there exists a set $W \subseteq \Nstr$ such that

Using a standard (effective) coding procedure, we can identify a finite sequence of natural numbers with a natural number, and thus can see $W$ as a subset of $\Nat$.

If we provide a Turing machine with oracle $W$, we can semi-effectively test for membership in $U$ as follows. Assume we want to determine whether some $\alpha \in \Baire$ is in $U$. Write ${}\alpha$ on another oracle tape, and start scanning the $W$ oracle. If we retrieve a ${}\sigma$ that coincides with an initial segment of ${}\alpha$, we know $\alpha \in U$. On the other hand, if $\alpha \in U$, then we will eventually find some $\alpha\Rest{n}$ in $W$. If $\alpha \not\in U$, then the search will run forever. In other words, given $W$, $U$ is semi-decidable, or, extending terminology from subsets of $\Nat$ to subsets of $\Baire$, $U$ is recusively enumerable (r.e.) relative to $W$.

Similarly, we can identify a closed set $F$ with the code for the tree

Then determining whether $\alpha \in F$ is co-r.e. in (the code of) $T_F$. If $\alpha \not\in F$ we will learn so after a finite amount of time.

These simple observations suggest the following general approach to Borel sets.

• Borel sets can be coded by a single infinite sequence in $\Baire$ (or $\Cant$).
• Given the code, we can recover the Borel set effectively, by means of oracle computations.
• The connection between degrees of unsolvability and definability results in a close correspondence between arithmetical sets ($\Sigma^0_n$) and Borel sets of finite order ($\bSigma^0_n$).

In this lecture we will fully develop this correspondence. Later, we will see that it even extends beyond the finite level.

Some notation for reals, strings, and numbers¶

We fix a computable bijection $\pi: \Nat \to \Nstr$. In general, we will often use string and their images under ${}\pi$ interchangeably, that is, for example, if $A \subset \Nat$, we will write $\sigma \in A$ to denote $\pi(\sigma) \in A$. We will also freely identify infinite binary sequences with the set of natural numbers they represent as their characteristic function.

Furthermore, let $\Tup{.,.}$ be the standard coding function for pairs,

Finally, let us define the following operations on elements of Baire (or Cantor) space: Given $\beta\in \Baire$,

• Let $\beta'$ be the real defined by $\beta'(n) = \beta(n+1)$. (We cut the first entry.)
• On the other hand, if $k \in \Nat$ and $\beta \in \Baire$, we obtain a new element of $\Baire$, which we denote by $(k, \beta)$, by concatenating $k$ and ${}\beta$.
• For $m \geq 0$, let $(\beta)_m$ be the $m$-th column of ${}\beta$, $(\beta)_m(n) = \beta(\Tup{m,n})$.

Borel codes of finite order¶

Borel codes are defined inductively.

The first position in each code indicates the kind of set it codes - an open set, a complement, or a union.

Note that the definition of Borel code actually assigns codes to representations of sets. A Borel set can have (and has) multiple codes, just as it has multiple representations. We can, for example, represent an open set by different sets $W$ of initial segments.

Moreover, every $\bSigma^0_1$ set is also $\bSigma^0_2$, and thus a set has codes which reflect the more complicated definition of the $\bSigma^0_1$ set as a union of closed sets. It is useful to keep this distinction between a Borel set and its Borel representation in mind.

The following is a straightforward induction.

Computing with Borel codes¶

Suppose ${}\gamma$ is a computable code for an $F_\sigma$ set $B$. We may assume ${}\gamma$ is of the form $(3,\gamma')$, with each column $(\gamma')_m$ being of the form $(2,1,(\alpha)_m)$, coding a closed set $F_m$.

With this, we can express membership in $B$ as follows:

Note that, since we assume ${}\gamma$ to be computable, the inner predicate $R(m,\sigma)$ given by

is decidable, that is, it can be decided by a Turing machine.

Hence any $\bSigma^0_2$ set $B$ with a computable code can be represented in the following form:

There exists a decidable predicate $R(m,\sigma)$ such that

$$\beta \in B \quad \iff \quad \exists m \: \forall n \; R(m, \beta\Rest{n}).$$

(6)

Conversely, if $R(m,\sigma)$ is a (decidable) predicate, let

We claim that $F_m$ is closed: Define a tree $T_m$ by letting

Then $[T_m] = F_m$. Moreover,

Thus, there seems to be a close connection between $F_\sigma$ sets with computable Borel codes and sets definable by $\Sigma^0_2$ formulas over computable predicates. Given that we introduced the notation $\bSigma^0_2$ for $F_\sigma$ sets earlier, this is perhaps not very surprising.

In this analysis, there seems to be nothing specific about the $F_\sigma$ set used in the example. Indeed, it can be extended to Borel sets of finite order, which we will do next.

We will introduce the lightface Borel hierarchy and show that it corresponds to Borel sets of finite order with recursive codes. Using relativization, we then obtain a complete characterization of Borel sets of finite order: They are precisely those sets definable by arithmetical formulas, relative to a real parameter.

But before we do that, we observe a basic fact about how we can compute with codes.

The effective Borel hierarchy¶

The following is an easy induction.

The following result is at the heart of the effective theory.

Relativization¶

Using relativized computations via oracles, we can define a relativized version of the effective Borel hierarchy. This way we can capture all Borel sets of finite order, not just the ones with computable codes.

A straightforward relativization gives the following analogue of Proposition 3.

We can now present the fundamental theorem of effective descriptive set theory.

The theorem facilitates working with Borel sets considerably. As an example, consider the set

We have

The predicate in the square brackets is computable and depends only on $\alpha\Rest{m}$. Therefore, $A$ is $\Sigma^0_2$ Borel set.