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

Числовые множества (стр. 2 )

Из за большого объема этот материал размещен на нескольких страницах: 1 2 3

На третьей строке – по три числа на каждое кубическое уравнение соотв. упорядоченным четверкам и т. д.

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

Факт эффективной перечислимости множества А напрямую следует из приведенного способа нумерации элементов натуральными числами, т. к. попутно указана эффективная процедура нумерации наборов рациональных чисел, однозначно задающих алгебраические уравнения соответствующей степени. При этом важно то, что алгебраическое уравнение n-ой степени имеет эффективный алгоритм решения, т. о. процедура полностью эффективна. Итак, множество алгебраических действительных чисел счетно и эффективно перечислимо, Q. E.D.

Счетными также будут множества, составленные из всех пар, троек, и т. д. алгебраических чисел.

2.3.7. Счетные числовые множества: обобщение

Т.2Теорема (без доказательства)

Множество элементов, которые можно представить с помощью конечного числа счетной системы знаков, счетно.

В реальной жизни мы используем различные конечные системы знаков, например цифры, буквы, ноты.

Рассмотрим систему знаков, например, числа в любой конечной системе счисления, допустим десятичной. Имея 10 знаков в нашем распоряжении: 0,1,2,3,4,5,6,7,8,9 мы можем составлять два типа множеств: фиксированной длины и произвольной длины.

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

Можно обобщить, что полученное в результате применения Теоремы 2.3.(7) множество будет счетно-бесконечно, если в случае конечной системы знаков допустить сколь угодно длинные комплексы знаков (сколько угодно длинные, но при этом все равно конечные!).

Счетно-бесконечными являются, например:

· множество всех книг, написанных на любом или даже на всех языках,

· множество всех симфоний и т. д.

§ 2.4. Несчетные множества

2.4.1. Несчетность множества действительных чисел (континуума)

Множество действительных чисел обозначим латинской буквой R.

Т.2Теорема

Множество действительных чисел несчётно.

Из того факта, что R2 – счетное, напрямую следует, что возможен какой-либо способ перечисления его элементов для установления взаимно-однозначного соответствия между элементами R2 и элементами множества натуральных чисел. Это следует из самого определения мощности множества, согласно которому предполагается, что в равномощных множествах каждый элемент одного множества имеет парный элемент из другого множества и наоборот. Обратите внимание, фундаментальное отличие данного определения от определения эффективной перечислимости состоит в том, что в данном случае мы даже не говорим о наличии какого-либо алгоритма перечисления, мы просто утверждаем, что можно привести список действительных чисел из множества R2 и список соответствующих им натуральных чисел из множества N. Алгоритм построения связи N ↔ R2 нас в данном случае не интересует, достаточно того, что такое соответствие возможно.

Построим такой список чисел из множества R2 и пронумеруем числа в разрядах:

Теперь построим число b=0.b1b2…, причём

bi=aii+1, где + обозначает операцию сложения, результатом которого не могут быть числа 0 и 9, т. е. если aii=1, то bi=2; если аii=2, то bi=3, …., если aii=8, то bi=1).

Так как множество R2 является по условию подмножеством множества R1, то R1 – несчетно, а т. к. R1 несчетно – то значит и множество R несчётно, Q. E.D.

Примечание: можно и не выбрасывать числа, содержащие 0 и 9. Таким образом, в наш ряд некоторые числа войдут дважды. Это связано с тем, что конечные дроби могут быть превращены в бесконечные. Например ½=0,5=0,5(0)=0,4(9).

В общем случае это могло стать причиной того, что не удалось сосчитать множество действительных чисел. Но множество чисел, представимых двояким образом (конечные дроби) – это множество рациональных чисел. Как было доказано ранее, их счетное количество. Можно даже показать, что это множество эффективно перечислимо. Т. о. даже двойное представление множества таких чисел образует счетное множество, следовательно, доказательство верно даже без такого упрощения.

Алеф (À) – второе трансфинитное число. По определению это мощность континуума (всех действительных чисел). Это вторая по величине бесконечная мощность. Доказанная только что Теорема 2.4.(1) о несчетности множества действительных чисел является убедительным доказательством того, что мощность этого множества больше, чем алеф-ноль (больше множества натуральных чисел). И это весьма важный результат после череды доказательства счетности разнообразных множеств чисел.

Если оперировать понятием кардинального числа (мощности), то получим, что, так как каждое число сегмента (0,1) может быть представлено десятичной дробью вида 0.a1a2a3… не менее одного раза и не более двух, то:

а т. к. 2À=À, то получим что 10 À0= À. Те же рассуждения справедливы в случае, если мы будем разлагать числа не в десятичные, а, например, в двоичные дроби, дроби с основанием 3, 15, 10005 или даже À0 (если вы можете такое себе представить).

