Question

For each prime $p$, we have the algebraically closed field $\bar{\mathbb F}_p$ with the Frobenius automorphism.

Given any first-order statement with no free variables using the symbols $0,1, +, \times, -, /, \sigma(),=$, we can interpret it in $\bar{\mathbb F}_p$, interpreting the field operations to mean themselves and $\sigma$ to mean Frobenius.

For each prime, it is either true of false. This gives us a set of primes.

What sets of primes can be described this way?

It is easy to pick out the primes whose Frobenius elements have a certain conjugacy class in in a Galois extension of $\mathbb Q$, and to pick out finite sets of primes.

Are there any sets of this type not generated by conjugacy classes in Galois groups and finite sets under the logical operations?

Answer 1

You guessed the correct answer. This is explained in the paper of Mike Fried and George Sacerdote, Solving Diophantine Problems Over All Residue Class Fields of a Number Field and All Finite Fields, The Annals of Mathematics, 2nd Ser., Vol. 104, No. 2. (Sep., 1976), pp. 203-233.

Since the theory of fields lacks elimination of quantifiers in the language of rings (the formula $\exists y,\ x=y^2$ which says that $x$ is a square cannot be expressed directly as a polynomial condition on $x$), the authors introduce a richer language, using the concept of Galois stratifications, which allows for elimination of quantifiers. Geometrically, this basically means that one can eliminate quantifiers up to the level of finite extensions of fields.

See also Chapters 30 and 31 on Galois stratifications in the book Field arithmetic by Mike Fried and Moshe Jarden.