Description

Fix your relations
Questions
1. 5 points Given Theorem 1 and Definition 1 below, prove Theorem 2.
Theorem 1. Let R be an equivalence relation on a set A. The following statements for elements a and b of A are equivalent.
(i)aRb (ii)[a] = [b] (iii)[a] ∩ [b] ̸= ∅
Definition 1. A partition of a set, A, is a set of non-empty subsets, Ai, of A, such that every element a in A is in exactly one of these subsets (i.e. A is a disjoint union of the subsets). [Wikipedia]
Theorem 2. Let R be an equivalence relation on a set S. Then the equivalence classes of R form a partition of S.
2. 5 points Prove the following theorem.
Theorem 3. Let R be an equivalence relation on a set A. The following statements for elements a and b of A are equivalent.
(i)aRb (ii)[a] = [b] (iii)[a] ∩ [b] ̸= ∅
3. 5 points Given non empty set S and a partition Ai of S. Prove that R = SAi(Ai×Ai) is an equivalence relation on S. Moreover the equivalence classes of R are exactly Ai.
4. 5 points Show that a finite nonempty poset has a maximal element.
5. 5 points The following is a summary of someone’s attempt to prove that exists only one unique God.
Find the error in the proof.
Proof: Assume there is more than one unique God.
Insert convincing argument to show that this leads to a contradiction.
Since having more than one unique God results in a contradiction, there exists only one unique God.

6. 5 points “Prove the least element is unique when it exists.”. State the error in the following proofs.
Proof 1: Assume that Least element exists and it is not unique. Let a be a least element and g be another least element and a ̸= g. Then by the definition of least element, g ≺ a. But we assumed that a is the least element. Therefore, this is a contradiction and hence we can say that, The least element is unique when it exists.
Proof 2: Let’s assume that there is more than one unique least element, with a and b being two distinct least elements. For the relation R to be antisymmetric, a must be equal to be (a = b), given that (a,b) ∈ R and (b,a) ∈ R. Since a and b are equal to each other, we can conclude that there is only one unique least element.
1
CS 113 Spring 201 Recitation: Relation Proofs Fix your relations

7. 5 points The relation R on a set A is transitive if and only if Rn ⊆ R for n = 1,2,3,…
8. 5 points Fix the problem in the proof. “Show that for a reflexive relation R, R−1 ⊆ R ◦ R−1”
Proof: By reflexivity, (a,a) ∈ R, therefore (b,a) ∈ R ◦ R−1
9. 5 points Show that a subset of an antisymmetric relation is also antisymmetric.
10. 5 points A relation R is called circular if aRb and bRc imply that cRa. Show that R is reflexive and circular if and only if it is an equivalence relation.

Page 2 of 2