Счетность

Разрешимость и вычислимость

Элементы теории алгоритмов

Доказуемые формулы в формальной арифметике

Общезначимые формулы в исчислении предикатов

Тавтология в классическом исчислении высказываний

Лекция 8

Разрешимость и вычислимость:

Объект является разрешимым по отношению к заданному свойству, если существует алгоритм, в результате работы которого будет однозначно получен ответ, обладает объект свойством, или нет.

Объект является вычислимым, если он может быть получен в результате работы некоего алгоритма.

Разрешимой является замкнутая формула теории К, которая либо сама доказуема, либо доказуемо ее отрицание. Это означает, что существует доказательство или вывод соответствующей формулы. Перебирая последовательно всевозможные доказательства теории, дожидаемся появления доказательства либо самой формулы, либо ее отрицания. Если удается организовать такой перебор (вычислимая последовательность), то такое событие рано или поздно произойдет, если формула является разрешимой (соответствующее доказательство вычислимо).

Среди формул теории К существуют неразрешимые формулы.

Множество называется счетным, если его элементы могут быть занумерованы (то есть существует вычислимая последовательность его элементов - ЭЛЕМЕНТi=F(i), i=1,2,...).

Примеры счетных множеств:

· Множество натуральных чисел f(i)=i.

· Множество четных чисел f(i)=2*i.

· Множество всех целых чисел f(i)=...

· Множество положительных рациональных чисел.

· Множество всех рациональных чисел.

· Любое конечное множество.

· Множество всех слов любого языка.

· Множество всех доказательств в теории К.

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

Так может быть все множества счетны? Нет!

Дата добавления: 2013-12-13