Karpの定理(無限論理)

概要

Karpの定理(無限論理)（Karp's theorem）とは、2 つの構造が無限論理 $L_{\infty\omega}$ の文をすべて同じように満たすことと、両者の間に部分同型の往復系（空でなく、各組をどちらの側の元にも延ばせる部分同型の集合）があることが同値であるという定理である。往復系があることは、長さ $\omega$ の Ehrenfeucht–Fraïssé ゲームで模倣者が必勝戦略をもつこととも同値である。可算な構造どうしでは往復系から Cantor の往復論法で同型が作れるので、同型であることと $L_{\infty\omega}$ 同値、さらに $L_{\omega_1\omega}$ 同値とが一致する。非可算な構造では、端点のない稠密な全順序のように、$L_{\infty\omega}$ 同値でも同型とは限らない。

$$\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}} $$

前提知識: 無限論理, 構造(モデル), 初等同値

Karp の定理（Karp's theorem）は、2 つの構造が無限論理 $L_{\infty\omega}$ の文をすべて同じように満たすことと、両者の間に部分同型の 往復系 があることが同値である、という定理である。無限個の論理式を調べる代わりに、有限個の元の対応を 1 つずつ延ばしていく組合せ的な条件を確かめればよい。往復系は、Cantor が可算な稠密順序の同型を作った往復論法を、同型まで作り切らずに「いつでも延ばせる」という性質として取り出したものである。
可算な構造どうしなら、往復系から往復論法で同型が作れる。したがって可算な構造は、$L_{\infty\omega}$ の文、さらには可算個の連言・選言だけを使う $L_{\omega_1\omega}$ の文で、同型を除いて区別できる。この記事では、Karp の定理と、それを長さ $\omega$ の Ehrenfeucht–Fraïssé ゲームで言い換えた形を証明し、可算な構造についての系、例、条件を外したときの反例を扱う。無限論理の証明体系の完全性定理など、Karp によるほかの結果とは別の定理である。

定義

言語 $L$ は定数記号・関係記号・関数記号からなり、等号はつねに使えるとする。構造の台集合は空でなく、構造 $\mathcal M$ の台集合を $M$ と書く。$L_{\infty\omega}$ と $L_{\omega_1\omega}$ は 無限論理 の定義「無限論理 $L_{\kappa\lambda}$ と $L_{\infty\omega}$」のものである。すなわち $L_{\infty\omega}$ の論理式は、原子論理式から、否定、任意の集合 $\Phi$ についての連言 $\bigwedge\Phi$ と選言 $\bigvee\Phi$（$\Phi$ の元の自由変数は全体で有限個）、有限個の変数の量化 $\exists\bar y$・$\forall\bar y$ によって作られる。$L_{\omega_1\omega}$ は $\Phi$ を可算集合に限ったものである。束縛変数は、必要なら名前を付け替えて、自由変数と重ならないものとする（充足の定義から真偽は変わらない）。
$\bar x=(x_1,\dots,x_n)$ を相異なる変数の列とし、自由変数が $\bar x$ の中にある論理式を $\varphi(\bar x)$ と書く。$M$ の長さ $n$ の列 $\bar a$（空列 $\emptyset$ も含む）について、$x_i$ に $a_i$ を割り当てたとき $\varphi$ が真であることを $\mathcal M\models\varphi[\bar a]$ と書く。$\bar ac$ は列 $\bar a$ の後に元 $c$ を付けた列である。$\mathcal M$ と $\mathcal N$ が $L_{\infty\omega}$ の文をすべて同じように満たすことを $\mathcal M\equiv_{\infty\omega}\mathcal N$、$L_{\omega_1\omega}$ の文について同じことが成り立つことを $\mathcal M\equiv_{\omega_1\omega}\mathcal N$ と書く。

部分同型と往復系

$\mathcal M,\mathcal N$ を $L$ 構造とする。

  1. $M$ の列 $\bar a$ と $N$ の列 $\bar b$ が同じ長さ $n$ で、すべての原子論理式 $\alpha(\bar x)$ について $\mathcal M\models\alpha[\bar a]\iff\mathcal N\models\alpha[\bar b]$ となるとき、組 $(\bar a,\bar b)$ は 部分同型 であるという。
  2. 部分同型の集合 $F$ が 往復系 であるとは、$F$ が空でなく、次の 2 つを満たすことをいう。
    • （行き）$(\bar a,\bar b)\in F$ と $c\in M$ に対し、$(\bar ac,\bar bd)\in F$ となる $d\in N$ がある。
    • （帰り）$(\bar a,\bar b)\in F$ と $d\in N$ に対し、$(\bar ac,\bar bd)\in F$ となる $c\in M$ がある。
      $\mathcal M$ と $\mathcal N$ の間に往復系があるとき、$\mathcal M$ と $\mathcal N$ は 部分同型的（partially isomorphic、potentially isomorphic）であるという。

