Skip to main content
MathOverflow

Return to Question

added possible solution
Source Link
Rachel Basse
Rachel Basse
  • 93
  • 5

You can fix this case with the same trick that you use to well-order the rationals. Put the $E$-classes of size $i$ into a column and well-order each column. Then move along the diagonals like so. But it's not clear to me what this looks like when you have any number of columns and rows rather than just countably many. I am not sure if it's

Edit to explain potential solution: It sounds plausible to me that sending an $E$-class to an $F$-class of the smallest available size that is large enough will avoid fatally wasteful assignments regardless of the order in which you make assignments. E.g., given an $E$-class of size $5$, if $F$-classes of sizes $4,7,$ and $9$ are available, choose one of size $7$.

The problem then is just how to iterate through the $E$-classes. This sounds problematic generally, but my knowledge of ordinals is weak. E.g., is there always some sense in which you can iterate through all the members of an initial ordinal?

Put the $E$-classes into an array like this one so that an $E$-class has an index (column,row). Let the index $(s,p)$ mean that $s$ is the size of the $E$-class and $p$ is its arbitrarily-assigned position in the column.

Consider the case where you have two wellat most countably many $E$-ordersclasses of each size and only countably many possible infinite sizes. That is, $p \in \omega$ and $s \in \omega \times \lbrace 0,1\rbrace$. That is, you have countably many finite sizes (tagged with $0$) and countably many infinite sizes (tagged with $1$). Then you just have two copies of the above array; one for finite cardinalssizes and one for infinite cardinals, and definesizes.

Separately snake through each of them in the overallway depicted in the linked picture. For the array of finite sizes, this hits indices in this order by alternating between these: $1_f,1_i,2_f,2_i,3_f,\ldots$$((1,0),1), ((1,0),2), ((2,0),1), ((1,0),3), \ldots$, where $1_f$ andthe $1_i$ are$0$ indicates that you're in the "finite" array. For the least elementsarray of the finite and infinite orderssizes, respectivelythis hits the indices in this (analogous) order: $((1,1),1), ((1,1),2), ((2,1),1), ((1,1),3), \ldots$. Here, $(1,1)$ denotes some infinite size such as $\omega$; $(2,1)$ might be $2^\omega$, and so on.

Finally, interleave the two orders that you got from snaking through each array. Most simply, you can take one member from each order at a time. This gives: $$((1,0),1), ((1,1),1), ((1,0),2), ((1,1),2), ((2,0),1), ((2,1),1), ((1,0),3), \ldots$$

I apologize for the somewhat cumbersome notation, but I hope that the pattern becomes clear.

Incidentally, you won't necessarily have an $E$-class for all of the points in the above arrays. E.g., you might not have any $E$-classes of size $2$. I am assuming the fullest possible case for simplicity, as it still defines a well-order when you remove some of the points.

You can fix this case with the same trick that you use to well-order the rationals. Put the $E$-classes of size $i$ into a column and well-order each column. Then move along the diagonals like so. But it's not clear to me what this looks like when you have any number of columns and rows rather than just countably many. I am not sure if it's enough to have two well-orders, one for finite cardinals and one for infinite cardinals, and define the overall order by alternating between these: $1_f,1_i,2_f,2_i,3_f,\ldots$, where $1_f$ and $1_i$ are the the least elements of the finite and infinite orders, respectively, and so on.

You can fix this case with the same trick that you use to well-order the rationals. Put the $E$-classes of size $i$ into a column and well-order each column. Then move along the diagonals like so. But it's not clear to me what this looks like when you have any number of columns and rows rather than just countably many.

Edit to explain potential solution: It sounds plausible to me that sending an $E$-class to an $F$-class of the smallest available size that is large enough will avoid fatally wasteful assignments regardless of the order in which you make assignments. E.g., given an $E$-class of size $5$, if $F$-classes of sizes $4,7,$ and $9$ are available, choose one of size $7$.

The problem then is just how to iterate through the $E$-classes. This sounds problematic generally, but my knowledge of ordinals is weak. E.g., is there always some sense in which you can iterate through all the members of an initial ordinal?

Put the $E$-classes into an array like this one so that an $E$-class has an index (column,row). Let the index $(s,p)$ mean that $s$ is the size of the $E$-class and $p$ is its arbitrarily-assigned position in the column.

Consider the case where you have at most countably many $E$-classes of each size and only countably many possible infinite sizes. That is, $p \in \omega$ and $s \in \omega \times \lbrace 0,1\rbrace$. That is, you have countably many finite sizes (tagged with $0$) and countably many infinite sizes (tagged with $1$). Then you just have two copies of the above array; one for finite sizes and one for infinite sizes.

