Зліченні множини, Детальна інформація

, n(Z,

.....................................................

, 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.