Changの予想

同義語:Chang's conjecture

概要

Changの予想(Chang's conjecture)とは、可算な言語の構造で、全体の濃度が $\aleph_2$、ある述語の解釈の濃度が $\aleph_1$ のものは、全体の濃度が $\aleph_1$、述語の部分の濃度が $\aleph_0$ の初等部分構造をもつ、という主張 $(\aleph_2,\aleph_1)\twoheadrightarrow(\aleph_1,\aleph_0)$ である。名は予想だが、ZFC からは証明できず、ある大きな基数の無矛盾性から無矛盾になる命題である。$\omega_2$ 上の関数の可算族で閉じた集合による言い換えをもち、スクエア原理 $\square_{\omega_1}$ と両立しないので、$V=L$ では成り立たない。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 初等部分構造, Löwenheim–Skolemの定理, 基数

Changの予想(Chang's conjecture)は、可算な言語の構造で、全体の濃度が $\aleph_2$、ある 1 変数述語の解釈の濃度が $\aleph_1$ のものは、全体の濃度が $\aleph_1$、その述語の部分の濃度が $\aleph_0$ の初等部分構造をもつ、という主張である。記号では
$$ (\aleph_2,\aleph_1)\twoheadrightarrow(\aleph_1,\aleph_0) $$
と書く。「予想」と呼ばれているが、真偽が証明されるのを待つ命題ではない。ZFC からは証明できず(cor-cc-l)、大きな基数の無矛盾性を仮定すれば否定もできない。ある大きな基数の存在の無矛盾性から CC の無矛盾性が従い(Silver)、逆向きは Donder が核モデルを使って示した(Kan12 p. 399 の脚注 15)。
Löwenheim–Skolemの定理 は、構造を小さくしても一階の性質が変わらないことを述べる。Chang の予想は、それを「2 つの濃度の比」を保ったまま行えるかを問う。全体を $\aleph_2$ から $\aleph_1$ に縮めるのは下向きの Löwenheim–Skolem の定理でいつでもできるが、述語の部分も同時に $\aleph_1$ から $\aleph_0$ に縮めるところに内容がある。この記事では、関数で閉じた集合による言い換えと、Chang の予想が スクエア原理 $\square_{\omega_1}$ と両立しないことを証明する。

定義

$\mathcal L$ を、1 変数述語記号 $P$ を含む言語とする。$\mathcal L$-構造 $\mathfrak A$ の台集合を $A$、$P$ の解釈を $P^{\mathfrak A}$ と書く。

型と矢印の記号

基数 $\kappa\ge\lambda$ について、$\lvert A\rvert=\kappa$、$\lvert P^{\mathfrak A}\rvert=\lambda$ となる構造 $\mathfrak A$ を $(\kappa,\lambda)$ 型 の構造という。基数 $\kappa\ge\lambda$、$\mu\ge\nu$ について
$$ (\kappa,\lambda)\twoheadrightarrow(\mu,\nu) $$
とは、可算な言語の $(\kappa,\lambda)$ 型の構造がどれも $(\mu,\nu)$ 型の初等部分構造をもつことをいう。Chang の予想(CC と略す)とは $(\aleph_2,\aleph_1)\twoheadrightarrow(\aleph_1,\aleph_0)$ のことである。

EH18 p. 1 は、無限基数 $\mu< \kappa$ について $(\kappa^+,\kappa)\twoheadrightarrow(\mu^+,\mu)$ を Chang の予想と呼び、$\kappa=\aleph_1$、$\mu=\aleph_0$ がこの記事の CC にあたる。

自明に成り立つもの

$(\aleph_2,\aleph_1)\twoheadrightarrow(\aleph_1,\aleph_1)$ は ZFC で成り立つ。$(\aleph_2,\aleph_1)$ 型の構造 $\mathfrak A$ に対し、下向きの Löwenheim–Skolem の定理(初等部分構造 の定理「下向き Löwenheim–Skolem の定理」)で $P^{\mathfrak A}$ を含む濃度 $\aleph_1$ の初等部分構造をとればよい。

難しいのは、述語の部分だけを可算にすることである。可算な初等部分構造をとれば述語の部分は可算になるが、全体も可算になってしまう。

関数で閉じた集合による言い換え

$\omega_2$ 上の有限変数の関数 $f\colon\omega_2^n\to\omega_2$($n\ge1$)について、$X\subseteq\omega_2$ が $f$ で 閉じている とは、$f[X^n]\subseteq X$ となることをいう。

関数による言い換え

次は同値である。
(a) CC。
(b) $\omega_2$ 上の有限変数の関数の可算族 $\mathcal F$ がどれも、$\mathcal F$ のすべての関数で閉じた $X\subseteq\omega_2$ で $\lvert X\rvert=\aleph_1$、$\lvert X\cap\omega_1\rvert=\aleph_0$ となるものをもつ。

Skolem 関数で証人を集める

(a)⇒(b):$\mathcal F$ の各 $f$ に関数記号を 1 つずつ割り当て、$P$ を $\omega_1$、関数記号を $f$ と解釈した構造 $\mathfrak A=(\omega_2,\omega_1,f)_{f\in\mathcal F}$ を考える。言語は可算で、$\mathfrak A$ は $(\aleph_2,\aleph_1)$ 型である。CC により $(\aleph_1,\aleph_0)$ 型の初等部分構造 $\mathfrak B$ がある。部分構造の台集合は関数記号の解釈で閉じているので、$X:=B$ が求める集合である。
(b)⇒(a):$\mathfrak A$ を可算な言語 $\mathcal L$ の $(\aleph_2,\aleph_1)$ 型の構造とする。$\lvert A\setminus P^{\mathfrak A}\rvert=\aleph_2=\lvert\omega_2\setminus\omega_1\rvert$、$\lvert P^{\mathfrak A}\rvert=\aleph_1$ なので、$P^{\mathfrak A}$ を $\omega_1$ に移す全単射 $A\to\omega_2$ がある。これで構造を移して、$A=\omega_2$、$P^{\mathfrak A}=\omega_1$ としてよい。
$\mathcal L$ の論理式 $\varphi(x_1,\dots,x_n,y)$ ごとに、$f_\varphi\colon\omega_2^{\max(n,1)}\to\omega_2$ を、$\mathfrak A\models\exists y\,\varphi(\bar a,y)$ なら $\mathfrak A\models\varphi(\bar a,b)$ となる最小の $b$、そうでなければ $0$ と定める($n=0$ のときは引数によらない定数の関数とする)。$\mathcal L$ の関数記号と定数記号の解釈(定数は定数の関数として)も加えた族 $\mathcal F$ は可算である。(b) の $X$ をとる。$X$ は空でなく、関数記号と定数の解釈で閉じているので、部分構造 $\mathfrak B$ の台集合になる。$\bar a\in X^n$ で $\mathfrak A\models\exists y\,\varphi(\bar a,y)$ なら、証人 $f_\varphi(\bar a)$ が $X$ に属する。初等部分構造 の定理「証人による初等性の判定」により $\mathfrak B$ は $\mathfrak A$ の初等部分構造で、$\lvert B\rvert=\aleph_1$、$\lvert P^{\mathfrak B}\rvert=\lvert X\cap\omega_1\rvert=\aleph_0$ である。$\square$

EH18 Lemma 2(p. 1)は、さらに「関数 $f\colon(\kappa^+)^{< \omega}\to\kappa$ ごとに、$\lvert X\rvert=\mu^+$ で $f$ による $X$ の有限列の像の濃度が $\mu$ 以下となる $X\subseteq\kappa^+$ がある」という形も同値として挙げている。
(b) の形では、$\mathcal F$ に好きな関数を足しておけば、$X$ はそれらでも閉じる。次の節ではこれを使って、$X$ に順序数の構造を持ち込む。

スクエア原理との関係

$\square_{\omega_1}$ は、$\omega_2$ の各極限順序数 $\alpha$ に、順序型 $\omega_1$ 以下の閉非有界集合 $C_\alpha\subseteq\alpha$ を、$C_\alpha$ の集積点 $\beta< \alpha$ で $C_\beta=C_\alpha\cap\beta$ となるように選べるという原理である(スクエア原理 の定義「スクエア列」)。$\operatorname{acc}(C)$ を $C$ の集積点の集合、$\operatorname{ot}$ を順序型とする。

Chang の予想は $\square_{\omega_1}$ と両立しない

CC が成り立てば $\square_{\omega_1}$ は成り立たない。

方針は次のとおりである。CC で得た $X$ について $\delta:=X\cap\omega_1$ は可算な順序数になり、$\gamma:=\sup X$ の閉非有界集合 $C_\gamma$ の集積点で $X$ の集積点でもあるもの全体 $L$ を見る。$L$ の点 $\beta$ の $\operatorname{ot}(C_\beta)$ は $\beta$ とともに狭義に増えるが、$X$ に属する $\beta$ では $\delta$ 未満、属さない $\beta$ ではちょうど $\delta$ になり、$L$ が可算になって矛盾する。

順序型 $\delta$ の点を数える

$\langle C_\alpha\rangle$ を $\square_{\omega_1}$ 列とし、CC を仮定して矛盾を導く。各 $\alpha< \omega_2$ について次を固定する。$\alpha\ge1$ なら全射 $e_\alpha\colon\omega_1\to\alpha$。$\operatorname{cf}(\alpha)=\omega$ または $0< \alpha< \omega_1$ なら値域が $\alpha$ で非有界な列 $d_\alpha\colon\omega\to\alpha$ で、$0< \alpha< \omega_1$ のときは($\alpha$ が後続順序数でも)全射とする。$\alpha$ が極限順序数なら、$C_\alpha$ の元を小さい順に並べる写像 $\pi_\alpha\colon\operatorname{ot}(C_\alpha)\to C_\alpha$。これらを使って、$\omega_2$ 上の次の関数を考える(定義されない引数では値を $0$ とする)。

  • $x\mapsto0$、$x\mapsto x+1$、後続順序数 $x+1\mapsto x$。
  • $(\alpha,\xi)\mapsto e_\alpha(\xi)$($\xi< \omega_1$)、$(\alpha,\zeta)\mapsto\min\{\xi< \omega_1\mid e_\alpha(\xi)=\zeta\}$($\zeta< \alpha$)、$(\alpha,n)\mapsto d_\alpha(n)$($n< \omega$)。
  • $\alpha\mapsto\operatorname{ot}(C_\alpha)$、$(\alpha,\xi)\mapsto\pi_\alpha(\xi)$、$(\alpha,\zeta)\mapsto\pi_\alpha^{-1}(\zeta)$($\zeta\in C_\alpha$)、$(\alpha,\zeta)\mapsto\min(C_\alpha\setminus(\zeta+1))$($\zeta< \alpha$)。
    $\operatorname{ot}(C_\alpha)\le\omega_1< \omega_2$ なので値はどれも $\omega_2$ に入る。thm-cc-functions により、これらすべてで閉じた $X\subseteq\omega_2$ で $\lvert X\rvert=\aleph_1$、$\lvert X\cap\omega_1\rvert=\aleph_0$ となるものがある。
    段 1($\delta$ と $X$ の形)。$0\in X$ で $X$ は $x+1$ で閉じているので $\omega\subseteq X$ である。$0< \xi\in X\cap\omega_1$ なら $d_\xi(n)\in X$($n< \omega$)から $\xi\subseteq X$ である。よって $\delta:=X\cap\omega_1$ は順序数で、可算なので $\delta< \omega_1$、$x+1$ で閉じているので極限順序数である。$\alpha\in X$、$\alpha\ge1$ なら $X\cap\alpha=e_\alpha[\delta]$ である:$\xi< \delta$ なら $e_\alpha(\xi)\in X$、逆に $\zeta\in X\cap\alpha$ なら $\zeta=e_\alpha(\xi)$ となる最小の $\xi$ が $X\cap\omega_1=\delta$ に属する。とくに $X$ の真の始切片はすべて可算で、$\lvert X\rvert=\aleph_1$ だから $X$ の順序型は $\omega_1$ である。$\gamma:=\sup X$ とおくと、$\gamma< \omega_2$($\omega_2$ は正則)、$\operatorname{cf}(\gamma)=\omega_1$ で、$X$ は最大元をもたないので $\gamma\notin X$ である。
    段 2($X$ の中の共終数 $\omega_1$ の点)。$\alpha\in X$、$\operatorname{cf}(\alpha)=\omega_1$ とする。$\operatorname{cf}(\operatorname{ot}(C_\alpha))=\omega_1$ かつ $\operatorname{ot}(C_\alpha)\le\omega_1$ なので $\operatorname{ot}(C_\alpha)=\omega_1$ で、$\pi_\alpha\colon\omega_1\to C_\alpha$ である。$\xi< \delta$ なら $\pi_\alpha(\xi)\in X$ で、逆に $\zeta\in X\cap C_\alpha$ なら $\pi_\alpha^{-1}(\zeta)\in X\cap\omega_1=\delta$ なので、$X\cap C_\alpha=\pi_\alpha[\delta]$ である。$\zeta\in X\cap\alpha$ なら $\min(C_\alpha\setminus(\zeta+1))\in X\cap C_\alpha$ なので $\zeta< \pi_\alpha(\xi)$ となる $\xi< \delta$ がある。$C_\alpha$ は閉なので $\pi_\alpha(\delta)=\sup\pi_\alpha[\delta]$ である。以上から $\sup(X\cap\alpha)=\pi_\alpha(\delta)$ で、これは $C_\alpha$ の集積点だから、整合性により
    $$ C_{\sup(X\cap\alpha)}=C_\alpha\cap\pi_\alpha(\delta)=\pi_\alpha[\delta],\qquad\operatorname{ot}\bigl(C_{\sup(X\cap\alpha)}\bigr)=\delta $$
    である。
    段 3(数える)。$\operatorname{acc}(C_\gamma)\cap\gamma$ と $\operatorname{acc}(X)\cap\gamma$ はどちらも $\gamma$ の閉非有界集合で(スクエア原理 の補題「集積点は閉非有界」。後者は $X$ の閉包に同じ議論を当てる)、$\operatorname{cf}(\gamma)=\omega_1$ だから、その交わり $L$ も閉非有界で $\lvert L\rvert=\aleph_1$ である。$L$ の 2 点 $\beta< \beta'$ はともに $C_\gamma$ の集積点なので、スクエア原理 の補題「集積点の上で順序型は増える」により $\operatorname{ot}(C_\beta)< \operatorname{ot}(C_{\beta'})$ である。
    $\beta\in L\cap X$ とする。$\beta\in\operatorname{acc}(X)$ なので $X\cap\beta$ は $\beta$ で非有界で、段 1 により可算だから $\operatorname{cf}(\beta)=\omega$ である。$\operatorname{ot}(C_\beta)\le\omega_1$ の共終数も $\omega$ なので $\operatorname{ot}(C_\beta)< \omega_1$ で、$\operatorname{ot}(C_\beta)\in X\cap\omega_1=\delta$ である。
    $\beta\in L\setminus X$ とする。$\beta< \gamma=\sup X$ なので $\alpha:=\min(X\setminus\beta)$ があり、$\alpha>\beta$、$X\cap\alpha=X\cap\beta$、$\sup(X\cap\alpha)=\beta$ である。$\alpha=\alpha'+1$ なら $\alpha'\in X\cap\alpha$ から $\alpha'< \beta$、すなわち $\alpha\le\beta$ となって矛盾するので、$\alpha$ は極限順序数である。$\operatorname{cf}(\alpha)=\omega$ なら $d_\alpha(n)\in X\cap\alpha\subseteq\beta$ から $\alpha\le\beta$ となって矛盾するので、$\operatorname{cf}(\alpha)=\omega_1$ である。段 2 により $\operatorname{ot}(C_\beta)=\delta$ である。
    $\operatorname{ot}(C_\beta)$ は $L$ の上で狭義に増えるので、値 $\delta$ をとる $\beta$ は高々 1 つで、$L\setminus X$ は高々 1 点である。$L\cap X$ の上では値は $\delta$ 未満の相異なる順序数なので、$L\cap X$ は可算である。よって $L$ は可算となり、$\lvert L\rvert=\aleph_1$ に反する。$\square$

