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

Improve this question
$\endgroup$
5
  • $\begingroup$ I suppose that all of these are boldface $\mathbf\Pi^1_n$, right? $\endgroup$
    – Asaf Karagila ♦
    Commented 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$
    – Noah Schweber
    Commented 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$
    – Mariano Suárez-Álvarez
    Commented Oct 27, 2013 at 7:50
  • $\begingroup$ I tend to agree. It's standardized, unfortunately. $\endgroup$
    – Noah Schweber
    Commented 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 ♦
    Commented Oct 27, 2013 at 8:30

2 Answers 2

Reset to default
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.

Improve this answer
$\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$
    – Noah Schweber
    Commented 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$
    – Ulrik Buchholtz
    Commented 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$
    – Noah Schweber
    Commented 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$
    – Ulrik Buchholtz
    Commented 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$
    – Noah Schweber
    Commented Oct 27, 2013 at 23:09
7
$\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$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Very nice example! $\endgroup$
    – Noah Schweber
    Commented Oct 28, 2013 at 19:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .