Halbe charakteristische Funktion

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

$\chi '_{A}\colon A\to \{1\},\;\;a\mapsto 1$.

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:

$\chi '_{A}\colon B\to \{0,1\},\;\;a\mapsto {\begin{cases}1&{\mbox{ falls }}a\in A\\{\mbox{undefiniert}}&{\mbox{ sonst }}\end{cases}}$

Semi-Entscheidbarkeit

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

• Rekursiv aufzählbare Menge