The truthteller sentence is the sentence "this sentence is true". The sigma_n and pi_n truthteller sentences are expressible in set theory (and PA) for n>0. For sigma_1, pi_2, sigma_3, and so on, the truthteller sentence is false. On the other hand, for pi_1, sigma_2, pi_3, and so on, the truthteller sentence is true.

What determines the truth is the last quantifier. If the last quantifier is an existential, then the truthteller sentence is false, otherwise it is true. Here is a quick sketch of the proof we came up with tonight, though I don't really expect it to be intelligible to anyone else.

The form of the delta_0 part of the truthteller sentence depends on the last quantifier, because the delta_0 truth predicate is delta_1 and must be put in the form that starts with the same quantifier.

The first case is when the last quantifier is an existential. Rewrite it in form "there exists (w, a_0, ..., a_m)", where w is the witness given as parameter to the delta_0 truth predicate, and a_0 to a_m are the auxiliary sets needed by the delta_0 truth predicate and other machinery (such as the machinery that gets the godel number of the truthteller sentence).

Since the w is smaller than the tuple (w, a_0, ..., a_m), the recursion eventually bottoms out when the delta_0 part of the formula is given invalid auxiliary sets. In that situation the formula is false, because the delta_0 part of the formula is in the form "the auxiliary sets have the correct shape AND something".

In the second case, with foralls at the end, it's similar, except that bottoming out at incorrect auxiliary sets results in truth, because the delta_0 part of the formula is in the form "the auxiliary sets are correct IMPLIES something".

Note that this proof depends on the axiom of regularity, and might not hold if there are sets which aren't well-founded.