Мощность

редактировать

Мера количества элементов в наборе

Набор

S {\ displaystyle S}

S

всех Платоновых тел имеет 5 элементов. Таким образом,

| S | = 5 {\ displaystyle | S | = 5}

{\ displaystyle | S | = 5}

В математике мощность набора является мерой «числа элементы "набора. Например, набор $A = {2, 4, 6} {\ displaystyle A = \ {2,4,6 \}}$ ${\ displaystyle A = \ {2,4,6 \}}$ содержит 3 элемента, и поэтому $A {\ displaystyle A}$ $A$ имеет мощность 3. Начиная с конца 19 века, это понятие было обобщено до бесконечных множеств, что позволяет различать разные типы бесконечности и выполнить с ними арифметические действия. Существует два подхода к количеству элементов: один, который сравнивает наборы напрямую, используя смещения и инъекции, и другой, который использует количественные числа. Мощность набора также называется его размером, когда недопустимо путаница с другими понятиями размера.

Мощность набора $A {\ displaystyle A}$ $A$ обычно обозначается $| А | {\ displaystyle | A |}$ $| A |$ , с вертикальной полосой с каждой стороны; это то же обозначение, что и абсолютное значение, а значение зависит от контекста. Мощность набора $A {\ displaystyle A}$ $A$ может также обозначаться $n (A) {\ displaystyle n (A)}$ $n (A)$ , $A {\ displaystyle A}$ $A$ , $карточка ⁡ (A) {\ displaystyle \ operatorname {card} (A)}$ ${\ displaystyle \ operatorname {card} (A)}$ или $# A {\ displaystyle \ #A}$ ${\ displaystyle \ #A}$ .

Содержание

1 Сравнение наборов
- 1.1 Определение 1: | A | = | B |
- 1.2 Определение 2: | A | ≤ | B |
- 1.3 Определение 3: | A | < |B|
2 Кардинальные числа
3 Конечные, счетные и несчетные множества
4 Бесконечные множества
- 4.1 Мощность континуума
5 Примеры и свойства
6 Объединение и пересечение
7 См. Также
8 Ссылки

Сравнение наборов

Биективная функция из N с набором E из четных чисел. Хотя E является правильным подмножеством N, оба набора имеют одинаковую мощность.

Nне имеет той же мощности, что и его набор мощности P(N): для каждой функции f из N на P (N ), набор T = {n∈ N : n∉f (n)} не согласуется с каждым набором в диапазоне функции f, следовательно, f не может быть сюръективным. На картинке показан пример f и соответствующий T; красный : n∈f (n) \ T, синий : n∈T \ f (n).

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

Определение 1: | A | = | B |

Два набора A и B имеют одинаковую мощность, если существует биекция (также известная как взаимно-однозначное соответствие) от A к B, то есть функция из От A до B, который является одновременно инъективным и сюръективным. Такие множества называются равносильными, равноправными или равноправными. Это соотношение также можно обозначить A ≈ B или A ~ B.

Например, множество E = {0, 2, 4, 6,...} неотрицательных четных чисел имеет той же мощности, что и множество N = {0, 1, 2, 3,...} натуральных чисел, поскольку функция f (n) = 2n является биекцией из N - E (см. Рисунок).

Определение 2: | A | ≤ | B |

A имеет мощность меньше или равную мощности B, если существует инъективная функция из A в B.

Определение 3: | A | < |B|

A имеет мощность строго меньше, чем мощность B, если существует инъективная функция, но нет биективной функции, от A до B.

Например, множество N из всех натуральные числа имеют мощность строго меньшую, чем его набор степеней P(N), потому что g (n) = {n} - инъективная функция от N до P (N ), и можно показать, что никакая функция от N до P (N ) не может быть биективной (см. Рисунок). По аналогичному аргументу, N имеет мощность, строго меньшую, чем мощность множества R всех действительных чисел. Для доказательств см. диагональный аргумент Кантора или первое доказательство несчетности Кантора.

If | A | ≤ | B | и | B | ≤ | A |, то | A | = | B | (факт, известный как теорема Шредера – Бернштейна ). Аксиома выбора эквивалентна утверждению, что | A | ≤ | B | или | B | ≤ | A | для каждого A, B.

Кардинальные числа

