Счетные множества определение и примеры

Счетные множества определение и примеры

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

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

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

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

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

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

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

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

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

□. Пусть А=1, S2, …, Sp-1>, p>1. Определим биекцию ν: N → А* следующим образом: ν(0)= Λ; произвольное число n сначала запишем в р-ичной системе счисления: n=akp k +ak-1p k-1 +…+a, 0≤ai ≤ p-1 т.е. n=[ak…a]p а затем положим ν(n)=San….Sa. Слово, определяемоер-ичным числом, единственное. И наоборот, каждому слову соответствует единственное число – следовательно, это биекция.

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

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

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

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

□ Пусть А — бесконечное множество. Значит, оно непусто и $ а1 ÎА. Положим А11>. А1 не пусто, т.к. в противном случае А =1>, что противоречит предположению о бесконечности А. Продолжим процедуру: в А1 найдётся a2 , положим А212>=А1, a2> …и т.д.

На n-шаге получим: Аn1, …,an> непусто, т.к. в противном случае А=1, …,an>. Кроме того, по построению ai≠ak, если i ≠ k – элементы попарно различны. Тогда $ аn ÎАn и, по построению, Аn+1= Аnn> непустое множество.

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

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

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

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

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

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

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

Последовательность (a11,a21,a12,a22,a31,…) – нумерация. Принцип её построения таков – сначала фиксируется N = 2 и записываются аik такие, что i+k = N. Затем N → N+1 и все повторяется.

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

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

Обозначим через Аn конечный алфавит: Аn=<а1, а2, …, an>. Любое слово в А* состоит из конечного числа букв (по определению), поэтому оно является словом в некотором конечном алфавите, а именно в Ak, k=max(k1, k2, …, kn). Т.о., множество всех слов в алфавите А есть объединение счётного числа множеств А1, А2,…, Аn .

Пример. Алгебраические числа. Корни произвольного многочлена anx n +… + a , где аk – целые числа, называются алгебраическими числами. Многочлен можно рассматривать как слово в конечном алфавите: А= <0,1,2,… ,*,+,->– множество таких слов счетно, а корней у многочлена конечное число. Поэтому и множество всех алгебраических чисел счётно.

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

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

Читайте также:  Как подтвердить заказ на юле

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

(А (BÇC))Ç(BÇC)= А→ AB=(А (BÇC))ÇC

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

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Как то на паре, один преподаватель сказал, когда лекция заканчивалась — это был конец пары: "Что-то тут концом пахнет". 8755 — | 8288 — или читать все.

Лекция 10. Конечные и бесконечные множества

10.1.Конечные и бесконечные множества

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

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

10.4.Несчетность множества действительных чисел

Программные положения

Лекция посвящена вопросам сравнения бесконечных множеств. Рассматриваются счетные и несчетные множества, вводится понятие мощности как инструмента различения бесконечных множеств

Методические рекомендации

Обратите внимание на различие в определении счетных и несчетных множеств, понятие мощности

Литература

А.В. Дорофеева «Высшая математика» глава XIV стр.330-356

Р.Курант, Г.Роббинс «Что такое математика» глава II § 4, стр. 104-115

А.Я.Хинчин «Восемь лекций по математическому анализу». Лекция 1 «Кнтинуум»

Контрольные вопросы

1. Приведите примеры конечных и бесконечных множеств

2. Дайте определение счетного множества (приведите примеры)

3. Дайте определение несчетно множества (приведите примеры)

4.Покажите, что у конечного множества из n элементов 2 n подмножеств

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

5. Докажите, что множество действительных чисел несчетно

6. Приведите примеры множеств эквивалентных отрезку [0,1]

Конечные и бесконечные множества

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

Определение 10.1.

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

Два конечных множества мы можем сравнивать по числу элементов и судить, одинаково это число или же в одном из множеств элементов больше, чем в другом. Спрашивается, можно ли подобным же образом сравнивать бесконечные множества? Иначе говоря, имеет ли смысл, например, вопрос о том, чего больше: кругов на плоскости или рациональных точек на прямой, функций, определенных на отрезке [0,1], или прямых в пространстве, и т.д.?

Сравнение конечных множеств

Сравнивая конечные множества можно поступать двояко:

1) подсчитать и сравнить число элементов

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

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

Например, сравнивая множество студентов 1 курса и множество стульев в аудитории № 1 можно подсчитать количество студентов и стульев, а можно рассадить студентов в аудитории, тем самым попробовав установить взаимно однозначное соответствие между этими множествами. Если мест хватит всем и не останется ни одного лишнего стула, т. е. если будет установлена биекция между этими двумя множествами, то это и будет означать, что число элементов в них одинаково.

