Зліченні множини, Детальна інформація
Зліченні множини
, n(Z.
, 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.
, 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.
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021