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

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] имеет мощность континуума.

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

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

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

Научный форум dxdy

В интернете говорят, что множества счетны если их можно «пронумеровать».Каким же образом?
По определению множество счетно, если и сколько их?Можете дать совет как находить такие «правила» для доказательства равномощности множеств.Объясняйте ,пожалуйста, не сложным языком, я пока только знакомлюсь с мат. анализом.

Последний раз редактировалось Anton_Peplov 16.02.2016, 22:37, всего редактировалось 1 раз.

Последний раз редактировалось Rusit8800 16.02.2016, 22:49, всего редактировалось 1 раз.

Видимо, Вы хотите сказать: их элементы можно «пронумеровать» (не сами множества).
Для этого, по сути, достаточно найти перечисление элементов множества, гарантированно «выдающее» все элементы (желательно без повторений, но это требование не принципиально). И если существует хоть одно такое перечисление, то можно найти и бесконечно много других.
Например, множество целых чисел можно выписать в следующем порядке:

Представьте себе, чтоб под каждым элементом этой последовательности мы записали его номер:

Тем самым будет построено биективное (взаимно-однозначное) отображение множества целых чисел на множество натуральных чисел, то есть, будет доказана счётность множества целых чисел.
Но общего рецепта для построения подобных отображений нет. Например, счётность множества рациональных чисел доказывается чуть более сложно.
Да, и конечно же, если Вам удастся построить в аналитическом виде (в виде формулы) функцию, которая вычисляет каждый элемент счётного множества по его номеру, это также служит доказательством счётности множества.
Например, для последовательности целых чисел, записанных так, как я указал выше, такую функцию построить несложно.

Последний раз редактировалось Anton_Peplov 16.02.2016, 23:16, всего редактировалось 3 раз(а).

Есть также полезная теорема, что подмножество счетного множества либо конечно, либо счетно. С помощью этой теоремы можно, например, сразу сказать, что множество всех натуральных чисел, делящихся на три, счетно. Впрочем, и указать правило для их нумерации тоже легко:
3 — первое число
6 — второе число
9 — третье число
.

Есть не менее полезная теорема: если взять конечную или счетную систему множеств , , . и все эти множества объединить, то результат объединения будет снова счетным множеством. С помощью этой теоремы можно, сразу сказать, что множество всех целых чисел счетно. Впрочем, и указать правило для их нумерации, опять же, легко:
0 — первое число
1 — второе число
-1 — третье число
2 — четвертое число
-2 — пятое число.
Можно придумать и другое правило нумерации. Главное, чтобы каждое число за конечное число шагов получило номер. Пытаться перенумеровать сначала все положительные числа, а потом все отрицательные, бессмысленно: ведь положительные никогда не закончатся. Как и в первом примере — с алфавитом — не получится перенумеровать сначала все слова, начинающиеся на «а», потом все слова, начинающиеся на «б» и т.д.

Последний раз редактировалось Rusit8800 16.02.2016, 23:02, всего редактировалось 1 раз.

Последний раз редактировалось Rusit8800 16.02.2016, 23:05, всего редактировалось 2 раз(а).

Ок, следующий вопрос.На mathprofi доказывают счетность рациональности так, что в дроби и принадлежат счетным множествам.
и — это только элементы счетных множеств, как можно говорить о счетности элементов?

Последний раз редактировалось Karan 17.02.2016, 18:52, всего редактировалось 2 раз(а).

Что такое счётное множество?

Множеств в математике… великое множество. 🙂 Вот ведь сказанул! Да простит меня русский язык, но иначе и не скажешь. 🙂 Самых-самых разнообразных. 🙂 Бывают числовые множества. Это, как и намекает название, множества, элементами которых являются числа. Бывают множества функций. Например, любой неопределённый интеграл ∫ f(x)dx — это множество функций вида F(x)+C, где С — любая константа. Но не просто функций, а таких, что F’(x) = f(x). Или множество всех слов, составленных из определённого набора букв. Да много чего можно насочинять. 🙂 Мы пока в данной теме для простоты ограничимся числовыми множествами. С ними как-то попроще в математике работать, чем с остальными видами множеств, правда?