В приведенном выше разделе «мощность» набора была определена функционально. Другими словами, он не был определен как конкретный объект. Однако такой объект можно определить следующим образом.

Отношение одинаковой мощности называется равнодоступностью, и это отношение эквивалентности в классе всех наборов. Таким образом, класс эквивалентности множества A в этом отношении состоит из всех тех множеств, которые имеют ту же мощность, что и A. Есть два способа определить "мощность набора":

мощность множества A определяется как его класс эквивалентности при равномасштабности.
Репрезентативный набор определяется для каждого класса эквивалентности. Наиболее распространенным выбором является начальный порядковый номер в этом классе. Это обычно принимается как определение кардинального числа в аксиоматической теории множеств.

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

ℵ 0 < ℵ 1 < ℵ 2 < …. {\displaystyle \aleph _{0}<\aleph _{1}<\aleph _{2}<\ldots.}

\ aleph _ {0} <\ aleph _ {1} <\ aleph _ {2} <\ ldots.

Для каждого ординала $α {\ displaystyle \ alpha}$ $\ alpha$ , $ℵ α + 1 {\ displaystyle \ aleph _ {\ alpha +1}}$ $\ aleph _ {\ alpha +1}$ - наименьшее кардинальное число, большее чем $ℵ α {\ displaystyle \ aleph _ {\ alpha}}$ $\ aleph _ {\ alpha}$ .

Мощность натуральных чисел обозначается aleph- null ( $ℵ 0 {\ displaystyle \ aleph _ {0}}$ $\ алеф _ {0}$ ), а мощность действительных чисел обозначается как « $c { \ displaystyle {\ mathfrak {c}}}$ ${\ mathfrak {c}}$ "(строчный скрипт fraktur « c »), также обозначается как мощность континуума. Кантор показал, используя аргумент диагональ, что $c>ℵ 0 {\ displaystyle {\ mathfrak {c}}>\ aleph _ {0}}$ ${\mathfrak {c}}>\ aleph _ { 0}$ . Мы можем показать, что $c = 2 ℵ 0 {\ displaystyle {\ mathfrak {c}} = 2 ^ {\ aleph _ {0}}}$ ${\ mathfrak {c}} = 2 ^ {\ aleph _ {0}}$ , это также мощность множества всех подмножеств натуральных чисел.

Согласно гипотезе континуума, $ℵ 1 = 2 ℵ 0 {\ displaystyle \ aleph _ {1} = 2 ^ {\ aleph _ {0}}}$ $\ aleph _ {1} = 2 ^ {\ aleph _ {0}}$ , то есть $2 ℵ 0 {\ displaystyle 2 ^ {\ aleph _ {0}}}$ $2 ^ {\ aleph _ {0}}$ - наименьшее кардинальное число, превышающее $ℵ 0 {\ displaystyle \ aleph _ {0}}$ $\ алеф _ {0}$ , т. Е. Не существует набора, мощность которого строго находится между мощностью целых и действительных чисел. Гипотеза континуума независима от ZFC, стандартная аксиоматизация теории множеств, т. е. невозможно доказать континуум hyp или его отрицание от ZFC - при условии, что ZFC согласован). Подробнее см. § Мощность континуума ниже.

Конечные, счетные и несчетные множества

Если выполняется аксиома выбора, закон трихотомии выполняется для мощности. Таким образом, мы можем сделать следующие определения:

Любое множество X, мощность которого меньше, чем у натуральных чисел, или | X | < | N |, называется конечным множеством.
Любое множество X, имеющее ту же мощность, что и множество натуральных чисел, или | X | = | N | = $ℵ 0 {\ displaystyle \ aleph _ {0}}$ $\ алеф _ {0}$ , называется счетно бесконечным множеством.
Любое множество X с мощностью больше чем натуральные числа, или | X |>| N |, например | R | = $c {\ displaystyle {\ mathfrak {c}}}$ ${\ mathfrak {c}}$ >| N |, называется несчетным.

Бесконечными множествами

