Saharon Shelah
Finite canonization

Comment.Math.Univ.Carolinae 37,3 (1996) 445-456.

Abstract:The canonization theorem says that for given $m,n$ for some $m^*$ (the first one is called $ER(n;m)$) we have

{ for every function $f$ with domain $[{1,...,m^*}]^n$, for some $A \in [{1,...,m^*}]^m$, the question of when the equality $f({i_1,...,i_n}) = f({j_1,...,j_n})$ (where $i_1 <...< i_n$ and $j_1 <...j_n$ are from $A$) holds has the simplest answer: for some $v \subseteq \{1,...,n\}$ the equality holds iff $\bigwedge _{\ell \in v} i_\ell = j_\ell $. }

We improve the bound on $ER(n,m)$ so that fixing $n$ the number of exponentiation needed to calculate $ER(n,m)$ is best possible.

Keywords: Ramsey theory, Erd\"os-Rado theorem, canonization
AMS Subject Classification: 05, 05C55

PDF