Среди всех множеств (в том числе и числовых) бывают конечные и бесконечные.

С конечными множествами всё просто. Это, как и намекает название, множества с конечным числом элементов. Во множестве может содержаться один элемент, может быть 345 элементов, хоть миллиард. Но — конечное число. Пусть даже очень большое.

Например, если A — множество корней квадратного уравнения x 2 — 3x + 2 = 0, то оно является конечным и состоит всего из двух элементов — чисел 1 и 2:

Или множество всех бактерий на планете Земля. Очень большое, но — тоже конечное.)

Примеры бесконечных множеств вам тоже хорошо знакомы ещё со школы.

N — множество всех натуральных чисел,

Z – множество всех целых чисел,

Q — множество всех рациональных чисел,

R — множество всех действительных чисел.

А теперь приведу более хитрые примеры бесконечных множеств:

— множество всех точек отрезка [0; 1];

— множество всех точек окружности радиуса «R«;

— множество всех точек квадрата со стороной «a«.

На первый (обывательский) взгляд может показаться, что эти три множества вполне себе конечны. И на то есть веские основания. В самом деле, ведь отрезок [0; 1] имеет вполне определённую длину и, по идее, должен «вмещать» в себя лишь некоторое конечное число точек! Окружность и квадрат тоже как-то ограничены по длине/площади и вмещают в себя лишь какое-то конечное число точек!

Но не всё так просто и очевидно, как кажется на первый наивный взгляд. К сожалению… Во всяком случае, для гуманитариев. А вот юные математики, возможно, уже сейчас смогли нутром прочувствовать, почему эти три множества бесконечны. Прочувствовали? Пока нет? Подробности — чуть позже. В соответствующем уроке.

Ну а коли уж мы затронули такое скользкое понятие, как бесконечность, то неплохо было бы о ней немного побеседовать. Пофилософствовать…

Немного о бесконечности…

Бесконечность во все времена привлекала внимание людей. И математиков — особенно.) Термином «бесконечность» мы обычно называем всё, что невозможно сосчитать или перечислить. Бесконечность в нашем воображении — это что-то запредельное, невообразимо большое. Или напротив, чрезвычайно маленькое, к чему можно стремиться сколь угодно долго, но достичь которого невозможно. Вроде бы всё просто, но… Сможете привести мне пример реально бесконечного объекта?

Первое, что приходит большинству на ум, — это наша Вселенная, состоящая из бесчисленного количества звёзд, планет, молекул, атомов и других частиц. Но на самом деле никто из нас не знает, какая именно наша Вселенная на самом деле — конечная она или бесконечная. Никто из нас не видел её границ. Человеку свойственно не видеть часть того, что происходит, да… И не только человеку. Например, какому-нибудь муравью его муравейник будет казаться примерно тем же самым, что и для нас, скажем, жилой дом. А наша планета в целом для муравья будет казаться такой же бесконечной, как и Вселенная для нас. Муравьи в космос ещё не летали, да.)

Но что такое муравейник, жилой дом и даже вся планета Земля не для муравья, а для нас с вами? В нашем мироощущении и в нашей системе координат? Песчинки! Ну… почти.) Зато для нас, скажем, число 2 100 настолько огромно, что простой перебор всех натуральных чисел, его не превосходящих, даже при помощи самого современного супермощного компьютера, потребует невообразимо много сроков жизни самого компьютера… Тем не менее, эти объекты (муравейник, жилой дом, планета Земля и даже число 2 100 ) — конечны. Это значит, что процесс их «пересчёта» (песчинок в муравейнике, кирпичей в жилом доме и всех натуральных чисел от 1 до 2 100 ) когда-нибудь да закончится. Рано или поздно…

А вот, скажем, множество всех целых чисел — бесконечно! Именно реально бесконечно. Какое бы целое число мы ни взяли, всегда можно перейти к следующему, прибавив к предыдущему единичку. Таким образом, мы никогда не сможем сказать: «Вот! Все целые числа перечислены, и других целых чисел больше нет!»

Как сравнивать бесконечности? Что такое взаимно-однозначное соответствие?

