negating propositional formula with quantifiers

Question

In order to solve an exercise in computer sciences (proving a language $L$ to not be context-free) I need to negate the Pumping-Lemma. I was provided with the definition in the following form:

If $L$ ist a a context-free language the following conditions are met: \begin{alignat*}{2} & \exists n\in\mathbb{N}^+. \forall z\in L: |z| \geq n \Rightarrow \exists u,v,w,x,y\in\Sigma^*: && \quad z = uvwxy \\ & && \land |vx| \geq 1 \\ & && \land |vwx| \leq n \\ & && \land \exists i\in\mathbb{N}: uv^iwx^iy\in L \\ \end{alignat*}

Someone I work with provided me with a negated form which I think is not correct: \begin{alignat*}{2} & \forall n\in\mathbb{N}^+. \exists z\in L: |z| \geq n \Rightarrow \exists u,v,w,x,y\in\Sigma^*: && \quad z = uvwxy \\ & && \land |vx| \geq 1 \\ & && \land |vwx| \leq n \\ & && \Rightarrow \exists i\in\mathbb{N}: uv^iwx^iy\not\in L \\ \end{alignat*}

I myself come to the following solution:

\begin{alignat*}{2} & \neg\left(\exists n\in\mathbb{N}^+. \forall z\in L: |z| \geq n \Rightarrow \exists u,v,w,x,y\in\Sigma^*: \right. && \quad z = uvwxy \\ & && \land |vx| \geq 1 \\ & && \land |vwx| \leq n \\ & && \left.{}\land \forall i\in\mathbb{N}: uv^iwx^iy\in L \right) \\ \equiv& \forall n\in\mathbb{N}^+. \exists z\in L: |z| \geq n \land \neg\left(\exists u,v,w,x,y\in\Sigma^*: \right. && \quad z = uvwxy \\ & && \land |vx| \geq 1 \\ & && \land |vwx| \leq n \\ & && \left.{}\land \forall i\in\mathbb{N}: uv^iwx^iy\in L \right) \\ \equiv& \forall n\in\mathbb{N}^+. \exists z\in L: |z| \geq n \land \forall u,v,w,x,y\in\Sigma^*: && \neg\left(z = uvwxy \right.\\ & && \land |vx| \geq 1 \\ & && \left.{} \land |vwx| \leq n \right) \\ & && \lor \neg \left(\forall i\in\mathbb{N}: uv^iwx^iy\in L \right) \\ \equiv& \forall n\in\mathbb{N}^+. \exists z\in L: |z| \geq n \land \forall u,v,w,x,y\in\Sigma^*: && \quad z = uvwxy \\ & && \land |vx| \geq 1 \\ & && \land |vwx| \leq n \\ & && \Rightarrow \neg \left(\forall i\in\mathbb{N}: uv^iwx^iy\in L \right) \\ \equiv& \forall n\in\mathbb{N}^+. \exists z\in L: |z| \geq n \land \forall u,v,w,x,y\in\Sigma^*: && \quad z = uvwxy \\ & && \land |vx| \geq 1 \\ & && \land |vwx| \leq n \\ & && \Rightarrow \exists i\in\mathbb{N}: uv^iwx^iy\not\in L \end{alignat*}

Did I make a mistake? I cannot believe both versions are right but the source of the solution I contest I also consider quite reliable.

Thanks for any help and pointers!

Remark. I did not post this in computer-sciences since it doesn't relate to the meaning of the Pumping-Lemma but to it's mathematical definition.

Answer 1

Firstly, your statement of the pumping lemma is wrong! The last quantifier should be universal.

Secondly, both of you are wrong! Next time don't write in that messy inconsistent form; either use brackets or "$:$" or "$.$" consistently. Push the negation in from the front, and systematically use De Morgan's:

$\neg \forall x \in S\ ( \cdots ) \longrightarrow \exists x \in S\ ( \neg \cdots )$

$\neg \exists x \in S\ ( \cdots ) \longrightarrow \forall x \in S\ ( \neg \cdots )$

I have no idea what you were doing once you started having unbalanced brackets. Your statement is of the form: $\def\imp{\to}$ $\def\nn{\mathbb{N}}$

$\exists n\in\mathbb{N}\ \forall z \in L\ ( \cdots \imp \exists u,..,y \in Σ^*\ ( \cdots \land \forall i\in\nn\ ( \cdots ) ) )$

Its negation would hence be:

$\forall n\in\mathbb{N}\ \exists z \in L\ ( \neg ( \cdots \imp \exists u,..,y \in Σ^*\ ( \cdots \land \forall i\in\nn\ ( \cdots ) ) ) )$

$\ \equiv \forall n\in\mathbb{N}\ \exists z \in L\ ( \cdots \land \neg \exists u,..,y \in Σ^*\ ( \cdots \land \forall i\in\nn\ ( \cdots ) ) )$

$\ \equiv \forall n\in\mathbb{N}\ \exists z \in L\ ( \cdots \land \forall u,..,y \in Σ^*\ ( \neg ( \cdots \land \forall i\in\nn\ ( \cdots ) ) ) )$

$\ \equiv \forall n\in\mathbb{N}\ \exists z \in L\ ( \cdots \land \forall u,..,y \in Σ^*\ ( ( \neg \cdots \lor \neg \forall i\in\nn\ ( \cdots ) ) ) )$

$\ \equiv \forall n\in\mathbb{N}\ \exists z \in L\ ( \cdots \land \forall u,..,y \in Σ^*\ ( ( \neg \cdots \lor \exists i\in\nn\ ( \neg \cdots ) ) ) )$

It's actually possible to write the negation down completely intuitively, though I recommend you first learn to do it mechanically. One intuitive way is via game semantics.