【MLG60発表報告】ランベック計算に循環証明を導入する試み

2025-12-19

2025年12月19日、数理論理学の集会であるMLG60にて、「ランベック計算の循環証明体系 $𝐿 𝜇$ の試み」というタイトルで発表を行いました。本記事では、言語学的な動機を持つランベック計算に循環証明を導入する意義と、形式言語理論における含意について解説します。

背景と動機：論理と形式言語の階層構造

通常の Lambek Calculus ( $𝐿$ ) は文脈自由文法 (CFG) と等価です。近年、論理側の制約（深さ制限など）を強めることで、正規言語や線形言語に対応する階層構造が整理されつつあります。本研究の目的は、この図式に「循環（サイクル）」、すなわち無限の証明構造を導入した μ-Lambek calculus ( $𝐿 𝜇$ ) を加えることで、この階層がどう拡張されるのかを探ることにあります。

基礎：ランベック計算

1958年に提唱されたこの体系は、交換則・弱化則・縮約則を持ちません。つまり、語の「順番」と「個数」を厳密に管理します。

𝜑 ≔ \frac{𝜑}{𝜑} ∣ 𝜑 ∖ 𝜑 ∣ 𝛼

解析例：Alice runs

Aliceを $np$ 、runsを $np ∖ s$ とすると、以下の証明により文の正当性が保証されます。

$np ⇒ np$	$s ⇒ s$
$np, np ∖ s ⇒ s$
$(∖ L)$

提案体系 $𝐿 𝜇$ と循環証明の導入

提案体系 $𝐿 𝜇$ では、再帰的な定義を扱うための最小不動点 ( $𝜇$ ) と、選択を行うための連言 ( $\land$ ) を追加しました。

𝜑 ≔ \frac{𝜑}{𝜑} ∣ 𝜑 ∖ 𝜑 ∣ 𝜑 \land 𝜑 ∣ 𝜇 𝑋 . 𝜑_{𝑋} ∣ 𝛼

推論規則と大域的トレース条件 (GTC)

不動点を展開する規則を追加します。ただし、論理的整合性を保つため、「すべての無限パスにおいて、左辺の $𝜇$ が無限回展開（unfold）される」という 大域的トレース条件 (GTC) を課します。

Left Rule ( $𝜇 𝐿$ ):

Γ, α[μX. α/X], Δ ⇒ γ

Γ, μX. α, Δ ⇒ γ

(μ L)

Right Rule ( $𝜇 𝑅$ ):

Γ ⇒ α[μX. α/X]

Γ ⇒ μX. α

(μ R)

応用：一般化された等位接続

$𝐿 𝜇$ では、“A, B, and C” のような可変長の接続をオートマトン的な挙動として記述できます。型を $𝜒 \equiv (𝜇 𝑌 . 𝑌 \land 𝑋)$ および $𝜏_{and} \equiv \frac{𝜇 𝑌 . (𝑋 ∖ 𝑋) \land (𝑋 ∖ 𝜏_{and})}{𝑋}$ と定義した際の証明構造は以下の通りです。

χ, τ_and, X ⇒ X

(Backlink)

χ, τ_and, X ⇒ X

(μ L)

$X ⇒ X$	$χ, X, (X ∖ τ_and), X ⇒ X$
$χ, X, (X ∖ τ_and), X ⇒ X$
$(∖ L)$

χ ∧ X, (X ∖ τ_and), X ⇒ X

(∧ L_2)

χ, (X ∖ X) ∧ (X ∖ τ_and), X ⇒ X

χ, τ_and, X ⇒ X

(μ L)

矛盾の定義

$𝐿 𝜇$ では「終わらない再帰」として矛盾 $⊥ \equiv 𝜇 𝑋 . 𝑋$ を定義可能です。これは GTC を満たしつつ、爆発原理（任意の命題の導出）を許容します。

⊥ ⇒ φ

(Backlink)

⊥ ⇒ φ

(μ L)

結びに代えて

私の予想 (Conjecture) は、 「循環証明を入れても、言語クラスは文脈自由言語 (CFL) のまま変わらない」 というものです。交換則がないため交差依存を作れず、GTC により有限停止性が保証されるためです。今後は、無限ストリームを扱うための最大不動点 $𝜈$ を含む $𝐿 𝜇 𝜈$ の構築を目指します。

← Blog

Categories:

Blog

Retrieved from "https://tani.cc/blog/lambek-calculus-cyclic-proofs.html"