Полная теория

В математической логике теория называется полной, если любая синтаксически корректная замкнутая формула или её отрицание доказуемы в данной теории[1]. Если же существует замкнутая формула ${\displaystyle \varphi }$ такая, что ни ${\displaystyle \varphi }$, ни отрицание ${\displaystyle \varphi }$ не доказуемы в теории ${\displaystyle T}$, то такая теория называется неполной. Замкнутость формулы означает, что она не содержит внешних параметров, а синтаксическая корректность означает соответствие правилам формального языка теории. Под доказуемостью формулы понимается существование последовательности формальных утверждений, каждое из которых либо является аксиомой теории, либо получается по формальным правилам вывода из предыдущих утверждений, причём последнее утверждение в последовательности совпадает с доказываемой формулой.

Неформально говоря, теория полна, если любое корректно сформулированное утверждение в ней можно доказать или опровергнуть. Так, в классической логике любая противоречивая теория очевидным образом полна, так как любая формула в ней выводится вместе со своим отрицанием. Из знаменитой теоремы Гёделя о неполноте следует, что всякая достаточно сильная рекурсивно аксиоматизируемая непротиворечивая теория первого порядка неполна. В частности, таковой является арифметика Пеано — теория, описывающая привычные свойства натуральных чисел со сложением и умножением.

Не следует путать введённое выше понятие полноты теории с понятием полноты логики, означающим, что в любой теории этой логики все общезначимые формулы окажутся выводимыми из аксиом логики. Например, теорема Гёделя о полноте утверждает, что классическая логика первого порядка полна. Это значит, что в любой теории первого порядка любая тождественно истинная формула (то есть истинная независимо от интерпретации сигнатуры и от значений переменных) будет выводима.