1. (Equivalence relations)
For each of the following relations R, prove or disprove that R is an equivalence relation.
a. Real number r is related to real number s iff |r − s| ≤ 1.
b. Pair of integers (i,j) is related to pair of integers (m,n) iff i + j ≡ m − n (mod2).
c. Set A is related to set B iff A ∩ B = A and B ∈ Pow(A).
d. Let Σ = {a,b}. Word ν ∈ Σ∗ is related to word ω ∈ Σ∗ iff ν = ωχ for some word χ ∈ Σ∗.
e. Propositional formula ϕ is related to propositional formula ψ iff ϕ ⊨ ψ and ⊨ ψ ⇒ ϕ.
f. Over the standard Boolean algebra, x,y ∈ B = {0,1} are related iff
(x + y′) ⋅ (x′ + y) = 0.
g. 1×2 matrix A is related to 1×2 matrix B iff A = B or A·BT = 0.
2. (Modular arithmetic)
a. Prove that if m,n ∈ Z and m ≡ n (modp) then m2 ≡ n2 (modp).
b. Let p = 3. Give all equivalence classes for m2 ≡ n2 (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.
Show that R is a partial order, but not a total order.
4. (Partial orders)
For each of the following relations, prove or disprove that it is a partial order.
a. Natural number m is related to natural number n iff n3 m2 + 1.
b. Natural number m is related to natural number n iff ⌈m + 0.5⌉ n.
c. Positive integer m is related to positive integer n iff 3m 2n.
d. Positive integer m is related to positive integer n iff gcd(m,n) = n.
e. Positive integer m is related to positive integer n iff m is a prime divisor of n.
f. Integer m is related to integer n iff m3 ≤ n3.
5. (Lattices)
a. 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?
b. 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:
a. product ⊑P
b. lexicographic ⊑L
Find the maximal length of a chain a1 ⊑ a2 ⊑ … ⊑ an (such that ai ≠ ai+1) for each of the two orderings
