Зчисленні множини

Означення. Множина Х називається зчисленною, якщо вона еквівалентна множині натуральних чисел N, тобто card X = card N = а.

Теорема (необхідна і достатня умова зчисленності). Для того, щоб множина А була зчисленною необхідно і достатньо, щоб її елементи можна було представити у вигляді послідовності.

Доведення. Необхідна умова. Нехай card A=a A~N, тобто існує бієкція Для будь-якого а А існує єдине , тобто елемент а розташуємо на n-му місці у послідовності. Таким чином всі елементи множини А розташуються у послідовності.

Достатня умова. Нехай тоді a_n↔n, тобто , бієкція: A→N. Отже A~N, що і доводить теорему.

Приклад 1. Z~N, оскільки

Розглянемо теореми про властивості зчисленних множин.

Теорема 1. У будь-якій нескінченій множині можна вибрати зчисленну підмножину.

Доведення. Нехай А – нескінченна множина. Візьмемо будь-яке і позначимо а₁. Оскільки А нескінченна, то у множині А\ є елементи. Візьмемо будь-який елемент з А\ та позначимо його а₂. У множині А\ є елементи. Продовжуючи процес отримуємо множину , що й треба довести.

Теорема 2. Об’єднання скінченної або зчисленної множин – зчисленне.

Доведення. Нехай , де card A_i=a, i =1,…. Покажемо, що card A=a, тобто А~N. Оскільки А_і~N то для кожного i =1,… множини А_і можливо представити у вигляді послідовності: , i =1, 2, ….

Множину А можливо представити у вигляді

, тоді , де розташування елементів у порядку зросту суми індексів. Згідно теореми A~N, що і треба було довести.

Теорема 3. Декартовий добуток скінченого числа зчисленних множин - зчисленний.

Доведення. Нехай А= , де А_і – зчисленні. Доведемо по індукції. Нехай n=2 , де - зчисленна оскільки А₁ – зчисленна. Оскільки А₂ – зчисленна, то - зчисленне об’єднання зчисленних множин – тобто зчисленна множина, згідно з властивістю 2.

Нехай при n=k (А= ), А – зчисленна. Доведемо, що при n=k+1 А= - зчисленна. Отже

А= , множина - зчисленна, згідно припущення, а A_k+1 – зчисленна за умовою. Згідно доведення для n=2 добуток - зчисленна множина, що й треба було довести.

Приклад 2 Множина алгебраїчних чисел - зчисленна.

Нехай А – множина алгебраїчних чисел, тоді , де А_n множина коренів многочленів порядку n з раціональними коефіцієнтами. Позначимо - множина коренів многочленна а₀хⁿ+…+a_n (вона скінченна), тоді .

Множина наборів (а_0, …, a_n), а_{і , і=0,…n} зчисленна згідно властивості 3, тобто об’єднання - зчисленне об’єднання скінченних множин. Згідно з властивістю 2 А_n – зчисленне, тоді теж зчисленне.

Приклад 3. card Q=a. Дійсно - зчисленна.

Теорема 4. Нехай X- нескінчена множина і card А = а, тоді Х А ~ X.

Доведення. Оскільки Х – нескінченна, то існує зчисленна множина М Х, тоді

(card A M=a)

, тобто .