24 lines
2.1 KiB
Markdown
24 lines
2.1 KiB
Markdown
Предполные классы. Теорема о 5 предполных классах
|
||
|
||
# Предполные классы
|
||
1. класс, являющийся полным полным только при добавлении любой новой функции
|
||
2. максимальное по отношению включения неполное множество
|
||
|
||
# Теорема о 5 предполных классах
|
||
## Теорема
|
||
Существует ровно 5 предполных классов: $T_0, T_1, S, M, L$
|
||
|
||
## Доказательство
|
||
НУО, возьмём класс L: $[L] = L \ne P_2$ ([[1 курс/2 семестр/Дискретка/Билеты/9#^ff2b6e|P2]])
|
||
Возьмём функцию $f \notin L$ и рассмотрим множество $L \cup \{f\}$. Если оно не полное, то по [[1 курс/2 семестр/Дискретка/Билеты/15#Теорема|теореме Поста]] оно должно быть подмножеством одного из классов $T_0, T_1, S, M$. Но тогда и L будет подмножеством этого класса, а это не так:
|
||
- $L \nsubseteq S$, т.к. $1 \in L - S$
|
||
- $L \nsubseteq M$, $L \nsubseteq T_0$, $L \nsubseteq T_1$, т.к. $\bar x \in L - (M \cup T_0 \cup T_1)$
|
||
Значит, $L \cup \{f\}$ - полное для любой функции f, а значит, L - предпольный класс
|
||
|
||
Докажем теперь, что других предпольных классов нет:
|
||
Пусть X - предпольный класс, отличный от $T_0, T_1, S, M, L$
|
||
|
||
По [[#Предполные классы|определению]], множество X не полное, значит, по [[1 курс/2 семестр/Дискретка/Билеты/15#Теорема|теореме]], оно включено в один из 5 классов
|
||
|
||
НУО, $X \subseteq S$. Т.к. $X \ne S$, то $\exists f \in S, f \notin X$
|
||
Но тогда $X \cup \{f\} \subseteq S$ и по теореме, X не полное, что противоречит определению |