Как доказать что множество счетно 8 класс

Математический портал

Nav view search

Navigation

Search

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

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

Примеры.

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

Решение.

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

Решение.

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

Решение.

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

Решение.

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

Примеры:

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

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

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

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

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

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

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

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

Источник

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

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

Например, множество целых чисел счетно, так как целые числа можно расположить в последовательность , , , , , , ,

(а) Подмножество счетного множества конечно или счетно.

(в) Объединение конечного или счетного числа конечных или счетных множеств конечно или счетно.

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

(в) Пусть имеется счетное число счетных множеств Расположив элементы каждого из них слева направо в последовательность ( ) и поместив эти последовательности друг под другом, получим таблицу

Замечание. В доказательстве утверждения (б) теоремы 2 есть тонкий момент: на каждом шаге мы должны выбрать один из оставшихся элементов множества ; такие элементы есть, но у нас нет никакого правила, позволяющего такой выбор описать. При более формальном построении теории множеств тут нужно сослаться на специальную аксиому, называемую аксиомой выбора. Законность этой аксиомы вызывала большие споры в начале 20-го века, но постепенно к ней привыкли, и эти споры сейчас почти не воспринимаются. В середине века великий логик Курт Гедель доказал, что аксиому выбора нельзя опровергнуть, пользуясь остальными аксиомами теории множеств, а в 1960-е годы американский математик Пол Дж.Коэн доказал, что ее нельзя и вывести из остальных аксиом. (Конечно, понимание этих утверждений требует подробного изложения теории множеств как аксиоматической теории.)

30. Такой же тонкий момент (хотя и менее очевидный) есть и в доказательстве утверждения (в). Можете ли вы догадаться, где он? (Ответ: мы знаем, что множества счетны, то есть что существует взаимно однозначное соответствие между и . Но нужно выбрать и фиксировать эти соответствия, прежде чем удастся построить соответствие между объединением всех и .)

Еще несколько примеров счетных множеств:

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

33. Докажите, что множество точек строгого локального максимума любой функции действительного аргумента конечно или счетно.

Докажите, что множество точек разрыва неубывающей функции Действительного аргумента конечно или счетно.

Источник

Разнообразие бесконечностей

Бесконечные множества содержат неограниченную последовательность элементов, объединенных общим признаком. Самые часто используемые из них в математике:

Все они бесконечны, вовсе не означает, что они равномощны.

Сравнение и отображение

Числа в математике можно сравнивать друг с другом и выяснять, какое из них больше. С множествами можно производить аналогичные действия. Это будет называться их отображение друг в друга. Оно может быть дизъюнктивно, конъюнктивно и биективно. Это аналог числовых понятий «больше», «меньше» и «равно». Для того чтобы разобраться, как происходит это сравнение, нужно понятие подмножества.

Подмножеством некоторого набора компонентов называется любая часть компонентов этого набора. То есть, совокупность состоящее из чисел 1 и 3 является подмножеством множества чисел 1, 3 и 5. А они оба, в свою очередь, являются подмножествами совокупности нечётных чисел и т. д.

Если каждому компоненту множества A можно сопоставить какой-то элемент подмножества совокупности В, то отображение А в В конъюнктивно или А меньше, чем В. Если при этом нельзя найти в наборе А подмножество, которое можно сопоставить с совокупностью В, то отображение В в А дизъюнктивно. Если же каждому компоненту из комплекса А можно сопоставить элемент из совокупности В и каждому компоненту из набора В можно сопоставить элемент из совокупности А, то эти множества отображаются друг в друге биективно. В таком случае говорят, что они эквивалентны.

Для сравнения совокупностей можно использовать их мощность. Если мощность А меньше мощности В, то и множество А меньше, чем В. Если мощности равны, то сами наборы элементов эквивалентны.

Сопоставление наборов элементов

Казалось бы, используя свойства сравнения наборов элементов, можно найти соотношение мощностей бесконечных совокупностей. Ведь очевидно, что множество N является подмножеством совокупности Z, они оба являются подмножеством Q, а множества Q и I вместе составляют R. И отсюда, по определению, следует, что мощности соотносятся так: |N| |I|, и загадкой остается только соотношение совокупностей Q и I. Но всё не так просто.

Выяснение размера бесконечного комплекса компонентов — такая же задача, как определение размера конечной совокупности — пересчёт компонентов. Возможность посчитать и пронумеровать элементы бесконечной совокупности называется счётностью. Совокупность натуральных чисел — счётная. Элементам в этом случае легко присвоить порядковые номера. И все множества, которые эквивалентны N, тоже будут счётными. Его размер |N| = a.

Но если взять R, то его элементы пронумеровать не получится. Ведь между любыми двумя точками, а прямой всегда можно поставить ещё одну. То есть, совокупность R «бесконечна вглубь»: каждый промежуток между бесконечным количеством точек содержит в себе бесконечное количество точек. Значит, свойство R — несчётность. Такие «бесконечные вглубь» множества называют континуальными. И их мощность обозначается как |R| = c.

