Кажете вашето мнение за нея и за изводите от нея.

Съдържаниет е скрито
Влезте за да го видите

Съдържаниет е скрито
Влезте за да го видите

Гьодел е доказал много теореми. Коя по-точно?
Сигурно имаш в пред вид теоремите за непълнотата, доказани от Гьодел през 1930. От развитата техника в тяхното доказателство е произлязла цяла дисциплина в математиката, а именно “Теория на рекурсията”, която се чете (само увод) на студентите по информатика в СУ по дисциплината “Теория на програмите”.

Ще цитирам тези деве теореми, за да се знае за какво говорим:


П ъ р в а т е о р е м а з а н е п ъ л н о т а т а. Нека T е формална теория, съдържаща аритметиката. Тогава съществува твърдение Ф, което твърди своята собствена непротиворечивост и такова, че

(i) ако T е непротиворечива, то T |--/- Ф, или казано с думи, Ф не е формално изводимо от T;

(ii) ако Т е омега-непротиворечива, то T |--/- ~Ф, или казано с думи, ~Ф (т.е. “не Ф”) не е формално изводимо от T.


В т о р а т е о р е м а з а н е п ъ л н о т а т а. Нека T е непротиворечива формална теория, съдържаща аритметиката. Тогава имаме

Т |--/- Con(T), или казано с думи, от T не е формално изводимо Con(T) ,

където Con(T) е твърдение, изразяващо непротиворечивостта на теорията Т.


Има и още важни теореми доказани от Гьодел. На пример, в теория на моделите имаме “теорема за пълнотата на Гьодел”. След това имаме теоремa на Гьодел която твърди, че континуум хипотезата (CH) не противоречи на теория на множествата. По късно Коен, 1969 създава метода на форсинга с който доказва, че и ~CH не противоречи на теория на множествата.

Kakvo tochno e "омега-непротиворечива" ?

Както обикновенно, термина "омега-" се използва за понятие свързано с безкрайна, но изброима съвкупност.
В случая с теория на числата (можем да си мислим теорията получена от аксиоматиката на Пеано) това означава следното.

Нека Ф(x) е твърдение в някоя теория на числата. Нека сега разгледаме безкрайната но редицата изброима редица от твърдения

Ex Ф(x), ~Ф(0), ~Ф(1), ~Ф(2), . . .

Разглеждайки тази редица, може да заподозрем, че не е възможно всички твърдения в нея да са едновременно вярни. Първото твърдение "Ex Ф(x)" ни казва, че за някое x е вярно Ф(x), но пък следващите твърдения ~Ф(0), ~Ф(1), . . . ни твърдят, че Ф(x) не се изпълнява за никое число 0, 1, 2, . . .

Сега, когато в дадена теория на числата, за никое нейно твърдение Ф(x) НЕ СЕ ИЗПЪЛНЯВАТ едновременно всички твърдения от посочената по-горе редица, тази теория се нарича ОМЕГА-НЕПРОТИВОРЕЧИВА.

Както се вижда, това е едно естествено изискване.
То се посочва допълнително, понеже е трудно да бъде изразено в езика на логика от първи порядък (виж Забележка2 по-долу).

Забележка1. Едно такова изискване за омега-непротиворечивост е разумно, но няма гаранция, че за всяка теория на числата това свойство ще е изпълнено. Прости примери ни дават такива модели, в който чрез добавяне към числата 0, 1, 2, . . . още един обект, "алфа", то горното не се изпълнява. Обикновенно се взема "алфа" така, че "алфа" да не е наследник за никое число (т.е за никое x не вярно "алфа" = x + 1).

Забележка2. Защо ни е необходимо специално понятие, като омега-непротиворечивост? Главно поради факта, че това свойство трудно се формулира в езика на логика от първи порядък. То може да се представи, разбира се, като безкрайната конюнкция

ExФ(x) /\ ~Ф(0) /\ ~Ф(1) /\ ~Ф(2) /\ . . .

Но в езика на логика от първи порядак не е дефинирано понятието "безкрайна конюнкция".

Вместо горната безкрайна конюнкция, в логика от първи порядък може да използваме следната безкрайна редица от твърдения

Г1(x) = ExФ(x) /\ Ф(0),
Г2(x) = ExФ(x) /\ Ф(0) /\ Ф(1),
. . .
Гn(x) = ExФ(x) /\ Ф(0) /\ Ф(1) /\ . . . /\ Ф(n),
. . .


Тези твърдения нарастват по дължина, но всяки от тях е крайна конюнкция.

Но и тук имаме проблем, понеже константите 0, 1, 2, . . . са понятие от езика на някой модел на теория на числата или от диаграмата му. Все пак, в термините на аксиоматиката на Пеано можем да изразим константите 0, 1, 2, . . . по следния начин

0 = 0 (нулата си е от езика на теорията)
1 = S(0) (т.е наследника на нула)
2 = S(S(0)),
3 = S(S(S(0))),
. . .

Допуснах грешка с редицата Г1(x), Г2(x), . . . Както съм я написал, тя изобщо не означава омега-непротоворечивост.

На нас ни трябва твърдение от рода

~ (ExФ(x) /\ ~Ф(0) /\ ~Ф(1) /\ . . . /\ ~Ф(n) /\ . . .)

което може да се запише като

Ax ~Ф(x) \/ Ф(0) \/ Ф(1) \/ . . . \/ Ф(n) \/ . . .

което е безкрайна дизюнкция (тук Ax означава “за всяко x”).
Просто няма начин как горното твърдение да се изрази в езика на логиката от първи порядък.

Следователно, понятието омега-непротиворечивост не е от езика на логиката от първи порядък!!!