Quantification in pumping lemma for regular languages

Question

The Wikipedia article on the pumping lemma states:

We now pump $y$ up: $xy^2z$ has more instances of the letter $a$ than the letter $b$, since we have added some instances of $a$ without adding instances of $b$. Therefore, $xy^2z$ is not in $L$. We have reached a contradiction. Therefore, the assumption that $L$ is regular must be incorrect. Hence $L$ is not regular.

But this formal version of the lemma seems to differ: $$ \begin{align*} &(\forall L \subseteq \Sigma^*) \\ &\quad (\text{regular}(L) \Rightarrow \\ &\quad ((\exists p \geq 1)((\forall w \in L)((|w| \geq p) \Rightarrow \\ &\quad ((\exists x,y,z \in \Sigma^*)(w=xyz \land (|y| \geq 1 \land |xy| \leq p \land (\forall i \geq 0)(xy^iz \in L)))))))) \end{align*} $$ I thought there only has to "exist a combination of $x,y,z$" in order to be regular (as stated in this answer as well).

As far as I can see, the Wikipedia example only takes a look at one possible combination/example. Am I missing something obvious here?

Answer 1

You are right that the pumping lemma requires only some $x,y,z$ to exist, for every string whose length is greater than the pumping length, that satisfy the three conditions. However, when you attempt to show that a language is not regular, you use the method of contradiction, which makes use of the negation of the consequent of the implication in the pumping lemma.

The pumping lemma states that

If a language $L$ is regular, then there exists $p\gt 0$ such that for all strings $s\in L$ such that $|s|\ge p$, there exists a way to split $s$ in the form $x,y,z$ such that all of the following conditions hold:

1. $xy^iz\in L$ for all $i\ge 0$
2. $|y|\gt 0$
3. $|xy|\le p$

Let $p$ be the statement: The language $L$ is regular.

Let $q$ be the statement: Given a language $L$, there exists $p\gt 0$ such that for all strings $s\in L$ such that $|s|\ge p$, there exists a way to split $s$ in the form $x,y,z$ such that all of the following conditions hold:

1. $xy^iz\in L$ for all $i\ge 0$
2. $|y|\gt 0$
3. $|xy|\le p$

The pumping lemma states that $p\implies q$.

---

To show that a language $L$ is not regular using the pumping lemma, you first assume that $L$ is regular, i.e., $p$ is true.

Then, you try to show that $\neg q$ is true. From the pumping lemma, as $p\implies q$, the contrapositive $\neg q\implies \neg p$ also holds. So, if you can show that $\neg q$ is true, it implies that $\neg p$ is true. From the assumption that $p$ is true, we have both $p$ and $\neg p$ to be true, which is a contradiction.

Now, let's see what is $\neg q$. We need to negate the statement $q$, which gives, $\neg q$:

Given a language $L$, for all $p\gt 0$, there exists string $s\in L$ such that $|s|\ge p$, and for all ways to split $s$ in the form $x,y,z$, at least one of the following conditions don't hold:

1. $xy^iz\in L$ for all $i\ge 0$
2. $|y|\gt 0$
3. $|xy|\le p$

Now, you can see from here, that in the negation, the statement must be true irrespective of how you split $s$ into $x,y,z$. So, for any arbitrary $p$, if you can find any one string $s$ such that for every way to split it in the form $x,y,z$, at least one of the three conditions are false, it implies that the language is not regular.

The only place where "one possible example" has been used is in the choice of $s$, which is correct as you can see from the statement. No assumption has been made in how $s$ splits into $x,y,z$, and yet, it has been shown that at least one of the conditions becomes false. So, for a given $s$, all $x,y,z$ have been indeed considered.

It may appear that the $|y|\gt 0$ and $|xy|\le p$ make the choice of $x,y,z$ a specific choice, however, this must be true if conditions 2. and 3. are to be true - if they were not, we trivially reach a contradiction as we need only any one of the three conditions (at least) to be false.