теорема Геделя о неполноте
... теорема утверждает, что если формальная арифметика непротиворечива, то в ней существует невыводимая и неопровержимая формула.
http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%93%D1%91%D0%B4%D0%B5%D0%BB%D1%8F_%D0%BE_%D0%BD%D0%B5%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D1%82%D0%B5
[Spoiler (click to open)]Связь с парадоксами
В стандартной интерпретации гёделева неразрешимая формула A означает «не существует вывода формулы A», то есть утверждает свою собственную невыводимость в системе S. Таким образом, A является аналогом парадокса лжеца. Рассуждения Гёделя в целом очень похожи на парадокс Ришара. Более того, для доказательства существования невыводимых утверждений может быть использован любой семантический парадокс.
Следует отметить, что выражаемое формулой A утверждение не содержит порочного круга, поскольку изначально утверждается только, что некоторая конкретная формула, явную запись которой получить несложно (хоть и громоздко), недоказуема. «Только впоследствии (и, так сказать, по воле случая) оказывается, что эта формула в точности та, которой выражено само это утверждение».
Эту теорему считают решением второй проблемы Гильберта о притиворечивости аксиом арифметики. Ответ звучит так:
непротиворечивость аксиом арифметики нельзя доказать, исходя из самих аксиом арифметики (если только арифметика не является на самом деле противоречивой)
http://ru.wikipedia.org/wiki/%D0%92%D1%82%D0%BE%D1%80%D0%B0%D1%8F_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D0%93%D0%B8%D0%BB%D1%8C%D0%B1%D0%B5%D1%80%D1%82%D0%B0
http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%93%D1%91%D0%B4%D0%B5%D0%BB%D1%8F_%D0%BE_%D0%BD%D0%B5%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D1%82%D0%B5
[Spoiler (click to open)]Связь с парадоксами
В стандартной интерпретации гёделева неразрешимая формула A означает «не существует вывода формулы A», то есть утверждает свою собственную невыводимость в системе S. Таким образом, A является аналогом парадокса лжеца. Рассуждения Гёделя в целом очень похожи на парадокс Ришара. Более того, для доказательства существования невыводимых утверждений может быть использован любой семантический парадокс.
Следует отметить, что выражаемое формулой A утверждение не содержит порочного круга, поскольку изначально утверждается только, что некоторая конкретная формула, явную запись которой получить несложно (хоть и громоздко), недоказуема. «Только впоследствии (и, так сказать, по воле случая) оказывается, что эта формула в точности та, которой выражено само это утверждение».
Эту теорему считают решением второй проблемы Гильберта о притиворечивости аксиом арифметики. Ответ звучит так:
непротиворечивость аксиом арифметики нельзя доказать, исходя из самих аксиом арифметики (если только арифметика не является на самом деле противоречивой)
http://ru.wikipedia.org/wiki/%D0%92%D1%82%D0%BE%D1%80%D0%B0%D1%8F_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D0%93%D0%B8%D0%BB%D1%8C%D0%B1%D0%B5%D1%80%D1%82%D0%B0