# negating propositional formula with quantifiers

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.

• Off-topic, but reliability in the real-world does not necessarily correspond to mathematical reliability, and technically it's irrelevant to your question. Commented Jul 7, 2016 at 11:11

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.

• Yes, the quantifier was wrong -- but it was just a typo. I use '.' to delimit quantifiers and ':' after these. One can use $\neg a \lor b \equiv a \Rightarrow \neg b$ -- with this I get the same solution as you get, right>
– ljrk
Commented Jul 7, 2016 at 11:18
• I've edited the typo
– ljrk
Commented Jul 7, 2016 at 11:20
• @larkey: Ok your final answer is correct by luck, since your intermediate steps were wrong. Commented Jul 7, 2016 at 11:20
• Oh, it seems that I made even more mistakes re-typing my draft. I hope it's correct now. But at least I know my result is right and it's not equivalent to the provided one.
– ljrk
Commented Jul 7, 2016 at 11:39
• @larkey: Yes I've checked your current version and it should be right. Yes the other one is wrong. Commented Jul 7, 2016 at 11:55