Autor Tema: Demostrar que \[J:ℕ×ℕ→ℕ\] es biyectiva

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

03 Julio, 2021, 03:10 am
Leído 226 veces

Rubén Maguregui

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 13
  • País: mx
  • Karma: +0/-0
  • Sexo: Masculino
\( \def\N{\mathbb{N}} \)Saludos.

En un problema se pide demostrar que la aplicación \( J:\N\times\N \rightarrow \N \) dada por
\[ J(m,n) = \frac{1}{2}[(m + n)^2 + 3m +n] \]
es biyectiva. La solución que se me ha ocurrido aparece abajo. Agradecería que puedieran darle una revisada. También me gustaría saber si se les ocurre una forma más simple de resolverlo.

    Mi solución:
    Observemos que \( J(m,n) \) puede expresarse en la forma
    \[
    J(m,n) = m + \sum_{i = 1}^{n + m} i.
    \]
    Para ver que \( J \) es inyectiva, supongamos que \( m,n,s,t\in\N \) y \( J(m,n) = J(s,t) \). Si fuese \( m + n < s + t \), tendríamos
    \begin{align*}
    J(s,t) - J(m,n) & = s - m + \sum_{{i = m + n + 1}}^{s + t} i \\
                    & \geq s - m + (s + t)                            \\
                    & \geq -m + s + t                                 \\
                    & \geq -(m + n) + s + t                           \\
                    & > 0,
    \end{align*}
    luego \( J(s,t) > J(m,n) \). Por tanto, ha de ser \( m + n = s + t \), pero esto y \( J(m,n) = J(s,t) \) claramente implican \( m = s \), de donde a su vez se sigue que \( n = t \), por lo que \( J \) es inyectiva.

    Para ver que también es sobreyectiva, supongamos que \( k \) es un número natural cualquiera. Entonces existe el mayor número natural \( b \) tal que
    \[
    s = \sum_{i = 1}^b i = 0 + 1 + 2 + \cdots + b \leq k,
    \]
    y dicho número cumple con \( 0\leq k - s < b + 1 \), pues si fuese \( k - s \geq b + 1 \), tendríamos
    \[
    k \geq s + (b + 1) = \sum_{i = 1}^{b + 1} i,
    \]
    en contradicción con la minimalidad de \( b \). Puesto que \( b \) es entero, \( k - s < b + 1 \) implica \( k - s \leq b \). Por lo tanto, si definimos \( m = k - s \), tendremos \( n = b - m \geq 0 \), luego \( m \) y \( n \) son ambos números naturales, y como \( k = s + m \) y \( b = m + n \),
    \[
    k = m + \sum_{i = 1}^{n + m} i,
    = J(m,n),
    \]
    lo que demuestra que \( J \) es sobreyectiva.

03 Julio, 2021, 10:16 am
Respuesta #1

geómetracat

  • Moderador Global
  • Mensajes: 2,583
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
La ecuación más bonita de las matemáticas: \( d^2=0 \)

03 Julio, 2021, 05:03 pm
Respuesta #2

Rubén Maguregui

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 13
  • País: mx
  • Karma: +0/-0
  • Sexo: Masculino

03 Julio, 2021, 07:39 pm
Respuesta #3

Fernando Revilla

  • Es más fácil engañar a alguien que convencerle de que ha sido engañado.
  • Administrador
  • Mensajes: 11,576
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • Las matemáticas son demasiado humanas (Brouwer).
    • Fernando Revilla

03 Julio, 2021, 08:04 pm
Respuesta #4

Juan Pablo Sancho

  • Moderador Global
  • Mensajes: 5,227
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Podrías también hacer una inyección de \( \mathbb{N} \times \mathbb{N} \to \mathbb{N}  \)
\( j(m,n) = 2^m \cdot 3^n  \).
Editado
Perdón, no era lo que pedías.

05 Julio, 2021, 07:16 pm
Respuesta #5

Rubén Maguregui

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 13
  • País: mx
  • Karma: +0/-0
  • Sexo: Masculino
Hola, Fernando.

También me gustaría saber si se les ocurre una forma más simple de resolverlo.

Puedes analizar Cantor pairing function.

Desconocía que esa construcción se debía a Cantor. Yo la encontré en el libro Elements of Set Theory de Herbert Enderton, pero en éste nunca se menciona el nombre que recibe esta biyección de \( \N^2 \) en \( \N \), y tampoco dice nada a cerca de su historia. Gracias por la referencia.

Saludos.