Notes

Description:

We give proofs due to \ac{A.~Rubin} that\(MC(\infty,\infty,\hbox{ even})\) (334) is true in \(\cal N2\) and\(MC(\infty,\infty,\hbox{ odd})\) (333) is true in \(\cal N2^*(3)\).\proclaim{Theorem 1} \(MC(\infty,\infty,\hbox{ even})\) is true in \(\cal N2\).

Content:

We give proofs due to A. Rubin that \(MC(\infty,\infty,\hbox{ even})\) (Form 334) is true in \(\cal N2\) and \(MC(\infty,\infty,\hbox{ odd})\) (Form 333) is true in \(\cal N2^*(3)\).

1. \(MC(\infty,\infty,\hbox{ even})\) (Form 334) is true in \(\cal N2\). Let \(M\) be a non-empty set in \(\cal N2\), each of whose elements has at least two elements. The group \(\cal G\) in \(\cal N2\) is Abelian and each of its elements has order two. Let \(\cal F\) be the filter determined by \(S\), the set of finite subsets of the set of atoms, \(A\). (\(\cal F\) is generated by the set of all subgroups \(H\) of \(\cal G\) such that there is an \(E\in S\) such that \(H\) fixes \(E\) pointwise.) The filter \(\cal F\) is in the model because each element in \(\cal G\) has order two so \(\cal F\) has null support. In fact, \[ \hspace{-2in} (1) \hspace{2in}(\forall H\in\cal F)(\forall\sigma\in H)\sigma(H)=H. \] Define a linear ordering \(\le\) on \(\cal F\) which extends \(\supseteq\), that is, if \(H_1, H_2\in\cal F\) and \(H_1\supseteq H_2\), then \(H_1\le H_2\). The relation \(\le\) is in the model because of (1). (In fact, \(\le\) is a well ordering, but we do not need this.) Let \(W\) be the set of all sets in the model that have null support. Every permutation in \(\cal G\) leaves \(W\) pointwise fixed so\(W\) can be well ordered by a relation \(R\).
\( \hspace{0.5in} \)Suppose \(X\in M\). We shall give an algorithm to construct a subset of \(X\) whose cardinality is a power of two. Let \(Y=\{\cal G''\{x\}:x\in X\}\). Each element of \(Y\) has null support so \(Y\) can be well ordered by \(R\). Moreover, each element of \(Y\) is finite. (In fact, the cardinality of each element of \(Y\) is a power of two because \(|\cal G''\{x\}| = |\cal G/\hbox{sym}_{\cal G}(x)|\), where \(\hbox{sym}_{\cal G}(x)=\{\sigma\in\cal G: \sigma(x)=x\}\).) Let \(y\) be the \(R\)-first element of \(Y\) and let \(x=y\cap X\). Let fix\(_{\cal G}(x)\) be the group of all \(\sigma\in\cal G\) that fixes \(x\) pointwise and let \[J=\{H\in\cal F: \hbox{fix}_{\cal G}(x)\subseteq H \; \& \; (\exists z\in x)H''\{z\}\subseteq x\}\] Since \(\hbox{fix}_{\cal G}(x)\in J\), \(J\ne\emptyset\). Moreover,\(J\) is finite and is linearly ordered by \(\le\). Let \(H_0\) be the \(\le\)-first element of \(J\). We claim that if \(z, w\in x\) and, \(H_0''\{z\}\) and \(H_0''\{w\}\) are both subsets of \(x\), then \(H_0''\{z\} = H_0''\{w\}\). The reason for this is as follows. By the definition of \(y\) (\(x\subseteq y\)), there is a \(\sigma\in\cal G\) such that \(\sigma(z)=w\). Let \(K=H_0\cup H_0\sigma\). Then \(K''\{z\}=H_0''\{z\}\cup H_0''\{w\}\subseteq x\). We have \(\hbox{fix}_{\cal G}(x)\subseteq H_0\subseteq K\) so \(K\in J\), and \(K\le H_0\). However, \(H_0\) is the \(\le\)-first element of \(J\), so \(K=H_0\). Consequently, \(H_0''\{z\} = H_0''\{w\}\).
\( \hspace{0.5in} \)Then, for each \(X\in M\),  we choose the unique \(H_0''\{z\}\) which is a subset of \(x\subseteq X\).  \(H_0''\{z\}\) has the same cardinality as the factor group, \(H_0/\hbox{sym}_{H_0}(z)\), which is a power of two.
\( \hspace{0.5in} \)Let \(Z=\{u\subseteq X: X\in M\}\) and let \(f\) be a multiple choicefunction on \(Z\) such that for each \(u\in Z\), \(|f(u)|\) is a power of 2. We define a multiple choice function \(g\) on \(M\) satisfying \(MC(\infty,\infty,\hbox{ even})\) as follows. Suppose \(X\in M\). If \(|f(X)|>1\), then \(g(X)=f(X)\). If \(|f(X)|=1\), consider \(u=f(X-\{f(X)\})\). If \(|u|=1\),  then define \(g(X)=\{f(X),u\}\); and if \(|u|>1\), define \(g(X)=u\). 2. \(MC(\infty,\infty,\hbox{ odd})\) (Form 333) is true in \(\cal N2^*(3)\) In this model the group \(\cal G\) is Abelian and each element has order three. Let \(M\) be a set of non-empty sets. We shall show that there is a multiple choice function \(f\) on\(M\) such that for each \(X\in M\), \(|f(X)|\) is a power of three. The proof is the same as the proof of \(MC(\infty,\infty,\hbox{ even})\) (Form 334) in Theorem 1 above up to and including the definition of \(x=y\cap X\). Then we proceed as follows. For each \(u\in x\), let \(Q(u)=\{\sigma\in\cal G: \sigma(u)\in x\}\).  Each \(Q(u)\) has null support and is therefore in\(W\). Let \(Q_0\) be the \(R\)-first element of \(\{Q(u): u\in x\}\) and let \(z=\{u\in x: Q(u)=Q_0\}\). We claim that the cardinality of \(z\)is a power of three. Fix \(u\in z\) and let \(K=\{\sigma\in\cal G:\sigma(u)\in z\}\). \(K\) is a subgroup of \(\cal G\) because \(K=\{\sigma\in\cal G: (\sigma^{-1})''Q_0=Q_0\}\).  Therefore, \(|z|=|\cal G/\hbox{fix}_{\cal G}(u)|\) which is a power of three.

Howard-Rubin number: 93

Type: Proofs and statements

Back