Exercise 3

We will now learn more about relations and do our first proof by cases.

R⁻¹ stands for the inverse of the relation R. That means if R[x,y], then (R⁻¹)[y,x]. The converse also holds, that means (R⁻¹)[x,y] implies R[y,x].

R ∪ S stands for the union of two relations R and S – that means it contains all tuples that R and S contained.

A relation is said to be symmetric if it always goes both ways: If R[x,y], then also R[y,x].

Try to complete the proof by inserting something for "{INSERT-SOLUTION-HERE}"!

Note that we do a case analysis in the proof: Since we do not know if R[x,y] or (R⁻¹)[x,y] holds, we proof both cases. Every proof of a case needs to be closed by "qed.".

Take care to always use parentheses around special notations: You need to write (R⁻¹)[x,y] instead of R⁻¹[x,y].

∈ ∩ ∪ ⊆ ᑦ -> ∘ ⁻¹ [ ] { }

Line , Col