Zupełność

Zupełność – cecha obiektu, polegająca na tym, że nie trzeba niczego do niego dodawać. To znaczenie jest uściślane w wielu dziedzinach.

W logice, semantyczna zupełność jest odwrotnością poprawności systemu formalnego. System formalny jest „semantycznie zupełny”, jeśli wszystkie tautologie są twierdzeniami, a „poprawny” gdy wszystkiego jego twierdzenia są tautologiami. Kurt Gödel, Leon Henkin, i Emil Post wszyscy opublikowali dowody zupełności. (Patrz Historia tezy Churcha–Turinga.) System nazywa się niesprzeczny, jeśli nie istnieje w nim dowód zarówno dla P, jak i zaprzeczenia P.

• Dla systemu formalnego S w języku formalnym L, S jest semantycznie zupełny, lub po prostu zupełny wtedy i tylko wtedy, gdy, każdy logicznie poprawny wzór z L (każdy wzór będący prawdziwym w ramach każdej interpretacji L) jest twierdzeniem w S. To znaczy że, ${\displaystyle \models _{\mathrm {S} }A\ \to \ \vdash _{\mathrm {S} }A}$^[1].

• System formalny S jest silnie zupełny, czy też inaczej mówiąc zupełny silnie, wtedy i tylko wtedy, gdy, dla każdego zbioru założeń T, każdy wzór wynikający semantycznie z T może zostać wyprowadzony z T. To znaczy, że ${\displaystyle T\models _{\mathrm {S} }A\ \to \ T\vdash _{\mathrm {S} }A.}$

• System formalny S jest syntaktycznie zupełny, lub inaczej zupełny dedukcyjnie, czy też maksymalnie zupełny, albo po prostu zupełny wtedy i tylko wtedy, gdy, dla każdego wyrażenia A z języka danego systemu A albo ¬A jest twierdzeniem w S. Mówimy wtedy o zupełności zaprzeczeniowej. Innym słowy, system formalny jest syntaktycznie zupełny wtedy i tylko wtedy, gdy nie można dodać żadnego niewywodzącego się zeń aksjomatu bez wprowadzenia niedorzeczności. Logika z funkcją prawdy predykatów i rachunek predykatów pierwszego rzędu są semantycznie zupełne, lecz nie są syntaktycznie zupełne (np. wyrażenie rachunku zdaniowego składające się z jednej zmiennej „a” ani jego zaprzeczenie nie jest twierdzeniem, ale nie są to tautologie). Twierdzenie Gödla o niezupełności pokazuje że nie ma systemu rekurencyjnie będącego dostatecznie bogatym, tak jak aksjomatyka Peana, który byłby zarówno niesprzeczny, jak i zupełny.

• System formalny jest niezupełny dokładnie gdy każde zdanie jest twierdzeniem^[2].

• System funktorów zdaniotwórczych jest funkcjonalnie zupełny wtedy i tylko wtedy, gdy można w nim wyrazić wszystkie funkcje predykatywne.

• Język jest wyrażeniowo zupełny jeśli można za jego pomocą opisać dziedzinę dla której został on przewidziany.

• Język formalny jest zupełny odnośnie do pewnej właściwości wtedy i tylko wtedy, gdy każde zdanie posiadające daną cechę jest twierdzeniem.

W matematyce, „zupełność” jest określeniem przyjmującym różne znaczenia w zależności od danego zagadnienia; nie w każdej sytuacji w której występuje „zupełność” mówi się o „zupełności”.

• Przestrzeń metryczna (lub przestrzeń jednostajna) nazywamy zupełną, gdy każdy ciąg Cauchy’ego elementów tej przestrzeni jest zbieżny do pewnego jej punktu.
• Miarę nazywamy zupełną, gdy każdy podzbiór zbioru miary zero, czyli każdy tzw. zbiór zaniedbywalny, jest mierzalny (i w konsekwencji miary zero).
• Porządek częściowy nazywamy zupełnym, gdy każdy jego ograniczony z dołu podzbiór ma kres dolny.

• Dla algorytmów zupełność oznacza że dany algorytm znajduje rozwiązanie jeśli takowe istnieją, a w przeciwnym razie wskazuje brak istnienia rozwiązania.
• W obliczeniowej teorii złożoności, problem P jest zupełny dla klasy złożoności C, pod pewnym rodzajem redukcji, jeśli P leży w C, i każdy problem z C da się sprowadzić do P używając danej redukcji. Na przykład każdy problem z klasy NP-zupełne jest zupełny dla klasy NP, jeśli jest redukowalny wielu-do-jednego w czasie wielomianowym.

• Logika matematyczna (pol.), Andrzej Mostowski niesprzeczność