С конечными множествами мы с вами худо-бедно работать умеем — изображать на картинках, объединять, пересекать и т.д. Также их легко сравнивать друг с другом — в каком-то множестве больше элементов, в каком-то — меньше. Пересчитали элементы каждого, сравнили два числа и — дело в шляпе.

А вот как грамотно работать с бесконечными множествами? И, в первую очередь, как правильно сравнивать бесконечные множества? В каком из двух бесконечных множеств больше элементов? И что подразумевается под этим самым «больше»? Пока для нас с вами это всё тайна, покрытая мраком…

Ответы на эти животрепещущие вопросы долгое время искал немецкий математик Георг Кантор (1845 — 1918). Вообще, Германия всегда славилась талантливыми учёными-математиками, чего греха таить! Кто не знает знаменитых Гаусса или Кеплера! А студенты физико-математических специальностей содрогаются от страха, услышав фамилии Вейерштрасс или Риман.) Да и Франция тоже не отставала: Паскаль, Лаплас, Коши, Лагранж, Лежандр, Фурье, Лебег, Лиувилль — все эти фамилии хоть раз были на слуху у любого человека, когда-либо всерьёз занимавшегося математикой.)

Но мы с вами обратимся к Кантору.) Его по праву считают основоположником теории множеств. И не зря! Ведь именно он перевёл часть наших знаний о бесконечности из ощущений в строгую математику!

Прежде всего, он придумал красивый и элегантный способ сравнения бесконечных множеств. Основывается этот интересный способ сравнения множеств на так называемом взаимно-однозначном соответствии. Или взаимно-однозначном отображении. Которое в высшей математике называется красивым словом «биекция». Но мы сейчас не будем изображать из себя «true-математегов», умничать, давать строгие определения и заниматься всякой клинописью типа

Этого добра хватает в любом учебнике по высшей математике. Не для этого разрабатывался этот сайт…

В чём же фокус? Как можно объяснить термин «взаимно-однозначное соответствие» на пальцах? Представим себе ситуацию, что в бесконечных размеров аудиторию входит бесконечное число студентов. Представили?) Всех студентов надо как-то рассадить на стулья. Которых, естественно, тоже будет бесконечное количество.)

А теперь возьмём два множества. Множество студентов назовём «А», а множество стульев в аудитории — «В».

Итак. Что же такое взаимно-однозначное соответствие?

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

Так вот, при взаимно-однозначном соответствии между множеством студентов (А) и множеством стульев (В) каждый студент сядет на некоторый свой персональный стул! Причём только на один! Более того, в аудитории (да-да, бесконечной!) не останется ни пустующих стульев, ни стоящих студентов. И никому не будет обидно: вся наша бесконечная орава студентов дружно будет сидеть на стульях и слушать увлекательную лекцию про теорию множеств.)

А теперь нарисуем наших студентов и аудиторию со стульями на картинке.

Так вот, математически термин взаимно-однозначное соответствие означает, что каждому элементу из первого множества «А» можно поставить в соответствие один и только один элемент из второго множества «В».

И наоборот, любому элементу множества «B» будет соответствовать некоторый единственный элемент из множества «А». И всё!

На нашей картинке каждый элемент из первого множества (студентов) связан с элементом второго (стульев) только одной стрелочкой. Причём очень важно, что ни в одном из множеств нету элемента без пары! К каждому элементу ведёт своя стрелочка. И притом только одна. А не две или ни одной. И именно эти самые стрелочки и показывают нам, что каждый студент сидит на своём стульчике. И наоборот, у каждого стульчика есть свой персональный хозяин.) Это важно!

Идём дальше. Наш уважаемый Кантор настолько увлёкся идеей взаимно-однозначного соответствия между различными множествами, что начал получать просто потрясные и совершенно неожиданные результаты! И тем самым развеял очень многие мифы, в которые до него исправно верило всё человечество, ссылаясь на пресловутую интуицию… Результаты настолько неожиданные, что у студентов-новичков на данном этапе знакомства с теорией множеств даже теряется вообще доверие к математике. Как вообще такое возможно? Неужели это и вправду не сон?!

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

Миф №1: Чётных чисел вдвое меньше, чем натуральных .

