admin / 20.03.2018

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

56. Конечные множества. Бесконечные множества, счетные множества.

Бертран Расселл: «Множество есть совокупность различных элементов, мыслимая как единое целое».

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

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

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

Два множества X и Y называются эквивалентными, если существует биективное отображение одного множества в другое. Если множества X и Y эквивалентны, то этот факт записывают X ῀ Y или и говорят, что множества имеют одинаковые мощности.

Два конечных множества равномощны тогда и только тогда, когда они состоят из одинакового числа элементов. То есть для конечного множества понятие мощности совпадает с привычным понятием количества.

Бесконечные множества.

В теории множеств, счётное множество есть бесконечное множество, элементы которого возможно пронумеровать натуральными числами. Более формально: множество X является счётным, если существует биекция XN, где N обозначает множество всех натуральных чисел. Другими словами, счётное множество — это множество, равномощное множеству натуральных чисел.

Счётное множество является «наименьшим» бесконечным множеством, то есть в любом бесконечном множестве найдётся счётное подмножество.

Свойства.

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

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

3. Прямое произведение конечного числа счётных множеств счётно.

4. Множество всех конечных подмножеств счётного множества счётно.

5. Множество всех подмножеств счётного множества континуально и, в частности, не является счётным.

57. Несчетные и континуальные множества.

Бертран Расселл: «Множество есть совокупность различных элементов, мыслимая как единое целое».

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

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

Множество X действительных чисел, заключенных между 0 и 1, несчетно.

Так же существует геометрическая версия этого утверждения: Множество всех точек отрезка [0,1] несчетно.

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

Мощность множества всех подмножеств счетного множества называется мощностью континуума.

Континуальным множеством называется множество, равномощное множеству вещественных чисел. Например, совокупность всех точек отрезка прямой (или множество всех трансцендентных чисел). Говорят: «континуум», «множество мощности континуум» или «континуальное множество».

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

Множество действительных чисел, заключенных между 0 и 1, несчетно.

Множество действительных чисел D включает в себя множество R рациональных чисел и множество Q иррациональных чисел. Любое иррациональное число можно представить бесконечной непериоди­ческой десятичной дробью.

Множество R – счетное, если мы докажем, что множество Q – несчетное, то несчетным будет и множество D.

Предположим, что дано какое-то счетное множество иррацио­нальных (действительных)чисел A , лежащих на отрезке [0; 1]:

A1 = 0, А11, А12, А13, …, А1n, …

A2 = 0, А21, А22, А23, …, А2n, …

. . . . . . .

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

. . . . . . . . .

AM = 0, Аm1, Аm2, Аm3, …, Аmn, …,

Где АijJ-я десятичная цифра числа AI.

Построим десятичную дробь

B = 0, B1, B2, B3, …, Bn

С помощью Диагональной процедуры Кантора, а именно: за B1 примем произвольную цифру, не совпадающую с А11; за B2 – произ­вольную цифру, не совпадающую с А22, и т. д. Вообще за BN примем произвольную цифру, не совпадающую с AMn. Построенная таким образом дробь b не совпадает ни с одной дробью a. От a1 она отли­чается по крайней мере первой цифрой, от a2 – по крайней мере второй цифрой и т. д.

Таким образом, никакое счетное множество иррациональных (действительных) чисел, лежащих на отрезке [0; 1], не исчерпывают этого отрезка. Следовательно, множество иррациональных чисел и мно­жество действительных чисел на отрезке [0; 1] является несчетным.

Любые множества, эквивалентные отрезку [0; 1], являются Несчетными:

1. Множество всех точек любого отрезка [ А; B ].

2. Множество всех точек прямой.

3. Множество всех прямых на плоскости.

4. Множество всех непрерывных функций одной или нескольких переменных и т. д.

