Теорема Гёделя о неполноте

[ArshakA]

Насколько я понимаю вторая теорема Гёделя о не полноте утверждает, что
В каждой формальной системе существуют утверждения которые нельзя ни доказать ни опровергнуть.
Но..
Берём некоторую формальную систему описываемую через $n$ аксиом :
$1)...$
$2)...$
...
$n)...$
Составляем список всех утверждений в этой теории (кол-во утверждений в формальной системе счётно). Задаем какой-нибудь порядок (только не по алфавиту ).
(1)Выбрасываем из списка все утверждения истинность или ложность которых можно доказать. (Остаются те самые недоказуемые)
(2)Принимаем первое утверждение в списке истинным.
..Повторяем..
Мы построили новую формальную систему в которой, для каждого утверждения за конечное число шагов можно установить является ли оно истинным или ложным.

[kwakush]

Так может этот процесс никогда и не закончится.

[ArshakA]

Кол-во утверждений счётно
До каждого утверждения истинность которого мы хотим установить мы дойдём за конечное число шагов

[Karan]

Идея контрпримера верная (но с "повторяем" надо разобраться подробнее - повторять просто недостаточно, может быть, в пределе все равно не все утверждения покроются).
Найдите где-нибудь формулировку теоремы Геделя и посмотрите, какие именно требования к формальной системе там предъявляются. Вот тут учебники: post773882.html#p773882

[ArshakA]

Karan в сообщении #1170819 писал(а):

Идея контрпримера верная (но с "повторяем" надо разобраться подробнее - повторять просто недостаточно, может быть, в пределе все равно не все утверждения покроются).

Почему не все?

[Sender]

ArshakA в сообщении #1170814 писал(а):

(1)Выбрасываем из списка все утверждения истинность или ложность которых можно доказать.

А как мы узнаем, можно ли доказать данное утверждение в данной теории?

[ArshakA]

Предполагается что при заданном наборе аксиом мы умеем определять истинно утверждение, ложно или не доказуемо (это уже связанно со спецификой теории)

[Sender]

Ещё раз перечитал стартовое сообщение. Боюсь, ошибка уже в формулировке теоремы...

[ArshakA]

Karan в сообщении #1170819 писал(а):

Найдите где-нибудь формулировку теоремы Геделя и посмотрите, какие именно требования к формальной системе там предъявляются

Наличие элементарной арифметики. И $w$-непротиворечивость. Но в следствие из неё (Теорема Геделя в форме Россера) оставалось только первое требование. Пожалуйста исходная форм. система ($n$ аксиом) содержала арифметику. Контр-пример сохранил силу.

-- 22.11.2016, 14:45 --

Sender
То есть могут существовать формальные системы каждое утверждение в которых либо истинно либо ложно?

-- 22.11.2016, 14:50 --

Sender в сообщении #1170824 писал(а):

Ещё раз перечитал стартовое сообщение. Боюсь, ошибка уже в формулировке теоремы...

Я правильно понял? Вот это

ArshakA в сообщении #1170814 писал(а):

В каждой формальной системе существуют утверждения которые нельзя ни доказать ни опровергнуть.

неверно?

[Sender]

ArshakA в сообщении #1170825 писал(а):

То есть могут существовать формальные системы каждое утверждение в которых либо истинно либо ложно?

Да, например, исчисление высказываний.

[ArshakA]

Окей
Могут ли существовать формальные системы в которых определены $ \mathbb{N}$ $ 0 $ $ 1 $ $ + $ $* $ и при этом каждое утверждение либо истинно либо ложно?

-- 22.11.2016, 15:02 --

Я просто считал, что вторая теорема Гёделя как раз утверждает обратное

[Sender]

ArshakA в сообщении #1170832 писал(а):

Могут ли существовать формальные системы в которых определены $ \mathbb{N}$ $ 0 $ $ 1 $ $ + $ $* $ и при этом каждое утверждение либо истинно либо ложно?

Ну, если вы предъявите такую, почему бы и нет? Не забудьте про

Sender в сообщении #1170822 писал(а):

А как мы узнаем, можно ли доказать данное утверждение в данной теории?

[Karan]

Утверждение не может быть истинно или ложно в теории, а может быть теории доказуемо или опровержимо. Истинность и ложность задаются в интерпретации.

ArshakA в сообщении #1170832 писал(а):

Я просто считал, что вторая теорема Гёделя как раз утверждает обратное

Может, все-таки почитать учебник?

[Sender]

Karan в сообщении #1170839 писал(а):

Утверждение не может быть истинно или ложно в теории, а может быть теории доказуемо или опровержимо. Истинность и ложность задаются в интерпретации.

Ну вот в исчислении высказываний, к примеру, выводимы только тавтологии, тождественно истинные для любой интерпретации.

[Karan]

Sender в сообщении #1170842 писал(а):

Ну вот в исчислении высказываний, к примеру, выводимы только тавтологии, тождественно истинные для любой интерпретации.

Я к тому, что ArshakA безграмотно использует терминологию.

ArshakA в сообщении #1170825 писал(а):

Наличие элементарной арифметики. И $w$-непротиворечивость. Но в следствие из неё (Теорема Геделя в форме Россера) оставалось только первое требование.

Еще рекурсивная перечислимость множества аксиом. Ваша конструкция этого не обеспечивает: множество доказуемых и опровержимых утверждений в общем случае не рекурсивно, а только рекурсивно перечислимо, поэтому мы вообще говоря не можем эффективно найти утверждение с минимальным номером, которое не доказуемо и не опровержимо.