Доказать что множество целых чисел счетно

1.6. Счетные множества

Определение 1.3. Множество, эквивалентное множеству натуральных чисел N = <1, 2, 3, …, n,…>, называется счетным.

Можно сказать также, что множество счетно, если его элементы можно перенумеровать.

Следующие множества являются счетными:

Чтобы установить счетность некоторого множества, достаточно указать взаимно однозначное соответствие между элементами данного множества и множества натуральных чисел. Для примера 1.19 взаимно однозначное соответствие устанавливается по следующим правилам: для множества A₁: –n  n; для множества A₂: 2 n  n; для множества A₃: 2n  n; счетность множества A₄ установлена в примере 1.19;

Установить счетность множеств можно также, используя следующие теоремы о счетных множествах (приводятся без доказательств).

Теорема 1. Всякое бесконечное подмножество счетного множества счетно.

Множество A = <3, 6, …, 3n,…> счетно, т.к. A – бесконечное подмножество множества натуральных чисел, A  N.

Теорема 2. Объединение конечной или счетной совокупности счетных множеств счетно.

Множество A = <0, 1, …, n,…> неотрицательных целых чисел счетно, множество B = <0, –1, …, –n,…> неположительных целых чисел тоже счетно, поэтому множество всех целых чисел С = АB = <…, –n, …– 2, –1, 0, 1, 2, …, n, …> тоже счетно.

Теорема 3. Множество всех рациональных чисел, т.е. чисел вида , гдеp и q целые числа, счетно.

Теорема 4. Если А = <a₁, a₂, …> и B = <b₁, b₂, …> – счетные множества, то множество всех пар С = <(a_k, b_n), k = 1, 2,…; n = 1, 2, …> счетно.

Геометрический смысл пары (a_k, b_n) – точка на плоскости с рациональными координатами (a_k, b_n). Поэтому можно утверждать, что множество всех точек плоскости с рациональными координатами счетно.

Теорема 5. Множество всех многочленов P(x) = a₀ + a₁x + a₂x 2 + … + a_nx n любых степеней с рациональными коэффициентами a₀, a₁, a₂, … a_n счетно.

Теорема 6. Множество всех корней многочленов любых степеней с рациональными коэффициентами счетно.

1.7. Множества мощности континуума

Существуют бесконечные множества, элементы которых нельзя перенумеровать. Такие множества называются несчетными.

Теорема Кантора. Множество всех точек отрезка [0, 1] несчетно.

Пусть множество точек отрезка [0, 1] счетно. Значит, эти точки можно перенумеровать, т. е. расположить в виде последовательности x₁, x₂ … x_n, … .

Разобьем отрезок [0, 1] на три равные части. Где бы ни находилась точка x₁, она не может принадлежать всем отрезкам , , . Поэтому среди них есть отрезок ₁, не содержащий точку x₁ (рис. 1.7). Возьмем этот отрезок ₁ и разделим его на три равные части. Среди них всегда есть отрезок ₂, не содержащий точку x₂. Разделим этот отрезок на три равные части и т. д. Получим последовательность отрезков ₁  ₂  ₃ …_n … . В силу аксиомы Кантора сходится к некоторой точке x при n  . По построению эта точка x принадлежит каждому отрезку ₁, ₂, ₃,…, _n, …, т. е. она не может совпадать ни с одной из точек x₁, x₂, … x_n, …, т. е. последовательность x₁, x₂ … x_n, …не исчерпывает всех точек отрезка [0, 1], что противоречит первоначальному предположению. Теорема доказана.

Множество, эквивалентное множеству всех точек отрезка [0, 1] называется множеством мощности континуума.

Так как множества точек интервалов, отрезков и всей прямой эквивалентны между собой, то все они имеют мощность континуума.

Чтобы доказать, что данное множество имеет мощность континуума, достаточно указать взаимно однозначное соответствие между данным множеством и множеством точек отрезка, интервала или всей прямой.

Из рис. 1.8 следует, что множество точек параболы y = x 2 эквивалентно множеству точек прямой – < x <  и, следовательно, имеет мощность континуума.

Установить мощность континуума можно также, используя следующие теоремы о множествах мощности континуума (приводятся без доказательств).

Теорема 1. Множество всех подмножеств счетного множества счетно.

Теорема 2. Множество иррациональных чисел имеет мощность континуума.

Теорема 3. Множество всех точек n—мерного пространства при любом n имеет мощность континуума.

Теорема 4. Множество всех комплексных чисел имеет мощность континуума.

Теорема 5. Множество всех непрерывных функций, определенных на отрезке [a, b] имеет мощность континуума.