Теория множеств появилась в конце 19 века благодаря работам немецкого математика Георга Кантора (1845-1918). Понятие множества принадлежит к числу фундаментальных неопределяемых понятий математики. Интуитивно мы понимаем множество как совокупность объектов. Кантор говорил: «Множество – это многое, понимаемое как единое». Примеры множеств: множество домов в городе, множество его жителей, множество звезд на небе и т.д.

Среди других множеств особое положение занимают так называемые числовые множества. Первое числовое множество, которое открылось человеческому сознанию, было множество натуральных чисел (обозначается буквой N): 1, 2, 3, … Идею их существования подсказывала сама природа (Nature). «Три дерева, три апельсина, три человека» – натуральное число «три» как-то связывало эти разные объекты, придавало им некую общность.

Но даже простые натуральные числа имели какую-то тайну. Это множество имело начало (число 1), однако не имело конца. Каким бы большим не было бы натуральное число, можно было бы получить еще большее, прибавив к нему единицу. Таким образом, множество натуральных чисел – бесконечное множество.

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

Например, множество четных чисел счетно. Числу 2 можно поставить в соответствие число 1, числу 4 – 2, числу 6 – 3 и т.д. Этот процесс можно продолжать до бесконечности.

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

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

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

Эти множества также являются счетными, так как можно установить взаимно однозначное соответствие между ними и множеством натуральных чисел, как показано в табл. 1.1.

Таблица 1.1

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

Кантор открыл, что множество рациональных чисел также счетно, хотя всюду плотно на числовой оси в отличие от множества натуральных чисел.

Таблица 1.2

1/2 2/2 3/2 4/2 5/2 6/2 7/2
1/3 2/3 3/3 4/3 5/3 6/3 7/3
1/4 2/4 3/4 4/4 5/4 6/4 7/4
1/5 2/5 3/5 4/5 5/5 6/5 7/5
1/6 2/6 3/6 4/6 5/6 6/6 7/6
1/7 2/7 3/7 4/7 5/7 6/7 7/7

Все рациональные числа можно внести в таблицу с бесконечным количеством строк и столбцов (табл. 1.2). Если двигаться из левого верхнего угла по зигзагообразной траектории, нумеруя по пути ячейки числами натурального ряда, то можно показать взаимно однозначное соответствие между множествами натуральных и рациональных чисел.

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

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

Рис. 1.1. Величина диагонали единичного квадрата

Математика древних греков носила геометрический характер. Из теоремы Пифагора следует, что диагональ единичного квадрата (рис. 1.1) равна по величине . Доказательство того, что число несоизмеримо с единицей, т.е. иррационально, греческие математики проводили методом от противного.

Прежде чем приступать к этому доказательству, рассмотрим следующую лемму (греч. lemma – вспомогательное предложение, используемое при доказательстве теоремы).

Лемма 1.1. Квадрат четного числа – четное число, а квадрат нечетного числа – нечетное число.

Доказательство. Любое четное число можно записать как , а нечетное – как , Квадрат четного числа является четным числом, так как делится на два без остатка. Квадрат нечетного числа является нечетным числом, поскольку делится на два с остатком.

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

. (1.1)

Считаем, что дробь несократима, иначе мы с самого начала сократили бы ее на общий наибольший делитель чисел и . С правой стороны имеется 2 в качестве множителя, и потому есть четное число, и, значит, само также четное. В таком случае можно положить . Тогда равенство (1.1) принимает вид: , или . Так как с левой стороны теперь имеется 2 в качестве множителя, значит , а следовательно, и – четное. Итак, и и – четные числа, т.е. делятся на два, а это противоречит допущению, что дробь несократима.

Итак, равенство (1.1) невозможно, и не может быть рациональным числом.

Иррациональными числами являются также число =3,14… – отношение длины окружности к ее диаметру и неперово число e=2,71… – основание натуральных алгоритмов.

Иррациональные числа могут быть представлены бесконечными непериодическими дробями.

и e – это «звезды», одни из самых знаменитых чисел на свете. Ординарных, ничем не примечательных иррациональных чисел гораздо больше. Их общее количество в бесконечное количество раз превышает счетное количество рациональных чисел.

