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

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

В теории множеств счётное мно́жество есть бесконечное множество, элементы которого возможно занумеровать натуральными числами.

Определения [ ]

• Пусть дано множество X . Тогда X называется счётным, если оно равномощно множеству натуральных чисел N >
• Бесконечное множество не являющееся счётным называется несчётным.
• Непустое множество являющееся конечным или счётным называется не более, чем счётным.

Замечание [ ]

Таким образом множество счётно, если его элементы можно занумеровать в виде последовательности неповторяющихся элементов X = < x n >n ∈ N _>> такой, что

∀ i , j ∈ N ( i ≠ j ) ⇔ ( x i ≠ x j ) . \quad \bigl(i \neq j\bigr) \Leftrightarrow \bigl(x_i \neq x_j\bigr).>

Свойства [ ]

• В предположении, что выполнена аксиома выбора, любое бесконечное множество содержит счётное подмножество.
• Непустое подмножество счётного множества не более, чем счётно.
• Не более, чем счётное объединение не более, чем счётных множеств само не более, чем счётно.
• Декартово произведение конечного числа не более, чем счётных множеств само не более, чем счётно.

Примеры [ ]

• Множество целых чисел счётно.
• Множество рациональных чисел счётно.
• Семейство всех подмножеств счётного множества несчётно.
• Множество бесконечных последовательностей из нулей и единиц несчётно.
• Множество вещественных чисел несчётно.

См. также [ ]

Множество целых чисел

Математика – фундаментальная наука, как никогда востребованная в 21 веке. Однако развитие ее началось с создания, а затем усовершенствования навыков практического счета.

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

Целыми числами являются натуриальные числа, отрицательные числа и ноль.

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

Первые упоминания об использовании отрицательных чисел восходят к Древнему Китаю II в. до н.э. На заре своего развития отрицательные числа использовались в качестве арифметического эквивалента долга. Примечательно, что в Древней Греции, где, как известно, зародилась западная философия, основанная на принципах рациональности, отрицательные числа не признавались. Древнегреческий математик Диофант Александрийский уже в III в. н.э. знал «правило знаков» и умножал отрицательные числа для получения положительного конечного результата, однако отбрасывал отрицательные корни уравнений как невозможные.

В Европе отрицательные числа были «официально» признаны спустя тысячу лет и очень долгое время носили обидные прозвища – «абсурдные», «ложные», «мнимые». Ученые продолжали проводить корреляцию между отрицательным числом и понятием «долга» или «недостачи». Сохранились сведения, что даже замечательный математик и философ Блез Паскаль, вычитая из ноля четыре, приходил к решению, равному нолю (потому что «нет ничего меньше, чем само ничто»). «Легализация» отрицательных чисел существенно упростила ряд математических операций: например, стал возможен перенос слагаемых из одной части уравнения в другую, независимо от знака этого слагаемого.

Как мы уже поняли, отрицательные числа долгое время находились в статусе вспомогательного математического «инструмента». Лишь в XIX веке Уильям Гамильтон (ирландский математик) и Герман Грассман (немецкий физик и математик) создали вполне строгую и полную теорию отрицательных чисел.

Давайте зафиксируем самые важные теоретические положения данной темы. Все целые числа образуют множество целых чисел. Множество целых чисел бесконечно. Нельзя назвать наименьшее целое число, равно как нельзя назвать и наибольшее целое число. Наибольшее отрицательное число равняется «-1»; наименьшее положительное целое число равняется «1».

С целыми числами выполняются арифметические операции сложения, вычитания и умножения. Также целое число можно возвести в степень. Существуют ограничения на операцию деления. Целые числа делятся на другие целые числа с остатком. Множество целых чисел счетно и обозначается буквой Z . Теория чисел – раздел математики, изучающий свойства целых чисел. Действительное число считается целым, если не содержит дробной части. Модулем целого числа или абсолютной величиной называется само число с отброшенным знаком.

Дарим в подарок бесплатный вводный урок!

