EMIS/ELibM Electronic Journals

Outdated Archival Version

These pages are not updated anymore. For the current production of this journal, please refer to http://www.jstor.org/journals/0003486x.html.

Annals of Mathematics, II. Series, Vol. 148, No. 3, pp. 803-893, 1998
EMIS ELibM Electronic Journals Annals of Mathematics, II. Series
Vol. 148, No. 3, pp. 803-893 (1998)

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home



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:

Electronic fulltext finalized on: 9 Sep 2001. This page was last modified: 22 Jan 2002.

© 2001 Johns Hopkins University Press
© 2001--2002 ELibM for the EMIS Electronic Edition
Metadata extracted from Zentralblatt MATH with kind permission