67593

Отношения и функции/ Произведение множеств

Лекция

Математика и математический анализ

Две пары считаются равными тогда и только тогда, когда x=u и y=v. Определение. Бинарным или двуместным отношением называют множество упорядоченных пар. Элементы x и y называют координатами или компонентами отношения.

Русский

2014-09-23

116.5 KB

1 чел.

Лекция №2  

Отношения и функции

Определение. Упорядоченной парой <x,y> называется совокупность, состоящая из двух элементов x и y, расположенных в определенном порядке.

Определение. Две пары <x, y> <u, v> считаются равными тогда и только тогда, когда x=u и y=v.

Определение. Бинарным или двуместным отношением  называют множество упорядоченных пар. Элементы x и y называют координатами или компонентами отношения .

Записи <x, y> и  xy  означают, что пара <x, y> принадлежит бинарному отношению .

Определение. Областью определения бинарного отношения  называют множество D={x | существует такое y, что  x  y}. Областью значений  называют множество R={y | существует такое  x, что x  y}.||

Примеры.

1. Множество {<1,2>,<2,4><3,3>,<2,1>} – бинарное отношение.

D={1,2,3}, R={2,4,3,1}={1,2,3,4}.

2. {<x, y> | x, y – действительные числа и x=y} - отношение равенства на множестве R действительных чисел (специальное обозначение «=»). D={x | xR}, R={y | yR}.

3. {<x, y> | для целых чисел x и y найдется положительное число z такое, что x+z=y} – отношение «меньше чем» на множестве целых чисел (специальное обозначение «<»). D и R - множества целых чисел.

Определение. Упорядоченным набором длины n или n-кой элементов называется последовательность, состоящая из n элементов x1, x2, x3,…, xn, расположенных в определенном порядке и обозначается <x1, x2, x3,…, xn>.

Определение. n-нарным отношением называют множество упорядоченных наборов длины n.

Произведение множеств

Определение. Пусть даны n множеств A1, A2,…, An. Множество всех наборов <x1, x2,…, xn> таких, что x1A1,…, xnAn называют прямым произведением A1, A2,…, An и обозначают A1A2An или .

Произведение одинаковых множеств обозначается An.

При n=2   XY={<x, y> | xX, yY}.

Каждое бинарное отношение есть подмножество прямого произведения, так что DX и RY. Если X=Y то говорят, что есть отношение на множестве X.

Примеры

1. Пусть X={0,1}, Y={x,y}. Тогда

XY={<0,x>, <0,y>, <1,x>, <1,y>};

YX={<x,0 >, <x,1>, <y,0>, <y,1>}.

2. X={1,2,3}, Y={0,1}.

XY={<1,0>,<1,1>,<2,0>,<2,1>,<3,0>,<3,1>};

YX={<0,1>,<0,2>,<0,3>,<1,1>,<1,2>,<1,3>}.

(Отметим, что XY  YX.)

К отношению «=» принадлежит одна пара <1,1>.

К отношению «<» в множестве YX принадлежат все пары, кроме <1,1>. В множестве XY таких пар нет.

3. RR - плоскость.

4. X = {x | x  [0,1]}

Y = {y | y  [1,2]}

XY = {<x, y> | x  [0,1], y  [1,2]} – множество точек квадрата:

           

Определение. Обратным отношением для ={<x,y> | <x,y>} называют отношение -1={<y,x> | <x,y>}.

Определение. Композицией отношений 1 и 2 называют отношение 21={<x,y> |  z такое, что <x, z>1 и <z, y>2}.

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

  1.  ;

2) .

Доказательство п. 2)

<y,x>    <x,y>21;

 z : <x,z>1 и <z,y>2

 z : <z,x>1-1 и <y,z>2-1 

 z : <y,z>2-1 и <z,x>1-1 

<y,x>.

Сравнивая с исходным соотношением убеждаемся в справедливости равенства 2).

Пример: система линейных алгебраических уравнений AB, где A и B - матрицы. Операция умножения матрицы на вектор устанавливает соответствие каждому вектору-операнду  результата операции . Это соответствие есть отношение .

С одной стороны

.

С другой стороны

; .

Тем самым, .

Функции

Определение. Бинарное отношение f называется функцией, если из <x,y>f и <x,z>f следует, что y=z. (Функция является однозначной).

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

Если Df =X и Rf Y, то говорят, что f осуществляет отображение множества X на множество Y. Обозначения:

f:XY или .

<x,y>f    y=f(x);  y – образ, x – прообраз элемента y.

Примеры

{<1,2>, <2,3>,< >} – функция;

{<1,2>,<1,3>,<2,4>} - не функция (1 отображается сразу на два элемента);

{<x, x2+2x+1> | x R} - функция y=x2+2x+1

Определение. n-местной функцией называют отношение f, если f:XnY. Обозначение y=f(x1,…,xn).

Определение. Функция f:XY называется инъективной, если

x1, x2, y : y=f(x1), y=f(x2) x1=x2.  (То есть, одинаковые значения y могут соответствовать только одинаковым x).

Определение. Функция f:XY называется сюръективной, если

yY xX : y=f(x). (То есть, каждому значению y соответствует некоторое x).

