Halbe charakteristische Funktion
# 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.

