完備性

维基媒体消歧义页

數學及其相關領域中,一個對象具有完備性(英語:Completeness),即它不需要添加任何其他元素,這個對象也可稱為完備的完全的。更精確地,可以從多個不同的角度來描述這個定義,同時可以引入完備化這個概念。但是在不同的領域中,「完備」也有不同的含義,特別是在某些領域中,「完備化」的過程並不稱為「完備化」,另有其他的表述,請參考代數閉域緊化哥德爾不完備定理

  • 圖論中,一個被稱為完全的,如果這個圖是無向圖,並且任何兩個頂點之間都恰有一條邊連接。
  • 範疇論,一個範疇被稱為完備的,如果任何一個從小範疇到函子都有極限。而它被稱為上完備的,如果任何函子都有一個上極限。請查看範疇論中的極限定義。
  • 數理邏輯,一個理論被稱為完備的,如果對於其語言中的任何一個句子,這個理論包括且僅包括。一個系統是相容的,如果不存在同時和非的證明。哥德爾不完備定理證明了,包含皮亞諾公理的所有公理系統都是不可能既完備又相容的。下面還有一些邏輯中關於完備性的定義。
  • 證明論和相關的數理邏輯的領域中,一個形式的演算相對於一個特定的邏輯(即相對於它的語義)是完備的,如果任何由一組前提根據語義導出的陳述,都可以從這組前提出發利用這個演算語法地導出。形式地說,導出一階邏輯在這個意義下是完備的。特別地,所有邏輯的重言式都可以被證明。即使在經典邏輯中,這與前述的完備性是不同的(即一個陳述和否定陳述對於這個邏輯而言不可能是重言式)。相反的概念被稱為可靠性soundness)。
  • 計算複雜度理論中,一個問題對於一個複雜度類,在某個給定類型的歸約下是完全的完備 (複雜度)),如果中,並且中的任何問題利用該歸約都可以化歸到。例如,NP完全問題NP類和多項式時間和多對一歸約的意義下是完全的。