Borel Equivalence Relations

$\omega:=\{1,2,3,...\}$を自然数全体の集合とする
$n\in\omega$に対して,$\langle a_0,...,a_{n-1} \rangle$および$\langle a_i:i< n \rangle$は長さ$n$の自然数列を表す.
$\langle a_i:i\in\omega \rangle$は自然数からなる無限数列を表す.
$\langle \rangle$は空列,すなわち長さ0の列を表す.
$\omega^n:=\{\langle a_0,...,a_{n-1} \rangle:\forall i< n(a_i\in\omega)\}$:長さnの自然数列全体
$\omega ^{<\omega}:=\bigcup_{n\in\omega}\omega^n$:有限数列全体
$\omega^\omega:=\{\langle a_i:i\in\omega \rangle:\forall i\in\omega(a_i\in\omega)\}$:無限数列全体
$2=\{0,1\}$である.同様に以下のように集合を定義する.
$2^n:=\{\langle a_0,...,a_{n-1} \rangle:\forall i< n(a_i\in2)\}$
$2^{<\omega}:=\bigcup_{n\in\omega}2^n$
$2^\omega:=\{\langle a_i:i\in\omega \rangle:\forall i\in\omega(a_i\in2)\}$

$\sigma,\tau\in\omega^{<\omega}$に対し,以下の記法を用いる.

• $\sigma$の長さを${\rm lh}(\sigma)$で表す.すなわち$\sigma=\langle a_0,...,a_{n-1}\rangle$のとき,${\rm lh}(\sigma)=n$.
• $i<{\rm lh}(\sigma)$に対し，$\sigma$の$i$番目の値を$\sigma(i)$で表す．すなわち，$\sigma=\langle a_0,...,a_{n-1} \rangle$のとき$\sigma(i)=a_i$.
• $i<{\rm lh}(\sigma)$対し，長さ$i$の始切片を$\sigma\upharpoonright i$で表す．すなわち，$\sigma=\langle a_0,...,a_{n-1} \rangle$のとき$\sigma\upharpoonright i=\langle a_0,...,a_{i-1} \rangle$.
• $\sigma$と$\tau$の連結(concatination)を$\sigma^\frown\tau$で表す．すなわち，$\sigma^\frown\tau=\langle \sigma(0),...,\sigma({\rm lh}(\sigma)-1),\tau(0),...,\tau({\rm lh}(\tau)-1) \rangle$.
• $\sigma$が$\tau$の始切片であることを$\sigma\subseteq_{\rm i.sg.}\tau$で表す．すなわち，$\sigma\subseteq_{\rm i.sg}\tau:\Leftrightarrow \exists i\leq {\rm lh}(\tau)(\sigma = \tau\upharpoonright i)$.

$\sigma\in\omega^{<\omega},\tau\in\omega^\omega$に対しても同様に${\rm lh}(\tau),\tau(i)\ (i\in\omega),\tau\upharpoonright i\ (i\in\omega),\sigma^\frown\tau,\sigma\subseteq_{\rm i.sg.}\tau$を次のように定める．

• ${\rm lh}(\tau):=\omega$
• $\tau=\langle a_0,a_1,...,a_i,...\rangle$のとき，$\tau(i):=a_i$
• $\tau\upharpoonright i := \langle \tau(0),...,\tau(i-1) \rangle$
• $\sigma^\frown\tau := \langle \sigma(0),...,\sigma({\rm lh(\sigma)-1}),\tau(0),...,\tau(n),...\rangle$
• $\sigma\subseteq_{\rm i.sg.}\tau:\Leftrightarrow \exists i\leq {\rm lh}(\tau)(\sigma = \tau\upharpoonright i)$

$\alpha\leq\omega_1$とするとき，$\omega^\omega$の部分集合からなるクラスとして${\bf\Sigma}^0_\alpha$,${\bf\Pi}^0_\alpha$,${\bf\Delta}^0_\alpha$を次のように定める．

