?

Log in

No account? Create an account
о подсчёте рациональных чисел - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

о подсчёте рациональных чисел [дек. 17, 2002|11:22 pm]
Anatoly Vorobey
Случайно наткнулся на небольшую милую статью о красивом способе подсчёта рациональных чисел.

Первым "посчитал" рациональные числа Кантор, доказавший во второй половине 19-го века существования разных видов бесконечности. Он доказал, что рациональные числа представляют собой счётное множество (что означает - бесконечное множество, имеющее столько же членов, сколько множество натуральных чисел; иными словами, рациональные числа можно все "пересчитать" с помощью натуральных), а действительные - несчётное множество: их пересчитать с помощью натуральных чисел невозможно.

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

0, 1, -1, 2, -2, 3, -3, 4, -4, ...

В этом списке каждое целое число рано или поздно встретится, и поэтому мы можем каждому целому числу поставить в соответствие натуральное - его номер в этом списке. Это и значит, что множество целых чисел счётное. Но если бы мы пробовали его пересчитать так: 0, 1, 2, 3, .... то это было бы неправильной стратегией, т.к. мы никогда бы не "дошли" до отрицательных чисел.

Стандартный способ пересчёта рациональных чисел вот какой:



(ради простоты здесь и далее будем подсчитывать только положительные рациональные числа; если их можно "пересчитать" натуральными, то 0 и отрицательные к ним можно добавить при помощи того же трюка, который позволяет пересчитать целые числа)

Сначала мы выстраиваем все положительные рациональные числа в бесконечном квадрате: строки и столбцы квадрата перенумерованы натуральными числами, а внутри квадрата в каждой клетке стоит рациональное число, равное частному номера столбца и номера строки. Ясно, что каждое рациональное число находится в этом квадрате. А затем мы его пересчитываем "по диагоналям" (картинка справа), начиная с левого верхнего угла, потом диагональ размером в два числа, потом следующая итд. итд. Ясно, что двигаясь таким образом, мы рано или поздно дойдём до любого числа в квадрате, а значит, в нашем списке будут все положительные рациональные числа.

Этот стандартный способ очень прост, но у него есть эстетические недостатки: например, в этом списке есть повторы: каждое рациональное число повторяется в нём бесконечное число раз (например, 1/2 встречается также как 2/4, 4/8 итд.) Это не мешает доказательству, т.к. эти повторы можно просто выбрасывать, строя список, но тогда для общего его члена не будет красивой лёгкой формулы.

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

Принцип наименьшего элемента эквивалентен принципу математической индукции по натуральным числам. Их можно легко доказать один с помощью другого. Например, предположим, что какое-то утверждение S выполняется для числа 1, и если оно выполняется для всех k<n, то выполняется также для n; и докажем теперь, что оно выполняется для любого n (принцип индукции). Предположим, что есть такие n, для которых S не выполняется; возьмём множество всех таких n. Согласно принципу наименьшего элемента у этого множества есть наименьший элемент M. Но если M=1, то это противоречит условию, т.к. S выполняется для 1; а если M>1, то S выполняется для всех k<M согласно минимальности M, и тогда S выполняется для M согласно условию. В любом случае получаем противоречие.

Можно доказать и наоборот: с помощью индукции доказать, что любое непустое множество имеет наименьший элемент. Для этого достаточно показать индукцией по n, что если n принадлежит множеству X натуральных чисел, то в X есть наименьший элемент. Если n=1, это очевидно, т.к. 1 и будет наименьший элемент. Если это утверждение верно для всех k<n, то пусть X будет множеством, содержащим число n. Если в X есть какие-то k<n, то утверждение верно по предположению; а если их нет, то n и будет наименьшее число. В любом случае в X есть наименьший элемент.


Итак, вот эта конструкция. Построим бесконечное дерево, в вершинах которого находятся положительые рациональные числа, следующим образом:



Принцип построения дерева вот какой. В корне дерева стоит число 1/1. Далее, у каждой вершины есть двое сыновей. Если в вершине стоит число i/j, то в левом сыне будет стоять число i/i+j, а в правом - число i+j/j:



