Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Элементы теории множеств




§1. Множества и их спецификация (способы задания)

Понятие множества - одно из основных понятий математики. Вообще говоря, это неопределяемое понятие, такое как точка или прямая в геометрии, как число в арифметике.

Ввел это понятие немецкий математик Георг Кантор(1849-1918). Он определил его так: множество есть многое мыслимое как единое целое.

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

Утверждения типа ”объект а есть элемент множества А” и “объект а принадлежит множеству А”, которые имеют один и тот же смысл, записывают а_А, а если объект а не является элементом множества А, то пишут а_А.

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

Множество, которое подчиняется лишь такому требованию, может содержать элементы любой природы:

· множество зарезервированных слов языка Паскаль;

· множество натуральных чисел;

· множество символов, доступных данному компьютеру;

· множество левых ботинок.

Множества будем обозначать прописными буквами А, В, С,..., а элементы строчными а, b, с,...

Есть и некоторые специальные, часто встречающиеся, множества, для которых мы будем использовать специальные обозначения: R- множество действительных чисел; Q- множество рациональных чисел; Z- множество целых чисел; N- множество натуральных чисел.

Одно и то же множество можно описать по-разному, например:

1) множество всех четных натуральных чисел;

2) множество всех чисел вида 2n, где n - натуральное.

Как видим, эти два описания определяют одно и то же множество.

Поэтому нужно ответить на вопрос: когда два описания определяют одно и то же множество?

Под спецификацией множества будем понимать символический способ его задания. Существует два основных способа спецификации множеств:

1. перечислить все его элементы: А={1,2,3,4,5}, B={begin, end, if, then, do, for, while, repeat, until,...}

2. записать признак, определяющий его элементы в виде высказывательной формы, то есть в виде {x| P(x) истинно}, где Р(х)— высказывательная форма или проще {x| P(x)} читается: множество состоит из таких элементов х, что истинно Р(х)( то есть множество определяется как множество истинности некоторой высказывательной формы).

Пример: А={a| a_N)a<6}, B={x| x-зарезервированное слово языка Паскаль}.

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



Приведем некоторые примеры.

Учитывая определение равенства множеств: {7,8,9} = {8,9,7} = {9,8,7} = ={7,8,9,8,9}, поскольку элемент каждого из выписанных здесь множеств является элементом другого. Однако если три первые спецификации можно как-то объяснить (например, требование какой-то задачи), то последнюю спецификацию следует считать неудачной, поскольку не все элементы можно отличить друг от друга.

Рассмотрим множество X={“Введение в Паскаль”, ”Основы структурных данных”, ”Введение в Паскаль”}. Что это: множество, состоящее из двух книг, записанных по невнимательности дважды, или это три книги, две из которых имеют одинаковое название? В последнем случае две книги “Введение в Паскаль” надо как-то разделить. Из данной информации нельзя извлечь правильный ответ. Поэтому со спецификациями надо быть осторожнее.

Элементами множества могут быть опять же множества:

А={1, {2,3}} — множество, состоящее из двух элементов, а множество В={1,2,3} — из трех. C={{3,5}, {5,7}, {7,9}} — оно состоит из трех элементов. D={3, 5, 7, 9} — из четырех. Конечно, С_D и A_B.

Задача 1: Описать словами рекурсивно заданное множество

X={x|x_Z)(x=1*(x-2) _X)}.

Определение 1: Два множества А и В называют равнымии пишут А=В, если А и В содержат одни и те же элементы.

Формально: два множества А и В равны, если "x (x_A + x_B).

 

Определение 2: Множество А называется подмножеством множества В, если каждый элемент множества А принадлежит множеству В ("х(х_А.х_В)).

Это записывают так: А_В, читаем: А содержится в В. Например: 3_{3,5,7}, {3}_{3,5,7}, аналогично {3,7}_{3,5,7}. А вот для множества {1;{2,3}} можно записать: {2,3}_{1;{2,3}}; 2_{1;{2,3}}. Чтобы заработал знак включения надо записать элемент {2,3} как множество, то есть {{2,3}}_{1;{2,3}}.

Другие примеры: 1. Q_R. 2. Z_Q, 3. N_R, 4. A={x|0_x<4 ) x_R}, B={y|1_y<3 ) y_R}, тогда B_A.

Определение 3: Множество А называется собственным подмножествоммножества В, если А_В и А_В. В случае, если надо подчеркнуть, что А_В или А=В будем писать А_ В.

Например, можно записать А_А, на самом деле будем использовать символ _,то есть А_А — почему?



Задача 2: Доказать, что если А_В и В_С, то А_С.

По определению подмножества, если А_В и В_А, то А=В (объясните, почему ).

Таким образом, чтобы доказать равенство двух множеств А и В надо доказать, что 1) А_В и 2) В_А. Фактически это означает, что любой элемент множества А является элементом множества В и любой элемент множества В является элементом множества А, что соответствует определению равенства двух множеств.

И в заключение введем еще два важных понятия.

Определение 4: Множество, не содержащее ни одного элемента, называется пустым множеством. Пустое множество обозначается символом Æ.

Формализуя: множество А пусто, если "x (x_A)— истинно.

Утверждение 1: Пустое множество единственно.

Доказательство:

Пусть C и D— пустые множества, тогда высказывание "x (x_С+x_D) истинно, поскольку x_С и x_D оба ложны. А по определению 1 это и означает, что С = D. Что и требовалось доказать.

Утверждение 2: Пустое множество является подмножеством любого множества.

Доказательство:

Действительно, для каждого x импликация x__.x_A истинна, так как посылка x__ ложна. Что и требовалось доказать.

Определение 5: Множество всех подмножеств множества X назовем степенью множества Хи будем обозначать Р(X).

Например, если X={1,2,3}, то P(X)={ _, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, X}.


mylektsii.ru - Мои Лекции - 2015-2017 год. (0.007 сек.)Пожаловаться на материал