Теорема о диагонали

Теорема о диагонали — утверждение теории множеств о свойстве функции, значениями которой являются подмножества множества, содержащего её область определения.

Формулировка

Пусть $A$ — некоторое множество, $F$ — некоторая функция, имеющая область определения $T$. Если область определения $T$ функции $F$ содержится в $A$, а значениями функции $F$ служат подмножества множества $A$, то множество

$Z=𝒻t\in T;t\notin F(t)ℊ$,

(то есть $Z$ - это множество всех элементов из $A$, для которых функция $F$ определена и которые не принадлежат своему образу при $F$) не является значением функции $F$ (то есть $F(a)\ne Z$ для всех $a\in T$)Шаблон:Sfn.

Доказательство

Предположим, что для некоторого $z\in A$ справедливо $F(z)=Z$, так что $z\in T$. Тогда либо $z\in Z$, либо $z\notin Z$. Если $z\in Z=F(z)$, то $z$ принадлежит своему образу и, следовательно, не принадлежит множеству $Z$ - противоречие.

Предположим, наоборот, что $z\notin Z=F(z)$, тогда $z$ не принадлежит своему образу и, следовательно, принадлежит множеству $Z$. Вновь противоречие, так что $Z$ не есть образ при $F$Шаблон:Sfn.

Литература

• Шаблон:Книга
• Шаблон:Книга