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

Теорема: множество рациональных чисел является счётным.

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

1 строка: 1 2 3 4 5 6 7 .

2 строка: ½ 2/2 3/2 4/2 5/2 6/2 7/2 .

3 строка: 1/3 2/3 3/3 4/3 .

Таким образом, будет записано каждое положительное число. Например, число 7/31 будет записано в 31-й строке в 7-м столбце. Вообще, дробь m/n будет записана в n-й строке m-м столбце.

Для установления взаимно-однозначного соответствия теперь уже нельзя переходить от столбца к столбцу, потому что в каждом столбце содержится бесконечное множество элементов. Для доказательства этой теоремы будем использовать диагональный метод Кантора. Он заключается в том, что мы подходим к каждому рациональному числу и, следовательно, каждому рациональному числу будет поставлено в соответствие какое-либо натуральное число.

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

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

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

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

Но это предположение противоречиво. В самом деле, построим вещественное число , где цифры подобраны так, чтобы и . Ясно, что , однако не совпадает ни с одним из чисел , так как иначе должно было бы быть , что не имеет места.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Сдача сессии и защита диплома – страшная бессонница, которая потом кажется страшным сном. 8912 – | 7222 – или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

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

Чтобы установить взаимно однозначное соответствие, необязательно пересчитывать элементы множеств. Например, мы знаем, что американские штаты находятся во взаимно однозначном соответствии с их столицами, хотя можем оставаться в неведении относительно общего их числа. Мы могли бы утверждать: «Столиц штатов ровно столько, сколько штатов».

Конечное множество состоит из конечного числа элементов, например, множество страниц в книге, множество студентов в группе и т.д.

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

Читайте также:  Майнинг биткоинов на процессоре

Мощностью конечного множества называется количество его элементов. Мощность множества A обозначается m (A).

В теории множеств, счётное мно́жество есть бесконечное множество, элементы которого возможно пронумеровать натуральными числами. Более формально: множество <displaystyle X> является счётным, если существует биекция <displaystyle Xleftrightarrow mathbb > , где <displaystyle <mathbb >> обозначает множество всех натуральных чисел. Другими словами, счётное множество — это множество, равномощное множеству натуральных чисел.

1. Любое подмножество счётного множества не более чем счётно (т.е. конечно или счётно). [1]

2. Объединение конечного или счётного числа счётных множеств счётно. [1]

3. Прямое произведение конечного числа счётных множеств счётно.

4. Множество всех конечных подмножеств счётного множества счётно.

5. Множество всех подмножеств счётного множества континуально и, в частности, не является счётным.

2.2 Свойства счётных множеств

Лемма 1. Объединение двух счётных множеств счётно.

