Description:
Prove forms [1 F] and [1 CC] are equivalent to Form 1
Content:
Prove forms [1 F] and [1 CC] are equivalent to Form 1
Form [1 F] is `` For all ordinals \(\alpha\), \(DC(\aleph_{\alpha})\): Given a relation \(R\) such that for every subset \(Y\) of a set \(X\) with \(|Y| < \aleph_{\alpha}\), there is and \(x \in X \) with \(Y\mathrel R x\), then there is a function \(f:\aleph_{\alpha} \to X\) such that \(\forall\beta < \aleph_{\alpha}\), \()\{f(\gamma):\gamma < \beta\}\mathrel R f(\beta)$\).)''. It is clear that Form 1 implies [1 F]. To prove the converse, well order \(X\) by using \(Y\mathrel R x\Leftrightarrow x\not\in Y\) and use \(DC(\aleph_{\alpha})\) for sufficiently large \(\aleph_{\alpha}\).
The question of the equivalence of [1 CC] and 1 was first raised by
K. Keremedis. Form [1 CC] is the conjunction of
\(PC(\aleph_0,\hbox{odd},\infty)\):
``Every denumerable family of odd sized (finite) sets has an
infinite subfamily with a choice function.'' and \(MC_{\omega^+}\):
``For every natural number \(n \ge 1\) and for
every set of non-empty sets, there is a function \(f\) such that for
each \(u\in x\), \(f(u)\) is a non-empty finite subset of \(u\) such
that \(|f(u)|\) and \(n\) are relatively prime.''
We first prove that \(PC(\aleph_0,\hbox{odd},\infty)\) implies ``every denumerable family of odd sized sets has a choice function''. Let \(X = \{x_n : n\in\omega\}\) be a denumerable family of odd sized sets. For each \(n\in\omega\), let \(y_n = \{f : f\) is a choice function for \(\{x_i : i \le n \}\,\}\). \(|y_n| = |x_1|\cdots |x_n|\) and is therefore odd. Applying \(PC(\aleph_0,\hbox{odd},\infty)\) to \(Y = \{ y_n : n\in \omega\}\) gives an infinite subset \(Y'\) of \(Y\) with a choice function \(F\). Then defining \(G\) by \(G(x_n) = F(y_k)(x_n)\) where \(k\) is the least natural number \(\ge n\) for which \(y_k\in\hbox{dom}(F)\) gives a choice function for \(X\).
To prove that \(PC(\aleph_0,\hbox{odd},\infty)\) and \(MC_{\omega^+}\) imply \(AC\). It suffices to show that \(\forall n\in\omega, C(\infty,n)\) (Form 61) \(+ MC\) (Form 67) \(+ MC_{\omega^+} + \)``Every denumerable family of odd sized sets has a choice function'' implies \(AC\). This is because \(MC_{\omega^+}\) is equivalent to \(\forall n\in\omega, C(\infty,n) + MC\) (by lemma 3 of Howard/Rubin/Rubin [1997] and because \(PC(\aleph_0,\hbox{odd},\infty)\) is equivalent to ``Every denumerable of odd sized sets has a choice function''
Let \(X\) be a set of pairwise disjoint, non-empty sets. By \(MC\) there is an \(f: X \to \cal P(\bigcup X)\) such that \(\forall x\in X\), \(\emptyset \ne f(x)\subseteq x\) and \(|f(x)|\) is finite. For each \(n\in\omega\), let \(Y_n = \{x\in X : |f(x)| = n\}\). By \(C(\infty,n)\), \(Y_n\) has a choice function (even if \(Y_n\) happens to be empty, but it might be clearer to exclude \(n\) for which \(Y_n\) is empty). Therefore the set \(C_n = \{g : g\) is a choice function for \(Y_n\}\) is non-empty. By \(MC_{\omega^+}\) there is a function \(F\) defined on \(\omega\) such that \(F(n)\) is an odd sized subset of \(C_n\) for each \(n\in\omega\). Since every denumerable of odd sized sets has a choice function, there is a function \(G\) defined on \(\omega\) such that for every \(n\in\omega\), \(G(n)\in F(n)\). We can now define a choice function \(Ch\) for \(X\) by \(Ch(x) = G(n)(x)\) where \(|f(x)| = n\).
Howard-Rubin number: 133
Type: proof of equivalencies
Back