Зліченні множини (реферат)

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

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

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

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

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

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

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

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

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

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

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

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

Очевидно, що множина Z цілих чисел, а також будь-яка її підмножина (зокрема, множина N натуральних чисел) — не щільні. У той же час множина Q раціональних чисел є щільною множиною. Справді, для будь-яких раціональних чисел r1 і r2 (r1<r2) число r=(r1+r2)/2 задовольняє нерівності r1<r<r2. Зокрема, для всіх чисел r' з нескінченної множини раціональних чисел {r1+(r2-r1)/2i | i=1,2,…} виконуються нерівності r1<r' <r2.

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

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

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

A1 = {0,1,-1,2,-2,3,-3,…} - усі цілі числа (або дроби виду $$\frac{n}{1}$$, n.

A2 = { $$\frac{0}{2},\frac{1}{2},-\frac{1}{2},\frac{2}{2},-\frac{2}{2},\frac{3}{2},-\frac{3}{2},\text{.}\text{.}\text{.}$$ } - усі дроби виду $$\frac{n}{2}$$, n.

A3 = { $$\frac{0}{3},\frac{1}{3},-\frac{1}{3},\frac{2}{3},-\frac{2}{3},\frac{3}{3},-\frac{3}{3},\text{.}\text{.}\text{.}$$ } - усі дроби виду $$\frac{n}{3}$$, n.

…

Ak = { $$\frac{0}{k},\frac{1}{k},-\frac{1}{k},\frac{2}{k},-\frac{2}{k},\frac{3}{k},-\frac{3}{k},\text{.}\text{.}\text{.}$$ } - усі дроби виду $$\frac{n}{k}$$, n.

…

Наслідок 1.4.3. Декартів добуток Aзліченних множин 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зліченних множин A1, A2,…, An — є зліченною множиною для довільного n.

Доведення проведемо методом математичної індукції.

Для n=1 P1=A1 і справедливість твердження випливає з умови зліченності множини A1. Нехай Pk-1=A11 — зліченна множина. Тоді зліченність множини Pk = Pk-1випливає з наслідку 1.4.3.

Наслідок 1.4.5. Множина P усіх многочленів p (x) = a0xn+a1xn-1+…+an-1x+an з раціональними коефіцієнтами aii=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* є зліченним об'єднанням скінченних множин {e} і An, де An — множина всіх слів довжини n в алфавіті A.