Отношения и отображения в теории множеств

Размещено на http://www.allbest.ru/

Лекция 2.

Отношения и отображения

План

1. Мощность множества

2. Бинарные отношения

3. Способы задания отношений

4. Свойства бинарных отношений

5. Отношение эквивалентности. Отношение частичного порядка

6. Отображения (функции)

1. Мощность множества

Альберт Эйнштейн как-то говорил: «Не все, что можно сосчитать, сосчитано, и не все, что сосчитано, можно сосчитать». Хотя это высказывание не очень воодушевляет, попытаемся заняться подсчетами.

Говорят, что между множествами A и B установлено взаимно однозначное соответствие, если каждому элементу множества A соответствует один и только один элемент множества B и каждому элементу множества B соответствует некоторый элемент множества A. В этом случае говорят также, что множества A и B изоморфны и используют обозначение AB.

Определение 2.2. Два множества A и B называются эквивалентными, или равномощными, если между этими множествами может быть установлено взаимно однозначное соответствие. В этом случае пишут: AB, или A=B, и говорят, что множества A и B имеют равные мощности.

Пример .. 1) Множество десятичных цифр равномощно множеству пальцев на руках человека.

2) Множество четных натуральных чисел (2N) равномощно множеству всех натуральных чисел (N).

Определение 2.3. Множество A называется конечным, если оно эквивалентно J_n при некотором n, где J_n=1, 2, …, n - множество n первых натуральных чисел.

Определение 2.4. Мощностью конечного множества A, которое содержит k элементов, называется число его элементов. Она обозначается A=k. Пустое множество считается конечным с числом элементов равным нулю, т.е. =0.

Таким образом, если множество A конечно, т.е. A=k, то элементы A всегда можно перенумеровать, то есть поставить в соответствие элементам номера из отрезка натурального ряда 1..k с помощью некоторой процедуры. Наличие такое процедуры подразумевается, когда употребляется запись A=a₁, a₂, …, a_k.

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

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

Множество A называется несчетным, если его мощность больше мощности множества N. В таком случае множество A называется континуальным или континуумом. Мощность континуума обозначается .

Теорема 2.1. Множество всех действительных чисел имеет мощность континуума, т.е. R=C.

2. Бинарные отношения

Когда говорят о родстве двух людей, например, Сергей и Анна, то подразумевают, что есть некая семья, к членам которой они относятся. Упорядоченная пара (Сергей, Анна) отличается от других упорядоченных пар людей тем, что между Сергеем и Анной есть некое родство (кузина, отец и т.д.).

В математике среди всех упорядоченных пар прямого произведения двух множеств A и B (AB) тоже выделяются «особые» пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других. В качестве примера рассмотрим множество S студентов какого-нибудь университета и множество K читаемых там курсов. В прямом произведении SK можно выделить большое подмножество упорядоченных пар (s, k), обладающих свойством: студент s слушает курс k. Построенное подмножество отражает отношение «… слушает …», естественно возникающее между множествами студентов и курсов.

Для строгого математического описания любых связей между элементами двух множеств введем понятие бинарного отношения.

Определение. Бинарным (или двухместным) отношением между множествами A и B называется произвольное подмножество AB, т.е.

.

В частности, если A=B (то есть A²), то говорят, что есть отношение на множестве A.

Элементы a и b называются компонентами (или координатами) отношения .

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

Определение. Областью определения бинарного отношения называется множество D=a b, что ab (левая часть). Областью значений бинарного отношения называется множество R=b a, что ab (правая часть).

Пример 1. Пусть даны два множества A=1; 3; 5; 7 и B=2; 4; 6. Отношение зададим следующим образом =(x; y)AB x+y=9. Это отношение будет состоять из следующих пар (3; 6), (5; 4) и (7; 2), которые можно записать в виде =(3; 6), (5; 4), (7;2). В данном примере D=3; 5; 7 и R= B=2; 4; 6.

Пример. Отношение равенства на множестве действительных чисел есть множество =(x; y) x и y - действительные числа и x равно y. Для этого отношения существует специальное обозначение «=». Область определения совпадает с областью значений и является множеством действительных чисел, D= R.

