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[\mathcal P(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 Blog, Expository and tagged . Bookmark the permalink.

5 Responses to The Engelking-Karlowicz theorem, and a useful corollary

  1. Pingback: The uniformization property for $aleph_2$ | Assaf Rinot

  2. DM says:

    There is a typo in the definition of $W$. It should not be $ \mathcal{A} \in [a]^{<\kappa} $ but $ \mathcal{A} \in [P(a)]^{<\kappa} $ (where $P(a)$ denotes the power set of $a$).

  3. D.A. Mejia says:

    This is a very helpful post.
    One easy (but practical) observation: the proof of (1)$\Rightarrow$(2) gives, independent of (1), that there is a collection of functions $\langle f_i\colon \mu\to\lambda :\, i<\lambda^{<\kappa} \rangle$ (note the power ${<}\kappa$) satisfying (2).

Leave a Reply

Your email address will not be published. Required fields are marked *