• ${\bf\Sigma}^0_0$は$\omega^\omega$の開集合全体
• $A\in {\bf\Sigma}^0_\alpha:\Leftrightarrow \exists\langle\beta_n:n\in\omega\rangle\exists\langle B_n:n\in\omega \rangle (\forall n\in\omega(\beta_n<\alpha\land B_n\in{\bf \Sigma}^0_{\beta_n})\land (A=\bigcup_{n\in\omega}B_n^{\rm c}))$
• $A\in {\bf \Pi}^0_\alpha :\Leftrightarrow A\in {\bf \Sigma}^0_\alpha$
• $A\in {\bf \Delta}^0_\alpha:\Leftrightarrow A\in {\bf \Sigma}^0_\alpha \land A\in{\bf \Pi}^0_\alpha$
• ${\bf\Sigma}^0_{\omega_1}={\bf \Pi}^0_{\omega_1}={\bf \Delta}^0_{\omega_1}$はcountable unionおよびcomplementationで閉じる最小の集合．これに属する集合をBorel集合という．

算術の項(term)とは，次の規則により得られるものである．

• 自然数の要素を表す変数は項である($n,m,l,...$などを主に用いる)
• 項$t_1,t_2$に対し$t_1+t_2,t_1\cdot t_2$は項．

原子論理式(atomic formula)とは，$t_1=t_2,\ t_1< t_2,\ t\in X$のことである．ここで$t_1,t_2,t$は項,$X$は$\omega$の部分集合を表す変数($X\in 2^\omega$)．

$\Sigma^0_0,\Pi^0_0,\Delta^0_0$はすべて同じ概念で，次の規則により得られるものである．

• 原子論理式は$\Sigma^0_0(,\Pi^0_0,\Delta^0_0)$論理式
• $\Sigma^0_0(,\Pi^0_0,\Delta^0_0)$論理式$\varphi,\psi$に対して$\neg\varphi,\varphi\land\psi,\varphi\lor\psi$は$\Sigma^0_0(,\Pi^0_0,\Delta^0_0)$論理式
• $\Sigma^0_0(,\Pi^0_0,\Delta^0_0)$論理式$\varphi$と自然数変数$n$,$n$を使用しない項$\tau$に対して,$(\exists n<\tau) \varphi$は$\Sigma^0_0(,\Pi^0_0,\Delta^0_0)$論理式

$1$以上の自然数$n$に対して$\Sigma^0_n,\Pi^0_n,\Delta^0_n$-論理式を次のように定める．

• $\varphi$が$\Sigma^0_n$論理式であるとは，$\varphi$が自然数変数$m$と$\Pi^0_{n-1}$論理式$\psi$を用いて$(\exists m\in\omega)\psi$と表せることをいう
• $\varphi$が$\Pi^0_n$であるとは$\varphi$が$\Sigma^0_n$論理式$\psi$によって$\neg \psi$と表せることをいう
• $\Sigma^0_n$論理式$\varphi$と$\Pi^0_n$論理式$\psi$が互いに同値であるとき，$\varphi$と$\psi$はともに$\Delta^0_n$論理式であるという．
• 論理式$\varphi$がある$n\in\omega$について$\Sigma^0_n$もしくは$\Pi^0_n$論理式であるとき，$\varphi$を算術式とよぶ．

$X\subseteq \omega$が$\Sigma^0_n(\text{resp. } \Pi^0_n,\Delta^0_n)$集合であるとは，以下が成立することをいう．

• $X= \{n\in\omega : \varphi(n)\}$,ここで$\varphi$は$\Sigma^0_n(\text{resp. } \Pi^0_n,\Delta^0_n)$論理式

$X\subseteq \omega^\omega$が$\Sigma^0_n(\text{resp. } \Pi^0_n,\Delta^0_n)$であるとは，以下が成立することをいう．

• $X=\{a\in\omega^\omega:\varphi(a)\}$,ここで$\varphi$は$\Sigma^0_n(\text{resp. } \Pi^0_n,\Delta^0_n)$論理式で，$a$の$\varphi$におけるすべての出現はある数項$t$によって$a\upharpoonright t$の形に限る．

