Приветствую Вас, уважаемые Читатели. Недавно я рассказывал Вам про одно из удивительных открытий — диагональный аргумент Кантора, который позволил доказать, что рациональных дробей и натуральных чисел одинаковое количество.
Сегодня покажу еще один крайне красивый способ этого доказательства, приписываемый американским математикам Нейлу Калкину и Герберту Уилфу, хотя из источников и известно, что подобное дерево строил и легендарный Галилео Галилей. Поехали!
Дерево, изображенное на рисунке называется двоичным, т.к. каждая вершина имеет не более двух потомков. В каждой вершине расположены рациональные дроби, а их потомки удовлетворяют формулам ——->
Ключевая особенность дерева Калкина -Уилфа в том,что все дроби в ней несократимы, и каждая встречается только один раз. Это легко показать, если произвести обход "в ширину" :
Два вышеперечисленных свойства выгодно отличают это двоичное дерево от диагонального аргумента Кантора, хотя и влияния на сам процесс доказательства счетности множества рациональных чисел не оказывают. Действительно, если мы развернем рациональные дроби из спирали на рисунке выше, то сможем построить взаимно-однозначное соответствие с множеством натуральных чисел ——>
Спасибо за внимание! Если было что-то непонятно, читайте материал на тему сравнения бесконечных множеств.
- TELEGRAM и Facebook— там я публикую не только интересные статьи, но и математический юмор и многое другое.
