Dimostrare che un insieme è finito

[Silente]

Forse è una cosa banale, ma evidentemente non per me.

Devo dimostrare che \(\displaystyle E_n=\begin{Bmatrix}
x \in \mathbb{N} |x\leq n
\end{Bmatrix} \) è un insieme finito.

In altre parole devo far vedere che non c'è modo di trovare una bijezione tra \(\displaystyle E_n \) e un qualunque suo sottoinsieme.
Ho tentato per induzione, ma alla fine si arriva a dover dimostrare che l'unione di due insiemi finiti è un insieme finito, di nuovo punto e accapo.

C'è ovviamente la soluzione brute-force di esplorare l'insieme di tutte le funzioni che è possibile definire tra \(\displaystyle E_n \) e (uno per uno) tutti i suoi sottinsiemi e vedere che nessuna di esse è biunivoca.
Cercavo qualcosa di più ragionevole.
Qualche input?

[anto_zoolander]

Ma essendo $E_n={x inNN:xleqn}$ allora $E_n={0,1,...,n}$

Ora siccome dovrebbe bastarti trovare una biezione $f$ tra $E_n$ e l'insieme $I_(n+1)={1,2,...,n+1}$

Io penso che la funzione $sigma(m)=m+1$ vada bene.

[Silente]

Questo dimostra che l'insieme E ed I hanno stessa cardinalità, punto.
Non che sono finiti.

[Bremen000]

@Ianero Dipende quale è la tua definizione di insieme finito.

[Silente]

Un insieme non infinito.
Un insieme infinito è un insieme che è equipollente con almeno un suo sottoinsieme proprio.

Ps: grazie a entrambi per la disponibilità.

[Bremen000]

Dunque il problema è appunto che ci sono in gioco due nozioni di infinitezza/finitezza:

1. Un insieme $X$ è detto Dedekind-finito se non può essere messo in corrispondenza biunivoca con un suo sottoinsieme proprio.
2. Un insieme $X$ è detto finito se è in biiezione con $I_n$ per qualche $n \in NN$, dove $I_n:=\{1, ... ,n \}$.

Quello che tu vuoi dimostrare è che un insieme Dedekind-finito è finito. Ciò equivale a dimostrare che un insieme infinito è Dedekind-infinito. Questa cosa si può fare solo con l'assioma della scelta e questa dovrebbe esserne una dimostrazione:
https://math.stackexchange.com/a/250132/402735

Detto ciò, non sono un logico e non mi intendo di queste cose (anzi, non so nemmeno se i matematici che si intendono di queste cose siano in effetti i logici) quindi prendi con le pinze tutto quello che ti ho detto.

[anto_zoolander]

Dai la seconda definizione è più bella

[Silente]

Quello che tu vuoi dimostrare è che un insieme Dedekind-finito è finito

No, il contrario, così se finito implica Dedekind-finito, allora la dimostrazione di anto_zoolander è già sufficiente così.

[Bremen000]

Si certo, mi sono confuso. Se cerchi finito implica dedekind finito dovresti trovare qualcosa. Più che altro si trova il se e solo se tra le due def di infinitezza, che è equivalente.

[Silente]

Ne ho tentata una da solo, vedi se ti sembra ci siano errori.

