Finite functions and the necessary use of large cardinals

Harvey M. Friedman

Review from Zentralblatt MATH:

The main result of the paper is that a certain finitary statement ${\cal B}$ can only be proved by using large cardinals. ${\cal B}$ is the finite version of the following assertion ${\cal A}$ (to which it is equivalent): Let $k,p>0$, and let $f_A:A\to A$ for each finite $A\subseteq \bbfN^k$ be such that for all $x\in\bbfN^k$, either $f_A\subseteq f_{A\cup \{x\} }$ or $\|f_A(y)\|>\|f_{A\cup\{x\}}(y)\|$ for some $y\in \bbfN^k$ with $\|y\|>\|x\|$, where $\|z\|= \max(z_1, \dots, z_k)$ for $z\in\bbfN^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)$.

${\cal 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\bbfN^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 \bbfN^{2k}$ is order isomorphic to $C\subseteq \bbfN^{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, ${\cal 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.

Reviewed by P.Matet

Keywords: finite function; $n$-subtle cardinals; large cardinals

Classification (MSC2000): 03E05 03E55 03E30

Full text of the article:

• PDF file (521 kilobytes)