Изброими множества

Изброимостта на множество е нещо като еквивалент на големината на множествата, защото при безкрайните множества не можем да броим елементите, тъй като броят на елементите е неочаквано … безкраен. Големината на множество наричаме още мощност или кардиналност.

Големина на безкрайно множество

Да определим големината на крайно множество е лесно – броим елементите. Така множеството M = {a, b, c, d, e} има големина 5, записваме |M| = 5.

При безкрайните множества положението е значително по-сложно. Как бихме могли да сравним големината на безкрайни множества? Изобщо възможно ли е това, или всички безкрайни множества са „еднакво големи“?

За пример да вземем множеството на естествените числа и множеството на четните естествени числа. Имаме множествата ℕ = {1; 2; 3; 4; 5; 6; …} и S = {2; 4; 6; …}. Бихме казали, че множеството на естествените числа е по-голямо от множеството на четните числа, защото естествените числа съдържат всички четни числа и освен това още някои елементи – нечетните числа.

Така бихме могли да запишем, че S ⊂ ℕ, множеството S е собствено подмножество на множеството ℕ. И бихме могли да кажем, че щом S ⊂ ℕ, множеството ℕ е по-голямо – нали съдържа повече елементи от множеството S.

Една от причините да не можем да мерим множествата по релацията подмножество е, че множествата могат да имат различна големина, макар нито едното да не е подмножество на другото. Това може да се покаже и при крайните множества: A = {1; 3; 4; 9} и B = {b, u, r, z, m}. Изпълнено е: |A| = 4 и |B| = 5. Множеството B е по-голямо от множеството A, но въпреки това не е изпълнено A ⊂ B. При безкрайните множества това можем да видим при четните и нечетните числа. Нито едното множество не е подмножество на другото.

Релацията подмножество следователно не е идеален кандидат, за да решаваме дали едно множество е по-голямо от друго.

Биекция

Ще опитаме друг подход. Имаме две множества, A и B. Можем да кажем, че имат еднаква големина, ако между тях съществува биективно изображение. Какво означава това? Че вземаме елемент от множеството A, елемент от множеството B и образуваме двойка (a; b). Тези елементи махаме от множествата и продължаваме нататък. Ако успеем да „изпразним“ и двете множества, значи сме намерили биективно изображение.

Пример при крайни множества: A = {a, b, c} и B = {1; 2; 3}. Първата двойка би могла да е (a; 1), следващата (b; 2) и накрая (c; 3). Изчерпахме всички елементи и на двете множества, намерихме биективно изображение. Важното е, че това не е единственото биективно изображение. И това е валидно решение: (a; 3), (b; 1), (c; 2).

При безкрайните множества нещата са вече малко по-интересни. Ще опитаме с нечетните и четните естествени числа. Интуитивно усещаме, че трябва да са еднакво много. Да опитаме. Вземаме първото нечетно число и го изобразяваме върху първото четно число: (1; 2). После второто нечетно и второто четно: (3; 4). И т.н. Така получаваме двойките: (1; 2), (3; 4), (5; 6), (7; 8), … Бихме могли да запишем, че всяко нечетно число l се изобразява върху четното число l + 1 и всяко четно число s е образ на нечетното число s − 1. За всяко нечетно и за всяко четно число имаме някаква двойка, която съдържа това число. Множествата на нечетните и на четните числа са следователно еднакво големи.

Четни и естествени числа

Сега ще опитаме същия подход и ще сравним множеството на естествените и на четните числа. Имаме множествата ℕ = {1; 2; 3; 4; 5; 6; …} и S = {2; 4; 6; …}. Интуитивно очакваме, че множеството на естествените числа ще е по-голямо.

Да се опитаме обаче да намерим съответното биективно изображение. Можем да кажем, че всяко естествено число n се изобразява върху удвоеното си, върху 2n. Така получаваме двойките (1; 2), (2; 4), (3; 6), (4; 8), (5; 10), … За всяко естествено число n имаме двойка (n; 2n) и за всяко четно число s имаме двойка (s/2; s). Намерихме биективно изображение, множеството на четните числа и множеството на естествените числа са следователно еднакво големи, имат еднаква мощност.

Това може да изглежда странно, защото естествените числа все пак съдържат повече елементи от четните. Естествените числа съдържат всички четни числа и освен това всички нечетни числа. И все пак успяваме да намерим биекция, така че двете множества са еднакво големи.

Сравнение с естествените числа

Естествените числа всъщност определят най-малката големина на безкрайно множество. Дали някое друго множество има същата големина като множеството на естествените числа, често може да се установи доста лесно – достатъчно е да намерим биекция към естествените числа, което на практика означава, че е достатъчно да успеем да номерираме, да наредим елементите на нашето множество M.

Т.е. ако можем да наредим елементите на множеството така, че да решим кой елемент е първи, кой втори, трети, четвърти, десети и т.н., множеството е толкова голямо, колкото ℕ. За такова множество казваме, че е изброимо.