Separately snake through each of them in the way depicted in the linked picture. For the array of finite sizes, this hits indices in this order: $((1,0),1), ((1,0),2), ((2,0),1), ((1,0),3), \ldots$, where the $0$ indicates that you're in the "finite" array. For the array of infinite sizes, this hits the indices in this (analogous) order: $((1,1),1), ((1,1),2), ((2,1),1), ((1,1),3), \ldots$. Here, $(1,1)$ denotes some infinite size such as $\omega$; $(2,1)$ might be $2^\omega$, and so on.

Finally, interleave the two orders that you got from snaking through each array. Most simply, you can take one member from each order at a time. This gives: $$((1,0),1), ((1,1),1), ((1,0),2), ((1,1),2), ((2,0),1), ((2,1),1), ((1,0),3), \ldots$$

I apologize for the somewhat cumbersome notation, but I hope that the pattern becomes clear.

Incidentally, you won't necessarily have an $E$-class for all of the points in the above arrays. E.g., you might not have any $E$-classes of size $2$. I am assuming the fullest possible case for simplicity, as it still defines a well-order when you remove some of the points.

added comb tag
Link
Rachel Basse
Rachel Basse
  • 93
  • 5
Source Link
Rachel Basse
Rachel Basse
  • 93
  • 5

Constructing an injective reduction of equivalence relations

[Metastuff: I asked this question in a slightly different way on mathSE last week, and it didn't go anywhere, which is why I am asking here. I added the DST tag because it's basically a problem about Borel equivalence relations stripped of all the Borelness constraints. I do need help, so helpful redirection is appreciated.]

I am trying to give a somewhat constructive definition of a function. It's somewhat constructive because I'll freely assume that I can well-order any set. Aside from that, I want to say what the function looks like.

I have two equivalence relations $E$ and $F$ on spaces $X$ and $Y$, respectively. There are no restrictions on the sizes of anything. I want to define a function $f : X \to Y$ such that $$ x E y \Leftrightarrow f(x) F f(y)\;\;\;\text{ and }\;\;\;f(x) = f(y) \Rightarrow x = y $$ for all $x,y \in X$. This makes $f$ send all points in an $E$-class to the same $F$-class and also be injective on equivalence classes (i.e., injective as $X/E \to Y/F$) and on the underlying space.

Let $I$ be the class of nonzero cardinals. For every $i \in I$, the number of $F$-classes of size at least $i$ is greater than or equal to the number of $E$-classes of size at least $i$. I want to give a mostly-constructive proof that this is sufficient for there to be a function as described above (from $E$ to $F$), i.e., I want to describe the function.

I have been struggling with this on and off for several weeks. Below are some possible time-savers for you guys. If you already have a solution, you can skip it.

The problem is extremely easy in the slightly nicer situation where, for every $i \in I$, the number of $F$-classes of size exactly $i$ is greater than or equal to the number of $E$-classes of size exactly $i$. Just partition the set of $E$-classes by size and put a well-order on each set in the partition. Do the same for $F$-classes. Then send the $n$th $E$-class of size $i$ to the $n$th $F$-class of size $i$.

The complication for the original case is that you might have to send an $E$-class of size $i$ to an $F$-class of size $j$ with $i < j$. Two problems arise this way.

First, you can't use the larger classes wastefully by sending relatively small classes to them. E.g., if $E$ has solely two classes, one of size $2$ and one of size $5$, and $F$ has solely two classes, one of size $4$ and one of size $6$, you cannot send the class of size $2$ to the class of size $6$. The only way that I can think to avoid this problem is inductively: (i) well-order the classes in some way, (ii) send the least $E$-class to the least $F$-class that is big enough, (iii) remove these, and (iv) repeat from step (ii).

This creates the second problem: how to choose the well-order for step (i). If you try, e.g., to order the classes by increasing size with an arbitrary order among classes of the same size, you run into the following problem (as Brian Scott pointed out to me on mathSE a week ago). Suppose $E$ has $\omega$ many classes of size $1$ and one class of size $2$. Suppose $F$ has one class each of every finite size. Then the above won't work because $F$ has order-type $\omega$, but $E$ has order-type $\omega+1$.

You can fix this case with the same trick that you use to well-order the rationals. Put the $E$-classes of size $i$ into a column and well-order each column. Then move along the diagonals like so. But it's not clear to me what this looks like when you have any number of columns and rows rather than just countably many. I am not sure if it's enough to have two well-orders, one for finite cardinals and one for infinite cardinals, and define the overall order by alternating between these: $1_f,1_i,2_f,2_i,3_f,\ldots$, where $1_f$ and $1_i$ are the the least elements of the finite and infinite orders, respectively, and so on.