この定義は 無限論理 の定義「部分同型と往復系」と同じものである。等号の原子論理式 $x_i=x_j$ も含むので、部分同型 $(\bar a,\bar b)$ では $a_i\mapsto b_i$ が矛盾なく定まる単射になり、関係記号の成否と、関数記号の値（$f(x_1,\dots,x_k)=x_j$ の形の原子論理式）を保つ。関係記号だけの言語では、これは 初等同値 の記事の定義「部分同型と往復系」で、有限部分写像の形で述べたものと同じである。同型 $\sigma\colon\mathcal M\to\mathcal N$ があれば、組 $(\bar a,\sigma(\bar a))$ の全体は往復系である。

往復系の平行移動

$F$ を $\mathcal M,\mathcal N$ の間の往復系とし、$(\bar a_0,\bar b_0)\in F$ とする。$F'=\{(\bar a,\bar b)\mid(\bar a_0\bar a,\bar b_0\bar b)\in F\}$ は、空列の組 $(\emptyset,\emptyset)$ を含む往復系である。

$(\emptyset,\emptyset)\in F'$ は $(\bar a_0,\bar b_0)\in F$ のことである。$\bar a$ についての原子論理式は、変数の名前を替えれば $\bar a_0\bar a$ についての原子論理式なので、$F'$ の元は部分同型である。（行き）：$(\bar a,\bar b)\in F'$ と $c\in M$ に対し、$F$ の（行き）で $(\bar a_0\bar ac,\bar b_0\bar bd)\in F$ となる $d$ をとれば $(\bar ac,\bar bd)\in F'$。（帰り）も同じである。$\square$

したがって、往復系は空列の組を含むものに取り替えてよい。

主定理

往復系は論理式の真偽を保つ

$F$ を $\mathcal M,\mathcal N$ の間の往復系とする。$(\bar a,\bar b)\in F$ で $\bar a,\bar b$ の長さが $n$ なら、自由変数が $\bar x=(x_1,\dots,x_n)$ の中にある $L_{\infty\omega}$ のすべての論理式 $\varphi(\bar x)$ について
$$ \mathcal M\models\varphi[\bar a]\iff\mathcal N\models\varphi[\bar b]. $$

論理式の組み立てに関する帰納法

主張を「すべての $n$ と、相異なる変数の長さ $n$ のすべての列 $\bar x$ と、$F$ に属する長さ $n$ のすべての組について」の形にして、$\varphi$ の組み立てに関する帰納法で示す。

  • 原子論理式：部分同型の定義そのものである。
  • $\lnot\psi$：同じ組 $(\bar a,\bar b)$ に帰納法の仮定を使えばよい。
  • $\bigwedge\Phi$・$\bigvee\Phi$：$\Phi$ の各元の自由変数は $\bar x$ の中にあるので、各元に同じ組で帰納法の仮定を使う。$\Phi$ が無限集合でも、使うのは各元についての仮定だけである。
  • $\exists\bar y\,\psi$（$\bar y=(y_1,\dots,y_k)$）：$\bar y$ に $\bar x$ の変数 $x_i$ が現れても、$x_i$ は $\exists\bar y\,\psi$ に自由に現れないので、$\bar x$ の中の $x_i$ を $\bar x$ にも $\bar y$ にも現れない変数に取り替えても示すべき同値は変わらない（真偽は自由変数への割り当てだけで決まる）。そこで $\bar y$ は $\bar x$ と重ならないとしてよい。$\psi$ の自由変数は $\bar x\bar y$ の中にある。$\mathcal M\models\exists\bar y\,\psi[\bar a]$ とし、$\mathcal M\models\psi[\bar a\bar c]$ となる $\bar c=(c_1,\dots,c_k)$ をとる。（行き）を $c_1,\dots,c_k$ について順に $k$ 回使うと、$(\bar a\bar c,\bar b\bar d)\in F$ となる $\bar d$ がとれる。長さ $n+k$ の組 $(\bar a\bar c,\bar b\bar d)$ に帰納法の仮定を使って $\mathcal N\models\psi[\bar b\bar d]$、よって $\mathcal N\models\exists\bar y\,\psi[\bar b]$。逆向きは（帰り）を $k$ 回使えば同じである。
  • $\forall\bar y\,\psi$：$\lnot\exists\bar y\,\lnot\psi$ と同じ真偽をもつので、前の場合に帰着する。$\square$
