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:
 
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 Rrelated 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:
 
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 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

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