Еще один способ показать главный парадокс бесконечных множеств

Приветствую Вас, уважаемые Читатели. Недавно я рассказывал Вам про одно из удивительных открытий - диагональный аргумент Кантора, который позволил доказать, что рациональных дробей и натуральных чисел одинаковое количество.

Сегодня покажу еще один крайне красивый способ этого доказательства, приписываемый американским математикам Нейлу Калкину и Герберту Уилфу, хотя из источников и известно, что подобное дерево строил и легендарный Галилео Галилей. Поехали!

Дерево, изображенное на рисунке называется двоичным, т.к. каждая вершина имеет не более двух потомков. В каждой вершине расположены рациональные дроби, а их потомки удовлетворяют формулам ------->

Ключевая особенность дерева Калкина -Уилфа в том,что все дроби в ней несократимы, и каждая встречается только один раз. Это легко показать, если произвести обход "в ширину" :

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

Спасибо за внимание! Если было что-то непонятно, читайте материал на тему сравнения бесконечных множеств.

• TELEGRAM и Facebook- там я публикую не только интересные статьи, но и математический юмор и многое другое.