0.1 Definable sets and functions
0.1.1 Definability In Model Theory
Then we write to denote . We say that is -definable. More generally if is some set and , and there is some from so that is -definable then we say that is -definable.
In particular we say that a set is -definable or zero definable iff it is the solution set of some formula without parameters.
A set or function is definable iff it is -definable for some parameters .
Some authors use the term definable to mean what we have called -definable here. If this is the convention of a paper, then the term parameter definable will refer to sets that are definable over some parameters.
0.1.2 Definability of functions in Proof Theory
In proof theory, given a theory in the language , for a function to be definable in the theory , we have two conditions:
(i) There is a formula in the language s.t. is definable over the model , as in the above definition; i.e., its graph is definable in the language over the model , by some formula .
(ii) The theory proves that is indeed a function, that is .
For example: the graph of exponentiation function is definable by the language of the theory (a subsystem of PA, with induction axiom restricted to bounded formulas only), however the function itself is not definable in this theory.
|Date of creation||2013-03-22 13:26:52|
|Last modified on||2013-03-22 13:26:52|
|Last modified by||CWoo (3771)|