Пример. Пусть A - множество угроз на ИС, а B - множество элементов защиты. Тогда =(x; y)AB y - защита от x - отношение множеств A и B.

Если обратить внимание на пример 1., то можно заметить, что данное отношение было задано сначала в виде =(x; y)AB x+y=9, а потом записано в виде =(3; 6), (5;4), (7;2). Это говорит о том, что отношения на множествах (или одном множестве) можно задавать различными способами. Рассмотрим способы задания бинарных отношений.

3. Способы задания отношений

1) с помощью подходящего предиката;

2) множество упорядоченных пар;

3) в графической форме

4) в виде матрицы: пусть A=a₁, a₂, …, a_n и B=b₁, b₂, …, b_m, - отношение на AB. Матричным представлением называется матрица M=m_ij размера nm, определенная соотношениями

.

Матричное представление является представлением отношения в компьютере.

Введем обобщенное понятие отношения.

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

A₁…A_n=(a₁, …, a_n) a₁A₁ … a_nA_n

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

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

Далее мы будем рассматривать только двухместные (бинарные) отношения, при этом опуская слово «бинарные».

Определение. Пусть AB есть отношение на AB. Тогда отношение ^-1 называется обратным отношением к данному отношению на AB, которое определяется следующим образом:

^-1=(b, a) (a, b).

Определение. Пусть AB есть отношение на AB, а BC - отношение на BC. Композицией отношений и называется отношение AC,которое определяется следующим образом:

=?= (a, c) b B, что (a, b) и (b, c).

Теорема 2. Для любых бинарных отношений выполняются следующие свойства:

1) ;

2) ;

3) - ассоциативность композиции.

4. Свойства бинарных отношений

Рассмотрим специальные свойства бинарных отношений на множестве A.

Свойства бинарных отношений.

1. Отношение на AA называется рефлексивным, если (a,a) принадлежит для всех a из A.

2. Отношение называется антирефлексивным, если из (a,b) следует ab.

3. Отношение симметрично, если для a и b, принадлежащих A, из (a,b) следует, что (b,a).

4. Отношение называется антисимметричным, если для a и b из A, из принадлежности (a,b) и (b,a) отношению следует, что a=b.

5. Отношение транзитивно, если для a, b и c из A из того, что (a,b) и (b,c), следует, что (a,c).

Как по матрице представления определить свойства бинарного отношения

1. Рефлексивность: на главной диагонали стоят все единицы, звездочками обозначены нули или единицы.

.

2. Антирефлексивность: на главной диагонали все нули.

3. Симметричность: если .

4. Антисимметричность: все элементы вне главной диагонали равны нулю; на главной диагонали тоже могут быть нули.

.

Операция «» выполняется по следующему правилу: , где , .

5. Транзитивность: если . Операция «?» выполняется по обычному правилу умножения, при этом надо учитывать: .

5. Отношение эквивалентности. Отношение частичного порядка

Отношение эквивалентности является формализацией такой ситуации, когда говорят о сходстве (одинаковости) двух элементов множества.

Определение. Отношение на A есть отношение эквивалентности, если оно рефлексивно, симметрично и транзитивно. Отношение эквивалентности ab часто обозначается: a b.

Пример. Отношение равенства на множестве целых чисел есть отношение эквивалентности.

Пример. Отношение «одного роста» есть отношение эквивалентности на множестве людей X.

Пример. Пусть Z - множество целых чисел. Назовем два числа x и y из Z сравнимыми по модулю m (m) и запишем , если равны остатки этих чисел от деления их на m, т.е. разность (xy) делится на m.

Отношение «сравнимых по модулю m целых чисел» есть отношение эквивалентности на множестве целых числе . В самом деле:

это отношение рефлексивно, т.к. для x имеем xx=0, и, следовательно, оно делится на m;

это отношение симметрично, т.к. если (xy) делится на m, то и (yx) тоже делится на m;

это отношение транзитивно, т.к. если (xy) делится на m, то для некоторого целого t₁ имеем , а если (yz) делится на m, то для некоторого целого t₂ имеем , отсюда , т.е. (xz) делится на m.

Определение. Отношение на A есть отношение частичного порядка, если оно рефлексивно, антисимметрично и транзитивно и обозначается символом .