Лесно се вижда, че четните и нечетните естествени числа са изброими, защото можем да определим първото, второто, третото и т.н. четно/нечетно число. А четните цели числа? Т.е. множеството S = {…; −4; −2; 0; 2; 4; …}. Можем ли да ги наредим? Можем, достатъчно е да вземем същата наредба като преди и веднага след положителното четно число да запишем и отрицателния му вариант: S = {0; 2; −2; 4; −4; 6; −6; …}. Подобно е например и за целите числа.

Големина на рационалните числа

По-интересен пример са рационалните числа, дробите. Можем ли да ги наредим? Можем, но ще е вече малко по-сложно. Ще построим таблица с безкрайно много редове и стълбове. Във всяка клетка ще има дроб. В n-тия стълб и m-тия ред ще имаме дробта n/m. Т.е. в 1-вия стълб и 2-рия ред имаме $\frac{1}{2}$, а в третия стълб и четвъртия ред имаме 3/4.

$$\begin{array}{ccccc}1/1& 2/1& 3/1& 4/1& \dots \\ 1/2& 2/2& 3/2& 4/2& \dots \\ 1/3& 2/3& 3/3& 4/3& \dots \\ 1/4& 2/4& 3/4& 4/4& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}$$

Как да наредим, да номерираме сега тези числа? Не можем да ги номерираме по редове или по стълбове, защото веднага ще „потънем“ в съответния ред/стълб. Вместо това вземаме числата по диагоналите: (първи диагонал:) 1/1, (втори диагонал:) 2/1, 1/2, (трети диагонал:) 3/1, 2/2, 1/3, (четвърти диагонал:) 4/1, 3/2, 2/3, 1/4, … Има още много повтарящи се дроби, но това не пречи. По-важното е, че няма отрицателни числа. Това се решава лесно: всеки път, когато запишем някоя дроб, веднага след нея поставяме и отрицателния ѝ вариант. И тогава в самото начало ни липсва само нулата. И това е всичко – имаме всички рационални числа в една редица.

Общо получаваме редицата: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

Големина на реалните числа

Реалните числа толкова ли са, колкото са естествените? Решението ще е още по-сложно, отколкото при рационалните числа. Ще направим доказателство от противното. Допускаме, че реалните числа са изброими и че съществува биективно изображение към естествените числа. Допускаме, че могат да се наредят. И да кажем, че следната таблица е тази наредба:

$$\begin{array}{ccccccccc}0,& 3& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& 9& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& 3& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& 7& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& 7& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& 6& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& 0& \dots \\ \dots \end{array}$$

В таблицата са първите седем реални числа от нашата наредба. Тази наредба, разбира се, може да е произволна, не е нужно числата да са подредени по големина.

Според допускането в тази безкрайна таблица са наредени всички реални числа. (Таблицата отново е безкрайна, тук са само първите седем записа.) Сега ще се опитаме да намерим/построим такова число, което е реално, но не е в тази таблица. Ако намерим такова число, това е противоречие с допускането, че в таблицата са всички реални числа, от което можем да заключим, че множеството на реалните числа не е изброимо.

Числото, което не е в таблицата, ще построим така:

$$\begin{array}{ccccccccc}0,& \boxed{\text{3}}& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& \boxed{\text{9}}& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& \boxed{\text{3}}& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& \boxed{\text{7}}& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& \boxed{\text{7}}& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& \boxed{\text{6}}& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& \boxed{\text{0}}& \dots \\ \dots \end{array}$$

Започваме, като запишем 0,… Така ще изглежда в началото новото ни реално число. На първото място след десетичната запетая ще има цифра, която не е на първото място в първото реално число от нашата наредба (в таблицата е оградено с рамка). Там е цифрата 3, така че избираме например 1 и получаваме числото 0,1…

Продължаваме нататък. На второто място ще има цифра, която не е на второто място във второто реално число. Там е 9, така че например 2. Получаваме числото 0,12… На третото място ще има цифра, различна от третата цифра в третото реално число. Там е 3, така че избираме например 7. Получаваме 0, 127…

И така нататък и така нататък. Винаги на n-тата позиция на новото число ще има цифра, различна от цифрата на n-тата позиция в n-тото число от нашата наредба.

Какво постигаме с това? Получаваме число, което се различава от всички числа в нашата наредба най-малко с една цифра. Нека вземем последния временен резултат: 0,127… Това число със сигурност се различава от първото число в наредбата ни най-малко в първата цифра – защото така сме го построили. От второто число се различава най-малко във втората цифра. От третото – в третата цифра. В общия случай това ново число се различава от числото в наредбата, което е на n-то място, най-малко в цифрата на n-тата позиция.

Следователно това новопостроено число няма да намерим в таблицата, която трябваше да изразява биекцията между естествените и реалните числа. Реалните числа са следователно повече от естествените числа. Реалните числа не са изброими, те са неизброими.

Допълнителни източници

• Are there more odd or even numbers?