7

Теорема Поста Доказательство теоремы Поста

Теорема Поста

Определение. Класс функций C F называется полным, если [C] = F.

Теорема. Класс функций C F является полным тогда и только тогда, когда C не содержится в классах T0; T1; M, L,

S:

Теорема Поста Доказательство теоремы Поста

Теорема Поста

Определение. Класс функций C F называется полным, если [C] = F.

Теорема. Класс функций C F является полным тогда и только тогда, когда C не содержится в классах T0; T1; M, L,

S:

Теорема Поста Доказательство теоремы Поста

Лемма о несамопряженной функции

Лемма. Если f 2= S, то 0; 1 2 [ff ; g].

Теорема Поста Доказательство теоремы Поста

Лемма о несамопряженной функции

Лемма. Если f 2= S, то 0; 1 2 [ff ; g].

Доказательство. Пусть f 2= S. Тогда существует набор ( 1; : : : ; n) такой, что

f ( 1; : : : ; n) = f ( 1; : : : ; n) 6= f ( 1; : : : ; n):

Теорема Поста Доказательство теоремы Поста

Лемма о несамопряженной функции

Лемма. Если f 2= S, то 0; 1 2 [ff ; g].

Доказательство. Пусть f 2= S. Тогда существует набор ( 1; : : : ; n) такой, что

f ( 1; : : : ; n) = f ( 1; : : : ; n) 6= f ( 1; : : : ; n):

Тогда f ( 1; : : : ; n) = f ( 1; : : : ; n).

Теорема Поста Доказательство теоремы Поста

Лемма о несамопряженной функции

Лемма. Если f 2= S, то 0; 1 2 [ff ; g].

Доказательство. Пусть f 2= S. Тогда существует набор ( 1; : : : ; n) такой, что

f ( 1; : : : ; n) = f ( 1; : : : ; n) 6= f ( 1; : : : ; n):

Тогда f ( 1; : : : ; n) = f ( 1; : : : ; n). Поэтому для формулы g(x) = f (x 1 ; : : : ; x n ) имеем

g(0) = f ( 1; : : : ; n) = f ( 1; : : : ; n) = g(1):

Теорема Поста Доказательство теоремы Поста

Лемма о несамопряженной функции

Лемма. Если f 2= S, то 0; 1 2 [ff ; g].

Доказательство. Пусть f 2= S. Тогда существует набор ( 1; : : : ; n) такой, что

f ( 1; : : : ; n) = f ( 1; : : : ; n) 6= f ( 1; : : : ; n):

Тогда f ( 1; : : : ; n) = f ( 1; : : : ; n). Поэтому для формулы g(x) = f (x 1 ; : : : ; x n ) имеем

g(0) = f ( 1; : : : ; n) = f ( 1; : : : ; n) = g(1):

Таким образом, одна из констант 0; 1 является формулой над ff ; g.

Теорема Поста Доказательство теоремы Поста

Лемма о несамопряженной функции

Лемма. Если f 2= S, то 0; 1 2 [ff ; g].

Доказательство. Пусть f 2= S. Тогда существует набор ( 1; : : : ; n) такой, что

f ( 1; : : : ; n) = f ( 1; : : : ; n) 6= f ( 1; : : : ; n):

Тогда f ( 1; : : : ; n) = f ( 1; : : : ; n). Поэтому для формулы g(x) = f (x 1 ; : : : ; x n ) имеем

g(0) = f ( 1; : : : ; n) = f ( 1; : : : ; n) = g(1):

Таким образом, одна из констант 0; 1 является формулой над ff ; g. Подставляя ее в отрицание, получим другую константу.

Теорема Поста Доказательство теоремы Поста

Лемма о немонотонной функции

Лемма. Если f 2= M, то 2 [ff ; 0; 1g].

Теорема Поста Доказательство теоремы Поста

Лемма о немонотонной функции

Лемма. Если f 2= M, то 2 [ff ; 0; 1g].

Доказательство. Пусть f 2= M.