Description:
Finite axioms of choice results
Content:
Finite axioms of choice:\(C(\infty ,n)\), \(C(LO,n)\), \(C(WO,n)\), \(C(\infty,\in Z)\),\(C(LO,\in Z)\), \(C(WO,\in Z)\) and \(C(\aleph_0,n)\), (forms
Form 45,
Form 33,
Form 47,
Form 46,
Form 120,
Form 48, and
Form 288 respectively) and generalizations have been studied extensively in Blass [1984b], Conway [1971], Gauntt [1970] and \cite{1968}, Mostowski [1958], Truss [1973a], Wi'sniewski [1972] and Zuckerman [1971]. Here is a summary of the results. (See Truss [1973a] for more details.)
Until further notice \(n\in\omega\) and \(Z\) is a finite subset of\(\omega \). The first two of the following conditions on the pair \((n,Z)\) were introduced by Mostowski in Mostowski [1958] and the third by Gauntt in Gauntt [1970].
Definitions:
| \(D(n,Z)\): |
For any subgroup \(G\) of \(S_n\) (the symmetric group on \(n\)) without fixed points, there is a subgroup \(H\) of \(G\) and proper subgroups \(K_1, \ldots, K_r\)of \(H\) such that \(\Sigma |H:K_i|\in Z\). |
| \(K(n,Z)\): |
For any subgroup \(G\) of \(S_{n}\) without fixed points,there is a subgroup \(H\) of \(G^{\omega }\) (the restricted direct product of countably many copies of \(G\)) and proper subgroups \(K_{1}, \ldots,K_{r}\) of \(H\) such that \(\Sigma |H:K_{i}| \in Z\) |
| \(L(n,Z)\): |
For any subgroup \(G\) of \(S_{n}\) without fixed points, there are proper subgroups \(K_{1}, \ldots , K_{r}\) of \(G\) such that \(\Sigma |G:K_{i}| \in Z\). |
Blass [1984b] has noticed that \(L(n,Z)\) is can be formulated as follows:
- Every group that can act without fixed points on an \(n\) element set can also act without fixed points on a \(k\) element set for at least one \(k\in Z\).
The equivalence of the two conditions is based on the following:
Suppose that \(H\) is a group and \(A\) is a set of cardinality \(k\) then \(H\) acts without fixed points on \(A\)\(\Leftrightarrow \) there are proper subgroups \(J_{1}, \ldots ,J_{r}\) of \(H\) (not necessarily distinct) such that \(\Sigma |H:J_{i}|=k\).
(Outline) \((\Rightarrow )\) If \(H\) acts without fixed points on \(A\), let \(A_{1},\ldots , A_{r}\) be the orbits of elements of A under the action. Then \(|A_{i}|\ge 2\) and \(\Sigma| A_{i}| = k\). If, for each \(i\), \(1 \le i \le r\) we choose \(a_{i}\in A_{i}\) and let \(J_{i}\) be the subgroup of \(H\) consisting of those elements that fix \(a_{i}\) then \(J_{i}\) is proper and \(| H:J_{i}| = | A_{i}| \).
\((\Leftarrow )\) Let \(A\) be the disjoint union of the leftcosets of the \(J_{i}\), \(1\le i\le r\). Then \(H\) acts on \(A\) without fixed points.
|
|
\(D(n,Z) \Leftrightarrow \hbox{ZF}\vdash C(\infty ,Z) \rightarrow C(\infty ,n)\).
(\(\Leftarrow \) Gauntt [1970], \(\Rightarrow \) Mostowski [1958])
|
|
\(L(n,Z) \Leftrightarrow \hbox{ZF}\vdash C(WO,Z) \rightarrow C(WO,n)\).
(Gauntt [1968])
|
|
\(K(n,Z) \Leftrightarrow \hbox{ZF} \vdash C(\infty ,Z) \rightarrow C(WO,n)\).
(\(\Rightarrow \) Truss [1973a], \(\Leftarrow \) Mostowski [1958])
|
|
\(L(n,Z) \Leftrightarrow \hbox{ZF} \vdash C(LO,Z) \rightarrow C(LO,n)\).
(Truss [1973a])
|
|
\(ZF \vdash C(LO,Z) \rightarrow C(WO,n)\Leftrightarrow \hbox{ZF} \vdash C(WO,Z) \rightarrow C(WO,n)\).
(Truss [1973a])
|
|
\(ZF \vdash C(\infty ,Z) \rightarrow C(LO,n)\Leftrightarrow \hbox{ZF} \vdash C(\infty ,Z) \rightarrow C(\infty ,n)\).
(Truss [1973a])
|
Blass [1984b] has introduced the following forms, each depending on the set \(I\):
- \(C(I,n)\): Every \(I\) indexed family of \(n\) element sets has a choice function. (Depends on \(n \in \omega\).)
- \(C(I,\in Z)\): \((\forall n \in Z)( C(I,n)\)). (Depends on finite \(Z \subseteq \omega\).)
and has shown
\(L(n,Z) \Leftrightarrow \hbox{ZF}\vdash(\forall I)( C(I,\in Z) \rightarrow C(I,n) )\).
We now turn to some generalizations of the finite axioms of choice due to Truss [1973a]. Some definitions are necessary. For any set \(X\) let \(e(X)\) be the set of non-empty finite subsets of \(X\) and define \(e(0,X) = X\) and \(e(n+1,X) = e(e(n,X))\). (We assume that\(e(k,X)\cap e(j,X)=\emptyset\) for \(j \neq k\). If this is not the case, we replace \(e(n,X)\) by \(\{e(n,X) \} \times e(n,X)\) for each \(n\in\omega\).) Let \(V(m,X)\) be the set of equivalence classes on \(e(m,X)\) under the equivalence relation \(a R b\) iff \(\exists\) a permutation \(\phi\) of \(X\) such that (the extension of) \(\phi (a)\) = b. If \(\left| X \right|=n\in\omega\) then there is a natural 1-1 correspondence between \(V(m,n)\) and \(V(m,X).(\nu\rightarrow f(\nu )\) where \(f\) is (the extension of) any one to one correspondence between \(X\) and \(n\).) For \(\nu\in V(m,n)\) we denote the corresponding equivalence class in \(V(m,X)\) by \(\nu(X)\). Let \(V =\bigcup \{V(m,n): m,n\in\omega, n\neq 0\}\). For any \(Z\subseteq V\), Truss defines the following choice axioms: (\(Z\) no longer denotes a finite subset of \(\omega\) .)
- \(C(\infty,Z)\): For any set \(Y\), \(\{\nu(X):\nu\in Z\) and\(X\in Y\) and \(\nu\in V(m,|X|)\) for some \(m\in\omega\}\) has a choicefunction.
- \(C(LO,Z)\): For any linearly ordered set \(Y\), same as above.
- \(C(WO,Z)\): For any well ordered set \(Y\), same as above.
- If \(\nu\in V\), then we let \(C(\infty,\nu)\), \(C(LO,\nu)\) and \(C(WO,\nu)\) denote respectively \(C(\infty,\{\nu\})\), \(C(LO,\{\nu\})\) and\(C(WO,\{\nu\})\).
For example, if \(Z = \{\nu \}\) where \(\nu \) is the set of all pairs of elements of \(n\) then \(C(\infty,\{\nu\})\equiv C(\infty,\nu)\) is "For every set \(Y\) of \(n\) elements sets there is a function \(f\) such that \(\forall X \in Y, f(X)\) is a two element subset of X." Necessary and sufficient conditions are given for
- \(ZF \vdash C(\infty ,Z_{1}) \wedge C(\hbox{LO},Z_{2})\wedge C(WO,Z_{3}) \rightarrow C(\infty ,\nu )\)
- \(ZF \vdash C(\infty ,Z_{1}) \wedge C(LO,Z_{2})\wedge C(WO,Z_{3}) \rightarrow C(LO,\nu )\) and
- \(ZF \vdash C(\infty ,Z_{1}) \wedge C(LO,Z_{2})\wedge C(WO,Z_{3}) \rightarrow C(WO,\nu )\).
They are:
| \(A(Z,\nu)\) |
If \(\nu \in V(m,n)\) and \(G\) is a group of permutations of \(n\) which moves every member of \(\nu \) then there is an \(X \in e(k,n)\) for some \(k\) such that there is and a \(w \in Z\) such that \(w \in V(n',|X|)\) for some \(n'\) and for each \(\zeta\in w(X)\), \(H(X) \cap G\) is not a subset of \(H(\zeta )\).(If \(\zeta \in e(n,X)\) then \(H(\zeta )=\{\sigma\in S(X):\sigma(\zeta) = \zeta\}\).) |
| Theorem> |
\(A(Z_1,\nu)\) is equivalent to (A). |
| \(B(Z_{1},Z_{2},\nu )\): |
If \(G\) is a group of permutations of \(n\) (where \(\nu \in V(j,n)\) for some \(j\)) which moves every member of \(\nu \), there is an \(X\) such that either
- \(X \in e(k,n)\) for some \(k\), and there is some \(w \in Z_{1}\) a such that \(w \in V(k,|X |)\) for some \(k\) and for each \(\zeta \in w(X)\), \(H(X) \cap G\)is not a subset of \(H(\zeta )\) or
- \(X \in e(k,n\cdot m)\) for some \(k\) and \(m \in \omega \) and there is a \(w\in Z_{2}\) such that \(w \in V(j,| X| )\) for some \(j \in \omega\) and for each \(\zeta \in w(X)\), \(G^{m}\) is not a subset of \(H(\zeta )\).
|
| Theorem: |
\(B(Z_{1},Z_{2},\nu )\) is equivalent to (B). |
| \(C(Z_{1},Z_{2},\nu )\): |
If \(G\) is a group of permutations of \(n\) (where \(\nu\in V(j,n)\) for some \(j\in\omega\)) which moves every member of \(\nu \), then there is an \(X\in e(j,n\cdot m)\) for some\(j, m \in \omega \) such that either
- for some \(w \in Z_{1}, w \in V(j,|X |)\) for some \(j\in\omega\) and for each \(\zeta\in w(X)\), \(G^{m}\cap H(X)\) is not a subset of \(H(\zeta)\)or
- for some \(w \in Z_{2}\), \(w \in V(j,| X| )\) for some \(j \in \omega \) and \(H(X) = G^{m}\) and for each \(\zeta\in w(X)\), \(G^{m}\) is not a subset of \(H(\zeta)\).
|
| Theorem: |
\(C(Z_{1},Z_{2}\cup Z_{3},\nu)\) is equivalent to (C). |
See Note 73 for adding dependent choice to the independence results above.
The finite axioms of choice have been generalized in Conway [1971] as follows:
Definition: Let \(k\) be a natural number.
- An ordered \(k\)-tuple \((A,B,C,\ldots)\) of disjoint finite sets of cardinalities \(a,\ b,\ \ldots\) respectively is called an \((a,b,c,\ldots)\) set.
- \([a,b,c,\ldots]\) is the axiom: For every collection of \((a,b,c,\ldots)\) sets there is a function \(f\) defined on the collection such that \(f(A,B,C,\ldots) \in A \cup B \cup C \cup \cdots\).
- \(\langle a,b,c,\ldots \rangle\) is the additive semi-group generated by \(a,\ b,\ c,\ldots\) (I. e., the closure of \(\{ a,b,c, \ldots\}\) under addition.)
- If \(S = \langle a, b, c,\ldots\rangle\) then \([S]\) denotes the axiom \([a,b,c,\ldots]\). (by result I below, if \(\langle a,b,c,\ldots\rangle \) and \(\langle \alpha,\beta,\gamma \ldots \rangle\) are equal then \([a,b,c,\ldots]\) and \([\alpha,\beta,\gamma, \ldots]\) are equivalent.)
- If \(G\) is any finite group, \(\langle G \rangle \subseteq {\Bbb N}\) is the semi-group generated by the indices in \(G\) of all proper subgroups of \(G\).
(Some parts due to Mostowski)
- If \(\langle \alpha, \beta, \gamma, \ldots \rangle \subseteq\langle a, b, c,\ldots \rangle \) then \([\alpha, \beta, \gamma, \ldots]\Rightarrow [a,b,c,\ldots]\).
- Let \(S_1,\ldots,S_N,\ S\) be semi-groups (\(\subseteq {\Bbb N}\)),then for the implication\(\)[S_1] \land [S_2] \land \dots \land [S_N] \Rightarrow [S] \tag *\(\)to hold it suffices that every group \(G\) with \(S \subseteq\langle G \rangle \) has some subgroup \(H\) for which \(S_i \subseteq\langle H \rangle\) for some \(i\), \(1 \le i \le N\).
- (Mostowski) For (\(*\)) to hold it is necessary that every Abelian group \(G\) with \(S \subseteq \langle G \rangle\) have some subgroup\(H\) with \(S_i\subseteq\langle H\rangle\) for some \(i\), \(1\le i\le N\).
- The condition of II is necessary and sufficient for effective implication, that is, for the existence of a formula \(F(f_1,\ldots,f_N)= f\) which defines a choice function \(f\) for the class of all \(S\) sets whenever we substitute such choice functions for the classes of all \(S_1\)sets, \(S_2\) sets, \(\ldots\), \(S_N\) sets for \(f_1,\ f_2,\ \ldots,\ f_N\).
The following are proved in Wi'sniewski [1972]:
Let \(P\) be the additive semi-group of positive integers generated by a set \(Z\) of prime numbers (\(P\) consists of sums of the form \(p_1+ p_2 + \cdots + p_k\) where \(p_i,\ i=1, \ldots, k\) are in\(Z\).) Then there is a model \(\cal N\) of \(ZF^0\) in which \(C(\infty, n)\) is true for all \(n \not\in P\) and \(C(\aleph_0,n)\) is false for all \(n\in P\).
Let \(G\) be a finite group, \(Q(G)\) the additive semi-group of positive integers generated by the indices of proper subgroups of \(G\) in \(G\) and \(R(G)\) the additive semi-group of positive integers generated by the orders of non-identity elements of \(G\). Then there is a model \(\cal N\) of ZF\(^0\) in which \(C(LO,n)\) is true for all \(n\not\in Q(G)\), \(C(\infty,n)\) is false for all \(n \not \in R(G)\) and\(C(\aleph_0,n)\) is false for all \(n \in Q(G)\).
Let \(p\) and \(q\) be primes such that \(p_1 =(p^q-1)/(p-1)\) is prime. Then there is a model \(\cal N\) of ZF\(^0\) in which
- \(C(LO,n)\) is true for \(n\) of the form \(kp_1 + rp^q\)
- \(C(\infty,n)\) is false for \(n\) of the form \(kp + rq\)
- \(C(\aleph_0,n)\) is false for \(n\) of the form \(kp_1 + rp^q\).
If for every prime \(p\) there are infinitely many primes of the form \((p^q - 1)/(p-1)\) then there is a model \(\cal N\)of \(ZF^0\) where \(C(\aleph_0,n)\) is true for every \(n\) and \(C(\infty,n)\)is false for every \(n > 1\).
Note: The Mersenne Prime conjecture (there are infinitely many primes of the form \(2^n - 1\)) is a special case of the hypotheses of this theorem.
Along the same lines Zuckerman [1971] proves
Let \(Z\) be any set of primes and \(P\) the additive semigroup of positive integers generated by \(Z\). Then there is a model \(\cal N\) of \(ZF^0\) in which Form 67 (the axiom of multiple choice,\(MC(\infty,\infty)\)) is true and for every \(n \in \omega,\ n >1\),\(C(\infty,n)\) is true if and only if \(n \in P\).
Howard-Rubin number:
15
Type:
Summary of definitions and results
Back