Рахункові множини

II.Определение 1. Пусть N безліч всіх натуральних чисел.

N={1, 2, 3,.. .}, тоді всяке безліч, А еквівалентну безлічі N називатиметься исчислимым, чи счётным безліччю. Отже, якщо безліч, А рахункове, то між безліччю Проте й безліччю натуральних чисел N можна встановити взаємно однозначне відповідність, чи, кажуть, можна занумерувати елементи безлічі А, розуміючи під номером кожного елемента, а (А відповідне йому за зазначеному відповідність натуральне число. Як із визначення счётного безлічі слід очевидний висновок, що це счётные безлічі еквівалентні між собою. Ось лише кілька прикладів счётных множеств:

А={1, 4, 9, 16,. .., n[pic],.. .};

B={3, 6, 9, 12,. .., 3n,. .. };

C={[pic],[pic]};

D={1, 8, 27, 64,. .., n[pic],. .. };

Теорему 1. Щоб безліч Х було счётным необхідне й досить, що його можна було «перенумерувати», тобто явити у формі последовательности:

Х={x[pic], x[pic], x[pic],. .., x[pic],. .. } .

Доказ необхідності: Нехай безліч Х рахункове, те з визначення счётного безлічі слід існування взаємно однозначного відповідності (між безліччю Х і безліччю натуральних чисел N. Досить позначити через х[pic], той із елементів безлічі Х, що у відповідність до (відповідає числу n, чтобы скласти уявлення безлічі Х у вигляді (*).

Доказ достатності: Якщо безліч Х представлено у вигляді (*), досить кожному його елементу x, співвіднести індекс n цього елемента, щоб отримати взаємно однозначного відповідності (між безліччю Х і безліччю натуральних чисел N, тож із визначення счётного безлічі слід, що багато Х счётное.

Наступна теорема дає цікавий приклад счётного множества.

Теорему 2. Раціональні числа R утворюють счётное безліч. Доказ: Розглянемо спочатку раціональні неотрицательные числа. Розташуємо в нескінченну таблицю так: під час першого рядок помістимо гаразд зростання в цілі числа 0, 1, 2,. ..; на другу — все позитивні несократимые дробу зі знаменником 2, впорядковані за величиною чисельника; загалом у n-ую рядок, n=1, 2, 3, …, — все позитивні раціональні числа, які записуються несократимой зі знаменником n, впорядковані за величиною чисельника. Вочевидь, що кожен раціональне ненегативне число потрапить на місце у получившейся таблице;

— 2 ;

0. 1 2 3 4.. .

[pic] [pic] [pic] [pic] [pic].. .

[pic] [pic] [pic] [pic] [pic].. .

.. .. .. .. ... .

[pic]. .. .. .. .. .

.. .. .. .. ... .

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

.. .

... .

.. .. .

.. .. .. Усе раціональні неотрицательные числа виявляються занумерованными, тобто довели, що вони утворюють счётное безліч. Щоб переконається, як і безліч всіх раціональних чисел також счётно, досить їх записати у таку ж таблицю. Це можна зробити, наприклад, помістивши в написану вище таблицю після кожного позитивного раціонального числа x в тугіше рядок число — х.

0. 1 -1 2 -2.. .

[pic] -[pic][pic]-[pic] [pic].. .

[pic] -[pic][pic]-[pic] [pic].. .

.. .. .. .. .. .

[pic] -[pic].. .. ... .

.. .. .. .. .. .. Перенумеровав елементи таблиці у той спосіб, як і вище, ми маємо, що багато всіх раціональних чисел є счётным безліч. III. Сформулюємо і доведемо кілька теорем характеризуючих лічильні множества.

— 3 ;

Теорему 3. З будь-якого нескінченного безлічі Х можна назвати рахункове безліч Y. Доказ: Нехай безліч Х безліч. Виділимо з багатьох Х довільний елемент і позначимо його х1. Так безліч Х нескінченно, воно не вичерпується виділення цього елемента х1. і ми можемо виділити елемент х2 з безлічі Х{ х1}. З тих самих міркувань безліч Х{ х1, х2} не порожньо, і ми і потім із нього виділити елемент х3. Через нескінченності безлічі Х ми можемо продовжувати той процес необмежено, у результаті одержимо послідовність виділених елементів х1, х2, х3,. .. , хn,. .. , що й утворює дані підмножина Y безлічі Х. Ця теорема може наштовхнути на цікаве запитання. На своє чергу чи можна з счётного безлічі виділити нескінченне підмножина, що було як і счётным? Саме це запитання відповідає наступна теорема.

Теорему 4. Будь-яке нескінченне підмножина счётного безлічі як і є счётным безліччю. Доказ: Нехай безліч Х счётное безліч, а безліч Y його нескінченне підмножина. Отже, безліч Х то, можливо представлено в виде.

Х={а1, А2, а3,. .. , аn,.. .}. Будемо перебирати одна одною елементи безліч Х гаразд їх номерів, цьому ми раз у раз будемо зустрічати елементи безлічі Y, і з елементів безлічі Y рано чи пізно зустрінеться нам. Співвідносячи кожному елементу безлічі Y номер «зустрічі» з нею, ми перенумеруем безліч Y, причому у силу нескінченності його, доведеться з цього нумерацію витратити все натуральні числа. Отже, безліч Y є счётным множеством.

Наведемо приклад безпосередньо належить до цієї теоремі. Приклад: Безліч Х={1, [pic],[pic]} як відомо, є счётным безліччю, бо як безліч Y={[pic],[pic]} є підмножиною безлічі Х, то доведеною вище теореми 3, безліч Y як і є счётным. З вище викладеної теореми випливає такі слідство. Слідство: Якщо з счётного безлічі Х видалити кінцеве підмножина Y, то що залишилося безліч ХY буде счётным множеством.

IV. Теорему 5. Об'єднання кінцевого числа й счётного безлічі без загальних елементів є счётное безліч. Доказ: Нехай дано.

А={а1, А2,. .. , аn} і В={b1, b2, b3,. .. },.

причому А (В = О. pic] Якщо безліч С=А (В, то З можна в форме.

С={а1, А2,. .. , аn, b1, b2, b3,. .. }, після чого ставати очевидною можливість перенумерувати безліч, отже по теоремі 1 отримуємо, що багато З счетно.

— 4 ;

Теорему 6. Об'єднання кінцевого числа попарно не від перетинання счётных множин є счётное безліч. Доказ: Проведемо доказ для випадку об'єднання трьох множин, з контексту буде зрозумілою повна спільність міркування. Нехай А, У, З три счётных множества:

А={а1, А2, а3,.. .}, В={b1, b2, b3,. .. } и.

С={с1, с2, с3,.. .}. Тоді безліч D = А (В (С можна у вигляді последовательности:

D={а1, b1, c1, А2, b2, c2, а3,.. .}, і счётность безлічі D очевидна.

Теорему 7. Об'єднання счётного безлічі попарно не від перетинання кінцевих множин є счётное безліч. Доказ: Нехай Аk (k=1, 2, 3,.. .) суть попарно не від перетинання кінцевих множеств:

А1={[pic]. .. , [pic]};

А2={[pic].. ., [pic]};

А3={[pic]. .. ,[pic]};

.. .. .. .. .. .. .. .

Щоб розмістити об'єднання З у вигляді послідовності, досить виписати підряд усі елементи безлічі А1, та був елементи безлічі А2 й дуже далее.

Теорему 8. Об'єднання счётного безлічі попарно не від перетинання счётных множин є рахункове безліч. Доказ: Нехай безлічі Аk (k=1, 2, 3,.. .) попарно не перетинаються і лічильні. Запишемо ці безлічі наступним образом:

А1={[pic]. .. };

А2={[pic]... };

А3={[pic]. .. };

.. .. .. .. .. .. Якщо ми випишемо елемент [pic], потім обидва елемента [pic] і [pic] які мають сума верхнього й нижнього індексів дорівнює 3, потім елементи які мають ця сума дорівнює 4, тощо, то безліч С=[pic] виявиться поданої у формі последовательности:

З = {[pic][pic][pic]. .. }, Звідки і треба счётность безлічі З. Зауваження: Умова відсутності загальних елементів в теоремах 5−8 може бути опущено.

— 5 ;

V. Використовуючи доведені вище теорем можна навести інше доказ теореми 2 не на предыдущего.

Доказ теореми 2: Безліч дробів виду [pic] з цим знаменником q, тобто безліч [pic].. ., очевидно счётное. Але знаменник може взяти також счётное безліч натуральних значень 1, 2, 3,. ... Отже з теореми 8, безліч дробів виду [pic] є счётным безліччю; видаляючи з нього всі сократимые дробу і застосовуючи теорему 4, переконуємося в счётности безлічі всіх позитивних раціональних чисел R+. Оскільки безліч Rнегативних раціональних чисел очевидно еквівалентно безлічі R+, то рахунковим є і це, тоді счётно і безліч R, бо R= R+[pic]R- [pic]{0}. З теореми 2 випливає такі очевидне слідство. Слідство. Безліч раціональних чисел будь-якого сегмента [a, b] є счётным безліччю. Сформулюємо як теореми іще одна приклад счётного безлічі. Теорему 9. Безліч Р всіх пар натуральних чисел є рахунковим безліччю. Відступ: Під парою натуральних чисел розуміють два натуральних числа даних в певному порядку. Доказ: Назвемо заввишки пари (n, m) натуральне число n+m. Вочевидь, є рівно k-1 пар даної висоти k, де k>1, именно.

(1, k-1), (2, k-2),. .. , (k-1, 1). У цій позначаючи через Рk безліч всіх пар висоти k, бачимо що багато Р є об'єднання счётного безлічі кінцевих множин Рk, а звідси по теоремі 7 отримуємо що багато Р є счётным множеством.

Теорему 10 також дає цікавий приклад лічильного безлічі. Теорему 10. Безліч P. S всіх кінцевих послідовностей, що складаються з елементів даного счётного безлічі D, є счётное безліч. Доказ: (посредствам повної математичної індукції) З попередньої теореми випливає, що багато пар, що складаються з елементів счётного безлічі D, є счётное безліч. Припустимо, що доведено счётность безлічі Sm всіх послідовностей, які з m елементів даного счётного безлічі D. Доведемо, що багато Sm+1 всіх послідовностей, які з m+1 елементів безлічі D також счётно. У насправді, пусть.

D={d1, d2,. .. , dk,.. .}. Кожній послідовності S (m +1)=(di[pic],. ., di[pic], dk)(Sm+1 відповідає пара (S (m), dk), де S (m)= (di[pic],. ., di[pic])(Sm, причому різним парам відповідають різні пари цього виду. Оскільки безліч Sm всіх S (m) счётно, і то, можливо записано як S[pic],. .. , S[pic],. .. , то счётно і безліч всіх пар (S[pic], dk) (взаємно однозначно відповідних парам натуральних чисел індексів і, k), отже, і безліч всіх S (m +1). Оскільки кожне Sm счётно, то счётно і безліч P. S, що доводить теорему. Наприкінці доведемо таку, дуже загальну теорему:

— 6 ;

Теорему 11. Якщо елементи безлічі А визначаються n значками, кожен із яких незалежно з інших пробіга счётное безліч значень А={a[pic],[pic],. .. ,[pic]} (xk=x[pic], x[pic],. ..; k=1, 2, 3, .

.., n), то безліч, А счётно. Доказ: Доведемо теорему методом математичної індукції. Теорему очевидна, якщо n=1, тобто є лише одне значок. Припустимо, що теорема правильна для n=m, і покажемо, що вона справедлива для n=m+1. Отже нехай А={a[pic],[pic],. .. ,[pic], [pic]}. Означимо через Ai безліч тих елементів Щодо яких [pic], де [pic] одне з можливих значень (m+1)-го значка, т. е. між іншим Ai =={a[pic],[pic],. .. ,[pic], [pic] }. З огляду на зробленого припущення безліч Ai счётно, бо як А=[pic], то счётно і безліч А. Ось лише кілька пропозицій, що випливають із цієї теореми: 1) Безліч точок (x, y) площині, які мають обидві координати раціональні, счётно. Але цікавішим є такий факт: 2) Безліч багаточленів [pic]с цілими коефіцієнтами счётно. У насправді, це безпосередньо випливає з теореми 11, за умови що розглядати багаточлени фіксованою ступеня n, й у завершення докази слід застосувати теорему 8.

— 7 ;

———————————- 7.

2 ??††?†???††?††??? 1.. .. .. ... .