Esercizio su funzione caratteristica e verifica biezione

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.
Questa sezione è un contenitore temporaneo per i topic speciali a pagamento (One-Shot)

Se hai acquistato uno o più Topic speciali, puoi pubblicarli qui cliccando su "Apri un Topic".

Il registro completo dei Topic risolti e in corso è disponibile sul proprio profilo.

Esercizio su funzione caratteristica e verifica biezione #98598

avt
fffight
Punto
Al corso d'esame di Logica Matematica (Primo Anno di università dipartimento di informatica) si è affrontato l'argomento della funzione caratteristica la quale, a quanto ho capito, è una funzione che dato un sottoinsieme A di un insieme X non vuoto restituisce 1 se un elemento di x è contenuto in A altrimenti 0.

Poco dopo la definizione, specifica che l'insieme di tutte le funzioni caratteristiche si denota con 2^x e spiega la dimostrazione della biettività di F: P(X) \to 2^x.

Sia la dimostrazione dell'iniettività che della suriettività mi suscitano diversi dubbi:

1) essendo 2^x un insieme di funzioni, la funzione

F: P(X) \to 2^x

ha come codominio un insieme di funzioni. Questo concetto non mi è assolutamente chiaro, nel senso, come si rappresenta un insieme di funzioni da un punto di vista concettuale? non riesco proprio ad immaginarmi una funzione che dato un insieme restituisca un altra funzione....

2) come si dimostra l'iniettività e la suriettività di una tale funzione? Nell'esempio c'è scritto il ragionamento da seguire però, soprattutto per dimostrare la suriettività, svolge dei ragionamenti abbastanza astratti basati sulle funzioni caratteristiche che non ho molto compreso applicate nel contesto.

Ad esempio, per la suriettività il testo afferma: Data f: X \to \{0,1\} sia A = \{x \in X : f(x) = 1\}. Allora per definizione di funzione caratteristica si ha Xa = f, ovvero F(A) = f

In questo caso:

- perché dobbiamo introdurre un sottoinsieme A per dimostrare la suriettività?

-Perché questa è una dimostrazione valida?

Chiedo il vostro aiuto in quanto veramente disperato, ho provato a confrontarmi in tutti i modi eppure c'è sempre qualcosa che mi sfugge. Sento che manca poco eppure non riesco e questo mi fa perdere le speranze oltre che provocare una perdita immediata di autostima :(

Confido in voi, vi ringrazio per l'attenzione.
 
 

Esercizio su funzione caratteristica e verifica biezione #98600

avt
Ifrit
Ambasciatore
Ciao fffight,

ho bisogno di chiederti alcune delucidazioni in merito alle notazioni usate, purtroppo ogni insegnante utilizza i simboli che preferisce e non sempre sono chiari senza un minimo di contesto. emt

In particolare:

2^{x} dovrebbe essere 2^{X} e rappresenta tutte le funzioni caratteristiche aventi per dominio X e codominio \{0,1\} (o comunque un qualsiasi insieme formato da due elementi).

2^{X}=\{f:X\to \{0,1\}\}

Dal contesto mi pare di comprendere che P(X) rappresenti l'insieme delle parti dell'insieme X e fin qui ok. Il problema sorge nel momento in cui scrivi Xa senza attribuirgli alcun significato. emt

Inoltre come agisce la funzione F? Non disperarti troppo, sono argomenti abbastanza delicati all'inizio, ma poi ci si prende la mano.

Esercizio su funzione caratteristica e verifica biezione #98601

avt
fffight
Punto
Si,  2^x è l'insieme delle funzioni caratteristiche mentre  P(x) è l'insieme delle parti.

 Xa l'ha definita come una funzione caratteristica generica di A sottoinsieme di un insieme non vuoto X.

Per quanto riguarda la funzione F, potresti specificare meglio cosa intendi per "come agisce"? emt
Da quello che ho capito dalla spiegazione in aula, la funzione F ha come dominio l'insieme delle parti e come codominio l'insieme delle funzioni caratteristiche. In pratica per ogni insieme di  P(x) la funzione restituisce la funzione caratteristica di quel insieme.

In ogni caso riporto la dimostrazione fatta a lezione per spiegare questo concetto.
Comprende sia la definizione di  Xa che un esempio della dimostrazione che mi crea dubbi.

Sia X un insieme non vuoto. Per ogni A\subseteq X la funzione caratteristica di A è la funzione \chi_{A}: X\to \{0,1\} definita da

