Conjunts, aplicacions i relacions: imatges, equivalències i ordres parcials

Aquest tema és la infraestructura de tota la matemàtica moderna. Gairebé tot el que faràs després (espais vectorials, grups, quocients, congruències) consisteix a prendre un conjunt, posar-hi una relació i mirar què en surt. Val la pena fer-lo bé perquè els errors d'aquí es propaguen silenciosament a tot arreu.

Conjunts i el conjunt de parts

La inclusió es defineix per una implicació: $A\subseteq B$ vol dir que tot element d'$A$ és element de $B$. D'aquí surt el mètode estàndard per demostrar una igualtat de conjunts: provar les dues inclusions per separat, agafant un element arbitrari d'un costat i comprovant que és a l'altre.

Les operacions tradueixen directament els connectius lògics: la unió és la disjunció, la intersecció és la conjunció i el complement és la negació, sempre respecte d'un univers fixat. Per això les lleis de De Morgan dels conjunts són literalment les mateixes que les de la lògica.

El conjunt de parts $\mathcal{P}(A)$ és el conjunt de tots els subconjunts d'$A$. Si $A$ té $n$ elements,

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

perquè construir un subconjunt és decidir, per a cadascun dels $n$ elements, si hi entra o no: dues opcions independents cada vegada. Compte amb un detall que costa punts: els elements de $\mathcal{P}(A)$ són conjunts, no elements d'$A$. El conjunt buit i el mateix $A$ hi són sempre.

Aplicacions

Una aplicació assigna a cada element del conjunt de sortida una única imatge. És injectiva si elements diferents tenen imatges diferents, exhaustiva si tot element d'arribada és imatge d'algun, i bijectiva si compleix les dues. Només una bijecció té inversa bilateral.

L'antiimatge es comporta molt millor que la imatge: preserva unions, interseccions i complements relatius, totes les operacions. La imatge només preserva unions. Per a interseccions, en general només es té

$$f(C\cap D)\subseteq f(C)\cap f(D),$$

i la igualtat pot fallar. Amb $f(x)=x^{2}$, $C=\{-1\}$ i $D=\{1\}$: la intersecció dels conjunts és buida, de manera que el membre esquerre és buit, però les dues imatges valen $\{1\}$ i la seva intersecció és $\{1\}$. Amb $f$ injectiva la igualtat sí que val.

Relacions d'equivalència i particions

Una relació sobre un conjunt és, formalment, un subconjunt del producte cartesià. És d'equivalència si és reflexiva, simètrica i transitiva. La classe d'un element és el conjunt de tots els que hi estan relacionats.

El conjunt quocient és el conjunt de les classes. És important no confondre'l amb un subconjunt del conjunt original: els seus elements són classes, és a dir conjunts. I quan defineixes una operació sobre classes has de comprovar que està ben definida: canviar de representant no pot canviar el resultat. Aquesta comprovació no és un formalisme, és on realment es demostra que l'operació té sentit.

Ordres parcials

Un ordre parcial és reflexiu, antisimètric i transitiu. L'antisimetria vol dir que si dos elements es comparen en tots dos sentits, aleshores són iguals. No s'ha de confondre amb «no simètric»: són condicions diferents.

L'ordre és total si qualsevol parella es pot comparar. La inclusió entre subconjunts no ho és (dos conjunts poden no contenir-se mútuament), i la divisibilitat entre enters positius tampoc.

Exercici resolt: classes d'una equivalència als reals

Als reals, diem que $x$ i $y$ estan relacionats si la seva diferència és un enter. Descriu la classe d'$1/2$.

És d'equivalència. La diferència d'un número amb ell mateix és $0$, que és enter (reflexiva). Canviar el signe d'un enter dona un enter (simètrica). I la suma de dos enters és entera (transitiva).

La classe. Els elements relacionats amb $1/2$ són els que en difereixen per un enter:

$$[1/2] = \left\{\tfrac12 + k : k\in\mathbb{Z}\right\} = \left\{\ldots, -\tfrac32, -\tfrac12, \tfrac12, \tfrac32, \ldots\right\}.$$

Un sistema de representants és l'interval de $0$ a $1$ tancat per l'esquerra: cada real és equivalent a exactament un punt d'aquest interval, que és la seva part decimal. El conjunt quocient es pot identificar, doncs, amb aquest interval amb els extrems enganxats: és el cercle.

Exercici resolt: comptar aplicacions injectives

Quantes aplicacions injectives hi ha d'un conjunt de $3$ elements a un de $5$?

Per ser injectiva, els tres elements han d'anar a imatges diferents. Tries la imatge del primer entre $5$, la del segon entre les $4$ que queden, i la del tercer entre $3$:

$$5\cdot 4\cdot 3 = 60.$$

Comparació. Aplicacions totals n'hi ha $5^{3} = 125$, perquè cada element tria lliurement. Exhaustives n'hi ha zero: amb només tres elements de sortida no pots cobrir cinc d'arribada. I bijectives tampoc, pel mateix motiu.

La conclusió general és que entre conjunts finits només hi pot haver bijecció si tenen la mateixa mida, cosa que sembla òbvia però és precisament el que fa que «comptar» sigui un concepte ben definit.