Demostrar que el conjunto de los números naturales Impares es infinito por el Principio de encasillamiento.

Question

Sólo se pueden utilizar números naturales, es decir, no se puede utilizar el 0. Tampoco se puede utilizar la resta. Demostrando que $f(n)=2n-1$ es biyectiva funcionaría, sólo que requeriría 0 y sustracción. Estas restricciones son difíciles pero quiero ver una prueba de Pigeonhole a esto. Gracias de antemano.

Answer 1

Podrías demostrar que el mapa $n\mapsto 2n+3$ definida sobre números naturales Impares es inyectiva pero no suryente.

Según el Principio de Pigeonhole las funciones inyectivas $f:S\to S$ son suryentes si $S$ es finito.

Answer 2

Supongamos que los enteros Impares son de número finito - digamos que hay $N$ de ellos. Si tenemos casillas $1,2, \dots N$ y poner el número de impar $2r-1$ en el $r^{th}$ de la casilla, entonces el número de impar $2N+1$ no tiene un lugar donde ir.

Pero esto no es realmente un problema de encasillamiento, en el sentido de que el argumento tiene que ser inventado, en lugar de argumentar directamente.

Answer 3

\=======

Rehacer.

1) Hay un número infinito de números naturales.

Pf: Supongamos que hay un número finito. Sea el número $k$ sea una "paloma" y que $k+1$ ser un "agujero". No hay $k + 1 = 1; k \in \mathbb N$ así que tenemos más palomas que agujeros. Por tanto, dos o más palomas ocupan el mismo agujero, es decir, existen $j \ne k$ pero $j + 1 = k+1$ . Esto es un error. Así que tenemos una contradicción.

A) Todos los números naturales son pares o Impares. Son mutuamente excluyentes y exhaustivos. Eso es simplemente una definición. $\mathbb N = \mathbb O \cup \mathbb E$ .

2) La unión de dos conjuntos finitos es finita.

Pf: Bueno, vale... empareja cada elemento del conjunto $A$ con un elemento del conjunto $B$ y llamar a ese par un "agujero", y tomar dos elementos de algún conjunto infinito $U$ y llamar a esos dos elementos "paloma". Eventualmente nos quedaremos sin elementos de cualquiera de los dos conjuntos $A$ o bien, establecer $B$ ya que son finitos pero no nos quedaremos sin pares de elementos de $U$ porque $U$ es infinito. Si uno de los conjuntos $A$ o $B$ es más grande seguir tomando "agujeros" del más grande y hacerlos coincidir con un solo elemento ("paloma") de $U$ . Al final nos quedaremos sin "agujeros" pero no sin palomas. Así que $A \cup B$ no puede inyectarse en $U$ así que $A \cup B$ no es infinito.

B) Así que o hay un número infinito de pares o un número infinito de probabilidades o ambos.

3) Para cualquier número natural $k$ los números $k$ y $k+1$ son paridades diferentes.

Si $k$ es incluso entonces $k = 2m$ donde $m$ es un número entero, por lo que $k + 1 = 2m + 1 = 2(m + \frac 12)$ y $m + \frac 12$ no es un número entero por lo que $k + 1$ no es uniforme, por lo tanto impar.

Si $k$ es $1$ entonces $k+1 = 2$ está en paz.

Si $k$ es impar y $k > 1$ entonces $k \ge 2$ pero como $2$ es incluso $k \ne 2$ así que $k > 2$ . Sea $2m$ sea el mayor número par para que $2m < k$ . Entonces $k = 2m + j$ y $k = 2(m + \frac j2)$ y ninguno de $m + \frac 12,.... m + \frac j2$ son números enteros. Pero $m + \frac 22$ es un número entero por lo que $0 < j < 2$ . Así que $j = 1$ . Así que $k = 2m + 1$ . Y $k + 1 = 2m + 2 = 2(m + 1)$ está en paz.

Así que

C) Si asignamos a los pares ser "agujeros" cada "agujero", $k$ tendrá una "paloma" impar, $k+1$ Así que hay al menos tantas palomas Impares como agujeros. Así que o bien hay finitamente muchos pares y por lo tanto infinitamente muchos impares. O hay infinitos pares y al menos infinitas probabilidades.

Así que... de cualquier manera hay infinitas probabilidades.

Y eso fue realmente un .... impar ... prueba.

\==== respuesta antigua abajo ======

Utilice el en jection $2n+1$ para demostrar que hay un número infinito de probabilidades iguales a $3$ o más. Si hay un número infinito de probabilidades con una restricción, habrá un número infinito de probabilidades sin la restricción (ya que no puede haber menos sin la restricción).

El agujero de la paloma parece una forma extraña de decirlo pero.... Para cada número par $k$ entonces $k + 2$ es el siguiente número par. Así que no hay un último número par, por lo que hay un número infinito de ellos. Para cada número par $k$ el siguiente número par será $k + 2$ . Pero entre cada $k$ y $k+2$ hay un número intermedio $k+1$ . Este número no puede ser par. Por lo tanto, según el principio de la colombofilia, es impar.

Pero eso no me gusta. Es ineficiente e innecesario y, probablemente, algo circular.

\==== en respuesta a un comentario =====

Si el propósito de esto es proporcionar una prueba sencilla y no perfeccionar nuestras habilidades teóricas, lo más fácil debe ser sencillo y sensible La prueba es simplemente demostrar:

$f: \mathbb N \to \mathbb O$ a través de $f(n) = 2n-1$ es una inyección.

Usted puede utilizar la sustracción siempre y cuando $a - b \ge 1$ . Eso será así y es parte de la prueba de $\mathbb O$ siendo la imagen de $f(\mathbb N)$ .

Pf:

1) $f(\mathbb N) \subset \mathbb O$ . Pf: $n \in N \implies n \ge 1 \implies 2n - 1 \ge 1; 2n - 1 \in \mathbb Z$ así que $f(\mathbb N) \subset \mathbb N$ . $f(n) = 2n-1 = 2(n-\frac 12)$ . $n - \frac 12$ no es un número entero por lo que $f(n)$ no es evven. ASÍ QUE $f(n)$ es un número natural impar. Así que $f(\mathbb N) \subset \mathbb O$ .

2) $f$ es inyectiva. $f(n) = f(m) \iff 2n - 1 = 2m - 1\iff n=m$

3) $f$ es suryente. $m \in \mathbb 0$ significa $m \ne 2k$ para cualquier número entero $k$ . $m < 2m$ por lo que existe un número par mayor que $m$ . Sea $m < 2j$ donde $j$ es el menor número par mayor que $m$ . $2j - 2$ es par (o inexistente y $2j = 2$ ) por lo que $2j -2 < m < 2j$ (o $m < 2$ ). Así que $m = 2j -1=f(j)$ (o $m = 1 = 2*1 -1=f(1)$ ).

Answer 4

Un conjunto $A$ es infinito si y sólo existe una biyección $f : A \rightarrow B$ , donde $B$ es un subconjunto propio de $A$ .

La función

$$f(n) = 2n + 1$$

es una biyección de este tipo, donde $A$ es el conjunto de números Impares y $B = \{ 2n + 1 \mid n \in \mathbb{N}, n\; \text{odd} \}$ .

Claramente $B \subsetneq A$ y vemos inmediatamente que $f$ es una biyección ya que $f$ es estrictamente creciente.