Cardinalitat

En matemàtiques, la cardinalitat d'un conjunt és una mesura del "nombre d'elements del conjunt". Per exemple, el conjunt A = {2, 4, 6} conté 3 elements, i per tant A té una cardinalitat de 3. Hi ha dues aproximacions al concepte de cardinalitat: un que compara conjunts directament utilitzant bijeccions i injeccions, i un altre que utilitza nombres cardinals. La cardinalitat d'un conjunt s'anomena la seva mida, sempre que no hi hagi confusió amb altres idees de mida.

La cardinalitat d'un conjunt $A$ es representa habitualment per $|A|$, amb una barra vertical a cada costat; aquesta és la mateixa notació que per al valor absolut i el significat depèn del context. Alternativament, la cardinalitat d'un conjunt $A$ es pot simbolitzar per $n(A)$, ${\bar {\bar {A}}}$, $card(A)$ o $\#A$.

Comparació de conjunts

Mentre que la cardinalitat d'un conjunt finit és només el nombre dels seus elements, si es vol estendre la idea a conjunts infinits normalment es comença definint la idea de comparació entre conjunts arbitraris (possiblement infinits).

Una funció bijectiva de N a E. Tot i que E és un subconjunt propi de N, ambdós conjunts tenen la mateixa cardinalitat.

Definició 1: |A| = |B|

Dos conjunts A i B tenen la mateixa cardinalitat si existeix una bijecció de A cap a B, és a dir, una funció de A cap a B que és alhora injectiva i exhaustiva. Hom diu que aquests conjunts són equipotents o equipol·lents. Aquesta relació també es pot denotar com A ≈ B o A ~ B.

Per exemple, el conjunt E = {0, 2, 4, 6, ...} dels nombres parells no negatius té la mateixa cardinalitat que el conjunt N = {0, 1, 2, 3, ...} dels nombres naturals, ja que la funció f(n) = 2n és una bijecció de N a E.

Definició 2: |A| ≤ |B|

A té una cardinalitat inferior o igual a la cardinalitat de B si existeix una funció injectiva de A cap a B.

Definició 3: |A| < |B|

A té una cardinalitat estrictament menor que la cardinalitat de B si hi ha una funció injectiva, però cap funció bijectiva, de A cap a B.

Per exemple, el conjunt N de tots els nombres naturals té una cardinalitat estrictament menor que la cardinalitat del conjunt R de tots els nombres reals, ja que la funció inclusió i : N → R és injectiva, però es pot demostrar que no existeix cap funció bijectiva de N cap a R.

Vegeu també: Diagonalització de Cantor

Si |A| ≤ |B| i |B| ≤ |A| llavors |A| = |B| (teorema de Schröder-Bernstein). L'axioma de l'elecció és equivalent a la declaració de què |A| ≤ |B| o |B| ≤ |A| per a qualssevol A, B.

Nombres cardinals

Fins ara, s'ha definit la "cardinalitat" en termes de funcions. És a dir, la "cardinalitat" d'un conjunt s'ha definir com un objecte específic i inherent al conjunt. Tanmateix, es pot definir un tal concepte intrínsec de la manera següent.

La relació de tenir la mateixa cardinalitat s'anomena equipotència, i això és una relació d'equivalència en la classe de tots els conjunts. La classe d'equivalència d'un conjunt A per aquesta relació consisteix llavors de tots aquells conjunts que tenen la mateixa cardinalitat que A. Hi ha dues maneres per definir la "cardinalitat d'un conjunt":

1. La cardinalitat d'un conjunt A es defineix com la seva classe d'equivalència per equipotència.
2. Es designa un conjunt representatiu per a cada classe d'equivalència. L'elecció més habitual és l'ordinal inicial d'aquella classe. Això es pren normalment com la definició de nombre cardinal en teoria de conjunts axiomàtica.

Amb la hipòtesi de l'axioma de l'elecció, les cardinalitats dels conjunts infinits es denoten per

$\aleph _{0}<\aleph _{1}<\aleph _{2}<\ldots$

Per a cada ordinal $\alpha$, $\aleph _{\alpha +1}$ és el menor nombre cardinal que és major que $\aleph _{\alpha }$.

La cardinalitat dels nombres naturals se simbolitza com aleph zero ($\aleph _{0}$), mentre que la cardinalitat dels nombres reals es denota per "${\mathfrak {c}}$" (una "c" fraktur minúscula), i hom també s'hi refereix com la cardinalitat del continu. Cantor va demostrar, utilitzant l'argument de la diagonal, que ${\mathfrak {c}}>\aleph _{0}$. Es pot demostrar que ${\mathfrak {c}}=2^{\aleph _{0}}$, que és la cardinalitat del conjunt de tots els subconjunts dels nombres naturals. La hipòtesi del continu diu que $\aleph _{1}=2^{\aleph _{0}}$, és a dir, $2^{\aleph _{0}}$ és el menor nombre cardinal que és més gran que $\aleph _{0}$, la qual cosa vol dir que no hi ha cap conjunt amb cardinalitat situada entre la dels enters i la dels reals. La hipòtesi del continu és independent de ZFC, una axiomatització estàndard de la teoria de conjunts; això és, és impossible demostrar la hipòtesi del continu o la seva negació a partir de ZFC (sempre que ZFC sigui compatible).

Conjunts finits, numerables i no numerables

Si se suposa que l'axioma de l'elecció és cert, llavors també és certa la llei de tricotomia per a la cardinalitat. Això, es poden fer les definicions següents:

