Зліченні множини
Множина A рівнопотужна множині N натуральних чисел називається зліченною множиною.
Іншими словами, зліченна множина A - це така множина, всі елементи якої можна занумерувати числами 1,2,3,..., тобто можна вказати спосіб, за яким першому елементу множини A ставиться у відповідність число 1, другому - число 2, третьому - число 3 і т.д. Отже, будь-яку зліченну множину A можна подати у вигляді A = {a1,a2,a3,...,an,...}.
Неважко переконатись, що множини квадратів натуральних чисел, усіх парних чисел, усіх непарних чисел, чисел кратних деякому числу k, чисел, які закінчуються парою цифр 00 тощо є зліченними множинами.
Перейдемо до вивчення властивостей зліченних множин.
Теорема 1.2. Будь-яка нескінченна множина M містить зліченну підмножину.
Доведення. Оскільки M нескінченна множина, візьмемо два елементи a1,b1?M (a1?b1). Очевидно, множина M\{a1,b1} є нескінченною множиною. Тоді візьмемо наступні два нові елементи a2,b2?M \{a1, b1} (a2?b2 ) і т.д. Таким чином, ми виділимо з множини M дві зліченні множини A={a1,a2,...,an,...}?M і B={b1,b2,...,bn,...}?M. Це дозволяє підсилити формулювання теореми. А саме: будь-яка нескінченна множина M містить зліченну підмножину A і при цьому множина M \ A є нескінченною множиною (оскільки B ?M \ A).
Теорема 1.3. Будь-яка підмножина зліченної множини є або скінченною, або зліченною множиною.
Доведення. Нехай A={a1,a2,...,an,...} - зліченна множина і B?A. Отже, B={a1,a2,...,ak,...} і можливі дві ситуації: або послідовність у фігурних дужках уривається на деякому елементі, тоді B - скінченна множина, або послідовність у дужках нескінченна, для якої, встановлюючи відповідність (l,al), l?N, одержуємо, що B - зліченна множина.
З теорем 1.2 і 1.3, зокрема, випливає, що зліченні множини є до певної міри найпростішими нескінченними множинами, бо, з одного боку, вони містяться в будь-якій нескінченній множині, а з другого - містять в собі тільки скінченні множини, або нескінченні множини, які є зліченними.
Теорема 1.4. Об’єднання скінченної або зліченної сукупності зліченних множин є зліченною множиною.
Доведення. Розглянемо спочатку скінченну сукупність зліченних множин {A1,A2,...,Ak}, де Ai={a1i,a2i,...,ani,...}, i=1,2,...,k. Запишемо всі елементи множин A1,A2,...,Ak в рядок таким чином: a11,a12,...,a1k,a21,a22,...,a2k,...,an1,an2,...,ank,....
Перенумеруємо записані елементи в порядку їх розташування в рядку. При цьому елемент, який вже одержав свій номер і повторно з'являється в рядку, з подальшої нумерації вилучається. В результаті кожен елемент об’єднання одержить свій номер, що і потрібно було довести.
У випадку зліченної сукупності множин Ai={a1i,a2i,...,ani,...}, i=1,2,..., перепишемо всі елементи множин Ai у такому порядку: a11,a12,a21,a13,a22,a31,a14,a23,a32,a41,....
Принцип переписування елементів множин A зображений за допомогою стрілок на рис.1.4.
a11, a21, a31, ..., an1,.... A1
? ?
a12, a22, a32, ..., an2,.... A2
? ?
a13, a23, a33, ..., an3,.... A3
?
a14, a24, a34, ..., an4,.... A4
...................................
Рис. 1.4.
Далі проводимо міркування аналогічні випадку скінченної сукупності множин. Теорему доведено.
З теореми 1.4 випливає низка цікавих наслідків.
Наслідок 1.4.1. Множина Z всіх цілих чисел зліченна.
Справді, подамо множину Z у вигляді Z = N ? {0} ? N'?, де N'? = { -1,-2,-3,... } - множина від’ємних цілих чисел, яка, очевидно, є зліченною.
Числова множина W називається щільною, якщо для будь-якої пари чисел a,b?W (a<b) завжди існує число c?W таке, що a<c<b.
Безпосередньо з означення випливає, що щільна множина завжди є нескінченною. Більш того, для кожної пари чисел a,b?W існує безліч чисел c?W, для яких виконується a<c<b.
Очевидно, що множина Z цілих чисел, а також будь-яка її підмножина (зокрема, множина N натуральних чисел) - не щільні. У той же час множина Q раціональних чисел є щільною множиною. Справді, для будь-яких раціональних чисел r1 і r2 (r1<r2) число r=(r1+r2)/2 задовольняє нерівності r1<r<r2. Зокрема, для всіх чисел r' з нескінченної множини раціональних чисел {r1+(r2-r1)/2i | i=1,2,...} виконуються нерівності r1<r' <r2.
Здавалося б зі щільності множини раціональних чисел повинно було б випливати, що ця множина має більшу потужність, ніж множина N або множина Z. Однак має місце таке твердження.
Наслідок 1.4.2. Множина Q всіх раціональних чисел зліченна.
Справді, множину Q можна подати як об’єднання таких зліченних множин:
A1 = {0,1,-1,2,-2,3,-3,...} - усі цілі числа (або дроби виду EMBED Equation.2 , n?Z),
A2 = { EMBED Equation.2 } - усі дроби виду EMBED Equation.2 , n?Z.
A3 = { EMBED Equation.2 } - усі дроби виду EMBED Equation.2 , n?Z,
.....................................................
Ak = { EMBED Equation.2 } - усі дроби виду EMBED Equation.2 , n?Z,
......................................................
Наслідок 1.4.3. Декартів добуток A?B зліченних множин A і B є зліченною множиною.
Справедливість цього твердження випливає з того, що множину всіх пар (a,b)?A?B, де A={a1,a2,...,an,...} і B={b1,b2,...,bn,...} можна подати як об’єднання такої зліченної сукупності зліченних можин
D1 = {(a1, b1 ), (a1, b2 ),..., (a1, bn ),... },
D2 = {(a2, b1 ), (a2, b2 ),..., (a2, bn ),... },
...........................................
Dk = {(ak, b1 ), (ak, b2 ),..., (ak, bn ),... },
...........................................
Зокрема, множина всіх точок координатної площини з раціональними координатами зліченна.
Наслідок 1.4.4. Декартів добуток Pn=A1?A2?...?An зліченних множин A1, A2,..., An - є зліченною множиною для довільного n.
Доведення проведемо методом математичної індукції.
Для n=1 P1=A1 і справедливість твердження випливає з умови зліченності множини A1. Нехай Pk-1=A1?A2?...?Ak-1 - зліченна множина. Тоді зліченність множини Pk = Pk-1?Ak випливає з наслідку 1.4.3.
Наслідок 1.4.5. Множина P усіх многочленів p(x) = a0xn+a1xn-1+...+an-1x+an з раціональними коефіцієнтами ai?Q, i=0,1,...,n, n=0,1,2,..., є зліченною множиною.
Множину P можна подати у вигляді об’єднання зліченної сукупності множин Pn, де Pn - це множина многочленів з раціональними коефіцієнтами, степінь яких не перевищує n, n=0,1,2,.... Разом із тим, будь-якому многочлену p(x)=a0xn+a1xn-1+ ...+an-1x+an з множини Pn можна поставити у відповідність кортеж (a0,a1,a2,...,an), який складається з раціональних чисел ai - коефіцієнтів цього многочлена. Очевидно, ця відповідність є взаємно однозначною. Отже, Pn ~ Qn+1. Тоді з наслідків 1.4.2 і 1.4.4 випливає, що множина Pn - зліченна, а тому зліченною є і множина P.
Назвемо число алгебричним, якщо воно є коренем деякого многочлена з раціональними коефіцієнтами. Відомо, що кожен такий многочлен має скінченну кількість коренів (не більшу від степені многочлена). Таким чином, множину всіх алгебричних чисел можна подати у вигляді об’єднання зліченної сукупності скінченних множин. Отже, має місце
Наслідок 1.4.6. Множина всіх алгебричних чисел зліченна.
Наслідок 1.4.7. Множина A всіх слів у заданому скінченному алфавіті A зліченна.
Справедливість твердження випливає з того, що
A* = {e} ? A ? A2 ? A3 ?...,
тобто множина A* є зліченним об’єднанням скінченних множин {e} і An, де An - множина всіх слів довжини n в алфавіті A.