Мощность множества.

Альберт Эйнштейн как-то говорил: «Не все, что можно сосчитать, сосчитано, и не все, что сосчитано, можно сосчитать». Хотя это высказывание не очень воодушевляет, попытаемся заняться подсчетами.

Говорят, что между множествами A и B установлено взаимно однозначное соответствие, если каждому элементу множества A соответствует один и только один элемент множества B и каждому элементу множества B соответствует некоторый элемент множества A. В этом случае говорят также, что множества A и B изоморфны и используют обозначение A~B.

Определение 2.2.Два множества A и B называются эквивалентными, или равномощными, если между этими множествами может быть установлено взаимно однозначное соответствие. В этом случае пишут: A~B, или |A|=|B|, и говорят, что множества A и B имеют равные мощности.

Пример 2.4. 1) Множество десятичных цифр равномощно множеству пальцев на руках человека.

2) Множество четных натуральных чисел (2N) равномощно множеству всех натуральных чисел (N).

,

Определение 2.3.Множество A называется конечным, если оно эквивалентно J_n при некотором n, где J_n={1, 2, …, n} – множество n первых натуральных чисел.

Определение 2.4. Мощностью конечного множества A, которое содержит k элементов, называется число его элементов. Она обозначается |A|=k. Пустое множество считается конечным с числом элементов равным нулю, т.е. |Æ|=0.

Таким образом, если множество A конечно, т.е. |A|=k, то элементы A всегда можно перенумеровать, то есть поставить в соответствие элементам номера из отрезка натурального ряда 1..k с помощью некоторой процедуры. Наличие такое процедуры подразумевается, когда употребляется запись A={a₁, a₂, …, a_k}.

Пример 2.5. В компьютере все множества реальных объектов конечны: множество адресуемых ячеек памяти, множество исполнимых программ, множество тактов работы процессора.

,

Множества, которые не являются конечными, называются бесконечными. Если некоторое множество A равномощно множеству N, т.е. A~N, то множество A называется счетным (в зарубежной литературе: множество называются счетным, если оно конечно или счетно бесконечно). Счетное множество A – это такое множество, все элементы которого могут быть занумерованы в бесконечную последовательность a₁, a₂, …, a_n, …, так, чтобы при этом каждый элемент получил лишь один номер n и каждое натуральное число n было бы номером лишь одного элемента множества A. Мощность счетного множества принято обозначать через ( – первая буква древнееврейского алфавита, называемая «алеф», символ читается: «алеф-нуль»). В частности |N|= .

Пример 2.6. Множество Z – множество целых чисел счетно.

Решение. Рассмотрим множество целых чисел Z:

…, -n, …, -3, -2, -1, 0, 1, 2, 3, …, n, … .

На первый взгляд, кажется, что это множество невозможно перенумеровать. Однако эту нумерацию можно осуществить, применив следующую хитрость: двигаясь не в одном направлении, а все время менять его. Иными словами, будем нумеровать так: числу 0 дадим номер 1, числу 1 – номер 2, числу -1 – номер 3, числу 2 – номер 4, числу -2 – номер 5, и т.д. Таким образом, получаем взаимно однозначное соответствие между множеством Z и N. А значит, множество Z счетно.

,

Множество A называется несчетным, если его мощность больше мощности множества N. В таком случае множество A называется континуальным или континуумом. Мощность континуума обозначается . Следующую теорему примем без доказательства.

Теорема 2.1. Множество всех действительных чисел имеет мощность континуума, т.е. |R|=C.