#3

2C2025 T3 - Cardinalidad II

14 min de lectura

Tue-09-09-2025 09:25 profe: Pablo Turco status: tags:

 ∃ f:N→B\:\exists\:f:\mathbb{N}\to B biyectiva Sea M=f−1(A)M=f ^{-1}(A) Sea h:N→Ah:\mathbb{N}\to A de la siguiente forma

h(1)=f(minM)h(2)=f(min{M2})⋮h(n+1)=f(min{Mn})\begin{array}{c} h(1)=f(minM) \\ h(2)=f(min\{ M_{2} \}) \\ \vdots \\ h(n+1)=f(min\{ M_{n} \}) \end{array}

Sea M1=M∖min{M}M_{1}=M \setminus min\{ M \}, con M1≠∅M_{1}\neq \emptyset

hh está bien definida hh es inyectiva. Si n<mn<m Si h(n)=h(m)  ⟹  f−1(h(n))=f−1(h(m))h(n)=h(m)\implies f ^{-1}(h(n))=f ^{-1}(h(m))

  ⟹  min{Mn}=min{Mm}\implies min\{ M_{n} \}=min\{ M_{m} \}

Absurdo pues

min{Mn}≠min{Mm}min\{ M_{n} \}\neq min\{ M_{m} \}

hh es sobreyectiva Sea a∈A, ∃ m0,n∣f(m)=aa \in A,\:\exists\: m_{0} ,n\bigm|f(m)=a Hay una cantidad finita de números en MM que sean menores a m.m. Si hay n0n_{0} números menores que mm en MM

  ⟹  m=min{Mn0+1}  ⟹  h(n0+2)=f(min{Mn0+1})=f(m)=a\implies m=min\{ M_{n_{0}+1} \}\implies h(n_{0}+2)=f(min\{ M_{n_{0}+1 \}})=f(m)=a

Def. :{\color{Cyan} \text{Def. :} }

A,B dos conjuntos, decimos que #A≤#B si  ∃ f:A→B inyectiva.\begin{array}{l} \text{$A,B$ dos conjuntos, decimos que $\#A\leq\#B$ si $\:\exists\:f:A\to B$ inyectiva.} \end{array}

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

A,B conjuntos. #A≤#B  ⟺   ∃ g:B→A sobreyectiva.\begin{array}{l} \text{$A,B$ conjuntos. $\#A\leq\#B \iff \:\exists\:g:B\to A$ sobreyectiva.} \end{array}

Dem:{\color{Orange} \text{Dem:} }

  ⟹  )\implies)

Sea f:A→Bf:A\to B inyectiva. Sea a0∈A.a_{0} \in A. Sea

g:B→A∣g(b)={f−1(b) ∃ a∈A∣f(a)=ba0ccg:B\to A\bigm|g(b)=\begin{cases} f ^{-1}(b) & \:\exists\:a \in A\bigm| f(a)=b \\ a_{0} & cc \end{cases}

Como g∘f:A→A∣g∘f=IdA  ⟹  gg\circ f:A\to A\bigm|g \circ f=Id_{A}\implies g es sobreyectiva. (EJERCICIO)

Si tengo una composición que resulta ser la identidad, entonces la de afuera debe ser sobreyectiva.

  ⟸  )\impliedby) Si g:B→Ag:B\to A es sobreyectiva. Sea f:A→Bf:A\to B tal que f(a)f(a) es un elemento de BB tal que g(b)=ag(b)=a

Como g∘f=IdA  ⟹  fg \circ f=Id_{A}\implies f es inyectiva. (Esto último se deja como EJERCICIO)

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

Si A es infinito   ⟹  #N≤#A \begin{array}{l} \text{Si $A$ es infinito $\implies\#\mathbb{N}\leq\#A$ } \end{array}

Dem:{\color{Orange} \text{Dem:} } Se deja como EJERCICIO Idea: primer proposición de hoy.

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

A conjunto no vacıˊo#A≤#P(A)∧#A≠#P(A)\begin{array}{l} \text{$A$ conjunto no vacío}\\ \#A\leq \#\mathcal{P}(A)\quad \land \quad \#A\neq \#\mathcal{P}(A) \end{array}
  •  ∃ f:A→P(A)\:\exists\:f:A\to\mathcal{P}(A) inyectiva.
  •  ∄ f:A→P(A)\:\not\exists\:f:A\to\mathcal{P}(A) biyectiva.

Dem:{\color{violet} \text{Dem:} }

f:A→P(A)a↦{a}\begin{array}{c} f:A&\to\mathcal{P}(A) \\ a &\mapsto \{ a \} \end{array}

Así, ff resulta ser inyectiva.

Veamos que no existe biyectiva: Supongo que  ∃ f:A→P(A)\:\exists\:f:A\to\mathcal{P}(A) biyectiva. Sea

B={a∈A∣a∉f(a)}B=\{ a \in A\bigm| a \not\in f(a) \}

Si ff fuera sobreyectiva.

  ⟹   ∃ b∈A∣f(b)=B\implies \:\exists\: b \in A\bigm| f(b)=B

Si b∈B  ⟹  b∉f(b)=B  ⟹  b∉Bb \in B\implies b \not\in f(b)=B\implies b \not\in B Absurdo. Si b∉B  ⟹  b∈f(b)=B  ⟹  b∈Bb \not\in B\implies b \in f(b)=B\implies b \in B Absurdo. Por lo tanto ff no es sobreyectiva y por lo tanto no es biyectiva.

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

Sea A conjunto, #P(A)=#{0,1}A \begin{array}{l} \text{Sea $A$ conjunto, $\#\mathcal{P}(A)=\#\{ 0,1 \}^{A}$ } \end{array}

