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

Определение 1: Множества Х и У называются равномощными, если между ними существует взаимно-однозначное соответствие (биекция)

|X| = |y| или X ~ Y

Замечания:

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

2) |N| = |Z| = |Q|

Свойство: Отношение «быть равномощным» является отношением эквивалентности

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

• Рефлексивность: |X| = |X| Id_x: X X : x x

• Симметричность: f: : X Y биекция => f^-1 : Y X биекция

• Транзитивность: |X| = |Y|, |Y| = |Z|; f : X Y биекция, g : Y Z биекция => g f:X Z биекция

Определение 2: Пусть n N. Отрезком натурального ряда называется множество [1;n]={k N|1

Пример: [1;1] = {1}; [1;4] = {1,2,3,4}

Определение 3: Множество Х, равномощное отрезку [1;n] называется конечным. Число n называется количеством элементов множества. Множество, которое не является конечным называется бесконечным

Определение 4: Пусть X~[1;n], число n называется количеством элементов множества Х.

Свойство: два равномощных множества имеют одно и то же количество элементов

Доказательство: Пусть X~Y; X~[1,n], Y ~ [1,k]

X ~ Y ~ [1,k] => X ~ [1,k] => k = n

Теорема 2: Каждое не пустое конечное множество содержит наибольший и наименьший элемент

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

ММИ(n)

n = 1 есть минимальный и максимальный

n = 2 A,B A>B, A<B, A=B

n = k каждое конечное множество Х в котором k элементов содержит наибольший и наименьший элемент.

n=k+1 X = X₁ X₂ , | X₁| = k, X₂ = {A}

По предположению индукции в множестве X₁ выберем наибольший элемент и обозначим его B. Сравним его с А и выберем наибольший. Аналогичным способом находим минимальный элемент.

Теорема 3: Множество всех натуральных чисел бесконечно

Доказательство (от противного): По теореме 2 в каждом конечном множестве существует максимальный элемент А, но А+1>А. Получили противоречие. Следовательно, максимального элемента нет, а значит множество бесконечно.

Определение 2: Пусть . Отрезком натурального ряда называется множество

[1, ] = .

Пример 1:

Определение 3: Множество X равномощное отрезку [1, ] называется конечным множеством, число называют количеством элементов конечного множества. Множество, которое не является конечным, называется бесконечным.

Теорема 1: Конечное множество равномощно только одному отрезку натурального ряда.

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

Отрезок [1, ] не может быть равномощным [1, ], если .

ММИ по

=1

1^’=

1

2

1. ?!

α

β

l+1

k+1

Рассмотрим ограничения на Так как - биекция, то ни один из элементов не отображается элементом

- инъекция – инъекция

– сюрьекция

- сюрьекция

– биекция

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