Проблема с перечислением формул

Question

Позволять $P_0, P_1, P_2, ...$ быть перечислением всех логических формул с одной свободной переменной $n$(счетные, поскольку они - конечные строки счетного алфавита). Позволять$Q(n) \iff \lnot P_n(n)$. Для любой$n$, $Q$ не является $P_n$ потому что они не согласны $n$. Но$Q$это логическая формула, поэтому она должна быть в перечислении ...

Что происходит?

Answer 1

Это сводится к следующему: каково точное определение «логической формулы»? Дело в том, что хотя$Q$ вы описали, безусловно, "значимый", он в определенном смысле сложнее, чем любой из $P_i$с. Когда мы определяем точное понятие «логической формулы» и их перечисление, например, «формула первого порядка на языке арифметики», упорядоченная лексикографически посредством некоторого разумного упорядочивания задействованных символов, соответствующие$Q$ окажется, что формула не может выразить в этом конкретном смысле.

Конкретный пример того, как это происходит, см., Например, в теореме Тарского о неопределенности . И сравните это с подобными «парадоксами выражения»: парадоксом Берри, парадоксом Ричарда и парадоксом Греллинга.

Answer 2

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

См. Следующее:

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