Факт: И тех и других одинаковое количество! Более того, натуральных чисел, кратных трём (пяти, десяти, да хоть миллиарду!), столько же, сколько и самих натуральных чисел.

Миф №2: Рациональных чисел гораздо больше, чем натуральных.

Факт: Ничего подобного! Их тоже одинаковое количество! Пускай и бесконечное…

Дальше — больше! Держитесь покрепче и не упадите! Вот вам ещё эпичные факты:

Точек на окружности радиуса 1 столько же , сколько и на окружности радиуса 5. Или радиуса 100. Или любого другого радиуса.

Точек на отрезке [0; 1] ровно столько же , сколько и точек на всей числовой прямой (-∞; +∞).

Точек в квадрате со стороной 1 столько же , сколько и на отрезке [0; 1] (и, соответственно, на всей прямой).

Что, неожиданно? Парадокс? Не вяжется с житейской логикой? Поначалу — да. Разгадка этих парадоксов кроется в том, что именно мы хотим подразумевать под понятием «столько же» для бесконечного множества. Кантор дал строгое определение этому понятию.

Бесконечное множество «А» (любое!) содержит СТОЛЬКО ЖЕ элементов, сколько и другое бесконечное множество «В», если между элементами этих множеств можно установить взаимно-однозначное соответствие!

Вот и всё.) И именно поэтому я начал наш урок с объяснения, что же такое взаимно-однозначное соответствие. Понятна эта фраза? Если непонятна, вернитесь чуток назад и снова перечитайте про студентов, сидящих на стульях в бесконечной аудитории.)

Ну что, вот мы плавненько подошли к основной теме нашего урока — понятию счётного множества. Оказывается, среди всего многообразия бесконечных множеств в математике выделяется особый класс множеств — счётные множества. Это очень-очень важное понятие в теории бесконечных множеств. Начнём разбираться. И параллельно доказывать эти, казалось бы, противоестественные в нашем восприятии факты.)

Что же такое счётное множество?

Так что же такое счётное множество? Слово «счётное», очевидно, однокоренное со словами «счёт», «считать». Значит, что-то в таком множестве мы должны считать. ) А считать мы будем его элементы. 🙂

Так вот, говоря по-русски, счётное множество — это такое множество, все элементы которого можно перенумеровать. Или пересчитать. По порядочку. Как цыплят. Ну, не совсем буквально, конечно. 🙂

Если наше рассматриваемое множество конечное (даже если оно очень большое), то вопросов нет: каждому его элементу можно так или иначе присвоить какой-то порядковый номер: какой-то элемент будет первым, какой-то вторым, какой-то сорок пятым и так далее. Пока все элементы не пересчитаем. 🙂

А что делать если множество бесконечно? Разве можно в этом случае взять и пересчитать все-все его элементы? Ведь так и будем считать до посинения…

Оказывается, для некоторых бесконечных множеств пересчитать все их элементы тоже можно! 🙂 Да-да! Как именно? Очень интересно! Нет, конечно же, мы не будем сидеть и кропотливо пересчитывать каждый элемент, как мы это обычно делаем для множеств конечных. Никакой даже самой длинной жизни не хватит. Так как же тогда можно пересчитать ВСЕ элементы БЕСКОНЕЧНОГО множества? Причём быстро! И ни один элемент не забыть!

А вот как. Нужно всего лишь установить правило (или закон), согласно которому каждому элементу данного бесконечного множества можно присвоить (то есть, поставить в соответствие) некоторый порядковый номер «n«.

Зачем нам понадобилось создавать какое-то правило? Представим себе, что мы — компьютерщики, и нам надо проделать одну и ту же операцию тысячи, миллионы и миллиарды раз. Что мы в таком случае сделаем? Правильно! Попробуем составить программу или алгоритм, автоматизирующую сей рутинный процесс! В нашем случае наша задача — пересчитать все элементы множества. Вот и пробуем составить нужный нам алгоритм (т.е. правило) который и автоматизирует нам весь увлекательный процесс пересчёта! Правда, в отличие от компьютерной программы, наш алгоритм будет работать бесконечно. Ибо пересчитываемых элементов бесконечное количество, да…

