Conferma sul mio ragionamento per questa dimostrazione (insieme delle parti)

Messaggioda alecs00 » 16/09/2019, 19:55

Ciao a tutti. Dopo aver seguito una lezione all'università sugli insiemi, ho provato a ricostruire questa dimostrazione di cui mi ero perso alcuni pezzi, e vorrei conferma che sia corretta.

Parlando di insieme delle parti, vogliamo dimostrare che l'affermazione P(A) contiene 2^n elementi è valida per ogni n >= (maggiore o uguale) 1; dove n è il numero di elementi dell'insieme A.

Partiamo assumendo la verità di queste due affermazioni:
- P(A) contiene 2^n elementi è vera per n=1
- P(A) contiene 2^n elementi è vera per n=k (la mia prof ha usato questa lettera, immagino come si userebbe x o y o z...)

di conseguenza supponiamo che P(A) contiene 2^n elementi sarà vera anche per n=k+1 (in pratica la nostra ipotesi).

Procediamo prendendo un insieme A=(1,k,k+1) e lo dividiamo in due sottoinsiemi A1=(1,k) e A2=(k+1)

A questo punto sappiamo che:
- P(A1) contiene 2^k elementi
- P(A2) contiene 2^k elementi
- P(A1) è incluso in P(A)
- P(A2) è incluso in P(A)

Quindi uniamo i due sottoinsiemi per tornare a A, che come numero di elementi avrà quindi:
2^k + 2^k = 2^k (1+1) = 2^k+1

quindi 2^k = 2^k+1

per cui l'ipotesi iniziale è corretta.

Grazie in anticipo a chi saprà aiutarmi.
alecs00
Starting Member
Starting Member
 
Messaggio: 1 di 2
Iscritto il: 16/09/2019, 19:44

Re: Conferma sul mio ragionamento per questa dimostrazione (insieme delle parti)

Messaggioda @melia » 17/09/2019, 18:16

Se $ A_1$ è un sottoinsieme di $A={1, 2, ..., k, k+1}$, allora va scritto con le parentesi graffe, inoltre non va bene mettere in $ A_1$ solo $1$ e $k$, ma $ A_1={1, 2, ...,k}$, cioè tutti gli elementi di $A$ escluso l'ultimo $k+1$, per ipotesi $|P(A_1)|=2^k$, poi prendiamo tutti gli elementi di $P(A_1)$ è gli aggiungiamo l'elemento $k+1$ chiamo questo nuovo insieme P, questi insiemi saranno tutti diversi da quelli di $P(A_1)$ perché contengono un elemento che nei precedenti non c'era, e saranno anche loro di cardinalità $2^k$, cioè tanti quanti $|P(A_1)|$, i due insiemi inoltre danno tutti gli elementi di $P(A)$, ne segue che
$|P(A)|=|P(A_1)|+|P|=2^k+2^k=2*2^k=2^(k+1)$
Sara Gobbato

732 chilometri senza neppure un autogrill
Avatar utente
@melia
Moderatore globale
Moderatore globale
 
Messaggio: 11787 di 21976
Iscritto il: 16/06/2008, 18:02
Località: Padova

Re: Conferma sul mio ragionamento per questa dimostrazione (insieme delle parti)

Messaggioda Bokonon » 17/09/2019, 19:39

Giusto per interloquire...il numero delle parti composte da 0,1,2,...,n elementi non sono altro che i coefficienti dello sviluppo del binomio di newton $(a+b)^n$ Ponendo $a=b=1$ si ottiene il totale, ovvero $2^n$.
I coefficienti della binomiale non sono altro che le $C(n,k)$ ovvero le combinazioni ordinate senza ripetizione di k elementi da n elementi. $sum_(k=0)^n C(n,k)=2^n$

Infine le combinazioni non sono altro che le righe del triangolo di Tartaglia.
Per esempio la riga 1 4 6 4 1 significa:
- 1 sottoinsieme composto dal solo insieme vuoto (zero elementi)
- 4 sottoinsiemi composti da un solo elemento
- 6 sottoinsiemi composti da 2 elementi
- 4 sottoinsiemi composti da 3 elementi
- 1 sottoinsieme composto da 4 elementi

Il totale è $1+4+6+4+1=16=2^4$ quindi l'insieme totale è composto da 4 elementi
Avatar utente
Bokonon
Cannot live without
Cannot live without
 
Messaggio: 1548 di 5942
Iscritto il: 25/05/2018, 20:22


Torna a Secondaria II grado

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite