Suppose that $(P,\leq)$ is a countably infinite linear ordering, and $U$ is a p-point ultrafilter on $P$. Show that there is an $X\in U$ such that $X$ has order type $\omega$ or $\omega^*$. (This is Exercise 7.8 in Jech)

I know that if $U=\{P\}$, or if $U$ is Ramsey, then this is true; enumerate $P=\{a_n\}_{n\in\omega}$ and color pairs $\{m,n\}$ according to whether or not their order in $\omega$ agrees with the order of $\{a_m,a_n\}$. But if $U$ is a p-point, I don't see how to adapt this argument.

(Edit) A definition: $U$ is a p-point ultrafilter on a countably infinite set $P$ if it is non-principle and for every partition $\{A_n:n\in\omega\}$ of $P$ into $\aleph_0$ many pieces such that $A_n\notin U$ for all $n$, there is an $X\in U$ such that $X\cap A_n$ is finite for all $n$.

  • 1
    $\begingroup$ What does p-point ultrafilter mean? $\endgroup$ – Chris Eagle Mar 1 '13 at 16:01
  • $\begingroup$ Chris: added the definition above. $\endgroup$ – Iian Smythe Mar 1 '13 at 16:04

We shall make use of the following facts:

  1. If $U$ is an ultrafilter and $X\cup Y\in U$, then $X\in U$ or $Y\in U$.
  2. (Exercise $7.7$ of Jech's Set Theory)If $D$ is a $p$-point on $\omega$, then for any decreasing sequence $A_0\supset A_1\supset \cdots \supset A_n\supset \cdots$ of elements of $D$, there exists $X\in D$ such that for each $n\in \mathbb N$, $X-A_n$ is finite.

With no loss of generality we may assume that $P\subseteq \mathbb Q$ and $<=<^{\mathbb Q}\cap P\times P$, and furthermore we may assume $P$ is bounded in $(\mathbb Q,<)$; $P\subseteq [a,b]$ for some $a,b\in \mathbb Q$.

Let $D$ be a $p$-point on $P$.

By fact $(1)$ we have that $[a,\frac{a+b}{2}]\cap P\in D$ or $[\frac{a+b}{2},b]\cap P\in D$, let $[a_1,b_1]$ be one of these half-intervals such that $[a_1,b_1]\cap P\in D$. Continuing this process we get a shrinking sequence of nested intervals $\{ [a_k,b_k]\}_{k\in \mathbb N}$; with $[a_o,b_0]=[a,b]$, such that $b_k-a_k=\frac{b-a}{2^k}$ and $[a_k,b_k]\cap P\in D$ for all $k\in \mathbb N$

By fact $(2)$ there exists $X\in D$ such that $X-([a_k,b_k]\cap P)$ is finite for all $k\in \mathbb N$. Let $r\in \mathbb R$ be such that $r\in \bigcap_{k\in \mathbb N}[a_k,b_k]$, then either $[a,r]\cap P\in D$ or $[r,b]\cap P\in D$.

If $[a,r]\cap P\in D$, then $[a,r]\cap P\cap X\in D$, and hence since $D$ is nonprincipal, $[a,r]\cap P\cap X$ is infinite, but $a_k\rightarrow r$ as $k\rightarrow \infty$ then $X\cap P\cap [a,r]$ is a discrete infinite linear ordering, since $X-[a_k,b_k]$ is finite for all $k$, since $X\cap P\cap [a_k,b_k]\neq \emptyset $ for all sufficiently large $k$; otherwise $[a,r]\cap P\cap X$ would be finite, and since the intersection of the nested intervals is $\{ r\}$, the order-type of $[a,r)\cap P\cap X$ must be $\omega$, but since $D$ is non-principal $[a,r)\cap P\cap X\in D$.

Similarly if $[r,b]\cap P \in D$, the order-type of $(r,b]\cap X$ must be $\omega^*$, and $(r,b]\cap X\in D$. Since one of this cases must hold by fact $(1)$, we are done.

  • $\begingroup$ In the second last paragraph, you are saying that $X\cap P\cap[a,r]$ is discrete since all of its initial segments are finite, correct? $\endgroup$ – Iian Smythe Mar 1 '13 at 17:09
  • $\begingroup$ I like this argument very much; thanks! $\endgroup$ – Iian Smythe Mar 1 '13 at 17:15
  • $\begingroup$ you're welcome. $\endgroup$ – Camilo Arosemena-Serrato Mar 1 '13 at 17:50
  • $\begingroup$ I'm probably being daft... But why can we assume P is bounded? i.e. if P is unbounded, why is the theorem 'obviously true' ? $\endgroup$ – qwert4321 Jul 5 '16 at 6:39
  • $\begingroup$ @qwert4321 Any countable linear order can be embedded in an open interval of $\Bbb Q$. $\endgroup$ – Camilo Arosemena-Serrato Jul 7 '16 at 14:16

I’m going to call the ultrafilter $\mathscr{U}$. Let $P_0=P\in\mathscr{U}$. Given $P_\xi\in\mathscr{U}$ for some $n\in\omega$, choose a non-endpoint $p_\xi\in P_\xi$. Exactly one of the sets $\{p\in P_\xi:p<p_\xi\}$ and $\{p\in P_\xi:p_\xi\le p\}$ belongs to $\mathscr{U}$; let it be $P_{\xi+1}$. If $\eta$ is a limit ordinal, $P_\xi$ has been constructed for each $\xi<\eta$, let $P_\eta=\bigcap_{\xi<\eta}P_\xi$. If $P_\eta\in\mathscr{U}$, continue the construction; otherwise, stop.

Since $P$ is countable, there must be a countable limit ordinal $\eta$ such that $P_\eta\notin\mathscr{U}$. For $\xi<\eta$ let $D_\xi=P_\xi\setminus P_{\xi+1}\notin\mathscr{U}$, and note that $\bigcup_{\xi<\eta}D_\xi=P\setminus P_\eta\in\mathscr{U}$, while each $D_\xi\notin\mathscr{U}$. Moreover, the sets $D_\xi$ are order-convex and pairwise disjoint, so the linear order on $P$ induces a natural linear order on $\mathscr{D}=\{D_\xi:\xi<\eta\}$. Each $D_\xi$ is either the left or the right end of the corresponding $P_\xi$; let $L=\{\xi<\eta:D_\xi\text{ is the left end of }P_\xi\}$, and let $R=\eta\setminus L$. Then exactly one of $\bigcup_{\xi\in L}D_\xi$ and $\bigcup_{\xi\in R}D_\xi$ belongs to $\mathscr{U}$; without loss of generality assume that $\bigcup_{\xi\in L}D_\xi\in\mathscr{U}$.

Let $L=\{\lambda_\xi:\xi<\alpha\}$ be an increasing enumeration of $L$, and let $\beta$ be minimal such that $\bigcup_{\xi<\beta}D_{\lambda_\xi}\in\mathscr{U}$; clearly $\beta$ is a limit ordinal, so there is a strictly increasing sequence $\langle\beta_n:n\in\omega\rangle$ of ordinals such that $\beta_0=\lambda_0$ and $\beta=\sup_n\beta_n$. For $n\in\omega$ let $E_n=\bigcup\{D_{\lambda_\xi}:\beta_n\le\lambda_\xi<\beta_{n+1}\}$; then $\bigcup_nE_n\in\mathscr{U}$, but $E_n\notin\mathscr{U}$ for $n\in\omega$, so there is a $U\in\mathscr{U}$ such that $U\subseteq\bigcup_nE_n$ and $U\cap E_n$ is finite for each $n\in\omega$. The construction then ensures that the order-type of $U$ as a subset of $P$ is $\omega$. (Had $\bigcup_{\xi\in R}D_\xi$ been a member of $\mathscr{U}$, we would instead have got a member of $\mathscr{U}$ of type $\omega^*$.)

  • $\begingroup$ Ah, I didn’t see that Camilo had already posted an answer. I’ll leave this, since it works without the preliminary embedding into $\Bbb Q$. $\endgroup$ – Brian M. Scott Mar 1 '13 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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