Бесконечное множество (любое!) является счётным, если можно установить взаимно-однозначное соответствие между каждым его элементом и всеми числами натурального ряда.

Вникли? Под умными словами «установить взаимно-однозначное соответствие между каждым его элементом и всеми числами натурального ряда» как раз и скрывается безобидный глагол «пересчитать». И всё. Никаких хитростей.) Представьте себе, что большая группа туристов собирается в интересный и насыщенный поход по Карелии. Руководитель-гуманитарий скажет: «Народ! Давайте-ка я вас пересчитаю!» А вот руководитель-математик может выпендриться и заявить: «Народ! Замрите! Мне надо установить взаимно-однозначное соответствие между нашей командой и числами натурального ряда!»))).

Так вот, если такое взаимно-однозначное соответствие между элементами множества и натуральными числами (т.е. способ пересчёта) установить можно, то в таких случаях математики говорят, что наше множество счётно. Причём совершенно не важно, как именно мы с вами это самое соответствие (или правило) установили. Хоть формулой, хоть табличкой, хоть картинкой, хоть словами… Главное — установили.)

А вот если нам удалось доказать, что такое соответствие (правило) установить нельзя, то в таком случае математики обычно говорят, что такое множество несчётно. 🙂

Вот так вот. Почувствуйте разницу! Ключевыми словами здесь являются слова «удалось доказать». Они означают, что, если мы с вами как-то докажем, что нужное нам взаимно-однозначное соответствие установить нельзя, то из этого автоматом будет следовать, что рассматриваемое нами множество несчётно.

Но! Если мы с вами, по каким-то причинам, никакого соответствия так и не установили, но при этом ещё и не доказали, что такое соответствие установить невозможно, то из этого факта не будет следовать ни того, ни другого! Ни счётности множества, ни его несчётности. Что правда, то правда. Мало ли? Может, мы с вами какие-то тупые двоечники и просто не смогли поднапрячься и придумать нужное правило, по которому можно было бы осуществить это соответствие?! А, скажем, дядя Вася из деревни Кукуево посидел на лавочке с бутылкой самогона часок-другой — и… эврика! Правило найдено!)

А говоря ещё более строго, научно и кратко, счётное множество – это множество, эквивалентное (или равномощное) множеству натуральных чисел N.

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

Посмотрим на счётное множество в жизни?

Например, давайте докажем, что множество всех положительных чётных чисел является счётным. Как это сделать? Очень просто. 🙂 Выпишем в ряд первые несколько таких чисел:

Любой ээээ… короче, любой сообразит, что первым таким числом будет двойка, вторым — четвёрка, третьим — шестёрка. И так далее.) Десятым номером пойдёт 20, сотым — 200. И так до бесконечности: каждое чётное число когда-нибудь получит свой заветный номер. А именно — вдвое меньший, чем само это число. 🙂 Вот мы и установили взаимно-однозначное соответствие между чётными числами и их номерами (т.е. ничем иным, как множеством натуральных чисел N!). Незаметно для себя. 🙂

Пожалуйста! Вот оно, это соответствие:

Вот вам и разгадка неожиданности №1, почему же чётных чисел ровно СТОЛЬКО ЖЕ, сколько и натуральных чисел. Хотя, казалось бы, чётных чисел должно быть вдвое меньше! Ибо чётные числа составляют лишь часть натуральных… Ан нет! Убедились?) Посмотрите ещё раз на картинку и представьте себе, что чётные числа — это студенты, а их номера — это стулья в аудитории. Пронумерованные, как в театре.) И всё станет понятно. Такие фокусы, противоречащие житейской логике, — яркий пример того, как интуиция и личные ощущения могут сыграть злую шутку при построении правильных и строгих математических умозаключений. Оказывается, чётных чисел СТОЛЬКО ЖЕ, сколько и натуральных! И мы это только что строго доказали! Миф №1 развеян.)

Сюрприз здесь состоит в том, что на бесконечности далеко не всегда работает наш незыблемый постулат, гласящий, что часть меньше целого. И это ещё далеко не все сюрпризы, которые готовит нам теория множеств и работа с бесконечными объектами!) На бесконечности — уже совершенно другая математика… И зачастую идущая вразрез с нашей интуицией, да.)

