Рахункові безлічі - студопедія

Безліч, рівносильне безлічі всіх натуральних чисел, називаетсясчётним.

Потужність безлічі натуральних чисел позначається # Тисячі чотиреста вісімдесят вісім; 0 = | N |.

Не більше ніж рахункове безліч - безліч рахункова або кінцеве.

Цим визначенням ми дістали з класу еквівалентності, який назвали рахунковим, одного представника - безліч натуральних чисел - і тепер є з чим порівнювати інші безлічі.

Будь-яка біекція # 957 ;. N → M називається нумерацією безлічі М. М = i | i = 0, 1,2, ...>.

Таким чином, якщо знайдена нумерація деякого безлічі, то тим самим доведено, що воно рахункова. Елементи рахункового безлічі називають також послідовністю.

Нехай заданий алфавіт А - деякий безліч символів, званих також буквами. Назвемо словом в даному алфавіті кінцевий ряд букв, написаних один за одним. Іноді зручно розглядати пусте слово, зовсім не містить букв - його позначають # 923 ;.

Доведемо, що в будь-якій мові є рахункова безліч слів

Теорема. Якщо алфавіт А кінцевий, то безліч слів в алфавіті А * лічильно.

Слідство. слів в алфавіті - рахункова число. Це - перевірка на коректність - ми знову підтвердили счетності безлічі натуральних чисел.

Теорема. Будь-яка підмножина рахункового безлічі не більше ніж лічильно.

# 9633; Нехай А - лічильно. Значить, його елементи можуть бути пронумеровані: 1. А2. ..., an, ...>. Елементи будь-якої підмножини ВÍА можна розташувати в порядку зростання номерів:. Отже, підмножина має нумерацію # 957; (n) = # 9632;

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

# 9633; Нехай А0 - безліч. Значить, воно непусто і $ а1 ÎА0. Покладемо А1 = А 0 \ 1>. А1 не порожньо, тому що в іншому випадку А0 = 1>, що суперечить припущенню про нескінченність А0. Продовжимо процедуру: в А1 знайдеться a2. покладемо А2 = А1 \ 2> = А0 \ 1. a2> ... і т.д.

На n-кроці отримаємо: Аn = А0 \ 1. ..., an> непусто, тому що в іншому випадку А0 = 1. ..., an>. Крім того, з побудови ai ≠ ak. якщо i ≠ k - елементи попарно різні. Тоді $ аn ÎАn і, по побудові, Аn + 1 = Аn \ n> непорожня множина.

Таким чином, по індукції ми побудували безліч, що складається з попарно різних елементів 1. А2. ..., an, ...>Î А0 з нумерацією # 957; (n) = an. # 9632;

З доведених теорем випливає, що рахункова безліч є мінімальним за потужністю з усіх нескінченних множин - тому, напевно, його і називають алеф нуль.

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

Теорема. Об'єднання будь-якого не більше ніж рахункового сімейства множин лічильно.

Занумеруем елементи об'єднання родин наступним чином:

a) I звичайно; б) I лічильно

Послідовність (a11, a21, a12, a22, a31, ...) - нумерація. Принцип її побудови такий - спочатку фіксується N = 2 і записуються аik такі, що i + k = N. Потім N → N + 1 і все повторюється.

Зауваження: У родинах можуть бути однакові елементи

Слідство. Безліч А * всіх слів в рахунковому алфавіті А лічильно. Нехай задана нумерація в А: A = 1. А2. ..., an, ...>

Позначимо через А n кінцевий алфавіт: Аn = 1. А2. ..., an>. Будь-яке слово в А * складається з кінцевого числа букв (за визначенням), тому воно є словом в деякому кінцевому алфавіті, а саме в Ak. k = max (k1. k2. ..., kn). Т.ч. безліч всіх слів в алфавіті А є об'єднання рахункового числа множин А1. А2, ..., Аn.

Приклад. Алгебраїчні числа. Коріння довільного многочлена an x ​​n + ... + a0. де аk - цілі числа, називаються алгебраїчними числами. Многочлен можна розглядати як слово в кінцевому алфавіті: А = - безліч таких слів лічильно, а коріння у многочлена кінцеве число. Тому і безліч всіх чисел алгебри лічильно.

Теорема. Безліч значень функції, визначеної на рахунковому безлічі, не більше ніж лічильно. # 957; (n) = f (an) - нумерація.

Теорема. Нехай А - безліч, а B - його не більше ніж рахункове підмножина. Тоді, якщо множина A \ B нескінченно, то воно рівносильне безлічі A.

Виберемо з A \ B рахункова підмножина C; з побудови B∩C = О. Об'єднання B і C лічильно, тому існує біекція f. BÇC → C. Треба побудувати біекція А → A \ B. побудуємо:

Слідство. якщо A нескінченно, а B не більше ніж лічильно, то об'єднання AÇB не більше ніж лічильно.