lectures.alex.balgavy.eu

Lecture notes from university.
git clone git://git.alex.balgavy.eu/lectures.alex.balgavy.eu.git
Log | Files | Refs | Submodules

index.md (963B)

      1 +++
      2 title = 'Relations'
      3 +++
      4 # Relations
      5 ## Cartesian product of sets
      6 
      7 A × B := {<a,b> : a ∈ A ∩ b ∈ B}
      8 
      9 A × A := A2
     10 
     11 #(A×B) = #A ⋅ #B
     12 
     13 **Binary relation:** relation of type A × B or A × A
     14 
     15 **Relation in set A:** relation of type A × A
     16 
     17 ## Infix notation:
     18 x R y — <x, y> ∈ R
     19 
     20 ## Visualisation
     21 directed graphs & matrix:
     22 
     23 ![screenshot.png](976a431a1cc75280f0fd2bca62a722da.png)
     24 
     25 Venn diagrams & matrix:
     26 
     27 ![screenshot.png](6e00283393a5ecb2b30c10ee0adc206a.png)
     28 
     29 ## Inverse of binary relation
     30 Inverse of R: R-1 := {<x,y> : <y,x> ∈ R}
     31 
     32 R ⊆ A × B => R-1 ⊆ B × A
     33 
     34 For Venn diagrams, you reverse the arrows.
     35 
     36 ## Composite relations
     37 R ∘ S := {<x,z> : x S y ∩ y R z for some y}
     38 
     39 ![screenshot.png](22dc5693b6ce96c68d71fc69d2f9d0d8.png)
     40 
     41 Composition is associative.
     42 
     43 Inverse: (R ∘ S)-1 = S-1 ∘ R-1
     44 
     45 ## Properties of relations
     46 ![screenshot.png](565aefaad582e4e41d23e0d0c072b464.png)
     47 ![screenshot.png](5dfd0a52a1c98207ba2d5b7cfdb10f97.png)