Крайни подмножества

[Гост]

Множеството 2 ^ N от всички подмножества на N е неизброимо. А какво е множеството от всички крайни подмножества на N - изброимо или неизброимо. ( N e множеството на естествените числа).

[ptj]

Изобщо не съм съгласен с написаното. Изброимо множество от изброими множества също е изброимо множество.

Образно казано за да е изброимо едно множество трябва да съществува наредба за неговите елементи.

Едно множество е неизброимо ако съществува съответствие между него и кое да е друго неизброимо множество.

Неизброими множества са [tex]I,R,C[/tex], всеки интервал върху числовата права...

Доколкото ми е известно, все още няма утвърдителен отговор дали съществуват множества с междинна мощност между тези на [tex]N[/tex] и [tex]I[/tex].

--------------------------------------------------------------------
Тривиално доказателство за първия ми ред:
Записваш въпросните изброими множества едно под друго, след това започваш да броиш елементите на получената безкрайна матрица по нараствашия номер на диагоналите успоредни на главния (без значение дали ще избереш нагоре-надясно или надолу-наляво за посока).

[Kre4etalo]

Към ptj - това, което казваш, колега, е вярно, но не е пряко свързано с първото твърдение на автора на въпроса. Всъщност е свързано обаче с втория му въпрос. Това, че множеството от всичко подмножества на естествените числа е неизброимо, се доказва например с диагоналния аргумент на Кантор.
Към питащия - множеството от крайните подмножества е изброимо. Идеята е да разбиеш по големините на тези подмножества. Първо доказваш, че множеството от n-елементните подмножества на множеството на естествените числа е изброимо (за всяко n), а след това вземаш правиш обединение по n. Както каза ptj, изброимо обединение (по n) на изброими множества, дава отново изброимо множество.
За размера на n-елементните -

Скрит текст: покажи

Това, че n-елементните подмножества са изброимо много, може да се докаже чрез този факт и индукция. Очевидно 1-елементните са изброимо много. Сега как доказваме за 2-елементните - ами фиксираме един елемент от множеството (условно казано "първия") и меним втория елемент - получаваме изброимо много подмножества (тук използваме това, което знаем за 1-елементните). Сега като започнем да меним и първия елемент, получаваме иброимо обединение на изброими множества.