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

Реферат на тему:

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

Множина A рівнопотужна множині N натуральних чисел називається зліченною множиною.

Іншими словами, зліченна множина A — це така множина, всі елементи якої можна занумерувати числами 1,2,3,…, тобто можна вказати спосіб, за яким першому елементу множини A ставиться у відповідність число 1, другому — число 2, третьому — число 3 і т.д. Отже, будь-яку зліченну множину A можна подати у вигляді A = {a1,a2,a3,…, an,…}.

Неважко переконатись, що множини квадратів натуральних чисел, усіх парних чисел, усіх непарних чисел, чисел кратних деякому числу k, чисел, які закінчуються парою цифр 00 тощо є зліченними множинами.

Перейдемо до вивчення властивостей зліченних множин.

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

Доведення. Оскільки M нескінченна множина, візьмемо два елементи a1, b1(M (a1(b1). Очевидно, множина M{a1,b1} є нескінченною множиною. Тоді візьмемо наступні два нові елементи a2, b2(M {a1, b1} (a2(b2) і т.д. Таким чином, ми виділимо з множини M дві зліченні множини A={a1,a2,…, an,…}(M і B={b1,b2,…, bn,…}(M. Це дозволяє підсилити формулювання теореми. А саме: будь-яка нескінченна множина M містить зліченну підмножину A і при цьому множина M A є нескінченною множиною (оскільки B (M A).

Теорема 1.3. Будь-яка підмножина зліченної множини є або скінченною, або зліченною множиною.

Доведення. Нехай A={a1,a2,…, an,…} - зліченна множина і B (A. Отже, B={a1,a2,…, ak,…} і можливі дві ситуації: або послідовність у фігурних дужках уривається на деякому елементі, тоді B — скінченна множина, або послідовність у дужках нескінченна, для якої, встановлюючи відповідність (l, al), l (N, одержуємо, що B — зліченна множина.

З теорем 1.2 і 1.3, зокрема, випливає, що зліченні множини є до певної міри найпростішими нескінченними множинами, бо, з одного боку, вони містяться в будь-якій нескінченній множині, а з другого — містять в собі тільки скінченні множини, або нескінченні множини, які є зліченними.

Теорема 1.4. Об'єднання скінченної або зліченної сукупності зліченних множин є зліченною множиною.

Доведення. Розглянемо спочатку скінченну сукупність зліченних множин {A1,A2,…, Ak}, де Ai={a1i, a2i,…, ani,…}, i=1,2,…, k. Запишемо всі елементи множин A1, A2,…, Ak в рядок таким чином: a11, a12,…, a1k, a21, a22,…, a2k,…, an1, an2,…, ank,…

Перенумеруємо записані елементи в порядку їх розташування в рядку. При цьому елемент, який вже одержав свій номер і повторно з «являється в рядку, з подальшої нумерації вилучається. В результаті кожен елемент об'єднання одержить свій номер, що і потрібно було довести.

У випадку зліченної сукупності множин Ai={a1i, a2i,…, ani,…}, i=1,2,…, перепишемо всі елементи множин Ai у такому порядку: a11, a12,a21,a13,a22,a31,a14,a23,a32,a41,…

Принцип переписування елементів множин A зображений за допомогою стрілок на рис. 1.4.

a11, a21, a31, …, an1,… A1.

((.

a12, a22, a32, …, an2,… A2.

((.

a13, a23, a33, …, an3,… A3.

(.

a14, a24, a34, …, an4,… A4.

…

Рис. 1.4.

Далі проводимо міркування аналогічні випадку скінченної сукупності множин. Теорему доведено.

З теореми 1.4 випливає низка цікавих наслідків.

Наслідок 1.4.1. Множина Z всіх цілих чисел зліченна.

Справді, подамо множину Z у вигляді Z = N ({0} (N «(, де N «(= { -1,-2,-3,… } - множина від'ємних цілих чисел, яка, очевидно, є зліченною.

Числова множина W називається щільною, якщо для будь-якої пари чисел a, b (W (a.

Безпосередньо з означення випливає, що щільна множина завжди є нескінченною. Більш того, для кожної пари чисел a, b (W існує безліч чисел c (W, для яких виконується a.

" .

d.

f.

n.

p.

r.

t.

v.

x.

z.

|.

~.

x02C6.

x0160.

x0152.

".

e.

e.

x0161.

*.

".

B (зокрема, множина N натуральних чисел) — не щільні. У той же час множина Q раціональних чисел є щільною множиною. Справді, для будь-яких раціональних чисел r1 і r2 (r1.

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

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

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

, n (Z),.

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