Лекции по линейной алгебре (стр. 3 )

2. Естественным образом для соответствий S1 и S2 определяются S1∩S2  и  S1U S2 – как пересечение и объединение подмножеств. Как и для любых подмножеств определяется понятие включения соответствий S1 ⊆ S2.  Так  S1 ⊆ S2  ⇔

из  a S1b ⇒ a S2b.

3. Для соответствий S1 ⊆ A×B и S2 ⊆ B×C определим композицию соответствий S1*S2 ⊆ A×С. Будем считать, что для элементов  a∈ A, с∈ С  по определению  a S1*S2 с ⇔ ∃ b∈ B такой, что  a S1 b  и  b S2 с.

4. Для соответствия S ⊆ A×B определим соответствие

S -1 ⊆ B×A так: по определению bS -1a ⇔ a S b.

5. Пусть по определению соответствие  ΔA⊆ A×A,

ΔA={(a, a), a∈ A}.

6. Соответствие F из множества A в  множество B называется функцией,  определенной на A, со значениями в B (или отображением из A в B), если ∀ a∈ A  ∃!  b∈ B такой, что aFb. В этом случае будем писать также  aF = b или, более привычно, Fa = b. В этом определении функция отождествляется со своим графиком. В наших обозначениях  aF1*F2 с  можно записать в виде  с = (aF1)F2 . Композиция F2F1 функций означает по определению, что (F2F1 )(a)= F2(F1 (a)). Таким образом,  F2F1 = F1*F2 . 

7. Для отображения F из A в B образом подмножества A1⊆ A

называется подмножество F(A1)= {F(a)| a∈ A1} ⊆ B, а прообразом подмножества B1 ⊆ B называется подмножество

F -1(B1)= { a∈ A | F(a) ∈ B1 } ⊆ A.

8. Отображение F из A в  B называется инъекцией, если из

a1 ≠ a2 ⇒ Fa1 ≠ Fa2.

9. Отображение F из A в  B называется  сюръекцией, если

∀ b∈ B  ∃ a∈ A  такой, что Fa = b.

10. Отображение F из A в  B называется  биекцией или взаимнооднозначным отображением, если F – инъекция и сюръекция одновременно.

11. Биекция конечного (а иногда и бесконечного) множества называется подстановкой.

12. Бинарным отношением на множестве Х называется подмножество R ⊆ X×X. Тот факт, что элементы x, y ∈ X находятся в отношении R, мы будем записывать в виде (x, y) ∈ R или в виде xRy.

  Упражнения.

1. Проверить, что ΔA*S = S,  S*ΔB =S  ∀S ⊆ A×B.

2. Проверить, что

  (S1*S2)*S3 = S1*(S2*S3)  ∀ S1 ⊆ A×B, S2 ⊆ B×C, S3 ⊆ C×D.

3. Проверить, что (S -1) -1  = S  ∀ S ⊆ A×B.

4. Проверить, что (S1*S2) -1  =  S2-1 * S1-1 ∀ S1 ⊆ A×B, S2 ⊆ B×C.

5. Доказать, что если отображения F1 из A в B и F2 из B в C являются инъекциями, то F2F1 – инъекция.

6. Доказать, что если отображения F1 из A в B и F2 из B в C являются сюръекциями, то F2F1 – сюръекция.

7. Доказать, что если отображения F1 из A в B и F2 из B в C являются биекциями, то F2F1 – биекция.

8. Доказать, что для отображения F из A в B соответствие F -1 будет отображением из B в A ⇔ F – биекция. В этом случае  F -1 - также биекция, и F* F -1 =ΔA,  F -1* F =ΔB.

9. Доказать, что для отображения F из A в B

уравнение Fx= b  имеет ≤ 1 решения ∀b ⇔ F – инъекция,

уравнение Fx= b  имеет  ≥1 решения ∀b ⇔ F – сюръекция,

уравнение Fx=b имеет ровно одно решение ∀b ⇔ F – биекция.

10. Доказать, что отображение F из A в B является инъекцией ⇔ F* F -1 =ΔA.

11. Доказать, что отображение F из A в B является сюръекцией ⇔ F -1* F =ΔB.

  Пусть S(X) – множество биекций множества Х. Тогда