Репетиторы

• Репетитор по математике
• Репетитор по физике
• Репетитор по химии
• Репетитор по русскому языку
• Репетитор по английскому языку
• Репетитор по обществознанию
• Репетитор по истории России
• Репетитор по биологии
• Репетитор по географии
• Репетитор по информатике

Специализация

• Подготовка к ЕГЭ по математике (профильный уровень)
• Репетитор по химии для подготовки к ЕГЭ
• Репетитор для подготовки к ЕГЭ по физике
• Репетитор по русскому языку для подготовки к ОГЭ
• Репетитор для подготовки к сочинению ЕГЭ по русскому
• Репетитор по английскому языку для подготовки к ЕГЭ
• Подготовка к олимпиадам по английскому языку
• Репетитор по разговорному английскому
• ВПР по физике
• Репетитор по информатике для подготовки к ЕГЭ

Предметы по класам

• 1 класс
• 2 класс
• 3 класс
• 4 класс
• 5 класс
• 6 класс
• 7 класс
• 8 класс
• 9 класс
• 10 класс
• 11 класс
• Не школьник

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

Множеств в математике… великое множество. 🙂 Вот ведь сказанул! Да простит меня русский язык, но иначе и не скажешь. 🙂 Самых-самых разнообразных. 🙂 Бывают числовые множества. Это, как и намекает название, множества, элементами которых являются числа. Бывают множества функций. Например, любой неопределённый интеграл ∫ 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. \(\mathbb\) = ;
2. \(\mathbb\) = ;
3. \(\mathbb\) = ;
4. \(\mathbb\) – множество действительных чисел;
5. Точки на плоскости с целыми координатами;
6. [0 ; 1] ;
7. [0 ; 1] \(\times\) [0 ; 1] = ;
8. Множество бесконечных последовательностей из нулей и единиц.

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

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

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

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

plot(c(-5:5), c(-5:5), type = 'n', xlab = "", ylab = "", xaxt = "n", yaxt = "n") axis(1, at = -5:5, labels = -5:5) axis(2, at = -5:5, labels = -5:5) x1 rep(c(0.5, 0), 3) r seq(1:6) / 2 for (i in 1:6) < curve(sqrt((r[i])^2 - (x - x1[i])^2), x1[i] - r[i], x1[i] + r[i], add = TRUE) if (i %% 2 == 1) < arrows(x1[i] + r[i], 0.01, x1[i] + r[i], 0, length = 0.1) > else < arrows(x1[i] - r[i], 0.01, x1[i] - r[i], 0, length = 0.1) > > arrows(-5, 0, 5, 0, col = "blue") arrows(0, -5, 0, 5, col = "blue") abline(h = -5:5, v = -5:5, lty = 3, col = "gray")

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

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

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

1. Из курса высшей алгебры:
   Для доказательства счетности множества предположим противное. Пусть множество \(\mathbb\) состоит из чисел a₁,a₂,…,a_n,…. Рассмотрим дробные части \(\alpha\) _n чисел a_n, 0 ,1,0,1,0,1,0,1. >\in A\)
   \(2\leftrightarrow ,0,1,0,0,0,1. >\in A\)
   …
   Во множестве А содержится бесконечное количество элементов — последовательностей из 0 и 1.

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

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

1.4 Мораль

1. Счетные множества — это конечные + равномощные множеству \(\mathbb\) ( \(\mathbb\) , \(\mathbb\) , \(\mathbb\times\mathbb\) ) ;
2. Несчетная мощность > Счетная мощность : \(\mathbb\) , [0 ; 1] , ( 0 ; 1 ) , [0 ; 1] \(\times\) [0 ; 1] ;
3. Бесконечности бывают разные: одна больше, другая меньше…
   card \(\mathbb\) ^ . Установлено отношение: (a;b;c) \preceq (d;e;f) тогда и только.

4057 / 3021 / 913
Регистрация: 19.11.2012
Сообщений: 6,160

