User:IssaRice/Computability and logic/Expresses versus captures

From Machinelearning
< User:IssaRice
Revision as of 06:17, 7 February 2019 by IssaRice (talk | contribs) (Capturing functions)
Jump to: navigation, search

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.

  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) T \vdash \exists y (\phi(\overline{m}, y) \wedge \forall v(\phi(\overline{m}, v) \to v=y)).[1]
  2. 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)\ne n then T \vdash \neg \phi(\overline m, \overline n).[1]
  3. 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]

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")[2]
Boolos, Burgess, Jeffrey arithmetically defines[3] defines (for sets), represents (for functions)[3]
Wikipedia arithmetically defines this page uses "represents", but I don't think there's a standalone article for the concept

References

  1. 1.0 1.1 1.2 Peter Smith. Godel book, p. 119, 120, 122.
  2. Goldrei. Propositional and Predicate Calculus. p. 137.
  3. 3.0 3.1 George S. Boolos; John P. Burgess; Richard C. Jeffrey. Computability and Logic (5th ed). p. 199 for "arithmetically defines". p. 207 for "defines".