# The Engelking-Karlowicz theorem, and a useful corollary

Theorem (Engelking-Karlowicz, 1965). For cardinals $\kappa\le\lambda\le\mu\le 2^\lambda$, the following are equivalent:

1. $\lambda^{<\kappa}=\lambda$;
2. there exists a collection of functions, $\langle f_i:\mu\rightarrow\lambda\mid i<\lambda\rangle$, such that for every $X\in[\mu]^{<\kappa}$ and every function $f:X\rightarrow\lambda$, there exists some $i<\lambda$ with $f\subseteq f_i$.

Proof. (2)$\Rightarrow$(1) Suppose $\langle f_i:\mu\rightarrow\lambda\mid i<\lambda\rangle$ is a given collection. Then $$|\{ f_i\restriction\theta\mid i<\lambda,\theta<\kappa\}|\le\lambda<\lambda^{<\kappa},$$
so there must exists some $f\in{}^{<\kappa}\lambda$ with $f\nsubseteq f_i$ for all $i<\lambda$.

(1)$\Rightarrow$(2) We follow a proof due to Shelah. Put:
$$W:=\{ (a,\mathcal A,g)\mid a\in[\lambda]^{<\kappa},\mathcal A\in[a]^{<\kappa}, g\in{}^{\mathcal A}\lambda\}.$$
Then $|W|=\lambda^{<\kappa}=\lambda$, and we may fix an enumeration
$$W=\{ (a_i,\mathcal A_i,g_i)\mid i<\lambda\}.$$
By $\mu\le 2^\lambda$, let $\langle B_\alpha\mid \alpha<\mu\rangle$ be a sequence of distinct subsets of $\lambda$.
For all $i<\lambda$, we now define $f_i:\mu\rightarrow\lambda$, by letting for all $\alpha<\mu$:
$$f_i(\alpha)=\begin{cases}g_i(a_i\cap B_\alpha),&a_i\cap B_\alpha\in\mathcal A_i\\0,&\text{otherwise}\end{cases}.$$
Finally, suppose that a set $X\in[\mu]^{<\kappa}$ and a function $f:X\rightarrow\lambda$ are given.
For all distinct $\alpha,\beta\in X$, pick $x(\alpha,\beta)\in B_\alpha\Delta B_\beta$.
Put $a=\{ x(\alpha,\beta) \mid \alpha,\beta\in X, \alpha\not=\beta\}$. Then, $|a|<\kappa$ and for all distinct $\alpha,\beta\in X$, we have $a\cap B_\alpha\not=a\cap B_\beta$.
It follows that $|\mathcal A|=|a|$, where $\mathcal A:=\{ a\cap B_\alpha\mid \alpha\in X\}$. It also follows that we may well-define a function $g:\mathcal A\rightarrow\lambda$ by letting:
$$g(a\cap B_\alpha):=f(\alpha),\quad(\alpha\in X).$$
Pick $i<\lambda$ such that $(a,\mathcal A,g)=(a_i,\mathcal A_i,g_i)$. Then, $f\subseteq f_i$. $\square$

Corollary (folklore). Assume CH.
Then there exists a function $G:[\omega_2]^{<\omega_1}\rightarrow\omega_1$ with the property that if $G(A)=G(B)$, then $A,B$ have the same order-type, and their intersection is an initial segment of $A$ and of $B$.
In particular, $G(A)=G(B)$ entails the existence of an order-preserving isomorphism $g:A\leftrightarrow B$, which is the identity on $A\cap B$.

Proof. For all $\alpha<\omega_2$, fix a bijection $g_\alpha:\alpha\leftrightarrow|\alpha|$. By $\aleph_1^{\aleph_0}=\aleph_1$ and the Engelking-Karlowicz theorem, we may also fix a sequence of functions $\langle f_i:\aleph_2\rightarrow\aleph_1\mid i<\aleph_1\rangle$ such that for every $X\in[\aleph_2]^{<\aleph_1}$ and $f:X\rightarrow\aleph_1$, there exists some $i<\aleph_1$ such that $f\subseteq f_i$.

We now define $G:[\omega_2]^{<\omega_1}\rightarrow{}^{<\omega_1}([\omega_1]^{<\omega_1})$, as follows.
Given $A\in[\omega_2]^{<\omega_1}$, let  $i<\aleph_1$ be the least ordinal such that the order-preserving isomorphism $\pi_A:A\leftrightarrow\text{otp}(A)$ is extended by $f_i$, and put:
$$G(A):=\{(0,i)\}\cup\langle g_{\pi^{-1}_A(j)}[A]\mid 0<j\le\text{otp}(A)\rangle.$$

Next, suppose that $G(A)=G(B)$, for distinct $A,B\in[\omega_2]^{<\omega_1}$. It follows that:

• $\text{otp}(A)=\text{dom}(G(A))-1=\text{dom}(G(B))-1=\text{otp}(B)$;
• $\pi_A\cup\pi_B\subseteq f_i$, for $i:=G(A)(0)$;
• if $\alpha\in A\cap B$, then $\pi_A(\alpha)=f_i(\alpha)=\pi_B(\alpha)$, and one of the following holds:

$\blacktriangleright$ $f_i(\alpha)=0$, and $A\cap\alpha=\emptyset=B\cap\alpha$;
$\blacktriangleright$ $f_i(\alpha)>0$, and $A\cap\alpha=g_{\alpha}^{-1}[g_\alpha[A]]=g_\alpha^{-1}[G(A)(\pi_A(\alpha))]=g_\alpha^{-1}[G(B)(\pi_B(\alpha))]=g_{\alpha}^{-1}[g_\alpha[B]]=B\cap\alpha$.

So $A\cap B$ is an initial segment of $A$ and of $B$.

Let $g:=\pi^{-1}_B\circ\pi_A$. Then $g:A\leftrightarrow B$ is an order-preserving isomorphism, and $g\restriction A\cap B$ is the identity function, since $\pi_A\restriction A\cap B=\pi_B\restriction A\cap B$ is simply the collapsing function from $A\cap B$ to $\text{otp}(A\cap B)$. $\square$

This entry was posted in and tagged . Bookmark the permalink.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://blog.assafrinot.com/?p=2054", "fetch_time": 1506274047000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2017-39/segments/1505818690112.3/warc/CC-MAIN-20170924171658-20170924191658-00447.warc.gz", "warc_record_offset": 644784854, "warc_record_length": 12780, "token_count": 1549, "char_count": 4277, "score": 3.53125, "int_score": 4, "crawl": "CC-MAIN-2017-39", "snapshot_type": "latest", "language": "en", "language_score": 0.5117606520652771, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00009-of-00064.parquet"}