Доказательство. Рассмотрим два счетных множества A и B; каждое из них можно записать в последовательность: a0, a1, a2, a3, . . . b0, b1, b2, b3, . . . Теперь нетрудно перечислить и элементы множества A ∪ B, чередуя элементы из A с элемен- тами из B: a0, b0, a1, b1, a2, b2, . . . . Если A и B не пересекаются, то на этом рассуждение заканчивается — но если пересекаются, то в этой последовательности общие элементы встретятся по два раза. Как это исправить? Если очередной элемент уже встречался ранее (например, если элемент aj совпадает с элементом bi , где i

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

Доказательство. Нам будет удобнее доказать отдельно, что множество неотрицательных ра- циональных чисел счётно и что множество отрицательных рациональных чисел счётно. Тогда счётность множества всех рациональных чисел сразу вытекает из леммы 1. Проведем рассуждение для неотрицательных рациональных чисел. Для отрицательных чи- сел рассуждение аналогично (а можно заметить, что смена знака даёт биекцию между отрица- тельными и положительными числами, а к положительным рациональным числам применить лемму 2). 5 Неотрицательное рациональное число задается парой чисел — числителем и знаменателем. Числитель может быть произвольным натуральным числом, а знаменатель произвольным положительным натуральным числом.

Выпишем все такие числа в виде таблицы, бесконечной вниз и вправо:

В строке с номером i этой таблицы стоят последовательно все числа со знаменателем i, а в столбце с номером j — все числа с числителем j. В этой таблице будут выписаны все рациональ- ные числа, причем некоторые будут повторяться много раз (например, 0/1 = 0/2 = 0/3 = . . . и 1/2 = 2/4 = 3/6 = . . .). Числа из этой таблицы теперь уже легко выписать в последовательность. Например, можно идти по диагоналям (вниз-влево). Сначала выпишем единственное число на первой диагонали (0/1), потом два числа на второй (1/1, 0/2), потом три числа на третьей и так далее: 0/1, 1/1, 0/2, 2/1, 1/2, 0/3, 3/1, 2/2, 1/3, 0/4, . . . . Другими словами, мы сначала выписываем все числа с суммой числителя и знаменателя 1, потом — с суммой 2, потом 3 и так далее. Конечно, нужно не забыть выбрасывать из последо- вательности повторяющиеся члены. То есть, когда мы доходим в таблице до очередного числа и видим что равное ему уже было выписано, мы пропускаем текущее число и переходим к следующему. Получится такая последовательность рациональных чисел: 0, 1, 2, 1/2, 3, 1/3, . . . . В этом доказательстве на самом деле не имеет значения, что именно мы записываем в бесконечную вправо и вниз таблицу: верно такое общее утверждение.

Читайте также:  Магнитный провод usb type c

Теорема 1. Объединение конечного или счётного числа конечных или счётных множеств конечно или счётно.

Доказательство. Пусть есть счётное количество счётных множеств A0, A1, A2, . . .. Как и в прошлой лемме, расположим их элементы в виде таблицы:

A0 : a00 a01 a02 a03 . . .

A1 : a10 a11 a12 a13 . . .

A2 : a20 a21 a22 a23 . . .

A3 : a30 a31 a32 a33 . . . . . . . . . . . . . . . . . . . . . . Здесь в первой строке мы последовательно выписали элементы A0, во второй — элементы A1 и так далее. Теперь снова соединяем эти последовательности в одну, идя по диагоналям: a00, a01, a10, a02, a11, a20, a03, a12, a21, a30, . . . . При этом нужно следить, чтобы члены последовательности не повторялись: когда мы рассматриваем очередной элемент таблицы, нужно проверить, не встретился ли он раньше. Если он уже был, его нужно пропустить. Мы предполагали, что все Ai счётны и что их счётное число. Если самих множеств лишь конечное число, или если какие-то из множеств конечны, то в таблице часть ячеек окажется пустой. Соответственно, мы будем их пропускать при составлении последовательности. В результате либо получится бесконечная последовательность, и тогда объединение счётно, либо получится только конечная последовательность — и тогда объединение конечно. 6 По существу ту же теорему можно сформулировать иначе:

Теорема 2. Декартово произведение двух счётных множеств A × B cчётно.

Доказательство. В самом деле, по определению декартово произведение есть множество всех упорядоченных пар вида ha, bi, в которых a ∈ A и b ∈ B. Разделим пары на группы, объединив пары с одинаковой первой компонентой (каждая группа имеет вид ×B для какого-то a ∈ A). Тогда каждая группа счётна, поскольку находится во взаимно однозначном соответствии с B (пара определяется своим вторым элементом), и групп столько же, сколько элементов в A, то есть счётное число.

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

Доказательство. Рассмотрим сначала положительные рациональные числа . Назовем натуральное число высотой рационального числа . Пусть – множество всех рациональных чисел с высотой, равной . Множества состоят из конечного числа элементов (рациональных чисел), например

.

Легко видеть, что ,

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

.

Так как рациональных положительных чисел бесконечно много, то мы используем все натуральные числа. Значит, счетно. Далее, очевидно, что счетно. Поэтому все множество рациональных чисел также счетно.

Теорема 2.Множество всех действительных чисел несчетно.

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

Читайте также:  Лучшие платные сайты знакомств для серьезных отношений

Но это предположение противоречиво. В самом деле, построим вещественное число , где цифры подобраны так, чтобы и . Ясно, что , однако не совпадает ни с одним из чисел , так как иначе должно было бы быть , что не имеет места.

Мощность множества — это обобщение понятия количества (числа элементов множества), которое имеет смысл для всех множеств, включая бесконечные. Существуют бо́льшие, есть ме́ньшие бесконечные множества, среди них счётное множество является самым маленьким.

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

Определение

Пусть даны два множества $ A $ и $ B. $ Тогда они называются равномощными, если между ними существует биекция $ f:A leftrightarrow B $ . Из свойств биекции следует, что равномощность является отношением эквивалентности. Мощностью или кардинальным числом множества $ A $ называется соответствующий ему класс эквивалентности. Мощность множества обозначается $ |A| $ . Тот факт, что два множества равномощны, записывается: $ |A| = |B|. $

Связанные определения

  • Множество $ A $ называется конечным, если оно равномощно множеству $ <1,ldots,n>$ для некоторого $ nin mathbb. $ Мощность такого множества идентифицируют с количеством его элементов: $ |A| = n. $ Таким образом по определению два конечных множества равномощны тогда и только тогда, когда они имеют одно и то же количество элементов.
  • Множество $ A $ называется бесконечным, если оно не является конечным.
  • Множество $ A $ называется счётным, если оно равномощно множеству натуральных чисел $ N $ . Мощность счётного множества обозначается $ aleph_0. $
  • Множество $ A $ называется не более чем счётным, если оно конечно или счётно.
  • Множество $ A $ называется несчётным, если оно бесконечно и не является счётным.

Свойства

  • Если $ A $ конечно, и $ 2^A $ – его булеан, то $ left| 2^A
    ight| = 2^<|A|>. $
  • Множество является бесконечным тогда и только тогда, когда оно содержит подмножество равномощное себе.
  • В предположении выполненности аксиомы выбора любое бесконечное множество содержит счётное подмножество.
  • Декартово произведение бесконечного множества $ A $ с самим собой равномощно $ A. $

Упорядочение кардинальных чисел

Будем предполагать, что выполнена аксиома выбора. Будем писать, что $ |A|le |B|, $ если существует инъекция $ f:A o B. $ Введённое таким образом бинарное отношение на мощностях множеств не зависит от выбора представителей обоих классов эквивалентности и обладает следующими свойствами:

  • (Теорема Кантора — Бернштейна.) $ igl( |A| le |B| igr) wedge igl( |B| le |A| igr) Rightarrow igl( |A| = |B| igr); $
  • (Теорема Цермело.) $ forall A,Bquad igl(|A| le |B| ) vee igl( |B| le |A|). $

Таким образом введённое отношение $ le $ является полным порядком на семействе мощностей. Следуя общей практике, будем также использовать строгое неравенство:

Теорема Кантора

Пусть $ A $ – произвольное множество, а $ 2^ $ – его булеан. Тогда

В частности множество вещественных чисел, будучи равномощным множеству подмножеств натуральных чисел, является несчётным.

Континуум-гипотеза

Обобщённая континуум-гипотеза утверждает, что неравенство в теореме Кантора плотное, то есть для любого бесконечного множества $ A $ не существует множества $ B $ такого, что

Это означает, что мощности множеств могут быть выписаны в виде возрастающей последовательности

  • $ aleph_0 $ – мощность счётных множеств,
  • $ aleph_1 $ – мощность множества вещественных чисел.

Читайте также:

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock detector