また$X$がある$x\subseteq\omega$と$\Sigma^0_n(\text{resp. } \Pi^0_n,\Delta^0_n)$論理式$\varphi$で$X=\{a\in\omega^\omega:\varphi(a,x)\}$(ここで$a$の$\varphi$におけるすべての出現はある数項$t$によって$a\upharpoonright t$の形に限る)と表せるとき，$X$は$\Sigma^0_n(x)(\text{resp. } \Pi^0_n(x),\Delta^0_n(x))$であるという．

自然数$n$に対して$X$が${\bf \Sigma}^1_n$(resp. ${\bf \Pi}^1_n,{\bf \Delta}^1_n$)集合であることを以下のようにして定める．

• $X$が${\bf \Sigma}^1_0,{\bf \Pi}^1_0,{\bf \Delta}^1_0$であることはすべて同じで$X$がBorel集合であることをいう．
• $X$が${\bf \Sigma}^1_n$集合であるとは，${\bf \Pi}^1_{n-1}$集合$Y\subseteq\omega^\omega\times\omega^\omega(\subseteq\omega^\omega)$によって$ X=\{x\in\omega^\omega:\exists y \in\omega^\omega((x,y)\in Y)\}$とあらわせることをいう．
• $X$が${\bf \Pi}^1_n$集合であるとは，${\bf \Sigma}^1_n$集合$Y$の補集合であることをいう．すなわち，$X=\omega^\omega\setminus Y$.
• $X$が${\bf \Sigma}^1_n$集合かつ${\bf \Pi}^1_n$のとき，$X$は${\bf \Delta}^1_n$集合であるという．

$\varphi$が$\Sigma^1_0$論理式，${\Pi}^1_0$論理式,${\Delta}^1_0$論理式であるとは，すべて同じで算術式であることをいう．

$1$以上の自然数$n$に対して$\Sigma^1_n,\Pi^1_n,\Delta^1_n$-論理式を次のように定める．

• $\varphi$が$\Sigma^1_n$論理式であるとは，$\varphi$が集合変数Xと$\Pi^1_{n-1}$論理式$\psi$を用いて$(\exists X \subseteq\omega)\psi$と表せることをいう
• $\varphi$が$\Pi^1_n$であるとは$\varphi$が$\Sigma^1_n$論理式$\psi$によって$\neg \psi$と表せることをいう
• $\Sigma^1_n$論理式$\varphi$と$\Pi^1_n$論理式$\psi$が互いに同値であるとき，$\varphi$と$\psi$はともに$\Delta^1_n$論理式であるという．

$X\subseteq \omega^\omega$が$\Sigma^1_n(\text{resp. } \Pi^1_n,\Delta^1_n)$であるとは，以下が成立することをいう．

• $X=\{a\in\omega^\omega:\varphi(a)\}$,ここで$\varphi$は$\Sigma^1_n(\text{resp. } \Pi^1_n,\Delta^1_n)$論理式で，$a$の$\varphi$におけるすべての出現はある数項$t$によって$a\upharpoonright t$の形に限る．

また$X$がある$x\subseteq\omega$と$\varphi$は$\Sigma^1_n(\text{resp. } \Pi^1_n,\Delta^1_n)$論理式$\varphi$で$X=\{a\in\omega^\omega:\varphi(a,x)\}$(ここで$a$の$\varphi$におけるすべての出現はある数項$t$によって$a\upharpoonright t$の形に限る)と表せるとき，$X$は$\Sigma^1_n(x)(\text{resp. } \Pi^1_n(x),\Delta^1_n(x))$であるという．

$T\subseteq\omega^{<\omega}$が木(tree)であるとは，$\forall\sigma\in T \forall i<{\rm lh}(\sigma)(\sigma\upharpoonright i \in T )$を満たすことをいう．
とくに$T\subseteq 2^{<\omega}$のとき，$T$を二分木(binary tree)という．
木$T\subseteq\omega^{<\omega}$,無限列$p\in\omega^\omega$に対して，$p$が$T$のpath(道)であるとは，$\forall i\in\omega (p\upharpoonright i \in T )$であることをいう．$T$のpath全体の集合を$[T]$であらわす．

$\mathbb{P}_{\rm GH}=\{A\subseteq X : A \text{ is }\Sigma^1_1\}$をGandy-Harrington強制法という.