Теперь, последовательно используя принцип наименьшего элемента, докажем следующие утверждения про наше дерево:
  • В каждой вершине дерева находится число вида i/j, где числитель и знаменатель - положительные натуральные числа. Это очевидно из построения и может быть формально доказано тривиальной индукцией.
  • Для каждой вершины верно, что в левом её сыне находится число меньше единицы, а в правом - число больше единицы. Это очевидно из построения (в левом сыне числитель меньше знаменателя, в правом - наоборот). Отсюда следует, что единица в этом дереве может находится только в корне.
  • В каждой вершине дерева находится несократимая дробь. Предположим, что это не так, тогда есть вершины, в которых расположены сократимые дроби, т.е. такие, для которых у числителя и знаменателя есть общий делитель больше 1. Из всех таких вершин выберем те, у которых наименьший знаменатель (мы здесь используем принцип наименьшего элемента: смотрим на множество знаменателей всех таких вершин и выбираем наименьший элемент); из всех этих вершин выберем вершину с наименьшим числителем. Пусть мы получили вершину, в которой записано число i/k, и у i с k есть общий делитель больше единицы. Не может быть, чтобы i=k, т.к. в любом сыне дерева записано число больше или меньше единицы, а 1 записана только в корне дерева в виде 1/1, и это несократимая дробь. Значит, либо i меньше k, либо наоборот. Если i<k, то у вершины i/k есть "отец" i/k-i. У чисел i и k-i тоже есть общий делитель, тот же, что у i и k, но у числа i/k-i знаменатель меньше, чем у i/k, что противоречит минимальности при выборе знаменателя. Если k<i, то у вершины i/k есть "отец" i-k/k, который тоже сократимая дробь, с тем же знаменателем, что у i/k, но с меньшим числителем - противоречит минимальности при выборе числителя. В любом случае получаем противоречие, поэтому сократимых дробей в дереве нет.
  • В дереве встречается каждое положительное рациональное число. Предположим, что это не так. Тогда есть непустое множество рациональных чисел, которые не встречаются в дереве; выберем из них сначала наименьший знаменатель, а потом среди всех с этим знаменателем наименьший числитель, и пусть это будет число i/k. Если i<k, то у числа i/k-i знаменатель меньше, и поэтому оно находится в дереве; но тогда i/k - его левый "сын". Если i>k, то у числа i-k/k тот же знаменатель, но меньший числитель, и поэтому оно находится в дереве; но тогда i/k - его правый "сын". В любом случае получаем противоречие, поэтому любое положительное рациональное число находится в дереве.
  • Каждое положительное рациональное число находится в дереве всего один раз, без повторов. Предположим, что это не так. Среди всех чисел, находящихся больше одного раза в дереве, выберем какое-нибудь, которое находится (в одном из своих повторов) на наименьшем уровне дерева (т.е. "строке" в картинке выше). Пусть это уровень номер k. k не может быть равно 1, т.к. на первом уровне находится только число 1/1, а оно не повторяется больше нигде (см. выше). Значит, k>1. Наше число, находящееся в вершине A на уровне k, встречается ещё хотя бы один раз в вершине B где-нибудь ещё в дереве (возможно, и на том же уровне). Может ли быть, что вершины A и B - сыновья одной вершины? Нет, т.к. у любой вершины один сын меньше 1, другой больше, и они не могут быть равны. Значит, A и B - сыновья разных вершин; но тогда отец A и отец B тоже равны между собой (сын определяет отца; если сын = i/k для i<k, то отец = i/k-i; если сын = i/k для i>k, то отец = i-k/k), причём отец A находится на уровне k-1, что противоречит минимальности выбора k. Значит, каждое число повторяется в дереве только один раз.

Мы уже доказали, что можно пересчитать все положительные рациональные числа: в дереве встречаются все такие числа по одному разу, так что можно их пересчитать, просто идя по дереву уровень за уровнем, слева направо по каждому уровню. Ясно, что таким образом рано или поздно дойдёшь до любой вершины дерева.

