超フィルター全体の集合の上のRudin-Keisler順序が全順序でないことの証明
この記事では，超フィルター全体の集合の上のRudin-Keisler順序が全順序でないことの証明を与える．
自然数全体の集合$\omega$上の超フィルター全体の集合を$\beta \omega$と書き，$\omega$上の非単項超フィルター全体の集合を$\beta \omega \setminus \omega$と書く．
$\F \subset \Pow(\omega)$のとき，$((\F))$で$\F$を含む最小のフィルターを表す．
すなわち
$$
((\F)) = \{ A \subset \omega : (\exists B_1, \dots B_n \in \F)(B_1 \cap \dots B_n \subset A) \}
$$
である．これは一般には真でないフィルター$\Pow(\omega)$になりえる．
$p \in \beta \omega$と$f \colon \omega \to \omega$に対して
$$
f^*(p) = \{ A \subset \omega : f^{-1}(A) \in p \}
$$
と定め，これを$f$による$p$の像フィルターという．これは超フィルターである．
$p, q \in \beta \omega$に対して$p \leRK q$という関係を，ある関数$f \colon \omega \to \omega$が存在して，$p = f^*(q)$であることだと定める．
この順序をRudin-Keisler順序と呼ぶ．
次の定理がこの記事の目標である．
擬順序集合$(\beta \omega, \leRK)$は線形でない．つまり互いに比較できない2元が存在する：
2元$p, q \in \beta \omega$が存在して$p \not \leRK q$かつ$q \not \leRK p$.
定理を証明するために必要となる，独立集合の概念を導入する．
$\S \subset \Pow(\omega)$かつ$\F$が$\omega$上のフィルターとする．
$\S$が$\F$を法として独立であるとは，任意の互いに異なる$\S$の元$X_1, \dots, X_n, Y_1, \dots, Y_m$に対して
$$ X_1^\c \cup \dots \cup X_n^\c \cup Y_1 \cup \dots \cup Y_m \not \in \F $$
となることを意味する．
:
$S \subset \Pow(\omega)$が存在して， $\omega$上のフレシェフィルターを法として独立であり，かつ濃度$\frakc$を持つ．
- $\S \ne \emptyset$かつ$\S$が$\F$を法として独立なとき，$\F$は真のフィルターである．
- $\S$が$\F$を法として独立であり，$\A \subset \S$のとき，$\S \setminus \A$は$((\F \cup \A))$を法として独立である．
- $\S$が$\F$を法として独立であり，$\A \subset \S$のとき，$\S \setminus \A$は$((\F \cup \{A^\c : A \in \A \}))$を法として独立である．
- $\S$が$\F$を法として独立で，$\S' \subset \S$のとき$\S'$も$\F$を法として合同である．
(1)の証明．$A \in \S$を取ると，独立性の定義より$A \not \in \F$．よって，$\F$は真のフィルターである．
(2)の証明．
$\S \setminus \A$から任意に元$X_1, \dots, X_n, Y_1, \dots, Y_m$を取る．
示すべきは，
$$
X_1^\c \cup \dots \cup X_n^\c \cup Y_1 \cup \dots \cup Y_m \not \in ((\F \cup \A))
$$
である．背理法でそうでないとするとある$F \in \F$と$A_1, \dots, A_k \in \A$について
$$
F \cap A_1 \cap \dots \cap A_k \subset X_1^\c \cup \dots \cup X_n^\c \cup Y_1 \cup \dots \cup Y_m
$$
を得る．この包含関係を変形すると
$$
F \subset X_1^\c \cup \dots \cup X_n^\c \cup Y_1 \cup \dots \cup Y_m \cup A_1^\c \cup \dots \cup A_k^\c
$$
である．これは仮定「$\S$が$\F$を法として独立」に矛盾している．
(3)は(2)と同様に示せる．
(4)は定義より明らか． ■
$\F$と$\G$を$\omega$上のフィルターとする．
$\S \subset \Pow(\omega)$を$\F$と$\G$の両方を法として独立である非空集合する．
$f \colon \omega \to \omega$とする．
このときフィルター$\F' \supset \F$と$\G' \supset \G$と$\S' \subset \S$が存在して，$\S'$は$\F'$と$\G'$の両方を法として独立であり，$S \setminus \S'$が有限集合で，かつある$B \in F'$について$f^{-1}(B)^\c \in \G'$となる．
$A \in \S$を一つ取り固定する．
ケース1: $\S \setminus \{A\}$が$((\G \cup \{f^{-1}(A)^c\}))$を法として独立なとき．
このとき，$\S' = \S \setminus \{A\}, \G' = ((\G \cup \{f^{-1}(A)^c\})), \F' = ((\F \cup \{A\})), B = A$が補題の結論を満たす．
$\S'$が$\G'$を法として独立なことはケース1の仮定そのものである．
$\S'$が$\F'$を法として独立なことは補題2の(2)よりよい．
: $\S \setminus \{A\}$が$((\G \cup \{f^{-1}(A)^c\}))$を法として独立でないとき．
このとき独立性の定義より，互いに異なる$X_1, \dots, X_n, Y_1, \dots, Y_m$が$\S \setminus \{A\}$の中に取れて，また，$G \in \G$が取れて，
$$
X_1^\c \cup \dots \cup X_n^\c \cup Y_1 \cup \dots \cup Y_m \supset G \cap f^{-1}(A)^\c.
$$
を満たす．
したがって，両辺の補集合を取って，$G$を「移項」すると
$$
X_1 \cap \dots \cap X_n \cap Y_1^\c \cap \dots \cap Y_m^\c \cap G \subset f^{-1}(A).
$$
を得る．
ここで，$\G' = ((G \cup \{X_1, \dots, X_n, Y_1^\c, \dots, Y_m^\c\}))$とおくと$f^{-1}(A^c)^c = f^{-1}(A) \in \G'$である．
また，$\F' = ((\F \cup \{A^c\}))$とおき，$\S' = \S \setminus \{ A, X_1, \dots, X_n, Y_1^c, \dots, Y_m^c \}$とおき，$B = A^c$とおく．
このとき補題2より$\S'$は$\F'$と$\G'$の両方を法として独立であることがわかる． ■
:
擬順序集合$(\beta \omega, \leRK)$は線形でない．つまり互いに比較できない2元が存在する：
2元$p, q \in \beta \omega$が存在して$p \not \leRK q$かつ$q \not \leRK p$.
長さ$\frakc$の再帰的構成による．
$(f_\alpha : \alpha < \frakc)$を$\omega$から$\omega$への関数の枚挙とする．
再帰的に$(\F_\alpha, \G_\alpha, \S_\alpha : \alpha < \frakc)$で次を満たすものを構成する．
- 各$\F_\alpha, G_\alpha$は$\omega$上のフィルターであり，列$(\F_\alpha : \alpha < \frakc), (\G_\alpha : \alpha < \frakc)$は単調増大かつ連続である．
- $\F_0$と$\G_0$はフレシェフィルター．
- 各$\alpha$について$X \in \F_{\alpha+1}$があって，$f_\alpha^{-1}(X)^c \in \G_{\alpha+1}$を満たす．また，各$\alpha$について$Y \in \G_{\alpha+1}$があって，$f_\alpha^{-1}(Y)^c \in \F_{\alpha+1}$を満たす．
- 各$\alpha$について$\S_\alpha$は$\F_\alpha$と$G_\alpha$の両方を法として独立であり，濃度$\frakc$を持つ．
- 列$(\S_\alpha : \alpha < \frakc)$は単調減少かつ連続である．
- 各$\alpha$について$\S_\alpha \setminus \S_{\alpha+1}$は有限集合である．
(3)が肝心な条件である．
この構成が終わったあと，$p$を$\bigcup_{\alpha < \frakc} \F_\alpha$を拡大して得られる超フィルター，$q$を$\bigcup_{\alpha < \frakc} \G_\alpha$を拡大して得られる超フィルターとする．
このとき$\omega$から$\omega$への関数をすべて枚挙していたことと，条件(3)より$p \not \leRK q$かつ$q \not \leRK p$が分かる．
独立集合の列$(\S_\alpha : \alpha < \frakc)$は補助的なものである．
これなしで(1)-(3)だけで帰納法が回ればそれでよかったのであるが，残念ながら回らない．
さて，$(\F_\alpha, \G_\alpha, \S_\alpha : \alpha < \frakc)$の構成方法を見よう．
$\alpha = 0$のとき，$\F_0, \G_0$はフレシェフィルターとして，$\S_0$はFichtenholz-Kantorovitch, Hausdorffにより定まるサイズ$\frakc$の独立集合とすればよい．
$\alpha$が極限順序数のとき．$\F_\alpha = \bigcup_{\beta < \alpha} \F_\beta$, $\G_\alpha = \bigcup_{\beta < \alpha} \G_\beta$, $\S_\alpha = \bigcap_{\beta < \alpha} \S_\beta$とする．これで条件(4)が満たされることは容易に確かめられる．
$\alpha = \beta + 1$が後続順序数のとき．
補題3を2回適用すればよい．なお，そのうちのちょうど1回は$\F$と$\G$の役割を入れ替えることに注意する． ■