funzione caratteristica
funzione caratteristica
funzione caratteristica per un sottoinsieme S di un insieme X, (S ⊆ X), è la funzione ƒS: X → {0, 1} tale che, per ogni x ∈ X, il suo valore è 1 se x appartiene a S, è 0 altrimenti:
Tale funzione è anche detta funzione indicatrice e per essa si utilizzano anche i simboli 1s, oppure IS oppure ancora χS. A ogni sottoinsieme di X è così associata iniettivamente una funzione caratteristica. Poiché l’insieme delle parti di un insieme X ha cardinalità 2|X|, risulta che l’insieme delle funzioni di dominio e codominio N ha cardinalità 2N e quindi superiore al numerabile. Ciò implica che non tutte le funzioni aritmetiche sono funzioni calcolabili. Un insieme la cui funzione caratteristica è effettivamente calcolabile è detto insieme ricorsivo. La funzione caratteristica dell’insieme dei punti della semiretta x > 0 nel piano cartesiano Oxy è detta funzione di → Heaviside.
☐ In logica, a un predicato P definito in un insieme A, è associata una funzione caratteristica: se il predicato è unario, la funzione caratteristica associa il valore 1 (o, comunque indicato, il valore «vero») agli elementi x ∈ A per i quali P(x) è una proposizione vera, associa il valore 0 (o, comunque indicato, il valore «falso») a quelli per i quali è una proposizione falsa. Analogamente, se il predicato è binario, ternario, n-ario si considerano le coppie, terne, n-ple di elementi di A.