Tue-27-08-2024 09:06 status: tags: Cardinalidad

---

Cardinalidad entre conjuntos

$Def:$

$$\text{$A,B$ conjuntos. Decimos que tienen el mismo cardinal si $\exists\:f:A\to B$ biyectiva.}$$

$Not:$ $A\sim B$ ó $\#A=\#B$

---

Ejercicios

• $\mathbb{N}\sim \mathbb{Z}$: Sea $f:\mathbb{N}\sim \mathbb{Z}$

$$f(n)=\begin{cases} k & n=2k \\ -k & n=2k+1 \end{cases}$$

Demostrar la biyectividad.

---

• $\mathbb{N}\sim \mathbb{Q}^{+}=Q\cap(0,+\infty)$ Tengo que enumerar a todos los racionales positivos $1\quad 2\quad 3\quad 4\dots$ $\frac{1}{2}\quad \frac{2}{2}\quad \frac{3}{2}\dots$ $\frac{1}{3}\quad \frac{2}{3}\dots$ Construyo la función$f$ diagonalmente:

$$f:\mathbb{N}\to \mathbb{Q}: f(1)=1,f(2)=2,f(3)=\frac{1}{2},f(4)=3\dots$$

---

$Prop:$ $\sim$ es una relación de equivalencia en el "conjunto de todos los conjuntos": Es decir que reflexiva, simétrica, y transitiva.

$Dem:$

• Transitividad: $f:A\to B$ y $g:B\to C$ biyectivas $\implies gof:A\to C$ biyectiva

---

$Not:$

$$Y^{X}=\{ f\:|\: f:X\to Y \}$$

---

$Lema:$ Supongamos que $A\sim C,B\sim D$

1. $A\times B\sim C\times D$
2. funciones de $A$ a $B:B^{A}\sim D^{C}$
3. Si $A\cap B=C\cap D=\emptyset \implies AUB\sim CUD$

dem. 3) Tomo $f:A\to C,g:B\to D$ biyecciones Defino $h:AUB\to CUD$

$$h(x)= \begin{cases} f(x)& x \in A\\ \\ g(x)& x \in B \end{cases}$$

Esta bien definida:

$$A\cap B=\emptyset \text{ es biyectiva}$$

---

• $\mathbb{N}\sim \mathbb{Q}$ Basta ver que $\mathbb{Z}\sim \mathbb{Q}$ (Pues $\mathbb{N}\sim \mathbb{Z}$) Basta ver que $\mathbb{Z}-\{ 0 \}\sim \mathbb{Q}-\{ 0 \}$ Basta ver que $\mathbb{N}\sim \mathbb{Q}^{+},-\mathbb{N}\sim \mathbb{Q}^{-}$ La primera está demostrada. Veamos la tercera

defino $g:-\mathbb{N}\to \mathbb{Q}^{-}$

$$g(k)=-f(-k)$$

con $f:\mathbb{N}\to \mathbb{Q}^{+}$

---

$Notación:$

$$n \in \mathbb{N},\underline{n}=\{ 1,\dots,n \},\underline{0}=\emptyset$$

---

$def:$ Sea $A$ un conjunto.

1. $A$ es finito si $\exists n \in \mathbb{N}_{0}$ con $A\sim \underline{n}$, denotamos $\#A=n$
2. $A$ es numerable si $A\sim \mathbb{N}$, denotamos $k\#A=\aleph_{0}$
3. $A$ es contable si es finito o numerable
4. $A$ es infinito si no es finito

---

$Prop$

