Difference between revisions of "User:IssaRice/Computability and logic/Expresses versus captures"
From Machinelearning
(→Comparison of usage patterns) |
|||
Line 28: | Line 28: | ||
| Boolos, Burgess, Jeffrey (5th ed) || arithmetically defines<ref name="boolos">George S. Boolos; John P. Burgess; Richard C. Jeffrey. ''Computability and Logic'' (5th ed). p. 199 for "arithmetically defines". p. 207 for "defines".</ref> || defines (for sets), represents (for functions)<ref name="boolos"/> | | Boolos, Burgess, Jeffrey (5th ed) || arithmetically defines<ref name="boolos">George S. Boolos; John P. Burgess; Richard C. Jeffrey. ''Computability and Logic'' (5th ed). p. 199 for "arithmetically defines". p. 207 for "defines".</ref> || defines (for sets), represents (for functions)<ref name="boolos"/> | ||
|- | |- | ||
− | | Wikipedia || [[wikipedia:Arithmetical set|arithmetically defines]] || [https://en.wikipedia.org/wiki/Diagonal_lemma#Background this page] uses "represents", but I don't think there's a standalone article for the concept | + | | Wikipedia || [[wikipedia:Arithmetical set|arithmetically defines]], i think [https://en.wikipedia.org/wiki/Tarski's_undefinability_theorem#Statement_of_the_theorem this page] uses "defines" in the expresses sense || [https://en.wikipedia.org/wiki/Diagonal_lemma#Background this page] uses "represents", but I don't think there's a standalone article for the concept |
|} | |} | ||
Revision as of 05:38, 11 February 2019
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).
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 | 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".