Zupełność

Ogólnie obiekt jest zupełny, gdy nie trzeba niczego do niego dodawać. To znaczenie jest uściślane w wielu dziedzinach.

Zupełność w logice

W logice, semantyczna zupełność jest przeciwieństwem 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, $\models_{\mathrm S} A\ \to\ \vdash_{\mathrm S} A$.

• 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 $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 Peano, który byłby zarówno niesprzeczny jak i zupełny.

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

• 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 pewnej właściwości wtedy i tylko wtedy, gdy każde zdanie posiadające daną cechę jest twierdzeniem.

Zupełność w matematyce

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.

Zupełność w informatyce

• 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 reukowalny wielu-do-jednego w czasie wielomianowym.

Odniesienia

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