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

Definition: A dilator is functor from ON to ON (the large poset of ordinals and strictly increasing functions) preserving filtered colimits and pullbacks. A dilator is weakly finite if it maps finite ordinals to finite ordinals. A dilator is recursive if it is weakly finite and the morphism part is a recursive function from N to N under a standard coding of finite sequences as numbers.

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'm finding Girard alternately vague and difficult to read; what is a "recursive dilator?" My understanding is that a dilator is a functor from ON to ON preserving limits and pullbacks. The obvious (to me) way of recursifying this results in recursive dilators being indexed by natural numbers, which isn't exactly what I was looking for. – Noah Schweber Oct 27 '13 at 7:09
• 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
• The abstract looks interesting; however, I have to ask: how is one supposed to pronounce "ptyx?" And why "ptyx" in the first place? jstor.org/stable/2907653 – Noah Schweber Oct 27 '13 at 23:09

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$.

• Very nice example! – Noah Schweber Oct 28 '13 at 19:09