Timeline for Cantor's diagonal argument and ZF
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 25, 2013 at 18:26 | answer | added | François G. Dorais | timeline score: 7 | |
| Feb 21, 2013 at 9:48 | comment | added | Asaf Karagila♦ | David, the order defined by surjection is commonly written as $|A|\lt^\ast|B|$. I am actually very interested in the well-foundedness of cardinals without choice; and in fact its relation to the problem of infinite antichains of cardinals (in $\leq^\ast$ more than in $\leq$ to be fair). In the presence of countable choice the two problems are equivalent, but I still don't know what happens when countable choice fails (if there is a D-finite set then there is a decreasing chain, and thus an antichain, but if there is no DF sets, I don't know much yet). | |
| Feb 21, 2013 at 4:52 | comment | added | David Feldman | Asaf, what interests me is the ambiguity I find, absent AC, around the word "decreasing." $|A| < |B|$ could mean, minimally, an injection $A\rightarrow B$ (or merely a surjection $B \rightarrow A$), plus the mere absence of any injection $B \rightarrow A$ (or surjection from $A\rightarrow B$). Instead of these "mere absence" conditions, we might demand a uniform supply of witnesses to the failure of any map (which AC would supply if we had it). My comment gives a proof that AC does actually preclude infinite decreasing (in one very strong sense) cardinals. One might seek variations. | |
| Feb 21, 2013 at 2:28 | comment | added | Asaf Karagila♦ | David, it is actually unknown whether or not the well-foundedness of cardinals is equivalent to the axiom of choice. All we know that the cardinals can get very wild, including infinite decreasing sequences. But we yet to know about a model where choice fails and there is no decreasing sequence of cardinals (and even more, decreasing cardinality $\subseteq$ chain of sets); nor we know about a proof that there are no such models. | |
| Feb 21, 2013 at 1:15 | history | edited | David Feldman | CC BY-SA 3.0 |
edited body
|
| Feb 21, 2013 at 0:49 | comment | added | David Feldman | ...this condition. You're right...Cantor's proof gives more, but I wanted to keep the effective burden as light as possible. If in addition $d_n(i)$ depends only on the image of $i$, then an argument along the lines of Ricky Demer's leads to a contradiction (because one gets a nested sub family with a well-ordering). I don't see how to get a contradiction dropping the depends-only-on-image condition, even if one requires witnesses of non-surjectively for all functions, not just injections. So naturally I wondered if any variation on Cantor could meet my side condition. | |
| Feb 21, 2013 at 0:43 | comment | added | David Feldman | Hi Joel...Here's what I was originally thinking about (this may become it's own question). ZFC makes cardinals well-ordered. Thus, ($\ast$) given sets $S_1 \supset S_2 \supset \cdots$ there must exist $n$ and a surjection $p:S_{n+1} \rightarrow S_n$. Surely ($\ast$) fails in ZF; I wonder how close one can come. One idea: from an effective guarantee that every injection $h:S{n+1} \rightarrow S_n$ misses an element of $S_n$ implemented by a function $d_n:{\rm Injections}(S_{n+1},S_n)\rightarrow S_n$ such that $d_n(i)\not\in i(S_{n+1})$,try to derive a contradiction. Cantor's proof inspires . | |
| Feb 19, 2013 at 23:34 | comment | added | Joel David Hamkins | David, Cantor's argument does not use that $i$ is injective, for we can diagonalize against any countable enumeration of reals, even if there are repetitions. Was there a reason you add that restriction? | |
| Feb 19, 2013 at 17:25 | history | edited | Asaf Karagila♦ |
edited tags
|
|
| Feb 19, 2013 at 4:44 | vote | accept | David Feldman | ||
| Feb 19, 2013 at 4:13 | answer | added | Joel David Hamkins | timeline score: 5 | |
| Feb 19, 2013 at 4:02 | comment | added | Noah Schweber | Yes, I put in my comment that I don't think that answer solves this question; still, it does make me suspect that ZF is already not enough for $X=\mathbb{N}$. | |
| Feb 19, 2013 at 4:01 | answer | added | user5810 | timeline score: 14 | |
| Feb 19, 2013 at 4:00 | comment | added | Joel David Hamkins | Noah, I see you and I were thinking alike! But that question was about Borel maps, and this question is more inclusive. | |
| Feb 19, 2013 at 4:00 | comment | added | Noah Schweber | @Joel: beat you to it! | |
| Feb 19, 2013 at 3:58 | comment | added | Joel David Hamkins | Different but related question: mathoverflow.net/questions/47185/… | |
| Feb 19, 2013 at 3:57 | comment | added | Noah Schweber | I suspect ZF doesn't even prove the existence of such a map in the case $X=\mathbb{N}$; see Joel David Hamkins' answer to mathoverflow.net/questions/47185/…. I don't think that answer answers this question, but it does make me suspect that in the smallest nontrivial case we've already gotten beyond ZF. | |
| Feb 19, 2013 at 3:30 | history | asked | David Feldman | CC BY-SA 3.0 |