Let L be a recursive algebraic extension of ℚ. Assume that, given α ∈ L, we can compute the roots in L of its minimal polynomial over ℚ and we can determine which roots are Aut(L)-conjugate to α. We prove that there exists a pair of polynomials that characterizes the Aut(L)-conjugates of α, and that these polynomials can be effectively computed. Assume furthermore that L can be embedded in ℝ, or in a finite extension of ℚp (with p an odd prime). Then we show that subsets of L[X]k that are recursively enumerable for every recursive presentation of L[X], are diophantine over L[X].
