What is the negation to almost everywhere? We have some statement $P$ which holds almost everywhere in some complete measure space 
$(\Omega, \mathcal{F}, \mu)$. 
Formally
$$ \exists N \in \mathcal{F} : \mu(N) = 0 : \forall x \in \Omega \setminus N : P(x) \ \text{holds}$$
so intuitively the statement $P$ holds in $\Omega$ except possible for some points in a null set $N$.
Now I think that the negation is
$$\forall N \in \mathcal{F} : \mu(N) \not = 0 : \exists x \in \Omega \setminus N : P(x) \text{ does not hold}$$
I can't quite put my finger on it, but this contradiction does not feel right. I have note taken any courses in formal mathematical logic so I am not sure if I have even constructed the negation correctly.  
The contradiction above does not feel like a "working mathematicians" negation. In the past I have blindly assumed that the negation implies that
$$\exists N \in \mathcal{F} : \mu \left( \left\{ x \in \Omega : P(x) \ \text{does not hold} \right\} \right) > 0$$
but I was unable to prove a strict equivalence between these statements.
 A: The problem is in your first statement, what does the second ":" mean? It's an "and" statement, really:
$$\exists N \in \mathcal{F}, (\mu(N) = 0 \text{ and } \forall x \in \Omega \setminus N : P(x) \ \text{holds}).$$
So the negation becomes:
$$\forall N, (N \not\in \mathcal{F}) \text{ or } (\mu(N) > 0 \text{ or } \exists x \in \Omega \setminus N, P(x) \text{ does not hold}).$$
Or equivalently ($P \text{ or } Q$ is the same as $\neg Q \implies P$):
$$\forall N, (N \not \in \mathcal{F}) \text{ or } ((\forall x \in \Omega \setminus N : P(x) \ \text{holds}) \implies \mu(N) > 0).$$
In English, if you have a measurable set such that $P(x)$ is true for all $x \not\in N$, then $N$ must have positive measure. Said in yet another way, you have to "miss" a set of positive measure if you want your statement to be true.
And since of course you can always consider the set $N = \{ x \in \Omega \mid P(x) \text{ does not hold} \}$, it does mean that this $N$ has positive measure (or is not measurable, which is a bit annoying in theory but not really in practice).
A: Here is a careful formulation which works as you would expect in an incomplete measure space. "$P$ holds a.e." is defined to mean that $B=\{ x \in \Omega : \neg P(x) \}$ is contained in a measurable set $N$ with measure zero. Being very formal, we can write
$$(\exists N \in \mathcal{F}) \left [ \mu(N)=0 \wedge \left [ (\forall x \in \Omega) \neg P(x) \Rightarrow x \in N \right ] \right ].$$
I stress that this formulation is clunky only because of the possibility of incompleteness. If you have completeness (which you usually do), then you can just define it as "$B \in \mathcal{F}$ and $\mu(B)=0$", which is easier to negate. But note that even in the presence of completeness, you need to include the "$B \in \mathcal{F}$" part to get the correct negation.
A: Let $$\alpha(N) \equiv N \in F$$ $$\beta (N)\equiv \mu (N)=0$$ $$\gamma (x) \equiv x \in \Omega/N$$
Then we can rewrite yoyr proposition as follows: $$\exists N [\alpha(N) \land \beta(N) \land \forall x (\gamma (x) \implies P(x))]$$
The negation then would be: $$\forall N [(\alpha (N) \land \beta (N)) \implies \exists x (\gamma (x) \land \lnot P(x))]$$
