Algebraic closure for $\mathbb{Q}$ or $\mathbb{F}_p$ without Choice? I know the usual proof of the existence of an algebraic closure for any field using Zorn's Lemma. The answer to this previous question makes it clear that in general, some nonconstructive axiom (not necessarily the full AC) is needed to guarantee an algebraic closure. My question is if we can avoid any of this in the cases of $\mathbb{Q}$ and $\mathbb{F}_p$.

Can algebraic closures for $\mathbb{Q}$ and $\mathbb{F}_p$ be constructed in ZF?

Intuitively, it seems plausible to me that they can. There are two places I see a need for an AC-typed axiom in the construction of an algebraic closure: one is to create some order (i.e. bijection with $\mathbb{N}$) for the set of polynomials whose roots I need to adjoin; two is to handle what happens when I start adjoining roots and the polynomials start factoring into smaller factors. (Which factor do I approach first?) It seems to me that $\mathbb{Q}$ and $\mathbb{F}_p$ both have structure that could be used cleverly to resolve both of these points without recourse to AC. However, I don't see the path clearly. 
 A: Actually, according to this FOM post, Wilfrid Hodges [1975, Läuchli's algebraic closure of $\mathbb{Q}$] proved that ZF is not enough to prove the existence of a unique algebraic closure of $\mathbb{Q}$, where he takes algebraic closure to mean an algebraically closed field containing (an isomorphic copy of) $\mathbb{Q}$ and no other strictly smaller algebraically closed subextension.
On the other hand, in the same post, Stephen Simpson asserts that every countable field $K$ admits a unique (up to non-unique isomorphism) countable algebraic closure, in the sense of a countable algebraically closed field containing (an isomorphic copy of) $K$ whose elements are all algebraic over (the copy of) $K$.
As far as I can tell, the construction given by Henning Mahkolm below should work to construct an algebraic closure of $\mathbb{Q}$, and so should Arturo Magidin's suggestion (modulo proving that $\mathbb{C}$ has all roots of all polynomials over $\mathbb{Q}$). Here is the required fact to pass from one to the other:
Proposition. Let $L$ be a field extension of $K$. If every polynomial over $K$ splits over $L$, then there is a unique subextension $\overline{K}$ such that


*

*$\overline{K}$ is an algebraically closed field.

*$\overline{K}$ is minimal with respect to this property.


Proof. Let $\overline{K} = \{ x \in L : x \text{ is algebraic over } K \} $. Clearly, if we can show (1), (2) will follow by construction: any algebraically closed subextension of $L$ must contain $\overline{K}$ as a subset.
By the usual dimension arguments – which I believe are allowed since we only need to work with finite-dimensional vector spaces over $K$ – it can be shown that $\overline{K}$ is a subfield of $K$: the key point is that if $K'$ is a finite extension of $K$ and $K''$ is a finite extension of $K'$, then $K''$ is a finite extension of $K$, and if $x$ is algebraic over $K'$ then $K'(x)$ is finite over $K'$, so $x$ is algebraic over $K$ itself.
Now, consider an arbitrary polynomial $p$ over $\overline{K}$. Since $p$ only has finitely many coefficients, it is in fact a polynomial over some subfield $K'$ which is a finite extension of $K$. So it is enough to show that, for any finite subextension $K'$, every polynomial $p$ over $K'$ splits over $\overline{K}$. But $K'$ is finite over $K$, so every root of $p$ must be algebraic over $K$, and every polynomial over $K$ splits over $\overline{K}$ by hypothesis, so $p$ must split over $\overline{K}$ as well, and hence, over $\overline{K}$. So $\overline{K}$ is indeed algebraically closed.

Regardless, a few of the things we want algebraic closures for can be done by hand in the absence of choice. For example:
Lemma. Let $K$ be a field, and let $K \hookrightarrow L$ and $K \hookrightarrow L'$ be any two finite extensions. Then, there is a finite extension $K \hookrightarrow M$ containing isomorphic copies of $L$ and $L'$ as subextensions.
Proof. Let $A = L \otimes_K L'$. This is a finite-dimensional $K$-algebra. As such, it has a finite upper bound on lengths of strictly ascending chains of ideals, and therefore contains a maximal ideal $\mathfrak{m}$. (Note: this is much stronger than the usual ascending chain condition, and the ascending chain condition is not enough to prove the existence of maximal ideal! See [Hodges, 1973, Six impossible rings].) It is easy to check that the field $M = A / \mathfrak{m}$ has the desired properties.
Lemma. Let $K$ be a field, and let $p$ be a polynomial over $K$. Then, there is an extension $K \hookrightarrow L$ which splits $p$.
Proof. By the preceding lemma, if we can do this for irreducible polynomials, then we can do this for all polynomials. We may assume $p$ is irreducible of degree at least 2. Observe that $K' = K[x] / (p)$ is a field, and $p$ factors over $K'$ into polynomials of strictly lower degree. The result follows by induction on the degree of $p$.
So as long as we are content to only work with finitely many polynomials at any time, things should be fine...
A: Even if the axiom of choice does not hold in the universe itself, many of its uses can be replaced de-facto by well orders (which allow effectively choosing elements). This allows showing existence of a minimal algebraically closed field, but it is not enough to show its uniqueness.
Much like Henning said, if a field is countable (like the rationals, or finite fields) then we can effectively order the polynomials then go through the list and add the needed roots. In the general case this won't really work because we don't have a way of choosing a lot of polynomials at once. As Zhen Lin notes in his answer, it was shown that such algebraic closure need not be unique up to isomorphism.
Let me digress for a moment (it's gonna be worth it in a paragraph or two) and talk about weak choice principles. I give a division of three kinds of weak choice principles. There are "choices family principles" (we can choose from certain families of nonempty sets) sort of choice principles like The Axiom of Countable Choice; there are topological principles (like the Ultrafilter lemma and its equivalents); and there are other weird principles (Small Violations of Choice, KWP's, etc etc.).
These are often independent of one another, for example the first Cohen model shows that choice for certain families fail strongly (we cannot choose from a countable family of infinite sets) while the ultrafilter lemma holds.
Interestingly enough, the existence and uniqueness of an algebraic closure follow from the ultrafilter lemma (equiv. Boolean prime ideal theorem; Compactness theorem; etc.) and not from well orders and choice related principles. So while we can use well orders to effectively choose how to add the roots to the polynomials, we can do it in a "less constructive" way by using the ultrafilter lemma instead - even if the field cannot be well ordered. It is not known (as far as I know) whether or not existence implies uniqueness; or the ultrafilter lemma. It is known that uniqueness does not imply neither of them though.
A: I believe we can generalize a bit: every well-orderable field $K$ has a well-orderable algebraic closure. (and any two are isomorphic)
First, choose a well-ordering $<$ on $K$. Also, choose a well-ordering of the polynomials over $K$ (e.g. a lexicographic order). The $\alpha$-th polynomial is $f_\alpha$.
Using transfinite recursion, construct a family $L_\alpha$ of algebraic extension fields of $K$, and well-orderings $<_\alpha$ on $L_\alpha$ such that, for any $\alpha < \beta$:


*

*$L_\alpha$ is a subfield of $L_\beta$

*If $x \in L_\alpha$ and $y \in L_\beta \setminus L_\alpha$, then $x < y$.


The base case will be $L_0 = K$ and $<_0 = <$. At each $\alpha > 0$, perform the following:


*

*$E = \cup_{\beta < \alpha} L_\beta$ is an algebraic extension of $K$

*$<_E = \cup_{\beta < \alpha} <_\beta$ is a well-ordering on $E$

*Construct $L_\alpha$, a splitting field of $f_\alpha$ over $E$

*Modify $L_\alpha$ so that $L \subseteq L_\alpha$.

*Construct a well-ordering $<_\alpha$ on $L_\alpha$ (e.g. lexicographical, as a finite-dimensional $E$-vector space)

*Modify $<_\alpha$ so that $E$ is an initial segment of $L_\alpha$


The main thing to make this work, I think, is to verify making the splitting field is constructive -- e.g. note that we have a canonical choice of well-ordering on polynomials over $E$, and thus a canonical way to choose factor of $f_\alpha$ each time we need to do so.
A: For any finite or countable field $K$, you can well-order $K$ even without AC, and then you don't actually need any further choice to construct a closure for it.
Namely, since $K$ can be well-ordered, you can well-order all monic polynomials over $K$ and adjoin roots for the irreducible ones one by one by transfinite induction up to $\omega_1$. Each time we adjoin elements, we can well-order the new elements and stick them at the end of the well-ordering of the ones we already have. If we order the polynomials primarily by "maximal coefficient" rather than by degree, the new polynomials that become possible after each extension will always come after the ones we already know.
By the time we reach $\omega_1$, there cannot be any more polynomials that need to have roots adjoined. Namely, every polynomial we can form at that point will have had each of its coefficients added at a time when there were only countably many polynomials in our list of polynomials to process, so this polynomial will have been processed at some step before $\omega_1$.
Edit to add: In fact, as Zhen Lin points out, one only has to adjoin roots for polynomials with coefficients in $K$. For $K=\mathbb Q$ that is shown in this question, but the arguments there appear to work in general. This is easy enough to do for any well-orderable $K$, not just countable ones.
