Доказать что множество всех рациональных чисел счетно
Счетность множества рациональных чисел
Теорема: множество рациональных чисел является счётным.
Необходимо доказать, что между множеством рациональных чисел и множеством натуральных чисел можно установить взаимо-однозначное соответствие. Для этого положительные рациональные числа запишем так:
Таким образом, будет записано каждое положительное число. Например, число 7/31 будет записано в 31-й строке в 7-м столбце. Вообще, дробь m/n будет записана в n-й строке m-м столбце.
Для установления взаимно-однозначного соответствия теперь уже нельзя переходить от столбца к столбцу, потому что в каждом столбце содержится бесконечное множество элементов. Для доказательства этой теоремы будем использовать диагональный метод Кантора. Он заключается в том, что мы подходим к каждому рациональному числу и, следовательно, каждому рациональному числу будет поставлено в соответствие какое-либо натуральное число.
Так, с помощью диагонального метода устанавливаем взаимно-однозначное соответствие между множеством положительных рациональных и множеством натуральных чисел, а это значит, что множество положительных рациональных чисел счетно.
Также можно доказать, что множество отрицательных рациональных чисел счётно. Сложив эти два множества и прибавив к ним конечное множество, состоящее из элемента нуль, мы получим всё множество рациональных чисел.
Теорема.Множество всех действительных чисел несчетно.
Доказательство. Для доказательства достаточно установить, что множество действительных чисел интервала 
образует несчетное множество. Допустим противное, что интервал есть счетное множество, т. е. все его точки можно перенумеровать:
Но это предположение противоречиво. В самом деле, построим вещественное число 
, где цифры 
подобраны так, чтобы 
и 
. Ясно, что 
, однако 
не совпадает ни с одним из чисел 
, так как иначе должно было бы быть 
, что не имеет места.
Счётность множества рациональных чисел
Нумерация положительных рациональных чисел
Чтобы оценить количество рациональных чисел, нужно найти мощность их множества. Легко доказать, что множество рациональных чисел счётно. Для этого достаточно привести алгоритм, который нумерует рациональные числа, т. е. устанавливает биекцию между множествами рациональных и натуральных чисел. Примером такого построения может служить следующий простой алгоритм. Составляется бесконечная таблица обыкновенных дробей, на каждой i-ой строке в каждом j-ом столбце которой располагается дробь 
. Для определённости считается, что строки и столбцы этой таблицы нумеруются с единицы. Ячейки таблицы обозначаются 
, где i — номер строки таблицы, в которой располагается ячейка, а j — номер столбца.
Полученная таблица обходится «змейкой» по следующему формальному алгоритму.
§ Если текущее положение таково, что i — нечётное, а j = 1, то следующим положением выбирается 
.
§ Если текущее положение таково, что i = 1, а j — чётное, то следующим положением выбирается 
.
§ Если для текущего положения сумма индексов 
нечётна, то следующее положение — 
.
§ Если для текущего положения сумма индексов чётна, то следующее положение — 
.
Эти правила просматриваются сверху вниз и следующее положение выбирается по первому совпадению.
В процессе такого обхода каждому новому рациональному числу ставится в соответствие очередное натуральное число. Т. е. дроби 1 / 1 ставится в соответствие число 1, дроби 2 / 1 — число 2, и т. д. Нужно отметить, что нумеруются только несократимые дроби. Формальным признаком несократимости является равенство единице наибольшего общего делителя числителя и знаменателя дроби.
Следуя этому алгоритму, можно занумеровать все положительные рациональные числа. Это значит, что множество положительных рациональных чисел 
счётно. Легко установить биекцию между множествами положительных и отрицательных рациональных чисел, просто поставив в соответствие каждому рациональному числу противоположное ему. Т. о. множество отрицательных рациональных чисел 
тоже счётно. Их объединение 
также счётно по свойству счётных множеств. Множество же рациональных чисел 
тоже счётно как объединение счётного множества с конечным.
Разумеется, существуют и другие способы занумеровать рациональные числа. Например, для этого можно воспользоваться такими структурами как дерево Калкина — Уилфа, дерево Штерна — Броко или ряд Фарея.
Утверждение о счётности множества рациональных чисел может вызывать некоторое недоумение, т. к. на первый взгляд складывается впечатление, что оно гораздо обширнее множества натуральных чисел. На самом деле это не так и натуральных чисел хватает, чтобы занумеровать все рациональные.
Счетные множества
Множество называется счетным, если оно равномощно множеству 
натуральных чисел, то есть если его можно представить в виде 
(здесь 
— элемент, соответствующий числу 
; соответствие взаимно однозначно, так что все различны).
Например, множество целых чисел 
счетно, так как целые числа можно расположить в последовательность 
, 
, 
, 
, 
, 
, 
, 
(а) Подмножество счетного множества конечно или счетно.
(в) Объединение конечного или счетного числа конечных или счетных множеств конечно или счетно.
(а) Пусть 
— подмножество счетного множества 
. Выбросим из последовательности 
те члены, которые не принадлежат (сохраняя порядок оставшихся). Тогда оставшиеся члены образуют либо конечную последовательность (и тогда конечно), либо бесконечную (и тогда счетно).
(в) Пусть имеется счетное число счетных множеств 
Расположив элементы каждого из них слева направо в последовательность ( 
) и поместив эти последовательности друг под другом, получим таблицу
Замечание. В доказательстве утверждения (б) теоремы 2 есть тонкий момент: на каждом шаге мы должны выбрать один из оставшихся элементов множества 
; такие элементы есть, но у нас нет никакого правила, позволяющего такой выбор описать. При более формальном построении теории множеств тут нужно сослаться на специальную аксиому, называемую аксиомой выбора. Законность этой аксиомы вызывала большие споры в начале 20-го века, но постепенно к ней привыкли, и эти споры сейчас почти не воспринимаются. В середине века великий логик Курт Гедель доказал, что аксиому выбора нельзя опровергнуть, пользуясь остальными аксиомами теории множеств, а в 1960-е годы американский математик Пол Дж.Коэн доказал, что ее нельзя и вывести из остальных аксиом. (Конечно, понимание этих утверждений требует подробного изложения теории множеств как аксиоматической теории.)
30. Такой же тонкий момент (хотя и менее очевидный) есть и в доказательстве утверждения (в). Можете ли вы догадаться, где он? (Ответ: мы знаем, что множества 
счетны, то есть что существует взаимно однозначное соответствие между 
и . Но нужно выбрать и фиксировать эти соответствия, прежде чем удастся построить соответствие между объединением всех и .)
Еще несколько примеров счетных множеств:
31. Докажите, что любое семейство непересекающихся интервалов на прямой конечно или счетно. (Указание: в каждом интервале найдется рациональная точка.)
33. Докажите, что множество точек строгого локального максимума любой функции действительного аргумента конечно или счетно.
Докажите, что множество точек разрыва неубывающей функции Действительного аргумента конечно или счетно.
Счетность множества рациональных чисел.
Дата добавления: 2015-08-14 ; просмотров: 3824 ; Нарушение авторских прав
Школьная математика имеет дело в основном с рациональными числами.
Рациональным числом называется число вида:
Что мы умеем делать с этими числами?
1) Складывать и вычитать:
Если 
, то 
2) Умножать и делить:
Если 
Но в связи с изучаемыми понятиями для нас нужна следующая теорема.
Теорема. Множество рациональных чисел счетно.
Представим множество всех рациональных чисел в виде бесконечной таблицы.
Оценим, как строятся строки этой таблицы.
Первая строка – это все целые числа, расположенные по возрастанию их модуля и так, что знаки “+” и “–” чередуются.
Вторая строка – это все несократимые дроби со знаменателем 2, расположенные по возрастанию их модуля и так, что знаки “+” и “–” чередуются.
Третья строка – это все несократимые дроби со знаменателем 3, расположенные по возрастанию их модуля и так, что знаки “+” и “–” чередуются.
Вообще,n-ая строка это все несократимые дроби со знаменателем n, расположенные по возрастанию их модуля и так, что знаки “+” и “–” чередуются.
Очевидно, что в этой таблице находятся все рациональные числа. Используя снова прием диагонализации представим R в виде:
Так как R представилось в форме последовательности, то отсюда следует, что R –счетное множество.
Не нашли то, что искали? Google вам в помощь!
Доказать что множество всех рациональных чисел счетно
Случайно наткнулся на небольшую милую статью о красивом способе подсчёта рациональных чисел.
«Пересчитать» множество с помощью натуральных чисел проще всего, выстроив элементы данного множества в бесконечный ряд, и позаботившись при этом, чтобы каждый элемент в этом ряду на каком-то месте оказался. Например, пересчитать целые числа можно так:
Стандартный способ пересчёта рациональных чисел вот какой:
(ради простоты здесь и далее будем подсчитывать только положительные рациональные числа; если их можно «пересчитать» натуральными, то 0 и отрицательные к ним можно добавить при помощи того же трюка, который позволяет пересчитать целые числа)
Сначала мы выстраиваем все положительные рациональные числа в бесконечном квадрате: строки и столбцы квадрата перенумерованы натуральными числами, а внутри квадрата в каждой клетке стоит рациональное число, равное частному номера столбца и номера строки. Ясно, что каждое рациональное число находится в этом квадрате. А затем мы его пересчитываем «по диагоналям» (картинка справа), начиная с левого верхнего угла, потом диагональ размером в два числа, потом следующая итд. итд. Ясно, что двигаясь таким образом, мы рано или поздно дойдём до любого числа в квадрате, а значит, в нашем списке будут все положительные рациональные числа.
Этот стандартный способ очень прост, но у него есть эстетические недостатки: например, в этом списке есть повторы: каждое рациональное число повторяется в нём бесконечное число раз (например, 1/2 встречается также как 2/4, 4/8 итд.) Это не мешает доказательству, т.к. эти повторы можно просто выбрасывать, строя список, но тогда для общего его члена не будет красивой лёгкой формулы.
Всё это не слишком важные вопросы, и, тем не менее, красивый другой способ пересчёта рациональных чисел, описанный в прочитанной мной статье, и свободный от этих недостатков, мне очень понравился. Ничего нового он не доказывает, он просто демонстрирует красивую конструкцию, а также, при доказательстве свойств этой конструкции, силу принципа наименьшего элемента, который гласит, что в любом непустом множестве натуральных чисел есть наименьший элемент.
Принцип наименьшего элемента эквивалентен принципу математической индукции по натуральным числам. Их можно легко доказать один с помощью другого. Например, предположим, что какое-то утверждение S выполняется для числа 1, и если оно выполняется для всех k 1, то S выполняется для всех k
Итак, вот эта конструкция. Построим бесконечное дерево, в вершинах которого находятся положительые рациональные числа, следующим образом:
Например, вот несколько первых членов последовательности f(k) (из картинки выше):
1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4
А 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 в виде суммы степеней двойки, не используя каждую более чем дважды, удовлетворяет тому же определению.