Мощность множества дискретная математика

Некоторые сведения о мощности множества приведены в [I]. Здесь мы рассмотрим это понятие более подробно.

Множество А равномощно множеству И, если существует биекцил f:A→B.

Из того, что существует биекция f:A→B, следует, что соответствие f -1 есть биекция В на А (см. 1,4). Поэтому если А равномощно В, то и В равномощно A, и мы можем говорить, что множества АиВ равномощны.

Факт равномощности множеств А и В будем записывать так: А

Из определения равномощности и свойств биекции также следует, что для любого множества А имеет место А

А (тождественное отображение есть биекция множества А на себя); а для любых множеств А, В, С из А

С (композиция биекций есть биекция).

Таким образом, отношение равномощности множеств есть отношение эквивалентности*, заданное на „множестве всех множеств" (на самом деле на множестве всех подмножеств некоторого универсального множества).

*Зачастую в литературе по теории множеств равномощные множества и называют „эквивалентными множествами". Однако следует различать общее понятие отношения эквивалентности и его частный случаи — эквивалентность, или равномощность, множеств.

Если мы обозначим через |А| класс эквивалентности множества А по отношению

, то утверждение о равномощности множеств Аи В можно записать так: |А| = |В|.

Этот класс эквивалентности |А| называют мощностью множества А.

Конечные множества А = <а1. аn> и В = 1 . bn> равномощны тогда и только тогда, когда множества А и В состоят из одного и того же числа элементов, т.е. n = m. Отсюда, в частности, следует, что конечное множество не является номощным никакому своему собственному подмножеству. Это свойство конечных множеств можно сформулировать так.

Теорема 1.8. Если А — конечное множество и f:A→B → А — инъекция, то она является сюръекцией и, следовательно, биекцией. #

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

Перейдем теперь к исследованию мощности бесконечных множеств. Таковы хорошо известные нам числовые множества ℕ, ℤ, ℚ, ℝ и ℂ.

