Description:
A proof that Form 284 impiies Form 61
Content:
In this note we prove that Form 284 (Every finitely solvable system of linear equations over a field has a solution in the field.) implies \(\forall n\in\omega, n\ge 2,C(\infty,n)\) (Form 61).
The proof is by mathematical induction on \(n\), starting with the case \(n=1\) which is clear. Assume that\(C(\infty,k)\) is true for every \(k \lt n\) and let \(X\) be a collection of pairwise disjoint \(n\) element sets. By the induction hypothesis there is a choice function \(h\) for the set \(Y = \{z: (\exists x\in X)(z\subseteq x)\) and \(1\le |z| \lt n\}\). Let \(p\) be the smallest prime that divides \(n\), say \( n = r\cdot p\). We define a system of linear equations over the field \({\Bbb Z}_p\) (the integers \(\mod p\)) as follows: We have one variable \(t_a\) for each \(a\in \bigcup X\) and for each \(x = \{a_1,\ldots,a_n\} \in X\) we include the equation \(t_{a_1} + \cdots + t_{a_n} = 1\). This system of equations is clearly finitely satisfiable hence by Form 284 it has a solution \(S:\{t_a : a\in\bigcup X\} \to {\Bbb Z}_p\). We now define a choice function \(f\) on \(X\). Let \(x = \{a_1, \ldots, a_n\}\) be an element of \(X\). The solution \(S\) determines a partition of \(x\) into the sets \(z_m = \{a\in x : S(t_a) = m\}\), \(0 \le m \le p-1\), some of which may be empty. However, there is no \(m\), \(0 \le m \le p-1\), for which \(x=z_m\) because the existence of such an \(m\) would mean that \(S(t_{a_1}) =\cdots = S(t_{a_n}) = m\). Hence \(S(t_{a_1}) + \cdots +S(t_{a_n}) = m\cdot n = m \cdot (r\cdot p) = 0\), which is a contradiction since \(S\) is a solution to the equation \(t_{a_1} + \cdots + t_{a_n} = 1\).
Let \(m_0\) be the least element of \({\Bbb Z}_p\) for which \(z_{m_0} \ne\emptyset\). Since \(z_{m_0} \ne x\), \(|z_{m_0}| < n\) and we may therefore define \(f(x) = h(z_{m_0})\).
Howard-Rubin number:
36
Type:
Proof
Back