OliForum Matematico

Non sapendo dove postare la domanda ho ritenuto questa sezione la più appropriata trattandosi di una questione teorica.
Ho cercato nel forum ma non ho trovato niente. Se c'era già qualcosa di simile (o la domanda è troppo banale) mi scuso, ma non sono ancora pratico né del forum né di matematica.

La questione è la seguente:

Se ho due insiemi A e B, di cui so che A è numerabile e non riesco a trovare una funzione biiettiva (o mi scoccio di scriverla), ma so che esiste una funzione suriettiva da A a B e un'altra sempre suriettiva da B ad A, posso affermare che A e B sono equipollenti?

Inoltre è errato dire che se una funzione da A a B è suriettiva allora il numero di elementi di B al più è pari al numero di elementi di A? (cioé, so che è errato perché stiamo parlando di insiemi non necessariamente fini, anzi mi interessa proprio su quelli finiti, però moralmente posso affermare che è come se fosse così?)


Mi scuso ancora ma non ho trovato nulla nella teoria gobbiniana che mi autorizzasse esplicitamente a fare una cosa del genere.



La questione è nata per una dimostrazione della numerabilità di Q.
Io ho proceduto così: ad ogni $ q \in \mathbb{Q} $ scritto nella forma $ \pm m/n $(ridotta ai minimi termini) con $ m \in \mathbb{N} $ e $ n \in \mathbb{N}_0 $ associo $ m $ se $ q \in \mathbb{N} $ e $ m+n $ altrimenti. Questa è una funzione suriettiva da Q a N.
Per trovare una funzione da N a Q faccio la solita matrice infinita di Cantor e la percorro a zigzag secondo le diagonali.
Ora Cantor prevede (mi pare) di eliminare le frazioni uguali. Io invece vorrei affermare che questo sistema mi produce una funzione da N a Q suriettiva. Poiché ho entrambi i versi Q e N sono equipollenti.
Va bene come dimostrazione?

C'è un importante teorema (attribuito a Cantor-Schroeder-Bernstein), il quale afferma che, dati due insiemi $ A $ e $ B $, se esiste una funzione iniettiva $ f: A \rightarrow B $ e un'altra funzione iniettiva $ g: B \rightarrow A $, allora $ A $ e $ B $ sono equipotenti.

Però... mi sembra proprio che tutto torni anche con le funzioni surgettive! Anzi... direi che è un buon esercizio controllare che, se tutto va bene con le funzioni iniettive allora va bene anche con quelle surgettive, e viceversa.

luvemil ha scritto:Se ho due insiemi A e B, di cui so che A è numerabile e non riesco a trovare una funzione biiettiva (o mi scoccio di scriverla), ma so che esiste una funzione suriettiva da A a B e un'altra sempre suriettiva da B ad A, posso affermare che A e B sono equipollenti?

Puoi usare l'assioma della scelta? Conosci il teorema di Cantor-Bernstein?
Se sì, la risposta è molto semplice e puoi trovarla da solo...
Comunque si dice "equipotenti", e non "equipollenti". L'equipollenza è un'altra cosa.

luvemil ha scritto:Inoltre è errato dire che se una funzione da A a B è suriettiva allora il numero di elementi di B al più è pari al numero di elementi di A? (cioé, so che è errato perché stiamo parlando di insiemi non necessariamente fini, anzi mi interessa proprio su quelli finiti, però moralmente posso affermare che è come se fosse così?)

Non si capisce una mazza. Ti interessa per quelli FINITI o per quelli INFINITI? Per quelli FINITI è ovvio che sia come dici, e lo dimostri per induzione, ad esempio. Per quelli INFINITI non si capisce cosa voglia dire "moralmente".

luvemil ha scritto:Mi scuso ancora ma non ho trovato nulla nella teoria gobbiniana che mi autorizzasse esplicitamente a fare una cosa del genere.

Non credo esista una "teoria gobbiniana". Esistono delle schede olimpiche gobbiniane e dei video vari sul sito di Gobbino. Nessuna di queste cose (che io sappia) tratta la teoria degli insiemi. In particolare, la teoria degli insiemi non è argomento olimpico e non andrebbe in Glossario ma in MNE.

luvemil ha scritto:Va bene come dimostrazione?

Sì, posto che dimostri l'affare iniziale sulle 2 funzioni suriettive.

Grazie mille per le risposte e scusate per il casino. Con teoria gobbiniana mi riferisco esattamente alle schede olimpiche e ai video tutorial.

L'assioma della scelta lo conosco poco e non so come usarlo, inoltre mi servirebbe di utilizzare concetti elementari o quasi, trattandosi di una dimostrazione che sto sviluppando per la tesina della maturità.

