今回の講演者は矢野雅彦氏です。タイトルは変数を制限した論理と有限構造についてです。

Definition 1 いくつかの記号を確認する

1. F O を普通の first order の logic とする. さらに無限の disjunction を許す logic を L_{∞} とする. また F O、 L_{∞}の変数を v̄ = v_{1}, ⋯, v_{s} の s 個に制限したものをそれぞれ F O^{s}, L_{∞}^{s} と書く.

2. ā ∈ (A ∪ {∗})^{s} に対して、 supp(ā) := {i : a_{i} ∈ A} とする.

3. ¯∗ := ∗, ⋯, ∗ と略記する.

4. ā ∈ (A ∪ {∗})^{s} に対して、 i 番目を a ∈ A で置き換えたものを ā_{i}^{a} と書く.

5. L_{∞}^{s}(F O)-formula ϕ に対して、 quantifier rank qr(ϕ) を次のように定義する.

qr(ϕ) := 0 if ϕ is atomic
qr(¬ϕ) := qr(ϕ)
qr(∨Φ) := max {qr(ϕ) : ϕ ∈ Φ}
qr(∃v_{i}ϕ) := qr(ϕ) + 1

6. structure A、および m ∈ N,ā ∈ (A ∪ {∗})^{s} に対して

tp_{m}^{s}(ā) := {ϕ ∈ F O^{s} : qr(ϕ) ≤ m, A ⊧ ϕ(ā)}
tp_{L_{∞}^{s}}(ā) := {ϕ ∈ L_{∞}^{s} : qr(ϕ) ≤ m, A ⊧ ϕ(ā)}

7. structure A,B に対して、 W_{m}^{s}(A, B) ⊆ (A ∪ {∗})^{s} × (B ∪ {∗})^{s} を次のように定義する.

(ā, b̄) ∈ W_{0}^{s}(A, B)  ↔^{def} supp(ā) = supp(b̄), qftp(ā) = qftp(b̄)
(ā, b̄) ∈ W_{m+1}^{s}(A, B) ↔^{def} (ā, b̄) ∈ W_{0}^{s}(A, B)
∀ a ∈ A ∃ b ∈ B (ā_{i}^{a}, b̄_{i}^{b}) ∈ W_{m}^{s}(A, B)
∀ b ∈ B ∃ a ∈ A (ā_{i}^{a}, b̄_{i}^{b}) ∈ W_{m}^{s}(A, B)

Fact 2 次は、上の定義からすぐに得られる。以下から、 W_{m}^{s}(A, B) を W_{m}^{s} と省略する。

1. W_{0}^{s} ⊇ W_{1}^{s} ⊇ ⋯

2. A と B が finite structures ならば ∃ n ∈ N W_{m+1}^{s} = W_{m}^{s}

Theorem 3 1. (ā, b̄) ∈ W_{m}^{s} ⇔ tp_{m}^{s}(ā) = tp_{m}^{s}(b̄)

2. W_{m+1}^{s} = W_{m}^{s} ≠ ∅ とする.

(ā, b̄) ∈ W_{m}^{s} ⇔ tp_{L_{∞}^{s}}(ā) = tp_{L_{∞}^{s}}(b̄)

A,B を finite structure とする. このとき、 A ≡^{F O} B (変数の数を制限しない場合) ならば、 A, B の構造が F O-formula で完全に書き切れるので A ≅ B となる。特に、 A ≡^{L_{∞}} B となる。変数の数を制限した場合も次のことが成り立つ。

Corollary 4 A,B を finite structure とする.

A ≡^{F O^{s}} B → A ≡^{L_{∞}^{s}} B

Corollary を証明する。まず、 A,B が finite なので、 W_{m+1}^{s} = W_{m}^{s} となる m ∈ N がとれる。 A ≡^{F O^{s}} B より、 Theorem 3 の 1 から (¯∗, ¯∗) ∈ W_{m}^{s}(∀m ∈ N) となる。そこで、 Theorem 3 の 2 から、 A ≡^{L_{∞}^{s}} B となる。

参考文献

[1] Heinz-Dieter Ebbinghaus, Joerg Flum, Finite Model Theory, Springer