# What sets of primes can we pick out with first-order statements?

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?

-
For some primes the interpretation of the statement might involve dividing by zero, and for others it might not. Is this a problem? Oh -- the examples I'm thinking of involve being able to talk about the number 1. I assume I'm allowed to do that? I've only just noticed it's not in your list. – user30035 Feb 14 '13 at 20:51
1 is definable from those operations – Cody Dance Feb 14 '13 at 21:29
I should have put $1$ and $0$ on the list for clarity, but as Cody points out it doesn't matter. – Will Sawin Feb 14 '13 at 21:49
These sets form a countable Boolean algebra, so one way to think about this is to characterize this Boolean algebra. – Andrej Bauer Feb 14 '13 at 21:55
I'm still finding it difficult to interpret what the question means. How does one interpret "there exists x such that for all y with sigma(y)=y, 1/(y^2+1)!=x". This seems to me to make sense only for 50 percent of primes. – user30035 Feb 14 '13 at 21:56

## 1 Answer

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.

-