Let $B/A$ be a integral extension of (commutative unital) rings. The "Lying over" theorem states that for any prime ideal $P$ in $A$ there is a prime ideal $Q$ in $B$ such that $Q\cap A=P$.
The usual proof runs as follows (forgive me for the excess of details, if you know the proof you can safely skip): consider the multiplicative subset $S=A\setminus P$ of $A$, which is also a multiplicative subset of $B$. Then the ring extension $S^{-1}B/S^{-1}A$ remains integral. If $Q'$ is any maximal ideal in $S^{-1}B$ then its contraction $P'=Q'\cap S^{-1}A$ is a maximal ideal in $S^{-1}A$ (this holds in general for integral extensions).
Now for a general multiplicative subset $S$ of a ring $R$ with $0\notin S$ there is a natural bijection between the prime ideals of $S^{-1}R$ and the prime ideals of $R$ disjoint from $S$, via contraction through the natural ring homomorphism $\varphi: R\to S^{-1}R\,$; in particular such correspondence preserve inclusions.
In our case of interest to $Q'$ corresponds the prime ideal $Q=\varphi^{-1}(Q')$ of $B$, which will be maximal with respect to the property of being disjoint from $A\setminus P$, that is $Q\cap A\subseteq P$. On the other hand to $P'$, which is maximal in $S^{-1}A$, corresponds the ideal $P_0=\varphi^{-1}(P')$ (beware: this is not the same $\varphi$ as before) which is maximal with respect to the property of being disjoint of $A\setminus P$, that is $P_0\subseteq P$. But evidently there is only such prime ideal satisfying this maximality condition, namely $P$ (and in particular $S^{-1}A$ is a local ring), so $P_0=P$. Finally all the contractions discussed above commute nicely, and under such contractions we have simultaneously $Q'\mapsto Q\mapsto Q\cap A$ and $Q'\mapsto P'\mapsto P$, and voilà! $Q\cap A=P$.
The point of the proof above is that we are we are working with prime ideals $Q$ in $B$ such that $Q\cap A\subseteq P$, and we maximize $Q$. In other words, we try to attain the equality $Q\cap A=P$ "from below". When I was teaching this subject recently I asked to my students for ideas, and one of them said "we can try to prove that $PB$ is a prime ideal in $B$". I agreed with him, but I said "OK, but first let us prove that at least $PB$ is a proper ideal in $B$". I get stuck at this point but the new strategy keeps turning over my head.
After some thinking I managed to prove this "first step" as follows: suppose that $PB=B$. Then we have $1=p_1b_1+\cdots p_nb_n$ for some $p_i\in P$ and some $b_i\in B$. Let $M=A[b_1,\dots,b_n]$. Since each $b_i$ is $A$-integral, then $M$ is a finitely generated $A$-module, and since $1\in PM$, it follows that $PM=M$, so by Corollary $2.5$ of Atiyah and Macdonald we have $(1+p)M=0$ for some $p\in P$; but this is impossible because $p+1\ne0$, yet $1\in M$ so $(p+1)\cdot1=0$. This shows that in fact we have $PB\ne B$.
The next step following the philosophy of "from above" is to consider a prime ideal $Q$ of $B$ that is minimal among those containing $PB$ (equivalently, containing $P$). Note that here we are using a choice principle twice: one in order to exhibit a prime ideal containing $PB$, and once again in order to exhibit a minimal prime ideal with this property. I don't care about using it several times. What I really want is to avoid the use of rings of fractions. If this is not possible, OK, no problem... but AAARRRRGGHHH! I feel that this approach is plausible!