$V=L$ では $\square_\kappa$ がすべての $\kappa$ で成り立つ(Kan12 p. 378、構成可能宇宙)ので、次が従う。

構成可能宇宙では成り立たない

$V=L$ なら CC は成り立たない。とくに CC は ZFC から証明できない(ZFC が無矛盾なら)。

$V=L$ なら $\square_{\omega_1}$ が成り立つので、thm-cc-square により CC は成り立たない。ZFC が無矛盾なら $\mathrm{ZFC}+V=L$ も無矛盾(構成可能宇宙)なので、CC は ZFC から証明できない。$\square$

無矛盾性と一般化

CC の否定は $V=L$ で成り立つが、CC 自身の無矛盾性には大きな基数が要る。以下は主張だけを挙げ、この記事では証明しない。

  • Silver は、ある大きな基数の存在の無矛盾性から CC の無矛盾性を示した。Donder は核モデルを使って逆向きを示した(Kan12 p. 399 の脚注 15。そこでは Donder–Jensen–Koppelberg 1981 が参照されている)。下からの評価の一部は thm-cc-square からも分かる。$\kappa^+$ が $L$ で Mahlo基数 でなければ $\square_\kappa$ が成り立つ(Jensen、Kan12 p. 378)ので、CC のもとでは $\omega_2$ は $L$ の中で Mahlo 基数である。
  • 一般の $(\kappa^+,\kappa)\twoheadrightarrow(\mu^+,\mu)$ について、EH18 は、$\kappa>\mu^+$ となる多くの組について超コンパクト基数の無矛盾性から無矛盾であること、huge 基数(huge cardinal)の無矛盾性から「すべての後続基数 $\kappa$ とすべての $\mu< \kappa$ で同時に成り立つ」ことが無矛盾であることを示している(p. 1 の要約)。
  • 特異基数の後続では ZFC で成り立たないものがある。$n\ge3$ なら $(\aleph_{\omega+1},\aleph_\omega)\twoheadrightarrow(\aleph_{n+1},\aleph_n)$ は成り立たず、$n=1,2$ の場合の無矛盾性は EH18 の時点で未解決とされている(EH18 p. 2)。

