#3Cardinalidad

2025 - Teórica 3 - Cardinalidad

12 min de lectura

Thu-27-03-2025 18:20 profe: Natalia Accomazzo Scotti status: tags: Cardinalidad

Ejemplos:Ejemplos:
  1. N∼Z\mathbb{N}\sim \mathbb{Z}
f(n)={n2si n es par−(n−12)si n es imparf(n)=\begin{cases} \frac{n}{2} & \text{si $n$ es par}\\ -\left( \frac{n-1}{2} \right)&\text{si $n$ es impar} \end{cases}

f(n)f(n) es biyectiva. 3. N∼Q+\mathbb{N}\sim \mathbb{Q}_{+}

Prop. :{\color{Orange} \text{Prop. :} }

Sea A numerable, B≠∅ y B⊆A   ⟹  B es contable. \begin{array}{l} \text{Sea $A$ numerable, $B\neq \emptyset$ y $B\subseteq A$ $\implies B$ es contable. } \end{array}

Dem:{\color{Orange} \text{Dem:} } Como AA es numerable, Puedo dar un orden a los elementos de AA

A={a1,a2,a3,… }A=\{ a_{1},a_{2},a_{3},\dots \}

Sea f:N→A ∣ f(n)=anf:\mathbb{N}\to A\:|\:f(n)=a_{n} Como B⊆AB\subseteq A, quiero definir g(1)g(1) con g:N→Bg:\mathbb{N}\to B Defino g(1)=aj1g(1)=a_{j_{1}} donde j1=min{j:aj∈B}j_{1}=min\{ j:a_{j}\in B \} Si B={aj1}B=\{ a_{j_{1}} \} listo pues conjunto finito. Si no, B∖{aj1}≠∅B\setminus \{ a_{j_{1}} \}\neq \emptyset y repito el procedimiento, defino g(n)g(n) de manera inductiva.

j2=min{j>j1:aj∈B},g(2)=aj2j_{2}=min\{ j>j_{1}:a_{j}\in B \},g(2)=a_{j_{2}}

Si termina en nn pasos   ⟹  B\implies B es finito. Si BB es infinito debería probar gg biyectiva.

  • inyectividad: Porque ff es inyectiva, la lista de AA no tiene elementos repetidos.
  • Sobreyectividad: Si b∈B  ⟹  b∈A  ⟹  b=anb \in B\implies b \in A\implies b=a_{n} para algún número.   ⟹  \implies en a lo sumo nn pasos llego a cubrirlo.
□\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \square

Teorema :{\color{violet} \text{Teorema :} }

Sea A infinito. Entonces existe B⊆A numerable.\begin{array}{l} \text{Sea $A$ infinito. Entonces existe $B\subseteq A$ numerable.} \end{array}

Dem:{\color{violet} \text{Dem:} } Sea a1∈Aa_{1}\in A cualquiera. Como AA es infinito entonces A∖{a1}≠∅A\setminus \{ a_{1} \}\neq \emptyset Luego  ∃ a2∈A∖{a1}\:\exists\:a_{2}\in A\setminus \{ a_{1} \} Inductivamente, si elegí a1,…,ana_{1},\dots,a_{n}. Como A∖{a1,…,an}≠∅A\setminus \{ a_{1},\dots,a_{n} \}\neq \emptyset entonces  ∃ an+1∈A∖{a1,…,an}\:\exists\:a_{n+1}\in A\setminus \{ a_{1},\dots ,a_{n} \} Defino B={an:n∈N}B=\{ a_{n}:n\in \mathbb{N} \} f:N→B ∣ f(n)=anf:\mathbb{N}\to B\:|\:f(n)=a_{n}

Si #A≤#B\#A\leq\#B y #A=#X,#B=#Y  ⟹  #X≤#Y\#A=\#X,\#B=\#Y\implies\#X\leq\#Y

Si g:X→Ag:X\to A biyección, h:Y→Bh:Y\to B biyección y f:A→Bf:A\to B inyección. entonces h−1ofogh^{-1}ofog es inyectiva.

N×N es numerable.\text{$\mathbb{N}\times \mathbb{N}$ es numerable.}

Considero 2 inyecciones: f:N→N×N ∣ f(n)=(n,1)f:\mathbb{N}\to \mathbb{N}\times \mathbb{N}\:|\:f(n)=(n,1) es inyectiva. g:N×N→N ∣ g(n,m)=2n⋅3mg:\mathbb{N}\times \mathbb{N}\to \mathbb{N}\:|\:g(n,m)=2^n\cdot3^m es inyectiva por descomposición única en factores primos. Por CSBCSB entonces N∼N×N\mathbb{N}\sim \mathbb{N}\times \mathbb{N}

(An)n∈N( A_{n} )_{n \in \mathbb{N}} sucesión de conjuntos numerables   ⟹  ⋃An=A\implies \bigcup A_{n}=A es numerable.

  1. #N≤#A\#\mathbb{N}\leq\#A
  2. #A≤#N\#A\leq\#\mathbb{N}
  3. #N→⋃An\#\mathbb{N}\to \bigcup A_{n} Sé que  ∃ f:N→A1\:\exists\:f:\mathbb{N}\to A_{1} biyectiva Pienso f:N→Af:\mathbb{N}\to A inyectiva A1={a11,a12,a13,… }A_{1}=\{ a_{11},a_{12},a_{13},\dots \} A2={a21,a22,a23,… }A_{2}=\{ a_{21},a_{22},a_{23},\dots \}

a∈A  ⟹  a∈Ana \in A \implies a \in A_{n} para algún nn. Si está en más de un AnA_{n} elijo n=min{m:a∈Am}n=min\{ m:a \in A_{m} \} a∈An={an1,an2,an3,… }  ⟹  a=anja \in A_{n}=\{ a_{n1},a_{n2},a_{n_{3}},\dots \} \implies a=a_{n_{j}} Defino f:A→N×N ∣ f(a)=(n,j)f:A\to \mathbb{N}\times \mathbb{N}\:|\:f(a)=(n,j)

Demostración en limpio: la unión numerable de conjuntos numerables es numerable

Sea (An)n∈N(A_n)_{n \in \mathbb{N}} una sucesión de conjuntos numerables y sea

A=⋃n∈NAn.A = \bigcup_{n \in \mathbb{N}} A_n.

Queremos probar que AA es numerable.

1. Idea general

Cada AnA_n es numerable, por lo tanto existe una biyección

fn:N→An.f_n : \mathbb{N} \to A_n.

Podemos enumerar los elementos de cada conjunto como:

An={an1,an2,an3,… }.A_n = \{ a_{n1}, a_{n2}, a_{n3}, \dots \}.

Entonces todo elemento de AA aparece como algún anja_{n j}.

2. Eliminación de repeticiones

Si un elemento pertenece a varios AnA_n, elegimos el primero en que aparece:

∀a∈A,n(a)=min⁡{ m∈N:a∈Am }.\forall a \in A, \quad n(a) = \min\{\, m \in \mathbb{N} : a \in A_m \,\}.

Así garantizamos una sola representación a=an(a), j(a)a = a_{n(a),\,j(a)}.

3. Definición de una inyección hacia N×N\mathbb{N} \times \mathbb{N}

Definimos

f:A→N×N,f(a)=(n(a),j(a)).f : A \to \mathbb{N} \times \mathbb{N}, \qquad f(a) = (n(a), j(a)).

donde:

  • n(a)n(a) es el menor índice mm tal que a∈Ama \in A_m,
  • j(a)j(a) es la posición de aa dentro de la enumeración de An(a)A_{n(a)} (es decir, a=an(a), j(a)a = a_{n(a),\, j(a)}).

Demostración de que ff es inyectiva:

Sean a,b∈Aa, b \in A tales que f(a)=f(b)f(a) = f(b). Entonces:

(n(a),j(a))=(n(b),j(b)).(n(a), j(a)) = (n(b), j(b)).

Por igualdad de pares, se tiene n(a)=n(b)n(a) = n(b) y j(a)=j(b)j(a) = j(b).

  • Como n(a)=n(b)n(a) = n(b), ambos elementos pertenecen al mismo conjunto An(a)A_{n(a)}.
  • Como j(a)=j(b)j(a) = j(b), y en An(a)A_{n(a)} cada elemento ocupa una posición única jj, se sigue que a=ba = b.

Por lo tanto, ff es inyectiva.

4. Conclusión

Sabemos que N×N\mathbb{N} \times \mathbb{N} es numerable, y que AA se inyecta en él:

A↪N×N.A \hookrightarrow \mathbb{N} \times \mathbb{N}.

Por tanto:

#A≤#(N×N)=#N.\#A \leq \#(\mathbb{N} \times \mathbb{N}) = \#\mathbb{N}.

Además, si alguno de los AnA_n es infinito, entonces #N≤#A\#\mathbb{N} \leq \#A.
En cualquier caso, se cumple:

#A=#N.\#A = \#\mathbb{N}.

Conclusión:
La unión numerable de conjuntos numerables es numerable.

⋃n∈NAn es numerable.\boxed{\bigcup_{n \in \mathbb{N}} A_n \text{ es numerable.}}

Citas y Comentarios

Temas relacionados

Cardinalidad