Итак, мощности бесконечных множеств могут различаться. Мощность континуума больше, чем мощность счетного множества. Ответ на вопрос, существуют ли множества более высокой мощности, чем мощность континуума, дает следующая теорема (приводится без доказательства).

Теорема о множествах высшей мощности. Множество всех подмножеств данного множества имеет более высокую мощность, чем данное множество.

Из этой теоремы следует, что множеств с максимально большой мощностью не существует.

Эквивалентные множества

Мощностью конечного множества называют число элементов этого множества.

В общем случае мощность множества A обозначают |A|.

Для конечных множеств чаще встречается обозначение n(A).

Конечные множества легко сравнивать по мощности.

Если n(A) = n(B), то конечные множества A и B равномощны.

Например: Мощность множества A= <1;3;5;7>равна n(A)=4.

Мощность множества B = <-3;13;2;4>равна n(B) = 4.

Множества A и B равномощны.

Взаимно однозначное соответствие двух множеств

Говорят, что между множествами A и B установлено взаимно однозначное соответствие , если:

1) каждому элементу множества A соответствует только один элемент множества B;

2) каждый элемент множества B при этом соответствует некоторому элементу множества A;

3) разным элементам множества A соответствуют разные элементы множества B.

Каждый раз, когда мы «считаем» множество каких-то объектов, мы устанавливаем взаимно однозначно соответствие между этим множеством и подмножеством натуральных чисел от 1 до некоторого n.

С этой точки зрения утверждение

«У Толи три друга: Вася, Коля и Петя» выглядит как соответствие:

Друзья Толи

Эквивалентность

Множества A и B называют эквивалентными (равномощными) , если между ними можно установить взаимно однозначное соответствие.

Обозначение: $A \sim B$ .

Такой подход даёт нам возможность сравнивать по мощности не только конечные, но и бесконечные (!) множества.

Сравним мощности множеств натуральных и натуральных чётных чисел:

Несмотря на бесконечность обоих множеств и отношение вложенности $B \subset A$, получаем взаимно однозначное соответствие, и может утверждать, что множества равномощны |A| = |B| и эквивалентны $A \sim B$.

Для мощности натуральных чисел используется специальное обозначение:

Счётные и несчётные множества

Множество называют счётным , если оно эквивалентно множеству натуральных чисел.

Чтобы доказать счётность множества достаточно придумать правило, по которому нумеруются его элементы.

Докажем, что множество целых чисел счётно.

Получаем взаимно однозначное соответствие между множествами целых и натуральных чисел. Значит, эти множества эквиваленты $\Bbb Z \sim \Bbb N$, и множество $\Bbb Z$ счётно.

Что и требовалось доказать.

Множество действительных точек отрезка [0;1] несчётно .

Мощность этого множества равна мощности континуума, $ c \gt \aleph_0$

Таким образом, множество отрезка [0;1]оказывается мощнее всего множества натуральных чисел.

Любой отрезок [a;b] и отрезок [0;1] эквивалентны.

Мощность любого действительного отрезка равна мощности континуума.

Любое множество, эквивалентное отрезку [0;1], называют континуальным .

Чтобы доказать несчётность множества, нужно показать, что нет таких правил, по которым можно его посчитать. Это значительно сложнее, чем доказать счётность.

Примеры

Пример 1. Среди данных конечных множеств укажите пары эквивалентных:

n(A) = 3, n(B) = 3, n(C) = 2

Запишем с помощью перечисления:

n(A) = 3, n(B) = 3, n(C) = 3

$A \sim B, B \sim C, A \sim C$

Пример 2. Пусть A — множество всех окружностей плоскости, B — множество всех правильных треугольников этой плоскости. Каждому треугольнику ставится в соответствие вписанная в него окружность. Является ли это соответствие взаимно однозначным?

Рассматриваем соответствие $B \rightarrow A$.

В каждый треугольник можно вписать окружность, и притом только одну. Условие единственности (1) выполняется.

Вокруг каждой окружности можно описать бесконечное количество правильных треугольников, поворачивая их на некоторый угол относительно центра окружности.

Условие (2) не выполняется.

Соответствие не является взаимно однозначным.

Пример 3. Постройте взаимно однозначное соответствие между отрезком [0;1] и отрезком [2;7] с помощью линейной функции.

Искомая функция имеет вид y = kx+b, где

$$x \in [0;1], y \in [2;7]$$

Прямая проходит через две точки: A(0;2),B(1;7).

$$ \frac <1>= \frac <7-2>\Rightarrow 5x = y-2 \Rightarrow y = 5x+2 $$

$$ x \in [0;1] \overset \mapsto y \in [1;7] $$

