Congruency and Equivalent classes. 1. The words in a usual dictionary are partit

Question

Congruency and Equivalent classes.

1. The words in a usual dictionary are partitioned into 26 subsets (so called alphabetically).
(a) Define an equivalence relation on this set of words whose equivalence classes are exactly those 27 subsets.
(b) Prove that the relation you defined in (a) indeed is an equivalence relation.

(c) Provide another equivalence relation that can partition the words in the dictionary. Prove that it is indeed an equivalence relation. Explain the equivalence classes.

2. Suppose that we send 8-digit numbers (data) plus 2-digit check numbers, total of 10-digit numbers over the network. Devise a method of using 2-digit check numbers with which the receiver can check if the first 8 digit numbers were correctly transmitted and received by looking at the last 2-digit check numbers. The method should use the concept of congruence modulo m. Choose the number m so that the likelihood of getting the same 2-digit check number from two different 8-digit numbers is minimal. Show all work.

Explanation / Answer

1.)

a.)

We can define a relation R as:

Let a and b be words in the dictionary

aRb iff b starts with the same letter as a

b.)

R satisfies the following properties:

1. for every word a,aRa because both a starts with the same letter as a

2. for every word a and b,aRb => bRa because if b starts with the same letter as a, then a also starts with the same letter as b

3. aRb ,bRc => aRc because if b starts with the same letter as a and c starts with the same letter as b, then c starts with the same letter as a

Therefore R is an equivalence relation

c.)

We can define another relation R2 as:

Let a and b be words in the dictionary

aRb iff b starts with the same 2 letters as a

R2 satisfies the following properties:

1. for every word a,aR2a because both a starts with the same 2 letters as a

2. for every word a and b,aRb => bRa because if b starts with the same 2 letters as a, then a also starts with the same 2 letters as b

3. aRb ,bRc => aRc because if b starts with the same 2 letters as a and c starts with the same 2 letters as b, then c starts with the same 2 letters as a

Therefore R2 is an equivalence relation

R divides the words into classes where every word in a class starts with the same letter

R has 27 equivalence classes-26 alphabets and non-alphabet

R2 divides the words into classes where every word in a class starts with the same 2 letters

R2 has 27^2 equivalence classes-(26 alphabets and non-alphabet for 1st character) * (26 alphabets and non-alphabet for 2nd character)

2.)

Choose m to be a prime number, like 11

Multiply each digit in data with its position and add the result. Take the result mod 11, this will be the checksum digits(if mod 11 = 9, checkdigits will be 09)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.