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

(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.)

• I suppose that all of these are boldface $\mathbf\Pi^1_n$, right? – Asaf Karagila Oct 27 '13 at 0:45
• I don't think so; e.g., the set of reals coding well-orderings is lightface $\Pi^1_1$. – Noah Schweber Oct 27 '13 at 1:04
• I wonder about the goodness of the idea of using font weight (of Greek letters!) as an apparently significative notation in this case! – Mariano Suárez-Álvarez Oct 27 '13 at 7:50
• I tend to agree. It's standardized, unfortunately. – Noah Schweber Oct 27 '13 at 8:04
• @Mariano: While I agree with your and Noah about this not necessarily being a good idea, there's an excellent reason for this notation and the relations between are excellent. That aside, you can see the boldface notation sometimes written as a lightface+under-tilde. This, I was told, is a result of "standard" boldface notation when writing on blackboards. Some papers I ran into used that notation instead. Amusingly, the same can be said about names in forcing, which were written as boldface letters, and then as under-tilded letters (as they are written today by some authors, e.g. Shelah). – Asaf Karagila Oct 27 '13 at 8:30

An example that comes to mind is the set of recursive dilators; this is a $\Pi^1_2$-complete set (Theorem 4.1 in Girard 1985, Introduction to $\Pi^1_2$-logic). Dilators have some use outside of logic (e.g.: Some uses of dilators in combinatorial problems I, II, III).

Thus, weakly finite dilators are coded by reals, while recursive dilators are coded by numbers, and in the latter case forming a $\Pi^1_2$-complete set, just as the usual set of codes of recursive ordinals forms a $\Pi^1_1$-complete set.
• I added the definitions. Rereading your question, I see you were looking at sets of reals, while my answer addresses subsets of $\omega$. But perhaps weakly finite dilators are a $\Pi^1_2$-complete set of reals? – Ulrik Buchholtz Oct 27 '13 at 17:18
• Thanks! I'd definitely be interested in whether weakly finite dilators are a $\Pi^1_2$-complete set of reals - that certainly seems plausible. – Noah Schweber Oct 27 '13 at 17:34
• Indeed, I think this is in this article by Ressayre. See Sec. 3 there (the objects are called ordered Ehrenfeucht-Mostowski models with finitely many function symbols, but I think they're the same thing as (codes of) weakly finite dilators). There are related notions (ptykes) at higher types that provide $\Pi^1_n$-complete notions, according to a hard-to-find paper by Girard and Ressayre. – Ulrik Buchholtz Oct 27 '13 at 22:37
An example directly generalizing well-orderings is that the better quasi-orderings are $\Pi^1_2$-complete, shown in Marcone's aptly named The Set of Better Quasi-Orders is $\Pi^1_2$.