# 4.2: Complexity of Formulas

- Page ID
- 9701

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

We work in the language of number theory

\[\mathcal{L}_{NT} = \{ 0, S, +, \cdot, E, < \},\]

and we will continue to work in this language for the next few chapters. \(\mathfrak{N}\) is the standard model of the natural numbers,

\[\mathfrak{N} = \left( \mathbb{N}, 0, S, +, \cdot, E, < \right),\]

where the functions and relations are the usual functions and relations that you have known since you were knee high to a grasshopper. \(E\) is exponentiation, which will usually be written \(x^y\) rather than \(Exy\) or \(xEy\).

One way to think about the simplest formulas of the language of the natural numbers (of any language, really) are the formulas that do not involve any quantifiers. It does seem natural that the formula \(S0 = y\) is simpler than \(\forall x S 0 = y\). One baby step more complicated than quantifier-free formulas are the formulas that contain what we will call bounded quantifiers:

If \(x\) is a variable that does not occur in the term \(t\), let us agree to use the following abbreviations:

\[ \left( \forall x < t \right) \phi \: \text{means} \: \forall x \left( x < t \rightarrow \phi \right) \\ \left( \forall x \leq t \right) \phi \: \text{means} \: \forall x \left( \left( x < t \lor x = t \right) \rightarrow \phi \right) \\ \left( \exists x < t \right) \phi \: \text{means} \: \exists x \left( x < t \land \phi \right) \\ \left( \exists x \leq t \right) \phi \: \text{means} \: \exists x \left( \left( x < t \lor x = t \right) \land \phi \right).\]

These abbreviations will constitute the set of **bounded quantifiers**.

Thus, the formula \(\exists x \left( \left( \forall y < \overline{42} \right) y = Sx \right)\) is a formula with one bounded quantifier and one unbounded quantifier.

Remember that our goal is to produce a sentence that is true in \(\mathfrak{N}\) and not provable from our set of axioms. Might we be able to find such a formula that only contains bounded quantifiers? That would be really great, but unfortunately it is not going to happen. Recall our set of axioms \(N\), back in Section 2.8? If you go back to that section you will see that all of these axioms are true statements about the natural numbers, so they should be a consequence of any potential set of axioms for \(Th \left( \mathfrak{N} \right)\). But \(N\) is actually a pretty strong collection of statements. In particular, \(N\) is robust enough to prove every true statement about \(\mathfrak{N}\) that contains only bounded quantifiers. Even better, \(N\) can refute every false statement that contains only bounded quantifiers. We'll prove this fact in Proposition 5.3.14. Since any potential candidate for an axiomatization of \(\mathfrak{N}\) must be at least as strong as \(N\), this tells us that our quest for a formula that is both true in \(\mathfrak{N}\) and not provable must look at formulas that contain at least some unbounded quantifiers.

The collection of **\(\Sigma\)-formulas** is defined as the smallest set of \(\mathcal{L}_{NT}\)-formulas such that:

- Every atomic formula is a \(\Sigma\)-formula.
- Every negation of an atomic formula is a \(\Sigma\)-formula.
- If \(\alpha\) and \(\beta\) are \(\Sigma\)-formulas, then \(\alpha \land \beta\) and \(\alpha \lor \beta\) are both \(\Sigma\)-formulas.
- If \(\alpha\) is a \(\Sigma\)-formula, and \(x\) is a variable that does not occur in the term \(t\), then the following are \(\Sigma\)-formulas: \(\left( \forall x < t \right) \alpha\), \(\left( \forall x \leq t \right) \alpha\), \(\left( \exists x < t \right) \alpha\), \(\left( \exists x \leq t \right) \alpha\).
- If \(\alpha\) is a \(\Sigma\)-formula and \(x\) is a variable, then \(\left( \exists x \right) \alpha\) is a \(\Sigma\)-formula.

We will prove later (Theorem 5.3.13) that in fact our set of axioms \(N\) is strong enough to prove every true \(\Sigma\)-sentence, so even these formulas are not complicated enough to establish Gödel's incompleteness result. However, if instead of allowing an unbounded existential quantifier, we allow an unbounded universal quantifier, the situation is different.

