Диагональный аргумент

Определение

Диагональный агрумент — изначально, это логический прием, которым воспользовался основатель теории множеств Георг Кантор для доказательства утверждения о том, что количество частей (подмножеств) любого множества всегда строго больше количества элементов этого множества. Утверждение теперь носит название теоремы Кантора и формально записывается так:

То есть мощность множества подмножеств любого множества А строго больше мощности самого множества А.

подмножеств (подумайте, почему это так), и, соответственно, количество подмножеств любого конечного множества действительно всегда заметно больше любого исходного количества его элементов (мы уже немного касались этой темы, когда разбирали задачу об отравленных бутылках и крысах на корабле).

Собственно, понятие мощности было введено тем же Кантором как обобщение понятия количества и на бесконечные совокупности. В отношении которых теорема как раз и становится нетривиальной и интересной — поскольку утверждает существование так называемых несчетных множеств, т. е. таких множеств, элементы которых не могут быть перенумерованы (пересчитаны) натуральными числами — первых оказывается больше.

последовательность из одних единиц и т д. И допустим, что каждую такую функцию/последовательность нам удалось занумеровать, то есть поставить во взаимное соответствие с каким-то натуральным числом. Получится какой-тo такой, бесконечный в обе стороны квадрат:

или в виде бесконечного списка различных бесконечных последовательностей нулей и единиц.

Техника доказательства.

Вот, как работает этот аргумент на примере доказательства неравномощности множества натуральных чисел и множества всех его подмножеств.

устроенной следующим образом:

А по нашему предположению, натуральными числами были занумерованы ВСЕ! подмножества. Противоречие.

Конструкция такой последовательности и называется диагональной конструкцией (ну и сам аргумент вслед за ней — диагональным) поскольку строится она действительно по диагонали: Кантор берет последовательность нулей и единиц, стоящих на диагонали составленного списка, и заменяет все ее элементы новыми — в частности, если на первом месте в последовательности f₁ стоял 0, то на первом месте вновь конструируемой последовательности f должна встать 1, если на втором месте f₂ стояла 1, но на втором месте f следует поставить 0. И так далее …

Несмотря на то, что Кантор использовал данный аргумент, так сказать, ad hoc, то есть по очень частному поводу, диагональная конструкция, как было показано позднее, обнаруживает себя в качестве центральной в достаточно широком классе математических доказательств: у Геделя — в его доказательстве первой теоремы о неполноте, у Тьюринга — в его решении проблемы остановки, а также создает логическую основу многих парадоксов автореференции — от парадокса лжеца до парадоксов Ришара и Рассела.

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

В самое ближайшее время такая формулировка теоремы с подробным разбором ее доказательства и некоторых важных следствий появится в соответствующем разделе «Теория категорий» на домашней странице нашего журнала.

Написать в чат

Есть вопросы по материалу?

Вы можете задать их в нашем специальном чате. Мы поможем разобраться в теме лучше

Понравилась статья?