Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Алгоритмы и вычислимость




Мощность множества

Напомним, что для конечного множества A мы обозначаем через |A| число его элементов. Будем называть число n мощностью множества A. Мощности конечных множеств A и B совпадают в том и только том случае, когда между элементами этих множеств можно установить взаимно однозначное соответствие. Если f:A→B – отображение, то |f(A)|≤|A| (некоторые элементы множества A могут «склеиться»). Отображение f инъективно тогда и только тогда, когда |f(A)|=|A| («склеек» не происходит). Для конечных множеств отображение f сюръективно тогда и только тогда, когда |f(A)|=|B|.

Предположим, что A и B – конечные множества одинаковой мощности, |A|=|B|, а f:A→B – некоторое отображение. Тогда следующие условия равносильны:

f инъективно;

f сюръективно;

f биективно (является взаимно однозначным соответствием).

В случае бесконечных множеств ситуация оказывается более сложной. Например, формулой f(n)=2n определяется отображение f множества натуральных чисел в себя, которое инъективно, но не сюръективно. В общем случае говорят, что множества A и B равномощны и пишут |A|=|B|, если между элементами этих множеств можно установить взаимно однозначное соответствие. Если существует инъективное отображение множества A в множество B, то говорят, что мощность A не превосходит мощности B и пишут |A|≤|B|.

Теорема Кантора–Бернштейна. Если существуют инъективные отображения f:A→B и g:B→A, то множества A и B равномощны. Иными словами: если |A|≤|B| и |B|≤|A|, то |A|=B|.

Доказательство. Положим A0=A и A1=g(B). Поскольку g устанавливает взаимно однозначное соответствие между элементами множеств B и A1=g(B), достаточно показать, что имеется взаимно однозначное соответствие между элементами множеств A и A1.

Рассмотрим отображение h:A→A, равное композиции отображений f и g. Как композиция инъективных отображений, оно инъективно. Определим индуктивно последовательность множеств A0, A1,…, полагая

A0=A; A1= g(B); Ai+2=h(Ai), i=0,1,2,…

Очевидно, A0⊃A1. Далее, A1=g(B)⊃g(f(A))=A2. Поэтому

A2=h(A0)⊃h(A1)=A3, A3=h(A1)⊃h(A2)=A4, …

Таким образом,

A0⊃A1⊃A2⊃ … ⊃Ai⊃Ai+1⊃…

Положим

Ci=Ai\Ai+1, i=0,1,…; I∞==0iiAC.

Отображение h устанавливает взаимно однозначное соответствие между элементами множеств Ci и Ci+2 для всех i=0,1,2,….

Множества C, Ci, i=0,1,2,… образуют разбиение множества A, то есть они попарно не пересекаются, а их объединение составляет все множество A:

A=C∪C0∪C1∪C2∪C3∪….

Точно так же множества C, Ci, i=1,2,… образуют разбиение множества A1:

A1=C∪C1∪C2∪C3∪….

Перепишем эти разложения в следующем виде:

A=(C∪C1∪C3∪…)∪ (C0∪C2∪С4∪…);

A1=(C∪C1∪C3∪…)∪ (C2∪С4∪…).

Отображение ϕ:A→A1, при котором

ϕ(x)=x, если x∈C∪C1∪C3∪…;

ϕ(x)=h(x), если x∈C0∪C2∪С4∪…,

устанавливает взаимно однозначное соответствие между элементами множеств A и A1.􀀀

Следующие две теоремы приведем без доказательства.

Теорема Цермело. Для любых множеств A и B выполняется одно из трех условий: |A|<|B|, |B|<|A|, |A|=|B|.

Теорема. Если существует сюръективное отображение множества A на множество B, то |A|≥|B|.

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

В заключение покажем, что существуют множества сколь угодно больших мощностей.

Теорема Кантора. Каково бы ни было множество A, множество всех его подмножеств 2A имеет мощность строго большую, чем само множество A, то есть |A|<|2A|.

Доказательство. Соответствие x→{x}, при котором каждому элементу x множества A сопоставлено одноэлементное подмножество {x}, задает инъективное отображение A в 2A. Следовательно, |A|≤|2A|. Покажем теперь, что |A|≠|2A|. Предположим противное, то есть, что существует биективное отображение f:A→2A. Положим

D={x∈A | x∉f(x)}.

Тогда

x∈D⇔x∉f(x)

Поскольку f биективно, существует такой элемент d∈A, что f(d)=D. Подстановка d вместо x в предыдущую формулу приводит к противоречию: d∈D ⇔ d∉D.􀀀

Счетные множества

