next up previous
Next: About this document

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

Symbolic Logic; April 23

Selmer Bringsjord

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



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

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