Numerabilità e funzioni suriettive

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
luvemil
Messaggi: 4
Iscritto il: 18 giu 2010, 10:49

Numerabilità e funzioni suriettive

Messaggio da luvemil »

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?
Ultima modifica di luvemil il 18 giu 2010, 21:27, modificato 1 volta in totale.
Avatar utente
Ani-sama
Messaggi: 418
Iscritto il: 19 feb 2006, 21:38
Località: Piacenza
Contatta:

Messaggio da Ani-sama »

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. :wink:
...
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Re: Numerabilità è funzioni suriettive

Messaggio da Tibor Gallai »

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.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
luvemil
Messaggi: 4
Iscritto il: 18 giu 2010, 10:49

Messaggio da luvemil »

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.
Ultima modifica di luvemil il 18 giu 2010, 23:30, modificato 1 volta in totale.
Avatar utente
julio14
Messaggi: 1208
Iscritto il: 11 dic 2006, 18:52
Località: Berlino

Messaggio da julio14 »

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.
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

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.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
luvemil
Messaggi: 4
Iscritto il: 18 giu 2010, 10:49

Messaggio da luvemil »

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
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

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.
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
luvemil
Messaggi: 4
Iscritto il: 18 giu 2010, 10:49

Messaggio da luvemil »

Infatti io non sono assolutamente convinto di quella roba XD

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