Свойства К-определимых предикатов и функций (теоремы).

Теорема 1. Если предикаты R(n1,…,nk) и Q(n1,…,nk) К-определимы, то предикаты R(n1,…,nk); R(n1,…,nk)&Q(n1,…,nk); R(n1,…,nk)γQ(n1,…,nk) K-определимы.

Т.е. с помощью булевых операций мы создаем новые предикаты, которые сохраняют свойство К-определимости.

Доказательство (для &).

Теорема 2. Если предикат R(n1,…,nk) и функция f(m1,…,mj) и δ(n1,…,nl) К-определимы в Р, то предикат R(n1,…,ni-1, f(m1,…,mj), ni+1,…,nk) и функция δ(n1,…,ni-1, f(m1,…,mj), ni+1,…,nl) К-определимы в Р.

Теорема 3. Если К-местный предикат R(n1,…,nk) К-определим в Р, то К-1-местный предикат (т.е. предикат на 1 меньше К) R(n1,…,nk) К-определим в Р.

Мы навешиваем ограниченный по числу l квантор.

Доказательство. Поскольку квантор ограничен числом l, то предикат может быть представлен в виде. Т.е. один из предикатов до l выполняет этот квантор. Мы получаем конечно-членную дизъюнкцию, ее доказательство – в теореме 1.

Теорема 4. Если предикат (функция) Т-определим в Р, то этот предикат (функция) формально определим (Tr-определим) в Р.

Теорема 5. Если предикат (функция) Т-определим в Р, то этот предикат (функция) К-определим в Р.

Если А теорема, то А выводима из любого множества посылок.

Теорема 6. Если к-местный предикат R Tr-определим в Р, то Tr-определим (к-1)-местный предикат

Навешиваем квантор, но квантор неограниченный.

Следствие 1. Любой рекурсивно перечислимый класс Q натуральных чисел формально определим в Р.

По определению (рекурсивно перечислимого предиката), непустой класс Q рекурсивно перечислим т.т.т., когда предикат n Q (или Q(n)) выразим в форме с общерекурсивным R (т.е. если мы навесим неограниченный квантор существования на общерекурсивный предикат R). Предикат R формально-определим (Тr-определим) в Р (потому что он рекурсивный), следовательно, формально-определим предикат n Q (навешивание неограниченного квантора будет сохранять формальную определимость).

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

Навешивание неограниченного квантора существования на Т-определимый предикат не обеспечивает нам Т-определимости, но обеспечивает Tr-определимость. Навешивание неограниченного квантора существования на Tr-определимый предикат обеспечивает нам Tr-определимость.

Дата добавления: 2015-07-16