deep-econom (deep_econom) wrote,
deep-econom
deep_econom

Category:

теория моделей, полнота, гедель

---------
Теорема Гёделя о неполноте.
Владимир Андреевич Успенский
М.: Наука, 1982. 110 с.
Тираж 100000 экз.
Серия Популярные лекции по математике, выпуск 57

В § 4 описывается язык формальной арифметики, дается точное определение понятия истинности утверждения этого языка и точная формулировка теоремы Гёделя о неполноте для формальной арифметики.
В § 5 на основе дальнейшего развития тех представлений об алгоритмах, которые были описаны в § 2,— развития, закрепляемого в виде трех аксиом теории алгоритмов, — завершается доказательство теоремы о неполноте формальной арифметики.
https://math.ru/lib/plm/57

--------------------
Теорема 1.2.7. (Теорема о полноте.) ⊢φ тогда и только тогда,
когда ⊨φ; иными словами, высказывание является тавтологией
тогда и только тогда, когда оно истинно.
стр.21. Кейслер...

---
Г. Кейслер, Ч. Ч. Чэн
ТЕОРИЯ МОДЕЛЕЙ
изд. Мир, 1977
обозначим КЧТМ=(Кейслер, Чэн, Теория Моделей)
---



1.2.13. Теория Г называется полной, если для всякого
высказывания φ справедливо в точности одно из двух: Г ⊨ φ или
Г ⊨ ¬φ. Для любого множества высказываний Σ равносильны
следующие утверждения:
(i) Множество всех следствий высказываний из Σ является
максимальным непротиворечивым.
(ϋ) Σ — полная теория.
(iii) Σ имеет точно одну модель.
(iv) Существует такая модель А, что для всякого
высказывания φ формулы Σ ⊨ φ и A ⊨ φ верны или неверны
одновременно.

стр.31 Кейслер
--------------

стр.48.

ТЕоремА 1.3.20. (Теорема Гёделя о полноте.) Произвольное
предложение языка X является теоремой тогда и только тогда,
когда оно истинно.
Теорема 1.3.21. (Обобщенная теорема о полноте.) Пусть
Σ — произвольное множество предложений', тогда оно
непротиворечиво в том и только том случае, когда оно имеет модель.
-----------
стр.52
Теория Τ называется полной (в языке X), если множество
всех ее следствий является максимальным непротиворечивым.
-------------

Верещагин Н. К., Шень А.
В31 Лекции по математической логике и теории алгоритмов.
Часть 2. Языки и исчисления. — 4-е изд., испр. — М.: МЦНМО,
2012. — 240 c.
ISBN 978-5-4439-0013-1
https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf

стр.147.

Непротиворечивое множество Γ, состоящее из замкнутых формул сигнатуры σ, называется полным в этой сигнатуре, если для
любой замкнутой формулы ϕ этой сигнатуры либо формула ϕ, либо
её отрицание ¬ϕ выводятся из Γ.
Другими словами, теория полна, если из любых двух формул ϕ
и ¬ϕ (соответствующей сигнатуры) ровно одна является теоремой
этой теории.
Полное множество можно получить, взяв какую-либо интерпретацию и рассмотрев все замкутые формулы, истинные в этой интерпретации. (Впоследствии мы увидим, что любое полное множество
может быть получено таким способом — это легко следует из теоремы 46.)
В определении полноты существенно, что мы ограничиваемся замкнутыми формулами той же сигнатуры. Например, если мы возьмём одноместный предикатный символ S, не входящий в Γ, то формулы из Γ про него ничего не утверждают, и потому, скажем, ни
формула ∀x S(x), ни её отрицание не выводимы из Γ. Замкнутость
формулы ϕ тоже важна. Например, множество всех истинных в натуральном ряду формул сигнатуры (=, <) полно, но ни формула
x = y, ни формула x 6= y из него не выводятся, иначе по правилу обобщения мы получили бы ложную в N формулу ∀x∀y (x = y)
или ∀x∀y (x 6= y).

-----------

https://ru.wikipedia.org/wiki/Теорема_Гудстейна

---------

Системой аксиом A в языке первого порядка L называется полной, если для любой
замкнутой формулы ϕ языка L либо сама ϕ, либо её отрицание ¬ϕ выводима из A.
-----

Если фиксировано конечное число схем правил вывода и перечислимое множество аксиом, то множество выводимых предложений теории получается рекурсивно перечислимым. А множество истинных предложений арифметики не то что не перечислимо, а вообще не является арифметическим. Так что не может тут быть никакой "полноты".

Профессор Снэйп
https://dxdy.ru/post155026.html
-------

пусть имеется
конечное множество схем правил вывода
перечислимое множество аксиом
тогда множество выводимых предложений теории будет рекурсивно перечислимым

в тоже время
множество истинных предложений арифметики не является перечислимым
и тем более не является арифметическим
следовательно полноты быть не может
----

Виноградов И.М. — «Математическая энциклопедия. Том 1.
стр.319.
АРИФМЕТИКА ФОРМАЛЬНАЯ, арифметическое исчисление, - логико-математич. исчисление, формализующее элементарную теорию чисел.
...
Формулы в языке А. ф. наз. арифметическими формулами. Постулатами А. ф. являются постулаты предикатов исчисления (классического или интуиционистского в зависимости от того, какая А. ф. рассматривается), аксиомы Пеано ...
и схема аксиом индукции...
...
В А. ф. можно формулировать суждения о конечных множествах. Более того, классич. А. ф. эквивалентна аксиоматической теории множеств Цермело-Френкеля без аксиомы бесконечности: в каждой из этих систем может быть построена модель другой.
...
Это позволяет погружать в А. ф. нек-рые ее расширения, напр. А. ф. с символами для всех примитивно рекурсивных функций и соответствующими дополнительными постулатами. А. ф. удовлетворяет условиям обеих Гёделя теорем о неполноте. В частности, имеются такие полиномы Р, Q от нескольких переменных, что формула ∀ X(Р (Х) ≠ Q(X)) невыводима, хотя и выражает истинное утверждение, а именно непротиворечивость системы А. ф.
...

==========

О непротиворечивости арифметики, теореме Гёделя, etc.
https://dxdy.ru/topic116500-15.html
====

Теорема Гёделя о полноте
https://dxdy.ru/topic38541-15.html
====


Subscribe

  • вобля

    Байден объявил режим ЧС в сфере нацбезопасности из-за России. "Я издал указ о национальной чрезвычайной ситуации в связи с нетипичной и чрезвычайной…

  • (no subject)

    русский американец политолог Злобин жжет ) начнется с нужного места 46м30с Вечер с Владимиром Соловьевым от 14.04.2021…

  • О смысле от автора Чупахин Н. П.

    Есть правильное. Но в целом не туда. --- Чупахин Н. П. Философия ВКС как способ решения проблемы бездорожья и разгильдяйства *Возможности…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic
  • 2 comments