Pensavo di utilizzare il lemma:
"The cardinality of the domain of a surjective function is greater than or equal to the cardinality of its codomain"
che vedo presente su wikipedia sia in italiano che in inglese, e che mi sembra abbastanza verisimile.

Una dimostrazione del lemma potrebbe essere:
Una funzione $ F:A\to B $ è suriettiva quando $ \forall b\in B: \exists a \in A :F(a)=b $, quindi esiste un sottoinsieme $ S $ di $ A $ per cui $ F:S\to B $ è biiettiva (forse è in questa affermazione che c'entra l'assioma della scelta), quindi $ |B|=|S|\leq |A| $

Se esiste una funzione suriettiva nell'altro verso vale la stessa cosa, e quindi $ |A|=|B| $.

Ovviamente tutto ciò vale solo se esiste tale sottoinsieme S.
Costruzione di $ S $: dati tutti i sottoinsiemi $ C $ di $ A $ tali che $ F:C\to B $ e $ \exists k: \forall c \in C: (F(c)=k)\wedge (\forall a\in A :F(a)=k\to a\in C) $, allora $ S $ è l'insieme che contiene uno e un solo elemento di ciascun insieme $ C $. Possibile per l'assioma della scelta. Serve l'assioma della scelta perché a priori non so se ogni $ C $ è finito o meno.

Posso scrivere una cosa del genere o c'è qualche errore?

Riguardo la parte di cui non si capisce niente: mi domandavo se è corretto dire che se $ F:A\to B $ è suriettiva allora B ha al più tanti elementi quanti ne ha A, anche nel caso di A e B infiniti.

EDIT: inserito "$ F:S\to B $" al posto di "esiste $ G:B\to S $"

PS: l'ho messo nel glossario perché mi sembrava una cosa abbastanza elementare.

Gli ordini tra cardinalità si definiscono con le funzioni iniettive, cioè $ $A\leq B\Leftrightarrow $ esiste $ $f:A\mapsto B $ iniettiva. Il teorema di Cantor Bernstein ti dice che se esistono le due iniettive, allora esiste anche una biettiva. Ora, trovare le iniettive tra $ $\mathbb{N} $ e $ $\mathbb{Q} $ è relativamente facile, almeno rispetto a quello che vorresti fare tu: trovare le due suriettive, usare l'assioma della scelta per dimostrare che esistono le iniettive opposte, e a questo punto usare Cantor Bernstein. Sostanzialmente, in questo caso ce l'hai già una funzione di scelta: è scegliere, tra tutte le frazioni che rappresentano lo stesso razionale, quella ridotta ai minimi termini. Per non usare la funzione di scelta data dalle frazioni ridotte ai minimi termini, fai un giro più lungo che passa dalle suriettive e dall'assioma scelta e che fa la stessa cosa, cioè ti trova una funzione di scelta. Non so se a te sembra più elegante così, ma io sceglierei la via standard.

Il punto è che non usare l'assioma della scelta in questo caso specifico è molto meglio, visto che si può tranquillamente farne a meno. Non è solo questione di estetica, è questione di usare un assioma in meno...
N.B. Cantor-Bernstein vale in ZF senza l'assioma della scelta.

luvemil ha scritto:Posso scrivere una cosa del genere o c'è qualche errore?

Io avevo capito che ti servisse per motivi "seri". In una tesina di maturità puoi scrivere qualunque oscenità e bestialità matematica, e nessuno te la verrà mai a contestare.
Entrando nel merito, il tuo sproloquio soffre di svariati errori d'impostazione e inconsistenze che potrai sistemare solo studiando teoria degli insiemi seguendo un percorso più ortodosso dello scartabellare wikipedia e chiedere nei forum. Quindi non intendo dirti di più, o rischio di fare più danni che altro.

Tibor Gallai ha scritto:Entrando nel merito, il tuo sproloquio soffre di svariati errori d'impostazione e inconsistenze che potrai sistemare solo studiando teoria degli insiemi seguendo un percorso più ortodosso dello scartabellare wikipedia e chiedere nei forum. Quindi non intendo dirti di più, o rischio di fare più danni che altro.

Grazie mille per la pazienza, mi rendo conto di dire molte stupidaggini ma è la prima volta che cerco di cimentarmi in qualcosa del genere ^^

Mi atterrò ad una dimostrazione classica, o al massimo toglierò dalla mia tutta una serie di cose presentandola quindi più come un modo di vedere la faccenda che una dimostrazione formalmente corretta.

Ancora grazie

il problema non e' dire stupidaggini, quanto crederci
Per quello Tibor preferisce lasciarti in uno stato in cui sai di non sapere. Il credere di aver compreso e' una brutta metastasi.

Infatti io non sono assolutamente convinto di quella roba XD

Comunque veramente grazie, ragazzi. Sembrerà strano ma anche questo è stato molto istruttivo per me.