Какие ещё можно привести примеры счётных множеств? Например, множество элементов любой арифметической или геометрической прогрессии (да и вообще любой числовой последовательности) всегда является счётным. Почему? Да потому, что сама конструкция числовой последовательности подразумевает нумерацию её элементов (т.е. членов)! Есть первый член, есть 37-й, есть 345-й и так далее. 🙂 Все элементы последовательности занумерованы и каждый — на своём месте. 🙂

Счётность множества всех целых чисел Z

А теперь давайте посмотрим, счётно ли множество всех целых чисел Z. Снова, как и чётные числа, попробуем их занумеровать по порядочку. Начнём наш пересчёт с нуля. Число 0 у нас получает почётный номер 1. А вот дальше возникает резонный вопрос — как нам быть с противоположными целыми числами? По какому принципу их нумеровать? Легко! Противоположные числа мы будем выписывать парами — положительное и отрицательное. 🙂 Вот так:

Таким образом, каждое целое число мы рано или поздно выпишем и ни одно не забудем. 🙂

А дальше всё просто — берём и начинаем нумеровать все наши выписанные целые числа по парам! По порядочку. Нолик будет под номером 1, единичка — под номером 2, минус единичка — под номером 3. И так далее. Все положительные числа нумеруем чётными номерами, а все отрицательные — нечётными.

Установили взаимно-однозначное соответствие между целыми числами и натуральным рядом? Конечно! 🙂

Как мы видим, любое целое число когда-нибудь получит номер. Свой персональный. Когда конкретно это самое «когда-нибудь» наступит, зависит от самого числа. И чётко видно из нашего правила. Положительное число (n) получит номер «2n». А противоположное ему отрицательное число (-n) в нашем списке автоматически будет под следующим номером «2n+1». Неизбежно. Например, число 100 получит номер 200. А число, скажем, -234 окажется под номером 469. И так далее. Каждое целое число будет на своём месте. Под своим номером. И ни одно из них не сможет «откосить» от армии процедуры быть пронумерованным. До каждого дойдёт очередь.

Кстати, и наоборот — любой номер обязательно будет «зарегистрирован» за каким-то конкретным целым числом, ему соответствующим. Скажем, под номером 1537 будет скрываться число -768. И только оно! У каждого номера — свой личный «владелец» в виде целого числа. Как у автомобиля, да. И ни один номерок не останется без хозяина. Все номера будут использованы. Все-все, прямо до бесконечности!) Взаимно-однозначное соответствие — штука жёсткая. Улавливаете?)

Итак, всё доказано! Множество Z — счётно. Вне всяких сомнений. 🙂

Переходим теперь к множеству рациональных чисел Q. То есть, множеству всех несократимых дробей вида m/n, где m — целое число, а n — натуральное.

Счётность множества всех рациональных чисел Q.

С рациональными числами вопрос похитрее будет. Тут есть одна проблемка. Проблемка состоит в том, что между любыми двумя соседними целыми числами находится бесконечно много рациональных чисел. Например, между 0 и 1 находятся дроби 1/2, 1/3, 1/4, 1/5, … И интуиция нам снова вполне справедливо подсказывает, что рациональных чисел больше, чем целых (а значит, и натуральных). Однако, как показал наш гениальный Кантор ещё в 1874 году, рациональных чисел тоже столько же, сколько и натуральных! Да-да, как это ни странно!

Как же тогда нам перенумеровать все-все рациональные числа? Понятное дело, что в связи с вышеописанной проблемкой выстроить все рациональные числа в один ряд уже несколько затруднительно, да… Мы поступим по-другому. 🙂 Как? Очень нетривиально! Мы составим волшебную табличку. Бесконечную в длину и в высоту…

В верхнем левом углу притаилось рациональное число 0/1. Или просто ноль. Он стоит отдельно чисто для нашего удобства, не более того.

