что такое счетное число

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

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

Мощность множества натуральных чисел обозначается א₀ = |N|.

Не более чем счётное множество – множество счётное или конечное.

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

Любая биекция ν : N → M называется нумерацией множества М. М=i| i= 0, 1,2, …>.

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

Пусть задан алфавит А – некоторое множество символов, называемых также буквами. Назовём словом в данном алфавите конечный ряд букв, написанных друг за другом. Иногда удобно рассматривать пустое слово, совсем не содержащее букв – его обозначают Λ.

Докажем, что в любом языке имеется счётное множество слов

Теорема. Если алфавит А конечен, то множество слов в алфавите А* счётно.

□. Пусть А=1, S₂, …, S_p-1>, p>1. Определим биекцию ν: N → А* следующим образом: ν(0)= Λ; произвольное число n сначала запишем в р-ичной системе счисления: n=a_kp k +a_k-1p k-1 +…+a₀, 0≤a_i ≤ p-1 т.е. n=[a_k…a₀]_p а затем положим ν(n)=Sa_n….Sa₀. Слово, определяемоер-ичным числом, единственное. И наоборот, каждому слову соответствует единственное число – следовательно, это биекция. ■

Следствие: слов в алфавите <0,1,2,…,9>– счётное число. Это – проверка на корректность – мы снова подтвердили счётность множества натуральных чисел.

Теорема. Любое подмножество счётного множества не более чем счётно.

□ Пусть А – счетно. Значит, его элементы могут быть перенумерованы: <а₁, а₂, …, a_n,…>. Элементы любого подмножества ВÍА можно расположить в порядке возрастания номеров: . Следовательно, подмножество имеет нумерацию ν(n)= ■

Теорема. Любое бесконечное множество содержит счётное подмножество.

Таким образом, по индукции мы построили множество, состоящее из попарно различных элементов <а₁, а₂, …, a_n,…>Î А₀ с нумерацией ν(n)=a_n. ■

Из доказанных теорем следует, что счётное множество является самым минимальным по мощности из всех бесконечных множеств – потому, наверно, его и называют алеф ноль.

Теорема. В любом бесконечном множестве можно выделить два непересекающихся между собой счётных множества. Доказательство – разбиение на чётную и нечётную нумерации.

Семейство множеств i>|_iÎIназывают не более чем счётным, если таково множество I.

Теорема. Объединение любого не более чем счетного семейства множеств счётно.

Занумеруем элементы объединения семейств следующим образом:

a) I конечно; б) I счетно

Последовательность (a₁₁,a₂₁,a₁₂,a₂₂,a₃₁,…) – нумерация. Принцип её построения таков – сначала фиксируется N = 2 и записываются а_ik такие, что i+k = N. Затем N → N+1 и все повторяется.

Замечание: В семействах могут быть одинаковые элементы

Следствие. Множество А* всех слов в счётном алфавите А счётно. Пусть задана нумерация в А: A=<а₁, а₂, …, a_n,…>

Теорема. Множество значений функции, определённой на счётном множестве, не более чем счётно. ν(n) = f(a_n) – нумерация.

Теорема. Пусть А – бесконечное множество, а B – его не более чем счётное подмножество. Тогда, если множество A\B бесконечно, то оно равномощно множеству A.

Выберем из A\B счётное подмножество C; по построению B∩C =О. Объединение B и C счётно, поэтому существует биекция f : BÇC→C. Надо построить биекцию А→ A\B. Построим:

(А\ (BÇC))Ç(BÇC)= А→ A\B=(А\ (BÇC))ÇC

Следствие: если A бесконечно, а B не более чем счётно, то объединение AÇB не более чем счетно.

Источник

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

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

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

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

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

Подмножеством некоторого набора компонентов называется любая часть компонентов этого набора. То есть, совокупность состоящее из чисел 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. Докажите, что множество точек строгого локального максимума любой функции действительного аргумента конечно или счетно.

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

Источник

Счётные и несчётные множества — понятие, свойства и примеры

Множество — это совокупность или набор элементов. Количество этих элементов называется мощностью этой совокупности. Мощность пустого набора компонентов равна нулю. С размером конечных совокупностей тоже всё просто. У них можно пересчитать количество компонентов. А вот возможность посчитать компоненты бесконечности различает счётные и несчётные множества.

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

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

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

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

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

Подмножеством некоторого набора компонентов называется любая часть компонентов этого набора. То есть, совокупность состоящее из чисел 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.

Поскольку N отображается в R конъюнктивно (N является подмножеством R, но не имеет подмножества эквивалентного R), то |R|=c > a=|N|. А так как R представляет собой объединение совокупностей Q и I, то размер |I| = |R| — |Q| = c — a = c. Значит, I тоже континуально.

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

Совокупность всех точек интервала или отрезка на прямой тоже будет континуальна, так как на неё можно спроецировать всю совокупность точек действительной прямой 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. А у этого булеана тоже есть булеан с ещё большей мощностью.

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

Источник