User:IssaRice/Computability and logic/Expresses versus captures: Difference between revisions

Revision as of 03:10, 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.

$f$ is captured by $\phi (x,y)$ iff for all $m,n$ (i) if $f(m)=n$ then $T\vdash \phi ({\overline {m}},{\overline {n}})$ and (ii) $T\vdash \exists y(\phi ({\overline {m}},y)\wedge \forall v(\phi ({\overline {m}},v)\to v=y))$ .^[1]
$f$ is captured by $\phi (x,y)$ iff for all $m,n$ , if $f(m)=n$ , then $T\vdash \forall y(\phi ({\overline {m}},y)\leftrightarrow y={\overline {n}})$ .^[1]
$f$ is captured by $\phi (x,y)$ iff for all $m,n$ (i) if $f(m)=n$ then $T\vdash \phi ({\overline {m}},{\overline {n}})$ , and (ii) if $f(m)\neq n$ then $T\vdash \neg \phi ({\overline {m}},{\overline {n}})$ .^[1]
$f$ is captured by $\phi (x,y)$ iff (i) for all $m,n$ , if $f(m)=n$ then $T\vdash \phi ({\overline {m}},{\overline {n}})$ , and (ii) we have $T\vdash \forall x\exists y(\phi (x,y)\wedge \forall v(\phi (x,v)\to v=y))$ .^[1]
$f$ is captured by $\phi (x,y)$ iff for all $m,n$ (i) if $f(m)=n$ then $T\vdash \phi ({\overline {m}},{\overline {n}})$ , and (ii) if $f(m)\neq n$ then $T\nvdash \phi ({\overline {m}},{\overline {n}})$ .^[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	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".

[smith-1] 1.0 ^1.1 ^1.2 ^1.3 Peter Smith. Godel book, p. 119, 120, 122.

[2] Leary and Kristiansen. A Friendly Introduction to Mathematical Logic (2nd ed). p. 121

[3] Goldrei. Propositional and Predicate Calculus. p. 137.

[boolos-4] 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".

[1]

[2]

[3]

[4]

@@ Line 26: / Line 26: @@
 | Goldrei || defines (but the book also uses "represents")<ref>Goldrei. ''Propositional and Predicate Calculus''. p. 137.</ref> ||
 |-
-| Boolos, Burgess, Jeffrey || 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