Что будем делать дальше? А вот дальше мы будем заполнять нашу табличку рациональными числами по такому простому принципу: в первый столбец пойдут все дроби со знаменателем 1 (т.е. не что иное, как все целые числа), во второй столбец — все дроби со знаменателем 2, в третий — со знаменателем 3. И так далее… Таким образом, наша табличка станет неограниченно простирающейся вниз и вправо: числители вписываемых дробей будут меняться по вертикали, а знаменатели — по горизонтали. Кроме того, опять же для удобства и компактности, в каждую ячейку я буду вписывать сразу по два рациональных числа. С плюсом и с минусом. Всё просто.)

Кстати, вы обратили внимание, что некоторые ячейки я покрасил в другой цвет (жёлтый), а находящиеся в них дроби выделил красным шрифтом? Не догадались, зачем? Да! В жёлтых ячейках находятся сократимые дроби. Эти дроби нас не интересуют и в нашей нумерации участвовать никак не будут.

Что делаем дальше? А дальше нумеруем наши выписанные числа вот такой интересной змейкой:

Поясняю. Змейка «стартует» из нуля и всё время ползает строго по диагоналям ячеек, постепенно смещаясь вправо-вниз. И… тщательно нумерует ВСЕ наши рациональные числа! Да-да, все без исключения! Ноль (т.е. дробь 0/1) при этом получает номер 1, номера 2 и 3 достаются дробям 1/1 и -1/1, следующие номера 4 и 5 — дробям ±1/2 и так далее. При этом сократимые дроби (в жёлтых ячейках) на нашу змейку не действуют: перескакивает она через них. Поэтому, например, после дробей ±3/1 (номера 8, 9) следующей пронумерованной парочкой (10, 11) становится ±1/3. А вот парочка ±2/2 сократима и посему остаётся непронумерованной. Ибо ±2/2 это то же самое, что и ±1/1, а эта парочка нашей змейкой уже пронумерована. Так что всё справедливо.)

Итак, всё доказано! Множество Q — счётно. 🙂 А этот факт и означает, что рациональных чисел столько же, сколько и натуральных! Миф №2 развеян.)

Заметьте снова, что нам здесь совершенно не важно, КАК мы установили наше правило нумерации! Важен только сам факт установления этого правила! Здесь мы составили табличку, запустили на неё змейку-«счётчика» и всё пронумеровали, ничего не забыв. А могли бы, например, придумать способ выстроить все рациональные числа в ряд и начать нумерацию членов ряда. И, кстати, такой способ тоже есть! Но он менее наглядный. Способов может быть много. Но факт — налицо. Все рациональные числа пронумерованы.)

А теперь предлагаю немного поразмышлять самостоятельно.

Доказать счётность множества всех точек координатной плоскости с целыми координатами.

Что такое точки с целыми координатами — представляете (надеюсь). Например, точка А (0; 0), точка B (-2; 5), точка C(123; -456). И так далее… В общем, вы поняли.) Счётно ли множество таких точек? Рисуйте, думайте… И змейка вам в помощь! Только ползать она будет немного по-другому (это подсказка!).

Так, ну хорошо. Множества целых и рациональных чисел — счётны. А что же насчёт множества действительных чисел R? А вот оно уже несчётно. Увы… То есть, перенумеровать все действительные числа у нас уже не получится. Принципиально не получится. Их, действительных чисел, настолько много, что натуральных чисел (а нумеруем мы, заметьте, только такими!) нам просто не хватит. Более того, несчётно даже множество всех десятичных дробей из отрезка [0; 1]! И скоро мы это докажем. Тоже весьма красиво, между прочим. И разберёмся с тем, что же всё-таки такое мощность множества. В следующем уроке.)

Счетность и несчетность множеств. Равномощность множеств.

Литература: Сборник задач по математике. Часть 1. Под ред А. В. Ефимова, Б. П. Демидовича.

Множество $X$ называется счетным, если может быть установлено взаимно однозначное соответствие между элементами этого множества и элементами множества $N$ всех натуральных чисел (то есть элементы множества $X$ можно пронумеровать 1, 2, . ).

Примеры.

Доказать, что следующие множества счетны:

Решение.

Установим взаимно однозначное соответствие между элементами этого множества и натуральными числами, например, упорядочив множество $\$ следующим образом:

