ordm; Отображения

1. Отображением f множества A в множество B называется правило, по которому каждому элементу a∈ A соответствует некоторый элемент b=f(a)∈ B.

Запись f: A→ B означает, что f является отображением множества A в множество B. При этом множество A называется областью определения отображения f.

Запись f: a↦ b означает, что f отображает элемент a в элемент b, т.е. что b=f(a). При этом b называется образом элемента a, а a — прообразом элемента b.

Множество всех a∈ A, для которых f(a)=b∈ B — фиксированный элемент, называется полным прообразом элемента b при отображении f и обозначается f-1(b)

f-1(b)={a∈ A|f(a)=b}.

Множество тех b∈ B, для которых существует прообраз в множестве A, называется областью значений отображения f и обозначается f(A)

f(A)={b∈ B|∃ a∈ A: b=f(a)}.

Пример

Пусть A={-2, -1, 0, 1, 2}, B={0, 1, 2, 3, 4, 5}, а отображение f действует по правилу f(a)=a2.

Тогда элемент 1∈ B является образом элементов -1, 1∈ A, а элементы -2, 2∈ A являются прообразами элемента 4∈ B.

Полные прообразы элементов множества B:

f-1(0)={0},   f-1(1)={-1, 1},   f-1(2)=∅,   f-1(4)={-2, 2}.

Множество f(A)={0, 1, 4}⊂ B является областью значений отображения f.

Если A={a1, a2, …, an}, B={b1, b2, …, bm}, то любое отображение f: A→ B задается упорядоченным набором (bi1, bi2, …, bin), где bi1=f(a1), bi2=f(a2) и т.д. При этом порядок записи элементов множества A предполагается фиксированным.

Пример

Пусть A={" Иванов", " Петров", " Сидоров" } — множество студентов, B={2, 3, 4, 5} — множество оценок. Пусть f: A→ B ставит в соответствие каждому студенту его оценку по математике.

Тогда отображение f может быть задано, например, строкой (3, 4, 3). Это означает, что Иванов и Сидоров имеют по математике оценки 3, а Петров — оценку 4.

Множество всех отображений множества A в множество B обозначается F(A, B) или BA.

Пример

Пусть A={1, 2, 3}, B={0, 1}. Перечислим все отображения A в B.

Каждое такое отображение определяется упорядоченным набором (b1, b2, b3), где каждый элемент равен 0 или 1. Мы будем теперь записывать их в столбцы.

Теорема   (Число всех отображений)

|F(A, B)|=|B||A|

Доказательство   Скрыть

2. Отображение f: A→ B называется инъекцией, если различным элементам множества A соответствуют различные элементы множества B. Другими словами, из f(x)=f(y) следует x=y.

Если существует инъекция f: A→ B, то для каждого элемента множества A имеется соответствующий уникальный элемент множества B. Это означает, что |A|⩽ |B|.

Отображение f: A→ B называется сюръекцией, если каждый элемент множества B есть образ некоторого элемента множества A. Другими словами, областью значений отображения f является все множество B.

Если существует сюръекция f: A→ B, то множество B должно полностью покрываться элементами вида f(a). Значит в этом случае |A|⩾ |B|.

Пример

Пусть A — множество пользователей форума Факультета открытого образования, B — множество всех буквенно-цифровых последовательностей. Пусть f: A→ B ставит в соответствие каждому пользователю форума его логин.

Тогда отображение f является инъекцией, но не сюръекцией.

Пример

Пусть A={1, 2, 3, 4, 5, 6, 7, 8}, B={-1, 1}, а отображение f действует по правилу f(a)=(-1)a.

Тогда отображение f — сюръекция, но не инъекция.

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

Пример

Пусть A={-1, 0, 1}, B={1, 2, 3, 4}. Перечислим все инъекции A в B.

Пример

Пусть A={-2, -1, 1, 2}, B={1, 2, 3}. Перечислим все сюръекции A в B.

Число всех инъекций A→ B зависит только от |A|=n, |B|=m и называется числом размещений — обозначается Amn. Для этого числа имеется простая формула.

Теорема   (Число всех инъекций)

Пусть |A|=n, |B|=m. Тогда число всех инъекций A→ B:

