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

04.02.2021

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

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

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

Z = f t ∈ T ; t ∉ F ( t ) g {displaystyle Z={mathcal {f}}tin T;t otin F(t){mathcal {g}}} ,

(то есть Z {displaystyle Z} - это множество всех элементов из A {displaystyle A} , для которых функция F {displaystyle F} определена и которые не принадлежат своему образу при F {displaystyle F} ) не является значением функции F {displaystyle F} (то есть F ( a ) ≠ Z {displaystyle F(a) eq Z} для всех a ∈ T {displaystyle ain T} ).

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

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

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