Witness (mathematics)
In mathematical logic, a witness is a specific value t to be substituted for variable x of an existential statement of the form ∃x φ(x) such that φ(t) is true.
Examples
For example, a theory T of arithmetic is said to be inconsistent if there exists a proof in T of the formula "0 = 1". The formula I(T), which says that T is inconsistent, is thus an existential formula. A witness for the inconsistency of T is a particular proof of "0 = 1" in T.
Boolos, Burgess, and Jeffrey (2002:81) define the notion of a witness with the example, in which S is an n-place relation on natural numbers, R is an (n+1)-place recursive relation, and ↔ indicates logical equivalence (if and only if):
- S(x1, ..., xn) ↔ ∃y R(x1, . . ., xn, y)
- "A y such that R holds of the xi may be called a 'witness' to the relation S holding of the xi (provided we understand that when the witness is a number rather than a person, a witness only testifies to what is true)."
In this particular example, the authors defined s to be (positively) recursively semidecidable, or simply semirecursive.
Henkin witnesses
In
Relation to game semantics
The notion of witness leads to the more general idea of game semantics. In the case of sentence the winning strategy for the verifier is to pick a witness for . For more complex formulas involving
See also
- Certificate (complexity), an analogous concept in computational complexity theory
References
- George S. Boolos, John P. Burgess, and Richard C. Jeffrey, 2002, Computability and Logic: Fourth Edition, Cambridge University Press, ISBN 0-521-00758-5.
- Leon Henkin, 1949, "The completeness of the first-order functional calculus", Journal of Symbolic Logic v. 14 n. 3, pp. 159–166.
- Peter G. Hinman, 2005, Fundamentals of mathematical logic, A.K. Peters, ISBN 1-56881-262-0.
- ISBN 0-08095-968-7, pp. 341–343