Учебное пособие: Дискретная_мат._пос, страницы 31-35

31

является биекцией

}

,

2

,

1

{

:

2

1

n

X

f

+

→

…

в силу биективности

1

f

и

2

f

.

Следовательно,

2

1

2

1

X

n

X

+

=

+

=

. Основание индукции доказано.

Шаг 2 . Индукционный переход заключается в следующем: предполо-

жим, что теорема справедлива при числе блоков разбиения

1

−

r

; докажем,

что в этом случае она будет справедлива и при числе блоков r.

Предположение: множества

1

,

2

,

1

,

−

=

r

i

Y

i

…

, конечны и образуют

разбиение множества

Y

. Тогда

.

1

∑

−

=

−

=

r

i

r

i

n

Y

Рассмотрим разбиение множества

X

на

r

конечных множеств. Тогда

r

i

X

∪

=

−

=

)

...

(

1

2

1

∪

по закону ассоциативности объ-

единения. Обозначим

∪

1

.

−

=

r

i

X

Y

Опираясь на основание индукции (шаг 1),

имеем

r

X

Y

X

Y

X

+

=

∪

=

, а по индукционному предположению

.

1

∑

=

−

=

−

=

+

=

+

=

r

i

r

i

r

i

X

∪

Индукционный переход доказан.

Заключение. Согласно методу математической индукции, теорема спра-

ведлива для любого натурального числа

r

блоков разбиения.

Теорема (правило произведения). Пусть конечное множество

X

пред-

ставлено в виде декартова произведения r конечных множеств

r

X

×

…

2

1

. Тогда

r

X

⋅

=

…

2

1

.

Правило произведения доказывается методом математической индукции

аналогично правилу суммы.

Теорема (правило включения – исключения). Пусть

1

X

и

2

X

конечные

множества. Тогда

2

1

2

1

2

1

X

∩

−

+

=

∪

.

Доказательство теоремы опирается на правило суммы. Представим мно-

жество

2

1

X

∪

в виде объединения непересекающихся множеств

C

B

A

X

∪

=

∪

2

1

, где

2

1

\

X

A

=

,

2

1

X

B

∩

=

,

1

2

\

X

C

=

(рис. 1.21). Тогда по правилу суммы

C

B

A

X

+

=

∪

2

1

, но

C

B

X

B

A

X

∪

=

∪

=

2

1

,

, поэтому

B

A

X

+

=

1

,

C

B

X

+

=

2

. Имеем

C

B

A

X

+

=

+

2

1

, отсюда

=

−

+

=

∪

B

X

2

1

2

1

2

1

2

1

X

∩

−

+

.

32

Теорема (обобщенное правило включения – исключения).
Пусть конечное множество X является объединением r конечных мно-

жеств:

∪

r

i

X

1

.

=

Тогда

.

...

)

1

(

...

2

1

r

n

k

j

i

k

j

i

n

j

i

j

i

r

i

X

∩

−

+

−

∩

+

∩

−

=

+

≤

<

≤

<

≤

=

∑

Теорема (о мощности булеана конечного множества). Пусть множество

X

конечно и

⏐X⏐

=

n

. Тогда

⏐

B

(X)

⏐

=

n

2

.

Напомним, что

B

(X

) есть булеан множества

X

, т.е. множество всех под-

множеств множества

X

(см 1.1.6). Докажем теорему методом математической

индукции по числу

n

элементов множества

X

.

Основание индукции. Проверим правильность теоремы при

n=

1

. Т.к.

множество

X

состоит из одного элемента

}

{

1

x

X

=

, то всех возможных под-

множеств у множества

X

будет два: пустое множество и само множество

X

,

т.е.

⏐

B

(X)

⏐

n

2

=

.

Индукционный переход. Пусть теорема справедлива при

⏐X⏐

= 1

−

n

.

Рассмотрим произвольное множество

}

,

{

2

1

n

x

X

…

=

и покажем, что

количество всех его подмножеств равно

n

2

.

Покрасим элемент

1

x

множества

X

в “зелубой ” цвет, и все подмноже-

ства множества

X

, содержащие этот элемент, назовем красивыми, а не содер-

жащие этот элемент – некрасивыми. Количество некрасивых подмножеств по

индукционному предположению равно

1

2

−

n

. Красивые подмножества полу-

чены добавлением “зелубого” элемента к каждому некрасивому подмножеству

33

поочередно, значит, их тоже

1

2

−

n

. По правилу суммы количество всех

подмножеств множества

X

равно

n

2

1

=

⋅

=

+

−

.

Заключение. Согласно методу математической индукции, теорема спра-

ведлива для любого натурального числа

n

.

1.4.7. Определение счетного множества

Будем говорить, что множество

X

счетно, если оно равномощно множе-

ству натуральных чисел

N

.

Пример 1. Пусть

X

множество нечетных натуральных чисел. Покажем,

что

X

счетно. Для этого нужно установить биекцию множества

X

на множе-

ство натуральных чисел, т.е. занумеровать элементы множества

X

так, чтобы

каждому элементу

X

соответствовал ровно один номер, а любому натурально-

му числу соответствовал ровно один элемент из

X

. Очевидно, соответствие

∈

−

=

n

f

,

1

2

N

, удовлетворяет этим требованиям:

...}

