Symbolic Logic; April 23
is one simple formula in which is such that
any interpretation that satifies it is finite:
An n-ary function f is representable in theory T iff there is a formula
such that for all natural numbers
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:
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
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.