Karp の定理

$L$ 構造 $\mathcal M,\mathcal N$ について、次の 2 つは同値である。

  1. $\mathcal M$ と $\mathcal N$ は部分同型的である。
  2. $\mathcal M\equiv_{\infty\omega}\mathcal N$。
    さらに 2 が成り立つとき、$L_{\infty\omega}$ の論理式を同じように満たす同じ長さの列の組 $(\bar a,\bar b)$ の全体 $F_\infty$ は往復系であり、$\mathcal M,\mathcal N$ の間のすべての往復系を含む。
区別する論理式をすべて連言でまとめる

1 ⇒ 2． 往復系 $F$ をとり、lem-karp-shift により $(\emptyset,\emptyset)\in F$ としてよい。文は自由変数をもたないので、thm-karp-preserve を空列の組に使えばよい。
2 ⇒ 1． $F_\infty$ が往復系であることを示す。$F_\infty$ の元は原子論理式も同じように満たすので部分同型であり、2 から $(\emptyset,\emptyset)\in F_\infty$ なので空でない。
（行き）を示す。$(\bar a,\bar b)\in F_\infty$（長さ $n$）と $c\in M$ をとる。$D$ を、$(\bar ac,\bar bd)\notin F_\infty$ となる $d\in N$ の全体とする。各 $d\in D$ について、$\bar ac$ と $\bar bd$ で真偽の違う論理式 $\chi(\bar x,y)$ があり、必要なら否定をとって、$\mathcal M\models\chi_d[\bar ac]$ かつ $\mathcal N\not\models\chi_d[\bar bd]$ となる $\chi_d$ を 1 つ選ぶ。
$$ \psi(\bar x,y)=\bigwedge_{d\in D}\chi_d(\bar x,y) $$
とおく。連言の添字は集合 $D\subset N$ で、自由変数は $\bar x,y$ の中にあるので、$\psi$ は $L_{\infty\omega}$ の論理式である（$D=\emptyset$ なら $\psi$ は空の連言で、つねに真）。$\mathcal M\models\psi[\bar ac]$ なので $\mathcal M\models\exists y\,\psi[\bar a]$ であり、$(\bar a,\bar b)\in F_\infty$ から $\mathcal N\models\exists y\,\psi[\bar b]$。そこで $\mathcal N\models\psi[\bar bd]$ となる $d\in N$ をとる。もし $d\in D$ なら、連言肢 $\chi_d$ が $\bar bd$ で偽なので $\psi$ も偽になり、矛盾する。よって $d\notin D$、すなわち $(\bar ac,\bar bd)\in F_\infty$ である。
（帰り）は $\mathcal M$ と $\mathcal N$ の役割を入れ替えて同じ議論をすればよい（今度は連言の添字が $M$ の部分集合になる）。
最後に、往復系 $F$ と $(\bar a,\bar b)\in F$ について、thm-karp-preserve から $(\bar a,\bar b)\in F_\infty$ なので、$F\subset F_\infty$ である。$\square$

この定理は KK04 Theorem 1.2.1（p. 4）であり、C. Karp による。2 ⇒ 1 では、$N$ の部分集合を添字とする連言を使った。$L_{\infty\omega}$ が任意の大きさの連言を許すことは、この一歩で効いている。

段階つきの形

往復を $\alpha$ 段に制限した同値関係 $\sim_\alpha$（順序数 $\alpha$ に関する超限帰納法で定める）は Scott高さ の記事の定義「$\alpha$ 往復同値」で、Scott 高さは同記事の定義「Scott 高さと標準 Scott 文」で扱う。同記事の命題「量化子の階数による言い換え」によれば、$(\mathcal M,\bar a)\sim_\alpha(\mathcal N,\bar b)$ は、量化子の階数が $\alpha$ 以下の $L_{\infty\omega}$ の論理式をすべて同じように満たすことと同値である。どの論理式もある順序数を量化子の階数にもつので、これと thm-karp-main を合わせると、$\mathcal M$ と $\mathcal N$ が部分同型的であることは、すべての順序数 $\alpha$ で $(\mathcal M,\emptyset)\sim_\alpha(\mathcal N,\emptyset)$ であることと同値になる。