Ещё одно важное свойство бесконечных множеств заключается в том, что если из бесконечной совокупности удалить (или добавить к ней) подмножество меньшей мощности, то размер исходной совокупности сохранится. Если из N убрать все числа от 1 до 10, то его мощность не уменьшится на 10, а останется прежней. Множество останется бесконечным и счётным: a — 10 = a.

Бесконечная мощность счётных и несчётных множеств может быть описана тремя формулами. Это два равенства и одно неравенство:

Совокупность всех точек интервала или отрезка на прямой тоже будет континуальна, так как на неё можно спроецировать всю совокупность точек действительной прямой R.

Соотношение мощностей

Континуальное множество больше счётного. Но какова их разница? Чтобы это вычислить, потребуется понятие булеан.

Что такое булеан

Есть некий набор компонентов V. Булеаном V будет называться комплекс всех его подмножеств. Как будут соотноситься размер булеана и самого V? Если V состоит из одного элемента, то его булеан будет состоять из двух элементов: пустого набора компонентов и самого V. Если V состоит из двух элементов, то булеан содержит 4 элемента: пустое множество, V и каждый из двух элементов. Если V содержит 3 элемента, то булеан содержит 8: пустое, само V, каждый из трёх его элементов в отдельности и каждую пару элементов (которых тоже три).

То есть мощность булеана — это 2 в степени размера самого V. Булеан так и записывается 2^|V|. Размер булеана всегда будет больше, чем мощность самой совокупности.

Результат сопоставления

Размер булеана любой счётной совокупности будет 2^a. Если рассматривать N, то его булеан будет состоять из пустоты, бесконечного числа элементов N, бесконечного числа пар элементов, бессчётного числа сочетаний элементов по 3, 4, 5 и так до бесконечности. Какому известному множеству можно сопоставить этот булеан?

Так как это N — натуральные числа, то каждый элемент булеана — это последовательность чисел. Если представить каждую такую последовательность в виде знаков после запятой в десятичной дроби, то получатся координаты точек в интервале от 0 до 1, который эквивалентен R. Так как булеан N содержит бесконечное количество комбинации бесконечных десятичных дробей, то он покрывает все точки в этом интервале. Это нестрогое доказательство уравнения c = 2^a.

Обозначения мощностей а и c происходят от слов account и continum, но именно такая последовательность букв порождает вопрос: а есть ли бесконечное множество мощностью b, которое меньше c, но больше a. Если и есть, то пока они неизвестны. А вот комплекс больший по мощности, чем c, есть. Это булеан континуального множества с мощностью 2^c. А у этого булеана тоже есть булеан с ещё большей мощностью.

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

Источник

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

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

Например, множество целых чисел счетно, так как целые числа можно расположить в последовательность , , , , , , ,

(а) Подмножество счетного множества конечно или счетно.

(в) Объединение конечного или счетного числа конечных или счетных множеств конечно или счетно.

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

(в) Пусть имеется счетное число счетных множеств Расположив элементы каждого из них слева направо в последовательность ( ) и поместив эти последовательности друг под другом, получим таблицу

Замечание. В доказательстве утверждения (б) теоремы 2 есть тонкий момент: на каждом шаге мы должны выбрать один из оставшихся элементов множества ; такие элементы есть, но у нас нет никакого правила, позволяющего такой выбор описать. При более формальном построении теории множеств тут нужно сослаться на специальную аксиому, называемую аксиомой выбора. Законность этой аксиомы вызывала большие споры в начале 20-го века, но постепенно к ней привыкли, и эти споры сейчас почти не воспринимаются. В середине века великий логик Курт Гедель доказал, что аксиому выбора нельзя опровергнуть, пользуясь остальными аксиомами теории множеств, а в 1960-е годы американский математик Пол Дж.Коэн доказал, что ее нельзя и вывести из остальных аксиом. (Конечно, понимание этих утверждений требует подробного изложения теории множеств как аксиоматической теории.)

30. Такой же тонкий момент (хотя и менее очевидный) есть и в доказательстве утверждения (в). Можете ли вы догадаться, где он? (Ответ: мы знаем, что множества счетны, то есть что существует взаимно однозначное соответствие между и . Но нужно выбрать и фиксировать эти соответствия, прежде чем удастся построить соответствие между объединением всех и .)

Еще несколько примеров счетных множеств:

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

33. Докажите, что множество точек строгого локального максимума любой функции действительного аргумента конечно или счетно.

Докажите, что множество точек разрыва неубывающей функции Действительного аргумента конечно или счетно.

Источник

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

Множеств в математике… великое множество. 🙂 Вот ведь сказанул! Да простит меня русский язык, но иначе и не скажешь. 🙂 Самых-самых разнообразных. 🙂 Бывают числовые множества. Это, как и намекает название, множества, элементами которых являются числа. Бывают множества функций. Например, любой неопределённый интеграл ∫ 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. Или любого другого радиуса.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник