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

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

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

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

$Z={\mathcal {f}}t\in T;t\notin F(t){\mathcal {g}}$,

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

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

Предположим, что для некоторого $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$.

Литература

• Куратовский К., Мостовский А. Теория множеств. — М.: Мир, 1970. — 413 с.
• Калужнин Л. А. Введение в общую алгебру. — М.: Наука, 1973. — 447 с.