Discrete Math / Proofs
Directions: Show all work/steps. State all assumptions as wellas the goal of the proof.
Define A = { all binary sequences of length 4 }
So < 1, 1, 0 1 > ε A, <0, 0, 0, 0 > ε A, <1, 0,0, 1> ε A etc.
i.) What is | A | ?
Define a relation R on A as follows:
For 1, a2, a3, a4 > R 1,b2, b3, b4> ε A
( 1, a2, a3, a4> R 1,b2, b3, b4> if and only ifa1 - a2 + a3 - a4 =b1 - b2 + b3 - b4 )
e.g. <0, 0, 1, 1> R <1, 1, 0, 0> since 0 - 1 + 1 - 1= 0 = 1 - 1 + 0 - 1 and <1, 0, 1, 1> R <0,0,1,0> since1 - 0 + 1 - 1 = 1 = 0 - 0 + 1 - 0Â Â etc.
ii.) Prove R is an equivalence relation on A. Please be clear inyour exposition.
iii.) List the elements (binary sequences of length 4) in eachequivalence class and name each equivalence class with one of itsnames.
iv.) Suppose an operation on the set of equivalence classes isintended to be defined as follows:
[1, a2, a3,a4>] * [1, b2,b3, b4>] = [a1b1,a2b2, a3b3,a4b4>]
Show by specific example that this operation isnot well-defined.
