Timeline for Constructing an injective reduction of equivalence relations
Current License: CC BY-SA 3.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 31, 2012 at 1:48 | comment | added | Joel David Hamkins | I have realized that there is no need to split into the case of $\delta$ finite and $\delta$ infinite, since the argument is actually uniform, and so I edited the answer to include this further simplification. | |
| Aug 31, 2012 at 1:47 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
Further simplification
|
| 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 23:27 | comment | added | Rachel Basse | @Joel: I'll read your simplified argument now. So that you don't feel ignored in the meantime: I thought your original argument was very nice because (i) I was mildly perturbed that I hadn't used the non-increasing property of these sequences yet and (ii) I think that handling the largest classes first makes it clearest that you avoid problems. So you gave me those two bonuses also. I am currently thinking about how to say more about the assignments within each constant segment. Since $\delta_{k_0} = \delta$ is the number of classes in the segment, it at least gives me a limit to work with. | |
| Aug 30, 2012 at 22:52 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
Simplified the argument; improved exposition
|
| Aug 30, 2012 at 22:48 | comment | added | Joel David Hamkins | I posted a simplified argument. | |
| Aug 30, 2012 at 22:46 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
Simplified the argument, better explanation
|
| Aug 30, 2012 at 20:12 | comment | added | Joel David Hamkins | Trevor and Rachel, in my argument, since we will ultimately reduce to a version of $E$ with a strictly larger $\delta$ value, in fact I think it is not so important to save $\delta$ many classes from $F$ as I did (although this was fine). Since on the next smaller interval, there will be always at least $\delta^+$ or more many classes, it follows that $F$ will also have $\delta^+$ many classes above, and so we didn't need to save any, as we will use only $\delta$ of them. | |
| Aug 30, 2012 at 19:37 | comment | added | Rachel Basse | @Gerhard: If you are curious, I think I know what happens with bijective reductions when everything is Borel, and it doesn't look like the generalization breaks anything. $E \cong F$ ($E$ bijectively reduces to $F$) iff $s_f(E)_i = s_f(F)_i$ for all $i$, where I am using slightly different notation from Hamkins. $s_f(E)$ is the sequence indexed by cardinals $I$ where $s_f(E)_i$ is the number of $E$-classes of size exactly $i$. [cont above...] (These are out of order because I mistyped your name the first time and had to delete the comment. It appears comments can't be edited here?) | |
| Aug 30, 2012 at 19:32 | comment | added | Rachel Basse | I have been calling this the fine shape of $E$ and the analogous sequence where $s_c(E)_i$ is the number of $E$-classes of size at least $i$ the coarse shape of $E$. Comparing the shapes of two relations componentwise (using the relations on cardinals) tells you exactly when reductions, bireductions, embeddings, biembeddings, and isomorphisms exist. The case above was by far the most difficult to prove in the Borel case. | |
| Aug 30, 2012 at 17:46 | comment | added | Trevor Wilson | Ok, your last post addresses my quibble. Thanks. | |
| Aug 30, 2012 at 17:44 | comment | added | Trevor Wilson | Yes, you are fine in both cases. But in the sub-case of the first case where there are $\delta$ many sizes with only one $F$-class of that size (and possibly $<\delta$ many sizes with more than one $F$-class of that size) the way to remove half is different: rather than removing half of the classes of each size, you line the uniquely-sized classes up by their size and remove the ones in odd positions. | |
| Aug 30, 2012 at 17:42 | comment | added | Joel David Hamkins | And to be clear: among the sizes with only one class of that size, remove "half" in the sense of every other one. | |
| Aug 30, 2012 at 17:35 | comment | added | Joel David Hamkins | Trevor, another way to say it is: if a bunch of cardinal numbers add up to an infinite cardinal $\delta$, then adding half of each of those numbers also adds up to $\delta$. | |
| Aug 30, 2012 at 17:27 | comment | added | Joel David Hamkins | I am saying that you can just go ahead and remove half even when there are only finitely many of that size. The situation is very flexible. The point is that it doesn't matter, since $\delta$ is infinite, and the later classes will still add up to $\delta$ many altogether. That is, either there are $\delta$ many sizes with only finitely many classes (in which case we're fine), or there are less than $\delta$ many sizes with only finitely many classes (in which case we're also fine, and can actually ignore them). | |
| Aug 30, 2012 at 17:14 | comment | added | Trevor Wilson | I think a bit more argument is required to show that you can remove $\delta$ many $F$-classes of size at least $\kappa_0$ while maintaining the desired inequalities for the remaining part of $F$. You can remove half of the classes of any given size above $\kappa_0$ from $F$, provided that there are infinitely many, but what if there are only finitely many classes of that size? For example, if for any given size above $\kappa_0$ there is only one $F$-class of that size, you can still do it but you have to use another method. | |
| Aug 30, 2012 at 15:43 | comment | added | Joel David Hamkins | Gerhard, that is an interesting idea. Here, the reductions need not be bijective, which makes it different from the marriage problem, but I agree that there is a family resemblence. | |
| Aug 30, 2012 at 15:36 | comment | added | Gerhard Paseman | I find some similarity between the posted problem and a lopsided version of Hall's marriage Theorem. Do you see it also? If so, there are some concerns in the infinite case, and I do not know of any constructive versions of proofs of Hall's theorem. I would be interested in your thoughts on the matter. Gerhard "Ask Me About System Design" Paseman, 2012.08.30 | |
| Aug 30, 2012 at 15:12 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 181 characters in body; added 3 characters in body
|
| Aug 30, 2012 at 15:06 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 57 characters in body; added 5 characters in body; added 4 characters in body
|
| Aug 30, 2012 at 14:56 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 69 characters in body
|
| Aug 30, 2012 at 14:51 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |