Timeline for Constructing an injective reduction of equivalence relations
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 31, 2012 at 16:44 | comment | added | Rachel Basse | @Joel: math.stackexchange.com/questions/184816 | |
| Aug 31, 2012 at 2:45 | comment | added | Joel David Hamkins | Can you give a link to the mathSE question? | |
| Aug 31, 2012 at 0:50 | vote | accept | Rachel Basse | ||
| Aug 31, 2012 at 0:50 | vote | accept | Rachel Basse | ||
| Aug 31, 2012 at 0:50 | |||||
| Aug 30, 2012 at 14:51 | answer | added | Joel David Hamkins | timeline score: 4 | |
| Aug 30, 2012 at 3:38 | comment | added | Rachel Basse | Perhaps I should mention another probably familiar trick: 1,1,2,1,2,3,1,2,3,4,.... You can use the pattern in this sequence to interleave ctbly many sequences by letting the 1st occurrence of 1 be the 1st term of sequence 1 and generally the ith occurrence of n be n_i. You can do this repeatedly, interleaving many sequences into one, then interleaving this with many others, etc. So if you can chunk up the problem into countable pieces, you can possibly weave together an order. Thanks for the welcome, @David. I have heard of JDH, which is why I am scared I won't finish this proof soon. | |
| Aug 30, 2012 at 0:29 | comment | added | David Roberts♦ | Welcome to MO, Rachel! When JDH compliments your set-theoretical question you know you're on to a good thing. | |
| Aug 30, 2012 at 0:28 | comment | added | Rachel Basse | @Trevor: I edited some further explanation into my question. | |
| Aug 30, 2012 at 0:27 | history | edited | Rachel Basse | CC BY-SA 3.0 |
added possible solution
|
| Aug 29, 2012 at 22:42 | comment | added | Trevor Wilson | Oh, I thought your last paragraph was just addressing the specific counterexample. I don't yet understand the method you are describing, although it's clear how to get around the specific counterexample. My intuition is that anything that works here in the countable case has a good chance of working in general. Of course, there are a lot of countable ordinals to consider. | |
| Aug 29, 2012 at 22:13 | comment | added | Rachel Basse | @Trevor: It sounds plausible to me (?) that sending a class to the smallest available one that works will avoid fatally wasteful assignments regardless of the order in which you make assignments. My eventual restrictions make the size of a class $\leq\omega$ and the number of classes $\leq 2^\omega$, changing the array in the link only by adding columns for $\omega$ and $2^\omega$. Snake through the finite part as shown, and separately snake through the two additional columns the same way. Then interleave your snakes, giving $(1,1),(\omega,1),(1,2),(\omega,2),(2,1),(2^\omega,1),\ldots$. Works? | |
| Aug 29, 2012 at 21:28 | history | edited | Rachel Basse |
added comb tag
|
|
| Aug 29, 2012 at 21:05 | comment | added | Trevor Wilson | It seems non-obvious even in the countable case: given two functions $s,t$ from countable sets to $\mathbb{N}$ such that for every $n \in \mathbb{N}$ the preimage of $[n,\infty)$ by $t$ has cardinality at least as big as the preimage by $s$, is there an injection $F:\text{dom}(s) \to \text{dom}(t)$ such that $t \circ F$ is pointwise $\ge s$? Maybe the "combinatorics" tag should be added. | |
| Aug 29, 2012 at 20:44 | comment | added | Rachel Basse | @Joel: Uh-oh. Does that mean it's not getting an answer soon? :^) This is just for an expository paper where I am trying to establish what happens with reductions of equivalence relations generally before I confine myself to Borel reductions of countable Borel equivalence relations. I want to be as constructive as possible now to inform later proofs. I might have made it too difficult by removing the cardinality constraints, esp. because I don't think I appreciate the vastness of the ordinals or even cardinals, which leaves me unsure of whether I am considering all that can happen. | |
| Aug 29, 2012 at 14:26 | comment | added | Joel David Hamkins | This is a nice problem! | |
| Aug 29, 2012 at 13:43 | comment | added | Trevor Wilson | It might help to make it explicit that under the Axiom of Choice the problem is equivalent to the following one: Given two sets $A,B$ and two ordinal-valued functions $s,t$ on $A,B$ respectively such that for every ordinal $\alpha$ we have $|\lbrace x \in A : s(x) \ge \alpha \rbrace| \le |\lbrace y \in B : t(y) \ge \alpha \rbrace|$, construct an injection $F:A \to B$ such that $t(F(x)) \ge s(x)$ for all $x \in A$. | |
| Aug 29, 2012 at 11:17 | history | asked | Rachel Basse | CC BY-SA 3.0 |