Amn=m(m-1)…(m-(n-1)).

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

Для числа всех сюръекций такой простой формулы нет, но все же что-то сказать можно. Мы вернемся к этому вопросу чуть позже.

3. Отображение f: A→ B называется биекцией, если оно является одновременно инъекцией и сюръекцией. Из предыдущих рассуждений следует, что биекция возможна только при |A|=|B|.

Если f: A→ B — инъекция и |A|=|B|, то будет задействован каждый элемент множества B, поэтому f окажется биекцией.

Если f: A→ B — сюръекция и |A|=|B|, то каждый элемент множества B будет иметь вид f(a) при однозначно определенном a∈ A, поэтому f будет биекцией.

Теорема   (Число всех биекций)

Пусть |A|=|B|=n. Тогда число всех биекций A→ B:

n(n-1)…1=n!

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

Биекция множества в себя f: A→ A называется перестановкой.

Пример

Пусть A={1, 2, 3}. Перечислим все перестановки множества A.

Перестановка f1 называется тождественной.

4. Вернемся еще раз к числу инъекций. Пусть |A|=n, |B|=m. Каждая инъекция A→ B может быть представлена как биекция множества A в некоторое n-элементное подмножество S множества B. Поэтому

(Число всехинъекцийA→ B)=(ЧислобиекцийA→ S)⋅ (Число всевозможныхподмножествS)

То что мы вывели является комбинаторной интерпретацией равенства

m(m-1)…(m-(n-1))=n! ⋅ m(m-1)…(m-(n-1))n!
Amn=n! ⋅ Cmn.

Вернемся к вопросу о числе сюръекций A→ B. Если B={b1, b2, …, bm}, то каждая сюръекция f: A→ B определяет некоторое разбиение множества A на m непересекающихся подмножеств:

A=f-1(b1)∪ f-1(b2)∪ …∪ f-1(bm).

Обратно, каждому такому разбиению

A=A1∪ A2∪ …∪ Am

соответствует m-элементное множество

C={A1, A2, …, Am},

которое может быть биективно отображено в

B={b1, b2, …, bm}

m! способами. Каждая биекция

F: C→ B

однозначно определяет сюръекцию f: A→ B следующим образом:

f(a)=bi   ⇔   a∈ Ai.

Итак:

(Число всехсюръекцийA→ B)=(Число разбиенийCмножестваAнаmчастей)⋅ (Число всехбиекцийC→ B)

Теорема   (Число всех сюръекций)

Пусть |A|=n, |B|=m. Тогда число всех сюръекций A→ B выражается через число Стирлинга:

(Число всехсюръекцийA→ B)=S(n, m)⋅ m!.

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

5. Исследуем связь между декартовой степенью AN, множеством всех подмножеств (булеаном) 2A и множеством отображений BA.

Пусть A — произвольное множество, а B={1, 2, …, N}. Отображение f: B→ A определяет упорядоченный набор (a1, a2, …, aN)∈ AN. Обратно, каждый такой набор задает некоторое отображение f: B→ A. Нетрудно проверить, что соответствие между AB (отображениями) и AN (упорядоченными наборами) является биекцией.

Пусть A — произвольное множество, а B={0, 1}. Отображение f: A→ B определяет некоторое подмножество S множества A следующим образом. Если f(a)=1, то элемент a∈ A включается в подмножество S, в противном случае — нет. Таким образом, каждому отображению f ставится в соответствие некоторый элемент S∈ 2A. Обратно, каждый элемент S∈ 2A задает некоторое отображение f: A→ B. Можно проверить, что соответствие между BA (отображениями) и 2A (подмножествами множества A) является биекцией. То, что B — 2-элементное множество, оправдывает обозначение 2A.

Пример

Какое множество могло бы обозначаться как 3A?

Пусть B={1, 2, 3} — 3-элементное множество. Под 3A можно понимать множество всех отображений A→ B.

Пусть A — множество ковбоев, B={" хороший", " плохой", " злой" } — множество качеств. Каждому ковбою присваивается некоторое качество. Некоторые ковбои будут объявлены " хорошими", другие — " плохими", оставшиеся — " злыми". Тогда 3A — множество способов, которыми это можно сделать.