Showing all finite subsets of $\mathbb{A}^n(k)$ are algebraic, and is it possible to sample from the resulting ideal? It would seem that this is pretty trivial but I'm self-teaching and wanted to check my proof with the huge brains lurking on this chan :)
It would seem to me you can show that every finite set of points in $\mathbb{A}^n(k)$ is algebraic.
Consider a set of $m$ points in $k^n$, $a_1, ..., a_m$. We do this by induction in number of points.
The base case: just the first point. $V(\{a_{1,1},a_{1,2},...,a_{1,m}\}) = V((X_1 - a_{1,1}, X_2 - a_{1,2}, ..., X_n - a_{1,n}))$, the variety corresponding to the ideal generated by linear monomials in the obvious way.
Then, the inductive case: we assume we have a variety for points $a_1$ through $a_{k-1}$ called $V_{k-1}$. We can form a variety for just this $k$th point with the above method -- i.e., $V'(\{a_{k,1},a_{k,2},...,a_{k,m}\}) = V((X_1 - a_{k,1}, X_2 - a_{k,2}, ..., X_n - a_{k,n}))$ Then, we can form the new variety $V_k = V' \cap V_{k-1}$, and $I(V_k) = I(V_{k-1}) \cup I(V')$.
So for any finite $k$ set of points, I show by induction that it is algebraic.
One thing that perplexes me -- when I get to the final $I(V_n)$, I am interested in what those polynomials look like. Is there any computationally efficient ways to "sample" from the ideal?
 A: Your proof is ok.
Here is a sketch how to find explicitely the polynomials, i.e write your finite set as intersections of hypersurfaces.

Lemma 1 :  Let $b, a_1, \dots, a_m$ be points in $\Bbb A^n$. There is always an irreducible subvariety $V$ with $b \not \in V$ and $a_i \in V$ for $i = 1, \dots, m$.
Lemma 2 : Let $a_1, \dots, a_m$ be points in $\Bbb A^n$ and $V$ a subvariety with $a_i \in V$. Then, there is a subvariety $W$ of smaller dimension, which contains $a_1, \dots, a_m$.

Now, applying $n$ times lemma 2 gives us a closed finite subset $F$ with $a_i \in F$. Applying Lemma $1$ and induction gives explicit polynomials.
Proof of lemma 1 : Exercise :-)
Proof of lemma 2 : Let $A_d = \{f \in \mathcal O(V) : \deg(f) \leq d\}$. This is a vector space, and for $d$ big enough $\dim A_d \geq m$ (this always works unless $\dim V = 0$). In particular, there is always an element $f \in \mathcal O(V)$ with $f \neq 0, f(a_i) = 0$ for all $i$. You can take  $W = Z(f_i)$.
An example : Assume $n=2$. Then, for any points $a_1, \dots, a_m$ there is a curve of large degree $d$ with $a_i \in C$. Now, consider a different curve $C'$ of degree $d$ (assume $C,C'$ irreducible and $C \neq C'$) with the same property. Now, $C \cap C' = \{a_1, \dots, a_m, b_1, \dots, b_r\}$. For each $1 \leq j \leq r$, pick a irreducible curve $C_j$ with $a_i \in C_j, b_j \not \in C_j$. Now, if $f,f',f_j$ are equations for $C,C',C_j$ then the solutions of $f = f' =  f_1 = \dots = f_r = 0$ are exactly $\{a_1, \dots, a_m\}$.
