Svědek (matematika) - Witness (mathematics)

v matematická logika, a svědek je konkrétní hodnota t nahradit proměnnou X z existenční prohlášení formuláře ∃X φ(X) takové, že φ(t) je pravda.

Příklady

Například teorie T aritmetiky se říká, že je nekonzistentní, pokud existuje důkaz v T vzorce "0 = 1". Vzorec I (T), který říká, že T je nekonzistentní, je tedy existenční vzorec. Svědek rozporuplnosti T je konkrétní důkaz "0 = 1" v T.

Boolos, Burgess a Jeffrey (2002: 81) definují pojem svědka na příkladu, ve kterém S je n-místný vztah na přirozená čísla, R je (n + 1)-místo rekurzivní vztah, a ↔ označuje logická ekvivalence (pokud a pouze pokud):

S(X₁, ..., X_n) ↔ ∃y R(X₁, . . ., X_n, y)

"A y takhle R chytí X_i lze nazvat „svědkem“ vztahu S držení X_i (za předpokladu, že chápeme, že pokud je svědkem spíše číslo než osoba, svědek pouze dosvědčuje, co je pravda). “

V tomto konkrétním příkladu autoři definovali s být (pozitivně) rekurzivně semidecidovatelnýnebo jednoduše semirekurzivní.

Henkinovi svědci

v predikátový počet, a Henkinův svědek za větu ${ displaystyle existuje x , varphi (x)}$ teoreticky T je období C takhle T dokazuje φ(C) (Hinman 2005: 196). Použití těchto svědků je klíčovou technikou při dokazování Gödelova věta o úplnosti předložený Leon Henkin v roce 1949.

Vztah k herní sémantice

Pojem svědek vede k obecnější myšlence herní sémantika. V případě trestu ${ displaystyle existuje x , varphi (x)}$ vítěznou strategií pro ověřovatele je vybrat si svědka ${ displaystyle varphi}$. Pro složitější vzorce zahrnující univerzální kvantifikátory, existence vítězné strategie pro ověřovatele závisí na existenci vhodné Funkce Skolem. Například pokud S označuje ${ displaystyle forall x , existuje y , varphi (x, y)}$ pak vyrovnatelný prohlášení pro S je ${ displaystyle existuje f , forall x , varphi (x, f (x))}$. Funkce Skolem F (pokud existuje) ve skutečnosti kodifikuje vítěznou strategii pro ověřovatele S vrácením svědka pro existenční podformulář pro každou volbu X padělatel by mohl udělat.

Viz také

• Osvědčení (složitost), analogický koncept v teorii výpočetní složitosti

Reference

• George S. Boolos, John P. Burgess a Richard C. Jeffrey, 2002, Vyčíslitelnost a logika: Čtvrté vydání, Cambridge University Press, ISBN  0-521-00758-5.
• Leon Henkin, 1949, „Úplnost funkčního počtu prvního řádu“, Journal of Symbolic Logic v. 14 n. 3, s. 159–166.
• Peter G. Hinman, 2005, Základy matematické logiky, A.K. Peters, ISBN  1-56881-262-0.
• J. Hintikka and G. Sandu, 2009, „Game-Theoretical Semantics“ in Keith Allan (ed.) Stručná encyklopedie sémantiky, Elsevier, ISBN  0-08095-968-7, str. 341–343