Дискретная математика. Множества. Отображения. Отношения

81 Доказательство . Докажем равенства (8.2) – (8.8). Пустое отношение ∅ не содержит ни одной пары , а универ - сальное отношение A B × содержит всевозможные пары , поэтому равенства (8.2) непосредственно следуют из определения матрицы отношения . Равенства (8.3) – (8.5) доказываются соответственно сле - дующими логическими цепочками : [ ] 1 ( ) (( ) ) (( ) ) ( 1) ( 1) ( 1) ([ ] [ ]) 1; ij i j i j i j ij ij ij ij ij Q R a b Q R a b Q a b R q r q r Q R ∪ = ↔ ∈ ∪ ↔ ∈ ∨ ∨ ∈ ↔ = ∨ = ↔ ∨ = ↔ ∨ = [ ] 1 ( ) (( ) ) & &(( ) ) ( 1) & ( 1) ( & 1) ([ ]&[ ]) 1; ij i j i j i j ij ij ij ij ij Q R a b Q R a b Q a b R q r q r Q R ∩ = ↔ ∈ ∩ ↔ ∈ ∈ ↔ = = ↔ = ↔ = [ ] 1 ( ) ( ) 0 1 1 1 (1 [ ]) 1. ij i j i j ij ij ij n m ij Q a b Q a b Q q q q Q × = ↔ ∈ ↔ ∉ ↔ ↔ = ↔¬ = ↔ − = ↔ − = Равенство (8.6) получается из (8.4), (8.5) с учетом того , что \ Q R Q R = ∩ . Докажем равенство (8.7): 1 1 [ ] 1 ( ) ( ) 1 [ ] 1 ([ ] ) 1. ij i j j i T ji ji ij Q b a Q a b Q q Q Q − − = ↔ ∈ ↔ ∈ ↔ ↔ = ↔ = ↔ = Равенство (8.8) получается из определений отношения тож - дества и единичной матрицы : [ ] 1 ( , ) . A ij i j A i j a a a a i j θ = ↔ ∈θ ↔ = ↔ = Это значит , что [ ] A ij ij θ = δ , т . е . [ ] A n E θ = . Теорема 8.2. Пусть , Q R A B ⊂ × . Тогда [ ] [ ] Q R Q R ⊂ ↔ ≤ . (8.9) Здесь неравенство матриц понимается как поэлементное : [ ] [ ] Q R ≤ ↔ , ( ) ij ij i j q r ↔∀ ≤ .