Description:
A proof that Form 409 implies Form 62.
Content:
Proof: Let \(X\) be a set of disjoint finite sets and construct the graph\ ((G,\Gamma) \) where \(G=\bigcup X\) and for \(t\in G\), if \(t\in y\in X\) then
\(\Gamma(t) = y\setminus \{t\}\). (So if \(y\in X\) there is an edge from every element of \(y\) to every other element of \(y\).) Let \(K=\{0,1\}\)
and define the function \(T:\cal P(K) \to \cal P(K)\) by \(T(\{0\}) =\{1\}\), \(T(\{1\}) = \{0\}\), \(T(\emptyset) = K\) and \(T(K) =K\). The hypotheses
of Form 409 are satisfied for\((G,\Gamma)\) and \(K\). Here is the argument:
If \(A\) is a finite subgraph of \(G\)(I.e., \(A\subseteq G\)), the \(A\) can be written as the disjoint union
\[A = (A\cap y_1)\cup \cdots (A\cap y_n),\]
where \(y_i\in X\) and \(y_i\cap A\ne \emptyset\), for \(i = 1,\ldots, n\). Choose one element \(t_i\) in each of the sets \(A\cap y_i\) for
\(i=1,\ldots n\) and define \(\phi_A:A\to K\) by \(\phi_A(t_i) = 0\) for \(i = 1,\ldots,n\) and \(\phi_A(t) = 1\) for other elements \(t\in A\). For
the proof that \(\phi_A(t)\in T(\phi_A(\Gamma_A(t)))\) for all \(t\in A\),(\(\Gamma_A\) is \(\Gamma\) restricted to \(A\)) assume that \(t\in A\cap
y_i\) and consider two cases:
Case 1: \(|A\cap y_1| = 1\). In this case \(t=t_i\) so \(\phi_A(t) =\phi_A(t_i) = 0\). Also in this case \(\Gamma_A(t) = \emptyset\) so \(T(\phi_A(\Gamma_A(t))) = T(\phi_A(\emptyset)) = T(\emptyset)= K = \{ 0,1\}\), so \(\phi_A(t)\in T(\phi_A(\Gamma_A(t)))\).
Case 2: \(|A\cap y_i| >1\). In this case let \(s\) be an element of \(A\cap y_i\) different from \(t_i\). If \(t=t_i\) then \(s\in\Gamma_A(t_i)=\Gamma_A(t)\) so \(\phi_A(s)\in \phi_A(\Gamma_A(t))\)so \(1\in \phi_A(\Gamma_A(t))\). By the definition of \(T\) it follows that \(0\in T(\phi_A(\Gamma_A(t)))\). But \(\phi_A(t) =\phi_A(t_i) = 0\). On the other hand if \(t\ne t_i\) then\(t_i\in \Gamma_A(t)\) so \(\phi_A(t_i) = 0\in\phi_A(\Gamma_A(t))\). Using the definition of \(T\) again, this means that \(1\in T(\phi_A(\Gamma_A(t)))\). But \(\phi_A(t) = 1\).
Therefore by Form 409, there is a function \(\phi_A : G\to K\) such that for all \(t\in G\),\(\phi(t) \in T(\phi(\Gamma(t)))\). We now argue that for each\(y\in X\), \(\phi\) restricted to \(y\) cannot be constant. (By contradiction.) Assume \(\forall t\in y\), \(\phi(t) = 0\). Then for any \(t\in y\), \(T(\phi(\Gamma(t))) = T(\{0\}) = \{1\}\). But then \(\phi(t)= 0 \notin T(\phi(\Gamma(t)))\). A similar argument shows that \(\phi(t) = 1\) for all \(t\in y\) is impossible. We can now get a Kinna-Wagner function for \(X\) by defining \(f(y) = \{ t\in y : \phi(t) = 0\}\) for each \(y\in X\). \25FBHoward-Rubin number: 152
Type: Proof
Back