$$\begin{array}{l} \text{$A\subset B,B$ finito.}\\ \text{Entonces $A$ es finito y $\#A< \#B$} \end{array}$$

$Dem:$ Por inducción en $\#B$

• $\#B=0$, joya. $\not\exists A$
• $\#B=1,A=\{ \},\#A=0\implies\#A<\#B$
• $k\implies k+1:$, sea $f:B\to \underline{k+1}$ biyección Sea $b_{0}=f^{-1}(k+1)$ Tengo dos casos para definir $A$:

1. $A=B\setminus\{b_{0} \}$ Aca no necesito la hipótesis inductiva, y se cumple la biyección. Luego $f|_{A}:A\to \underline{k}$ es biyección. Es decir la aplicación de $f$ sobre el conjunto $A$.
2. Si $A\neq B\setminus\{ b_{0} \}=B´$ $A´=A\setminus\{ b_{0} \}$ Así, $A'\subset B'$, $f|_{B'}:B' \to \underline{k}$ es biyección. Por HI, $\exists g:A' \to \underline{l}$ biyección. y como $l<k.$ Defino

$$G:A\to \underline{l+1},G(a)=\begin{cases} g(a) & a\in A' \\ \\ l+1 & a=b_{0} \end{cases}$$

$A$ resulta ser finito pues encontramos biyección y $\#A=l+1<\#B=k+1$ $Corolario:$

$$\text{$B$ finito $\implies \not\exists A\subset B$ con $A\sim B$}$$

En particular, $\mathbb{Z}$ es infinito. Luego, $\mathbb{N}$ lo es.

---

$Prop:$

$$\text{$A\subseteq B, B$ numerable. Si $A$ es infinito, es numerable.}$$

$Dem:$ Idea: A tiene primer elemento por principio. y vamos a querer enumerar los elementos de $A$. Supongo sin perdida de generalidad, $B=\mathbb{N}$(Como ejercicio ver porque elegí $\mathbb{N}$) Defino $f:\mathbb{N}\to A$ recursivamente.

• $f(1)=min(A)$
• $f(n+1)=min\{ A\setminus \{ f(1),\dots,f(n) \} \}, \{ f(1),\dots,f(n) \}\neq \emptyset$ pues $A$ infinito

Esto implica que $f(n+1)\neq f(k)\quad\forall k\leq n$

Como ejercicio, mostrar que $f$ es biyección

Orden entre conjuntos

$Def$

$$\text{$A,B$ conjuntos. Decimos que $\#A\leq\#B$ si $\exists f:a\to B$ inyectiva.}$$

Ejemplos:

1. Si $A\subseteq B,\#A\leq\#B$, tengo $f:A\to B\:|f(x)=x$ inyectiva.
2. $\#\mathbb{Q}\leq\#\mathbb{N}$, anteriormente vimos que existe biyección. Luego, existe inyección $f:\mathbb{Q}\to \mathbb{N}$.
3. En general, $\#A=\#B\implies\#A\leq\#B \land\#B\leq\#A$

---

$Prop:$

$$\text{$\#A\leq\#B\iff \exists g:B\to A$ sobreyectiva}$$

$Dem:$ $\Rightarrow)$ Sea $f:A\to B$ inyectiva. Y tomo $a_{0}\in A$ auxiliar. Defino

$$g(b)=\begin{cases} a & b=f(a) \\ a_{0} & cc \end{cases}$$

$g$ está bien definida pues $f$ es inyectiva Así, $gof=id_{A}$. Ver además que si $gof$ es sobreyectiva entones $g$ también es sobreyectiva.

$\Leftarrow)$ Sea $a\in A$. $\exists b\in B$ con $a=g(b)$. Y defino $f(a)=b$. Acá uso el axioma de elección. (Para cada elemento de A un b). Así, $gof=id_{A}$. Como $gof$ es inyectiva, entonces $f$ es inyectiva.

---

$Prop:$

$$\text{$A$ infinito $\implies \aleph_{0}\leq\#A$}$$

$Dem:$ Defino recursivamente:

• $f(1)$ un elemento cualquiera de $A$
• $f(n+1)$ un elemento cualquiera de $A\setminus \{ f(1),\dots,f(n) \}\neq \emptyset$ pues $A$ infinito Así, $f$ es inyectiva pues $f(n+1)\neq f(k)\quad\forall k\leq n$

---

$Prop:$

$$\text{$\#A\leq\#B$ y $\#B\leq\#C\implies \#A\leq\#C$}$$

Composición de inyectivas da inyectiva.

---

Teorema

Citas y Comentarios