Funzioni caratteristiche

Funzioni caratteristiche e biiezione tra 2^A e P(A)

Definizione

Sia dato un insieme A e un suo sottoinsieme X . Posto 2 = {0, 1} (oppure un qualsiasi altro insieme di cardinalità due), si definisce funzione caratteristica del sottoinsieme X Í A


*la funzione h_X* Î2^A = { f : A®2 } definita da**	h_X(a) =	{	0		, se aÎA \ X
*la funzione h_X* Î2^A = { f : A®2 } definita da**	h_X(a) =	{	1		, se aÎX

Si ha quindi che

aÎX h_X(a) = 1

e questo spiega il nome di funzione caratteristica del sottoinsieme.

Risulta dunque

X = h^{^-1}_X( { 1 })

Esempio

Dati A = {3, 5, 6, p} e X = { 5, p}Í A, la funzione caratteristica di X è

h_X :	A	®	{0,1}
	3	®	0
	5	®	1
	6	®	0
	p	®	1

Esempio

Dati A = R² e X = { (x, y)ÎR² / ax+by+c=0} Í R², la funzione caratteristica di X è definita da


	h_X((x, y)) =	{	0		, se ax+by+c ¹ 0
	h_X((x, y)) =	{	1		, se ax+by+c = 0

Osservazione

La funzione caratteristica di un sottoinsieme X Í A è definita anche se X = f e in questo caso si ha

h_f (a) = 0 "aÎA

Se X = A risulta invece

h_A (a) = 1 "aÎA

Definizione

Sia dato un insieme A. L'insieme 2^A ={ f : A®2 } delle funzioni di dominio A e codominio 2 = {0,1} (oppure un qualsiasi altro insieme di cardinalità due) si chiama insieme delle funzioni caratteristiche di A

Esempio

Dato A = {3, 5, 6, p} e la seguente funzione caratteristica di A

h :	A	®	{ 0, 1}
	3	®	1
	5	®	1
	6	®	0
	p	®	1

, il sottoinsieme X di A individuato dalla funzione h è X = { 3, 5, p}, ossia è X = h^{^-1}({1})

Proposizione

Dato un insieme A (finito o infinito), i due insiemi 2^A ={ f : A®2 } e P(A) = { X / X Í A } sono equipotenti

| P(A) | = | 2^A |

Dim.

Devo esibire una biiezione tra 2^A e P(A). Prendiamo la funzione

a : 2^A ® P(A) definita da a ( f ) = f^{^-1}( {1} )

La funzione a è iniettiva poichè " f, gÎ2^A con f ¹ g si ha

f ¹ g $aÎA / f(a) ¹ g(a) $aÎA / ( f(a) =1 e g(a) =0) aut ( f(a) =0 e g(a) =1)

e , supposto che risulti f(a) =1 e g(a) =0, segue che

$aÎA / aÎf^{^-1}({1}) e ag^{^-1}({1}) f^{^-1}({1}) ¹ g^{^-1}({1}) a ( f ) ¹ a (g)

Per dimostrare che la funzione a è suriettiva devo far vedere che

"XÎP(A) $hÎ2^A / a(h) = X

ovvero, per come abbiamo definito la funzione a , che

"XÎP(A) $hÎ2^A / h^{^-1}({1}) = X

e per questo basta prendere la funzione h definita da
	h(a) =	{	0		, se aÎA \ X
	h(a) =	{	1		, se aÎX

Osservazione

Se A è finito, allora | 2^A | = 2^{| A |}

Esempio

Dato A = {0, 1, 2}, esplicitare l'insieme 2^A ={ h : A®2}

Essendo | A | = 3, allora | 2^A | = 2³ = 8.

Si ha P(A) = {f , {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}

Ad ognuno dei sottoinsiemi di A corrisponde una funzione caratteristica

h_f :	A	®	2			h_{0}:	A	®	2			h_{1}:	A	®	2			h_{2}:	A	®	2			h_{0,1}:	A	®	2			h_{0,2}:	A	®	2			h_{1,2}:	A	®	2			h_{0,1,2}:	A	®	2
	0	®	0				0	®	1				0	®	0				0	®	0				0	®	1				0	®	1				0	®	0				0	®	1
	1	®	0				1	®	0				1	®	1				1	®	0				1	®	1				1	®	0				1	®	1				1	®	1
	2	®	0				2	®	0				2	®	0				2	®	1				2	®	0				2	®	1				2	®	1				2	®	1

La biiezione a : 2^A i P(A) definita da a ( h ) = h^{^-1}({1}) utilizzata nella dimostrazione del teorema è

a :	2^A	®	P(A)
	h_f	®	f
	h_{0}	®	{0}
	h_{1}	®	{1}
	h_{2}	®	{2}
	h_{0,1}	®	{0,1}
	h_{0,2}	®	{0,2}
	h_{1,2}	®	{1,2}
	h_{0,1,2}	®	{0,1,2}