My Math Forum Equivalence classes

 Applied Math Applied Math Forum

 February 28th, 2011, 09:40 AM #1 Newbie   Joined: Feb 2011 Posts: 5 Thanks: 0 Equivalence classes Hi guys, S is the set of all binary strings of finite length and R = {(b1, b2) are elements of S x S | b1 and b2 have the same number of 1's} My understanding of equivalence classes is not very clear. My interpretation of this question is set S has a set of binary string, where b1, b2 has the same number of 1's in the set. To describe and determine Reflexive, Symmetric and Transitive. it should be not by symmetric b1={0,0,1,1} b2={1,0,0,1}. How do I explain for the other 2 properties?
 March 1st, 2011, 07:48 AM #2 Senior Member   Joined: Jun 2010 Posts: 618 Thanks: 0 Re: Equivalence classes Hello liangteh. It seems to me, if I am interpreting your problem correctly, that R is indeed symmetric, as well as reflexive and transitive. To show reflexivity, we simply note that every finite binary string has the same number of ones as itself, so it is clearly in R. To show symmetry, assume (b?, b?) ? R. This means that b? and b? have the same number of 1's, which is the same as saying (b?, b?) ? R, proving symmetry. Finally, to prove transitivity, note that if b? and b? have the same number of 1's, and b? and b? have the same number of 1's, then they all have the same number of 1's, in particular, b? and b? have the same number of 1's. We have succeeded in showing that R is an equivalence relation on S. -Ormkärr-
March 2nd, 2011, 09:09 AM   #3
Newbie

Joined: Feb 2011

Posts: 5
Thanks: 0

Re: Equivalence classes

Hi Ormkärr,

Can you further elaborate? I dont quite get understand the concept of equivalence classes.

Quote:
 R is reflexive if xRx holds for all x in X. R is symmetric if xRy implies yRx for all x and y in X R is transitive if xRy and yRz together imply that xRz holds for all x, y, and z in X.

 March 2nd, 2011, 06:26 PM #4 Senior Member   Joined: Jun 2010 Posts: 618 Thanks: 0 Re: Equivalence classes Hi liangteh. One definition of a binary relation R on a set A is as a subset of the cartesian product A×A, i.e. R ? A×A. If one takes any two elements a, b ? A, he says that "a is R-related to b", or sometimes aRb, if (a,b) ? R. To say that a binary relation is an equivalence relation means that it satisfies the properties you listed: reflexivity, symmetry, and transitivity. Given an equivalence relation R on a set A and some member a ? A, the set of all b ? A such that (a,b) ? R is called the equivalence class of a. An equivalence relation partitions A into a disjoint union of equivalence classes, i.e. every a ? A belongs to a unique equivalence class under the equivalence relation R. Does this clear things up, or do you have another question? -Ormkärr-
 March 5th, 2011, 09:19 AM #5 Newbie   Joined: Feb 2011 Posts: 5 Thanks: 0 Re: Equivalence classes Hi Ormkärr, I understand better after your explanations Thank you =)
 March 11th, 2011, 08:42 AM #6 Newbie   Joined: Feb 2011 Posts: 5 Thanks: 0 Re: Equivalence classes How do I determine the number of different equivalence classes?
March 11th, 2011, 08:54 AM   #7
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Equivalence classes

Quote:
 Originally Posted by liangteh How do I determine the number of different equivalence classes?
It's infinite in this case.

 March 12th, 2011, 06:42 AM #8 Newbie   Joined: Feb 2011 Posts: 5 Thanks: 0 Re: Equivalence classes why is it so?
 March 12th, 2011, 05:31 PM #9 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Equivalence classes What does each congruence class represent? Once you understand that it's obvious.

 Tags classes, equivalence

### equivalence relations for binary strings

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post LaC0saNostra Applied Math 4 October 27th, 2012 05:02 PM thadroberts77 Linear Algebra 2 January 27th, 2012 01:54 AM guynamedluis Real Analysis 0 November 21st, 2011 09:39 PM tsmith Abstract Algebra 1 May 10th, 2010 03:01 PM Zhai Applied Math 9 May 5th, 2010 02:18 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top