Finite Canonization

by Shelah. [Sh:564]
Commentationes Math Universitatis Carolinae, 1996
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 (for all ell in v)(i_ell = j_ell) . In this paper 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.

Back to the list of publications