The collection of **\(\Pi\)-formulas** is the smallest set of \(\mathcal{L}_{NT}\)-formulas such that:

- Every atomic formula is a \(\Pi\)-formula.
- Every negation of an atomic formula is a \(\Pi\)-formula.
- If \(\alpha\) and \(\beta\) are \(\Pi\)-formulas, then \(\alpha \land \beta\) and \(\alpha \lor \beta\) are both \(\Pi\)-formulas.
- If \(\alpha\) is a \(\Pi\)-formula, and \(x\) is a variable that does not occur in the term \(t\), then the following are \(\Pi\)-formulas: \(\left( \forall x < t \right) \alpha\), \(\left( \forall x \leq t \right) \alpha\), \(\left( \exists x < t \right) \alpha\), \(\left( \exists x \leq t \right) \alpha\).
- If \(\alpha\) is a \(\Pi\)-formula and \(x\) is a variable, then \(\left( \forall x \right) \alpha\) is a \(\Pi\)-formula.

So, while the set of \(\Sigma\)-formulas is closed under bounded quantification and unbounded existential quantification, the collection of \(\Pi\)-formulas is closed under bounded quantification and unbounded universal quantification.

The major result of the rest of the book, Gödel's First Incompleteness Theorem, states that if we are given any consistent and decidable set of axioms, then there will be a \(\Pi\)-formula \(\sigma\) such that \(\sigma\) is a true statement about the natural numbers but there is no deduction from our axioms of the formula \(\sigma\). So our set of axioms must be incomplete. Getting to that theorem will occupy us for the rest of our time together.

You might notice that every denial of a \(\Sigma\)-formula is logically equivalent to a \(\Pi\)-formula, and vice versa (see Exercise 3). If we take the intersection of the collection of \(\Sigma\)-formulas and the collection of \(\Pi\)-formulas, we have the \(\Delta\)-formulas:

The collection of **\(\Delta\)-formulas** is the intersection of the collection of \(\Sigma\)-formulas with the set of \(\Pi\)-formulas.

Thus in every \(\Delta\)-formula all quantifiers are bounded. It will turn out that our mysterious (well, it isn't really that mysterious) set of axioms \(N\) is strong enough to prove every true-in-\(\mathfrak{N}\) \(\Delta\)-formula and refute every false-in-\(\mathfrak{N}\) \(\Delta\)-formula. This will be very important to us.

## Exercises

- Referring to Definition 4.2.2, explain in detail why the following formulas are (or are not) \(\Sigma\)-formulas.

(a) \(S0 + S0 = SS0\)

(b) \(\neg \left( 0 < 0 \lor 0 < S0 \right)\)

(c) \(\left( \forall x < \overline{17} \right) x < \overline{17}\)

(d) \(S0 \cdot S0 = S0 \land \left( \exists y < x \right) \left( \exists z < y \right) y + z = x\)

(e) \(\left( \forall y \right) \left( y < 0 \rightarrow 0 = 0 \right)\)

(f) \(\left( \exists x \right) \left( x < x \right)\) - Let's define the set of Cool Formulas to be the smallest set of \(\mathcal{L}_{NT}\)-formulas that:

(a) Contains all atomic formulas.

(b) Contains all negations of atomic formulas.

(c) Is closed under the connectives \(\land\) and \(\lor\).

(d) Is closed under bounded quantifiers and the quantifier \(\exists\)

Prove that a formula is Cool if and only if the formula is a \(\Sigma\)-formula. (The four conditions above are sometimes used to define the set of \(\Sigma\)-formulas. You've just proved that the definition here is equivalent to Definition 4.2.2.) - Think about the \(\Sigma\)-formula

\[\alpha \: \text{is} \: x< y \lor \left( \forall z < w \right) x + \overline{17} = \overline{42}.\]

(a) Is \(\alpha\) a \(\Pi\)-formula?

(b) Is \(\neg \alpha\) a \(\Pi\)-formula?

(c) Can you find a \(\Pi\)-formula that is equivalent to \(\neg \alpha\)?

(d) Carefully prove that, if \(\alpha\) is any \(\Sigma\)-formula, then \(\neg \alpha\) is logically equivalent to a \(\Pi\)-formula.