Ответы на экзаменационные вопросы № 1-31 по курсу "Дискретная математика" (Определение взаимно однозначного соответствия между двумя множествами. Определение транспортной сети, разреза в ней и его пропускной способности. Теорема Форда-Фолкерсона), страница 2

Множество Z всех целых чисел счетно.

…,-2,-1,0,1,2,…

…,а₄,а₂,а₀,а₁,а₂,…

Вопрос 2

Множество А называется счетным, если А~N. N – все натуральные числа. Иными словами счетность множества А означает, что все его элементы можно занумеровать (без повторений) натуральными числами.

Вопрос 3

Теорема

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

Доказательство: Множество А бесконечно, и поэтому очевидно не пусто. $a₀ÎA. Но, будучи ¥, А не исчерпывается подмножеством {a₀}ÌA. Значит $a₁ÎA-{a₀}. Но, в силу ¥ А, оно не исчерпывается подмножеством {a₀,a₁}ÌA. Значит $a₂ÎA-{a₀,a₁} и т.д. Подмножество {a₀,a₁,a₂,…}ÌА содержится в А и является счетным.

Теорема

Если А и В счетны, то счетны и множества АÈВ, А´В={(a,b)½aÎA,bÎB}.

Докажем счетность множества АÈВ:

а) АÇВ=Æ

Ввиду счетности множеств А и В имеем:

А={a₀,a₁,a₂,…}

В={b₀,b₁,b₂,…}

Положим c_n=a_k, если n=2k и c_n=b_k, если n=2k+1.

Тогда АÈВ={c_n½nÎN}, причем все элементы этого множества занумерованы натуральными числами, чем и доказана его счетность.

б) АÇВ¹Æ

АÈВ=АÈ(В-А)

АÇ(В-А)=Æ

В-А счетно – доказательство аналогично приведенному в п.а)

В-А конечно.

Следствие: Пусть А₀,А₁,…,А_l,… - счетная последовательность счетных множеств. А₀ÈА₁È…ÈА_l… счетно. Под А₀È…ÈА_l…. понимают множество всех элементов, каждый из которых входит хотя бы в одно из данных множеств.

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

А₀: а₀₀, а₀₁, а₀₂,…

А₁: а₁₀, а₁₁, а₁₂,…

А₂: а₂₀, а₂₁, а₂₂,…

…

Нумерация: а₀₀, а₀₁, а₁₀, а₀₂, а₁₁, а₂₀, …

Вопрос 4

Несчетным называется бесконечное множество, не являющееся счетным.

Теорема

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

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

Пусть а₀, а₁, … а_n, … - некоторая последовательность для которой каждая из a_n – последовательность из нулей и единиц.

а₀: а₀₀, а₀₁, а₀₂,… а_0n,…

а₁: а₁₀, а₁₁, а₁₂,… а_1n,…

…

а₂: а₂₀, а₂₁, а₂₂,… а_nn,…

…

Построим последовательность a={a_n}, определяемую так: a_n=1-а_nn= 0,если а_nn=1 и 1,если а_nn=0.

a₀=1-а₀₀¹а₀₀ a¹а₀.

a₁=1-а₁₁¹а₁₁ a¹а₁.

…

a_n=1-а_nn¹а_nn a¹а_n.

…

Значит последовательность a не входит в список последовательностей а₀, а₁, …, а_n, … Значит множество всех последовательностей из нулей и единиц не исчерпывается никаким таким списком. Значит оно не является счетным.

Вопрос 5

Несчетным называется бесконечное множество, не являющееся счетным.

Вопрос 6

Пусть А и В – множества. Говорят, что мощность |А| множества А больше мощности |В| множества В, если:

1.  А не эквивалентно В

2.  $А_ВÌА: А_В~В

Если А и В эквивалентны, то их мощности считаются одинаковыми.

Теорема

Пусть А – произвольное множество. Тогда множество 2^А всех его подмножеств имеет мощность, большую, чем А.

Доказательство:

Предположим противное, т.е. А~2^А. Пусть f:А®2^А – взаимно-однозначное соответствие. "а f(а)ÌА. аÎА, f(а)Î2^А. Очевидно возможно одно из двух ("аÎА):

1.  аÎf(а)

2.  аÏf(а)

Рассмотрим множество D={aÏA½aÏf(a)}. DÌА. Поэтому, т.к. f по предположению есть взаимно-однозначное соответствие между А и 2^А, $dÎD, D=f(d). Рассмотрим вопрос: dÎD?

1.  Предположим, что dÏD, т.е. dÏf(d). Но по определению множества D заключаем dÎD. Полученное противоречие показывает, что предположение dÏD выполняться не может.

2.  Предположим, что dÎD. D=f(d). Для элемента d выполняется условие dÏf(d) и значит по определению множества D dÏD. Значит и это предположение ведет к противоречию.

Следовательно, первоначальное предположение об эквивалентности множеств А и 2^А ведет к противоречию и потому должно быть отброшено.

Итак, множества А и 2^А не эквивалентны. Чтобы получить соотношение ½2^А½>½А½ остается проверить существование такого подмножества ВÌ2^А, которому А было бы эквивалентно (А~В). Достаточно принять В={{a}½aÎA}. Иными словами В есть множество всех одноэлементных подмножеств множества А. Взаимно-однозначное соответствие f:А®В очевидно: f(a)={a}. Итак, ½2^А½>½А½. Теперь имеем: ½N½<½2^N½<½2^{2 в степ. N}½<½2^…½<….