\chi_{A}=\begin{cases}1&\mbox{se} \ x\in A\\ 0&\mbox{se}\ x\notin A\end{cases}

Sia 2^{X} l'insieme di tutte le funzioni da X in \{0,1\}. In particolare \chi_{A}\in 2^{X} per ogni A\in\mathcal{P}(X).

Dimostrare che la funzione F:\mathcal{P}(X)\to 2^{X} che manda ogni A\subseteq X nella sua funzione caratteristica F(A)=\chi_{A} è una biezione.

Iniettività: dati A, B\in\mathcal{P}(X) distinti, o esiste x\in A-B oppure esiste x\in B-A. Nel primo caso si avrà \chi_{A}(x)=1 e \chi_{B}(x)=0, nel secondo caso \chi_{A}(x)=0 e \chi_{B}(x)=1. In ogni caso \chi_{A}(x)\ne \chi_{B}(x), per cui \chi_{A}\ne \chi_{B}, cioè F(A)\ne F(B).

Suriettività: data f:X\to \{0,1\}, sia

A=\{x\in X|f(x)=1\}

allora per definizione di funzione caratteristica si ha \chi_{A}=f, ovvero F(A)=f.

Esercizio su funzione caratteristica e verifica biezione #98602

avt
Ifrit
Ambasciatore
Perfetto, ora mi è chiaro. Grazie per l'immagine, purtroppo c'era un conflitto di simboli simili e non riuscivo a raccapezzarmici. Nota infatti che per indicare la funzione caratteristica su un insieme A utilizza il simbolo matematico

\chi_{A}(x):=\begin{cases}1&\mbox{se} \ x\in A\\ 0&\mbox{se} \ x\notin A\end{cases}

dove \chi è la ventiduesima lettera dell'alfabeto greco da non confondere con X.

Ad ogni modo tentiamo di rispondere alle domande:

1. il concetto di funzione in matematica è molto più generale rispetto a quello a cui siamo abituati.

Alle scuole superiori, le funzioni sono presentate come relazioni che associano a ogni numero del dominio, uno e un solo numero del codominio.

Questa definizione va bene nel momento in cui il dominio e il codominio sono insiemi numerici, però l'idea di funzione può essere tranquillamente generalizzata a insiemi qualsiasi: l'importante è che venga rispettata la definizione.

Siano dati A \ \mbox{e} \ B due insiemi qualsiasi (non necessariamente numerici) e diversi dall'insieme vuoto.

f è una funzione dall'insieme A all'insieme B se e solo se a ogni elemento a di A associa uno e un solo elemento b di B.

Un esempio: considera come insieme di partenza A l'insieme dei figli e come insieme di arrivo l'insieme delle madri B.

Come legge di corrispondenza (o se vuoi relazione) possiamo considerare la seguente

"a è figlio di b"

che associa a ogni figlio la propria madre.

Essa è una funzione, infatti a ogni elemento dell'insieme di partenza A (a ogni figlio) è possibile associare uno e un solo elemento b di B (una e una sola madre [biologica]).

Questa relazione definisce una funzione tra l'insieme A\ \mbox{e} \ B.

In questo caso, non puoi "rappresentare" la funzione, però intuisci che lo è perché rispetta la definizione generale.

Nel caso in esame la funzione

F:P(X)\to 2^{X}

associa a ogni sottoinsieme A di un insieme non vuoto X la sola funzione caratteristica \chi_{A}(x).

In maniera esplicita, per ogni A\subset X

F(A)=\chi_{A}(x)=\begin{cases}1&\mbox{se} \ x\in A \\ 0&\mbox{se} \ x\notin A\end{cases} \ \ \

(ecco cosa intendevo: non avevi scritto come agiva F emt ).

Attingendo al linguaggio informatico, la funzione F prende in input un sottoinsieme A di X e fornisce in output la funzione \chi_{A}(x).

Ti faccio notare che l'idea di funzione sta alla base dell'informatica, quindi assimilala bene. emt

Ad ogni modo tentiamo di dimostrare il seguente

Teorema

Siano

\bullet \ \ \ X un insieme non vuoto;

\bullet \ \ \ P(X) l'insieme delle parti di X;

\bullet \ \ \ 2^{X} l'insieme delle funzioni caratteristiche

2^{X}=\{f: X\to \{0,1\}\}

La funzione

F:P(X)\to 2^{X}

che associa a ogni sottoinsieme A\subseteq X la funzione caratteristica su A

F(A)=\chi_{A}(x)

è una funzione biettiva.

Dimostrazione

