	Предполные классы. Теорема о 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 не полное, что противоречит определению