# p-point ultrafilters on a countable linear order

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$.

• What does p-point ultrafilter mean? – Chris Eagle Mar 1 '13 at 16:01
• Chris: added the definition above. – 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.

• 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? – Iian Smythe Mar 1 '13 at 17:09
• I like this argument very much; thanks! – Iian Smythe Mar 1 '13 at 17:15
• you're welcome. – Camilo Arosemena-Serrato Mar 1 '13 at 17:50
• 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' ? – qwert4321 Jul 5 '16 at 6:39
• @qwert4321 Any countable linear order can be embedded in an open interval of $\Bbb Q$. – 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^*$.)

• 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$. – Brian M. Scott Mar 1 '13 at 17:24