I. ∀ f, g∈ S(X)  f g ∈ S(X)  (из упр. 5),

II. 1. ∀ f, g, h∈ S(X)  (f g) h =  f (gh)  (из упр. 2),

  2.  ∃ ΔX∈ S(X) (очевидно, ΔX – биекция из Х  в Х  и ΔX(х)=х ∀ х∈ X)  и ∀ f∈ S(X)  f ΔX = ΔX f = f  (из упр.1). Биекция  ΔX  обозначается ещё  idX  или  id.

  3. ∀ f∈ S(X)  ∃ f -1∈ S(X) и  f -1f = f f -1= ΔX  (из упр.6).

  Далее множества с такими свойствами мы будем называть группами. Таким образом,  S(X) - группа.

  3.2. Подстановки.

  Пусть Х – конечное множество, Х = {х1, х2 ,…, хn }.  Группу подстановок S(X) в этом случае мы будем обозначать Sn. Подстановку σ множества Х можно записывать в виде таблицы σ = , где в нижней строке стоят каким-то образом переставленные элементы множества Х. Такая таблица означает, что σ(х1)= , σ(х2)= , σ(х3)=…

Так как σ - инъекция, то все элементы нижней строки различные. Так как  σ - сюръекция, то в нижней строке присутствуют все элементы множества Х. То есть, нижняя строка – это перестановка множества Х. Таким образом, различных подстановок существует ровно столько, сколько имеется различных перестановок множества Х, то есть n!, и, значит, группа Sn подстановок множества из п элементов состоит из  n! элементов.

  Упражнение. Доказать, что для конечного множества Х

из инъективности σ  следует её сюръективность, а из сюръективности  - инъективность.

  Чаще всего мы будем считать, что  Х = {1, 2, 3, …, n }. В этом случае подстановки мы будем записывать в виде

σ =, где  i1, i2 ,…, in  - перестановка чисел 1, 2, 3, …, п.

  Для композиции подстановок σ1σ2  вначале выполняется подстановка σ2, а затем  σ1, а для композиции  σ1*σ2  - вначале σ1, а затем  σ2 .

  Пусть σ k =σ σ …σ - произведение  k  множителей. Так как  Х - конечное множество, то ∀ x∈ Х  ∀σ ∈ Sn  {σ kx | k∈ N} – конечное подмножество в  Х, то есть ∃ k≠ m такие, что  σ k x = σ m x. Тогда, если  k> m, то, очевидно,

σ k-m x = x. Пусть s – наименьшее  натуральное число такое, что σ sx = x. Тогда подмножество {x, σ x, σ 2x, σ 3x,…,σ s-1x} будем называть циклом, порожденным элементом х, и обозначать O(х). Очевидно, все элементы в O(х) – различны, то есть O(х) состоит из s элементов. Будем считать, что по определению σ 0 = id, σ0x= х.

  Упражнения.

1. Проверить, что, σ s+1x =σ x, σ s+2x =σ 2x, σ -1x = σ s-1x, …, σ(О(x))=О(х), σ k(О(х)) = О(x), О(σx) =О(х), О(σ kх) = О(x), О(х) = {σ kx| k =0,1, 2,…, s-1 } =  {σ kx| k ∈ Z }.

2. Проверить, что циклы разных элементов либо не пересекаются, либо совпадают.

  Таким образом, множество Х разбивается в объединение непересекающихся циклов.

  Пусть х = a1, σ x = a2 , σ 2x = a3 , σ 3x = a4 ,…, σ s-1x = as, и соответственно цикл О(х) ={a1, a2 ,.., as}. Тогда σ(О(x))= О(х), и σ на О(x) является биекцией, которую можно записать в виде таблицы или в виде таблицы с одной строкой: (a1, a2, a3,…, as ). Запись σ в виде такой строки означает, что σ a1= a2, σ a2= a3 ,…,σ as-1= as, σ as= a1 . Записывая подстановку на каждом цикле в виде одной строки, получим циклическую запись подстановки. Так, например, подстановка

σ = в циклической записи имеет вид  σ =(1, 4, 2, 5)(3)(6, 8, 7).

  Определение. Транспозицией будем называть подстановку tij  такую, что  tij (i)= j, tij (j) = i, tij (k) = k при k ≠ i, k≠j.