Autor Tema: Cardinalidad de biyecciones de los naturales

0 Usuarios y 1 Visitante están viendo este tema.

09 Diciembre, 2011, 04:40 pm
Leído 952 veces

jbgg

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 218
  • Karma: +0/-0
  • Sexo: Masculino
La pregunta es cual es la cardinalidad del conjunto de las biyecciones de \( \mathbb{N} \). Y si sabeis o se os ocurre una manera de probarlo lo agradecería.

Gracias.

09 Diciembre, 2011, 05:02 pm
Respuesta #1

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,346
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
El cardinal es el del continuo, o sea, el mismo de \( \mathcal P(N) \) y el de \( \mathbb R \).

Como el cardinal del conjunto de funciones de N en N es el del continuo (verificarlo), y la clase de biyecciones está contenida allí, el cardinal de la clase de biyecciones de N en N es menor o igual que el del continuo.

__________-

Para ver que es (mayor o) igual, se me ocurre un análisis casero, así:

Considerar las funciones estrictamente crecientes g de N en N.
Dichas funciones son inyectivas.


Denotamos B = 2g(N), o sea, el recorrido de 2g.
Tanto el conjunto B, como el conjunto N - B son infinitos, y además su unión es todo N.

Ahora definimos una biyección G asociada a g, así:
Para x = 2n, o sea x par, hacemos:

 G(2n) = 2g(n).

Y cuando x es impar, definimos G(x) por recurrencia, así:

G(1) = 1er elemento de N - B,
...
G(2n+1) = n-ésimo elemento de N - B
___________________

Se puede demostrar (verificar) que G es una biyección de N en N.

La aplicación que a cada g le asigna su correspondiente G es una inyección entre la clase de inyecciones de N en N, en la clase de biyecciones de N en N.

Se puede comprobar más o menos fácilmente que el cardinal de las sucesiones crecientes de N en N (o sea, las inyecciones crecientes), es el mismo que el de \( \mathcal P(N) \).
Por lo tanto el cardinal de las biyecciones es mayor o igual, por la manera en que construimos la aplicación:

g ----->  G

Y esto termina las comprobaciones.

09 Diciembre, 2011, 05:20 pm
Respuesta #2

Carlos Ivorra

  • Administrador
  • Mensajes: 9,674
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Una alternativa:

Descompón \( \mathbb{N}=A\cup B\cup C \) en unión disjunta de tres conjuntos infinitos.

Para cada \( X\subset A \), los conjuntos \( X\cup B,\quad (A\setminus X)\cup C,\quad  A\cup B,\quad  C \) son infinitos numerables, luego puedes tomar biyecciones (puedes incluso definirlas explícitamente)

\( f_X:X\cup B\longrightarrow A\cup B \),      \( g_X: (A\setminus X)\cup C\longrightarrow C \)

de modo que \( h_X=f_X\cup g_X: \mathbb{N}\longrightarrow \mathbb{N} \) es una biyección tal que \( h_X^{-1}[A\cup B]\cap A = X \).

Por lo tanto, la aplicación \( \mathcal PA\longrightarrow B \) dada por \( X\mapsto h_X \), donde \( B \) es el conjunto de biyecciones de \( \mathbb{N} \), es inyectiva, luego \( 2^{\aleph_0}=|\mathcal P A|\leq |B| \).

09 Diciembre, 2011, 05:26 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 9,674
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Otra posibilidad, si sabes que el conjunto de los subconjuntos finitos de \( \mathbb{N} \) es numerable y que, por tanto, el conjunto de los subconjuntos infinitos de \( \mathbb{N} \) tiene cardinal \( 2^{\aleph_0} \), es que consideres únicamente conjuntos infinitos \( X \). En tal caso te basta dividir \( \mathbb{N}=A\cup B \) y biyectar \( X \) con \( A \) y \( (A\setminus X)\cup B \) con \( B \).

09 Diciembre, 2011, 05:33 pm
Respuesta #4

jbgg

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 218
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias a ámbos. He entendido la primera alternativa de Carlos Ivorra. Y me parece entendible más o menos a la segunda lectura.

09 Diciembre, 2011, 05:40 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 9,674
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Muchas gracias a ámbos. He entendido la primera alternativa de Carlos Ivorra. Y me parece entendible más o menos a la segunda lectura.

No entiendo el "más o menos". Si necesitas alguna aclaración, no dudes en preguntar.

09 Diciembre, 2011, 05:44 pm
Respuesta #6

jbgg

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 218
  • Karma: +0/-0
  • Sexo: Masculino
Quizás el orden de la frase no está bien, he querido decir que he la he entendido a las 2 lecturas. Y el "más o menos" hace referencia al número de lecturas. Disculpe mi forma de expresarme.