Esercizio su insieme infinito nel senso di Cantor
Ciao a tutti! Sono ancora alle prime armi con l'algebra e volevo chiedere un aiuto nella risoluzione del seguente esercizio:
Se un insieme $ X $ ammette una suriezione $ f:Xrarr X $ che non è iniettiva, dimostrare che $ X $ è infinito nel senso di Cantor.
Io ho provato a dimostrare l'esercizio in questo modo:
Innanzitutto ricordiamo che un insieme è infinito nel senso di Cantor se esiste un'applicazione iniettiva, ma non suriettiva, $ h:Xrarr X $.
Definisco $ h:Xrarr X $ nel seguente modo: $ h(x)=min(f^-1({x})) $. Dimostro che $ h $ è iniettiva, ma non suriettiva.
Suppongo esistano $ x_1,x_2in X $ tali che $ h(x_1)=h(x_2) $ . Allora $ min(f^-1({x_1}))=min(f^-1({x_2}))rArr x_1=x_2 $ , dunque $ h $ è iniettiva.
Ora conidero $ x in X $ . Poichè $ f $ è suriettiva (ma non iniettiva) si ha che $ f^-1({x})={min(f^-1{x}), x_1, x_2, ...}sube X $, con $ f(min(f^-1{x}))=f(x_1)=f(x_2)=... $ . Allora $ f^-1(x)\\ {h(x)}={x_1,x_2, ...}sup f^-1(x)supe X $ . Dunque $ h $ non è suriettiva e dunque $ X $ è infinito nel senso di Cantor.
Temo però di aver commesso degli errori. Non so se sia "giusto" definire $ h $ in quel modo, perchè nell'insieme $ X $ non viene indicata nessuna relazione d'ordine. Inoltre non vorrei aver sbagliato alcune implicazioni.
Se un insieme $ X $ ammette una suriezione $ f:Xrarr X $ che non è iniettiva, dimostrare che $ X $ è infinito nel senso di Cantor.
Io ho provato a dimostrare l'esercizio in questo modo:
Innanzitutto ricordiamo che un insieme è infinito nel senso di Cantor se esiste un'applicazione iniettiva, ma non suriettiva, $ h:Xrarr X $.
Definisco $ h:Xrarr X $ nel seguente modo: $ h(x)=min(f^-1({x})) $. Dimostro che $ h $ è iniettiva, ma non suriettiva.
Suppongo esistano $ x_1,x_2in X $ tali che $ h(x_1)=h(x_2) $ . Allora $ min(f^-1({x_1}))=min(f^-1({x_2}))rArr x_1=x_2 $ , dunque $ h $ è iniettiva.
Ora conidero $ x in X $ . Poichè $ f $ è suriettiva (ma non iniettiva) si ha che $ f^-1({x})={min(f^-1{x}), x_1, x_2, ...}sube X $, con $ f(min(f^-1{x}))=f(x_1)=f(x_2)=... $ . Allora $ f^-1(x)\\ {h(x)}={x_1,x_2, ...}sup f^-1(x)supe X $ . Dunque $ h $ non è suriettiva e dunque $ X $ è infinito nel senso di Cantor.
Temo però di aver commesso degli errori. Non so se sia "giusto" definire $ h $ in quel modo, perchè nell'insieme $ X $ non viene indicata nessuna relazione d'ordine. Inoltre non vorrei aver sbagliato alcune implicazioni.
Risposte
"maxfed":
Non so se sia "giusto" definire $ h $ in quel modo, perchè nell'insieme $ X $ non viene indicata nessuna relazione d'ordine.
Fai bene ad avere questo dubbio perchè in effetti $X$ non è (ben) ordinato quindi non puoi fare il minimo di un suo sottoinsieme.
Credo si possa fare così.
Definisci in $X$ la relazione di equivalenza \(x\sim x' \stackrel{(def.)}{\iff} f(x)=f(x')\).
Indicata con $[x]$ la classe di equivalenza di $x$, la funzione \(\psi_f\colon (X/\sim)\longrightarrow X\), definita da \(\psi_f([x]):=f(x)\), è ben definita e biiettiva. Infatti:
-) (buona definizione) \(x'\in [x] \Longrightarrow [x']= [x] \Longrightarrow \psi_f([x'])=\psi_f([x])=f(x)\);
-) (suriettività) \(\forall x\in X, \exists y\in X\mid y=f(x)=\psi_f([x])\);
-) (iniettività) \(\psi_f([x])=\psi_f([x'])\Longrightarrow f(x)=f(x')\Longrightarrow x\sim x'\Longrightarrow [x]=[x']\space\).
Inoltre, per l'Assioma della scelta, esiste una biiezione \(\varphi\colon (X/\sim)\longrightarrow R\), dove $R\subset X$ è un insieme completo di rappresentanti (l'inclusione è stretta, perché $f$ non è iniettiva). Pertanto, \(\phi\colon R\longrightarrow X\) definita da \(\phi:=\psi_f\circ \varphi^{-1}\) è una biiezione (composizione di biiezioni); quindi \(\phi^{-1}\colon X\longrightarrow R\) è una biiezione. Infine, \(\Phi\colon X\longrightarrow X\), definita da \(\Phi(x):=\phi^{-1}(x)\), è una funzione iniettiva ma non suriettiva (poichè \(\Phi(X)=\phi^{-1}(X)=R\subset X\)).
Definisci in $X$ la relazione di equivalenza \(x\sim x' \stackrel{(def.)}{\iff} f(x)=f(x')\).
Indicata con $[x]$ la classe di equivalenza di $x$, la funzione \(\psi_f\colon (X/\sim)\longrightarrow X\), definita da \(\psi_f([x]):=f(x)\), è ben definita e biiettiva. Infatti:
-) (buona definizione) \(x'\in [x] \Longrightarrow [x']= [x] \Longrightarrow \psi_f([x'])=\psi_f([x])=f(x)\);
-) (suriettività) \(\forall x\in X, \exists y\in X\mid y=f(x)=\psi_f([x])\);
-) (iniettività) \(\psi_f([x])=\psi_f([x'])\Longrightarrow f(x)=f(x')\Longrightarrow x\sim x'\Longrightarrow [x]=[x']\space\).
Inoltre, per l'Assioma della scelta, esiste una biiezione \(\varphi\colon (X/\sim)\longrightarrow R\), dove $R\subset X$ è un insieme completo di rappresentanti (l'inclusione è stretta, perché $f$ non è iniettiva). Pertanto, \(\phi\colon R\longrightarrow X\) definita da \(\phi:=\psi_f\circ \varphi^{-1}\) è una biiezione (composizione di biiezioni); quindi \(\phi^{-1}\colon X\longrightarrow R\) è una biiezione. Infine, \(\Phi\colon X\longrightarrow X\), definita da \(\Phi(x):=\phi^{-1}(x)\), è una funzione iniettiva ma non suriettiva (poichè \(\Phi(X)=\phi^{-1}(X)=R\subset X\)).
Non puoi evitare l’assioma della scelta?
Per assurdo, supponiamo che $X$ sia finito. Siano $x\!=y$ in $X$ con $f(x)=f(y)$.
Allora l’immagine di $f$ e’ $\{f(t):t \in X-\{x\}\}$ ed ha quindi $\le \#X - 1$ elementi.
Ma questo contraddice il fatto che $f$ e' suriettiva'.
Per assurdo, supponiamo che $X$ sia finito. Siano $x\!=y$ in $X$ con $f(x)=f(y)$.
Allora l’immagine di $f$ e’ $\{f(t):t \in X-\{x\}\}$ ed ha quindi $\le \#X - 1$ elementi.
Ma questo contraddice il fatto che $f$ e' suriettiva'.
Non c'è bisogno di passare da una relazione d'ordine ne da una relazione di equivalenza.
Puoi assumere tranquillamente che la cardinalità di \(X\) è infinita. Infatti Se \(X\) è di cardinalità finita allora se \( f: X \to X \) è suriettiva è anche iniettiva. Dunque puoi assumere senza perdita di generalità che \(X\) è di cardinalità infinita. Dunque esiste \(Y \subsetneq X \) e una biiezione \( g: Y \to \mathbb{N} \). E puoi costruire \( h : X \to X \) nel seguente modo:
\[ x \mapsto h(x) = \left\{\begin{matrix}
x& \text{se } x \not\in Y \\
y& \text{se } x \in Y \text{ con } g(x) = n \text{ dove } y \text{ è l'unico elemento tale che } g(y) = n+1
\end{matrix}\right. \]
Abbiamo allora che è iniettiva ma non suriettiva. Chiaramente è iniettiva perché se \(x,y \not\in Y \) e \( h(x) = h(y) \) allora chiaramente \( x = y \). Se \( x,y \in Y \) e \( x \neq y \) allora \( g(x) \neq g(y) \), dunque \( g(x) + 1 \neq g(y) + 1 \) abbiamo per definizione di \(h \) che \( g(h(x)) = g(x) + 1 \neq g(y) + 1 = g(h(y) ) \). Per biettività di \(g \) deduciamo che \( h(x) \neq h(y) \).
Chiaramente se \(x \in Y \) e \( y \not\in Y \) allora \( h(x) \in Y \) e \(h(y) \not\in Y \) pertanto \( h(x) \neq h(y) \). Inoltre \( h \) non è suriettiva poiché non lo è ristretta a \(Y\), infatti se \(x \in Y \) è tale che \(g(x) = 1 \) allora \(x \not\in h(X)\).
Edit:
Non credo, perché dimostrare che \(X\) è finito non è sufficiente. Ti serve dimostrare pure che un insieme di cardinalità infinita ammette una funzione \( h: X \to X \) iniettiva che non suriettiva. E questo credo che necessiti dell'assioma della scelta. Nella prova proposta da me ad esempio l'assioma della scelta (credo) l'ho usato quando ho affermato che esiste \(Y \subsetneq X \) tale che \( Y \) è in biiezione con \( \mathbb{N} \).
Puoi assumere tranquillamente che la cardinalità di \(X\) è infinita. Infatti Se \(X\) è di cardinalità finita allora se \( f: X \to X \) è suriettiva è anche iniettiva. Dunque puoi assumere senza perdita di generalità che \(X\) è di cardinalità infinita. Dunque esiste \(Y \subsetneq X \) e una biiezione \( g: Y \to \mathbb{N} \). E puoi costruire \( h : X \to X \) nel seguente modo:
\[ x \mapsto h(x) = \left\{\begin{matrix}
x& \text{se } x \not\in Y \\
y& \text{se } x \in Y \text{ con } g(x) = n \text{ dove } y \text{ è l'unico elemento tale che } g(y) = n+1
\end{matrix}\right. \]
Abbiamo allora che è iniettiva ma non suriettiva. Chiaramente è iniettiva perché se \(x,y \not\in Y \) e \( h(x) = h(y) \) allora chiaramente \( x = y \). Se \( x,y \in Y \) e \( x \neq y \) allora \( g(x) \neq g(y) \), dunque \( g(x) + 1 \neq g(y) + 1 \) abbiamo per definizione di \(h \) che \( g(h(x)) = g(x) + 1 \neq g(y) + 1 = g(h(y) ) \). Per biettività di \(g \) deduciamo che \( h(x) \neq h(y) \).
Chiaramente se \(x \in Y \) e \( y \not\in Y \) allora \( h(x) \in Y \) e \(h(y) \not\in Y \) pertanto \( h(x) \neq h(y) \). Inoltre \( h \) non è suriettiva poiché non lo è ristretta a \(Y\), infatti se \(x \in Y \) è tale che \(g(x) = 1 \) allora \(x \not\in h(X)\).
Edit:
"Stickelberger":
Non puoi evitare l’assioma della scelta?
Non credo, perché dimostrare che \(X\) è finito non è sufficiente. Ti serve dimostrare pure che un insieme di cardinalità infinita ammette una funzione \( h: X \to X \) iniettiva che non suriettiva. E questo credo che necessiti dell'assioma della scelta. Nella prova proposta da me ad esempio l'assioma della scelta (credo) l'ho usato quando ho affermato che esiste \(Y \subsetneq X \) tale che \( Y \) è in biiezione con \( \mathbb{N} \).
"3m0o":
Non c'è bisogno di passare da una relazione d'ordine ne da una relazione di equivalenza.
Tuttavia non le metterei proprio sullo stesso piano: la relazione d'ordine semplicemente non c'è nel setting del problema; la relazione d'equivalenza, invece, sì (basta esplicitarla).
perché dimostrare che X è finito non è sufficiente
Ma non dimostro che $X$ e' finito. Va dimostrato "$X$ ammette $f$" $\Rightarrow$ "$X$ e' infinito".
Questo e' equivalente a dimostrare "$X$ e' finito" $\Rightarrow$ "$X$ non ammette $f$".
Infatti, se esistesse $f$, ottengo una contraddizione.
"Stickelberger":
Va dimostrato "$X$ ammette $f$" $\Rightarrow$ "$X$ e' infinito".
Questo e' equivalente a dimostrare "$X$ e' finito" $\Rightarrow$ "$X$ non ammette $f$".
Infatti, se esistesse $f$, ottengo una contraddizione.
Sarà equivalente, ma la richiesta dell'OP è dimostrare il seguente claim: $X$ insieme, \(f\colon X\to X\) suriettiva e non iniettiva \(\Longrightarrow \exists h\colon X\to X\) iniettiva e non suriettiva. Quindi, senza altra accezione di "finito" e "infinito". Almeno io l'ho interpretata così.
"Stickelberger":
Ma non dimostro che $X$ e' finito. Va dimostrato "$X$ ammette $f$" $\Rightarrow$ "$X$ e' infinito".
Questo e' equivalente a dimostrare "$X$ e' finito" $\Rightarrow$ "$X$ non ammette $f$".
Infatti, se esistesse $f$, ottengo una contraddizione.
Tu stai dicendo, se \(X \) è finito allora ottengo una contraddizione, perché non esiste questa \(f\) nelle ipotesi. Poi concludi quindi il claim è vero. Ma non è sufficiente la tua contraddizione per dire che il claim dell'OP è vero, l'unica cosa che puoi concludere è che \(X\) è di cardinalità infinita (ammettendo le ipotesi del claim). Quindi dimostri che \(X\) non è finito. Ma devi per l'appunto anche dimostrare che
"luca69":
\( \exists h\colon X\to X \) iniettiva e non suriettiva
edit:
perché dimostrare che X è finito non è sufficiente
Ho sbagliato, volevo scrivere:
perché dimostrare che \(X\) non è finito non è sufficiente.
Stiamo parlando di questo claim, giusto?
Se l'ipotesi e' falsa, il claim e' anche vero, perche' un'affermazione falsa implica tutto che vuoi.
L'affermazione "$A\Rightarrow B$" e' equivalente a "$(\not A) \vv B$". Non e' equivalente a "$A\^^ B$".
invece lo e'
Se un insieme X ammette una suriezione $f:X\rightarrow X$ che non è iniettiva, allora $X$ e' infinito
Se l'ipotesi e' falsa, il claim e' anche vero, perche' un'affermazione falsa implica tutto che vuoi.
L'affermazione "$A\Rightarrow B$" e' equivalente a "$(\not A) \vv B$". Non e' equivalente a "$A\^^ B$".
perché dimostrare che X non è finito non è sufficiente.
invece lo e'
"Stickelberger":
Stiamo parlando di questo claim, giusto?
Se un insieme X ammette una suriezione $f:X\rightarrow X$ che non è iniettiva, allora $X$ e' infinito
No, credo che l'omissione di "nel senso di Cantor" faccia la differenza rispetto all'OP.
No.
personalmente non sapevo nemmeno io che un insieme infinito "nel senso di Cantor" significasse questa roba qui. Dando per buona la definizione dell'OP la tua contraddizione non è sufficiente.
Edit:
Tu hai semplicemente dimostrato che per dimostrare il claim è sufficiente dimostrare che un insieme di cardinalità infinita è un insieme infinito nel senso di Cantor.
O detto in altro modo, è sufficiente dimostrare che un insieme \(X\) di cardinalità infinita ammette sempre una mappa \( X \to X \) iniettiva che non è suriettiva.
"maxfed":
Se un insieme $ X $ ammette una suriezione $ f:Xrarr X $ che non è iniettiva, dimostrare che $ X $ è infinito nel senso di Cantor.
Io ho provato a dimostrare l'esercizio in questo modo:
Innanzitutto ricordiamo che un insieme è infinito nel senso di Cantor se esiste un'applicazione iniettiva, ma non suriettiva, $ h:Xrarr X $.
personalmente non sapevo nemmeno io che un insieme infinito "nel senso di Cantor" significasse questa roba qui. Dando per buona la definizione dell'OP la tua contraddizione non è sufficiente.
Edit:
Tu hai semplicemente dimostrato che per dimostrare il claim è sufficiente dimostrare che un insieme di cardinalità infinita è un insieme infinito nel senso di Cantor.
O detto in altro modo, è sufficiente dimostrare che un insieme \(X\) di cardinalità infinita ammette sempre una mappa \( X \to X \) iniettiva che non è suriettiva.
No, credo che l'omissione di "nel senso di Cantor" faccia la differenza rispetto all'OP.
Ah! Grazie Luca69 e 3m0o . Errore mio. Avevo letto male. Neanche io sapevo
che un insieme infinito "nel senso di Cantor" significasse questa roba qui.
Non voglio entrare nei dettagli tecnici,
ma un insieme \(\displaystyle X\) che ammette l'esistenza di una funzione \(\displaystyle f:X\to X\) suriettiva che non sia iniettiva è un insieme dualmente infinito secondo Dedekind!
Secondo la teoria assiomatica ZF, questi non sono sempre insiemi infiniti secondo Dedekind[nota]Un insieme \(\displaystyle X\) che ammette l'esistenza di una funzione \(\displaystyle f:X\to X\) iniettiva che non sia suriettiva si definisce infinito secondo Dedekind.[/nota].
Quindi che "cavolo è" un insieme infinito secondo Cantor?
ma un insieme \(\displaystyle X\) che ammette l'esistenza di una funzione \(\displaystyle f:X\to X\) suriettiva che non sia iniettiva è un insieme dualmente infinito secondo Dedekind!
Secondo la teoria assiomatica ZF, questi non sono sempre insiemi infiniti secondo Dedekind[nota]Un insieme \(\displaystyle X\) che ammette l'esistenza di una funzione \(\displaystyle f:X\to X\) iniettiva che non sia suriettiva si definisce infinito secondo Dedekind.[/nota].
Quindi che "cavolo è" un insieme infinito secondo Cantor?
"j18eos":
Quindi che "cavolo è" un insieme infinito secondo Cantor?
Provo a fare il quadretto che mi sembra di ricostruire delle questioni di definizione di insiemi infiniti in questo thread. Poi potete anche lanciare pomodori (mi piacciono i pomodori
).Secondo me, semplicemente, capita, ho notato in altre occasioni, che si attribuiscano a Cantor delle cose che Cantor non ha fatto manco per niente.
maxfed definisce un insieme infinito secondo Cantor nel modo seguente:
"maxfed":
[...] ricordiamo che un insieme è infinito nel senso di Cantor se esiste un'applicazione iniettiva, ma non suriettiva, $ h:Xrarr X $.
che è la stessa cosa che scrive j18eos chiamandola 'insieme infinito secondo Dedekind', e pure io questa definizione la conoscevo come definizione di Dedekind, non di Cantor:
"j18eos":
Un insieme \( \displaystyle X \) che ammette l'esistenza di una funzione \( \displaystyle f:X\to X \) iniettiva che non sia suriettiva si definisce infinito secondo Dedekind.
Che è equivalente (anche se secondo me molto più brutta, ma de gustibus) all'altra definizione che conoscevo, di insieme infinito secondo Dedekind, ossia:
'Un insieme $A$ è Dedekind-infinito se qualche sottoinsieme proprio $B$ di $A$ è equipollente[nota]o 'equipotente' o il termine che vi pare, scrivo 'equipollente' perché il libro di Moore citato sotto che ho sottomano dice così[/nota] a $A$; altrimenti $A$ è 'Dedekind finito'.
Un libro che ho dice che Cantor l'aveva introdotta come proprietà, ma non aveva dato una definizione di insieme infinito e finito. Cito:
"In 1882 Cantor still did not believe that a simple definition of finite set was necessary or even possible. Therefore he was surprised when Dedekind communicated his own definition of finite set [quella di sopra, nota mia], the first adequate definition of finite set that did not presuppose the natural numbers". [nota]G.H. Moore, Zermelo' Axiom of Choice. Its origins, Development and Influence, p. 24.[/nota]
La definizione di insieme dualmente infinito secondo Dedekind non l'avevo mai sentita (e non ne sentivo la mancanza
, a che serve? )j18eos dice che nella teoria assiomatica ZF, non sempre quelli dualmente infiniti sono insiemi infiniti secondo Dedekind.
In effetti perché siano equivalenti c'è bisogno dell'assioma della scelta, quindi non ZF senza assioma.
Nella voce di Wikipedia citata da j18eos c'è l'implicazione:
"ZF proves the following implications: Dedekind-infinite ⇒ dually Dedekind-infinite ⇒ weakly Dedekind-infinite ⇒ infinite."
(non so che sia weakly Dedekind infinite).
Per insieme 'infinito' si intende la definizione tramite i numeri naturali:
'Un insieme non vuoto $A$ è finito se per qualche intero positivo $n$ è equipollente a ${1, 2, ....,n}$; altrimenti, $A$ è infinito.'
Però, se si aggiunge l'Assioma della scelta, si ha il risultato dell'equivalenza tra il primo e l'ultimo termine del'implicazione, cioè l'equivalenza tra insieme infinito e Dedekind infinito, quindi il cerchio si chiude[nota]Una dimostrazione la ho in Munkres, Topology[/nota]. E' un degli esempi storici di uso dell'Assioma della scelta numerabile.
Quindi Cantor non aveva dato nessuna definizione di insieme infinito perchè pensava fosse impossibile? Interessante.
Guarda otta96, così dice questo libro che ho citato, Moore, è un libro molto approfondito e anche famoso. Ma è tutto molto complicato, perché c'è una grande quantità di lavori in quel periodo e c'è anche tutta la corrispondenza Cantor-Dedekind da analizzare. Con la difficoltà che il linguaggio matematico non è uguale a quello attuale, e con l'intrico di capire chi ha detto prima cosa, e quindi è davvero complicato.
Questo libro è molto approfondito, io ne ho letto una metà, ma spesso è difficile da seguire, anche per il motivo che ho detto.
Comunque mi pare di avere letto proprio lì, o in un altro libro, non mi vorrei sbagliare, che capita che risultati di insiemistica siano attribuiti a Cantor, ma non sono suoi.
Questo libro è molto approfondito, io ne ho letto una metà, ma spesso è difficile da seguire, anche per il motivo che ho detto.
Comunque mi pare di avere letto proprio lì, o in un altro libro, non mi vorrei sbagliare, che capita che risultati di insiemistica siano attribuiti a Cantor, ma non sono suoi.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo