как доказать что множество действительных чисел несчетно

Множество всех действительных чисел не счетно. Г. Кантор

И тем не менее несчетные множества суще­ствуют. Оказывается, множество всех дейст­вительных чисел — не счетно. Этот заме­чательный факт, как и теорема о счетности множества всех рациональных чисел, впервые в 1874 г. был доказан знаменитым немецким математиком Г. Кантором, основателем современной теории множеств.

Воспроизводим доказательст­во Кантора. Доказываем, что несчетным являет­ся уже множество всех действительных чисел интервала 1 (0; 1).

Каждое такое действительное число может быть записано в виде бесконечной десятичной дроби с целой частью нуль. При этом каждому действительному числу соответствует лишь од­на такая запись, за исключением действительных чисел, выражаемых конечными десятичны­ми дробями: каждое такое число, например 0,2476622021711, может быть записано двумя способами в виде бесконечной десятичной дроби:

Одна из этих записей начиная с некоторого момента содержит одни лишь нули, а другая— одни девятки. Если мы согласимся не употреблять записей, в которых, начиная с какого-нибудь места, идут одни девятки, то каждое действительное число будет иметь лишь един­ственную запись в виде бесконечной десятич­ной дроби. Докажем теперь теорему о несчет­ности множества действительных чисел от про­тивного: предположим, что множество дей­ствительных чисел [мы говорим все время о чис­лах X интервала (0 ; 1)] счетно, т.е. может быть занумеровано посредством натуральных чисел. Тогда вся совокупность действительных чисел интервала (0 ; 1) может быть записана в виде последовательности: х₁, х₂. Запишем разложение числа x_n в бесконечную десятичную дробь в виде:

суть последовательные десятичные знаки числа x_n, причем, согласно заключенному нами условию, не может слу­читься, что все десятичные знаки начиная с некоторого суть девятки. Итак, все действительные числа х [интерва­ла (0; 1)] предполагаются записанными в виде:
Табл: I

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

и выберем для каждого n натуральное число b_n, не превосходящее число 8 и отличное от числа a ( n) _n (например, при а ( n) _n (n) _n=8 полагаем b_n=7). Рассмотрим бесконечную десятичную дробь

то на n-м месте в разложении числа с мы должны были бы иметь цифру

тогда как действительно имеем

1 Под интервалом (а; b) числовой прямой понимает­ся множество всех действительных чисел х, удовлет­воряющих неравенству а

Источник

Пронумеровать все действительные числа на отрезке [0,1]

В качестве доказательства несчетности действительных чисел во всех учебниках по теории множеств приводится так называемый диагональный метод Кантора (подробнее можно ознакомиться в книге «Что такое математика?», авторы Курант, Роббинс, §4. Математический анализ бесконечного. 2. Счетность множества рациональных чисел и несчетность
континуума.). Данный метод доказывает несчетность подмножества действительных чисел, принадлежащих диапазону [0,1]. Однако, если присмотреться к доказательству, становится ясно, что оно не учитывает экспоненциальный рост возможных вариантов с каждым увеличиеним порядкового номера в десятичной дроби.

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

Недостаток диагонального метода

Для того, чтобы понять о чем речь, давайте попробуем рассмотреть идею диагонального метода на следующем примере. Рассмотрим конечные дроби вида: 0,a₁a₂a₃a₄a₅, сформируем из них список так, чтобы получился квадрат размером 5*5, как это показано на рисунке ниже:

Идея моего подхода

Чтобы пронумеровать все действительные числа, принадлежащие диапазону [0, 1], их надо располагать в виде экспоненциально растущего дерева. Рассмотрим десятичные дроби, записанные в двоичной системе. Пусть k – количество знаков после запятой, n – размер алфавита системы счисления. Тогда количество возможных вариантов дробей начиная с k=1 и до ∞ будет функцией от k, это видно на рисунке ниже:

Назовем каждую строку в вышеприведенной таблице – уровнем. Таким образом k – это и номер уровня, и количество знаков после запятой одновременно.

Введем два порядковых номера:

Каждая отдельная цифра в позиции десятичного числа располагается в отдельной ячейке. Напротив каждой такой цифры записываем 2 индекса C и L следующим образом: N C L, где N – значение цифры.

Cтановится очевидно, что С и L – это функции от k и цифр самого числа N: С = fC(k; N), L = fL(k; N). Также становится очевидно, что мы можем пронумеровать все числа из диапазона [0,1], т.к. мы последовательно проходим по каждому уровню и последовательно нумеруем все возможные комбинации на данном уровне.

Осталось вывести аналитическую зависимость для счетчиков C = f C (N) и L = f L (k;N).

Для удобства обозначим L(k;N) как L_k.
Будем считать, что L₀ — 1 = 0.

Если внимательно изучить таблицу, то вырисовывается следующая закономерность:
L_k = (L_k-1 — 1)*S + N + 1,
где k >= 1, N – текущая цифра в дроби, S = |<0,1>| = 2 – размер алфавита двоичной системы счисления. Запись |A| означает мощность множества A, для конечного множества – это количество элементов в нем.

Очевидно, что C содержит сумму всех комбинаций для всех предыдущих уровней плюс L числа для текущего уровня, т.е. C(N) = Σ_i∈[1,k-1]2 i + L(k; N).

Примеры

Рассмотрим произвольное число 0,0101. Его порядковый номер C(0,0101) = 2 1 + 2 2 + 2 3 + L₄ = 2 + 4 + 8 + 6 = 20.

Рассмотрим произвольное число 0,1001. Его порядковый номер C(0,1001) = 2 1 + 2 2 + 2 3 + L₄ = 2 + 4 + 8 + 10 = 24.
L₁ = (L₀ — 1)*2 + 1 + 1 = 0*2 + 1 + 1 = 2
L₂ = (L₁ — 1)*2 + 0 + 1 = (1 — 1)*2 + 0 + 1 = 3
L₃ = (L₂ — 1)*2 + 0 + 1 = (2 — 1)*2 + 0 + 1 = 5
L₄ = (L₃ — 1)*2 + 1 + 1 = (3 — 1)*2 + 1 + 1 = 10

Выводы

Таким образом мы получили алгоритм, который последовательно нумерует абсолютно все действительные числа из диапазона [0,1], при этом, если взять произвольную десятичную дробь произвольной длины, то мы можем вычислить ее уникальный прядковый номер.

Источник

Как вообразить несчетное множество?

Как известно, бесконечности бывают разных типов. Бывают счетные, бывают несчетные. Несчетные делятся на множества мощности континуум и все остальные. Счетные множества это такие, элементы которых можно упорядочить в длинный ряд и занумеровать натуральными числами. С несчетными такой фокус не удается. Тогда как же можно представить несчетное множество, в частности множество вещественных чисел [0;1)? Ответ — дерево бесконечной высоты.

Для меня несчетные множества всегда выглядели как непонятное, туманное облако символов витающее где-то на задворках мозга. Но вот недавно
облако скондесировалось в пару не слишком аккуратных, но компактных кристаллов. О них собственно и речь.
Чтобы избежать путаницы, под несчетным множеством будем подразумевать множество мощности континуум (к таким относятся вещественные числа, иррациональные числа, множество всех подмножеств натуральных чисел и другие).

Карусель

Как известно из википедии и других достоверных источников, мощность вещественных чисел отрезка [0;1) является континуумом. Вещественные числа из этого отрезка нельзя посчитать натуральными числами, т.е. сделать так чтобы одному натуральному числу соответствовало одно вещественное и наоборот. Для неверующих проведем диагональную процедуру Кантора.

Представим чисела отрезка [0,1) в двоичной системе счисления и получим набор бесконечных последовательностей единиц и нулей.

Допустим, мы упорядочили такой набор в виде бесконечного списка как на рисунке. Упорядочив, получим квадратную таблицу в каждой ячейке которой находится либо 1, либо 0. Рассмотрим ячейки располагающиеса на главной диагонали.

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

Исходя из приведенной схемы несчетное множество можно представлять в виде непрерывногенерируемых последовательностей. Инвертировали одну диагональную последовательность — вставили её в начало списка — сгенерировали новую и так далее. Такая карусель выглядит сомнительно.

Дерево

Получается, множество максимальных путей в бинарном дереве бесконечной высоты имеет мощность континуум, что эквивалентно мощности вещественных чисел отрезка [0;1).

Если вернуться к интерпретации бинарных последовательностей как двоичных дробей, то рациональные дроби вида 0,x(y) будут выглядеть в виде конечной кривулины х и бесконечной последовательности кривулин y, иррациональные числа будут выглядеть как одна бесконечная неповторяющаяся кривулина x.

Смешная загогулина

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

Для дерева конечной высоты расклад другой:
Количество путей максимальной длинны, исходящих из корня в двоичном дереве высотой N равно 2^(N-1), а количество вершин почти в два раза больше — 2^N — 1. Устремляя N к бесконечности получим, что счетная бесконечность вершин в два раза “больше” несчетной бесконечности путей.
Вот такой псевдопарадокс, иллюстрирующий работу интуиции.

Источник

1.21 Несчетные множества

Мы рассмотрели счетные множества. Примеры их можно про­должить. Кроме того, как мы показали, сумма конечного числа или счетного числа счетных множеств есть снова счетное множество. Есте­ственно возникает вопрос: «а существуют ли вообще несчетные мно­жества?». Положительный ответ на него дает следующая теорема:

