*L*. Let L be a subset of

_{A}*L*and let T be some AFT of arithmetic.

_{A}We say that T is

**L-sound**iff, for any sentence φ in L, if T ⊢ φ, then φ is true.

We say that T is

**L-complete**iff, for any sentence φ in L, if φ is true, then T ⊢ φ.

In chapter 9, Peter Smith defines a subset of

*L*, called Σ

_{A}_{1}. Then, using the fact that Q is order-adequate, he proves that Q is Σ

_{1}-complete. This is important because the well-formed formulas (

**wff**'s) of Σ

_{1 }can express the decidable numerical properties and relations, and therefore Q will be sufficiently strong. Now to the details...

First, let's define a few interesting subsets of

*L*:

_{A}- The set of
**atomic Δ**is the set of wff's of the form σ = τ or σ ≤ τ, where σ and τ are terms of_{0}wff's*L*._{A} - The set of
**Δ**is defined inductively by the following rules:_{0}wff's - Every atomic Δ
_{0}wff is a Δ_{0}wff. - If α and β are Δ
_{0}wff's, then so are ¬α, α ∧ β, α ∨ β, and α → β. - If α is a Δ
_{0}wff, then so are (∀χ ≤ κ) α and (∃χ ≤ κ) α, where χ is any variable that appears free in α and κ is a numeral or a variable that is different from χ (see this post for the definition of these bounded quantifiers). - Nothing else is a Δ
_{0}wff. - A wff is
**strictly Σ**iff it is of the form ∃α∃β...∃ω φ, where φ is Δ_{1}_{0}and α, β, ... , ω are one or more distinct variables that appear free in φ. - A wff is
**Σ**iff it is logically equivalent to a strictly Σ_{1}_{1 }wff. - A wff is
**strictly Π**iff it is of the form ∀α∀β...∀ω φ, where φ is Δ_{1}_{0}and α, β, ... , ω are one or more distinct variables that appear free in φ. - A wff is
**Π**iff it is logically equivalent to a strictly Π_{1}_{1 }wff.

Note that these sets contain not only sentences but also open wff's, that is, wff's with one or more free variables. Here are two examples of Δ

_{0}wff's:
(∃v ≤ x) (2 × v = x)

2 ≤ x ∧ (∀t ≤ x) (∀u ≤ x) (t × u = x → (t = 1 ∨ u = 1))

According to Smith, the set Δ

_{0}is built in such a way that its elements do not contain any (unbounded) universal or existential quantifiers. I find this statement a bit surprising because the atomic Δ_{0}wff of the form σ ≤ τ is really an abbreviation for:
∃v (v + σ = τ)

which

Now, let's consider the following wff:

The interpretation of this open wff is "Every even number greater than 2 is the sum of two primes," which is the famous Goldbach conjecture. Since the sub-formula after the ∀x is a Δ

*does*contain an unbounded existential quantifier. The only reasoning I could come up with to resolve this difficulty is that, to determine the truth value of σ ≤ τ, one only needs to check a finite number of addition facts, because the value of v that works, if it exists, must be less than or equal to the numerical value of τ (which must be a constant number for the truth value of the whole formula to be defined).Now, let's consider the following wff:

∀x ( (e(x) ∧ 4 ≤ x) → (∃y ≤ x) (∃z ≤ x) (p(y) ∧ p(z) ∧ y + z = x) )

The interpretation of this open wff is "Every even number greater than 2 is the sum of two primes," which is the famous Goldbach conjecture. Since the sub-formula after the ∀x is a Δ

_{0}wff, the entire wff is strictly**Π**_{1}. Recall that a strictly**Π**_{1 }wff is a Δ_{0}wff preceded by a single group of one or more (unbounded) universal quantifiers. Similarly, a strictly**Σ**_{1 }wff is a Δ_{0}wff preceded by a single group of one or more (unbounded) existential quantifiers.Second, let's state some simple results:

**Lemma 1:**The negation of a_{0}wff is also Δ_{0}.**Lemma 2:**The negation of a_{1 }wff is Π_{1}and vice versa.**Lemma 3:**A Δ_{0}wff is also both Σ_{1 }and Π_{1}.**Lemma 4:**The function that assigns a truth value to each Δ_{0}wff is effectively computable.

Lemma 2 follows directly from De Morgan's laws for quantifiers, namely:

- ¬∃x φ(x) is logically equivalent to ∀x ¬φ(x)
- ¬∀x φ(x) is logically equivalent to ∃x ¬φ(x)

Proof sketch of Lemma 3:

- Let φ be any Δ
_{0}wff in which the variable z does not appear free. - φ is logically equivalent to both ∀z (φ ∧ z = z) and ∃z (φ ∧ z = z).
- ∃z (φ ∧ z = z) is strictly Σ
_{1}. - ∀z (φ ∧ z = z) is strictly Π
_{1}.

Proof sketch of Lemma 4:

- Computing the truth value of any Δ
_{0}wff takes only a finite number of well-defined steps because: - Each universally or existentially bounded quantified wff can be converted to a finite conjunction or disjunction, respectively.
- As mentioned above, any atomic Δ
_{0}wff using ≤ can be converted to a finite disjunction. - One can use the truth tables of the connectives to compute truth values compositionally.
- This proof can be made rigorous using structural induction, where each atomic wff has a structural complexity of 0 and each connective increments the structural complexity by 1.

Third, we come to the main result of this post:

**Theorem:**Q is Σ

_{1}-complete.

- Q correctly decides every atomic Δ
_{0}sentence: these sentences are either closed equalities or closed inequalities; the first case is already covered in our proof that BA correctly decides all sentences in*L*; the second case also works out because each inequality between terms can be reduced to an inequality between numerals (since each closed term can be reduced to a numeral SSS...S0), which in turn is correctly decided, because Q captures the ≤ relation._{B} - Q correctly decides every Δ
_{0}sentence: we can again use structural induction here - Q proves every true Σ
_{1 }sentence: since each true bounded kernel (that is, every true Δ_{0}sentence) is proved by Q, every true sentence obtained by adding one or more existential quantifiers in front of the kernel is derivable in Q, using the inference rule called existential generalization (or existential introduction).

Finally, let's wrap up this post with a couple of corollaries.

**Corollary 1:**A Π

_{1}sentence φ is true iff ¬φ cannot be derived in Q (i.e., φ is consistent with Q).

Proof sketch:

- If φ is false, then ¬φ is a true Σ
_{1}sentence (by Lemma 2) and thus derivable in Q. - If φ is true, then ¬φ is false and thus not derivable in Q (since Q is sound, because its axioms are true and its inference rules are truth-preserving).

So, if derivability in Q were effectively decidable (we'll see later that it's not), then the function that assigns a truth value to each sentence in Π

Before the next and last corollary, a quick definition:

A theory T

Proof sketch: Assume T extends Q.

_{1}would be effectively computable.Before the next and last corollary, a quick definition:

A theory T

_{2}**extends**a theory T_{1}if:- The language of T
_{1}is a subset of the language of T_{2}, - The wff's common to T
_{1 }and T_{2}have the same truth values in both interpreted languages, and - T
_{2}can prove (at least) all of the theorems of T_{1}.

**Corollary 2:**If a theory T extends Q, then T is consistent iff T is Π

_{1}-sound.

Proof sketch: Assume T extends Q.

- If T is inconsistent, then it can derive everything in T's language, including all of the false Π
_{1}sentences. Therefore, T is not Π_{1}-sound. - If T is not Π
_{1}-sound, then T proves some false Π_{1}sentence φ. Thus, ¬φ is a true Σ_{1}sentence (by Lemma 2) and T must derive ¬φ (since Q being Σ_{1}-complete implies that T is also Σ_{1}-complete). Therefore T is inconsistent (since it derives both φ and ¬φ). By contraposition, if T is consistent, it is Π_{1}-sound.

Nice post. Keep updating

ReplyDeleteArtificial Intelligence Online Training