I'm looking at some work with Combinatorial Game Theory and I have currently got: (P-Position is previous player win, N-Position is next player win)
Every Terminal Position is a P-Position,
For every P-Position, any move will result in a N-Position,
For every N-Position, there exists a move to result in a P-Position.
These I am okay with, the problem comes when working with the Sprague-Grundy function; g(x)=mex{g(y):y \in F(x)}, where F(x) are the possible moves from x and mex is the minimum excluded natural number.
I can see every Terminal Position has SG Value 0, these have x=0, and F(0) is the empty set.
The problem comes in trying to find a way to prove the remaining two conditions for positions, can anyone give me a hand with these?
If I understand correctly, you're trying to prove that the Sprague-Grundy function outputs zero exactly on the $\mathcal P$ positions. Since you have a characterization of $\mathcal P$ positions and $\mathcal N$ positions in terms of the options (positions you can get to in one move), then the best way for you to do this would be induction, the exact form of which depends on your background.
If you have a theorem about how induction can work for games, use that. If you don't, but are comfortable with structural induction (say, on graphs), then induct on the game tree. If you're not comfortable with that, but are okay with the idea of the game tree and standard induction, induct on the depth $n$ of the game tree. The proof is essentially the same in all cases.