теоремы Гёделя о полноте и неполноте

[nikov]

MaxOpSu в сообщении #246241 писал(а):

Прошу, разъясните для меня, гумманитария, в чем суть и научная значимость этих теорий. Речь о теоремах Гёделя о полноте и, соответственно, неполноте.

Очень хорошее объяснение и доказательство я встречал в книге Верещагина и Шеня "Вычислимые функции" (она бесплатно распостраняется в интернете).

Есть очень наглядная арифметическая переформулировка, основанная на работе Джеймса Джонса Undecidable diophantine equations (http://www.ams.org/bull/1980-03-02/S027 ... 4832-6.pdf):

Цитата:

Для каждой непротиворечивой теории T можно указать такое целое значение параметра K, что уравнение

$$(elg^2 + \alpha - bq^2)^2 + (q - b^{5^{60}})^2 + (\lambda + q^4 - 1 - \lambda b^5)^2 + $$

$$ (\theta + 2z - b^5)^2 + (u + t \theta - l)^2 + (y + m \theta - e)^2 + (n - q^{16})^2 + $$

$$ ((g + eq^3 + lq^5 + (2(e - z \lambda)(1 + g)^4 + \lambda b^5 + \lambda b^5 q^4)q^4)(n^2 - n) + $$

$$ (q^3 - bl + l + \theta \lambda q^3 + (b^5-2)q^5)(n^2 - 1) - r)^2 + $$

$$ (p - 2w s^2 r^2 n^2)^2 + (p^2 k^2 - k^2 + 1 - \tau^2)^2 + $$

$$ (4(c - ksn^2)^2 + \eta - k^2)^2 + (r + 1 + hp - h - k)^2 + $$

$$ (a - (wn^2 + 1)rsn^2)^2 + (2r + 1 + \phi - c)^2 + $$

$$ (bw + ca - 2c + 4\alpha \gamma - 5\gamma - d)^2 + $$

$$ ((a^2 - 1)c^2 + 1 - d^2)^2 + ((a^2 - 1)i^2c^4 + 1 - f^2)^2 + $$

$$ (((a + f^2(d^2 - a))^2 - 1) (2r + 1 + jc)^2 + 1 - (d + of)^2)^2 + $$

$$ (((z+u+y)^2+u)^2 + y-K)^2 = 0$$

не имеет решений в неотрицательных целых числах, но этот факт не может быть доказан в теории T. Более того, для каждой непротиворечивой теории множество значений параметра K, обладающих таким свойством бесконечно и алгоритмически неперечислимо.