Я бы каждой такой последовательности поставил в соответствие рациональное число по такому правилу
0.a(2), где после десятичной точки стоит последовательность а, состоящая из 0,1,2, но за нею идут только двойки. Легко понять, что тем самым установлена биекция нашего множества последовательностей на подмножество рациональных чисел.

Регистрация: 18.11.2013
Сообщений: 337

kabenyuk, а если рассмотреть не множество рациональных чисел, а просто подмножество последовательностей из 0,1, 2 бесконечного множества, если например L=-это множество последовательностей из 0,1 ,2, а подмножество будет конченое так как у нас 0,1 конечно l(i)=, но только как сюда приписать 2, я не знаю, ну вот, а потом мы получим что L=объединение l(i), где l(i) конечное подмножество и тогда это объединение будет счетное множество, это так вообще, я просто не могу понять ваше рассуждение с рациональными числами

183 / 167 / 53
Регистрация: 27.01.2013
Сообщений: 788

на счетность множества не влияет добавление (объединение) конечного множества. Если множество (2,2,2,2. ) счетно, то .

4057 / 3021 / 913
Регистрация: 19.11.2012
Сообщений: 6,160

Сообщение от ilya0610

я просто не могу понять ваше рассуждение с рациональными числами
Жаль. Красивое рассуждение — специально для вас придумал.

Сообщение от ilya0610

а потом мы получим что L=объединение l(i), где l(i) конечное подмножество и тогда это объединение будет счетное множество

Ваши рассуждения абсолютно ничего не доказывают. Знаете почему? Потому что конечных последовательностей из 0, 1, 2 бесконечное множество, как это вам не покажется странным. Более того эта последняя задача с конечными последовательностями равносильна первоначальной. Просто допишите каждую КОНЕЧНУЮ последовательность из 012 до бесконечной одними двойками.

Сообщение от saden

Если множество (2,2,2,2. ) счетно, то .

Указанное вами множество состоит из одного элемента.

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

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

Re: Счетные множества
16.02.2016, 22:35

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

Например, множество всех слов, составленных из букв русского алфавита, счетно (словом называем любой конечный набор букв, независимо от того, есть ли у него смысл). Нумеруем их так: выписываем в алфавитном порядке сначала все однобуквенные слова, затем все двухбуквенные и т.д.
а — 1
б — 2
.
я — 33
аа — 34
аб — 35
.
ая — 66
ба — 67
.
Таким образом, каждое слово имеет единственный номер, и каждому номеру соответствует единственное слово. Это и есть нужное правило.

Re: Счетные множества
16.02.2016, 22:46

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

Anton_Peplov в сообщении #1100002 писал(а):

Например, множество всех слов, составленных из букв русского алфавита, счетно (словом называем любой конечный набор букв, независимо от того, есть ли у него смысл). Нумеруем их так: выписываем в алфавитном порядке сначала все однобуквенные слова, затем все двухбуквенные и т.д.
а — 1
б — 2
.
я — 33
аа — 34
аб — 35
.
ая — 66
ба — 67
.
Таким образом, каждое слово имеет единственный номер, и каждому номеру соответствует единственное слово. Это и есть нужное правило.

А почему не дать такую нумеровку: 1.в 2.ипп 3.ба. или что-то в этом роде?
Re: Счетные множества
16.02.2016, 22:47
Rusit8800 в сообщении #1099999 писал(а):
множества счетны если их можно «пронумеровать».

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

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

Re: Счетные множества
16.02.2016, 22:50
Rusit8800 в сообщении #1100007 писал(а):
Счетные множества бесконечны, а алфавит конечен, поэтому не счетен.
Re: Счетные множества
16.02.2016, 22:52
Rusit8800 в сообщении #1100007 писал(а):
Счетные множества бесконечны, а алфавит конечен, поэтому не счетен.

