I'm glad you decided to follow up on my suggestion to look at Descriptive Set Theory! As I mentioned in my earlier answer, there are two flavors of Descriptive Set Theory: the "boldface theory" and the "lightface theory." As you observed, the boldface theory of sets of natural numbers is completely trivial since every subset of $mathbb{N}$ is clopen, but the lightface theory is not trivial at all.
The lightface theory is completely analogous to the boldface theory except that all operations are required to be computable, or effective in the descriptive lingo. Let's go through the first few levels of the boldface and lightface Borel hierarchies in parallel. Let $X$ be a Polish space and let $(U_n)_{n=0}^infty$ be a nice enumeration of a basis for the topology on $X$.
A boldface $boldsymbol{Sigma}^0_1$ set is simply an open subset of $X$, or a countable union of basic open sets. Similarly, a lightface $Sigma^0_1$ set is an effective union of basic open sets, i.e. a union of the form $bigcup_{n=0}^infty U_{f(n)}$ where $f$ is a computable function. Well, not quite, since this informal definition technically excludes the empty set. A better definition is that the lightface $Sigma^0_1$ sets are the sets $G_e = bigcup_{n in W_e} U_n$ where $W_e$ is the $e$-th computably enumerable set. This also gives a better listing of the lightface $Sigma^0_1$ sets.
A boldface $boldsymbol{Pi}^0_1$ set is simply a closed subset of $X$, or the complement of a boldface $boldsymbol{Sigma}^0_1$ set. Similarly, a lightface $Pi^0_1$ set is a the complement of a lightface $Sigma^0_1$ set. Note that we have a nice enumeration of all lightface $Pi^0_1$ sets, namely $F_e = X setminus G_e$ where $G_e$ was defined above.
A boldface $boldsymbol{Sigma}^0_2$ set is a $F_sigma$ subset of $X$, or a countable union of boldface $boldsymbol{Pi}^0_1$ sets. Similarly, a lightface $Sigma^0_2$ set is an effective union of $Pi^0_1$ sets. As above, the lightface $Sigma^0_2$ sets are enumerated by $G'_e = bigcup_{n in W_e} F_n$ where $W_e$ is the $e$-th computably enumerable set and $F_e$ was defined above.
A boldface $boldsymbol{Pi}^0_2$ set is a $G_delta$ subset of $X$, or the complement of a boldface $boldsymbol{Sigma}^0_2$ set. Similarly, a lightface $Pi^0_2$ set is a the complement of a lightface $Sigma^0_2$ set. Note that we again have a nice enumeration of all lightface $Pi^0_2$ sets, namely $F'_e = X setminus G'_e$ where $G'_e$ was defined above.
And so on, lightface $Sigma^0_{n+1}$ sets are effective countable unions of lightface $Pi^0_n$ sets, which in turn are complements of lightface $Sigma^0_n$ sets and at each step we have a nice enumeration of all of these sets.
Just as for the boldface Borel hierarchy, there is no reason to stop at $omega$; this process can be continued well into the transfinite, but there are a few roadblocks along the way. Because we want the hierarchy to be effective, we can only go up to the Church-Kleene ordinal $omega_1^{CK}$, which is the smallest non-computable ordinal. (Also, the hierarchy is defined using ordinal notations instead of actual ordinals.) In the end, we get the family lightface Borel sets, which is a countable subfamily of the usual Borel sets.
The analytic sets, or boldface $boldsymbol{Sigma}^1_1$ sets, also have a lightface analogue. The boldface $boldsymbol{Sigma}^1_1$ sets are precisely the projections onto the $X$-axis of the boldface $boldsymbol{Pi}^0_1$ subsets of the Polish space $X times mathbb{N}^mathbb{N}$, where $mathbb{N}^mathbb{N}$ denotes Baire space. Similarly, the lightface $Sigma^1_1$ subsets of $X$ are the projections onto the $X$-axis of the lightface $Pi^0_1$ subsets of $X times mathbb{N}^mathbb{N}$. Note that since we have a nice enumeration of the lightface $Pi^0_1$ sets, we also have a nice enumeration of the lightface $Sigma^1_1$ sets. There are similar lightface analogues of the entire projective hierarchy. A lot of the results of the boldface theory transfer to the lightface theory. For example, the Suslin Theorem that the boldface $boldsymbol{Delta}^1_1$ sets are precisely the Borel sets. A theorem of Kleene says that the same holds for the lightface $Delta^1_1$ sets, namely these are precisely the lightface Borel sets described above.
In the case of the discrete (and Polish) space $mathbb{N}$, the natural choice of basis are the singletons $U_n = {n}$. Working through the definitions, we see that the lightface $Sigma^0_1$ subsets of $mathbb{N}$ are precisely the computably enumerable subsets of $mathbb{N}$ and the lightface $Pi^0_1$ sets are the complements thereof. Hence, the $Delta^0_1$ subsets of $mathbb{N}$ are precisely the computable sets. In fact, the lightface $Sigma^0_n$, $Pi^0_n$, $Delta^0_n$, perfectly match the arithmetic hierarchy. The lightface Borel subsets of $mathbb{N}$ are commonly called hyperarithmetic sets.
Obviously, there are lots and lots of interesting properties of subsets of sets of natural numbers!
No comments:
Post a Comment