Esercizio su funzione caratteristica e verifica biezione

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 di un insieme non vuoto restituisce 1 se un elemento di è contenuto in A altrimenti 0.

Poco dopo la definizione, specifica che l'insieme di tutte le funzioni caratteristiche si denota con e spiega la dimostrazione della biettività di

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

1) essendo un insieme di funzioni, la funzione



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 sia . Allora per definizione di funzione caratteristica si ha , ovvero

In questo caso:

- perché dobbiamo introdurre un sottoinsieme 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.

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.

In particolare:

dovrebbe essere e rappresenta tutte le funzioni caratteristiche aventi per dominio e codominio (o comunque un qualsiasi insieme formato da due elementi).



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

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

Si, è l'insieme delle funzioni caratteristiche mentre è l'insieme delle parti.

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"?
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 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 che un esempio della dimostrazione che mi crea dubbi.

Sia un insieme non vuoto. Per ogni la funzione caratteristica di è la funzione definita da



Sia l'insieme di tutte le funzioni da in . In particolare per ogni .

Dimostrare che la funzione che manda ogni nella sua funzione caratteristica è una biezione.

Iniettività: dati distinti, o esiste oppure esiste . Nel primo caso si avrà e , nel secondo caso e . In ogni caso , per cui , cioè .

Suriettività: data , sia



allora per definizione di funzione caratteristica si ha , ovvero .

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 utilizza il simbolo matematico



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

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 due insiemi qualsiasi (non necessariamente numerici) e diversi dall'insieme vuoto.

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

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

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 ogni figlio) è possibile associare uno e un solo elemento di (una e una sola madre [biologica]).

Questa relazione definisce una funzione tra l'insieme .

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

Nel caso in esame la funzione



associa a ogni sottoinsieme di un insieme non vuoto la sola funzione caratteristica .

In maniera esplicita, per ogni



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

Attingendo al linguaggio informatico, la funzione prende in input un sottoinsieme di e fornisce in output la funzione .

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

Ad ogni modo tentiamo di dimostrare il seguente

Teorema

Siano

un insieme non vuoto;

l'insieme delle parti di ;

l'insieme delle funzioni caratteristiche



La funzione



che associa a ogni sottoinsieme la funzione caratteristica su



è una funzione biettiva.

Dimostrazione

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

Iniettività di

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

Consideriamo quindi due elementi distinti di , essi saranno necessariamente due insiemi che differiscono almeno di un elemento (in caso contrario sarebbero uguali!).

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



Analizziamo i due casi:

se , ossia se appartiene ad ma non a , per definizione di funzione caratteristica



Simmetricamente se , ossia se appartiene a ma non ad , per definizione di funzione caratteristica



In entrambi i casi, , di conseguenza le due funzioni caratteristiche non coincidono.

Dalla definizione di segue quindi che



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

Suriettività

Per mostrare che è una funzione suriettiva, bisogna far vedere che per ogni elemento dell'insieme di arrivo ( dev'essere una funzione di ) esiste almeno un elemento dell'insieme di partenza (sottoinsieme di ) tale che .

Consideriamo quindi una qualsiasi funzione



(è una funzione che appartiene a ) e prendiamo in considerazione l'insieme (è un sottoinsieme di ). In base alla definizione stessa di funzione caratteristica coincide con



e dunque . Ossia la funzione è suriettiva.

La biettività segue dalla definizione.

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

"Simulando" io dovrei prendere un insieme contenuto in facciamo .

Lo associo alla sua funzione caratteristica contenuta in (che se ho capito bene, queste funzioni differiscono nel dominio ovvero ci sarà una funzione per ogni sottoinsieme di giusto?) quindi dovrò "calcolare" dove la è un elemento del sottoinsieme scelto di e il risultato di questa ultima 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 con parametro un sottoinsieme di sia uguale alla funzione caratteristica di quel sottoinsieme

è corretto questo ragionamento?


2) Nella dimostrazione della suriettività, Perché si definisce un insieme 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

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

Consideriamo l'insieme formato da tre elementi



e costruiamo l'insieme delle parti , costituito da tutti i possibili sottoinsiemi di



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

Per come è definita, la funzione trasforma ogni insieme nella funzione caratteristica :



Osserva che fissato , la funzione è definita sull'intero insieme .

Se ad esempio fissiamo (è un elemento dell'insieme delle parti). In che modo lo trasforma Semplicemente:



dove è una funzione definita su e associa 1 agli elementi e 0 all'elemento 3




Nota che la variabile indipendente varia su .

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

Ogni funzione produce due possibili valori e sono infatti:



Ha senso quindi definire l'insieme formato dagli elementi di tale che ; per tutti gli elementi di che non appartengono ad , necessariamente (ricorda i possibili output di )

Osservazione: formalmente è la controimmagine di 1 mediante , in simboli . Se non conosci l'argomento, non preoccuparti, era solo per mettere i puntini sulle i.

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



definita come:



si comporta esattamente come - cioè associa 1 agli elementi di , 0 agli elementi che non stanno in - dunque .

Poiché questo ragionamento è valido indipendentemente dalla funzione allora possiamo affermare quanto segue:

per ogni esiste un insieme tale che , ossia è una funzione suriettiva.

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

Ricapitolando:

la funzione ritorna la funzione caratteristica di un insieme contenuto in {tex}P(X){\tex} non il "risultato" della funzione caratteristica

Quindi se se prendessi contenuto in P(X) allora la funzione F(X) ritornerebbe e non 0 o 1

Giusto?

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

Essendo una funzione caratteristica generica = a
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, e quindi x appartiene ad A) di X e quindi ad un elemento di 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?

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



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.


Esatto!


Non esattamente, devi dimostrare che per ogni funzione caratteristica appartenente a , esiste un insieme tale che .


Ci sei. 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.

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.


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

Sì, essenzialmente sì.