Пример 4*. Постройте взаимно однозначное соответствие между отрезком [0;1] и отрезком [a;b], $a \in \Bbb R, b \in \Bbb R$ с помощью линейной функции.

Искомая функция имеет вид y=kx+b, где $x \in \Bbb [0;1], y \in \Bbb [a;b]$

Прямая проходит через две точки: A(0;a),B(1;b). Уравнение прямой:

$$ \frac <1>= \frac \Rightarrow (b-a)x = y-a \Rightarrow y = (b-a)x+a $$

Доказать что множество целых чисел счетно

· Множество четных чисел 2N – счетное. Действительно, биекцию задает, например, отображение .

Доказательство. Можно считать, что все множества и элементы в них уже пронумерованы. Пусть , , , … . Расположим все элементы объединения следующим образом и пронумеруем в порядке, указанном стрелкой:

Понятно, что при указанном способе рассмотрения элементов всякий элемент рано или поздно получит свой номер. Если имеют непустые пересечения и в процессе нумерации встречаются элементы уже ранее пронумерованные, то их будем пропускать и переходить к следующим элементам.

Доказательство. Пусть . Элементы декартового произведения расположим так же, как и в предыдущем примере (в виде бесконечной вправо и вниз прямоугольной таблицы) и пронумеруем аналогично. Таким образом, произведение двух счетных множеств — счетно. Дальше по индукции для любого числа множителей.

Доказательство. Представим множество всех рациональных чисел в виде , где Q+ И Q — — подмножества положительных и отрицательных рациональных чисел, соответственно. Достаточно показать, что Q+ Счетно. А это действительно так, поскольку

Глава 1 Счётные и несчётные множества

Рассмотрим ряд примеров на определение счётности/несчётности множеств:

1. \(\mathbb\) = <1, 2, 3, …>;
2. \(\mathbb\) = <- … , -3, -2, -1, 0, 1, 2, 3, …>;
3. \(\mathbb\) = < \(\frac\) | \(m\in\mathbb\) , \(n\in\mathbb\) > ;
4. \(\mathbb\) – множество действительных чисел;
5. Точки на плоскости с целыми координатами;
6. [0 ; 1] ;
7. [0 ; 1] \(\times\) [0 ; 1] = < (x, y) | \(x\in\) , \(y\in\) >;
8. Множество бесконечных последовательностей из нулей и единиц.

Будет рассматривать эти примеры в ходе изложения в порядке их нумерации.

1.1 Счётное множество

Определение:
Счётное множество — это либо конечное, либо равномощное натуральным числам множество (иными словами, каждому элементу можно сопоставить натуральное число взаимно однозначно, то есть так, что ни один элемент в таких множествах не будет пропущен).

Элементы множества натуральных чисел можно пронумеровать, следовательно множество \(\mathbb\) — счетно.

По определению счетного множества, множество целых чисел \(\mathbb\) — счётно, так как целые числа можно расположить в виде последовательности 0, 1, −1, 2, −2, 3, −3, … . Иными словами, можно привести взаимнооднозначное соответствие между целыми и натуральными числами, например, таким способом (см. рисунок):
\(0\leftrightarrow1\)
\(1\leftrightarrow2\)
\(-1\leftrightarrow3\)
\(2\leftrightarrow4\)
\(-2\leftrightarrow5\)
\(3\leftrightarrow6\)
…

1. Докажем счетность множества рациональных чисел:
   Расположим рациональные числа в виде таблицы, строку которой с номером n образуют дроби со знаменателем n. Нумеруем по прямоугольникам, начиная с нуля и пропуская при этом числа, которые уже получили номер ранее. Так, любое рациональное число получит некоторый номер, что доказывает счетность множества рациональных чисел.

1.2 Сравнимость мощностей

Утверждение: Если множество А равномощно подмножеству В, то либо мощность А меньше мощности В, либо А и В равномощны.

1. Из курса высшей алгебры:
   Для доказательства счетности множества предположим противное. Пусть множество \(\mathbb\) состоит из чисел a₁,a₂,…,a_n,…. Рассмотрим дробные части \(\alpha\) _n чисел a_n, 0 < \(\alpha\) _n < 1, расположим в виде таблицы:
   \(\alpha\) ₁ = 0, \(\alpha\) ₁₁, \(\alpha\) ₁₂, …, \(\alpha\) _1n, …
   \(\alpha\) ₂ = 0, \(\alpha\) ₂₁, \(\alpha\) ₂₂, …, \(\alpha\) _2n, …
   …
   Чтобы опровергнуть гипотезу о счетности множества \(\mathbb\) , приведем пример числа a, отличного от всех чисел a₁,a₂,…,a_n,… .
   Рассмотрим число \(\beta\) = 0, \(\beta\) ₁, \(\beta\) ₂, …, \(\beta\) _n, … . Пусть \(\beta_1\ne\alpha_<11>\) , \(\beta_2\ne\alpha_<22>\) , …, \(\beta_n\ne\alpha_\) , тогда \(\beta_k\ne\alpha_k\) , k = 1,2,…,n,…, т.е. это число не совпадает ни с одним из чисел a₁,a₂,…,a_n,…, что означает, что наше предположение о том, что все числа множества \(\mathbb\) удалось пронумеровать, привело к противоречию, и множество несчетно.