反例

外した仮定例成り立たなくなる結論
言語が可算(def-cc-arrow)$(\omega_2,\omega_1)$ に、$\xi< \omega_1$ を名指す定数記号 $c_\xi$ を $\aleph_1$ 個加えた構造$(\aleph_1,\aleph_0)$ 型の初等部分構造をもたない:初等部分構造はすべての $c_\xi$ の解釈を含むので、述語の部分は $\omega_1$ 全体になる
述語の部分の濃度が無限(右辺の $\nu\ge\aleph_0$)$(\aleph_1,\aleph_0)\twoheadrightarrow(\aleph_0,n)$($n$ は自然数)を問う。構造 $(\omega_1,\omega)$$(\aleph_0,n)$ 型の初等部分構造はない:「$P$ は $n+1$ 個以上の元をもつ」は一階の文なので、初等部分構造でも成り立つ
述語の部分を縮める(thm-cc-square の仮定 CC)CC を自明に成り立つ $(\aleph_2,\aleph_1)\twoheadrightarrow(\aleph_1,\aleph_1)$(ex-cc-trivial)に替える$V=L$ でも成り立つので、$\square_{\omega_1}$ の否定は従わない($V=L$ では $\square_{\omega_1}$ が成り立つ)

2 行目は、矢印の右辺の 2 つの基数の両方を無限に保つ必要があることを示す。3 行目は、thm-cc-square の証明が $X\cap\omega_1$ の可算性(段 1 の $\delta< \omega_1$)を本質的に使っていることに対応する。

関連項目

参考文献

[1]
Akihiro Kanamori, Large cardinals with forcing, D. M. Gabbay, A. Kanamori, J. Woods (eds.), Handbook of the History of Logic, Vol. 6: Sets and Extensions in the Twentieth Century, Elsevier/North-Holland, pp. 359–413, 2012, §2.4(p. 378:$V=L$ で $\square_\kappa$ が成り立つこと、$\kappa^+$ が $L$ で Mahlo でなければ $\square_\kappa$)、§4.2(p. 399 の脚注 15:Chang の予想の無矛盾性の文献)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する