8
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ I suppose that all of these are boldface $\mathbf\Pi^1_n$, right? $\endgroup$
    – Asaf Karagila
    Oct 27, 2013 at 0:45
  • 1
    $\begingroup$ I don't think so; e.g., the set of reals coding well-orderings is lightface $\Pi^1_1$. $\endgroup$ Oct 27, 2013 at 1:04
  • 1
    $\begingroup$ I wonder about the goodness of the idea of using font weight (of Greek letters!) as an apparently significative notation in this case! $\endgroup$ Oct 27, 2013 at 7:50
  • $\begingroup$ I tend to agree. It's standardized, unfortunately. $\endgroup$ Oct 27, 2013 at 8:04
  • $\begingroup$ @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). $\endgroup$
    – Asaf Karagila
    Oct 27, 2013 at 8:30

2 Answers 2

7
$\begingroup$

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

Added October 27:

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.

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ Oct 27, 2013 at 7:09
  • $\begingroup$ 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? $\endgroup$ Oct 27, 2013 at 17:18
  • $\begingroup$ Thanks! I'd definitely be interested in whether weakly finite dilators are a $\Pi^1_2$-complete set of reals - that certainly seems plausible. $\endgroup$ Oct 27, 2013 at 17:34
  • $\begingroup$ 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. $\endgroup$ Oct 27, 2013 at 22:37
  • $\begingroup$ 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 $\endgroup$ Oct 27, 2013 at 23:09
8
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Very nice example! $\endgroup$ Oct 28, 2013 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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