Discussioni su Algebra astratta, Logica Matematica, Teoria dei Numeri, Matematica Discreta, Teoria dei Codici, Algebra degli insiemi finiti, Crittografia.
31/07/2023, 19:00
Sia $X$ un insieme e sia $P(X)$ l’insieme delle parti di $X$, cioè l’insieme i cui elementi sono tutti e soli i sottoinsiemi di $X$. Se $f:X->P(X)$ è una funzione, allora si provi che $f$ non è suriettiva.
Per dimostrarlo ho pensato di fare così:
Consideriamo l'insieme $S={x inX|xnotinf(x)}inP(X)$, supponiamo per assurdo che $Ssubef(X)$, quindi $EEx inX$ tale che $f(x)=S$. Ora se $x inS$ si avrebbe che $x inf(x)$ il che assurdo poichè siccome $x inS$ si dovrebbe avere $xnotinf(x)$, mentre se $xnotinS$ allora $xnotinf(x)$ e quindi per definizione di $S$ si avrebbe $x inS$ assurdo. Per cui tale $x$ non può esistere e dunque $Snotsubef(X)$ e quindi $f$ non è suriettiva, va bene?
31/07/2023, 19:10
Per dimostrarlo ho pensato di fare così:
Sì, va essenzialmente bene, ma l'idea di dimostrarlo così non è venuta a te!
31/07/2023, 19:22
megas_archon ha scritto:Per dimostrarlo ho pensato di fare così:
Sì, va essenzialmente bene, ma l'idea di dimostrarlo così non è venuta a te!
No intendevo dire come l'avrei dimostrata io, non che l'ho dimostrata io, haahhaha.
31/07/2023, 21:39
andreadel1988 ha scritto:Consideriamo l'insieme $S={x inX|xnotinf(x)}inP(X)$,
Perché?
andreadel1988 ha scritto: supponiamo per assurdo che \( \displaystyle \color{red}S\subseteq f(X) \) ,
- In una dimostrazione per assurdo devi negare la tesi, quindi supponiamo per assurdo che...
- Se \( \displaystyle X=\{1,2,3\} \) allora \( \displaystyle \mathcal{P}(X)=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},X\} \) . Preso \( \displaystyle S\subseteq X \) , ha senso scrivere \( \displaystyle S\subseteq\mathcal{P}(X) \) ?
andreadel1988 ha scritto: quindi $EEx inX$ tale che $f(x)=S$.
Perché?
andreadel1988 ha scritto:Ora se $x inS$ si avrebbe che \( \displaystyle x \in f(x) \) il che assurdo poichè siccome $x inS$ si dovrebbe avere $xnotinf(x)$, mentre se $xnotinS$ allora $xnotinf(x)$ e quindi per definizione di $S$ si avrebbe $x inS$ assurdo.
Un po' ingarbugliato... ci sono due possibilità, o \( \displaystyle x\in S \) oppure \( \displaystyle x\not\in S \) :
- se \( \displaystyle x\in S \) , allora \( \displaystyle x\not\in f(x) \) , ma \( \displaystyle f(x) = S \) , quindi contemporaneamente si ha \( \displaystyle x\in S \) e \( \displaystyle x\not\in S \) , che è una contraddizione;
- se \( \displaystyle x\not\in S \) , allora \( \displaystyle x\in f(x) \) , ma \( \displaystyle f(x)=S \) , quindi contemporaneamente si ha \( \displaystyle x\in S \) e \( \displaystyle x\not\in S \) , che è di nuovo una contraddizione.
andreadel1988 ha scritto:
Per cui tale \( \displaystyle \color{red}x \) non può esistere e dunque \( \displaystyle \color{red}S\not\subseteq f(X) \) e quindi \( \displaystyle \color{red} \) non è suriettiva.
In ogni caso raggiungi una contraddizione, quindi...
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.