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?



What sets of primes can we pick out with first-order statements?
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](http://www.math.uci.edu/~mfried/paplist-ff/annals76.pdf)*,
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.