Lemma 1:
Se \(\displaystyle g:A\rightarrow B
\) è una funzione iniettiva, allora \(\displaystyle g(A'\subset A)=B'\subset B \).

Dimostrazione:

poichè \(\displaystyle A'\subset A \) allora per tutti gli \(\displaystyle a \) che appartengono ad \(\displaystyle A \) e non ad \(\displaystyle A' \), \(\displaystyle g(a) \in B \), ma \(\displaystyle g(a)\notin B' \) a causa dell'iniettività di \(\displaystyle g \).
Per cui \(\displaystyle B'\subset B \).

[fcd][FIDOCAD]
EV 55 35 120 155 0
EV 250 35 160 205 0
TY 70 35 4 3 0 0 0 * A
TY 245 175 4 3 0 0 0 * B
TY 220 155 4 3 0 0 0 * f(A)
TY 200 105 4 3 0 0 0 * f(A')
TY 80 80 4 3 0 0 0 * A'
TY 85 40 15 15 0 0 0 * .
TY 88 53 4 3 0 0 0 * a'
BE 95 60 120 45 165 30 190 50 0
FCJ 2 0 3 2 0 0
TY 185 30 15 15 0 0 0 * .
TY 195 46 4 3 0 0 0 * f(a')
LI 85 35 205 35 2
LI 90 155 205 155 2
EV 170 35 240 155 2
LI 90 135 210 100 11
LI 90 85 205 60 11
EV 80 85 100 135 11
EV 195 60 220 100 11[/fcd]

Dimostro ora che un insieme A che sia Dedekind-infinito è anche infinito nel senso che non è possibile trovare una mappa biunivoca tra esso e un \(\displaystyle E_n=\begin{Bmatrix}
1,2,...n
\end{Bmatrix} \) per qualsiasi \(\displaystyle n \).

Per assurdo sia A Dedekind-infinito e A finito, ovvero A in corrispondenza biunivoca con un suo sottoinsieme proprio (tramite \(\displaystyle f \)) e A in corrispondenza biunivoca con un \(\displaystyle E_n=\begin{Bmatrix}
1,2,...n
\end{Bmatrix} \), per qualche n naturale (tramite \(\displaystyle g \)).

[fcd][FIDOCAD]
EV 55 35 120 155 0
TY 70 35 4 3 0 0 0 * A
TY 200 105 4 3 0 0 0 * A'=f(A)
EV 170 35 240 155 0
TY 220 30 4 3 0 0 0 * A
LI 90 155 210 100 11
EV 195 60 220 100 11
LI 90 35 205 60 11[/fcd]

Chiamiamo il sottoinsieme proprio di \(\displaystyle A \), \(\displaystyle A' \). Allora dal Lemma 1 (e siccome \(\displaystyle g \) è biunivoca) \(\displaystyle A' \) è in corrispondenza biunivoca con un sottoinsieme proprio di \(\displaystyle E_n \).

Ora andiamo avanti per caso peggiore.
Nel peggiore dei casi (peggiore per me che voglio andare a trovare la contraddizione) il sottoinsieme proprio di \(\displaystyle E_n \) con cui \(\displaystyle A' \) è in corrispondenza biunivoca è l'insieme che si ottiene eliminando da \(\displaystyle E_n \) un solo elemento.
Sarà quindi \(\displaystyle E_{n-1}= {\begin{Bmatrix}
1,2,...n-1
\end{Bmatrix}} \) o un insieme che è in corrispondenza biunivoca con esso.
Infatti poichè l'insieme \(\displaystyle E_n \) è della forma \(\displaystyle {\begin{Bmatrix}
1,2,...n
\end{Bmatrix}} \) posso scegliere ogni volta un elemento diverso da eliminare (diverso da \(\displaystyle n-1 \)) e mettere tale insieme ottenuto in corrispondenza biunivoca con \(\displaystyle E_{n-1} \).

[fcd][FIDOCAD]
TY 90 50 4 3 0 0 0 * A
TY 155 50 4 3 0 0 0 * A'
TY 90 100 4 3 0 0 0 * En
BE 95 50 125 35 135 40 150 50 0
FCJ 2 0 3 2 0 0
TY 125 30 4 3 0 0 0 * f
BE 90 60 75 70 80 90 90 100 0
FCJ 2 0 3 2 0 0
TY 75 80 4 3 0 0 0 * g
BE 155 60 145 70 145 85 155 95 0
FCJ 2 0 3 2 0 0
TY 140 75 4 3 0 0 0 * g
TY 155 100 4 3 0 0 0 * En-1[/fcd]

A questo punto posso riapplicare \(\displaystyle f \) ad \(\displaystyle A' \), ottenendo \(\displaystyle A'' \).
\(\displaystyle A'' \) è un sottoinsieme proprio di \(\displaystyle A' \) per il Lemma 1.
Sempre per il Lemma 1 \(\displaystyle A'' \) è in corrispondenza biunivoca (tramite una restrizione di \(\displaystyle g \)) nel caso peggiore con \(\displaystyle E_{n-2} \).

[fcd][FIDOCAD]
TY 90 50 4 3 0 0 0 * A
TY 155 50 4 3 0 0 0 * A'
TY 90 100 4 3 0 0 0 * En
BE 95 50 125 35 135 40 150 50 0
FCJ 2 0 3 2 0 0
TY 125 30 4 3 0 0 0 * f
BE 90 60 75 70 80 90 90 100 0
FCJ 2 0 3 2 0 0
TY 75 80 4 3 0 0 0 * g
BE 155 60 145 70 145 85 155 95 0
FCJ 2 0 3 2 0 0
TY 140 75 4 3 0 0 0 * g
TY 155 100 4 3 0 0 0 * En-1
TY 220 50 4 3 0 0 0 * A''
BE 160 50 190 35 200 40 215 50 0
FCJ 2 0 3 2 0 0
BE 220 60 210 70 210 85 220 95 0
FCJ 2 0 3 2 0 0
TY 205 75 4 3 0 0 0 * g
TY 220 100 4 3 0 0 0 * En-2[/fcd]

Posso ripetere questo discorso nel caso peggiore n volte arrivando a dire che \(\displaystyle A^{n} \), che è in corrispondenza biunivoca con \(\displaystyle A \) (tramite \(\displaystyle f \)), è anche in corrispondenza biunivoca con \(\displaystyle \phi \) (tramite \(\displaystyle g \)).

Assurdo.

Quindi un insieme Dedekind-infinito è anche infinito nel senso che non è possibile trovare una mappa biunivoca tra esso e un \(\displaystyle E_n \) per qualsiasi \(\displaystyle n \).

Quindi un insieme finito è anche Dedekind-finito.

Quindi abbiamo finito

Ti pare corretta?

PS: inoltre non mi sembra di aver usato l'assioma di scelta da nessuna parte.

[anto_zoolander]

Ho letto non mi ricordo dove, ma wiki lo espone anche, che per dimostrare l'equivalenza tra le due asserzioni bisogna assumere l'assioma della scelta.

Non avevo letto che lo avesse già detto @Bremen000 quindi lo metto come spoiler.

[vict85]

"Bremen000":Si certo, mi sono confuso. Se cerchi finito implica dedekind finito dovresti trovare qualcosa. Più che altro si trova il se e solo se tra le due def di infinitezza, che è equivalente.

Ciò che dici è falso. Dire che finito implica Dedekind finito non vuol dire che ogni insieme Dedekind finito sia finito. Pertanto non stai dimostrando l'equivalenza delle due definizioni di insieme infinito.

Per la dimostrazione richiesta non serve alcun assioma della scelta, si può fare per induzione su \(n\). Infatti basta dimostrare che se si avesse\(E_n\) Dedekind infinito allora anche \(E_{n-1}\) lo sarebbe. Siccome l'insieme di un elemento non lo è, si conclude per assurdo.

[Bremen000]

@vict85 Probabilmente mi sono espresso male, volevo dire che (D-finito se e solo se finito ) implica (D-infinito se e solo se infinito). E che in rete si trovano dimostrazioni di questa ultima cosa.

[vict85]

"Bremen000":@vict85 Probabilmente mi sono espresso male, volevo dire che (D-finito se e solo se finito ) implica (D-infinito se e solo se infinito). E che in rete si trovano dimostrazioni di questa ultima cosa.

Ah ok. Sì questo è vero.

[Silente]

. Infatti basta dimostrare che se si avesseEn Dedekind infinito allora anche En−1 lo sarebbe. Siccome l'insieme di un elemento non lo è, si conclude per assurdo.

Uh, era molto più facile allora.

La mia proposta comunque contiene errori?

[vict85]

Ho letto velocemente, va sicuramente tutto bene fino al reale inizio della dimostrazione, da

Ora andiamo avanti per caso peggiore.
Nel peggiore dei casi (peggiore per me che voglio andare a trovare la contraddizione) il sottoinsieme proprio di En con cui A′ è in corrispondenza biunivoca è l'insieme che si ottiene eliminando da En un solo elemento.

Mi sembra che faccia un po' acqua. Andare avanti per caso peggiore non è una dimostrazione valida, devi considerare tutti i casi. Al limite puoi escludere immediatamente i casi che fornirebbero immediatamente un assurdo.

In ogni caso, ti sei complicato la vita perché devi di fatto dimostrare che per ogni \(\displaystyle f\colon E_n\to E_n \) iniettivo implica suriettivo.

[Silente]

Come mai un ragionamento come quello non è accettabile come dimostrazione?
Poiché sto prendendo sottoinsiemi propri di En, vuol dire che ogni sottoinsieme proprio ha almeno un elemento in meno rispetto al precedente.
Se ha più di un elemento in meno, allora l'algoritmo che ho usato nel mio tentativo di dimostrazione si conclude prima, in meno di n passi. No?

Chiedo solo per capire bene, voglio capire perché matematicamente non è accettabile fare quello che ho fatto.

Grazie ancora.