Exercicis de conjunts, aplicacions i relacions

El raonament. Construir un subconjunt és prendre $12$ decisions independents, una per element: hi entra o no hi entra. Dues opcions cada vegada, i es multipliquen:

$|\mathcal{P}(A)| = 2^{12} = 4096$

Comprovació amb casos petits. Un conjunt buit té $1$ subconjunt (ell mateix). Un conjunt d'un element en té $2$. Un de dos elements en té $4$: el buit, els dos unitaris i el total.

Un avís. Els elements de $\mathcal{P}(A)$ són conjunts, no elements d'$A$. El conjunt buit i el mateix $A$ hi són sempre, i és fàcil oblidar-se'n en comptar a mà.

El raonament. Una aplicació assigna a cada element de sortida exactament una imatge, i les eleccions són independents:

$n^{m} = 2^{4} = 16$

Compte amb l'ordre dels exponents. La base és la mida del conjunt d'arribada (les opcions) i l'exponent és la del de sortida (les decisions). Intercanviar-los dona $16$, que és una resposta diferent.

De pas: injectives n'hi ha zero, perquè amb $4$ elements de sortida no pots anar a $2$ imatges diferents, i bijectives només si els dos conjunts tenen la mateixa mida.

El raonament. El primer element tria entre $4$ imatges; el segon, entre les $3$ que queden lliures; i així fins a acabar:

$4\cdot3\cdots1 = 24$

Comparació. Aplicacions totals n'hi ha $256$, o sigui que només una fracció són injectives. I si el conjunt de sortida fos més gran que el d'arribada, no n'hi hauria cap: aquest és el principi del colomar en la seva forma més bàsica.

Cas particular. Quan els dos conjunts tenen la mateixa mida, injectiva, exhaustiva i bijectiva són el mateix, i el recompte dona el factorial.

La fórmula i el seu perquè.

$|A\cup B| = |A| + |B| - |A\cap B| = 12 + 8 - 3 = 17$

En sumar $12$ i $8$, els $3$ elements comuns s'han comptat dues vegades, una en cada conjunt. Restar-los una vegada els deixa comptats exactament un cop.

Comprovacions de coherència. El resultat ha de quedar entre el més gran dels dos ($12$) i la suma ($20$). I la intersecció mai no pot superar el més petit dels dos conjunts.

Amb tres conjunts la fórmula segueix alternant signes: se sumen les tres mides, es resten les tres interseccions dos a dos i es torna a sumar la triple. Aquest és el principi d'inclusió i exclusió general.

El raonament. Construir un subconjunt és prendre $13$ decisions independents, una per element: hi entra o no hi entra. Dues opcions cada vegada, i es multipliquen:

$|\mathcal{P}(A)| = 2^{13} = 8192$

Comprovació amb casos petits. Un conjunt buit té $1$ subconjunt (ell mateix). Un conjunt d'un element en té $2$. Un de dos elements en té $4$: el buit, els dos unitaris i el total.

Un avís. Els elements de $\mathcal{P}(A)$ són conjunts, no elements d'$A$. El conjunt buit i el mateix $A$ hi són sempre, i és fàcil oblidar-se'n en comptar a mà.

El raonament. Una aplicació assigna a cada element de sortida exactament una imatge, i les eleccions són independents:

$n^{m} = 3^{4} = 81$

Compte amb l'ordre dels exponents. La base és la mida del conjunt d'arribada (les opcions) i l'exponent és la del de sortida (les decisions). Intercanviar-los dona $64$, que és una resposta diferent.

De pas: injectives n'hi ha zero, perquè amb $4$ elements de sortida no pots anar a $3$ imatges diferents, i bijectives només si els dos conjunts tenen la mateixa mida.

El raonament. El primer element tria entre $5$ imatges; el segon, entre les $4$ que queden lliures; i així fins a acabar:

$5\cdot4\cdots2 = 120$

Comparació. Aplicacions totals n'hi ha $625$, o sigui que només una fracció són injectives. I si el conjunt de sortida fos més gran que el d'arribada, no n'hi hauria cap: aquest és el principi del colomar en la seva forma més bàsica.

Cas particular. Quan els dos conjunts tenen la mateixa mida, injectiva, exhaustiva i bijectiva són el mateix, i el recompte dona el factorial.

La fórmula i el seu perquè.

$|A\cup B| = |A| + |B| - |A\cap B| = 12 + 8 - 5 = 15$

En sumar $12$ i $8$, els $5$ elements comuns s'han comptat dues vegades, una en cada conjunt. Restar-los una vegada els deixa comptats exactament un cop.

Comprovacions de coherència. El resultat ha de quedar entre el més gran dels dos ($12$) i la suma ($20$). I la intersecció mai no pot superar el més petit dels dos conjunts.

Amb tres conjunts la fórmula segueix alternant signes: se sumen les tres mides, es resten les tres interseccions dos a dos i es torna a sumar la triple. Aquest és el principi d'inclusió i exclusió general.

El raonament. Construir un subconjunt és prendre $14$ decisions independents, una per element: hi entra o no hi entra. Dues opcions cada vegada, i es multipliquen:

$|\mathcal{P}(A)| = 2^{14} = 16384$

Comprovació amb casos petits. Un conjunt buit té $1$ subconjunt (ell mateix). Un conjunt d'un element en té $2$. Un de dos elements en té $4$: el buit, els dos unitaris i el total.

Un avís. Els elements de $\mathcal{P}(A)$ són conjunts, no elements d'$A$. El conjunt buit i el mateix $A$ hi són sempre, i és fàcil oblidar-se'n en comptar a mà.

El raonament. Una aplicació assigna a cada element de sortida exactament una imatge, i les eleccions són independents:

$n^{m} = 4^{4} = 256$

Compte amb l'ordre dels exponents. La base és la mida del conjunt d'arribada (les opcions) i l'exponent és la del de sortida (les decisions). Intercanviar-los dona $256$, que és una resposta diferent.

De pas: injectives n'hi ha $4\cdot3\cdots$, és a dir $24$, i bijectives només si els dos conjunts tenen la mateixa mida.