Частичный порядок важен в тех ситуациях, когда мы хотим как-то охарактеризовать старшинство. Иными словами, решить при каких условиях считать, что один элемент множества превосходит другой.

Пример. Отношение xy на множестве действительных чисел есть отношение частичного порядка.

Пример. Во множестве подмножеств некоторого универсального множества U отношение AB есть отношение частичного порядка.

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

Формулировка задачи: пусть имеется совокупность объектов A и требуется сравнить их по предпочтительности, т.е. задать отношение предпочтения на множестве A и определить наилучшие объекты.

Отношение предпочтения P, которое можно определить как «aPb, a, bA объект a не менее предпочтителен, чем объект b» является по смыслу рефлексивным и антисимметричным (каждый объект не хуже самого себя, и, если объект a не хуже b и b не хуже a, то они одинаковы по предпочтительности). Естественно считать, что отношение P транзитивно (хотя в случае, когда, например, предпочтения обсуждаются группой лиц с противоположными интересами, это свойство может быть нарушено), т.е. P - отношение частичного порядка.

Один из возможных способов решения задачи сравнения объектов по предпочтительности - ранжирование, т.е. упорядочение объектов в соответствии с убыванием их предпочтительности или равноценности. В результате ранжирования мы выделяем «наилучшие» или «наихудшие» с точки зрения отношения предпочтения объекты.

6. Отображения (функции)

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

Определение. Отношение f на AB называется отображением (функцией) из A в B, если для каждого xA существует один и только один yB. множество бинарный отношение эквивалентность

f: AB или y=f(x)

Множество A называется областью определения. Множество B - областью значений.

Если y=f(x), то x называют аргументом, а y - значением функции.

Пусть f: AB, тогда

множество определения функции:

;

множество значений функции:

.

Множество определения функции является подмножеством области определения, т.е. Dom f A, а множество значений функции является подмножеством области значений функции, т.е. Im f B. Если , то функция называется тотальной, а если частичной функцией. Так диаграмма Венна служит удобной иллюстрацией функции, определенной на множестве A со значениями в множестве B.

Размещено на http://www.allbest.ru/

Способы задания функции:

1) Словесный.

2) Аналитический.

3) С помощью графика, рисунка.

4) С помощью таблиц.

Определение. Если MA, то множество f(M)=y f(x)=y для некоторого x из M называется образом множества M.

Если KB, то множество f ^-1(K)=x f(x)K называется прообразом множества K.

Определение Функция называется функцией n аргументов, или n-местной функцией. Такая функция отображает кортеж в элемент bB, .

Свойства отображений (функций).

1) Отображение f: AB называется инъективным, если оно различные элементы из A отображает в различные элементы из B: .

Это свойство можно показать с помощью диаграмм Венна.

Размещено на http://www.allbest.ru/

2) Отображение f: AB называется сюръективным или отображением на все мно-жество B, если в каждый элемент множества B отображается хотя бы один элемент из A: .

Это свойство тоже можно показать с помощью диаграмм Венна.

Размещено на http://www.allbest.ru/

3) Отображение f: AB, которое одновременно инъективно и сюръективно, называется биективным или взаимно однозначным отображением множества A на множество B.

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

Решение. Функция f не является инъективной, т.к. f (2)=f (2), но 2 2.

Функция f не является также и сюръективной, поскольку не существует такого действительного числа x, для которого f (x)= 1.

Определение. Пусть f биективное отображение множества A в множество B. Если поставить в соответствие каждому элементу из B связанный с ним элемент из A, то такое соответствие является отображением B в A. Это отображение обозначается и называется отображением, обратным отображению f.

Обратное отображение обладает некоторыми свойствами, которые сформулируем в следующей теореме.

Теорема 3. Если f: AB - биекция, то

1) для любого y из B;

2) для любого x из A.

Доказательство. 1) Пусть yB и. Тогда f(x)=y. Но поскольку

, то .

2) Аналогично доказывается, что для любого x из A.

Определение. Композицией (суперпозицией, произведением) отображений f: AB и g: BC называется отображение h: , которое записывается h=g f.

Такой способ записи суперпозиции функций объясняется тем, что обозначение функции принято писать слева от списка аргументов:

.

Размещено на Allbest.ru

...