Т. о. À =2À0=3À0=…=10À0=…nÀ0=…À0À0

Для À0- мерного действительного пространства или множества всех последовательностей действительных чисел счетной длины с точки зрения операций над кардинальными числами получим ÀÀ0=(2À0)À0=2À0∙À0=2À0=À.

В этом месте интересно будет обратиться к историческим событиям, связанным с чередой доказательств в этой сфере. С тем, что на бесконечной прямой столько же точек, сколько и на отрезке, математики, хотя и не сразу, но в итоге примирились. Но следующий результат Кантора оказался еще более неожиданным. В поисках множества, имеющего больше элементов, чем отрезок на действительной оси, он обратил внимание на множество точек квадрата. Изначально сомнений в результате не было: ведь отрезок целиком размещается на одной стороне квадрата, а множество всех отрезков, на которые можно разложить квадрат, само по себе имеет ту же мощность, что и множество точек отрезка. На протяжении почти трех лет (с 1871 по 1874) Кантор искал доказательство того, что взаимно однозначное соответствие между точками отрезка и точками квадрата невозможно. И в какой то момент совершенно неожиданно получился прямо противоположный результат: ему удалось построить соответствие, которое он искренне считал невозможным. Кантор не верил сам себе и даже написал немецкому математику Рихарду Дедекинду: «Я вижу это, но не верю этому». Когда шок от этого факта прошел, стало интуитивно понятно и вскоре доказано, что и куб имеет столько же точек, сколько отрезок. Вообще говоря, любая геометрическая фигура на плоскости (геометрическое тело в пространстве), содержащая хотя бы одну линию, имеет столько же точек, сколько отрезок. Такие множества назвали множествами мощности континуума (от латинского continuum – непрерывный). Следующий шаг почти очевиден: размерность пространства в определенных пределах несущественна. Например, 2-х мерная плоскость, 3-х мерное привычное пространство, 4-х, 5-ти и далее n-мерные пространства с точки зрения количества точек, содержащихся в соответствующем n-мерном теле, равномощны. Такая ситуация будет наблюдаться даже в случае пространства с бесконечным количеством измерений, важно только чтобы это количество было счетным.

На данном этапе обнаружены два типа бесконечностей и соответственно два трансфинитных числа, обозначающих их мощности. Множества первого типа имеют мощность, эквивалентную мощности натуральных чисел (алеф-ноль). Множества второго типа имеют мощность, эквивалентную количеству точек на действительной оси (мощность континуума, алеф). Показано, что во множествах второго типа элементов больше, чем во множествах первого типа. Естественно, возникает вопрос – а нет ли в природе «промежуточного» множества, которое имело бы мощность больше чем количество натуральных чисел, но при этом меньше, чем множество точек на прямой? Этот непростой вопрос получил название «проблема континуума». Она же известна как «континуум-гипотеза» или «первая проблема Гильберта». Точная формулировка звучит следующим образом:

Континуум-гипотеза: с точностью до эквивалентности, существуют только два типа бесконечных числовых множеств: счетное множество и континуум.

Иначе говоря, гипотеза предполагает, что не существует множества промежуточной мощности, т. е. такого множества X, X , которое не эквивалентно ни , ни . Этой проблемой занимались очень многие математики. Сам Георг Кантор неоднократно заявлял, что доказал эту гипотезу, но всякий раз находил у себя ошибку.

Название «первая проблема Гильберта» относится к публикации Давидом Гильбертом на II Международном Конгрессе математиков в Париже в 1901 году списка из 23 кардинальных проблем математики. Тогда эти проблемы не были решены, позднее окончательное решение получили 16 проблем из 23.

В результате после долгих исследований по вопросу континуум-гипотезы в 1938 году немецкий математик Курт Гедёль доказал, что существование промежуточной мощности не противоречит остальным аксиомам теории множеств. И позднее, в гг. почти одновременно, но независимо друг от друга, американский математик Коэн и чешский математик Вопенка показали, что наличие такой промежуточной мощности не выводимо из остальных аксиом теории множеств. Кстати, интересно заметить, что этот результат очень похож на историю с постулатом о параллельных прямых. Как известно, две тысячи лет его пытались вывести из остальных аксиом геометрии, но только после работ Лобачевского, Гильберта и других удалось получить тот же результат: этот постулат не противоречит остальным аксиомам, но и не может быть выведен из них.

2.4.2. Множества комплексных, трансцендентных и иррациональных чисел

Приведем в дополнение к множеству действительных чисел еще несколько несчетных множеств.

Комплексное число задается парой (r1, r2), где r1, r2 принадлежат множеству действительных чисел.

