Интуитивное понятие множества. Элементы множества

ДИСКРЕТНАЯ МАТЕМАТИКА

Лекция 1

Обозначения: знаки Ç, Þ, Û заменяют словесные обороты «есть по определению», «если …то …», «тогда и только тогда, когда» соответственно.

ЧАСТЬ 1. МНОЖЕСТВА И ОТНОШЕНИЯ

Основные понятия теории множеств

Окружающий нас мiр – неразрывное целое, но человеческое мышление устроено так, что мiр представляется состоящим из отдельных «объектов». По-видимому, выделение объектов и их совокупностей – единственный способ организации нашего мышления, позволяющий сформулировать доступную для рационального анализа картину мiра. Неудивительно, что этот способ лежит в основе математики. Тем не менее, общее (абстрактное) понятие множества появилось в математике сравнительно недавно, в конце 19-го века, в связи с работами Кантора по сравнению мощностей различных множеств. В то время пересматривались основы математики, и теорию множеств сочли наилучшим кандидатом на роль фундамента.

Интуитивное понятие множества. Элементы множества

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

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

· Множество S студентов, присутствующих на лекции.

· Множество Í натуральных чисел 1, 2, 3, …

· Множество Ï простых чисел 2, 3, 5, 7, …

· Множество Ù целых чисел …, –2, –1, 0, 1, 2, …

· Множество Ñ действительных чисел.

· Множество А символов на данной странице.

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

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

А. Существенным пунктом канторовского понятия множества является то, что совокупность предметов рассматривается как один предмет («представляется как единое целое»). Основное внимание тут переносится с отдельных предметов на совокупности, которые, в свою очередь, можно рассматривать как предметы.

Б. Что касается «предметов нашей интуиции или интеллекта», то эта формулировка даёт значительную свободу прежде всего тем, что никак не ограничивает природу предметов, составляющих множество. Множество может состоять, например, из людей, точек плоскости, простых чисел, планет Вселенной. Заметим также, что канторовская формулировка множества дает возможность рассматривать множества, элементы которых по определённой причине точно задать невозможно. Так, элементы любого бесконечного множества, даже теоретически, нельзя собрать в законченную совокупность («актуальная бесконечность»). Известны и конечные множества, которые имеют такую же меру неопределённости, как и любое бесконечное множество.

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

Интуитивный принцип объёмности или аксиома экстенсиональности:

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

Таким образом, два множества равны, если каждый элемент одного из них является элементом другого и наоборот. Равенство двух множеств А и В обозначают А = В.

· Если объект а является элементом множества А, то говорят, что а принадлежит А. Обозначение: а Î A. В противном случае говорят, что а не принадлежит А. Обозначение: а Ï A.

· Через { а ₁, а ₂, …, а _n} обозначается множество, которое содержит элементы а ₁, а ₂, …, а _n и не содержит других.

· Множество называется конечным, если оно состоит их конечного числа элементов.

В менее формальных ситуациях через { а ₁, а ₂, …, а _n, … } или даже через { а _i} обозначают множество членов последовательности а ₁, а ₂, …, а _n,… Более аккуратная запись для того же множества такова: {a_i| i ÎÍ }, где Í – множество натуральных чисел.

Из множеств, как объектов, можно составлять новые множества. Множество, элементами которого являются множества, иногда называют семейством. Как правило, обозначения множеств–элементов в этом случае снабжают индексом. Запись:

M = {M_α}_αÎA

означает, что M является множеством, элементами которого являются множества M_α, причём индекс α «пробегает» множество А.

· Множество { а } – так называемое одноэлементное множество – единственным элементом которого является а.

· Множества A={2,4,6}, B={2,6,4}, C={2,2,6,4,4}, C´={2,2,4,4,6,6} – равны, поскольку состоят из одних и тех же элементов. Различие здесь состоит в порядке элементов и в множественности их.

· Множества {{ a,b }, { b,c }} и { a, b, c } не равны, поскольку первое состоит из элементов { a,b } и { b,c }, а второе – из элементов a,b,c.

