Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is every $\Delta_2$ set a 'finite boolean combination' of $\Sigma_1$ sets? (I.e. is it a member of the smallest collection of sets closed under finite union, intersection and complement that contains all $\Sigma_1$ sets?)

Probably not. But is there an easy counterexample?

Same question for $\Delta_3$ and $\Sigma_2$.

share|cite|improve this question
But $\Sigma_0$ is closed under all such operations. – yaakov Jan 4 '12 at 10:33
Huh? Also under complement? – Anonymous Jan 4 '12 at 10:34
The definition I know is $\Sigma_0=\Pi_0=\Delta_0$ are the sets describable by formulas in which all quantifiers are bounded. – yaakov Jan 4 '12 at 10:36
Oops; question edited. – Anonymous Jan 4 '12 at 10:43
The topological version (boldface version)... Given a set, which is both $F_\sigma$ and $G_\delta$, is it necessarily a finite Boolean combination of open sets? Or (next level): Given a set, which is both $F_{\sigma\delta}$ and $G_{\delta\sigma}$, is it necessarily a finite Boolean combination of $F_\sigma$ sets? – GEdgar Jan 4 '12 at 14:19

It's not clear to me which context you're asking about. The tag "descriptive set theory" suggests that you're referring to a topological context, as in GEdgar's comment, but then there would ordinarily be superscripts 0 or 1 on $\Sigma$ and $\Delta$ to indicate which hierarchy you're asking about. Anyway, I'll answer the recursion-theoretic interpretation of the question --- with $\Delta^0_2$ and $\Sigma^0_1$ over the natural numbers. I believe the argument can be lifted to the corresponding boldface classes over the reals, but I haven't checked this carefully.

Consider tuples of natural numbers $(n,e_1,\dots,e_n,t)$ representing Boolean combinations of $\Sigma^0_1$ sets; $n$ tells how many $\Sigma^0_1$ sets are being combined, $e_1,\dots,e_n$ are their indices (in some standard scheme for indexing r.e. sets), and $t$ codes (in some fixed, standard way) the truth table of the Boolean operation that is to be applied to these r.e. sets. By means of another standard coding function, encode such tuples as natural numbers. Now let $D$ be the set of those natural numbers $x$ such that $x$ is a code, in the sense just described, for a Boolean combination $X$ of $\Sigma^0_1$ sets and $x\notin X$. As with all such diagonal constructions, it follows immediately that $D$ is not a Boolean combination of $\Sigma^0_1$ sets. (If it were such a combination, described by the tuple $(n,e_1,\dots,e_n,t)$, let $x$ code that tuple and observe that $x\in X$ iff $x\notin X$, a contradiction.) Yet $D$ is a $\Delta^0_2$ set; that is, it is recursive in the universal $\Sigma^0_1$ set $0'$. Indeed, given an oracle for $0'$, we can compute $X$ as follows: On input $x$, decode $x$ and see whether it coded a tuple $(n,e_1,\dots,e_n,t)$ representing a Boolean combination of $\Sigma^0_1$ sets. If not, output "no". If so, use the oracle to determine, for each $i=1,\dots,n$, whether $x$ is in the $\Sigma^0_1$ set with index $e_i$; then apply to these answers the truth table coded by $t$; finally output the opposite of the truth value given by $t$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.