Exercicis de conjunts, aplicacions i relacions

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

$|\mathcal{P}(A)| = 2^{0} = 1$

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^{2} = 4$

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 $4$, que és una resposta diferent.

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

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

$3\cdot2\cdots2 = 6$

Comparació. Aplicacions totals n'hi ha $9$, 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| = 10 + 8 - 3 = 15$

En sumar $10$ 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 ($10$) i la suma ($18$). 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.

Les propietats que cal comprovar.

• Reflexiva: tot element es relaciona amb ell mateix.
• Simètrica: si $x$ es relaciona amb $y$, llavors $y$ amb $x$.
• Antisimètrica: si es relacionen en tots dos sentits, són iguals.
• Transitiva: es poden encadenar.

Per a «$x = y$ sobre els enters», la resposta és Equivalència i ordre parcial alhora: compleix les quatre propietats; això només ho pot fer la igualtat.

El detall que separa els dos tipus. Simetria i antisimetria són gairebé incompatibles: una relació que compleixi totes dues només pot relacionar cada element amb ell mateix, que és exactament la igualtat. Per això cap relació interessant no és les dues coses.

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

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

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^{2} = 9$

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 $8$, que és una resposta diferent.

De pas: injectives n'hi ha $3\cdot2\cdots$, és a dir $6$, 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\cdots3 = 12$

Comparació. Aplicacions totals n'hi ha $16$, 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| = 10 + 8 - 5 = 13$

En sumar $10$ 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 ($10$) i la suma ($18$). 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.

Les propietats que cal comprovar.

• Reflexiva: tot element es relaciona amb ell mateix.
• Simètrica: si $x$ es relaciona amb $y$, llavors $y$ amb $x$.
• Antisimètrica: si es relacionen en tots dos sentits, són iguals.
• Transitiva: es poden encadenar.

Per a «$x \leq y$ sobre els enters», la resposta és Ordre parcial (de fet total): és reflexiva, antisimètrica i transitiva, però no és simètrica.

El detall que separa els dos tipus. Simetria i antisimetria són gairebé incompatibles: una relació que compleixi totes dues només pot relacionar cada element amb ell mateix, que és exactament la igualtat. Per això cap relació interessant no és les dues coses.