3.7. Счётные и несчётные множества
Определение 3.20. Множества A и B называются эквивалентными (равномощными), если ∃f:A→B — биекция. Обозначение: A∼B.
Определение 3.21. Множество называется счётным, если оно эквивалентно N.
Замечание. Множество A счётно, если оно бесконечно и его элементы можно занумеровать. Действительно, ∀n∈N ∃!a∈A:a=f(n). Обозначим его через an. ∀a∈A ∃!n∈N:a=an, тогда A={a1,a2,…},ai≠aj при i≠j.
Определение 3.22. Множество называется не более чем счётным, если оно конечно или счётно.
Теорема 3.17 (Кантора). Не более чем счётное объединение не более чем счётных множеств не более чем счётно.
▴ Занумеруем все множества последовательными натуральными числами, пусть Ek — множество, соответствующее номеру k, где k пробегает либо конечное множество {1,…,K}, либо N. Занумеруем все элементы множества Ek,Ek={ekm}, где номер m пробегает либо конечное множество {1,…,Mk}, либо N. Запишем элементы ekm в таблицу:
E1={e11,e12,e13,e14,…},
E2={e21,e22,e23,e24,…},
E3={e31,e32,e33,e34,…},
…………………
Теперь будем последовательно нумеровать элементы этой таблицы следующим образом: e11, e21,e12, e31,e22,e13, …, пропуская пустые места и те элементы, которые ранее были занумерованы. В результате получим биекцию между ⋃kEk и либо N, либо конечным множеством. ◼
Следствие 1. Z счётно.
▴ Z=N∪{0}∪(−N). ◼
Следствие 2. Q счётно.
▴ Q=⋃q∈NEq, где Eq={pq:p∈Z}∼Z∼N. ◼
Определение 3.23. Бесконечное множество, не являющееся счётным, называется несчётным.
Теорема 3.18 (Кантор). Отрезок [a,b] несчётен.
▴ Предположим обратное. Пусть [a,b]={x1,x2,…}. Поделим [a,b] на три равных отрезка и обозначим через [a1,b1] тот из них, который не содержит x1. Пусть уже построен отрезок [an,bn]∌. Поделим [a_ n, b_ n] на три равных отрезка и обозначим через [a_{n+1}, b_{n+1}] тот из них, который не содержит x_{n+1}. Так будет построена последовательность вложенных отрезков \{ [a_ n, b_ n]\} _{n=1}^\infty . По теореме Кантора о вложенных отрезках \exists c \in \bigcap \limits _{n=1}^{\smash {\infty }} [a_ n, b_ n] \Rightarrow \forall n \in \mathbb {N}\colon c \in [a_ n, b_ n] \Rightarrow \forall n \in \mathbb {N}\colon c \not= x_ n. Итак, c \in [a_1, b_1] \subset [a, b], \forall n \in \mathbb {N}\colon c \not= x_ n. !!! \blacksquare