User:IssaRice/Computability and logic/Expresses versus captures
The expresses versus captures distinction is an important one in mathematical logic, but unfortunately the terminology differs wildly between different texts. The following table gives a comparison.
- Expressing is done by a language. There is only one form of expressing; I think this follows from the wikipedia:Law of excluded middle.
- Capturing is done by a theory or by axioms. There are two forms of capturing: strong capture (corresponding to deciding), and weak capture (corresponding to recognizing, or semi-deciding).
For functions, it seems like there are at least four different strengths.
- is captured by iff for all (i) if then and (ii) .
- is captured by iff for all (i) if then , and (ii) if then .
- is captured by iff (i) for all , if then , and (ii) we have .
Comparison of usage patterns
|Peter Smith. Godel book (see especially footnote 9 on p. 45)||expresses||captures|
|Leary & Kristiansen||defines||represents|
|Goldrei||defines (but the book also uses "represents")|
|Boolos, Burgess, Jeffrey||arithmetically defines||defines (for sets), represents (for functions)|
|Wikipedia||arithmetically defines||this page uses "represents", but I don't think there's a standalone article for the concept|
- Peter Smith. Godel book, p. 119, 120, 122.
- Goldrei. Propositional and Predicate Calculus. p. 137.
- George S. Boolos; John P. Burgess; Richard C. Jeffrey. Computability and Logic (5th ed). p. 199 for "arithmetically defines". p. 207 for "defines".