Expressibility within the Theory

I could use this topic for most of the rest of the semester.

We express facts, properties, and relations using formulas. Therefore, if we want to prove anything about expressibility, we will need to use induction on formulas. For the atomic formulas, we need facts about terms. Thus, each result will rely on a lemma on terms.

We already proved the main lemma on terms last time: Lemma 33B stated that for any term, we can prove it equal to a (unique) canonical term.

Theorem 33C. For every quantifier-free sentence %$\tau$% true in %$\mathfrak N$%, %$A_{E}\vdash\tau$%, that is, we can derive %$\taue$%$ from our theory.

Our seemingly weak theory is sufficiently strong to answer every quantifier-free question about the natural numbers.

Proof. HOMEWORK. The proof is, of course, by induction on the formation of quantifier-free formulas, and so the cases are

• Atomic
  • %$t_{1}=t_{2}$%
  • %$t_{1}<t_{2}$%
• Negation
• Conditional

To complete the atomic case, we use Lemma 33B.

NOTE. You can "never" prove a conditional by induction. Thus, we cannot prove, by induction that if %$\mathfrak{N}\vDash\tau$% then %$A_{E}\vdash\tau$%. We need to prove instead something stronger, roughly a biconditional of which what we want is half.

So, we need to prove, roughly, that %$\mathfrak{N}\vDash\tau$% if and only if %$A_{E}\vdash\tau$%. That biconditional involves something not being provable, which is difficult notion, and so we strengthen a bit more:

if %$\mathfrak{N}\vDash\tau$% then %$A_{E}\vdash\tau$%, and
if %$\mathfrak{N}\not\vDash\tau$% then %$A_{E}\vdash\lnot\tau$%

Definition. A formula is an existential ( universal ) formula if it is a quantifier-free formula with zero or more existential (universal) quantifiers on the front.

Corollary 33D. Every existential sentence true in %$\mathfrak{N}$% is a consequence of %$A_E$%.

The corresponding result for universal formulas is false, as we shall prove later in the semester.

Proof. If %$\tau$% is %$\exists x_{1}\cdots\exists x_{n}\theta$% and %$\tau$% is true, then %$\theta (S^{m_1},\dotsc ,S^{m_k})$% is a true quantifier-free sentence, for suitable %$m_{1},\dotsc ,m_{k}$%. That formula is a consequence of %$A_E$% by the theorem and %$\tau$%$ follows from it. %$\qed%^

-- ShaughanLavine - 13 Feb 2008

• Set #DENSITY = 232
• Set #SIZE = +