$$2, 4, 6, 8, . $$ а затем каждому элементу множества поставив в соответствие его порядковый номер в этой последовательности $$1, 2, 3, 4, . .$$ Таким образом заданное множество является счетным.

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

Решение.

Множество $\$ упорядочим следующим образом:

$$2^1, 2^2, 2^3, 2^4, . $$ далее каждому элементу множества поставив в соответствие его порядковый номер в этой последовательности. Таким образом, установлено взаимно однозначное соответствие между заданнім множеством и множеством натуральніх чисел. Следовательно, множество $$\$$ является счетным.

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

1.68. Пусть $X_1, X_2, X_3, . -$ счетные множества. Доказать, что их объеденение $\bigcup\limits_ X_n-$ счетное множество.

Решение.

Пусть $X_n=\, x_, . x_. \>.$ Тогда элементы множества $\bigcup\limits_ X_n$ можно записать в виде следующей таблицы:

Занумеруем элементы этой таблицы следующим образом: в качестве первого элемента берем элемент $x_<1, 1>,$ следующие два элемента — элементы стоящие на диагонали $x_<1, 2>$ и $x_<2, 1>,$ затем считаем три элемента стоящие на следующей диагонали $x_<3, 1>,\,\, x_<2, 2>$ и $x_<1, 3>$ и так далее. Таким образом, каждому элементу множества $\bigcup\limits_ X_n$ можно поставить в соответствие натуральное число (порядковый номер элемента, если их пересчитывать по указанной выше схеме). Следовательно, заданное множество счетное.

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

1.69.Используя результат задачи 1.68 доказать, что множество всех рациональных чисел $Q=\,\,\, n\neq 0,\,\, m,\, n \in Z \>.$

Решение.

Множество рациональных чисел можно представить как объединение счетных множеств $X_n=\<\frac\, | k\in N \>=\left\<\frac<1>,\frac<2>, \frac<3>, \cdots\right\>.$

Каждое множество $X_n$ счетное, поскольку каждому элементу можно поставить в соответствие натуральное число, стоящее в знаменателе. Тогда множество $$Q=\,\,\, n\neq 0,\,\, m,\, n \in Z \>=\bigcup\limits_ X_n$$ так же является счетным, как было доказано в задаче 1.68.

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

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

Примеры:

1. Докажите, что отрезки $[0, 1]$ и $[0, 2]$ равномощны.

Доказательство.

Каждому элементу $x\in [0, 1]$ поставим в соответствие число $2x.$ Очевидно $2x\in [0, 2].$ Аналонгично каждому элементу $y\in[0, 2]$ соответствует, и притом единственное, число $\frac<2>\in\,[0, 1].$

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

2. Докажите, что интервалы $(a, b)$ и $(c, d)$ равномощны.

Доказательство.

Проведем доказательство в несколько этапов:

1) Заметим, что отображение $x\rightarrow x-a$ является взаимно однозначным соответствием между интервалами $(a, \, b)$ и $(0,\, b-a).$

2) Отображение $x\rightarrow\frac<(d-c)x>$ взаимно однозначно отображает интервал $(0, b-a)$ на $(0, \, d-c).$

3) Отображение $x\rightarrow x+c$ взаимно однозначно отображает интервал $(0, d-c)$ на $(c, d).$

Композиция приведенных отображений $x\rightarrow\frac<(d-c)(x-a)>+c$ является взаимно однозначным отображением между интервалами $(a,\, b)$ и $(c,\, d).$ Следовательно интервалы $(a,\, b)$ и $(c,\, d)$ равномощны.

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

Домашнее задание.

Доказать, что следующие множества счетны:

1.67. Доказать, что если множество $X$ счетно и $A\subset X$ его бесконечное подмонжество, то множество $A$ так же счето используя этот результат доказать, что множество $$n\in Z | n=k^2-k+1, k\in N$$ счетно.

1.70. Используя результат задачи 1.68, доказать, что множество всех точек плскости с рациональными координатами счетно.

1. Докажите, что полуинтервал $[0,\, 1)$ равномощен полуинтервалу $(0,\, 1].$

2. Докажите, что интервал $(0, 1)$ и луч $(0, \, +\infty)$ равномощны.