Композиция функциональных отношений. Пример.

опр: Пусть , где , тогда функция y ставящая в соответствие каждому x из множества X элементов , ставится элемент y из множества Y называется сложной функцией или композицией функции, или суперпозицией и обозначается .

X Y

X E(f₁)

Пример:

Свойства сложной функции:

1. – не коммутативность

2. 

Понятие обратной функции.

Функция называется обратной функции , если .

21. Виды функциональных отношений.

    1. Понятие инъекции.

    2. Понятие сюрьекции.

    3. Понятие биекции. Примеры.

Понятие инъекции

опр: Функция называется взаимооднозначным отображением X в Y или инъективным отношением или просто инъекцией, если

, т.е. неравные элементы имеют неравные образы.

Определение можно сформулировать иначе:

– инъекция, если .

Е сли множества X и Y конечны, то понятие инъекции легко рассмотреть используя диаграммы Эйлера-Венна:

1. X Y 2) X Y

• * * *

• *

* * * * *

• *

* *

не инъекция инъекция

Понятие сюрьекции

опр: Функция называется отображением X на Y или сюрьективным отношением или сюрьекцией, если:

т.е. для каждого элемента из Y найдется прообраз , т.е. E(f)=Y

Если X и Y конечны, то можно изобразить граф сюрьективного и не сюрьективного отношения.

1. X Y 2) X Y

• * * *

* *

• * * *

• * * *

Должны быть заполнены все Y.

опр: Функция называется взаимно однозначным соответствием X на Y или биективным отношением, или биекцией, если f одновременно инъективно и сурьективно.

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

21. Принцип Дирихле

    1. Понятие функционального отношения.

    2. Формулировка принципа Дирихле.

    3. Пример использования принципа Дирихле для решения задач.

Бинарное отношение φ, заданное на множествах X и Y называется отображением X в Y или функциональным отношением, или функцией, если выполняются условия:

, т.е. каждому x ставится в соответствие, при функциональном отношении единственное y.

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

Принцип Дирихле: Если , то найдется по крайней мере одно значение функции f встречающиеся более одного раза, т.е.

В хвойном лесу растут 800000 елей. На каждой ели - не более 500000 иголок. Доказать, что существуют хотя бы две ели с одинаковым числом иголок. Решение. Предположим противное, то есть, предположим, что в этом лесу не существуют две ели с одинаковым числом иголок. Тогда существует не более одной ели (одна ель или ни одной), имеющей одну иголку. Аналогичным образом, существует не более одной ели с двумя иголками и т.д., не более одной ели с 499999 иголками, не более одной ели с 500000 иголками. Таким образом, не более 500000 елей обладают числом иголок от 1 до 500000. Поскольку всего растут 800000 елей, и каждая ель имеет не долее 500000 иголок, следует, что найдутся хотя бы две ели с одинаковым числом иголок.

В зале находятся n человек (n ≥ 2). Доказать, что среди них найдутся два человека с одинаковым числом знакомых (предполагается, что если человек A является знакомым человека B, то и B является знакомым A; никто не считается своим собственным знакомым). Рещение. Обозначим через m количество человек, которые имеют хотя бы одно знакомство в зале (это и будут "предметы"). Каждый из этих m человек может иметь 1,2,...,m-1 знакомых ("коробки" - число знакомых). Согластно принципу Дирихле, сущетсвуют два человека с одинаковым числом знакомых. При решении некоторых задач полезно применять обобщенный принцип Дирихле. Если pn+1 предметов поместить в n коробок, тогда хотя бы одна коробка будет содержать по крайней мере p+1 предметов.

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

    1. Антиномии наивной теории множеств.

    2. Перечень существующих аксиоматик теории множеств.

27.1 Антиномии наивной теории множеств

1. Аксиома объемности. Если два множества имеют одни и те же элементы, они тождественны.

A, B: A=B  c, cA cB.

2. Аксиома пустого множества. Существует пустое множество , которое не содержит элементов.

: a, a.

3. Аксиома пары. Для любых множеств A и B существует множество C такое, что A и B являются его единственными элементами. Множество C обозначается {A, B} и называется неупорядоченной парой A и B. Если A = B, то C состоит из одного элемента.

A, B, C: D, DC(D=A  D=B).

4. Аксиома объединения. Для любого множества A существует множество B=a₁a₂…a_n – объединение всех элементов множества A, состоящее из тех и только тех элементов, которые содержатся в элементах множества А.

A, B: C, CB  D, (CD  DA).

5. Аксиома бесконечности. Существует множество, которое содержит ∅ в качестве своего элемента, и такое, что если а есть элемент этого множества, тогда последовательность a{a} есть также элемент этого множества.

:   x, x  {x,{x}}.

6. Аксиома регулярности. Если A – непустое множество, тогда имеется подмножество В множества A, такое, что не имеется множеств, которые принадлежат обоим множествам А и В.

7. Аксиома выделения. Любому множеству A и свойству  отвечает множество B, элементами которого являются те и только те элементы A, которые обладают свойством .

A B: c, cB  (cA  (c)).

8. Аксиома основания. Каждое непустое множество S содержит подмножество A такое, что что SA=.

S, S  A, AS  AS=.

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

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

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

    1. Понятие кардинального числа. Мощность конечных и бесконечных множеств.

    2. Равномощные множества.