Finite functions and the necessary use of large cardinals (Q1281440): Difference between revisions

The main result of the paper is that a certain finitary statement \({\mathcal B}\) can only be proved by using large cardinals. \({\mathcal B}\) is the finite version of the following assertion \({\mathcal A}\) (to which it is equivalent): Let \(k,p>0\), and let \(f_A:A\to A\) for each finite \(A\subseteq \mathbb{N}^k\) be such that for all \(x\in\mathbb{N}^k\), either \(f_A\subseteq f_{A\cup \{x\} }\) or \(\|f_A(y)\|>\|f_{A\cup\{x\}}(y)\|\) for some \(y\in \mathbb{N}^k\) with \(\|y\|>\|x\|\), where \(\|z\|= \max(z_1, \dots, z_k)\) for \(z\in\mathbb{N}^k\). Then for some \(A\) and \(E\) with \(|E|=p\) and \(E^k \subseteq A\), there are at most \(k^k\) elements \(t\) of \(A\) for which one can find \(z\in E\) such that \(f_A(z)=t\) and \(\|t\|<\min (z_1, \dots,z_k)\). \({\mathcal A}\) is provable from ZFC + ``for all \(n\), there exists an \(n\)-subtle cardinal''. This is shown by using the following key observation: Given \(k>0\), \(f_A: A\to A\) for each finite \(A\subseteq\mathbb{N}^k\), and an infinite cardinal \(\lambda\), there exists \(f:\lambda^k \to\lambda^k\) with the property that for every finite \(X\subseteq\lambda^k\), one can find a finite \(Y\subseteq \lambda^k\) such that \(X\subseteq Y\) and the graph of \(f\upharpoonright Y\) is order isomorphic to the graph of some \(f_A(B)\subseteq \mathbb{N}^{2k}\) is order isomorphic to \(C\subseteq \mathbb{N}^{2k}\) if there is an order-preserving bijection \(h\) from the field of \(B\) (i.e., the set of all coordinates of elements of \(B)\) onto the field of \(C\) such that \(h\) maps \(B\) onto \(C)\). Conversely, \({\mathcal A}\) implies that there exists a model \((W,R)\) of ZFC which satisfies the existence of \(n\)-subtle cardinals for every standard \(n\). The (rather technical) proof of this fact takes about two-thirds of the paper.