\begin{align} v+(-1)v &= (1+(-1))v \\ &= 0v \\ &= 0 \end{align}

As \((-1)v=0\), \((-1)v\) is the additive identity of \(v\) which we defined as \(-v\) \(\blacksquare\).

Key Takeaway: a powerful technique, diagonalization, is doomed to fail at resolving P vs. NP.

Context

Complexity theory is generally the study of impossibilities. This is also an impossibility result. Here are some impossibility results!

1. The reals are uncountable [Cantor 1874]
2. Godel’s incompleteness theorem [Godel 1931]
3. halting problem is undecidable [Turing 1936]
4. time hierarchy theorem [Hartmanis-Stearns 1965] — \(\text{P}\) is a strict subset of \(\text{EXP}\)

Notice! All of these theorems uses a single technique—diagonalization.