Множество комплексных чисел обозначим латинской буквой С.

Т.2.4.(2) Теорема

Множество комплексных чисел несчетно.

Так как множество действительных чисел R, несчётное по доказанной ранее Теореме 2.4.(1), является подмножеством множества комплексных чисел С, то множество комплексных чисел также несчётно, Q. E.D.

Иррациональным называется действительное число, не являющееся рациональным.

Множество иррациональных чисел обозначим латинской буквой I.

Т.2.4.(3) Теорема

Множество иррациональных чисел несчетно.

Поскольку действительных чисел – несчетное множество, а рациональных – счетное, то иррациональных чисел – несчетное множество, Q. E.D.

Множество трансцендентных чисел обозначим латинской буквой Т. Каждое трансцендентное действительное число является иррациональным, но обратное неверно. Например, число иррациональное, но не трансцендентное: оно является корнем уравнения x2 − 2=0.

Т.2Теорема

Множество трансцендентных чисел несчетно.

Поскольку действительных чисел – несчетное множество, а алгебраических – счетное, и при этом множество A является подмножеством R, то R \ А (множество трансцендентных чисел) представляет собой несчетное множество, Q. E.D.

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

Важно отметить, что долгое время математики имели дело лишь с алгебраическими числами. Потребовались значительные усилия, чтобы найти хотя бы несколько трансцендентных чисел. Впервые это удалось французскому математику Лиувиллю в 1844 году, который доказал набор теорем, позволяющий строить конкретные примеры таких чисел. Например, трансцендентным числом является число 0,…, в котором после первой единицы стоит один нуль, после второй – два, после третьей – 6, после n-ой соответственно n! нулей.

Квадратура круга — задача, заключающаяся в нахождении построения с помощью циркуля и линейки квадрата, равновеликого по площади данному кругу.

Наряду с трисекцией угла (разбиение произвольного угла на три равные части) и удвоением куба (построение отрезка, являющегося ребром куба в два раза большего объёма, чем куб с данным ребром), эта задача является одной из самых известных неразрешимых задач на построения с помощью циркуля и линейки. В такого рода задачах на построение циркуль и линейка считаются идеальными инструментами, при этом, в частности линейка не имеет делений и имеет только одну сторону бесконечной длины, а циркуль может иметь сколь угодно большой раствор. Напомним, что отношение длины окружности к ее диаметру есть величина постоянная, не зависящая от радиуса круга, именно она обозначается буквой π. Таким образом, длина окружности круга радиуса r равна 2πr, а площадь круга равна S =1/2πr2. Если принять за единицу измерения радиус круга и обозначить x длину стороны искомого квадрата, то задача сводится к решению уравнения: x2 = π, откуда: . Как известно, с помощью циркуля и линейки можно выполнить все 4 арифметических действия и извлечение квадратного корня. Это означает, что квадратура круга возможна в том и только в том случае, если с помощью конечного числа таких действий можно построить отрезок длины π. Таким образом, неразрешимость этой задачи следует из неалгебраичности (трансцендентности) числа π. Собственно задача о квадратуре круга сводится к задаче построения треугольника с основанием πr и высотой r. Для него потом уже без труда может быть построен равновеликий квадрат.

В упоминаемом ранее списке из 23 кардинальных проблем математики под номером 7 шла проблема, касающаяся трансцендентности чисел, образованных определенным образом.

В 1934 году советский математик Гельфонд и чуть позже немецкий математик Шнайдер доказали справедливость этого утверждения, и таким образом, эта проблема была решена.

С принципом деления чисел на рациональные и иррациональные связаны еще два занимательных факта, не сразу воспринимаемые как истинные.

Т.2.4.(5) Теорема

Между любыми двумя различными рациональными числами всегда найдется множество иррациональных чисел мощности континуума.

В целом данная теорема интуитивно кажется вполне логичной. Следующая, на первый взгляд, воспринимается скептически.

Т. 2.4.(6) Теорема

Между любыми двумя различными иррациональными числами всегда найдется счетное множество рациональных чисел.

Существует довольно тесная связь между построенным множеством функций и булеаном множества А (множеством всех подмножеств А). Рассмотрим множество В всех подмножеств множества А. Пусть С – некоторое подмножество в А. Возьмем функцию f(x), принимающую значении 1, если х принадлежит С, и значение 0 в противном случае. Таким образом, разным подмножествам С соответствуют различные функции. Наоборот, каждой функции f(x), принимающей два значения 0 и 1, соответствует подмножество в А, состоящее из тех элементов х, в которых функция принимает значение 1. Таким образом, установлено взаимно-однозначное соответствие между множеством функций, заданных на множестве А и принимающих значения 0 и 1, и множеством всех подмножеств в А.