Rusit8800 ,
Вы лучше вдумывайтесь в то, что Вам говорят, раз уж просите помощи.
Алфавит конечен, но это не значит, что множество слов в алфавите конечно.
Натуральные числа — это «слова» в «алфавите» из 10 цифр. Разве отсюда следует, что множество натуральных чисел конечно?

Re: Счетные множества
16.02.2016, 22:52

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

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

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

gris в сообщении #1100012 писал(а):

Интересно, а сколько различных способов пронумеровать счётное множество? То есть этих самых «правил».

Rusit8800 в сообщении #1100007 писал(а):
А почему не дать такую нумеровку: 1.в 2.ипп 3.ба. или что-то в этом роде?
На это я только что отвечал.
Anton_Peplov в сообщении #1100014 писал(а):

Можно придумать и другое правило нумерации. Главное, чтобы каждое число за конечное число шагов получило номер. Пытаться перенумеровать сначала все положительные числа, а потом все отрицательные, бессмысленно: ведь положительные никогда не закончатся. Как и в первом примере — с алфавитом — не получится перенумеровать сначала все слова, начинающиеся на «а», потом все слова, начинающиеся на «б» и т.д.

Re: Счетные множества
16.02.2016, 23:00

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

То есть нумерацию нужно составлять так, чтобы получился бесконечный цикл, содержащий все «типы» чисел, например: 0; 1;-1;2;-2 и так далее с увеличением на 1.

Re: Счетные множества
16.02.2016, 23:04

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

Допустим нужно доказать счетность множества всех нечетных чисел, составим «бесконечный цикл нумерации»: 1;-1;3;-3;5;-5 и т.д.Так доказывать?

Re: Счетные множества
16.02.2016, 23:08
Rusit8800 в сообщении #1100018 писал(а):

Допустим нужно доказать счетность множества всех нечетных чисел, составим «бесконечный цикл нумерации»: 1;-1;3;-3;5;-5 и т.д.Так доказывать?

Вполне можно и так.
Re: Счетные множества
17.02.2016, 16:26

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

Re: Счетные множества
17.02.2016, 16:42

Rusit8800 ,
очевидно, там подразумевается использование вспомогательного утверждения: если элементы множества определяются двумя значками («индексами»), каждый из которых пробегает счётное множество значений, то данное множество счётно. Конечно, это утверждение должно быть доказано отдельно.
Но если Вы действительно интересуетесь данным вопросом, попробуйте вначале заглянуть в какой-нибудь подробный учебник матанализа. Например, Л.Д. Кудрявцев, том 1, пункт 4.11. Обнаружите очень понятное доказательство счётности множества рациональных чисел.

Re: Счетные множества
17.02.2016, 16:49
Mihr в сообщении #1100172 писал(а):

Rusit8800 ,
очевидно, там подразумевается использование вспомогательного утверждения: если элементы множества определяются двумя значками («индексами»), каждый из которых пробегает счётное множество значений, то данное множество счётно. Конечно, это утверждение должно быть доказано отдельно.
Но если Вы действительно интересуетесь данным вопросом, попробуйте вначале заглянуть в какой-нибудь подробный учебник матанализа. Например, Л.Д. Кудрявцев, том 1, пункт 4.11. Обнаружите очень понятное доказательство счётности множества рациональных чисел.

Я так понял вы хотите сказать, что если какую-то переменную, которая «подразумевает» из себя счетное множество поделить на аналогичную переменную, то полученное множество будет счетным, не так ли?

Мощность множества функций и континуум-гипотеза
17.02.2016, 17:20

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

Rusit8800 ,
Ваша формулировка мне малопонятна. Ещё раз предлагаю: загляните сначала в учебник. Указанный материал вполне доступен и школьнику.

Re: Счетные множества
17.02.2016, 17:21
Rusit8800 в сообщении #1100175 писал(а):

если какую-то переменную, которая «подразумевает» из себя счетное множество поделить на аналогичную переменную

— бессмысленный набор слов.

Страница 1 из 4

[ Сообщений: 53 ]

На страницу 1 , 2 , 3 , 4 След.

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей