Model given for a formula The formula in question
$$ \forall x \exists y [\ \ P(x,y) \rightarrow \exists z \forall u (\lnot P(u,z))\ \ ] $$
according to my text-book, has the following model
$ \text{Domain} = \mathbb{N} $
$ \lvert P\rvert = \{ (n,m): n,m \ \in \mathbb{N},\ \  n =2m \} $
According to its description, I'd assume the set $ \lvert P\rvert $ to have the following elements:
$$  \lvert P\rvert = \{ \\(0, 0) \\ (2, 1) \\ (4,2) \\ (6,3) \\ ... \} $$
So there has to exist a $z$ , which applied to any possible $u$ is not part of set  $\lvert P\rvert$ so that $\exists z \forall u (\lnot P(u,z))$ this condition can hold.
But inside $\lvert P\rvert$ every possible $z \in \mathbb{N}$ is inside the set, meaning there doesn't exist a $z$ in common to every $u$ which could satisfy the model.
Am I missing something? 

Every $z$ belongs to a pair $(2z,z)$. Thus (as you say) there is no $z$ such that $\lnot P(u,z)$ does hold for every $u$.
Thus, up to now: $∃z∀u(¬P(u,z))$ is false, and this is independent of $x$ and $y$.
Consider now $P(x,y)$; obviously, the pair $(x,x+1) \notin |P|$ and thus, we have that for every $x$ there is an $y$ such that $P(x,y)$ is false.
Now, "cook them" together: $\text { false } \to \text { false }$ is $\text { true}$. 