Ehrenfeucht–Fraïssé ゲームとの関係

Ehrenfeucht–Fraïsséゲーム は $n$ 手で終わるゲームで、量化子の階数が $n$ 以下の一階の文に対応する。手数の制限をなくすと、往復系に対応するゲームになる。

長さ $\omega$ のゲーム

$L$ 構造 $\mathcal M,\mathcal N$ と同じ長さの列 $\bar a,\bar b$ について、局面 $(\bar a,\bar b)$ から始まるゲーム $G_\omega(\mathcal M,\bar a;\mathcal N,\bar b)$ を次で定める。妨害者と模倣者が、手番 $t=1,2,3,\dots$ ごとに、

  1. 妨害者が $\mathcal M,\mathcal N$ の一方を選び、その台集合から元を 1 つ選ぶ。
  2. 模倣者が他方の台集合から元を 1 つ選ぶ。
    第 $t$ 手で $M$ から選ばれた元を $c_t$、$N$ から選ばれた元を $d_t$ とし、$t$ 手の後の局面を $(\bar ac_1\cdots c_t,\bar bd_1\cdots d_t)$ とする。ゲームは終わらず、すべての $t\ge0$ で局面が部分同型であれば模倣者の勝ち、そうでなければ妨害者の勝ちとする。空列から始めるゲームを $G_\omega(\mathcal M,\mathcal N)$ と書く。

$n$ 手のゲームでは、最後の局面が部分同型なら途中の局面もすべて部分同型である（部分列の原子論理式は元の列の原子論理式でもある）。したがって「各局面で部分同型」という勝ちの条件は、$n$ 手で打ち切れば Ehrenfeucht–Fraïsséゲーム の記事の定義と一致する。

ゲームによる特徴づけ

$L$ 構造 $\mathcal M,\mathcal N$ について、$G_\omega(\mathcal M,\mathcal N)$ で模倣者が必勝戦略をもつことと、$\mathcal M$ と $\mathcal N$ が部分同型的であることは同値である。

証明を開く

⇐：lem-karp-shift により、$(\emptyset,\emptyset)$ を含む往復系 $F$ をとる。局面が $F$ に属するとき、妨害者が $M$ から $c$ を選べば（行き）の $d$ で、$N$ から $d$ を選べば（帰り）の $c$ で応じる（選択関数をあらかじめ固定しておく）。初めの局面は $F$ に属し、この応じ方では次の局面も $F$ に属するので、すべての局面が $F$ に属し、部分同型である。よってこれは必勝戦略である。

⇒：$G$ を、$G_\omega(\mathcal M,\bar a;\mathcal N,\bar b)$ で模倣者が必勝戦略をもつ組 $(\bar a,\bar b)$ の全体とする。仮定から $(\emptyset,\emptyset)\in G$ である。$(\bar a,\bar b)\in G$ なら、第 0 手の局面 $(\bar a,\bar b)$ が部分同型でなければならない。（行き）：$(\bar a,\bar b)\in G$ と $c\in M$ をとり、必勝戦略を 1 つ固定する。妨害者が第 1 手で $c$ を選んだときの応答を $d$ とすると、第 2 手以降は局面 $(\bar ac,\bar bd)$ から始まるゲームそのもので、固定した戦略の続きに従えば模倣者は勝つ。よって $(\bar ac,\bar bd)\in G$。（帰り）は妨害者が $N$ から選ぶ場合を考えればよい。したがって $G$ は往復系である。$\square$

模倣者が $G_\omega$ に勝てば、とくに手数を $n$ に制限したゲームにもすべて勝つ。言語が有限個の関係記号だけからなるときは、Ehrenfeucht–Fraïsséゲーム の記事の系「初等同値のゲームによる特徴づけ」により、$\mathcal M\equiv\mathcal N$（一階の初等同値）になる。逆は成り立たない。一階の初等同値は部分同型的であることを導かない（後の反例の表の 4 行目）。

可算な構造

Cantor の往復論法

