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

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

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

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

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

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

Предположим, наоборот, что ${\displaystyle z\notin Z=F(z)}$, тогда ${\displaystyle z}$ не принадлежит своему образу и, следовательно, принадлежит множеству ${\displaystyle Z}$. Вновь противоречие, так что ${\displaystyle Z}$ не есть образ при ${\displaystyle F}$^[2].

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