MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

One way to construct an Aronszajn tree is to build a sequence of functions $\langle e_\alpha : \alpha < \omega_1 \rangle$ such that $e_\alpha$ is an injection from $\alpha$ to $\omega$, and for any $(\alpha, \beta)$, $e_\alpha$ agrees with $e_\beta$ except on a finite set.

Is the following generalization possible? There is a family of functions {$e_x : x \in [\omega_2]^\omega$} such that each $e_x$ is an injection from $x$ to $\omega$, and for any $x,y \in [\omega_2]^\omega$, {$\alpha : e_x(\alpha) \not= e_y(\alpha)$} is finite.

share|cite|improve this question
In my answer, I was assuming that by $[\omega_2]^\omega$ you meant the collection of countable subsets of $\omega_2$. But perhaps you mean instead the subsets of $\omega_2$ with order type $\omega$? Also, I assume that you are taking $\alpha\in x\cap y$ when forming the set of differences. Right? – Joel David Hamkins Dec 15 '12 at 16:43
Sorry for not answering earlier, but yes your assumption was correct. Is there a less ambiguous notation for that? I get confused about that too with some authors. – Monroe Eskew Dec 17 '12 at 5:20
Oh, I think you've used the standard notation. (I had just wanted to check, since in some cases, one wants the collection of order-type-$\omega$ sets.) – Joel David Hamkins Dec 17 '12 at 6:48
up vote 5 down vote accepted

If the continuum hypothesis holds, then this is impossible. To see this, consider a family of $\omega_2$ many pairwise disjoint subsets of $\omega_2$, and for each $x$ in this family, consider the range of $e_x$, which is a subset of $\omega$. By the continuum hypothesis, there are only $\omega_1$ many possible ranges, and so there must be two disjoint countable subsets $x,y\subset\omega_2$ with $\text{ran}(e_x)=\text{ran}(e_y)$. Let $z=x\cup y$ and consider $e_z$. It cannot be that $e_z$ has only finite difference from $e_x$ and also from $e_y$, if $e_z$ is injective.

I'm not yet sure what happens when CH fails...

Meanwhile, here are a few slightly weaker generalizations that are possible.

  1. There is a family of injective functions $e_x:x\to \omega$ for all countable $x\subset\omega_1$, that is, for $x\in [\omega_1]^\omega$, such that $e_x$ and $e_y$ have at most finitely many disagreements on $x\cap y$. To see this, first fix a family of functions $e_\alpha$ for $\alpha\lt\omega_1$ as mentioned at the outset of the question, so that $e_\alpha$ injects $\alpha$ to $\omega$, and any two of them disagree only finitely. The point is that we may extend this family to $e_x:x\to \omega$ for $x\in[\omega_1]^\omega$ by defining $e_x=e_\alpha\upharpoonright x$, where $\alpha=\sup(x)$. The point is that if $\sup(y)=\beta$, then $e_\beta$ and $e_\alpha$ have only finitely many disagreements on their common domain, and so also $e_x$ and $e_y$ will therefore also have only finitely many disagreements.

  2. There is a family of injective functions $f_x:x\to \omega$ for all $x\in(\omega_2)^\omega$, meaning $x\subset\omega_2$ and $x$ has order type $\omega$, such that $f_x$ and $f_y$ have at most finitely many disagreements on $x\cap y$. To see this, fix the $e_x$ as in the previous paragraph, and also for each $\beta\lt\omega_2$, fix an injection $\pi_\beta:\beta\to \omega_1$, and now for $x\subset\omega_2$ of order type $\omega$, let $\beta=\sup(x)$, and consider $\pi_\beta[x]\subset \omega_1$. We may let $f_x=(e_{\pi_\beta[x]}\circ\pi_\beta)\upharpoonright x$. That is, we use $\sup(x)$ to tell us how to regard $x$ as really a subset of $\omega_1$, and then we apply the corresponding function from before. The point is that if $x$ and $y$ are two increasing $\omega$ sequences in $\omega_2$, then if they have different suprema, then $x\cap y$ is finite anyway and we needn't worry about it, and if they have the same suprema, then $f_x$ and $f_y$ agree completely.

share|cite|improve this answer

To add to Joel's answer; you can construct such a family, so long as you're willing to relax the injectivity requirement to just "finite-to-one". See P. Koszmider, "On Coherent Families of Finite-to-One Functions", JSL 58 (1993) no. 1, 128-138. It's in JSTOR.

Koszmider proves that you can construct such a family (with functions that are finite-to-one) on any $[\omega_n]^\omega$ in ZFC, and any $[\kappa]^\omega$ ($\kappa$ an infinite cardinal) assuming $V = L$.

share|cite|improve this answer
Thanks Paul, this may turn out to be useful to me. – Monroe Eskew Dec 17 '12 at 1:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.