My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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?
liangteh is offline  
 
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-
 is offline  
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.
liangteh is offline  
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-
 is offline  
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 =)
liangteh is offline  
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?
liangteh is offline  
March 11th, 2011, 08:54 AM   #7
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

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.
CRGreathouse is offline  
March 12th, 2011, 06:42 AM   #8
Newbie
 
Joined: Feb 2011

Posts: 5
Thanks: 0

Re: Equivalence classes

why is it so?
liangteh is offline  
March 12th, 2011, 05:31 PM   #9
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

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.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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





Copyright © 2018 My Math Forum. All rights reserved.