Problemino di logica

[JackNewHouse]

Ecco il mio primo post


Siano A e B due insiemi finiti.
Si consideri l'insieme F = {f | f : A -> B } , che è l'insieme di tutte le funzioni possibili da A in B.

Qual è la cardinalità di F? Dimostrarlo.


(scrivendo |A| si intende la cardinalità di A)

[Kashaman]

è un problema proposto agli utenti o vuoi che te lo svolgiamo?
Se è il primo, se $|A|=n,|B|=m$ Allora $|F|=n^m$ se non sbaglio.
Nel secondo caso, dovresti proporre un tentativo di risoluzione.

[JackNewHouse]

sbagliato...
il tuo algoritmo funziona solo se n ed m sono uguali . se per esempio n < m da un risultato falso. Quello corretto sarebbe m^n (m elevato alla n, scusatemi per le formule... imparerò). Io l'ho gia più o meno risolto ma la mia dimostrazione non mi convince più di tanto. ho provato con una dimostrazione per induzione. Riguardo alla prima domanda... beh... svolgetelo se ne avete voglia , mi interessa confrontarmi più che altro con altre dimostrazioni.

[gundamrx91-votailprof]

Potresti scrivere la tua dimostrazione intanto...

[JackNewHouse]

si: ho fatto una dimostrazione per induzione sulla variabile n.
allora il caso base e' evidentemente vero : m^0=1 che e' l'insieme vuoto.
Passo induttivo:se m^n=F
allora m^n * m = F*m
ovvero m^(n+1) = F*m

A questo punto comincia la parte 'controversa' della mia dimostrazione; dimostrare che F*m e' la cardinalita' dell'insieme cercato.
Una funzione e' una relazione che associa ad ogni elemento di A un elemento di B, quindi se aggiungo un elemento ad A e' chiaro(?) che dovendo cercare l'insieme di tutte le possibili funzioni dovro' moltiplicare il tutto per |B|.

Esempio: se la cardinalita' di A e' 2 allora |F|= |B|*|B|
se la cardinalita' di A diventa 3 allora |F'| = |B|*|B|*|B| = |F|*|B|

..... Non fa una piega vero?