Question

Discrete Math / Proofs

Directions: Show all work/steps. State all assumptions as well as 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, a₂, a₃, a₄ > R 1, b₂, b₃, b₄> ε A

( 1, a₂, a₃, a₄> R 1, b₂, b₃, b₄> if and only if a₁ - a₂ + a₃ - a₄ = b₁ - b₂ + b₃ - b₄ )

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> since 1 - 0 + 1 - 1 = 1 = 0 - 0 + 1 - 0   etc.

ii.) Prove R is an equivalence relation on A. Please be clear in your exposition.

iii.) List the elements (binary sequences of length 4) in each equivalence class and name each equivalence class with one of its names.

iv.) Suppose an operation on the set of equivalence classes is intended to be defined as follows:

[<a₁, a₂, a₃, a₄>] * [<b₁, b₂, b₃, b₄>] = [a₁b₁, a₂b₂, a₃b₃, a₄b₄>]

Show by specific example that this operation is not well-defined.

Answer 1