• Tot conjunt X amb una cardinalitat menor a la dels nombres naturals, o | X | < | N |, és un conjunt finit.
• Tot conjunt X amb la mateixa cardinalitat que la del conjunt dels nombres naturals, o | X | = | N | = ℵ₀, és un conjunt infinit numerable.
• Tot conjunt X amb una cardinalitat més gran que la dels nombres naturals, o | X | > | N |, per exemple | R | = ${\mathfrak {c}}$ > | N |, és un conjunt infinit no numerable.

Conjunts infinits

Cardinalitat del continu

Un del resultats més importants de Cantor va ser el que diu que la cardinalitat del continu (${\mathfrak {c}}$) és major que la cardinalitat dels nombres naturals ($\aleph _{0}$). és a dir, hi ha més nombres reals R que nombres naturals N. De fet, Cantor va demostrar que ${\mathfrak {c}}=2^{\aleph _{0}}=\beth _{1}$ satisfà:

$2^{\aleph _{0}}>\aleph _{0}.$

La hipòtesi del continu afirma que no existeix cap nombre cardinal entre la cardinalitat del reals i la cardinalitat dels nombres naturals, és a dir,

$2^{\aleph _{0}}=\aleph _{1}$

Tanmateix, aquesta hipòtesi no es pot demostrar ni refutar dins del marc de la teoria axiomàtica de conjunts ZFC, si ZFC és consistent.

Es pot utilitzar l'aritmètica cardinal no només per demostrar que nombre de punts de la recta real és igual al nombre de punts de qualsevol segment de recta, sinó que també és igual al nombre de punts d'un pla i, de fet, al de qualsevol espai de dimensió finita. Aquests resultats no són gens intuïtius, perquè impliquen que existeixen subconjunts propis i superconjunts propis d'un conjunt infinit S que tenen la mateixa grandària que S, encara que S conté elements que no pertanyen als seus subconjunts, i els superconjunts de S contenen elements que no pertanyen a S.

El primer d'aquests resultats es pot visualitzar si es considera, per exemple, la funció tangent, que proporciona una correspondència bijectiva entre l'interval (−½π, ½π) i R (vegeu també la paradoxa de Hilbert de l'hotel infinit).

El segon resultat fou demostrat per primer cop per Cantor l'any 1878, però va assolir més difusió l'any 1890, quan Giuseppe Peano va introduir les corbes que emplenen tot l'espai, que són línies corbes que es retorcen tant que poden ocupar la totalitat d'un quadrat, o d'un cub, o d'un hipercub, o d'un espai de dimensió finita. Aquestes corbes no són una demostració directa que una recta té el mateix nombre de punts que un espai de dimensió finita, però es poden utilitzar per construir-ne una demostració.

Cantor també va demostrar que existeixen conjunts amb una cardinalitat estrictament més gran que ${\mathfrak {c}}$ (vegeu el seu argument de la diagonal i el seu teorema). Per exemple:

• el conjunt de tots els subconjunts de R, és a dir, el conjunt de les parts de R, escrit P(R) o 2^R
• el conjunt R^R de totes les funcions de R en R

Tots dos tenen cardinalitat $2^{\mathfrak {c}}=\beth _{2}>{\mathfrak {c}}$.

Les igualtats cardinals ${\mathfrak {c}}^{2}={\mathfrak {c}}$, ${\mathfrak {c}}^{\aleph _{0}}={\mathfrak {c}}$ i ${\mathfrak {c}}^{\mathfrak {c}}=2^{\mathfrak {c}}$ es poden demostrar utilitzant aritmètica cardinal:

${\mathfrak {c}}^{2}=\left(2^{\aleph _{0}}\right)^{2}=2^{2\times {\aleph _{0}}}=2^{\aleph _{0}}={\mathfrak {c}},$

${\mathfrak {c}}^{\aleph _{0}}=\left(2^{\aleph _{0}}\right)^{\aleph _{0}}=2^{{\aleph _{0}}\times {\aleph _{0}}}=2^{\aleph _{0}}={\mathfrak {c}},$

${\mathfrak {c}}^{\mathfrak {c}}=\left(2^{\aleph _{0}}\right)^{\mathfrak {c}}=2^{{\mathfrak {c}}\times \aleph _{0}}=2^{\mathfrak {c}}.$

Exemples i propietats

• Si X = {a, b, c} i Y = {pomes, taronges, préssecs}, llavors | X | = | Y | perquè { (a, pomes), (b, taronges), (c, préssecs) } és una bijecció entre els conjunts X i Y. Tant la cardinalitat de X com la de Y és 3.
• Si | X | < | Y |, llavors existeix Z tal que | X | = | Z | i Z ⊆ Y.
• Si | X | ≤ | Y | i | Y | ≤ | X |, llavors | X | = | Y |. Això és cert fins i tot per a cardinals infinits, i es coneix com a teorema de Cantor-Bernstein-Schroeder.
• Vegeu Cardinalitat del continu#Conjunts amb la cardinalitat del continu

Unió i intersecció

Si A i B són conjunts disjunts, llavors

$\left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert B\right\vert .$

A partir d'aquí, es pot demostrar que, en general, les cardinalitats de les unions i interseccions compleixen la següent relació:

$\left\vert C\cup D\right\vert +\left\vert C\cap D\right\vert =\left\vert C\right\vert +\left\vert D\right\vert \,.$

Vegeu també

• Cardinalitat del continu
• Compte (càlcul)
• Conjunt numerable
• Nombre cardinal
• Nombre infinit