Но оказывается, у этой конструкции есть ещё несколько интересных особенностей. Пусть g(k) - число в k-й вершине в описанном выше обходе дерева слева направо и сверху вниз. При этом начнём с k=0, т.е. самая первая вершина будет "нулевой" (это окажется удобным впоследствии). Тогда
  • Для каждого k верно, что знаменатель g(k) равен числителю g(k+1).

    Доказательство: если g(k) и g(k+1) - два идущих друг за другом сына одного отца, тогда это очевидно из построения дерева (т.к. это числа вида i/i+k и i+k/k). Если g(k) - "правый" сын какого-то отца, а g(k+1) - "левый" сын другого, тогда знаменатель g(k) равен знаменателю его отца, а числитель g(k+1) равен числителю его отца, и их отцы находятся рядом друг с другом на предыдущем уровне, и потому тоже имеют вид g(i) и g(i+1) для какого-то i. Значит, индукция по номеру уровня доказывает утверждение в этом случае. Осталось рассмотреть, что происходит, когда g(k) и g(k+1) находятся на разных уровнях. Но тогда g(k) - число в самой правой вершине своего уровня, и знаменатель g(k) равен 1; а g(k+1) - число в самой левой вершине своего уровня, и его числитель тоже равен 1 (см. картинку).

Обозначим через f(k) числитель k-й вершины при обходе дерева, т.е. числитель g(k). Тогда из вышеописанного следует, что список всех рациональных чисел можно построить с помощью последовательности f(0), f(1), f(2), f(3).... следующим образом: f(0)/f(1), f(1)/f(2), f(2)/f(3), f(3)/f(4)... , деля каждый раз следующее по списку число в последовательности f на следующее за ним.

По-моему, это красиво. Но и это ещё не всё: оказывается, что саму последовательность f(k) можно описать независимым образом, наполнить её "смыслом". А именно: f(k) - количество путей, с помощью которых k можно представить в виде суммы степеней двойки, так что каждую степень можно использовать не более двух раз.

Например, вот несколько первых членов последовательности f(k) (из картинки выше):

1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4

Значит, скажем, f(9)=3 (помним, что счёт f(k) начинается с k=0). И есть ровно 3 способа записать 9 в виде суммы степеней двойки, используя каждую степень не более двух раз (помня при этом, что 1 - тоже степень двойки, нулевая):

9=8+1
9=4+4+1
9=4+2+2+1

А f(10)=5, и для десятки есть пять способов: 8+2, 8+1+1, 4+4+2, 4+4+1+1, 4+2+2+1+1.

Наконец, докажем строго, что f(k) имеет именно этот смысл. Для этого построим рекурсивное определение f(k) и докажем, что b(k), если обозначить так кол-во способов представить k в виде суммы степеней двойки, не используя каждую более чем дважды, удовлетворяет тому же определению.

Во-первых, f(0)=1, т.к. первая вершина в нашем обходе - 1/1, и её числитель равен 1.
Далее, посмотрим на n-ю вершину в обходе: в ней стоит число f(n)/f(n+1). Пользуясь формулами постройки дерева, видим, что её левый сын равен f(n) / (f(n)+f(n+1)), а правый сын равен (f(n) + f(n+1)) / f(n+1). Но, с другой стороны, её левый сын - это 2n+1-я вершина в том же обходе, а правый сын - 2n+2-я (в этом легко убедиться, посмотрев на картинку, и легко доказать строго: сыновья n-й вершины - 2n+1-я и 2n+2-я вершины в обходе). Значит, f(2n+1) равен числителю левого сына, т.е. f(n), а f(2n+2) равен числителю правого сына, т.е. f(n)+f(n+1). Мы получили следующие рекурсивные формулы:
  • f(0)=1
  • f(2n) = f(n) + f(n+1)
  • f(2n+1) = f(n)