Начальный отрезок натурального ряда [0;n−1]={1,2,…,n−1} конечен и содержит n элементов. Сам же натуральный ряд N ={0,1,2,…} бесконечен. Поэтому не может быть инъективным никакое отображение N в [0;n−1]. Следовательно, | N |>n, то есть мощность натурального ряда превосходит любое натуральное число. Множества, равномощные натуральному ряду, называются счетными. Для обозначения мощности счетных множеств используется символ ℵ0 (читается «алеф ноль»). Если множество A конечно или счетно, его элементы могут быть занумерованы, то есть расположены в виде списка

a0, a1, a2, a3, …,

так, что всякий элемент множества A рано или поздно встретится в этом списке. Если множество A конечно, то и список конечен; в противном случае список оказывается бесконечным. Ясно, что при таких обозначениях отображение i→ai – это и есть та самая биекция начального отрезка или всего натурального ряда на множество A, которая устанавливает конечность или счетность множества A.

Пример. Множество четных чисел счетно; их можно представить списком 0,2,4,6,…. Соответствие очевидно: n↔2n. Точно так же счетно и множество нечетных чисел 1,3,5,…. Здесь можно положить n↔2n+1.􀀀

Пример. Множество рациональных чисел счетно. Напомним, что всякое рациональное число однозначно записывается в виде несократимой дроби p/q, где p и q – взаимно простые целые числа и q>0. Составим список, содержащий все рациональные числа, в порядке возрастания величины |p|+q:

0; −1/1; 1/1; −2/1; −1/2; 1/2; 2/1; …

Ясно, что любая дробь p/q появится в этом списке через конечное число шагов и получит свой номер.􀀀

Укажем некоторые свойства счетных множеств.

1. Всякое подмножество счетного множества конечно или счетно.

Доказательство. Достаточно доказать справедливость утверждения для множества натуральных чисел: всякое подмножество A множества натуральных чисел конечно или счетно. Составим список элементов множества A в порядке их возрастания. Если этот список конечен – множество A конечно; если бесконечен – счетно.􀀀

Из предыдущего предложения вытекает, что счетные множества являются наименьшими по мощности бесконечными множествами: если |A|≤ℵ0, то A конечно или счетно.

2. Образ счетного множества относительно произвольного отображения является конечным или счетным множеством.

Доказательство. Пусть множество В является образом счетного множества A относительно некоторого отображения. Тогда, по теореме из предыдущего пункта, |B|≤|A| и, значит, B конечно или счетно.􀀀

Если элементы множества A представлены списком с повторениями

a0, a1, a2, a3, …,

то есть списком, в котором некоторые элементы могут попадаться многократно, это означает, что отображение i→ai сюръективно (но не инъективно). Таким образом, множество A является образом натурального ряда, и потому конечно или счетно.

3. Всякое бесконечное множество содержит счетное подмножество.

Доказательство. Пусть A – бесконечное множество. Тогда |A|≥ℵ0. Но это неравенство означает, что существует инъективное отображение множества натуральных чисел в A. Образ этого отображения – счетное подмножество множества A.􀀀

4. Объединение любого конечного (непустого) или счетного семейства счетных множеств счетно.

Доказательство. Пусть счетные множества A0, A1, … представлены списками своих элементов: A0 = {a00, a01, a02, a03, … };

A1 = {a10, a11, a12, a13, … };

A2 = {a20, a21, a22, a23, … };

A3 = {a30, a31, a32, a33, … };

…………………………….

Составим список объединения этих множеств A, располагая элементы объединения в порядке возрастания суммы индексов:

A = { a00, a01, a10, a02, a11, a20, a03, …}.

(если некоторые из множеств имеют общие элементы, в этом списке возможны повторения). Множество A бесконечно, и, значит, счетно.􀀀

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

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

Доказательство. Пусть

A = { a0, a1, a2, a3, …}, B = { b0, b1, b2, b3, …}

– счетные множества. Покажем, что счетно декартово произведение A×B. Составим список его элементов подобно тому, как составлялся список рациональных чисел:

(a0,b0), (a0,b1), (a1,b0), (a0,b2), (a1,b1), (a2,b0), ….

Если счетны множества A, B, C, то счетно A×B, а вместе с ним и A×B×С = (A×B)×С как произведение двух счетных множеств. Аналогично устанавливается счетность любого конечного семейства счетных множеств.􀀀

6. Пусть L = {a,b, …, } счетный алфавит. Тогда множество слов над алфавитом L (то есть конечных упорядоченных наборов символов алфавита) счетно.

Доказательство. Множество n-буквенных слов можно естественным образом отождествить с Ln, счетность которого следует из утверждения 5. Теперь достаточно сослаться на утверждение 4: множество всех слов представляет собой объединение счетного семейства счетных множеств: слов из одной буквы; слов из двух букв, и т. д.􀀀






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

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных