多對一歸約

數學敘述

有限題族明示source carrier、target carrier、decision predicates與完整total mapping table，逐x雙向驗x∈A iff f(x)∈B；只驗yes instances不足。composition須保留方向：A≤mB且B≤mC推出A≤mC。若A≤mB且B decidable，先算f再跑B decider可得A decider；反向transfer不成立。partial map、倒轉方向與Turing reduction混同均須拒絕。有限mapping table只證指定finite domain；無限domain仍需完整可計算算法及termination certificate。

代表公式（精確 TeX）

R(A,B,f)=1

成立條件

• 本輪exact families限明示bounded finite carriers與complete mapping arrays。
• decider transfer使用完整finite truth tables或明示total termination。

符號作用域

• R — 多對一歸約述詞
• A — 來源判定問題
• B — 目標判定問題
• f — 全可計算映射

直觀、定義與常見誤解

total map資格先於reduction。

membership equivalence需正反雙向。

composition與decider transfer都保持正確方向。

只驗yes instances、使用partial map，或由A decidable倒推出B decidable。

已採用的推導導讀

原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。

前置知識

• 決定問題 — yes/no predicates。
• 函數映射 — complete total map。
• 函數合成 — reduction transitivity。
• Turing機判定模型 — decider與termination界線。

驗證界線

finite table不證無限domain computability；不混同Turing reduction。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。

下一個義務

加入undecidability reductions與recognizability boundaries。

同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。