16
$\begingroup$

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?

Improve this question
$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – user30035
    Feb 14, 2013 at 20:51
  • $\begingroup$ 1 is definable from those operations $\endgroup$
    – Cody Dance
    Feb 14, 2013 at 21:29
  • $\begingroup$ I should have put $1$ and $0$ on the list for clarity, but as Cody points out it doesn't matter. $\endgroup$
    – Will Sawin
    Feb 14, 2013 at 21:49
  • 1
    $\begingroup$ These sets form a countable Boolean algebra, so one way to think about this is to characterize this Boolean algebra. $\endgroup$
    – Andrej Bauer
    Feb 14, 2013 at 21:55
  • $\begingroup$ 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. $\endgroup$
    – user30035
    Feb 14, 2013 at 21:56

1 Answer 1

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.