   # 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. Selmer Bringsjord
Tue Apr 23 08:32:51 EDT 1996