Skip to main content
MathOverflow

Return to Question

added 142 characters in body
Source Link
Noah Schweber
Noah Schweber
  • 21.2k
  • 10
  • 110
  • 331

(To clarify, my interest is mainly lightface, that is, $\Pi^1_2$ instead of $\bf \Pi^1_2$, although it doesn't particularly matter.)

This is just an idle curiosity. In logic, I find myself frequently working with the countable ordinals; this is a $\Pi^1_1$ set of structures, in the sense that the set of reals coding well-orderings with domain $X\subseteq\omega$ is $\Pi^1_1$. This is also a fairly natural class of structures, of interest outside logic as well; and other interesting classes of structures - e.g., torsion groups, Artinian rings, infinite graphs into which a given infinite graph $G$ does not embed - are also $\Pi^1_1$ (and usually are vastly simpler than $\Pi^1_1$).

Obviously, there are more complicated classes of structures; however, all the examples I know are pretty artificial. So my question is: what are some natural classes of countable structures, which are worse than $\Pi^1_1$?

In particular:

Is there a natural class of countable structures which is $\Pi^1_2$ complete?

(Of course, what "natural" means is subjective. What I mean by natural here is "of roughly equal interest to non-logicians as well-orderings," but examples from within logic would be okay if there is an interesting argument to be made that they will someday be of interest outside logic.)

This is just an idle curiosity. In logic, I find myself frequently working with the countable ordinals; this is a $\Pi^1_1$ set of structures, in the sense that the set of reals coding well-orderings with domain $X\subseteq\omega$ is $\Pi^1_1$. This is also a fairly natural class of structures, of interest outside logic as well; and other interesting classes of structures - e.g., torsion groups, Artinian rings, infinite graphs into which a given infinite graph $G$ does not embed - are also $\Pi^1_1$ (and usually are vastly simpler than $\Pi^1_1$).

Obviously, there are more complicated classes of structures; however, all the examples I know are pretty artificial. So my question is: what are some natural classes of countable structures, which are worse than $\Pi^1_1$?

In particular:

Is there a natural class of countable structures which is $\Pi^1_2$ complete?

(Of course, what "natural" means is subjective. What I mean by natural here is "of roughly equal interest to non-logicians as well-orderings," but examples from within logic would be okay if there is an interesting argument to be made that they will someday be of interest outside logic.)

(To clarify, my interest is mainly lightface, that is, $\Pi^1_2$ instead of $\bf \Pi^1_2$, although it doesn't particularly matter.)

This is just an idle curiosity. In logic, I find myself frequently working with the countable ordinals; this is a $\Pi^1_1$ set of structures, in the sense that the set of reals coding well-orderings with domain $X\subseteq\omega$ is $\Pi^1_1$. This is also a fairly natural class of structures, of interest outside logic as well; and other interesting classes of structures - e.g., torsion groups, Artinian rings, infinite graphs into which a given infinite graph $G$ does not embed - are also $\Pi^1_1$ (and usually are vastly simpler than $\Pi^1_1$).

Obviously, there are more complicated classes of structures; however, all the examples I know are pretty artificial. So my question is: what are some natural classes of countable structures, which are worse than $\Pi^1_1$?

In particular:

Is there a natural class of countable structures which is $\Pi^1_2$ complete?

(Of course, what "natural" means is subjective. What I mean by natural here is "of roughly equal interest to non-logicians as well-orderings," but examples from within logic would be okay if there is an interesting argument to be made that they will someday be of interest outside logic.)

Source Link
Noah Schweber
Noah Schweber
  • 21.2k
  • 10
  • 110
  • 331

Natural $\Pi^1_2$ (or worse) classes of structures?

This is just an idle curiosity. In logic, I find myself frequently working with the countable ordinals; this is a $\Pi^1_1$ set of structures, in the sense that the set of reals coding well-orderings with domain $X\subseteq\omega$ is $\Pi^1_1$. This is also a fairly natural class of structures, of interest outside logic as well; and other interesting classes of structures - e.g., torsion groups, Artinian rings, infinite graphs into which a given infinite graph $G$ does not embed - are also $\Pi^1_1$ (and usually are vastly simpler than $\Pi^1_1$).

Obviously, there are more complicated classes of structures; however, all the examples I know are pretty artificial. So my question is: what are some natural classes of countable structures, which are worse than $\Pi^1_1$?

In particular:

Is there a natural class of countable structures which is $\Pi^1_2$ complete?

(Of course, what "natural" means is subjective. What I mean by natural here is "of roughly equal interest to non-logicians as well-orderings," but examples from within logic would be okay if there is an interesting argument to be made that they will someday be of interest outside logic.)