2

I've been looking around and found questions related to deriving partitions from equivalence relations; however I was wondering if there is a method to finding an equivalence relation from a given partition.

For example the partition $\{\{1, ..., 9\},\{10, ..., 99\},\{100, ..., 999\}, ...\}$ of the natural numbers (not counting 0). The best I can come up with (by guessing) for an equivalence relation is $x{R}y$ iff [$x$ and $y$ have the same number of digits], but that doesn't seem very mathematical. Otherwise my second best guess is something to do with logarithms. (Full disclosure, this is a homework problem.)

So I was wondering, is there a method to derive an equivalence relation based on the equivalence classes set by the partition?

qwersjc
  • 145
  • 1
    A partition defines an equivalence relation. a~b if a and b are in the same partition. It is a good exercise to prove that statement. – John Douma Nov 04 '15 at 02:51
  • 1
    @JohnDouma Yep and vice versa. The full story is: an equivalence relation $R$ determines a partition $P_R$, a partition $P$ determines an equivalence relation $R_P$, and these are inverses of each other: $R_{P_R} = R$ ("the equivalence relation determined by the partition induced by an equivalence relation is the original equivalence relation"), and similarly $P_{R_P} = P$ for a partition. It's a very good exercise to work out the details. Once. (It's not hard, though.) – BrianO Nov 04 '15 at 03:16

1 Answers1

3

The same number of decimal digits sounds good to me.

To make it harder to understand, we could write $x\sim y$ if $\lfloor \log_{10} x\rfloor=\lfloor \log_{10} y\rfloor$.

André Nicolas
  • 507,029
  • Thanks for answering my question! But I am also wondering about generally finding an equivalence relation from a partition (other than listing out all the ordered pairs from the equivalence classes). My example probably wasn't the best; what about for example ${..., {-2}, {-1}, {0}, {1}, {2}, {3, 4, 5, ...}}$ on the integers? I'm not sure how I would go about defining the equivalence relation for that partition. – qwersjc Nov 04 '15 at 03:15
  • 1
    Equivalence relation and partition are essentially the same. One can go seamlessly from one to the other. The only issue, a not very interesting one, is expressing the relation, or the partition, in a compact way. – André Nicolas Nov 04 '15 at 03:31
  • Fair enough. I guess I assumed that all relations could be expressed neatly (which doesn't make much sense at all). I will just have to list the ordered pairs of the relation then. Thanks again for your help. – qwersjc Nov 04 '15 at 03:38
  • In a reasonably precise sense of most (cardinality) most relations cannot be expressed neatly. But many important relations can be. – André Nicolas Nov 04 '15 at 03:42