Per definizione, una funzione è biettiva se e solo se è sia una funzione iniettiva che una funzione suriettiva, ergo affinché F sia una biezione è necessario dimostrare sia l'iniettività che la suriettività.

Iniettività di F

Per dimostrare che F è a tutti gli effetti una funzione iniettiva è sufficiente mostrare che essa trasforma due elementi distinti dell'insieme di partenza (P(X)) in due elementi distinti dell'insieme di arrivo.

Consideriamo quindi due elementi distinti di P(X), essi saranno necessariamente due insiemi A\ \mbox{e} \ B che differiscono almeno di un elemento (in caso contrario sarebbero uguali!).

Proprio perché i due insiemi sono distinti, esisterà un elemento x che appartiene alla differenza insiemistica A\setminus B oppure a B\setminus A, ossia

A\ne B\implies \exists x\in A\setminus B\ \mbox{oppure} \ \exists x\in B\setminus A

Analizziamo i due casi:

se x\in A\setminus B, ossia se x appartiene ad A ma non a B, per definizione di funzione caratteristica

\\ \chi_{A}(x)=1\ \ \ \mbox{perch}\acute{\mbox{e}} \ x\in A \\ \\ \chi_{B}(x)=0 \ \ \ \mbox{perch}\acute{\mbox{e}} \ x\notin B

Simmetricamente se x\in B\setminus A, ossia se x appartiene a B ma non ad A, per definizione di funzione caratteristica

\\ \chi_{A}(x)=0\ \ \ \mbox{perch}\acute{\mbox{e}} \ x\notin A \\ \\ \chi_{B}(x)=1 \ \ \ \mbox{perch}\acute{\mbox{e}} \ x\in B

In entrambi i casi, \chi_{A}(x)\ne \chi_{B}(x), di conseguenza le due funzioni caratteristiche non coincidono.

Dalla definizione di F segue quindi che

F(A)\ne F(B)

Abbiamo quindi dimostrato che a due elementi distinti dell'insieme di partenza, F associa due elementi distinti dell'insieme di arrivo, ossia F è iniettiva.

Suriettività

Per mostrare che F è una funzione suriettiva, bisogna far vedere che per ogni elemento f dell'insieme di arrivo (f dev'essere una funzione di 2^{X}) esiste almeno un elemento A dell'insieme di partenza (sottoinsieme di X) tale che F(A)=f.

Consideriamo quindi una qualsiasi funzione

f:X\to \{0,1\}

(è una funzione che appartiene a 2^{X}) e prendiamo in considerazione l'insieme A=\{x\in X: f(x)=1\} (è un sottoinsieme di X). In base alla definizione stessa di funzione caratteristica \chi_{A} coincide con f

\chi_{A}=f

e dunque F(A)=f. Ossia la funzione F è suriettiva.

La biettività segue dalla definizione.
Ringraziano: Omega, Galois

Esercizio su funzione caratteristica e verifica biezione #98603

avt
fffight
Punto
Ti ringrazio per la esauriente risposta.
Mi ha aiutato a comprendere meglio il contesto generale della dimostrazione.
Mi rimangono, però, alcuni dubbi.
Cerco di spiegarli il più dettagliato possibile:

1) Quando una funzione porta un elemento del suo dominio nel suo codominio (composto da un insieme di funzioni) restituisce, come valore, il risultato della funzione (scelta dal codominio) associata all'elemento del dominio scelto?

Provo a fare l'esempio con la funzione dell'esercizio:

Io ho P(X) \to 2^x

"Simulando" io dovrei prendere un insieme contenuto in P(X) facciamo {a,b,c}.

Lo associo alla sua funzione caratteristica contenuta in 2^x (che se ho capito bene, queste funzioni differiscono nel dominio ovvero ci sarà una funzione per ogni sottoinsieme di  P(x) giusto?) quindi dovrò "calcolare" \chi a (y) dove la y è un elemento del sottoinsieme scelto di  P(x) e il risultato di questa ultima \chi a (y) dovrebbe essere il "risultato" della funzione iniziale.

Questo dovrebbe funzionare perché ti dice che la funzione "funziona" (scusate il gioco di parole) in modo tale che la funzione F con parametro un sottoinsieme di X sia uguale alla funzione caratteristica di quel sottoinsieme

è corretto questo ragionamento?


2) Nella dimostrazione della suriettività, Perché si definisce un insieme A contenente soltanto gli elementi a cui la funzione caratteristica "assegna" 1 quando, la funzione caratteristica, almeno nella mia concezione, dovrebbe essere sempre definita in qualsiasi caso? in quanto ritorna 0 o 1 in ogni caso possibile

