13.4: Діяльність

Діяльність\(\PageIndex{1}\)

У кожному з наступних, довести, що даний множина піддається підрахунку, проявляючи явно визначену двооб'єктивну відповідність між ним і\(\mathbb{N}\text{.}\)

1. Безліч натуральних чисел без урахування 0.
2. Безліч натуральних чисел, які більше\(9,999,999\text{.}\)
3. Безліч непарних натуральних чисел.
4. Множина цілочисельних степенів\(2\) (включаючи як додатні, так і від'ємні показники).

Діяльність\(\PageIndex{2}\)

Не обманюючи і не дивлячись на докази в цьому розділі, доведіть кожне з наступних тверджень. Можливо, ви захочете скористатися характеристикою підрахунку в Факті 13.1.2 замість технічного визначення лічильної множини.

Примітка: Кожне твердження, крім перших двох, може бути доведено безпосередньо з попередніх тверджень.

1. Кожна\(\mathbb{N}\) підмножина підрахунку.
2. Якщо два набори мають однаковий розмір і один з них є підрахунковим, то і інший.
3. Кожен набір, який має той самий розмір, що і підмножина\(\mathbb{N}\), підрахунок.
4. Кожна підмножина обчислюваного множини є підрахунковою.
5. Кожен набір, який має той самий розмір, що і підмножина обчислюваного множини, підраховується.
6. Набір, що містить незліченну підмножини, є незліченним

Діяльність\(\PageIndex{3}\)

1. Доведіть,\(\mathbb{N} \times \mathbb{N}\) що підраховується.

Підказка.

Використовуйте метод зиг-заг-через сітку, подібний до доказу підрахунку раціональних чисел. (Див. Теорему 13.1.1 та її доказ.)

2. Доведіть, що\(B\) якщо\(A\) і обидва лічильні, то так\(A \times B\text{.}\)

Підказка.

Ви можете зробити більше зиг-заг, або ви можете використовувати оператор Task a.

3. Доведіть, що\(Z\) якщо\(X\text{,}\)\(Y\text{,}\) і кожен підраховується, то так\(X \times Y \times Z\text{.}\)

Підказка.

Використовуйте операцію Task b двічі.

4. Який метод доказування, на вашу думку, ви б використали для підтвердження наступного твердження?

Якщо\(A_1, A_2, \ldots, A_n\) всі підрахункові, то так

\ begin {рівняння*} A_1\ times A_2\ times\ cdots\ times a_n\ text {.} \ end {рівняння*}

Діяльність\(\PageIndex{4}\): The Infinite Orchard Problem.

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

Діяльність\(\PageIndex{5}\)

Доведіть, що якщо\(A_0,A_1,A_2,\ldots\) нескінченна колекція множин, кожен з яких є зліченно нескінченним, то союз

\ begin {рівняння*}\ bigcup_ {n=0} ^\ infty a_n = A_0\ чашка A_1\ чашка A_2\ cup\ cdots\ end {рівняння*}
також незліченно нескінченна.

Підказка.

Що робити, якщо в кожному наборі була яблуня?

Діяльність\(\PageIndex{6}\)

\(\mathscr{F}\)Дозволяти представляти множини всіх функцій з доменом\(\{0,1\}\) і codomain\(\mathbb{N}\text{.}\)

1. Визначити двооб'єктивну відповідність між\(\mathscr{F}\) і\(\mathbb{N} \times \mathbb{N}\text{.}\)
2. Поясніть, чому Task a доводить,\(\mathscr{F}\) що підлягає підрахунку.

Підказка.

Див. розділ Активність\(\PageIndex{2}\) і активність\(\PageIndex{3}\).

Діяльність\(\PageIndex{1}\)

\(\mathscr{F}'\)Дозволяти представляти множини всіх функцій з доменом\(\mathbb{N}\) і codomain\(\{0,1\}\text{.}\)

Зверніть увагу, що кожен елемент\(\mathscr{F}'\) визначає нескінченну послідовність\(0\) s і\(1\) s.

1. Припустимо,\(A\) це підмножина підмножини\(\mathscr{F}'\text{.}\) (Так\(A\) це нескінченний список нескінченних послідовностей\(0\) s і\(1\) s.)

Опишіть, як побудувати елемент\(\mathscr{F}'\), який, безумовно, не в\(A\text{.}\) Тобто побудувати нескінченну послідовність\(0\) s і\(1\) s, яка, безумовно, не така ж, як будь-яка з нескінченних послідовностей в нескінченному списку\(A\text{.}\)

Підказка.

Використовуйте діагональний аргумент Кантора з доказу Лемми 13.1.1.

2. Поясніть, чому Task a доводить, що\(\mathscr{F}'\) це незліченно.

Підказка.

\(\mathscr{F}' \subseteq \mathscr{F}'\text{.}\)