Halbe charakteristische Funktion

Funktion, die jedes Element einer Menge sicher als solches identifiziert, aber nicht enthaltene Elemente einer Obermenge nicht sicher ausschließen kann

Die halbe charakteristische Funktion oder partielle charakteristische Funktion ist eine Funktion der Mathematik, die eine Menge identifiziert. Sie ist folgendermaßen definiert:

.

Wie man sehen kann, steckt die ganze „Magie“ der Funktion im Definitionsbereich. Ist nun A eine Teilmenge einer größeren Menge B, so ist χ'A auf B\A undefiniert. Man erhält dann:

Semi-Entscheidbarkeit

Bearbeiten

Die halbe charakteristische Funktion kann auf B alle Elemente nennen, die zu A gehören, aber Elemente, die nicht zu A gehören, nicht recht ausschließen. Man spricht davon, χ'A sei partiell. Ist nun χ'A außerdem berechenbar, so nennt man A semi-entscheidbar oder rekursiv aufzählbar, da man zwar alle Elemente aufzählen kann, aber die Elemente B\A nicht ausschließen kann. Dafür benötigt man die charakteristische Funktion, die total ist.

Siehe auch

Bearbeiten