Symbolic Logic; April 23

Selmer Bringsjord

- Review Last Class
- The Theorem
- and corollary

- Power of

- The Theorem
- 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 ** R**ecursive 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.

Tue Apr 23 08:32:51 EDT 1996