No decreasing sequence of cardinals (Q283108): Difference between revisions

For sets \(x\) and \(y\), \(x\prec y\) means there is a one-to-one function \(g: x\rightarrow y\), but no one-to-one function \(h: y\rightarrow x\). NDS is the following principle: there is no function \(f\) on \(\omega\) such that \(\forall n\in\omega\; f(n+1)\prec f(n)\). A venerable open question asks: Does NDS imply AC? The authors investigate the set theoretic strength of NDS in set theory without the Axiom of Choice (AC). Two variants of AC appear in this article: \(\mathrm{AC}^{\mathrm{LO}} \) and \(\mathrm{AC}^{\mathrm{WO}}\). The first is the restriction of AC to linearly ordered families of non-empty sets, and the second is the restriction of AC to well-ordered families of non-empty sets. In ZF, AC and \(\mathrm{AC}^{\mathrm{LO}}\) are equivalent, but they are not equivalent in ZFA (Zermelo-Fraenkel set theory with atoms) [\textit{P. E. Howard} and \textit{J. E. Rubin}, Fundam. Math. 97, 111--122 (1977; Zbl 0365.02051)]. Using FM models, one old and one new, the authors show that in ZFA, \(\mathrm{AC}^{\mathrm{LO}} \) does not imply NDS. Thus, it is also the case that \(\mathrm{AC}^{\mathrm{WO}}\) does not imply NDS in ZFA. With the aid of a known symmetric model of ZF, the authors also show that \(\text{AC}^{\text{WO}}\) does not imply NDS in ZF. This particular result leads to the conclusion that ``Every Dedekind finite set is finite'' (DF = F) does not imply NDS. (A theorem of Tarski shows that NDS implies DF = F.) Finally, using the Halpern/Howard permutation model, the authors establish that ``\(\forall m \text{ infinite }\, m+m=m\)'' does not imply NDS in ZFA.