Замечание 10.1.

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

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

Определение 10.2.(1)

Назовем счетным множеством всякое множество, элементы которого можно биективно сопоставить со всеми натуральными числами. Иначе говоря, счетное множество — это такое множество, элементы которого можно занумеровать в бесконечную последовательность: а1 , а2, а3, …

Примеры 10.2.

1. Множество всех целых чисел. Установим соответствие между всеми целыми и всеми натуральными числами по следующей схеме:

Читайте также:  Решение дифференциальных уравнений с переменными коэффициентами

вообще, неотрицательному числу n≥0 сопоставим нечетное число

2n + 1, а отрицательному n n . степеней числа 2. Здесь соответствие также очевидно. Каждому числу 2 n сопоставляется число n.

4. Множество рациональных чисел (см. п.10.3)

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

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

Замечание 10.2.

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

Теорема 10.2(1).

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

Пусть X — бесконечное множество; тогда оно во всяком случае непусто, т. е. в нем существует по крайней мере один элемент, обозначим его через х1. Поскольку множество X бесконечно, то множество X 1> также непусто, т. е. содержит по крайней мере один элемент, обозначим его х2. Продолжая этот процесс, на n-м шаге получим элемент хn. Поскольку X — бесконечное множество, то множество X <х1,x2, . хn> непусто, т. е. содержит по крайней мере один элемент, обозначим его хn+1 и т. д.

Множество < х1,x2, . хn. > — искомое счетное подмножество множества X.

Теорема 10.2(2).

Любое бесконечное подмножество счетного множества счетно.

Пусть X — счетное множество: X = < х1,x2, . хn …>и .

Обозначим через у1 элемент из У, имеющий наименьший номер в X, через y2 — элемент множества У, имеющий следующий ближайший номер, и т. д. Поскольку каждый элемент множества Y является некоторым элементом хn множества X и, следовательно, имеет номер n, то через конечное число шагов (не больше, чем n) он получает некоторый номер m и в множестве У, т. е. будет обозначен уm, причем, поскольку множество Y бесконечно, этот процесс может быть продолжен неограниченно. Таким образом, все элементы множества Y окажутся перенумерованными, что и означает счетность этого множества. |

Возникает естественный вопрос, существуют ли несчетные множества, т. е. бесконечные множества, не являющиеся счетными, а если существуют, то интересно построить пример несчетного множества. Соответствующий пример рассмотрен в п.10.4

Будем говорить, что множество X счетно, если оно равномощно множеству натуральных чисел N.

Пример 1. Пусть X множество нечетных натуральных чисел. Покажем, что X счетно. Для этого нужно установить биекцию множества X на множество натуральных чисел, т.е. занумеровать элементы множества X так, чтобы каждому элементу X соответствовал ровно один номер, а любому натуральному числу соответствовал ровно один элемент из X. Очевидно, соответствие N, удовлетворяет этим требованиям:

Таким образом, ½X½=½N½ и X счетно.

Пример 2. Пусть X=N´N – декартово произведение множества N на себя. Покажем, что X счетно. Расположим все элементы X в виде матрицы (рис. 1.24) и занумеруем его элементы “ по диагоналям ”: номер 1 присвоим элементу (1,1), номер 2 – элементу (2,1), 3 – (1,3) и т.д.

Полученное отображение X на N также является биекцией (хотя записать формулу в явном виде сложнее, чем в примере 1).

Мощность счетного множества обозначается À. Когда мы пишем ½X½=À, мы утверждаем, что множество X счетно, т.е. относится к тому же классу эквивалентности, что и множество натуральных чисел. А множество N считается эталоном (образцом) счетных множеств.

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

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

Основой для такого утверждения служат следующие теоремы о счетных множествах.

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

Пусть X – счетное множество, а – произвольное его подмножество. Занумеруем элементы множества и выберем тот элемент, который имеет минимальный номер и принадлежит подмножеству Y, – обозначим его . Затем рассмотрим множество и найдем в нем элемент с минимальным номером, принадлежащий Y, — обозначим , и т.д. Если на n-ом шаге мы не обнаружим в множестве элементов множества Y, то Y конечно и ½Y½=n. В противном случае (если процесс будет продолжаться бесконечно) множество Y счетное, т.к. указан способ нумерации его элементов.

Читайте также:  В какой программе можно сделать фильм

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