,

...

,

4

,

3

,

2

,

1

{

...}

,

1

2

...,

,

7

,

5

,

3

,

1

{

n

N

n

X

=

−

=

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

⏐X⏐

=

⏐

N

⏐

и

X

счетно.

Пример 2. Пусть

X

=

N

×N

– декартово произведение множества

N

на се-

бя. Покажем, что

X

счетно. Расположим все элементы

X

в виде матрицы (рис.

1.22) и занумеруем его элементы “ по диагоналям ”: номер 1 присвоим эле-
менту (1,1), номер 2 – элементу (2,1), 3 – (1,3) и т.д.

Полученное отображение

X

на

N

также является биекцией (хотя записать

формулу в явном виде сложнее, чем в примере 1).

Мощность счетного множества обозначается

ℵ

0

. Когда мы пишем

⏐X⏐

=

ℵ

0

, мы утверждаем, что множество

X

счетно, т.е. относится к тому же

34

классу эквивалентности, что и множество натуральных чисел. А множество

N

считается эталоном (образцом) счетных множеств.

1.4.8. Свойства счетных множеств

Покажем, что класс счетных множеств расположен в ряду мощностей ле-

вее любых других классов бесконечных множеств, а предшествуют ему только
классы конечных множеств (рис. 1.23).

Основой для такого утверждения служат следующие теоремы о счетных

множествах.

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

но.

Пусть

X

– счетное множество, а

X

Y

⊆

– произвольное его подмноже-

ство. Занумеруем элементы множества

}

,

{

2

1

…

n

x

X

=

и выберем тот

элемент, который имеет минимальный номер и принадлежит подмножеству

Y

– обозначим его

1

y

. Затем рассмотрим множество

}

{

\

1

y

X

и найдем в нем

элемент с минимальным номером, принадлежащий

Y

, - обозначим

2

y

, и т.д.

Если на

n

-ом шаге мы не обнаружим в множестве

}

,

{

\

2

1

n

y

X

…

элемен-

тов множества

Y

, то

Y

конечно и

⏐Y⏐

=

n

. В противном случае (если процесс

будет продолжаться бесконечно) множество

Y

счетное, т.к. указан способ ну-

мерации его элементов.

Теорема 2. Всякое бесконечное множество имеет счетное подмножество.
Пусть

X

– бесконечное множество. Выберем произвольный элемент

X

x

∈

1

. Так как

X

бесконечно, то

≠

}

{

\

1

x

X

∅

. Обозначим

2

x

произвольный

элемент

из

}

{

\

1

x

X

.

Далее

найдется

},

,

{

\

2

1

3

x

X

x

∈

…

},

,

{

\

3

2

1

4

x

X

x

∈

. Поскольку

X

бесконечно, этот процесс не может

оборваться из-за “нехватки” элементов, и мы получим счетное подмножество

Y

множества

X

:

X

x

Y

⊆

=

}

,

{

3

2

1

…

.

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

множеств есть множество счетное.

Пусть

∪

∞

=

1

n

X

, где

…

,

2

1

n

X

- счетные множества. Будем

считать, что они попарно не пересекаются (в противном случае перейдем от

35

множеств

n

X

к множествам

∪

1

\

−

=

n

k

n

X

Y

, которые попарно не пересе-

каются и

∪

∞

=

∞

=

1

n

Y

X

). Все элементы множества

X

запишем в виде беско-

нечной таблицы:

…

33

34

31

23

22

21

13

12

11

x

где в первой строке записаны элементы множества

1

X

, во второй –

2

X

и т.д.

Занумеруем эти элементы “по диагонали” (как в примере 2 из 1.4.7), при этом
устанавливается биекция между множествами

X

и

N

, т.е.

X

– счетное множе-

ство.

Теорема 4. Пусть

X

бесконечное множество, а

Y

– счетное. Тогда

X

Y

X

=

∪

.

Теорема утверждает, что добавление счетного множества элементов не

увеличивает мощность бесконечного множества.

Доказательство. Рассмотрим множество

Y

X

Z

∪

=

и представим его в

виде объединения непересекающихся множеств

,

1

Y

X

Z

∪

=

где

X

Y

\

1

=

.

Так как

Y

счетно, то

1

Y

конечно или счетно (по теореме 1). Множество

X

бес-

конечно, значит, существует счетное подмножество

X

⊆

1

(по теореме 2).

Тогда

)

\

(

1

X

∪

=

, а

)

(

)

\

(

)

\

(

1

Y

X

Y

X

Y

X

Z

∪

=

∪

=

∪

=

.

По

теореме 3

1

Y

X

∪

счетно,

т.е

1

X

Y

X

=

∪

.

Поэтому

X

Z

=

∪

=

1

)

\

(

. Теорема доказана.

В примере 1 из 1.4.7 мы установили, что множество

N

равномощно сво-

ему собственному подмножеству. Рассуждения, близкие к доказательству тео-
ремы 4, позволяют утверждать, что таким свойством обладает не только мно-
жество

N

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

Рассмотренные четыре теоремы показывают, что среди бесконечных

множеств счетные множества являются наименьшими по мощности. Суще-
ствуют ли множества более чем счетные?

Учебное пособие: Дискретная_мат._пос

Смотрите также: