May 5th, 2010, 03:41 AM  #1 
Newbie Joined: Oct 2009 Posts: 14 Thanks: 0  Equivalence Classes
Hi, I have a task here that ask me to find the equilvalence classes. The task is written as following: Let X = {2, ..... , 12} ? N and define a relation R on X with nRm <=> m/n ? N Now let S be the least (or smallest) equivalence relation that expand R so that we have a relation 2S3. Find S by describing all the equivalence classes to S. The problem for me here is that I can't see how we have a relation 2S3 at all. And I can't describe the equivalence classes without knowing what the relation S is here. I do know that S is an equivalence relation since it is said in the task's text, which also mean that S is a relation that is reflexive, symmetric and transitive. But still, I just can't see what the S relation is, especially when we have a relation 2S3 somehow. So I would appreciate any kind of help or suggestions here. 
May 5th, 2010, 07:57 AM  #2 
Global Moderator 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 "expand R" mean? I suspect that if I understood that I could answer the question.

May 5th, 2010, 08:14 AM  #3 
Newbie Joined: Oct 2009 Posts: 14 Thanks: 0  Re: Equivalence Classes
Thanks for reply, If I understand the text correctly, "expand R" might mean that S is an equvalence relation on X so that nRm <=> nSm, or something like that. There are no clear definitions of the word "expand" in the text so that's what I guess is the meaning of "expand". Maybe you have a different opinion on what S expanding R might be? 
May 5th, 2010, 08:36 AM  #4  
Global Moderator 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:
Perhaps it means that S is a superset of R, viewed as a collection of ordered pairs (m, n)?  
May 5th, 2010, 08:44 AM  #5 
Newbie Joined: Oct 2009 Posts: 14 Thanks: 0  Re: Equivalence Classes
Can you give me a concrete example on that please, i don't quiet get it yet. Because you might be right, and if so, that can be what I have missed to solve this task.

May 5th, 2010, 09:08 AM  #6  
Global Moderator 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:
If that was the case, then since 1Rn for n = 1,2,...,12 then 1Sn for those n, and the same if we change variables: 1Rm and 1Sm. Then since S is an equivalence relation, nS1 and mS1. By transitivity, mS1 and 1Sn give mSn. So if that interpretation is right, then S is the trivial relation where everything is related to everything else.  
May 5th, 2010, 09:58 AM  #7 
Newbie Joined: Oct 2009 Posts: 14 Thanks: 0  Re: Equivalence Classes
I see... But the relation is based on X, which was X = {2, ..... , 12} ? N You explained it with 1, and 1 is not in X, so would that give another meaning if we only consider the numbers in X? And if what you are saying is correct, wouldn't it be existing a lot of equivalence classes which is what we are looking for to begin with? 
May 5th, 2010, 10:26 AM  #8  
Global Moderator 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:
2Rn for n even, 2Rm for m even, thus 2Sn, 2Sm, nS2, and mS2. By transitivity on mS2 and 2Sn, all even numbers are related to each other by S. We can then glob all the evens together; I'll call them [2]. Similarly, all multiples of three are Srelated: mSn for m,n divisible by 3 (call such elements [3]). Since 6 is divisible by both 2 and 3, we have [2] = [3]. So right now we have [2], 5, 7, and 11. I'll let you finish this off. So far we know that 5S5, 7S7, 11S11, and mSn for any m,n in X other than 5, 7, and 11. But do any other pairs hold?  
May 5th, 2010, 12:21 PM  #9 
Newbie Joined: Oct 2009 Posts: 14 Thanks: 0  Re: Equivalence Classes
Ok, think things are starting to get more clear for me, I think. So if I am gonna write the equivalence classes, we would have a class for 2, which you called [2]? If we take that as example, an equivalence class where we pair numbers with 2 would be something like this? E(2) = {2, 4, 6, 8 ,10, 12} ? Since the pairings with 2 are the even numbers in X? 
May 5th, 2010, 01:18 PM  #10  
Global Moderator 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:
Edit: Of course you don't need to use this notation, but I imagine you'll cover it soon and it's good to recognize it.  

Tags 
classes, equivalence 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Congruence Classes  LaC0saNostra  Applied Math  4  October 27th, 2012 04:02 PM 
Classes of equations?  thadroberts77  Linear Algebra  2  January 27th, 2012 12:54 AM 
Equivalence Classes of Subsets of R^2  guynamedluis  Real Analysis  0  November 21st, 2011 08:39 PM 
Equivalence classes  liangteh  Applied Math  8  March 12th, 2011 04:31 PM 
isomorphism classes  tsmith  Abstract Algebra  1  May 10th, 2010 02:01 PM 