Esercizio su funzione caratteristica e verifica biezione #98607

avt
Ifrit
Ambasciatore
Penso di aver capito quale sia il tuo problema. Facciamo così: mettiamoci comodi scegliendo insiemi semplici e gestibili.

Consideriamo l'insieme X formato da tre elementi

X=\{1,2,3\}

e costruiamo l'insieme delle parti P(X), costituito da tutti i possibili sottoinsiemi di X

P(X)=\{\emptyset,\ \{1\},\ \{2\},\ \{3\}, \ \{1,2\},\ \{1,3\}, \ \{2,3\}, \ \{1,2,3\}\}

Osserviamo che gli elementi dell'insieme delle parti sono a loro volta insiemi.

Per come è definita, la funzione F trasforma ogni insieme A\in P(X) nella funzione caratteristica \chi_{A}: X\to \{0,1\}:

\begin{matrix} F: & P(X) & \longrightarrow & 2^{X} \\ & A & \longmapsto & \chi_{A} \end{matrix}

Osserva che fissato A\in P(X), la funzione F(A)=\chi_{A} è definita sull'intero insieme X.

Se ad esempio fissiamo A=\{1,2\} (è un elemento dell'insieme delle parti). In che modo lo trasforma F\ ? Semplicemente:

F(A)=F(\{1,2\})=\chi_{A}=\chi_{\{1,2\}}

dove \chi_{\{1,2\}} è una funzione definita su X=\{1,2,3\} e associa 1 agli elementi 1 \ \mbox{e} \ 2 e 0 all'elemento 3


\chi_{\{1,2\}}(x)=\begin{cases}1&\mbox{se} \ x=1 \ \vee \ \ x=2 \\ \\ 0&\mbox{se} \ x=3\end{cases}

Nota che la variabile indipendente x varia su X.

Per quanto concerne la seconda domanda: nella dimostrazione si considera quell'insieme perché "siamo furbi".

Ogni funzione f\in 2^{X} produce due possibili valori e sono \{0,1\} infatti:

\begin{matrix} f: & X & \longrightarrow & \{0,1\} \\ \\ & x & \longmapsto & f(x)=1\ \dot{\vee} \ f(x)=0 \end{matrix}

Ha senso quindi definire l'insieme A=\{x\in X: f(x)=1\} formato dagli elementi di X tale che f(x)=1; per tutti gli elementi di X che non appartengono ad A, necessariamente f(x)=0 (ricorda i possibili output di f)

Osservazione: formalmente A è la controimmagine di 1 mediante f, in simboli A=f^{-1}(\{1\}). Se non conosci l'argomento, non preoccuparti, era solo per mettere i puntini sulle i.

Perché lo fa? Semplicemente perché la funzione F trasforma tale insieme nella seguente funzione caratteristica

F(A)=\chi_{A}

definita come:

\chi_{A}(x)=\begin{cases}1&\mbox{se} \ x\in A \\ \\ 0&\mbox{se} \ x\notin A\end{cases} \ \ \ \forall x\in X

F(A)=\chi_{A} si comporta esattamente come f - cioè associa 1 agli elementi di A, 0 agli elementi che non stanno in A - dunque F(A)=f.

Poiché questo ragionamento è valido indipendentemente dalla funzione f\in 2^{X} allora possiamo affermare quanto segue:

per ogni f\in 2^{X} esiste un insieme A\in P(X) tale che F(A)=f, ossia F è una funzione suriettiva.

Esercizio su funzione caratteristica e verifica biezione #98608

avt
fffight
Punto
Grazie Ifrit per la risposta! Hai proprio centrato il dubbio che avevo, ovvero capire come funzionasse con un insieme di funzioni.

Ricapitolando:

la funzione F(X): P(X) -> 2^x ritorna la funzione caratteristica di un insieme contenuto in {tex}P(X){\tex} non il "risultato" della funzione caratteristica

Quindi se X = {1,2,3} se prendessi A = {1,2} contenuto in P(X) allora la funzione F(X) ritornerebbe \chi\{1,2\} e non 0 o 1

Giusto?

Per quanto riguarda la dimostrazione della suriettività a livello concettuale dovrebbe essere:

Essendo una funzione caratteristica generica = a  X -> /{0,1/}
e dato 2^x come insieme di tutte queste funzioni, se applico questa funzione caratteristica ad un sottoinsieme A (dove per ogni x di X,  f(x) = 1 e quindi x appartiene ad A) di X e quindi ad un elemento di  P(X) allora troverò che la funzione caratteristica applicata al sottoinsieme A è definita per quel sottoinsieme A
ed essendo un ragionamento generico questa dimostrazione si può applicare a tutti i sottoinsiemi di X

Quindi per l'iniettività in questo caso controllo che a valori diversi non corrispondano funzioni del codominio uguali quindi controllo i valori delle funzioni caratteristiche e dimostro che a elementi di sottoinsiemi diversi corrispondono valori di funzione caratteristica diversa

Per quanto riguarda la suriettività cerco di vedere se ogni funzione del codominio è definita da un insieme di P(X). Per farlo prendo un insieme di P(X) quindi un sottoinsieme A di X definito nell'ambito della funzione caratteristica f come A = {x in X tale che f(x) = 1} e per definizione la funzione caratteristica risulterà definita con valori 1 per ogni elemento di X appartente al sottoinsieme dato in "input" altrimenti con 0

Dovrebbe essere giusto almeno a grandi linee? emt

Esercizio su funzione caratteristica e verifica biezione #98610

avt
Ifrit
Ambasciatore
La funzione F(X): P(X) -> 2^x [Meglio scrivere F:P(X)\to 2^{X}, attento alle maiuscole, non sono casuali] ritorna la funzione caratteristica di un insieme contenuto in P(X) non il "risultato" della funzione caratteristica

Quindi se X = \{1,2,3\} se prendessi A = \{1,2\} contenuto in P(X) allora la funzione F(X) [ F(A)] ritornerebbe \chi_{\{1,2\}} e non 0 o 1. [Esatto!]

Giusto?

Ho messo tra le parentesi quadre e in grassetto i miei commenti, cura maggiormente il matematichese. emt

Per quanto riguarda la dimostrazione della suriettività a livello concettuale dovrebbe essere:

Essendo una funzione caratteristica generica uguale a X \to\{0,1\} e dato 2^X come insieme di tutte queste funzioni, se applico questa funzione caratteristica ad un sottoinsieme A (dove per ogni x di X, f(x) = 1 e quindi x appartiene ad A) di X e quindi ad un elemento di P(X) allora troverò che la funzione caratteristica applicata al sottoinsieme A è definita per quel sottoinsieme A ed essendo un ragionamento generico questa dimostrazione si può applicare a tutti i sottoinsiemi di X.


Penso che tu abbia capito l'idea, però il linguaggio non è preciso. Cerca di migliorare il linguaggio matematico, altrimenti l'insegnante non è in grado di capirti.

Quindi per l'iniettività in questo caso controllo che a valori diversi non corrispondano funzioni del codominio uguali quindi controllo i valori delle funzioni caratteristiche e dimostro che a elementi di sottoinsiemi diversi corrispondono valori di funzione caratteristica diversa

Esatto!

Per quanto riguarda la suriettività cerco di vedere se ogni funzione del codominio è definita da un insieme di P(X).

Non esattamente, devi dimostrare che per ogni funzione caratteristica fappartenente a 2^{X}, esiste un insieme A\in P(X) tale che F(A)=f.

Per farlo prendo un insieme di P(X) quindi un sottoinsieme A di X definito nell'ambito della funzione caratteristica f come A = {x in X tale che f(x) = 1} e per definizione la funzione caratteristica risulterà definita con valori 1 per ogni elemento di X appartenente al sottoinsieme dato in "input" altrimenti con 0

Dovrebbe essere giusto almeno a grandi linee? emt

Ci sei. emt Alla luce di ciò, ti invito a rivedere per bene le definizioni e a rileggere con estrema attenzione la dimostrazione, porgendo la dovuta cautela al linguaggio tecnico.

Esercizio su funzione caratteristica e verifica biezione #98611

avt
fffight
Punto
Si il mio intento era quello di cercare di capire abbastanza bene il concetto generale e poi di scriverlo con rigido rigore matematico. Anche perché sono 5 giorni che sono bloccato su questo concetto.

Non esattamente, devi dimostrare che per ogni funzione caratteristica f appartenente a 2^{X}, esiste un insieme A\in P(X) tale che F(A)=f.

Quindi, sempre a livello concettuale, ogni f deve "provenire" da un sottoinsieme di A (ovviamente applicato alla funzione)

Esercizio su funzione caratteristica e verifica biezione #98612

avt
Ifrit
Ambasciatore
Sì, essenzialmente sì.
  • Pagina:
  • 1
Os