The Borel hierarchy is, of course, strictly increasing at
every step, so there will be sets of every countable
ordinal rank. Furthermore, all of these sets are relatively
concrete, obtained as countable unions of sets having lower
rank. But you asked for natural examples, so let me give a
few.
1) The collection of true statements of number theory, in
the ring of integers Z. This is well known to have
complexity Sigma^0_omega, which is a large step up from the
complexity you mentioned. This is, of course, a light-face
notion. The corresponding bold-face notion would be truth in arbitrary countable structures. That is, the
set of pairs (A,phi), where A is a first-order structure
and phi is true in A. This has complexity Sigma^0_omega for
the same reason as (1). (I regard this as a highly natural example, but Kechris' remark was about natural examples specifically from topology and analysis.)
2) The set of countable graphs with finitely many connected
components. This has complexity Sigma^0_3, since you must
say: there is a finite set of vertices, for all other
vertices, there is a path to one of them.
There are numerous other statements about finiteness that
also arise this way.
3) The set of (reals coding) finitely generated groups.
This is Sigma^0_3, since you say: there is a finite set in
the group, such that for all other elements of the group,
there is a generating word.
4) finitely-generated other structures, etc. etc.
5) The set of pairs (A,p), such that A is a real and p is a
Turing machine program with oracle A that accepts all but
finitely many input strings. Sigma^0_3, since "There is a
finite set of strings, for all other strings, there is a
computation showing them to be accepted."
No comments:
Post a Comment