Любое множество, равномощное множеству всех натуральных чисел, называют счетным. Мощность счетного множества обозначают ℵ (читается „алеф нуль").

Любую биекцию v: ℕ → М называют нумерацией счетного множества М; если элемент М есть v(n) для некоторого n ∈ ℕ, то этот элемент М обозначаем через an, называя туральное число n номером элемента an относительно данной нумерации v.

Таким образом, элементы счетного множества можно перенумеровать, записав их в виде последовательности а1. аn, . или n>n∈ℕ Другими словами, счетное множество есть область значений некоторой функции натурального аргумента.

Пример 1.21. а. Множество всех нечетных натуральных чисел счетно. Нумерацию v можно задать так: v(n) = 2n — 1,

б. Множество всех натуральных чисел, делящихся на заданное число k ≥ 2, счетно. Нумерацию v можно задать так: v(n) = kn, n∈ℕ. В частности, при k = 2 получаем, что множество всех четных чисел счетно. Этот и предыдущий примеры показывают, что бесконечное (счетное) множество может иметь собственное равномощное ему подмножество.

в. Множество ℤ всех целых чисел счетно. Нумерацию можно установить так:

Рассмотрим свойства счетных множеств.

Теорема 1.9. Любое бесконечное множество содержит счетное подмножество.

◀ Пусть М — бесконечное множество. Значит, оно не пусто и существует элемент а1 ∈ М. Положим М1 = М 1>. Множество М1 не пусто, так как в противном случае имело бы место равенство М = i>, что противоречит предположению о бесконечности М. Выберем элемент а2 ∈ М1 и положим М2 = М12> = М 1, а2>. Множество М2 также не пусто, поскольку иначе мы бы имели М = 1, а2> и множество было бы конечным.

Методом математической индукции можно показать, что для любого n ≥ 1 множество Мn = M 1. an>, где а1 ∈ М, . an ∈ Мn-1, не пусто. Тогда существует элемент an+1 ∈ Мn и an+1 ∉ Mn+1 = Мnn+1>. Таким образом, все элементы an, n ∈ ℕ, попарно различны и множество <аn:n ∈ ℕ> счетно, а его нумерация может быть задана так: v(n) = аn.

Теорема 1.10. В любом бесконечном множестве можно выделить два не пересекающихся между собой счетных подмножества.

Читайте также:  Модели телефонов поддерживающие беспроводную зарядку

◀ Разобьем множество натуральных чисел на два подмножества: ℕ1 = (множество нечетных чисел), и ℕ2 = (множество четных чисел). Оба эти множества счетны (см. пример 1.21).

Согласно теореме 1.9, бесконечное множество содержит некоторое счетное подмножество А. Пусть установлена некоторая его нумерация. Разобьем это подмножество на два подмножества: всех элементов с четными и всех элементов с нечетными номерами. По построению эти подмножества не пересекаются и являются счетными, поскольку счетны множества четных и нечетных чисел. >

Теорема 1.11. Любое подмножество счетного множества конечно или счетно.

◀ Пустое подмножество конечно по определению. Пусть М — счетное множество, а В — его некоторое непустое подмножество. Поскольку множество М счетно, можно считать, что задана некоторая его нумерация. Следовательно, каждый элемент подмножества В имеет свой номер. Запишем номера элементов множества В в порядке возрастания: i1, . in, .

Если среди них есть наибольший номер ip, то подмножество В конечно. В противном случае получим счетное подмножество i1, ai2. ain. >, нумерация которого установлена так: v(n) = ain.

Если множество конечно или счетно, его называют не более чем счетным. Семейство (Аi)i∈I множеств называют не более чем счетным, если множество (индексов) I не более чем счетно.

Теорема 1.12. Объединение любого не более чем счетного семейства счетных множеств счетно.

Полезно отметить также и следующий факт.

Теорема 1.13. Объединение конечного и счетного множеств счетно. #

Теорема 1.14. Пусть М — бесконечное множество, а N — его не более чем счетное подмножество. Если множество MN бесконечно, то оно равномощно множеству М.

◀ По теореме 1.10 в множестве MN, поскольку оно бесконечно, можно выбрать счетное подмножество N’. Ясно, что N∩N’ = ∅. Множество N∪N’ является счетным как объединение двух счетных множеств или объединение счетного и конечного множеств. Поэтому существует биекция f: N∪N’ → N’. Поскольку (M(N∪N’))∪(N∪N’)=M, M (N∪N’)∪N’ = = MN, то требуемую биекцию М на МN строим так: на подмножестве М (N∪N’), общем для М N и М, эта биекция совпадает с тождественным отображением; на подмножестве N∪N’ эта биекция есть биекция f. ▶

Следствие 1.1. Если М — бесконечное множество, а N — не более чем счетное множество, то М

Существуют бесконечные множества, не являющиеся счетными. Это вытекает из следующих рассуждений.

Рассмотрим множество всех последовательностей нулей и единиц, т.е. последовательностей вида <α12, . αn. >, где αi ∈ <0,1>для каждого i ≥ 1.

Обозначим множество таких „двоичных" последовательностей через <0,1>ω .

Теорема 1.15 (теорема Кантора). Множество <0,1>ω не есть счетное множество.

◀ Пусть множество <0,1>ω счетное. Тогда существует биекция φ: ℕ → <0,1>ω . Выпишем все последовательности φ(n):

Построим последовательность β = <β1. βn. >: положим βi = 1, если αii = 0, и βi = 0, если αii = 1. Ясно, что эта последовательность не совпадает ни с одной из последовательностей φ(n), а это противоречит допущению, что любая последовательность из <0,1>ω есть φ(k) для некоторого k.

Итак, ℕ не равномощно <0,1>ω .

В то же время <0,1>ω содержит подмножество последовательностей, в каждой из которых только один член отличен от нуля. Это подмножество равномощно множеству всех одноэлементных подмножеств ℕ и, следовательно, самому ℕ. Следовательно, множество <0,1>ω бесконечно, но не равномощно счетному множеству и потому не является счетным. ▶

Теорема 1.16. Множество 2 ℕ всех подмножеств множества натуральных чисел и множество <0,1>ω равномощны.

◀ Определим отображение φ множества 2 ℕ на множество <0,1>ω следующим образом: если X ⊆ ℕ, то φ(Х)i = 1 при i ∈ X и φ(Х)i = 0 при i ∉ X.

Тем самым подмножеству X ставится в соответствие последовательность φ(Х), i-й член которой равен единице тогда и только тогда, когда число i есть элемент множества X. Докажем, что φ — биекция 2 ℕ на <0,1>ω .

Покажем, что отображение φ — инъекция. Пусть X и Y — различные подмножества ℕ. Тогда найдется число i ∈ X Y или число j ∈ YX. В первом случае в последовательности φ(Х) i-й член будет равен единице, а в последовательности φ(Y) — нулю. Таким образом, φ(Х) ≠ φ(Y). Во втором случае φ(Y)j = 1, φ(Х)j = 0 и опять φ(Х) ≠ φ(Y). Следовательно, отображение φ — инъекция.

Покажем, что φ — сюръекция. Возьмем произвольную последовательность α ∈ <0,1>ω . Образуем множество Хα = = i = 1>. Ясно, что φ(Хα) = α. Таким образом, для любой последовательности α ∈ <0,1>ω существует подмножество Хα ∈ 2 ℕ , такое, что φ(Хα) = α. Следовательно, φ — сюръекция.

Таким образом, мы показали, что φ — биекция, а множества 2 ℕ и <0,1>ω равномощны. >

Читайте также:  Мегафон логин 2 фото

Мощность множества 2 ℕ обозначают с и называют мощностью континуума, а любое множество, эквивалентное множеству 2 ℕ , называют множеством мощности континуума или континуальным множеством.

Теорема 1.17. Множество действительных чисел отрезка [0,1] равномощно множеству всех последовательностей нулей и единиц <0,1>ω .

◀ Каждое действительное число из отрезка [0,1] представим в виде бесконечной дроби в двоичной системе счисления. Число 1 представим в виде периодической дроби, содержащей бесконечное число единиц — 0,1(1). Конечные рациональные дроби представим как бесконечные, дополнив справа бесконечным числом нулей. Таким образом, каждое число из [0,1] представлено в виде последовательности нулей и единиц. Кроме этого, выбросим счетное множество всех периодических дробей вида O,αα1. αkO(1), поскольку каждая такая дробь представляет то же самое число, что и дробь O,αα1. αk1(0), где αi ∈ <0,1>для всякого i = 1,k . Легко видеть, что полученное таким образом множество двоичных дробей равномощно множеству <0,1>ω ▶

Следствие 1.2. [0,1]

◀ Выше была доказана равномощность множеств (0,1) ω и 2 ℕ . Тогда имеем [0,1]

Теорема 1.18. Следующие множества равномощны:

  1. множество действительных чисел отрезка [0,1];
  2. множество действительных чисел интервала (0,1);
  3. множество действительных чисел отрезка [а, b];
  4. множество действительных чисел интервала (а, b);
  5. множество действительных чисел (числовая ось) ℝ;
  6. множество всех подмножеств множества натуральных чисел 2 ℕ .

◀ Покажем равномощность множеств [0,1] и (0,1). Из множества действительных чисел отрезка [0,1] выделим двухэлементное подмножество <0,1>. Разностью этих множеств будет множество действительных чисел интервала (0,1), и, согласно теореме 1.14, [0,1]

Отображение у = (b — a)х + а задает биекцию множества [0,1] на множество [а, b]. Следовательно, эти множества номощны. Заметим, что аналогично доказывается равномощность (0,1) и (а, b).

ℝ. Биекцию можно установить, например, с помощью функции у = 1/πarctgx + 1/2.

Поскольку равномощность [0,1] и 2 ℕ ранее доказана, имеем

Замечание 1.7. Заметим, что если в условиях теоремы 1.14 множество М несчетно, а N — его счетное подмножество, то множество MN бесконечно, ибо иначе получилось бы, что множество М = (М N) U N счетно как объединение конечного и счетного множеств.

Таким образом, можно утверждать, что для любого несчетного множества М и его не более чем счетного подмножества N имеет место равенство |М N| = |М|. #

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

Считают, что мощность множества А не превышает мощность множества В (|А| ≤ |В|), если А равномощно некоторому подмножеству множества В. Можно показать, что из соотношений |A| ≤ |В| и |В| ≤ |А| следует, что |A| = |B|.

Мощность множества А считается строго меньшей мощности множества В (|А| ℕ | > |А|. #

В силу теоремы 1.20 нет наибольшей мощности, так как для любого множества А существует множество большей мощности — его булеан. Заметим, что для счетного множества А теорема 1.20 сводится к теореме Кантора 1.15.

Теорема 1.21 (теорема о квадрате). Для любого бесконечного множества М его декартов квадрат М × М мощен самому множеству М.

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

Сначала обратимся к счетному множеству. Для доказательства утверждения достаточно показать, что ℕ × ℕ

ℕ, т.е. задать на ℕ × ℕ некоторую нумерацию. Рассмотрим множество Ai = <(i, j): j ∈ ℕ>упорядоченных пар. Это множество счетно по построению. Легко видеть, что справедливо равенство

откуда, согласно теореме 1.12, вытекает счетность декартова квадрата ℕ × ℕ множества ℕ как счетного объединения счетных множеств.

Перейдем к континуальному множеству. Докажем, что множество всех упорядоченных пар двоичных последовательностей эквивалентно множеству всех таких последовательностей, т.е. 2 ℕ × 2 ℕ

Паре последовательностей (α, β) поставим в соответствие последовательность α, β, α1, β1, . αn, βn, . Это соответствие будет взаимно однозначным, т.е. установлена биекция между 2 ℕ × 2 ℕ

Получается, что — как это ни удивительно — в квадрате „столько же" точек, сколько и в каждой его стороне. Можно обобщить это утверждение для произвольной конечной декартовой степени множества М.

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

◀ Каждому рациональному числу, представленному несократимой дробью a/b, однозначно соответствует упорядоченная пара (а, b), и, напротив, любая упорядоченная пара (а, b) взаимно простых целых чисел а и b однозначно определяет несократимую дробь a/b и значит, рациональное число. Следовательно, множество ℚ эквивалентно некоторому бесконечному подмножеству множества ℤ × ℤ. Поскольку множество ℤ × ℤ счетно, из теоремы 1.11 вытекает, что любое его бесконечное подмножество счетно. Таким образом, множество ℚ счетно. >

Читайте также:  Мини elm327 bluetooth obd2

В заключение приведем сводку результатов по мощностям некоторых конечных множеств.

Теорема 1.22. Если М и N — конечные множества и |М| = m, a |N| = n, то:

  1. мощность множества всех отображений М в N равна n m ;
  2. мощность множества всех биекций из N на себя равна Pn=n!;
  3. мощность множества всех инъекций из М в N (m ≤ n) равна A m n = n! (n-m)! ;
  4. мощность множества всех подмножеств множества N равна 2 n ;
  5. мощность множества всех k-элементных подмножеств множества N равна C k n = n! k!(n-k)! ;
  6. мощность прямого произведения М × N равна mn. #

Напомним [I], что в комбинаторике число Рn называют числом перестановок n элементов, число A m n — числом размещений без повторений из n элементов по m, число C k n (обозначаемое также ( n k )) — числом сочетаний из n элементов по k. Эти числа называются также биномиальными коэффициентами, поскольку (формула бинома Ньютона).

чему равна и как найти мощность множества биективных функций R->R? или хотя бы сравнить с континуумом

задан 17 Окт ’18 22:24

1 ответ

Для начала рассмотрим множество всех отображений из R в R. Их будет R^R, что равномощно (2^N)^R

Покажем теперь, что биекций R на R не меньше, чем 2^R. Отсюда будет следовать, что их по мощности именно столько, то есть 2 в степени континуум.

Рассмотрим множество X мощности континуум, состоящее из двух параллельных прямых. Пусть это будут прямые y=0 и y=1 на координатной плоскости. Загадаем произвольное подмножество A в R. По нему определим биекцию X на X таким образом: если x принадлежит A, то точки (x,0) и (x,1) множества X переставим. Если не принадлежит, то оставим обе точки на месте. При разных A, получаются разные биекции. Этим мы получаем не меньше биекций континуума на себя, чем имеется подмножеств прямой.

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

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

Определение

Пусть даны два множества $ 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