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

Множество, эквивалентное множеству ={0, 1, 2,...}, называется счетным, и его мощность обозначается w.

ТЕОРЕМА. Бесконечное множеств содержит счетное подмножество.

Доказательство. Пусть бесконечно, . Тогда \{ a ₀} тоже бесконечно. (Если предположить, что = \{ a ₀} конечно, то и также конечно). Следовательно, существует a ₁Î \{ a ₀}, что \{ a ₀, a ₁} бесконечно, и т.д. Полoжим f (0) = a ₀, f (1) = a ₁,... Тогда f осуществляет взаимнооднозначное соответствие между множествами и { a ₀, a ₁,...}. ■

ТЕОРЕМА. Множество бесконечно тогда и только тогда, когда оно эквивалентно некоторому собственному подмножеству.

Доказательство. Пусть бесконечно, = { b ₀, b ₁,...} – его счетное подмножество. Тогда = ( È( \ )) ~ ( \{ b ₀})È( \ ) = \{ b ₀} Обратное очевидно. ■

ТЕОРЕМА. Подмножество счетного множества счетно или конечно.

Доказательство. Достаточно доказать для . Пусть I Ì и I бесконечно. Построим f: ® I. Возьмем в качестве f (0) наименьший элемент множества I, в качестве f (1) наименьший элемент множества I \{ f (0)} и т.д.; f осуществляет взаимнооднозначное соответствие между и I.

ТЕОРЕМА. Если и счетны, то È счетно.

È счетно, если все счетны.

Доказательство. Способ нумерации элементов È :

1 2 ®3 4 ®... номера элементов множества ,

¯ ­ ¯ ­

1® 2 3® 4 номера элементов множества .

Способ нумерации

1 ® 2 3 ® 4 5 ® 6 7 …

1 2 3 4 5 6 7 …

¯

1 2 3 4 5 6 7 …

ТЕОРЕМА. Если бесконечно, – конечное или счетное множество, то ( È )~ . Если бесконечно и несчетно, конечно или счетно, то (А\ )~ .

Доказательство. Если счетное подмножество множества , то ( È ) ~ . Поэтому È = ( \ )È( \ ) ~ ( \ )È = . Здесь \ бесконечно, поэтому ( \ )È ~ ( \ ).

Отсюда ~ ( \ ). ■

Будем говорить, что £ если эквивалентно некоторому подмножеству множества . Если £ а и неэквивалентны, то будем писать <