Наша интуиция, полученная из конечных множеств, не работает при работе с бесконечными множествами. В конце девятнадцатого века Георг Кантор, Готлоб Фреге, Ричард Дедекинд и другие отвергли точку зрения о том, что целое не может быть того же размера, что и часть. Одним из примеров этого является парадокс Гильберта в Гранд Отеле. В самом деле, Дедекинд определил бесконечное множество как такое, которое может быть помещено во взаимно однозначное соответствие со строгим подмножеством (то есть имеющим тот же размер в смысле Кантора); это понятие бесконечности называется бесконечным дедекиндовым. Кантор ввел кардинальные числа и показал - согласно его определению размера, основанному на биекциях, - что одни бесконечные множества больше других. Наименьшее бесконечное количество элементов - это натуральные числа ( $ℵ 0 {\ displaystyle \ aleph _ {0}}$ $\ алеф _ {0}$ ).

Мощность континуума

Одним из наиболее важных результатов Кантора было то, что мощность континуума ( $c {\ displaystyle {\ mathfrak {c}} }$ ${\ mathfrak {c}}$ ) больше, чем у натуральных чисел ( $ℵ 0 {\ displaystyle \ aleph _ {0}}$ $\ алеф _ {0}$ ); то есть действительных чисел R больше, чем натуральных чисел N . А именно, Кантор показал, что $c = 2 ℵ 0 = ℶ 1 {\ displaystyle {\ mathfrak {c}} = 2 ^ {\ aleph _ {0}} = \ beth _ {1}}$ ${\ displaystyle {\ mathfrak {c}} = 2 ^ {\ aleph _ {0}} = \ beth _ {1}}$ (см. Beth one ) удовлетворяет:

2 ℵ 0>ℵ 0 {\ displaystyle 2 ^ {\ aleph _ {0}}>\ aleph _ {0}}

2^{\aleph _{0}}>\ aleph _ {0}

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

Гипотеза континуума утверждает, что нет кардинального числа между мощность действительных чисел и мощность натуральных чисел, то есть

2 ℵ 0 = ℵ 1 {\ displaystyle 2 ^ {\ aleph _ {0}} = \ aleph _ {1}}

2 ^ {\ aleph _ {0}} = \ aleph _ {1}

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

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

Первый из этих результатов очевиден при рассмотрении, например, касательной функции, которая обеспечивает взаимно однозначное соответствие между интервалом (−½π, ½π) и R (см. Также парадокс Гильберта Гранд Отеля ).

Второй результат был впервые продемонстрирован Кантором в 1878 году, но он стал более очевидным в 1890 году, когда Джузеппе Пеано представил кривые заполнения пространства, изогнутые линии, которые поверните и поверните так, чтобы заполнить весь квадрат, куб, гиперкуб или конечномерное пространство. Эти кривые не являются прямым доказательством того, что прямая имеет такое же количество точек, что и конечномерное пространство, но они могут быть использованы для получения такого доказательства.

Кантор также показал, что множества с мощностью строго больше, чем $c {\ displaystyle {\ mathfrak {c}}}$ ${\ mathfrak {c}}$ существуют (см. Его обобщенный диагональный аргумент и теорему ). Они включают, например:

набор всех подмножеств R, т. Е. набор мощности из R, записанный P (R ) или 2
набор R всех функций от R до R

Обе имеют мощность

2 c = ℶ 2>c { \ displaystyle 2 ^ {\ mathfrak {c}} = \ beth _ {2}>{\ mathfrak {c}}}

2^{\mathfrak {c}}=\beth _{2}>{\ mathfrak {c}}

(см. Beth two ).

The кардинальные равенства $c 2 = c, {\ displaystyle {\ mathfrak {c}} ^ {2} = {\ mathfrak {c}},}$ ${\ mathfrak {c} } ^ {2} = {\ mathfrak {c}},$ $c ℵ 0 = c, {\ displaystyle {\ mathfrak {c}} ^ {\ aleph _ {0}} = {\ mathfrak {c}},}$ ${\ mathfrak {c}} ^ {\ aleph _ {0}} = {\ mathfrak {c}},$ и $cc = 2 c {\ displaystyle {\ mathfrak {c}} ^ {\ mathfrak {c}} = 2 ^ {\ mathfrak {c}}}$ ${\ mathfrak {c}} ^ {\ mathfrak {c}} = 2 ^ {\ mathfrak {c}}$ можно продемонстрировать с помощью кардинальной арифметики :

c 2 = (2 ℵ 0) 2 = 2 2 × ℵ 0 знак равно 2 ℵ 0 знак равно с, {\ displaystyle {\ mathfrak {c}} ^ {2} = \ left (2 ^ {\ aleph _ {0}} \ right) ^ {2} = 2 ^ {2 \ раз {\ aleph _ {0}}} = 2 ^ {\ aleph _ {0}} = {\ mathfrak {c}},}

{\ mathfrak {c}} ^ {2} = \ left (2 ^ {\ aleph _ {0}} \ right) ^ {2} = 2 ^ {2 \ times {\ aleph _ {0}}} = 2 ^ {\ aleph _ {0}} = {\ mathfrak {c}},

с ℵ 0 = (2 ℵ 0) ℵ 0 = 2 ℵ 0 × ℵ 0 = 2 ℵ 0 = с, {\ displaystyle {\ mathfrak {c }} ^ {\ aleph _ {0}} = \ left (2 ^ {\ aleph _ {0}} \ right) ^ {\ aleph _ {0}} = 2 ^ {{\ aleph _ {0}} \ раз {\ aleph _ {0}}} = 2 ^ {\ aleph _ {0}} = {\ mathfrak {c}},}

{\ mathfrak {c}} ^ {\ aleph _ {0}} = \ left (2 ^ {\ aleph _ {0}} \ right) ^ {\ aleph _ {0}} = 2 ^ {{\ aleph _ {0}} \ times {\ алеф _ {0}}} = 2 ^ {\ aleph _ {0}} = {\ mathfrak {c}},

cc = (2 ℵ 0) c = 2 c × ℵ 0 = 2 c. {\ Displaystyle {\ mathfrak {c}} ^ {\ mathfrak {c}} = \ left (2 ^ {\ aleph _ {0}} \ right) ^ {\ mathfrak {c}} = 2 ^ {{\ mathfrak {c}} \ times \ aleph _ {0}} = 2 ^ {\ mathfrak {c}}.}

{\ mathfrak {c}} ^ {\ mathfrak {c}} = \ left (2 ^ {\ aleph _ {0}} \ right) ^ {\ mathfrak {c}} = 2 ^ {{\ mathfrak {c}} \ times \ aleph _ {0}} = 2 ^ {\ mathfrak {c}}.

Примеры и свойства

Если X = {a, b, c} и Y = {яблоки, апельсины, персики}, затем | X | = | Y | потому что {(a, яблоки), (b, апельсины), (c, персики)} - это взаимно однозначное соответствие между множествами X и Y. Мощность каждого из X и Y равна 3.
Если | X | ≤ | Y |, то существует Z такое, что | X | = | Z | и Z ⊆ Y.
Если | X | ≤ | Y | и | Y | ≤ | X |, то | X | = | Y |, Это справедливо даже для бесконечных кардиналов и известно как теорема Кантора – Бернштейна – Шредера.
Множества с мощностью континуума включают в себя набор всех действительных чисел, набор всех иррациональных чисел и интервал $[0, 1] {\ displaystyle [0,1]}$ $[0,1 предлагает$ .

Объединение и пересечение

Если A и B являются непересекающимися множествами, то

| A ∪ B | = | А | + | B |. {\ displaystyle \ left \ vert A \ cup B \ right \ vert = \ left \ vert A \ right \ vert + \ left \ vert B \ right \ vert.}

\ left \ vert A \ cup B \ right \ vert = \ left \ vert A \ right \ vert + \ left \ vert B \ right \ vert.

Отсюда можно показать, что в целом мощности объединений и пересечений связаны следующим уравнением:

| C ∪ D | + | C ∩ D | = | C | + | D | {\ Displaystyle \ left \ vert C \ чашка D \ right \ vert + \ left \ vert C \ cap D \ right \ vert = \ left \ vert C \ right \ vert + \ left \ vert D \ right \ vert}

{\ displaystyle \ left \ vert C \ чашка D \ right \ vert + \ left \ vert C \ cap D \ right \ vert = \ left \ vert C \ right \ vert + \ left \ vert D \ right \ vert}

См. Также

Викискладе есть медиафайлы, связанные с Мощность.

Викиданные имеют свойства:

мощность группы (P1164) (см. использует )

мощность этого множества (P2820) (см. использует )

Ссылки