Множество всех рациональных и иррациональных чисел составляет множество действительных чисел (обозначается буквой R). Кантор доказал, что множество всех действительных чиселнесчетно. Другими словами, совокупность всех действительных чисел совершенно иного (так сказать более высокого) «типа бесконечности», чем совокупность одних только целых или одних только рациональных чисел.

Докажем это фактически. Допустим, что все действительные числа, представленные в виде бесконечных десятичных дробей, расположены в порядке последовательности, или списка:

1-е число:

2-е число:

3-е число:

……………………………

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

Построим такое число.

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

Для этого возьмем первую цифру после запятой , какую угодно, но отличную от , а также от 0 и 9 (последнее – чтобы избежать затруднений, возникающих из равенств вроде следующего: 0,999…= 1,000…); затем вторую цифру возьмем отличной от , а также от 0 и 9; третью цифру – отличной от и т.д.

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

Это новое число наверняка не входит в наш список; действительно, оно не равно первому числу, стоящему в списке, так как от него отличается первой цифрой после запятой, оно не равно второму числу, так как от него отличается второй цифрой после запятой, и вообще отлично от -го числа по списку, так как от него отличается -ой цифрой после запятой. Итак, в нашем списке, составленном будто бы из всех действительных чисел, нет числа . Значит, множество всех действительных чисел несчетно.

Позже всех остальных было открыто множество комплексных чисел, которое обозначается буквой C. Комплексное число записывается следующим образом: , где и – действительные числа, – мнимая единица. Множество комплексных чисел равномощно множеству действительных чисел.

Итак, существует, по меньшей мере, два различных «типа бесконечности»: счетная бесконечность натуральных чисел и несчетная бесконечность континуума (от латинского continuum – «непрерывное») действительных (и комплексных) чисел. Дискретная математика имеет дело со счетными множествами. Более того, она, как правило, имеет дело с конечными счетными множествами.


⇐ Предыдущая24252627282930313233Следующая ⇒


Дата публикования: 2014-11-03; Прочитано: 1062 | Нарушение авторского права страницы



studopedia.org — Студопедия.Орг — 2014-2018 год.(0.004 с)…

Не следует путать с перечислимым множеством.

В теории множеств, счётное мно́жество есть бесконечное множество, элементы которого возможно пронумероватьнатуральными числами. Более формально: множество является счётным, если существует биекция , где обозначает множество всех натуральных чисел.

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

Другими словами, счётное множество — это множество, равномощное множеству натуральных чисел.

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

Счётное множество является «простейшим» бесконечным множеством, то есть: в любом бесконечном множестве найдётся счётное подмножество; всякое подмножество счётного множества конечно или счётно; если к бесконечному множеству присоединить конечное или счётное, то получится множество, эквивалентное исходному[1].

Мощность множества всех натуральных чисел обозначается символом (произносится: «алеф-ноль»).

Свойства

  1. Всякое бесконечное множество имеет счётное подмножество[1].
  2. Любое подмножество счётного множества не более чем счётно (т.е. конечно или счётно).[2][1]
  3. Если к бесконечному множеству присоединить конечное или счётное, то получится множество эквивалентное исходному[1].
  4. Объединение конечного или счётного числа счётных множеств счётно.[2]
  5. Прямое произведение конечного числа счётных множеств счётно.
  6. Множество всех конечных подмножеств счётного множества счётно.
  7. Множество всех подмножеств счётного множества континуально и, в частности, не является счётным.

Связанные понятия

Несчётное множество — такое бесконечное множество, которое не является счётным. Таким образом, любое множество является либо конечным, либо счётным, либо несчётным.

Примеры

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

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

Примечания

См. также

Литература

  • Брудно А. Л. Теория функций действительного переменного. — М.: Наука, 1971. — 119 с.

FILED UNDER : IT

Submit a Comment

Must be required * marked fields.

:*
:*