Dem:{\color{Orange} \text{Dem:} }

h:P(A)⟶{0,1}AB↦f:A→{0,1}∣f(a)={1a∈B0cc\begin{array}{l} h:\mathcal{P}(A)\longrightarrow \{ 0,1 \}^{A} \\ B\quad \quad \quad \mapsto f:A\to \{ 0,1 \}\quad \bigm|f(a)=\begin{cases} 1 & a \in B \\ 0 & cc \end{cases} \end{array}

hh es biyectiva

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

proposicion\begin{array}{l} \text{proposicion} \end{array}

En #A,≤\#A, \leq es un ORDEN. Es decir:

  1. #A≤#A\#A\leq\#A (IdA:A→AId_{A}:A\to A inyectiva)
  2. #A≤#B,#B≤#C  ⟹  #A≤#C\#A\leq\#B,\#B\leq\#C\implies\#A\leq\#C Por un lado  ∃ f:A→B\:\exists\:f:A\to B inyectiva y g:B→Cg:B\to C inyectiva. Entonces g∘f:A→Cg \circ f:A\to C es inyectiva.
  3. Si #A≤#B,#B≤#A  ⟹  #B=#A\#A\leq\#B,\#B\leq\#A\implies\#B=\#A ? Va a pasar que si.

Teorema de Cantor-Schroder-Bernstein:{\color{violet} \text{Teorema de Cantor-Schroder-Bernstein:} }

Sean A,B conjuntos tales que  ∃ f:A→B,g:B→A ambas inyectivas. Entonces existe h:A→B biyectiva.\begin{array}{l} \text{Sean $A,B$ conjuntos tales que $\:\exists\:f:A\to B,g:B\to A$ ambas inyectivas. }\\ \text{Entonces existe $h:A\to B$ biyectiva.} \end{array}

Dem:{\color{violet} \text{Dem:} } Supongamos que existe conjuntos A1A_{1} y A2A_{2} disjuntos tal que A1∪A2=A.A_{1} \cup A_{2}=A. También existen conjuntos B1B_{1} y B2B_{2} disjuntos talque B1∪B2=BB_{1}\cup B_{2}=B Sean f:A1→B1f:A_{1}\to B_{1} biyectiva g:B2→A2g:B_{2}\to A_{2} biyectiva.

Si eso vale f(A1)=B1f(A_{1})=B_{1} y B2=B∖f(A1)B_{2}=B \setminus f(A_{1})

Luego A2=g(B∖f(A1))A_{2}=g(B \setminus f(A_{1}))

  ⟹  A1=A∖A2=A∖g(B∖f(A1))\implies A_{1}=A \setminus A_{2}=A \setminus g(B \setminus f(A_{1}))

Buscamos un conjunto C⊆A∣C \subseteq A\bigm| C=A∖g(B∖f(C))C=A \setminus g(B \setminus f(C)) Sea

φ:P(A)⟶P(A)∣φ(X)=A∖g(B∖f(X))\begin{array}{c} {\Large\varphi}:\mathcal{P}(A)\longrightarrow \mathcal{P}(A) \bigm| {\Large\varphi}(X)=A \setminus g(B \setminus f(X)) \end{array}

Quiero ver que existe C⊆A∣φ(C)=CC \subseteq A\bigm|{\Large\varphi}(C)=C

Notar que si X⊆Y  ⟹  φ(X)⊆φ(Y)X \subseteq Y\implies {\Large\varphi}(X)\subseteq {\Large\varphi}(Y)

X⊆Y  ⟹  f(X)⊆f(Y)  ⟹  B∖f(X)⊇B∖f(Y)  ⟹  g(B∖f(X))⊇g(B∖f(Y))  ⟹  φ(X)=A∖g(B∖f(X))⊆A∖g(B∖f(Y))=φ(Y)\begin{array}{c} X\subseteq Y\implies f(X)\subseteq f(Y)\implies B \setminus f(X)\supseteq B \setminus f(Y) \\ \implies g(B \setminus f(X))\supseteq g(B \setminus f(Y)) \\ \implies {\Large\varphi}(X)= A \setminus g(B \setminus f(X))\subseteq A \setminus g(B \setminus f(Y))={\Large\varphi}(Y) \end{array}

Sea

G={C⊆A∣φ(C)⊆C}\mathcal{G}=\{ C \subseteq A\bigm| {\Large\varphi}(C)\subseteq C \}

G≠∅\mathcal{G}\neq \emptyset y A∈GA \in \mathcal{G} pues (φ(A)⊆A{\Large\varphi}(A)\subseteq A ) Sea

C=⋂D∈GDC=\bigcap_{D \in \mathcal{G}}D

Afirmo que φ(C)=C{\Large\varphi}(C)=C

C⊆D∀D∈G  ⟹  φ(C)⊆φ(D)⊆D∀D∈GC\subseteq D\quad \forall D \in\mathcal{G} \implies {\Large\varphi}(C)\subseteq {\Large\varphi}(D)\subseteq D\quad \forall D \in\mathcal{G}   ⟹  φ(C)⊆⋂D∈GD=C\implies {\Large\varphi}(C)\subseteq \bigcap_{D \in\mathcal{G}}D=C

Luego φ(C)∈G  ⟹  C⊂⋂D∈GD⊆φ(C)\displaystyle{\Large\varphi}(C) \in\mathcal{G}\implies C \subset \bigcap_{D \in\mathcal{G}} D\subseteq {\Large\varphi}(C)

  ⟹  φ(C)=C\implies {\Large\varphi}(C)=C

Citas y Comentarios