· Множества {{1,2}} и {1,2} не равны, поскольку первое множество одноэлементное, а второе – двухэлементное.

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

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

Множество, которое состоит из элементов некоторого множества А, так, что эти элементы могут входить в состав этого множества в каком угодно количестве экземпляров, будем называть мультимножеством множества А (или набором). С точки зрения теории множеств множество и его мультимножество – это один и тот же объект, и они между собой не различаются. Однако часто, особенно когда заходит о представлении множеств в памяти вычислительной машины, возникает потребность отличать множества от мультимножества.

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

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

Свойствами являются, например, такие записи: «3 делит х»; «x < x»; «x² = 2»; «x²+1>0».

Выражения: «для всех х, y xy = yx»; «существует такой х, что 2х<0» – не являются свойствами, потому что их нельзя характеризовать как истинные или ложные относительно х.

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

Интуитивный принцип абстракции или аксиома свёртки.

Всякое свойство Р определяет некоторое множество А с помощью условия: элементами множества А являются те и только те предметы а, которые обладают свойством Р(а).

Обозначение: A={ а | P(а)} – читается: множество А элементов а, которые удовлетворяют условию Р(а) (характеристический предикат).

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

· Множество натуральных чисел Í ={0,1,2,…,n,…} можно задать с помощью принципа свертки. Пусть А={0,1,2,3,4,5,6,7,8,9} – множество из 10-ти элементов, которое будем называть алфавитом. Всякий набор символов (=букв) из этого алфавита, записанных один за другим, назовём словом в алфавите А. Тогда множество Í ={р = xy…z| x, y, …, z Î A} составляет множество натуральных чисел. Для того чтобы запись любого числа была однозначной, можно доопределить: Í ={p =xy…z| x, y, …, z Î A, х≠0 или р=0}.

· Множество натуральных положительных чисел Í ₊={1,2,…,n,…} – множество слов в алфавите А, среди которых нет слова 0.

· Множество целых чисел Ù ={…, -n,…,-2,-1,0,1,2,…,n,…} это множество слов в алфавите B={-,0,1,2,3,4,5,6,7,8,9} Ù ={ p=xy…z| x, y, …, z Î B и х≠0 и y,…,z ≠ -, 0, если р=0}

· Множество рациональных чисел состоит из всех целых чисел и несократимых рациональных дробей. Q={m/n| m, n ÎÙ b, n ≠ 0}.

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

· Пусть А – некоторое множество, а Р(а) имеет вид а ≠ а, тогда множество { х | Р(х)}, очевидно, не имеет элементов.

Из принципа объёмности следует, что может существовать только одно такое множество. Оно называется пустым множеством и обозначается ¯.

Подводя итоги, отметим, что множества могут задаваться:

А) перечислением элементов;

Б) с помощью свойств, которым удовлетворяют его элементы;

В) порождающей процедурой, т.е. способом построения элементов.

Понятие множества, элемента и принадлежности, которые на первый взгляд представляются интуитивно ясными, при ближайшем рассмотрении такую ясность утрачивают. Например, символы а и а, которые встречаются на данной странице – это один элемент множества А или два? Является ли число 123…137 простым?

Задание множеств с помощью предиката в некоторых случаях может приводить к противоречию.

Парадокс Рассела:

Ни одно известное множество Х не содержит себя в качестве элемента: ХÏХ. Определим этим свойством множество Y = {X| ХÏХ}. Естественно спросить, а будет ли обладать свойством YÏY? Если обладает, то оно должно быть включено в самого себя (!), т.е. YÎY. Если же, напротив, YÎY, то по свойству элементов Y должно быть YÏY. Таким образом, введение «множества всех множеств» приводит к логическому парадоксу.

Избежать парадоксов подобных этому можно разными способами, например:

а) Использовать только множества, заведомо существующие, из некоторого достаточно обширного семейства – универсума.

б) Теория типов.

в) Явный запрет принадлежности множества самому себе: ХÎХ – недопустимый предикат. Аксиома регулярности.