My Math Forum  

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

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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.
Zhai is offline  
 
May 5th, 2010, 07:57 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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 "expand R" mean? I suspect that if I understood that I could answer the question.
CRGreathouse is offline  
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?
Zhai is offline  
May 5th, 2010, 08:36 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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 Zhai
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?
There is only one relation S such that, for all n and m, nRm <=> nSm, and in your case it's not an equivalence relation.

Perhaps it means that S is a superset of R, viewed as a collection of ordered pairs (m, n)?
CRGreathouse is offline  
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.
Zhai is offline  
May 5th, 2010, 09:08 AM   #6
Global Moderator
 
CRGreathouse's Avatar
 
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 Zhai
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.
In other terms, for all (m, n), mRn => mSn (but maybe mSn even if not mRn).

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.
CRGreathouse is offline  
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?
Zhai is offline  
May 5th, 2010, 10:26 AM   #8
Global Moderator
 
CRGreathouse's Avatar
 
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 Zhai
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?
Oh good, I missed that -- I must have misread the "2" as a "1". Let's see what we get.

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 S-related: 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?
CRGreathouse is offline  
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?
Zhai is offline  
May 5th, 2010, 01:18 PM   #10
Global Moderator
 
CRGreathouse's Avatar
 
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 Zhai
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?
Well, you knew that [2] contained at least 2,4,6,8,10,12, so you can write . You don't know that they're equal, and in fact they're not since it also contains 3 and 9 and I showed above.

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

  My Math Forum > College Math Forum > Applied Math

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





Copyright © 2018 My Math Forum. All rights reserved.