Пусть X – бесконечное множество. Выберем произвольный элемент . Так как X бесконечно, то Æ. Обозначим произвольный элемент из . Далее найдется . Поскольку X бесконечно, этот процесс не может оборваться из-за “нехватки” элементов, и мы получим счетное подмножество Y множества X: .

Теорема 3. Объединение конечного или счетного количества счетных множеств есть множество счетное.

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

,

где в первой строке записаны элементы множества , во второй – и т.д. Занумеруем эти элементы “по диагонали”(как в примере 2 из 1.4.5), при этом устанавливается биекция между множествами X и N, т.е. X – счетное множество.

Теорема 4. Пусть X бесконечное множество, а Y – счетное. Тогда .

Теорема утверждает, что добавление счетного множества элементов не увеличивает мощность бесконечного множества.

Доказательство. Рассмотрим множество и представим его в виде объединения непересекающихся множеств где . Так как Y счетно, то конечно или счетно (по теореме 1). Множество X бесконечно, значит, существует счетное подмножество (по теореме 2). Тогда , а

.

По теореме 3 счетно, т.е . Поэтому . Теорема доказана.

В примере 1 из 1.4.5 мы установили, что множество N равномощно своему собственному подмножеству. Рассуждения, близкие к доказательству теоремы 4, позволяют утверждать, что таким свойством обладает не только множество N, но любые бесконечные множества.

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

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

Рассмотрим множество R. Сравним его с множеством N. Очевидно, что ½N½. Действительно, отрезок [0;1] содержит счетное подмножество , значит, является не менее, чем счетным. Покажем, что [0;1] и N не являются равномощными множествами, т.е. что .

Теорема. Множество точек отрезка [0;1] не является счетным.

Проведем доказательство методом “от противного”. Предположим, что множество [0;1] счетно, т.е. существует биекция N на [0;1], и каждому элементу отрезка можно присвоить номер: N>. Каждый элемент отрезка [0;1] представляется в виде бесконечной десятичной дроби , где j-я десятичная цифра i-го элемента. Запишем все элементы N, в порядке возрастания номеров. Покажем, что найдется элемент b, принадлежащий отрезку [0;1], но не совпадающий ни с одним из занумерованных элементов N. Метод построения такого элемента называется диагональной процедурой Кантора и заключается в следующем. Будем строить элемент b в виде бесконечной десятичной дроби , где i-я десятичная цифра. В качестве возьмем любую цифру, не совпадающую с , – любую цифру, не совпадающую с , и т.д., при любых N (рис. 1.26). Построенный таким образом элемент b принадлежит отрезку[0;1], но отличается от каждого из занумерованных элементов хотя бы одной цифрой. Следовательно, предположение о том, что существует биекция N ® [0;1]ошибочно, и множество [0;1] не является счетным.

Рис. 1.26. Диагональная процедура Кантора

Итак, мы показали, что ½[0;1]½>½N½, т.е. класс эквивалентности, которому принадлежит отрезок [0;1], расположен правее класса À счетных множеств в ряду мощностей (рис. 1.25). Обозначим этот класс À (без индекса). Множества, принадлежащие этому классу, называются несчетными или множествами мощности континуум (континуум – непрерывный). Этому классу принадлежат и интервал (0;1), и множество R действительных чисел, и множество точек круга на плоскости.

Пример. Множество R имеет мощность континуума, т.к. равномощно отрезку [0;1]. Действительно, по теореме Кантора-Бернштейна (см. 1.4.3) ½[0;1]½= ½(0;1)½. Биекцию интервала (0;1)на множество R можно задать с помощью сложной функции , где имеет вид и отображает интервал (0;1)на интервал , а отображает интервал на R по закону .

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого.

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций.

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

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ — конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой.

Ссылка на основную публикацию
Стиральная машина самсунг горит красный замок
Любая стиральная машина в независимости от марки производителя иногда выходит из строя. Довольно частым признаком неисправности, является мигание индикатора замка....
Справка по форматированию steam
С помощью этих тегов разметки можно форматировать текст ваших сообщений, примерно как в HTML. Маркированный список Маркированный список Маркированный список...
Справочные материалы база данных
АРМ предназначено для комплексной автоматизации операций, связанных с первичным размещением и вторичным обращением ценных бумаг. Оно рассчитано на работу с...
Стиральная машинка lg не выжимает
Покупка стиральной машинки – знаменательное событие для любой хозяйки. Незаменимая помощница позволяет женщинам экономить личное время, не тратя его на...
Adblock detector