Tanık (matematik) - Witness (mathematics)

İçinde matematiksel mantık, bir şahit belirli bir değerdir t değişken yerine ikame edilecek x bir varoluşsal ifade formun ∃x φ(x) öyle ki φ(t) doğru.

Örnekler

Örneğin bir teori T aritmetiğin tutarsız olduğu söylenir. T "0 = 1" formülünün. Formül I (T) diyor ki T tutarsızdır, dolayısıyla varoluşsal bir formüldür. Tutarsızlığına tanık T "0 = 1" in belirli bir kanıtıdır. T.

Boolos, Burgess ve Jeffrey (2002: 81) tanık nosyonunu örnekle tanımlarlar. S bir n-doğal sayılarda yer ilişkisi, R bir (n + 1)-yer yinelemeli ilişki ve ↔, mantıksal eşdeğerlik (ancak ve ancak):

S(x₁, ..., x_n) ↔ ∃y R(x₁, . . ., x_n, y)

"A y öyle ki R ... x_ben ilişkiye 'tanık' denebilir S tutmak x_ben (tanığın bir kişiden ziyade bir sayı olması durumunda, bir tanığın yalnızca doğru olana tanıklık ettiğini anlamamız şartıyla). "

Bu özel örnekte yazarlar, s olmak (pozitif olarak) özyinelemeli olarak yarı iletken, ya da sadece yarı hedefli.

Henkin tanıkları

İçinde yüklem hesabı, bir Henkin tanık bir cümle için ${ displaystyle vardır x , varphi (x)}$ bir teoride T bir dönem c öyle ki T kanıtlar φ(c) (Hinman 2005: 196). Bu tür tanıkların kullanılması, kanıtlamada anahtar bir tekniktir. Gödel'in tamlık teoremi tarafından sunulan Leon Henkin 1949'da.

Oyun semantiğiyle ilişki

Tanık kavramı, daha genel bir fikre götürür. oyun semantiği. Cümle durumunda ${ displaystyle vardır x , varphi (x)}$ doğrulayıcı için kazanan strateji, bir tanık seçmektir. ${ displaystyle varphi}$. Daha karmaşık formüller için evrensel niceleyiciler doğrulayıcı için kazanan bir stratejinin varlığı, uygun olanın varlığına bağlıdır. Skolem fonksiyonları. Örneğin, eğer S gösterir ${ displaystyle forall x , vardır y , varphi (x, y)}$ sonra bir eşitlenebilir için açıklama S dır-dir ${ displaystyle vardır f , forall x , varphi (x, f (x))}$. Skolem işlevi f (eğer varsa) aslında doğrulayıcı için kazanan bir stratejiyi kodlar S her seçim için varoluşsal alt formül için bir tanık döndürerek x sahtekar yapabilir.

Ayrıca bakınız

• Sertifika (karmaşıklık), hesaplama karmaşıklığı teorisinde benzer bir kavram

Referanslar

• George S. Boolos, John P. Burgess ve Richard C. Jeffrey, 2002, Hesaplanabilirlik ve Mantık: Dördüncü Baskı, Cambridge University Press, ISBN  0-521-00758-5.
• Leon Henkin, 1949, "Birinci dereceden fonksiyonel analizin bütünlüğü", Journal of Symbolic Logic v. 14 n. 3, sayfa 159–166.
• Peter G. Hinman, 2005, Matematiksel mantığın temelleri, A.K. Peters, ISBN  1-56881-262-0.
• J. Hintikka ve G. Sandu, 2009, "Oyun-Teorik Anlambilim", Keith Allan (ed.) Kısa Anlambilim Ansiklopedisi, Elsevier, ISBN  0-08095-968-7, s. 341–343