목격자(수학)

수학논리학에서 증인은 θ(t)가 참이 되도록 θx θ(x) 형식의 실존 스테이트먼트의 변수 x에 치환되는 특정값 t이다.

예

예를 들어, 산술 이론 T는 "0 = 1" 공식의 T에 증거가 존재한다면 불일치하다고 한다.따라서 T가 부정합임을 나타내는 공식 I(T)는 실존적 공식이다.T의 불일치에 대한 증인은 T에서 "0 = 1"의 특별한 증거이다.

Boolos, Burgess 및 Jeffrey(2002:81)는 다음과 같은 예제를 통해 증인의 개념을 정의한다. 여기서 S는 자연수의 n자리 관계이고 R은 (n+1)자리 재귀 관계이며 ↔는 논리적 등가성을 나타낸다(만 해당).

S(x₁, ..., x_n) ↔ µy R(x₁, ., x, y_n)

R이 X를 보유하는_i y는 X의_i S를 보유하는 관계에 대한 '증인'이라고 할 수 있다(증인이 사람이 아닌 숫자일 경우 증인은 진실만을 증언하는 것으로 이해한다).

이 특별한 예에서 저자들은 s를 (긍정적으로) 재귀적으로 반감정적이거나 단순히 반감정적이라고 정의했다.

헨킨 증인

술어 미적분학에서, 이론 T에서 문장${\displaystyle \mathrm{}x}$ x ${\displaystyle （}$ $）$ {displaystyle $\exists$ x$,\varphi(x)}$의 헨킨 증인은 T가 ((c)를 증명하는 용어 c이다(힌만 2005:196).이러한 증인의 사용은 1949년 레온 헨킨이 제시한 괴델의 완전성 정리를 증명하는 핵심 기법이다.

게임 의미론과의 관계

목격자의 개념은 게임 의미론의 보다 일반적인 개념으로 이어진다.문장${\displaystyle \mathrm{}x}$ ${\displaystyle x}$ ${\displaystyle (}$( x$$) \ $displaystyle$\$exists$ x , \ $varphi ( x$ )의$$ 경우 검증자의 승리 전략은 ${\$ \ $displaystyle$\ $varphi$의 증인을 선택하는 것입니다.유니버설 수량화자와 관련된 보다 복잡한 공식의 경우 검증자를 위한 승리 전략의 존재 여부는 적절한 스콜렘 펑티오의 유무에 달려 있습니다.ns. 예를 들어, S가${\displaystyle \mathrm{}x}$ x${\displaystyle y}$ ${\displaystyle y（}$, y )$${ $displaystyle$ \$forall$x , \$exists$y , \$varphi$(${\displaystyle }$x$$, y ) }를$$ 나타내는 경우, S에 대한 등가성 스테이트먼트는 f${\displaystyle \mathrm{}\mathrm{fx}}$ ${\displaystyle (\mathrm{}}$ ${\displaystyle x}$,${\displaystyle f}$ ) {$displaystyle$\ $exists$ f $, all$x , $varphi ($x $)$입니다$.$스콜렘 함수 f(존재하는 경우)는 가증자가 만들 수 있는 모든 x 선택에 대해 존재론적 하위 공식에 대한 증인을 반환함으로써 실제로 S의 검증자를 위한 승리 전략을 성문화한다.

「 」를 참조해 주세요.

• 증명서(복잡도), 계산 복잡도 이론의 유사한 개념

레퍼런스

• 조지 S.불로스, 존 P.버지스, 그리고 리처드 C.Jeffrey, 2002, Computability and Logic: 케임브리지 대학 출판부 제4판 ISBN0-521-00758-5.
• Leon Henkin, 1949, "1차 함수 미적분의 완전성", Journal of Symbolic Logic v. 14 n. 3, 페이지 159–166.
• 피터 G.Hinman, 2005, 수리논리의 기초, A.K. Peters, ISBN 1-56881-262-0.
• J. Hintikka와 G. Sandu, 2009, Keith Allan (ed.)의 "게임 이론 의미론" 간결한 의미론 백과사전, Elsevier, ISBN 0-08095-968-7, 페이지 341-343