¿Por qué mi prueba es incorrecta para mostrar el conjunto de todas las funciones en aumento$f:\Bbb N\to\Bbb N$ no es contable?

Question

Básicamente, mi razonamiento es: se puede demostrar un bijection entre el conjunto de todas las funciones de $f(x)=x+a$ y números naturales mediante la asignación de cada número natural a la función con la correspondiente a un valor. ($1\mapsto x+1$... etc) Desde allí, se puede fácilmente demostrar que hay más funciones crecientes, además de la $x+a$, y por lo tanto la cardinalidad de funciones crecientes es mayor que el de los números naturales.

Mi amigo señaló este es defectuoso, utilizando el hecho de que podemos formar bijections con $\Bbb N$ por tanto $\Bbb Z^+$$\Bbb Z$.

Yo estaba modelando mi prueba después de la Diagonalización de Cantor, que muestra un bijection con un conjunto de números reales y, a continuación, demuestra que se pueden crear nuevos números reales fuera de nuestro original bijection. ¿Por qué es esto correcto, pero mi prueba no?

Answer 1

La idea crítica aquí es que el Cantor de la diagonalización argumento se basa en el hecho de que funciona no importa que propone la enumeración de los reales de empezar con. No es suficiente simplemente proporcionar una lista que echa de menos algunas cosas - si lo fuera, podríamos mostrar que los naturales eran incontables! Con el fin de mostrar que un conjunto $S$ es incontable, usted debe mostrar que no hay ninguna forma de asignar un diferente número natural a cada uno de los miembros de $S$, y no que uno que se pasó a elegir no funciona.

Es importante destacar que, el Cantor de la diagonalización ¿ no mostrar un bijection entre el$\mathbb{N}$$\mathbb{R}$; dice: "supongamos que un bijection existe" y, a continuación, se deriva una contradicción. O, si usted frase el argumento de forma ligeramente diferente, se dice "seleccionar cualquier función de $\mathbb{N}$ $\mathbb{R}$" y muestra que no importa cual sea la función que ha elegido, que no es una función surjective.

Answer 2

Creo que la parte que omitió es que al aplicar el Cantor diagonalisation, usted no puede especificar lo que su supuesta lista de elementos es, porque el punto es demostrar que , independientemente de cómo la lista se construye, siempre te echaremos de menos un elemento. Normalmente sólo construir una lista cuando quieres demostrar que esa lista existe (que es el caso cuando usted está tratando de mostrar un bijection entre conjuntos, por ejemplo, para mostrar que los racionales son numerables).

Así que en lugar de "Vamos a la lista de las funciones $x$, $x+1$, $x+2$, ..." usted tiene que decir "Supongamos que hay una lista. Deje que los elementos de la lista se $f_1, f_2, f_3, \ldots$" y trabajar desde allí.

Answer 3

$\newcommand{\Natl}{\mathbf{N}}\newcommand{\Incr}{\mathcal{I}}$Deje $\Incr$ denota el conjunto de funciones crecientes de $\Natl$ a sí mismo.

• Su objetivo es mostrar cualquiera de:

  No existe un surjection $\Phi:\Natl \to \Incr$.

  Contrapositively, si $\Phi:\Natl \to \Incr$ es arbitraria asignación y, a continuación, $\Phi$ no es surjective.

• Que han demostrado:

  Una asignación determinada $\Phi:\Natl \to \Incr$ no es un surjection. (Específicamente, la asignación de $a \mapsto \Phi_{a}$, $\Phi_{a}(x) = x + a$ para todos los números naturales $x$ no es un surjection.)

La diferencia es, tal vez algunos otros mapeo $\Phi:\Natl \to \Incr$ es surjective. En otras palabras, no tuvo en cuenta una arbitraria asignación de $\Phi:\Natl \to \Incr$.

---

Lo que puede ayudar en tu situación es mostrar que:

1. Una función creciente $f:\Natl \to \Natl$ se asocian únicamente con un subconjunto infinito de $\Natl$ (es decir, su imagen).

2. El conjunto de los infinitos subconjuntos de a $\Natl$ es incontable.

Answer 4

El error está en suponer que "hay más". El concepto de "hay más" debe ser demostrado, demostrando que existe un bijection a algunos de la multitud innumerable o, equivalentemente, que no existe una contables bijection (como el teorema de diagonalización).

Observar que, en el mismo sentido, podemos decir que el conjunto definido por $\Bbb N_{\ge0}\cup\{\sqrt 2\}$ "tiene más elementos" de $\Bbb N_{\ge 0}$. Pero la cardinalidad de un conjunto se define a través de bijection con otro conjunto. En nuestro caso, la función de $f(n):=\delta_{0,n}(\sqrt2+1)+n-1$ es un bijection de$\Bbb N_{\ge 0}$$\Bbb N_{\ge 0}\cup\{\sqrt2\}$, con lo que ambos conjuntos tienen la misma cardinalidad (donde $\delta_{j,k}$ es la delta de Kronecker).