User:IssaRice/Computability and logic/Expresses versus captures
From Machinelearning
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).
Comparing strengths
For the predicate version of expresses/captures, does one imply the other?
It turns out that given a sound theory, "captures" implies "expresses".
However, even for a "nice" theory, the implication in the other direction does not hold. A good example is the provability property for the theory, which takes a Goedel number of a sentence and is true iff that sentence is provable. This property turns out to be expressible but not capturable.
Capturing functions
For functions, it seems like there are at least four different strengths.
- is captured by iff for all (i) if then and (ii) .^{[1]}
- is captured by iff for all , if , then .^{[1]}
- is captured by iff for all (i) if then , and (ii) if then .^{[1]}
- is captured by iff (i) for all , if then , and (ii) we have .^{[1]}
- is captured by iff for all (i) if then , and (ii) if then .^{[2]}
Comparison of usage patterns
Text | "Expresses" | "Captures" |
---|---|---|
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")^{[3]} | |
Boolos, Burgess, Jeffrey (5th ed) | arithmetically defines^{[4]} | defines (for sets), represents (for functions)^{[4]} |
Wikipedia | arithmetically defines, i think this page uses "defines" in the expresses sense (? actually i'm not sure; this sense of "defines" seems different) | this page uses "represents", but I don't think there's a standalone article for the concept |
References
- ↑ ^{1.0} ^{1.1} ^{1.2} ^{1.3} Peter Smith. Godel book, p. 119, 120, 122.
- ↑ Leary and Kristiansen. A Friendly Introduction to Mathematical Logic (2nd ed). p. 121
- ↑ Goldrei. Propositional and Predicate Calculus. p. 137.
- ↑ ^{4.0} ^{4.1} George S. Boolos; John P. Burgess; Richard C. Jeffrey. Computability and Logic (5th ed). p. 199 for "arithmetically defines". p. 207 for "defines".