可算な構造 $\mathcal M,\mathcal N$ の間の往復系 $F$ と $(\bar a,\bar b)\in F$ について、$\bar a$ を $\bar b$ に送る同型 $\sigma\colon\mathcal M\to\mathcal N$ がある。

元を交互に取り込む

$M=\{m_0,m_1,\dots\}$、$N=\{n_0,n_1,\dots\}$ と並べる（有限なら同じ元を繰り返す）。$(\bar a_0,\bar b_0)=(\bar a,\bar b)$ とし、$(\bar a_{2k+1},\bar b_{2k+1})$ は（行き）で $(\bar a_{2k},\bar b_{2k})$ に $m_k$ を加えた $F$ の元、$(\bar a_{2k+2},\bar b_{2k+2})$ は（帰り）で $n_k$ を加えた $F$ の元とする。列は延びていくだけなので、$\bar a_j$ の $i$ 番目の元を $\bar b_j$ の $i$ 番目の元に送る対応を $j$ について合わせたものを $\sigma$ とする。部分同型は等号の原子論理式を保つので $\sigma$ は矛盾なく定まる単射であり、作り方から定義域は $M$、値域は $N$ である。原子論理式に現れる元は有限個なので、それらがすべて $\bar a_j$ に現れる段階 $j$ をとれば、$(\bar a_j,\bar b_j)$ が部分同型であることから、$\sigma$ はその原子論理式の成否を保つ。よって $\sigma$ は関係と関数を保つ全単射、すなわち同型である。$\square$

可算な構造の同型の判定

可算な $L$ 構造 $\mathcal M,\mathcal N$ について、次は同値である。

  1. $\mathcal M\cong\mathcal N$。
  2. $\mathcal M$ と $\mathcal N$ は部分同型的である。
  3. $\mathcal M\equiv_{\infty\omega}\mathcal N$。
  4. $\mathcal M\equiv_{\omega_1\omega}\mathcal N$。
    また、$M$ の同じ長さの列 $\bar a,\bar a'$ が $L_{\omega_1\omega}$ の論理式をすべて同じように満たすなら、$\bar a$ を $\bar a'$ に送る $\mathcal M$ の自己同型がある。

