# “Interesting” properties of sets of natural numbers

On Wikipedia, there is a list of properties of sets of reals, which are in some sense "interesting": just have a look.

I could not find a comparable list of properties of sets of natural numbers (except their classification in the arithmetical hierarchy).

a) Any suggestions where to find such a list? (Arithmetic analogon to "Descriptive Set Theory"?)

b) Any reasons why (properties of) sets of natural numbers are less "interesting" than (properties of) sets of reals? Is it simply because the basic property of "open-ness" is missing for sets of natural numbers?

-
I have voted to close: this question is so subjective that it would be impossible to tell what counts as a correct answer. Also "tell me something interesting about math topic X" is not the kind of question that MO was created to answer, IMO. – Pete L. Clark Feb 8 '10 at 18:06
I think it is clear from Pete's reply and from the problems some of my recent questions have engendered, that there is a need for an MO-like forum for questions such as this (speculative, foundational, etc.). If MO (via the community wiki tag) is not the place, then perhaps the creators of MO will share their code with someone willing to set up a companion site of some sort. – Ian Durham Feb 8 '10 at 18:14
@ID: If you go to meta and make this comment, you will likely start an interesting discussion. You will also find that the same code used (and not written) by the MO creators is available to anyone: you could start such a companion site yourself. I should say though that I don't find this question to be either speculative or foundational: it's just very, very soft. – Pete L. Clark Feb 8 '10 at 18:27
Please move this discussion (re: a companion site) to meta. – Scott Morrison Feb 8 '10 at 18:45
@Pete: I'm not actually upset, at you or anyone else, though I think this is unfortunate for Hans. There are plenty of poorly formulated questions on MO. This one was actually not so bad, though it suffers from Hans's tendency to use intensional adjectives such as "natural" and "interesting," which could be avoided. (@Hans: I think this would be a good way to avoid such reactions since people tend to interpret these words subjectively.) – François G. Dorais Feb 8 '10 at 20:21

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!

-
Thanks a lot, you really encouraged me to delve deeper into descriptive set theory: sounds really promising and ... "interesting";-) – Hans Stricker Feb 8 '10 at 20:56
+1 Excellent as usual, Francois. – Joel David Hamkins Feb 8 '10 at 23:06
Excellent answer. – Pandelis Dodos Feb 9 '10 at 10:36

Theorem. Every natural number is interesting.

Proof. If not, then there are some uninteresting numbers. Let n be the least number that is not interesting.

• Now, that is INTERESTING!

:-)

-
And also every transfinite ordinal is interesting! (for the same reason...) – Joel David Hamkins Feb 8 '10 at 16:40
Also, every natural number is interesting in infinitely many ways. – MBN Feb 8 '10 at 16:47
Chapeau! But: The question was about interesting properties of sets of natural numbers. Can your proof be generalized? – Hans Stricker Feb 8 '10 at 16:52
At least every interesting natural number is (= represents) also an interesting (finite) set of natural numbers - via Ackermann encoding of hereditarily finite sets (see: gdz.sub.uni-goettingen.de/dms/load/img/…). – Hans Stricker Feb 8 '10 at 20:20

If there is no such list, why not make one?

Interesting properties of sets of natural numbers...

finite (infinite, cofinite ... other properties can be similarly extended)

density zero (for any of the common densities)

$\displaystyle\sum_{n \in A} \frac{1}{n}$ converges

-