Re: Costruzione di biezione e classi di equivalenza

Messaggioda killing_buddha » 17/07/2018, 09:44

cptpackage ha scritto:Ma non si può metterli in una struttura binomiale? Tipo \( \begin{pmatrix} a \\ b \end{pmatrix} = \frac{a!}{b!(a-b)!} \) $\forall a \in R, b \in R-\{ 0 \} $ ? Sarebbe valida come risposta?

Cos'è $a!$ se $a\in RR$? Perché rimuovi lo zero dal dominio di "ciò che sta sotto il binomiale"1?

Note

  1. hanno un nome? Binomiando e binomiore?
- "Everything in Mathematics that can be categorized, is trivial" (P. J. Freyd), which should be understood as: "category theory is good ideas rather than complicated techniques".
- "I always disliked Analysis" (P. J. Freyd)
Avatar utente
killing_buddha
Cannot live without
Cannot live without
 
Messaggio: 2665 di 5766
Iscritto il: 03/05/2008, 17:33

Re: Costruzione di biezione e classi di equivalenza

Messaggioda gugo82 » 18/07/2018, 11:37

cptpackage ha scritto:Ma non si può metterli in una struttura binomiale? Tipo \( \begin{pmatrix} a \\ b \end{pmatrix} = \frac{a!}{b!(a-b)!} \) $\forall a \in R, b \in R-\{ 0 \} $ ? Sarebbe valida come risposta?

Le formule da usare dipendono da cosa devi fare.
Ad esempio, il coefficiente binomiale serve per contare il numero di sottoinsiemi con $b$ elementi distinti scelti tra $a$ elementi disponibili (queste sono quelle che in Calcolo Combinatorio si chiamano combinazioni semplici).

In questo problema nessuno ti sta chiedendo di contare sottoinsiemi, quindi tirare in ballo un coefficiente binomiale (senza una strategia) potrebbe anche non servirti a nulla e/o complicarti la vita.

Quello che il problema ti chiede è di ragionare sulle cardinalità dei sottoinsiemi di un insieme con $4$ elementi. In particolare, si tratta di stabilire se una relazione definita in base alla cardinalità è o non è un’equivalenza.
La strategia che mi viene in mente (implementata nel mio post precedente) è questa:

Testo nascosto, fai click qui per vederlo
  • innanzitutto, è bene farmi un’idea di quali sono i sottoinsiemi che sono in relazione tra loro;
    1. i possibili sottoinsiemi sono “tanti” ($2^4=16$) ed io sono troppo pigro per scriverli tutti;
    2. a me importa solo della cardinalità, è inutile scrivere o contare tutti i vari sottoinsiemi, piuttosto mi serve sapere quanti elementi hanno;
    3. in un insieme con $4$ elementi si possono formare solo sottoinsiemi con $0,1,2,3,4$ elementi, per stabilire quali sottoinsiemi sono in relazione basta che studio come funziona la \(\equiv \mod 3\) limitatamente ai numeri $0,1,2,3,4$;
    4. chiaramente \(0\equiv 0\equiv 3\equiv 3, 1\equiv 1\equiv 4 \equiv 4, 2\equiv 2\mod 3\), e ciò significa che la relazione $R$ definita nell'esercizio mette in relazione il vuoto con se stesso e con tutti i sottoinsiemi di tre elementi, che sono anche in relazione tra loro, tutti i singleton in relazione tra loro e con l’insieme ambiente, che è in relazione con se stesso, e tutti i sottoinsiemi con due elementi tra loro;
  • ragionando in questo modo, mi accorgo che ho determinato una “suddivisione” in $\mathcal{P}(S)$ in classi che non hanno elementi in comune, poiché infatti posto:
    \[
    \begin{split}
    X_0 &= \Big\{ T\subseteq S:\ \# T = 0 \text{ opp. } 3 \Big\} \\
    &= \Big\{ T\subseteq S:\ \# T \equiv 0 \mod 3 \Big\} \\
    X_1 &= \Big\{ T\subseteq S:\ \# T = 1 \text{ opp. } 4 \Big\} \\
    &= \Big\{ T\subseteq S:\ \# T \equiv 1 \mod 3 \Big\} \\
    X_0 &= \Big\{ T\subseteq S:\ \# T = 2 \Big\} \\
    &= \Big\{ T\subseteq S:\ \# T \equiv 2 \mod 3 \Big\}
    \end{split}
    \]
    risulta \( X_i\cap X_j = \varnothing\) per $i!=j$ e $X_0 uu X_1 uu X_2 = \mathcal{P}(S)$;

  • ricordo che una “suddivisione” come quella determinata in precedenza si chiama partizione di $\mathcal{P}(S)$ è che c'è un teorema molto bello che lega partizioni di un insieme con le relazioni di equivalenza; quindi sono quasi a posto, perché la mia $R$ individua un partizione;

  • vado a verificare che effettivamente tutto funzioni, cioè che $R$ sia di equivalenza e ciò posso farlo in più modi:
    1. mi vado a fare tutti i casi possibili, ma come detto sopra sono troppo pigro per farlo;
    2. mi faccio un disegno, cosa che preferisco: in ogni classe $X_0, X_1,X_2$, che sono disgiunte, la $R$ deve essere un’equivalenza (cioè riflessiva, simmetrica e transitiva) e posso verificarlo “a mano” facendo un grafo orientato. Ad esempio per la classe $X_2$ (dei sottoinsiemi con due elementi) la situazione è quella descritta dal grafo orientato in figura:

      Immagine

      che è pieno, dunque $R$ è di equivalenza abbondantemente.

Come vedi, i coefficienti binomiali non mi sono serviti a nulla...
Ma io non sono te: tu probabilmente hai attaccato il problema diversamente ed hai giudicato che ti servisse contare quanti sottoinsiemi di $k$ elementi potevi creare.
Il che porta alla domanda: come avevi pensato di risolvere il problema?

Tieni, per le prossime volte, presente che (in generale) se non hai un’idea precisa di come risolvere il problema è inutile tentare di “indovinare” una formula.
La scelta delle formule e delle rappresentazioni grafiche sta a valle di un ragionamento complessivo sul problema.


@k_b: Di solito $a$ e $b$ si chiamano primo e secondo indice del coefficiente binomiale \(\binom{a}{b}\)... Però “binomiando” ha il suo perché come nome. :-D
Sono sempre stato, e mi ritengo ancora un dilettante. Cioè una persona che si diletta, che cerca sempre di provare piacere e di regalare il piacere agli altri, che scopre ogni volta quello che fa come se fosse la prima volta. (Freak Antoni)
Avatar utente
gugo82
Cannot live without
Cannot live without
 
Messaggio: 19191 di 44916
Iscritto il: 12/10/2007, 23:58
Località: Napoli

Precedente

Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite