МНОЖИНИ І ВІДНОШЕННЯ

Здавалося б зі щільності множини раціональних чисел повинно було б випливати, що ця множина має більшу потужність, ніж множина N або множина Z. Однак має місце таке твердження.

Наслідок 1.4.2. Множина Q всіх раціональних чисел зліченна.

Справді, множину Q можна подати як об’єднання таких зліченних множин:

A1 = {0,1,-1,2,-2,3,-3,...} - усі цілі числа (або дроби виду , nZ),

A2 = { } - усі дроби виду , nZ.

A3 = { } - усі дроби виду , nZ,

Ak = { } - усі дроби виду , nZ,

Наслідок 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=A1A2...An зліченних множин A1, A2,..., An - є зліченною множиною для довільного n.

Доведення проведемо методом математичної індукції.

Для n=1 P1=A1 і справедливість твердження випливає з умови зліченності множини A1. Нехай Pk-1=A1A2...Ak-1 - зліченна множина. Тоді зліченність множини Pk = Pk-1Ak випливає з наслідку 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 зліченна.