§ 2.5. Множества с мощностью, больше чем мощность континуума

Итак, множества самой большой мощности не существует. Первые два трансфинитных числа имели в природе образующие их множества (множество натуральных чисел и множество действительных чисел). Если отталкиваться от множества континуума, то можно построить множество всех подмножеств континуума, получим его булеан, назовем это множество BR. По определению мощность множества BR равна 2À. Согласно теореме Кантора 2À≠À. Очевидно что множество BR бесконечно, следовательно, его кардинальное число является числом трансфинитным и оно никак не может совпадать ни с одним из двух рассмотренных ранее трансфинитных чисел. А значит, в нашу шкалу пора вводить третье трансфинитное число.

Алеф-один (À1) – третье трансфинитное число. По определению, это мощность множества всех подмножеств континуума. Это же число соответствует мощности многих других множеств, например:

· Множества фигур на плоскости, т. е. множества всех подмножеств точек на плоскости или множества всех подмножеств пар действительных чисел.

· Множества тел в обычном трехмерном пространстве, а также, вообще говоря, в любом счетно-мерном пространстве, где количество измерений n – любое конечное число или даже À0.

Поскольку число À1 вводится как мощность булеана множества с мощностью À, получаем утверждение, что À1 =2À.

§ 2.6. Парадоксы теории множеств

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

Хотя нами показано, что наибольшего трансфинитного числа не существуют, как показывают исследования, восходить всё далее и далее к новым большим кардинальным числам небезопасно – это приводит к антиномии (парадоксам). Действительно, каково бы ни было множество кардинальных чисел, всегда можно найти кардинальное число, большее, чем все числа данного множества и, следовательно, не входящее в него. Т. о. ни одно такое множество не содержит все кардинальные числа и множество всех кардинальных чисел немыслимо.

Вполне естественно, что каждому математику хочется иметь дело с непротиворечивой теорией, т. е. такой, что в ней нельзя одновременно доказать две теоремы, явно отрицающие друг друга. Является ли теория Кантора непротиворечивой? До каких пределов можно расширять круг рассматриваемых множеств? К сожалению, не все так безоблачно. Если ввести такое внешне безобидное понятие как «множество всех множеств U», то возникает ряд любопытных моментов.

Т.2.6.(1) Парадокс Кантора

Кардинальное число множества всех подмножеств P(U) множества всех множеств U не больше чем |U|.

Так как U содержит все мыслимые и возможные множества, то оно по логике вещей, содержит в частности и множество всех своих подмножеств. Более того, все элементы множества P(U) принадлежат U, следовательно, |P(U)| ≤ |U|. Однако существует доказанная ранее Теорема Кантора 2.4.(7), согласно которой для любого кардинального числа α справедливо α |U|. Два полученных вывода |P(U)| ≤ |U| и |P(U)| > |U| прямо противоречат друг другу, что в принципе не должно быть возможно и является иллюстрацией парадокса, Q. E.D.

Т.2.6.(2) Парадокс Рассела

Пусть В – множество всех множеств, которые не содержат самих себя в качестве своих собственных элементов. Тогда можно доказать две теоремы.

Предположим противное, т. е. В не принадлежит В. По определению, это означает, что В принадлежит В. Получили противоречие – следовательно, исходное предположение неверно и В принадлежит В, Q. E.D.

В не принадлежит В.

Предположим противное, т. е. В принадлежит В. По определению множества В любой его элемент не может иметь себя в качестве собственного элемента, следовательно, В не принадлежит В. Противоречие – следовательно, исходное предположение неверно и В не принадлежит В, Q. E.D.

Нетрудно видеть, что Теоремы 2.6.(2).1. и 2.6.(2).2. исключают друг друга.

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

Уже при выводе парадокса используется логический закон исключенного третьего, являющийся одним из неотъемлемых приемов рассуждений в классической математике (т. е. если истинно утверждение не-А, то ложно А). Если задуматься о сути вещей, то можно в целом уйти и от теории множеств, и от математики в целом.

Т.2.6.(3) Парадокс

Пусть Р – некоторое свойство. Обладает ли само Р этим свойством Р?

Интересная постановка, не правда ли? Например, свойство быть сладким не применимо само к себе, потому что свойство быть сладким само по себе не сладкое. Зато свойство быть абстрактным, будучи абстрактным, разумеется, абстрактно, т. е. применимо само к себе. Дадим следующее определение.

Источник

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

И тем не менее несчетные множества суще­ствуют. Оказывается, множество всех дейст­вительных чисел — не счетно. Этот заме­чательный факт, как и теорема о счетности множества всех рациональных чисел, впервые в 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) числовой прямой понимает­ся множество всех действительных чисел х, удовлет­воряющих неравенству а

Источник