Timeline for Cantor's diagonal argument and ZF
Current License: CC BY-SA 3.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 27, 2013 at 20:14 | comment | added | Asaf Karagila♦ | Oh. I haven't noticed that! :-) Sorry! | |
| Feb 27, 2013 at 20:12 | comment | added | François G. Dorais | I'm still confused. That equivalence is exactly what I wrote in the addendum, so where is the issue? | |
| Feb 27, 2013 at 19:11 | comment | added | Asaf Karagila♦ | (In the other direction part is a bit out of context, it's the proof that the existence of $d$ for $[X+n]^X\to X+n$ implies a choice function for $[X]^n$, which is what I suggested in a previous comment.) | |
| Feb 27, 2013 at 19:10 | comment | added | Asaf Karagila♦ | My remark about Joel's conjecture is exactly what you said. The post suggests that Joel's conjecture has been refuted by the case of $Y=X+1$, but in fact it is still open. In the other direction suppose that $d\colon[X+n]^X\to X+n$ such that $d(A)\notin A$ exists, we define a choice function on $[X]^n$. Given $a_1\ldots,a_n\in X$ replace them by the $1,\ldots,n$ and you have a subset of size $X$ in $X+n$, apply $d$ to this set and the result must be an element from $a_1,\ldots,a_n$. So we are done. | |
| Feb 27, 2013 at 18:58 | comment | added | François G. Dorais | I don't understand your remark on Joel's conjecture. The fact that the extended conjecture is false when $X$ is Dedekind finite and $Y = X+1$ does not rule out the original conjecture since he only conjectured it for $Y = \mathcal{P}(X)$. | |
| Feb 27, 2013 at 18:54 | comment | added | François G. Dorais | I haven't had a chance to read the article yet, but my understanding is that this is exactly what Conway's "effective implications" are: he characterizes when choice functions for $[X]^{n_1},\dots,[X]^{n_k}$ give a choice function for $[X]^m$, which is much stronger than $C_{n_1} \land \cdots \land C_{n_k} \to C_m$. | |
| Feb 27, 2013 at 18:30 | comment | added | Asaf Karagila♦ | I don't think it's right to cross off Joel's conjecture because he only conjectured it for the case $Y=\mathcal P(X)$, and we only disproved this for the cases of $Y=X+1$ (in $\sf ZF$) and $Y=X+n$ ($\sf ZF+C_n$). I also think that we may want to try and prove that local version of $C_n$ might hold, e.g. $[X+4]^X\to X+4$ implies $C_4(X)$ (choice from subsets of size $4$ of $X$) or something similar. | |
| Feb 27, 2013 at 18:16 | comment | added | Asaf Karagila♦ | That's a nice and reasonably sounding observation. After this we can do $X\times n$ and then $X\times X$ and so on... :-) | |
| Feb 27, 2013 at 18:15 | history | edited | François G. Dorais | CC BY-SA 3.0 |
Update on Dedekind finite case
|
| Feb 27, 2013 at 10:42 | comment | added | François G. Dorais | After checking, the between finite choice principles $C_n$ is all proved locally and the results transfer to this. For example, if there is a $d:[X+2]^X\to X+2$ then there is also a $d:[X+4]^X\to X+4$ but there is not necessarily a $d:[X+3]^X\to X+3$. The known stuff takes care of $Y=X+n$ for $1 \leq n \lt \aleph_0$. The next interesting case is $Y = X+X$. | |
| Feb 27, 2013 at 4:20 | comment | added | Asaf Karagila♦ | Not surely, but likely. :-) Either way if $Y$ is amorphous and $Z>1$ you can't make that choice. Perhaps this could be a way of proving Joel's conjecture. | |
| Feb 27, 2013 at 3:32 | comment | added | François G. Dorais | Aha! Nice, Asaf! In the case where $X$ and $Y = X + Z$ are Dedekind finite, there is such a $d:[Y]^{X}\to Y$ if and only if there is a choice function $c:[Y]^{Z}\to Y$. This has surely been looked at... | |
| Feb 27, 2013 at 1:51 | comment | added | Asaf Karagila♦ | (I still feel that in the case where $Y=\mathcal P(X)$ this should hold, but that is certainly not the same as any two sets such that $X\prec Y$.) | |
| Feb 27, 2013 at 1:49 | comment | added | Asaf Karagila♦ | Well, here is a trivial proof that it fails. Let $X$ be any Dedekind-finite set, and let $Y=X\cup\{X\}$. Then $X\prec Y$, and $d\colon[Y]^X\to Y$ is easily defined by $d(A)$ is the unique member of $Y\setminus A$. | |
| Feb 27, 2013 at 0:29 | comment | added | François G. Dorais | It's a question of perspective. From my point of view, the case when $X$ is infinite Dedekind-finite is the only remaining case to check for the conjectured equivalence $(\forall Y)[\aleph(X) \preceq Y \leftrightarrow (\exists d:[Y]^X\to Y)(\ldots)]$. From your point of view, the only remaining case is to show that there is no such $d:[Y]^X\to Y$ when $X$ and $Y$ are both infinite but Dedekind finite. | |
| Feb 26, 2013 at 22:54 | comment | added | Asaf Karagila♦ | (Removing my previous comment correction, obviously if we require $X\prec Y$ and $Y$ is Dedekind-finite then we are requiring that $X$ is Dedekind-finite as well...) | |
| Feb 26, 2013 at 19:40 | comment | added | Asaf Karagila♦ | The remaining case is not when $X$ is Dedekind-finite but rather when $Y$ is Dedekind-finite. If $Y$ is Dedekind-infinite then $\aleph(X)\preceq Y$ and we can easily give a solution. Additionally, if $Y=X\cup\{X\}$ then it is also clear what $d$ should be. Beyond these two trivial cases, I can't really say too much. | |
| Feb 26, 2013 at 6:11 | comment | added | Asaf Karagila♦ | Joel, I am still trying to wrap my head around the amorphous case. I think I may have to call a specialist. | |
| Feb 26, 2013 at 0:13 | comment | added | Joel David Hamkins | Great job, François! Will someone kindly prove or refute the conjecture? | |
| Feb 25, 2013 at 22:50 | history | edited | François G. Dorais | CC BY-SA 3.0 |
typo
|
| Feb 25, 2013 at 22:42 | comment | added | David Roberts♦ | Should that be "...such that $d(A) \not\in A$ for all $A \in [\mathcal{P}(X)]^X$."? | |
| Feb 25, 2013 at 18:37 | history | edited | François G. Dorais | CC BY-SA 3.0 |
minor correction
|
| Feb 25, 2013 at 18:26 | history | answered | François G. Dorais | CC BY-SA 3.0 |