Определение. Функция f называется биективной, если f одновременно сюрьективна и инъективна.

Говорят, что биективная функция f осуществляет взаимно однозначное отображение множества X на множество Y.

Примеры

f(x)=ex - инъективна, но не сюръективна при x  R;

f(x)=x3-x - сюръективна, но не инъективна;

f(x)=2x+1, f(x)=x3+x – биективна.

Утверждение. Композиция двух функций есть функция.

Доказательство. Допустим, композиции gf принадлежат две пары:

.

Поскольку f – функция, то u=v. Поскольку g – функция и u=v, то y=z, т.е. gof – функция.

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

Определение. Тождественным отображением множества X в себя называется отображение 

ex: XX такое, что xX ex(x)=x. Тогда fex=f, eyf=f.

Утверждение. Отображение f:XY имеет обратное отображение f1:YX тогда и только тогда, когда f – биекция.

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

Пусть f – биекция. Поскольку f – сюръективна, то отношение f-1 определено на множестве Y (каждому y соответствует определенное x).

В связи с инъективностью функции f обратное отношение f-1 является функцией (так как функция – однозначна, а инъективность означает невозможность соответствия различных x одному y). Прямое утверждение доказано.

Пусть теперь отображение f имеет обратное – f-1, определенное на множестве Y со значениями во множестве X. Тогда f сюръективно.

Но f также инъективно, так как f-1 – функция.

Утверждение доказано.

Замечание. Для того, чтобы обратное отношение f-1 было функцией на множестве значений Rf функции f, достаточно, чтобы функция f была инъективной. Тогда для инъективных функций выполняются следующие свойства бинарных отношений

1) (f)=f;                   2) (gf) =fg.

Свойства биективных функций

3) ff=ex;                  4) ff=ey.


 

А также другие работы, которые могут Вас заинтересовать

44949. Работа с EEPROM памятью данных 61.93 KB
  Поставим перед собой достаточно простую и конкретную задачу (что-то типа задания на первоначальную разработку). Допустим, что в ходе исполнения программы нужно изменить (модифицировать) содержимое пяти ячеек EEPROM памяти, начиная с адреса 7. Для простоты модификации (и для обеспечения наглядности наблюдения за происходящими в EEPROM памяти изменениями) к первому числу (по адресу 7) необходимо добавить 1...
44950. Однокристальные микроконтроллеры серии PIC 231 KB
  Микроконтроллеры семейств PIC (Peripheral Interface Controller) компании Microchip, обладающие особой популярностью, построены на основе передовых технологий микроконтроллеров. Им свойственны следующие особенности: электрически программируемые пользователем ППЗУ, минимальное энергопотребление, высокая производительность, хорошо развитая RISC-архитектура
44952. Автоколебательный мультивибратор 33.87 KB
  Проанализируем нашу программу, реализующую функцию автоколебательного мультивибратора, с одним выходом. Форма сигнала меандр (скважность, т.е. отношение периода к длительности импульса – 2). Под этот выход можно назначить любой из выводов порта А или В...
44953. Устройство формирования сигнала тонального вызова 87.52 KB
  Полупериоды формируем используя закольцовку рабочей точки программы в подпрограммах задержки по аналогии с программой Multi. К моменту начала составления текста программы желательно определиться с как можно большим количеством исходных данных. Так как программа должна исполняться непрерывно то в случае нахождения устройства в режиме ожидания включения на передачу рабочая точка программы должна закольцеваться до последующего нажатия на кнопку в какой-нибудь подпрограмме. Часто такого рода закольцовки осуществляют в...
44954. Сканирование с прерыванием 110.21 KB
  Определимся с терминологией применяемой при описании программы работы устройства. Для удобства объяснения и восприятия целесообразно разделить рабочую часть программы на две части. Условимся называть группу команд в которой осуществляется сканирование каналов на наличие сигнала прерывания âосновным теломâ программы а часть которая отрабатывается после ухода в прерывание как подпрограмму прерывания. Следовательно речь идет о необходимости âуходаâ рабочей точки программы на время наличия сигнала прерывания в подпрограмму...
44956. Индивидуальные и общественные потребности 35 KB
  Индивидуальные и общественные потребности Общество состоит из индивидов имеющих свои биологические особенности состояние здоровья особенности физиологических процессов в организме различия в строении и функционировании нервной системы которые определяют природные задатки человека. В простейшем случае общественные потребности представляют собой просто сумму потребностей индивидуальных. В более сложных случаях общественные потребности выходят за пределы индивидуальных и не сводятся к их сумме. Томас Гоббс считал что государство необходимо...
44957. Потребности в общении, самореализации, собственности и статусе. Смысл богатства 35.5 KB
  Любой человек будет испытывать дискомфорт когда блокирована его потребность в Познании например когда долгое время нет доступа к новой информации.Потребность в общении Человек испытывает потребность поделиться е другими своими мыслями и чувствами читать газеты книги и журналы смотреть кинофильмы в спектакли слушать музыку и т. Следует особо выделить такую духовную потребность как потребность в общении с другими людьми. Возникшая на заре человеческого общества потребность в общении породившая язык как средство общения была наряду с...