Множество действительных чисел, заключенных между 0 и 1, несчетно.

Множество действительных чисел D включает в себя множество R рациональных чисел и множество Q иррациональных чисел. Любое иррациональное число можно представить бесконечной непериоди­ческой десятичной дробью.

Множество R – счетное, если мы докажем, что множество Q – несчетное, то несчетным будет и множество D.

Где Аij – J-я десятичная цифра числа AI.

Построим десятичную дробь

С помощью Диагональной процедуры Кантора, а именно: за B1 примем произвольную цифру, не совпадающую с А11; за B2 – произ­вольную цифру, не совпадающую с А22, и т. д. Вообще за BN примем произвольную цифру, не совпадающую с AMn. Построенная таким образом дробь b не совпадает ни с одной дробью a. От a1 она отли­чается по крайней мере первой цифрой, от a2 – по крайней мере второй цифрой и т. д.

Таким образом, никакое счетное множество иррациональных (действительных) чисел, лежащих на отрезке [0; 1], не исчерпывают этого отрезка. Следовательно, множество иррациональных чисел и мно­жество действительных чисел на отрезке [0; 1] является несчетным.

Любые множества, эквивалентные отрезку [0; 1], являются Несчетными:

1. Множество всех точек любого отрезка [ А; B ].

2. Множество всех точек прямой.

3. Множество всех прямых на плоскости.

4. Множество всех непрерывных функций одной или нескольких переменных и т. д.

Источник

счетность множества действительных чисел, 1-ая проблема Гильберта

Новичок

Метрическая схема доказательства счетности действительных чисел.

Регистрационный номер: №243 В-2008 от 25.03.2008г.

В данной работе приводится метрическая схема доказательства счетности действительных чисел (N↔R).. Поскольку каждому действительному числу от 0 до 1 соответствует точка отрезка [0, 1], мы будем называть точки отрезка числами.

↔ эквивалентно (равномощно)
→ знак соответствует
N множество натуральных чисел
R множество действительных чисел
[0, 1] отрезок от 0 до 1
+ операция объединения

Возьмем любое натуральное число n большее 0 и 1. Пусть это будет число 2. Схема подходит для любого натурального числа: достаточно вместо числа 2 подставить любое другое натуральное число большее 0 и 1. Далее разобьем отрезок на две части (необязательно равные). Для наглядности будем в дальнейшем разбивать на равные части. Каждый из получившихся отрезков снова разобьем на 2 части и т.д. В результате получим следующую последовательность систем отрезков:

А1= ([0, 1/2]; [1/2, 1]) – 1-ый этап,
А2 = ([0, 1/4]; [1/4, 2/4]; [2/4, 3/4]; [3/4, 1]) – 2-ой этап,
:
Аn= ([0, 1 / 2^n]; … [2^n – 1 / 2^n, 1]) – n-ый этап
и т.д.

1. При стремлении n к бесконечности концы отрезка имеют пределом одно и то же действительное число x (отрезок стягивается в точку).

2. Длина этого отрезка стремится к 0, при стремлении n к бесконечности.

Счетность множества действительных чисел.

Если мы устремим n к бесконечности, то отрезок [m / 2^n, m+1 / 2^n] будет иметь своим пределом отрезок типа [x, x], где число x лежит между 0 и 1 (0≤ x ≤1) по построению. С другой стороны, для любого x (0≤ x ≤1) каждый отрезок типа [x, x] будет результатом стягивания концов одного из отрезков в построении, так как на каждом этапе n система отрезков An полностью покрывает отрезок [0, 1]:

В доказательстве мы опирались на понятие длины отрезка (метрическое понятие). Поэтому построение носит название метрической схемы.

О ложности метода Кантора.

0, а1; 0, а1,а2; 0, а1,а2,а3…→ х *

В доказательстве о несчетности Кантор отождествляет последовательность и ее предел, записывая это так: 0, а1, а2, а3, … (!)
Метод Кантора, примененный к системе А, дает последовательность, которая будет последовательностью выше указанного типа (*). Ее пределом будет некоторое число х отрезка [0, 1]. Но для этого числа х уже есть сходящаяся к нему последовательность (по разбиению). Таким образом, чтобы доказать свое предположение о несчетности действительных чисел, Кантор допускает две ошибки:

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

2. Построенная методом Кантора последовательность дублирует одну из исходных т.е. принадлежит А (см. построение А).

1. Доказана счетность множества действительных чисел метрическим способом (способ разбиения отрезка на части).
2. Указано на ошибки в доказательстве Кантора о несчетности с метрической точки зрения.

Источник