Expert: Sherry Wallin - 3/24/2009

Question
What equivalence relation gives this partition P of the natural numbers?

P ={{1},{2,4,8,...},{3,9,27,...},{5,25,...},{6,36,...},{7.49,...}...}

I can see that the different sets or partitions are:

{1} is 1^1
{2,4,8,...} is 2^1, 2^2, 2^3,...
{3,6,9,...} is 3^1, 3^2, 3^3,...
{5,25,...} is 5^1, 5^2,...
{6,36,...} is 6^1, 6^2,...
{7,49,...} is 7^1, 7^2,...

I also note that 4^1, 4^2....is left out but presume that this is because these would be covered in the partition 2^1, 2^2, 2^3,....

But I do not know how to relate this to an equivalence relation?  Can you assist please?

Thanks

Answer
Steve~
    How about aRb iff a = b^n for n a natural number? Yes your assumption is correct that 4^1,4^2,...would be contained in the partition of 2^1,2^2,...but look carefully at your (3,6,9,...} which isn't in P. What is in P is {3,9,27,...} = {3^1,3^2,3^3,...}. Of course you will want to check that this definition/relation satisfies the reflexive, symmetric, and transitive properties.

Math Prof