Кроме того, \(\mathbb\)

[0 ; 1] — это несчетные множества с одинаковой мощностью. Однако как можно показать, что \(\mathbb\) не мощнее [0 ; 1] ? Для наглядности можно использовать график арктангенса. Преобразуем его до вида \(atan(x)/pi+1/2\) . Видно, что его асимптоты будут иметь координаты 0 и 1 по оси ординат. Также видно, что каждой точке на оси X (эквивалентно множеству \(\mathbb\) ) соответствует значение на оси Y, причем каждое из соответствующих значений лежит в промежутке от нуля до единицы. Таким образом, \(\mathbb\)

1. Проведем в данном случае аналогию с точками на плоскости. Так, например, можно двигаться “по спирали”, пересчитывая тем самым все точки на этой плоскости.
   Во избежание путаницы, важно отметить, что в рамках этого способа \((-3,-1)\ne(-6,-2)\) , в то время как \(\frac<-3><-1>=\frac<-6><-2>\) .

Отрезок [0,1] равномощен множеству всех бесконечных последовательностей нулей и единиц, то есть является несчетным множеством. Подробнее см. в учебнике Н.К.Верещагина и А.Шень Начала теории множеств.

[0 ; 1] \(\times\) [0 ; 1] — декартов квадрат; он обладает большей мощностью, чем отрезок [0 ; 1], который является несчетным множеством. Заключаем, что [0 ; 1] \(\times\) [0 ; 1] — несчетное множество.

Пусть есть некоторое множество А, состоящее из последовательностей 0 и 1. Рассмотрим такие последовательности и пронумеруем их:
\(1\leftrightarrow <\underline<0>,1,0,1,0,1,0,1. >\in A\)
\(2\leftrightarrow<0,\underline<0>,0,1,0,0,0,1. >\in A\)
…
Во множестве А содержится бесконечное количество элементов — последовательностей из 0 и 1.

1.3 Доказательство от принцессы

Утверждение: А — несчетно.
Доказательство от принцессы: Тому, кто приведет взаимнооднозначное соответствие между множеством А и множеством натуральных чисел \(\mathbb\) , полагается сердце и полцарства в придачу!
Пусть пришел индийский принц. Принц развернул длинный список, и она видит, что он пронумеровал бесконечно много последовательностей из нулей и единиц. Что будет делать принцесса? Предположим, что в его списке, помимо отмеченных нами последовательностей №1 и №2, присутствуют и такие последовательности:
\(3\leftrightarrow <1,1,\underline<1>,1,1,1,1,1. >\in A\)
\(4\leftrightarrow<0,0,0,\underline<0>,0,0,0,0. >\in A\) .
Чтобы принцу ничего не досталось, принцесса меняет значение i-го элемента i-го списка на противоположное (0 на 1 и 1 на 0 соответственно). Это можно сделать в каждой последовательности, тогда
…
\(101\leftrightarrow<. \underline<1>>\in A\)
…
И такая измененная последовательность не может быть у него ни под каким номером.
Пусть пришел и арабский принц. Принцесса проводит аналогичную операцию по замене значения i-го элемента i-го списка на противоположное:
\(1\leftrightarrow <\underline<1>,1,1,1,1,1,1,1,1,1. >\in A\)
\(2\leftrightarrow<1,\underline<0>,1,0,0,1,0,0,0,1. >\in A\)
\(3\leftrightarrow<. \underline< >. >\in A\)
Аналогичный результат и со списком второго принца. Таким образом, мы можем сделать вывод, что такого взаимнооднозначного соответствия не существует, и принцесса может отказать любому принцу! Отсюда следует, что множество А не равномощно множеству \(\mathbb\) .
Пояснение: A > \(\mathbb\) :
\(1\leftrightarrow<100000. >\in A\)
\(2\leftrightarrow<010000. >\in A\)
\(3\leftrightarrow<001000. >\in A\)
\(4\leftrightarrow<000100. >\in A\)
…