В математической логике , А свидетель является значение , удельной т быть заменена переменной х из в экзистенциальном заявлении вида ∃ х φ ( х ) такого , что φ ( т ) истинно.
Примеры
Например, теория арифметики T называется несовместимой, если в T существует доказательство формулы «0 = 1». Таким образом, формула I ( T ), которая утверждает, что T несовместима, является экзистенциальной формулой. Свидетель за несогласованности T является частным доказательством «0 = 1» в Т .
Булос, Берджесс и Джеффри (2002: 81) определяют понятие свидетеля на примере, в котором S - это n- местное отношение натуральных чисел, R - (n + 1) -местное рекурсивное отношение , а ↔ указывает логическая эквивалентность (если и только если):
- S ( x 1 , ..., x n ) ↔ ∃ y R ( x 1 , ..., x n , y )
- «А у такого , что R трюмы х я могу быть назван„свидетелем“в отношении S проведения х я ( при условии , мы понимаем , что если свидетель является числом , а не человек, свидетелем только свидетельствует тому , что правда)."
В этом конкретном примере авторы определили s как (положительно) рекурсивно полуразрешимый или просто полурекурсивный .
Свидетели Хенкина
В исчислении предикатов , в свидетельство Хенкин для предложенияв теории T - это такой член c , что T доказывает φ ( c ) (Hinman 2005: 196). Использование таких свидетелей - ключевой прием в доказательстве теоремы Гёделя о полноте, представленной Леоном Хенкиным в 1949 году.
Отношение к семантике игры
Понятие свидетеля приводит к более общему представлению о семантике игры . В случае приговора выигрышная стратегия для проверяющего - выбрать свидетеля для . Для более сложных формул, включающих универсальные кванторы , наличие выигрышной стратегии для верификатора зависит от наличия соответствующих функций Сколема . Например, если S обозначаетто равно выполнимое утверждение для S есть. Функция Сколема f (если она существует) фактически кодирует выигрышную стратегию для проверяющего S , возвращая свидетельство экзистенциальной подформулы для каждого выбора x, который может сделать фальсификатор.
Смотрите также
- Сертификат (сложность) , аналогичное понятие в теории вычислительной сложности
Рекомендации
- Джордж С. Булос, Джон П. Берджесс и Ричард С. Джеффри, 2002 г., Вычислимость и логика: четвертое издание , Cambridge University Press, ISBN 0-521-00758-5 .
- Леон Хенкин, 1949, "Полнота функционального исчисления первого порядка", Journal of Symbolic Logic v. 14 n. 3. С. 159–166.
- Питер Г. Хинман, 2005 г., Основы математической логики , А.К. Петерс, ISBN 1-56881-262-0 .
- Дж. Хинтикка и Г. Санду, 2009 г., «Теоретико-игровая семантика» в Кейт Аллан (ред.) Краткая энциклопедия семантики , Elsevier, ISBN 0-08095-968-7 , стр. 341–343