[SOLVED] COMP9020-Set 4 Equivalence Relations and Orderings

Description

1. (Equivalence relations)

For each of the following relations R, prove or disprove that R is an equivalence relation.

1. Real number r is related to real number s iff |r − s| ≤ 1.
2. Pair of integers (i,j) is related to pair of integers (m,n) iff i + j ≡ m − n (mod2).
3. Set A is related to set B iff A ∩ B = A and B ∈ Pow(A).
4. Let Σ = {a,b}. Word ν ∈ Σ^∗ is related to word ω ∈ Σ^∗ iff ν = ωχ for some word χ ∈ Σ∗.
5. Propositional formula ϕ is related to propositional formula ψ iff ϕ ⊨ ψ and ⊨ ψ ⇒ ϕ.
6. Over the standard Boolean algebra, x,y ∈ B = {0,1} are related iff

(x + y^′) ⋅ (x^′ + y) = 0.

1. 1×2 matrix A is related to 1×2 matrix B iff A = B or A·B^T = 0.

2. (Modular arithmetic)
   1. Prove that if m,n ∈ Z and m ≡ n (modp) then m² ≡ n² (modp).
   2. Let p = 3. Give all equivalence classes for m² ≡ n² (modp) where m,n ∈ Z.
3. (Partial versus total orders)

Consider the relation R ⊆ R × R defined by (a,b) ∈ R iff either a ≤ b − 0.5 or a = b.

4. (Partial orders)

For each of the following relations, prove or disprove that it is a partial order.

1. Natural number m is related to natural number n iff n³ > m² + 1.
2. Natural number m is related to natural number n iff ⌈m + 0.5⌉ > n.
3. Positive integer m is related to positive integer n iff 3m > 2n.
4. Positive integer m is related to positive integer n iff gcd(m,n) = n.
5. Positive integer m is related to positive integer n iff m is a prime divisor of n.
6. Integer m is related to integer n iff m³ ≤ n³.

5. (Lattices)
   1. Draw a Hasse diagram for the following partially ordered set:

S = {1,2,3,5,6,10,15,30} x ⪯ y iff x|y

Is (S,⪯) a lattice? Why or why not?

10. Let binary relation R on {1,…,20} be defined by aRb iff either a = b or a − b > 10. Show that ({1,…,20},R) is a partial order. Is ({1,…,20},R) a lattice? Why or why not?

6. Challenge Exercise Using the set {1,…,10} with the natural total order, define A = {1,…,10} × {1,…,10} and consider these two orderings over A:
   1. product ⊑_P
   2. lexicographic ⊑_L

Find the maximal length of a chain a₁ ⊑ a₂ ⊑ … ⊑ a_n (such that a_i ≠ a_i+1) for each of the two orderings.