Chapter 14, 15.1 Overview (Preparing for the ``Shockers")

Symbolic Logic; April 23

Selmer Bringsjord

• Review Last Class
  • The Theorem
    • and corollary
  • Power of
• Chapter 12
  • Part I
  • Part II
  • Part III
• gödel numbering

Here is one simple formula in which is such that any interpretation that satifies it is finite:

Part I

An n-ary function f is representable in theory T iff there is a formula

such that for all natural numbers

IF

THEN

Part II

A function is recursive if and only if it's Recursive.

A function f is Recursive iff it can be obtained from the functions +, , and by means of a finite number of applications of composition and minimization of regular functions.

Successor function s:

Part III

All Recursive functions are representable in Q. (Corollary: All recursive functions are representable in Q.)

E.g., the identity functions id are all representable in Q, because for any

Gödel Numbering

• Tables 15-1 and 15-2
• Any questions?

Skolem-Löwenheim Theorem. If a set of sentences has a model, then it has a model with an enumerable domain.

Proof. Suppose that has a model, i.e. is satisfiable. By Lemma I there is a canonical derivation from . By the soundness theorem, is not a refutation of and so no finite subset of the set of quantifier-free sentences in is unsatisfiable. So is an enumerable O.K. set of sentences.

• About this document ...