My Math Forum Equivalence Classes

 Applied Math Applied Math Forum

 May 5th, 2010, 04: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, 08:57 AM #2 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 "expand R" mean? I suspect that if I understood that I could answer the question.
 May 5th, 2010, 09: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, 09:36 AM   #4
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 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)?

 May 5th, 2010, 09: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, 10:08 AM   #6
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 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.

 May 5th, 2010, 10: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, 11:26 AM   #8
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 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?

 May 5th, 2010, 01: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, 02:18 PM   #10
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 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 $\{2,4,6,8,10,12\}\subseteq[2]$. 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.

 Tags classes, equivalence

 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 liangteh Applied Math 8 March 12th, 2011 05:31 PM tsmith Abstract Algebra 1 May 10th, 2010 03:01 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top