5
$\begingroup$

Recall that a set $A \subseteq \mathbb N$ is (many-one, Turing) $\Sigma_n$-complete if it's $\Sigma_n$ and any other $\Sigma_n$ set (many-one, Turing) reduces to it. This definition actually makes sense in any model of arithmetic and I want to focus on the possibility that $\omega$ is non-standard in this question.

In the context of arithmetic the notion of a $\Sigma_n$-complete set is well studied. There are several well-known examples of $\Sigma_n$-complete sets. For instance the $n^{\rm th}$-jump of $\mathbf{0}$ is one and the set of true $\Sigma_n$ sentences is another. Both of these have the appeal that they are definable in any model of $\mathsf{PA}$ (by the same formula, regardless of the model, though of course different models of $\mathsf{PA}$ might disagree about what elements satisfy the definition).

My question is about the analogue of this situation for models of $\mathsf{ZF}$. Specifically I want to know:

  1. What (if any) analogues of the notion of a $\Sigma_n$-complete set have been studied for the Levy hierarchy?
  2. Are there "nice" (i.e. well-known) examples of $\Sigma_n$-complete sets that are definable in any model of $\mathsf{ZF}$ similar to e.g. the $n^{\rm th}$-jump of $\mathbf{0}$?

For the particular application I'm looking at I would prefer to work with models of $\mathsf{ZF}$ (not necessarily with choice) but if choice is somehow needed for the answer, that's interesting too.

Improve this question
$\endgroup$
7
  • 6
    $\begingroup$ Isn't $\Sigma_n$ truth predicate the example here? $\endgroup$
    – Asaf Karagila ♦
    Commented Sep 2, 2021 at 11:30
  • $\begingroup$ @AsafKaragila presumably yes, this is what I'm expecting, but what exactly does this mean formally? What is the analogue of many-one/Turing reduction that makes the $\Sigma_n$-truth predicate complete? I started to write in a paper that the $\Sigma_n$-truth predicate is a $\Sigma_n$-complete set and then realized I didn't know how to define this. A look through a number of standard set theory books turned up nothing on this. $\endgroup$
    – Corey Bacal Switzer
    Commented Sep 2, 2021 at 11:52
  • 4
    $\begingroup$ Are you interested in $\Sigma_n$-complete classes (e.g., satisfaction predicates) or $\Sigma_n$-complete sets of integers (e.g., truth predicates)? $\endgroup$
    – Gabe Goldberg
    Commented Sep 2, 2021 at 13:56
  • 2
    $\begingroup$ @GabeGoldberg Yes, I wrote "set" but I guess I really meant class (e.g. satisfaction predicate)! $\endgroup$
    – Corey Bacal Switzer
    Commented Sep 3, 2021 at 12:10
  • 1
    $\begingroup$ Assuming ZFC, the class $C$ of $V_\alpha$'s is "$\Sigma_2$-complete", in that it is $\Sigma_2$-definable, and there is a uniform reduction of $\Sigma_2$ to $\Sigma_1$-in-$C$. But I don't know if this holds only assuming ZF (this relates to @HanulJeon's question math.stackexchange.com/questions/4075153/…) $\endgroup$
    – Farmer S
    Commented Sep 3, 2021 at 12:14

0

Reset to default

You must log in to answer this question.