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

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

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

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

[math]\displaystyle{ Z = \mathcal{f} t \in T ; t \notin F(t) \mathcal{g} }[/math],

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

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

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

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

Литература

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