Ясно, что вместе они полностью определяют все значения f. Значит, осталось только доказать, что b(k) выполняет те же формулы.
  • b(0)=1, т.к. есть только один способ представить 0 в виде суммы степеней двойки: "пустая" сумма без единого слагаемого (если этот трюк не убеждает, то можно просто объявить b(0)=1 по определению и проверить, что использование этого значения согласуется с формулами при подсчёте b(1) и b(2), а для всех больших значений аргумента это уже неважно).
  • Пусть теперь наш аргумент - 2k+1, т.е. нечётное число. Тогда в его представлении в виде суммы степеней двойки обязана участовать единица, причём ровно один раз. Если мы теперь уберём эту единицу, а все остальные слагаемые поделим на 2, то получим представление в виде степеней двойки числа k. И наоборот, если есть представление числа k, можно все слагаемые умножить на 2 и прибавить ко всему 1 и получить представление числа 2к+1. Из этого ясно, что кол-во представлений для 2k+1 и k равно, т.е. b(2k+1)=b(k).
  • Пусть теперь наш аргумент - 2k+2, т.е. чётное число. Для любого представления 2k в виде суммы степеней двойки есть два случая: либо в нём не участвует ни одна единица, и тогда, поделив все слагамые на 2, получим представление числа k+1; либо в нём участвуют две единицы, тогда выбросим их и поделим оставшееся на 2, и получим представление числа k. Рассуждая так же, как в прошлом пункте, видим, что b(2k+2) = b(k+1) + b(k).


Всё.
СсылкаОтветить

Comments:
From: ex_ilyavinar899
2002-12-17 01:26 pm
По-моему, в Concrete Mathematics Кнута, Грэма и Паташника что-то рассказывалось о свойствах этого дерева, но я слишком плохо выспался, чтобы ее доставать и читать.
(Ответить) (Thread)
[User Picture]From: readership
2002-12-17 01:58 pm
А как вы к этому относитесь: "ОШИБКА ГЕОРГА КАНТОРА". http://www.com2com.ru/alexzen/papers/vf1/vf-rus.html ?

Или: http://www.com2com.ru/alexzen/papers/Cantor/Fatal_Mistake_of_Cantor.html

Очень мне любопытно, не математик я.
(Ответить) (Thread)
[User Picture]From: avva
2002-12-17 02:10 pm

Re:

Это бред очень грустный весьма.

Меня огорчает, что "Вопросы философии" могут такое напечатать. Хотя, впрочем, я их не читаю, может, они постоянно такое печатают.
(Ответить) (Parent) (Thread)
[User Picture]From: lnvp
2002-12-17 02:17 pm

Так в том-то и дело, что Зенкин - "философ от компьютера" типа тех инженеров, которые Эйнштейна опровергают. Ну вот его соответствующий журнал и печатает. Они же не специалисты в математике, да?

Философия - не наука :^)
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-12-17 02:22 pm

Re:

Философия - действительно не наука. По крайней мере не в том смысле наука, в каком физика - наука.

Но это не значит, что философский журнал должен столь очевидный бред печатать. Если сами не понимают - могут математика спросить.
(Ответить) (Parent) (Thread)
From: ex_petruha
2002-12-17 02:29 pm

мое мнение

все науки кроме философии отчвечают на вопросы "что?" и "как?"

а сама философия отвечает, а точнее пытается ответить, на вопрос "зачем?" не менее важный тем не менее. и вот когда (если) это произойдет то ни физика ни пр. будут не нужны.
(Ответить) (Parent) (Thread)
[User Picture]From: lnvp
2002-12-17 02:35 pm

Re: мое мнение

В данном случае товарищ Зенкин по-философски разбирался в том, "что" и "как". Если бы только "зачем" (т.е. философы занимали бы свою узкую нишу и ни на что другое не претендовали бы), гораздо меньше было бы пустых споров...
(Ответить) (Parent) (Thread)
[User Picture]From: malaya_zemlya
2002-12-17 05:10 pm

Советую посмотреть статью:

Editor recalls some hopeless papers (Bulletin of Symbolic Logic, Vol 4, Number 1, 1998)
http://www.math.ucla.edu/~asl/bsl/0401/0401-001.ps
(в формате Постскрипт)