1 ⇒ 2 は同型の組の全体が往復系であることから、2 ⇒ 3 は thm-karp-main、3 ⇒ 4 は $L_{\omega_1\omega}\subset L_{\infty\omega}$ から従う。4 ⇒ 1：$L_{\omega_1\omega}$ の論理式を同じように満たす組の全体を $F_{\omega_1}$ とし、prf-karp-main の 2 ⇒ 1 を $L_{\omega_1\omega}$ で繰り返す。そこで使った連言の添字は $N$（帰りでは $M$）の部分集合なので可算であり、$\psi$ は $L_{\omega_1\omega}$ の論理式である。よって $F_{\omega_1}$ は $(\emptyset,\emptyset)$ を含む往復系で、lem-karp-cantor から同型を得る。後半は $\mathcal N=\mathcal M$ として $(\bar a,\bar a')\in F_{\omega_1}$ に lem-karp-cantor を使う。$\square$

KK04 Corollary 1.2.2（p. 4）は、可算な言語の場合に 1 ⇔ 4 を述べている。上の証明は言語の可算性を使わない。

例

端点のない稠密な全順序

言語 $\{<\}$ で、端点のない稠密な全順序 $\mathcal M,\mathcal N$ をとる。成分の大小と等号の関係が同じ列の組の全体は往復系である（初等同値 の記事の例「端点のない稠密な全順序」の議論を列の組に書き直したもの）。よってこのような全順序はすべて互いに $\equiv_{\infty\omega}$ であり、可算なものは cor-karp-countable によりすべて $(\mathbb Q,<)$ に同型である（カテゴリー性 の記事の定理「Cantor の定理」）。非可算なものは同型とは限らない。たとえば $(\mathbb R,<)$ と $(\mathbb R\setminus\{0\},<)$ は濃度も同じだが同型でない（同記事の例「連続体濃度では範疇的でない」）。

無限次元のベクトル空間

体 $K$ 上のベクトル空間を、構造(モデル) の記事の例「体上のベクトル空間」の言語 $L_K=\{0,+,-\}\cup\{\lambda_k\mid k\in K\}$ の構造とみる。$V,W$ が無限次元なら $V$ と $W$ は部分同型的である。

一次関係が同じ列を延ばす
証明を開く

$F$ を、すべての $(k_1,\dots,k_n)\in K^n$ で $\sum k_ia_i=0\iff\sum k_ib_i=0$ となる組 $(\bar a,\bar b)$ の全体とする。$(\emptyset,\emptyset)\in F$ である。$L_K$ の項 $t(\bar x)$ には、項の組み立てに関する帰納法で、どの空間でも $t(\bar a)=\sum k_ia_i$ となる係数 $k_i$ が対応するので、原子論理式 $t=s$ の成否は 1 つの一次関係の成否であり、$F$ の元は部分同型である。（行き）：$(\bar a,\bar b)\in F$、$c\in V$ とする。$c=\sum q_ia_i$ と書けるなら $d=\sum q_ib_i$ とおく。$\sum p_ia_i+pc=0$ は $\sum(p_i+pq_i)a_i=0$ と同じなので、$F$ の条件から $\sum p_ib_i+pd=0$ と同値である。$c$ が $a_i$ たちの一次結合でないなら、$W$ は無限次元なので $b_i$ たちの一次結合でない $d\in W$ をとる。$\sum p_ia_i+pc=0$ なら $p=0$ でなければならず（$p\ne0$ なら $c$ が一次結合になる）、条件は $\sum p_ia_i=0$ に帰着し、$d$ の側も同じである。どちらの場合も $(\bar ac,\bar bd)\in F$。（帰り）も同じである。$\square$

とくに $\mathbb Q$ 上の次元 $\aleph_0$ の空間と次元 $2^{\aleph_0}$ の空間は $\equiv_{\infty\omega}$ だが、濃度が違うので同型でない。可算な体の上の可算な無限次元の空間はどれも次元が $\aleph_0$ であり、cor-karp-countable と合っている。

反例：条件を外すと成り立たない

外す条件反例成り立たなくなること
cor-karp-countable の「可算」$\mathbb Q$ 上の次元 $\aleph_0$ の空間と次元 $2^{\aleph_0}$ の空間（ex-karp-vector）部分同型的なら同型
往復系が「空でない」等号だけの言語で 1 点集合と 2 点集合、$F=\emptyset$往復系があれば $\equiv_{\infty\omega}$
往復系の（帰り）$(\mathbb Q,<)$ と、$\mathbb Q$ に最大元 $\infty$ を付け加えた順序、$F$ は大小の型が同じで $\infty$ を含まない組の全体往復系があれば $\equiv_{\infty\omega}$
cor-karp-countable の 4 を一階の初等同値に替える加法群 $(\mathbb Q,+)$ と $(\mathbb Q^2,+)$初等同値な可算構造は同型
反例の確かめ
各行の確かめを開く

1 行目：ex-karp-vector による。2 行目：$F=\emptyset$ は部分同型の集合で、（行き）（帰り）は条件が空なので満たされるが、空でないという条件だけを満たさない。文 $\exists x\exists y\,x\ne y$ は 2 点集合でだけ真である。3 行目：$F$ は空列の組を含み、元は部分同型である。（行き）は、$\bar b$ が $\mathbb Q$ の元だけからなるので、ex-karp-dlo と同じく $\mathbb Q$ の中から同じ位置の $d$ をとれる。しかし $d=\infty$ に対する（帰り）は満たされない。文 $\exists x\forall y\,\lnot(x< y)$ は最大元のある側でだけ真である。4 行目：両者は可算で初等同値だが同型でない（初等同値 の記事の例「初等同値だが同型でない構造」の 2）。cor-karp-countable から両者は $\equiv_{\omega_1\omega}$ でもない。実際、任意の 2 元が $\mathbb Z$ 上一次従属であることを表す $L_{\omega_1\omega}$ の文 $\forall x\forall y\bigvee_{(m,n)\in\mathbb N^2\setminus\{(0,0)\}}(mx=ny\lor mx+ny=0)$（$mx$ は $x$ の $m$ 個の和、$0x$ は $0$）は、$\mathbb Q$ で真、$\mathbb Q^2$ で偽である（$x=(1,0)$、$y=(0,1)$ では $mx\pm ny=(m,\pm n)$ が $0$ にならない）。thm-karp-game により、模倣者は $G_\omega$ に勝てない。

関連項目

参考文献

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

Mathpediaを支援する
Karpの定理(無限論理)