I think I figured out some things about $\Sigma^0_1$ and $\Pi^0_1$ in the arithmetical hierarchy, for sets of infinite sequences, and I'm hoping I can get confirmation that I'm right, or can understand the ways in which my thinking is incorrect.

What I think I have figured out is that every set of infinite sequences in $\Sigma^0_1$ must be infinite in size--in fact uncountable--since a sentence containing only existential quantifiers over indexes into a sequence can only require that some digits satisfy a predicate. Therefore, any sequence satisfying the sentence would do because of a property of a finite number of locations in the sequence. All subsequent digits after those locations would be allowed to vary freely, in which case the number of sequences with the same initial pattern would be uncountable.

By contrast, sets of infinite sequences in $\Pi^0_1$ may be either be finite or infinite, I think. For example:

$\{x: (\forall n)\, x[n]=0\}$ contains only one element, $000\ldots$ .

$\{x: (\forall n)\, x[n]=0$ if $n$ is odd$\}$ allows the digits at the even-numbered locations to vary freely, so the number of sequences that satisfy this predicate for all $n$ is uncountable.

Is this correct? Are there ways in which I'm confused, or some obvious nuance that I'm missing?

  • 2
    $\begingroup$ The empty set is $\Sigma_1^0$. $\endgroup$ – Andrej Bauer Oct 29 '20 at 19:18

First observe that any $S \subseteq \{0,1\}^\mathbb{N}$ described by a $\Delta^0_1$-formula is clopen (open and closed subset), where we topologize with the product topology. Indeed, the subbasic sets of the form $B_{i,k} = \{x \in \{0,1\}^\mathbb{N} \mid x(i) = k\}$ are clopen by definition, and then complements (negation), finite unions (disjunction and bounded $\exists$) and intersections (conjunction and bounded $\forall$) of those are still clopen.

A $\Sigma^0_1$ subset $S \subseteq \{0,1\}^\mathbb{N}$ is a countable union of $\Delta^0_1$ sets, therefore it is open. But every open subset of $\{0,1\}^\mathbb{N}$ is either empty, or it contains a basic open set and is therefore uncountable.

  • $\begingroup$ Thanks Andrej. I assume that by $\mathbb{N}^\mathbb{N}$ you mean a countable sequence of integers. Is that right? So we could also use a countable sequence of 0's and 1's? Unfortunately, I have seen, but have not yet understood claims about open/closed/clopen-ness of sets of sequences. As a result, understanding your answer would require a bit of study. Such study would be worthwhile, but I suspect that there is a way of making the point without topology as well. $\endgroup$ – Mars Oct 29 '20 at 23:23
  • $\begingroup$ The same argument works for Cantor space $\{0,1\}^{\mathbb{N}}$. Yes, you can do "poor man's topology": just observe that every $\Sigma^0_1$ set is a countable union (because of $\exists$) of basic open sets, which are sets of the form $B(a_0, \ldots, a_n) = \{x \in \mathbb{N}^\mathbb{N} \mid x(0) = a_0 \land \cdots \land x(n) = a_n\}$. Each one of them is uncountable. $\endgroup$ – Andrej Bauer Oct 30 '20 at 8:23
  • $\begingroup$ I rephrased my answer so that it speak of the Cantor space instead of the Baire space. $\endgroup$ – Andrej Bauer Oct 30 '20 at 8:41
  • $\begingroup$ Thanks very much Andrej--I understand now. The comment about poor many's topology was very helpful. $\endgroup$ – Mars Oct 31 '20 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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