Это разбор типичных ошибок в опровержениях теоремы Кантора. Что приятно, автор не становится в позицию "что с них, психов, возьмешь!", а доброжелательно и терпеливо разбирает все логические несостыковки.

(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-12-17 06:28 pm

Да, отличная статья, спасибо.

Мне вообще нравится, как пишет Hodges; в частности, его учебник по теории моделей нравится больше, чем классический Chang&Keisler (хоть это мнение и не комильфо в определённых кругах, кажется).

Помнится, он заканчивает предисловие хорошей фразой:

"I" means I. "We" means we.

(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-12-17 06:32 pm

Editor recalls some hopeless papers

Забавная каламбурность, или точнее намёк на каламбурность, в названии.
(Ответить) (Parent) (Thread)
[User Picture]From: readership
2002-12-17 06:09 pm
Может быть....По крайней мере, у меня большие претензии к его другому доказательству - развенчанию парадокса Лжеца. Собственно, не к доказательству, а к его выводам из.

Не могли бы вы дать свой краткий анализ? Доказательство то небольшое :) Было бы крайне полезно многим, думаю. Тем более, что http://science.ng.ru/magnum/2000-07-19/5_mathem.html
А у меня есть с этим связанная одна идейка, объясняющая неоторые жж-феномы неполной комуникации :)
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-12-17 06:17 pm

Re:

Признавайтесь: Вы - Зенкин? ;)
(Ответить) (Parent) (Thread)
[User Picture]From: readership
2002-12-17 06:21 pm
А как доказать?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-12-17 06:24 pm

Re:

Да я ж не против, мне просто интересно.
(Ответить) (Parent) (Thread)
[User Picture]From: readership
2002-12-17 06:20 pm
Ого, какие феномы поперли :( Пошел спать.
(Ответить) (Parent) (Thread)
[User Picture]From: lnvp
2002-12-17 02:13 pm

Насколько я понимаю, это математический аналог любителей опровергать теорию относительности (или квантовую механику, но ТО почему-то больше любят) в физике. Зенкинская "дотошность", обращённая к Кантору, сама не выдерживает довольно элементарного анализа с точки зрения классической матлогики. На его страницах можно посмотреть его ответы опонентам - так вот, тексты опонентов выглядят гораздо разумнее зенкинских.

Впрочем, я ведь тоже не специалист - вышесказанное видится с точки зрения здравого смысла и базового математического образования.
(Ответить) (Parent) (Thread)
[User Picture]From: thumm
2002-12-18 07:40 pm

А кванты "опровергнуть" сложнее. Надо хоть что-то понять для начала, язык выучить.
А про ТО они думают, что им все ясно;)
(Ответить) (Parent) (Thread)
[User Picture]From: lnvp
2002-12-18 08:40 pm

Re:

Точно! С математикой - та же история. Не слышно, чтобы кто-нибудь теорию Галуа, скажем, опровергал - разбираться лень :)
(Ответить) (Parent) (Thread)
[User Picture]From: lnvp
2002-12-17 02:28 pm
А вот мне ещё какой метод вспомнился (в одной из Гарднеровских книжек в детстве читал, кажется).

Начинаем с двух дробей: 0/1 и 1/0 (последняя не представляет число, чисто формальная запись).

Далее, повторяем следующие шаги: везде между уже выписанными n дробями выписываем n-1 новых следующим образом: между a/b и c/d пишем (a+b)/(c+d) (не сокращая). Очевидно, каждая новая дробь стоит на своём месте (в смысле упорядочивания по возрастанию) и отличается от ранее написанных. Отсюда, кстати, и несократимость может следовать (не уверен).

Нетрудно доказать, что любое рациональное число рано или поздно окажется выписанным.

Похоже на диагональный метод, но по-своему красивее :^). С деревом не сравнивал - уж очень длинный текст про него, не дочитал пока.
(Ответить) (Thread)
[User Picture]From: lnvp
2002-12-17 02:29 pm
Пардон, опечатался: конечно, следует читать (a+c)/(b+d)!
(Ответить) (Parent) (Thread)