Artículos

1.1: El principio del buen orden y la inducción matemática - Matemáticas


Dado un conjunto (S ) de números (de cualquier tipo), decimos que ( ell in S ) es un elemento mínimo de (S ) si ( forall x in S ), ya sea (x = ell ) o ( ell

Cada conjunto no vacío de números naturales tiene un elemento mínimo.

Este principio a menudo se toma como un axioma.

El principio del casillero

[thm: casillero] El principio del casillero: Deje que (s, k in NN ) satisfaga (s> k ). Si los objetos (s ) se colocan en cajas (k ), entonces al menos una caja contiene más de un objeto.

Suponga que ninguna de las cajas contiene más de un objeto. Entonces hay como máximo (k ) objetos. Esto conduce a una contradicción con el hecho de que hay (s ) objetos para (s> k ).

El principio de inducción matemática

Ahora presentamos una valiosa herramienta para probar resultados sobre números enteros. Esta herramienta es el principio de inducción matemática.

El primer principio de inducción matemática: Sea (S subset NN ) un conjunto que satisfaga las siguientes dos propiedades:

  1. (1 en S ); y
  2. ( forall k in NN, k in S Rightarrow k + 1 in S ).

Entonces (S = NN ). De manera más general, si ( Pp (n) ) es una propiedad de los números naturales que puede o no ser cierta para cualquier (n in NN ) particular, satisfaciendo

  1. ( Pp (1) ) es cierto; y
  2. ( forall k in NN, Pp (k) Rightarrow Pp (k + 1) )

entonces ( forall n in NN, Pp (n) ) es verdadero.

Usamos el principio del buen orden para probar este primer principio de inducción matemática.

Sea (S ) el conjunto de la primera parte del teorema y sea (T ) el conjunto de números naturales que no están en (S ). Usaremos una prueba por contradicción, así que suponga que (T ) no está vacío.

Entonces, por el principio de ordenamiento correcto, (T ) contiene un elemento mínimo ( ell ).

Tenga en cuenta que (1 in S ), entonces (1 notin T ) y por lo tanto ( ell> 1 ). Por tanto, ( ell-1 ) es un número natural. Dado que ( ell ) es el elemento menor de (T ), ( ell-1 ) no está en (T ), por lo tanto, está en (S ).

Pero por las propiedades definitorias de (S ), ya que ( ell-1 en S ), ( ell = ell-1 + 1 in S ), lo cual contradice el hecho de que ( ell ) es un elemento mínimo de (T ), entonces en (T ), entonces no en (S ).

Esta contradicción implica que la suposición de que (T ) no está vacía es falsa, por lo tanto (S = NN ).

Para la segunda parte del teorema, deje (S = {n in NN mid Pp (n) text { is true} } ) y aplique la primera parte.

[por ejemplo: inducciónv1a] Usamos la inducción matemática para mostrar que ( forall n in mathbb {N} ) [ sum_ {j = 1} ^ nj = frac {n (n + 1)} {2 }. ] Primero tenga en cuenta que [ sum_ {j = 1} ^ 1j = 1 = frac {1 cdot 2} {2} ] y por lo tanto la declaración es verdadera para (n = 1 ). Para el paso inductivo restante, suponga que la fórmula es válida para algún (n in NN ) particular, es decir ( sum_ {j = 1} ^ nj = frac {n (n + 1)} {2 } ). Demostramos que [ sum_ {j = 1} ^ {n + 1} j = frac {(n + 1) (n + 2)} {2}. ] Para completar la demostración por inducción. De hecho [ sum_ {j = 1} ^ {n + 1} j = sum_ {j = 1} ^ nj + (n + 1) = frac {n (n + 1)} {2} + (n + 1) = frac {(n + 1) (n + 2)} {2}, ] y el resultado sigue.

[por ejemplo: inducciónv1b] Ahora usamos la inducción matemática para demostrar que (n! leq n ^ n ) ( forall n in NN ).

Tenga en cuenta que (1! = 1 leq 1 ^ 1 = 1 ). Presentamos ahora el paso inductivo. Supongamos que [n! Leq n ^ n ] para algunos (n in NN ), demostramos que ((n + 1)! Leq (n + 1) ^ {n + 1} ). Tenga en cuenta que [(n + 1)! = (N + 1) n! Leq (n + 1) .n ^ n <(n + 1) (n + 1) ^ {n} = (n + 1) ^ {n + 1}. ] Esto completa la demostración.

El segundo principio de inducción matemática: Sea (S subset NN ) un conjunto que satisfaga las siguientes dos propiedades:

  1. (1 en S ); y
  2. ( forall k in NN, 1, dots, k in S Rightarrow k + 1 in S ).

Entonces (S = NN ). De manera más general, si ( Pp (n) ) es una propiedad de los números naturales que puede o no ser cierta para cualquier (n in NN ) particular, satisfaciendo

  1. ( Pp (1) ) es cierto; y
  2. ( forall k in NN, ) si ( Pp (1), dots, Pp (k) ) son todos verdaderos, entonces ( Pp (k + 1) ) también es cierto

entonces ( forall n in NN, Pp (n) ) es verdadero.

Para probar el segundo principio de inducción, usamos el primer principio de inducción.

Sea (S ) un conjunto de números enteros como en la primera parte del teorema. Para (n in NN ), sea ( Pp (n) ) la propiedad matemática “ (1, dots, n in S )”. Entonces podemos aplicar el Primer Principio de Inducción Matemática para demostrar que ( forall n in NN Pp (n) ) es verdadero, lo que significa (S = NN ). [Detalles dejados al lector.]

La segunda parte del teorema se deriva de la primera exactamente de la misma manera que la segunda parte del primer principio de inducción matemática siguió a la primera.

Ejercicios

Demuestre usando inducción matemática que (n <3 ^ n ) para todos los enteros positivos (n ).

Muestre que ( sum_ {j = 1} ^ nj ^ 2 = frac {n (n + 1) (2n + 1)} {6} ).

Utilice la inducción matemática para demostrar que ( sum_ {j = 1} ^ n (-1) ^ {j-1} j ^ 2 = (- 1) ^ {n-1} n (n + 1) / 2 ).

Utilice la inducción matemática para demostrar que ( sum_ {j = 1} ^ nj ^ 3 = [n (n + 1) / 2] ^ 2 ) para cada entero positivo (n ).

Usa la inducción matemática para demostrar que ( sum_ {j = 1} ^ n (2j-1) = n ^ 2 ).

Usa la inducción matemática para demostrar que (2 ^ n

Usa la inducción matemática para demostrar que (n ^ 2


  1. Un matemático ficticio y autor de muchos textos excelentes de matemáticas (no ficticios, realmente existen), como ↩
  2. Espía aparentemente proviene del inglés antiguo yfesdrype, que significa literalmente uno que se para al escuchar a escondidas [suelo donde el agua gotea de los aleros del techo] escuchar conversaciones dentro de una casa.
  3. ¡Otra sinécdoque! ↩
  4. Al-Kindi es una figura muy interesante de la historia intelectual musulmana temprana: p.ej., parece haber traído los números hindúes, con su notación de valor posicional, al mundo musulmán.
  5. En un clásico computadora: existe un algoritmo eficiente conocido por factorizar en un computadora cuántica, ver y .↩
  6. Aunque, de hecho, alguna criptografía de clave pública viable se había inventado anteriormente dentro de la comunidad de inteligencia de EE. UU./ Reino Unido y no se compartió con el público. Desde muy temprano en la Guerra Fría, ha habido teoremas matemáticos y demostraciones mantenidas en secreto por los grandes gobiernos.
  7. Como es el caso de la factorización, existe un algoritmo conocido para computadora cuántica que resuelve el DHP de manera eficiente, consulte .↩

El principio del buen orden

El principio de ordenamiento correcto dice que los enteros positivos son bien ordenado. Un conjunto ordenado se ha dicho bien ordenado si todos y cada uno de los subconjuntos no vacíos tienen un elemento menor o menor. Entonces, el principio de buen orden es la siguiente declaración:

Tenga en cuenta que esta propiedad no es cierta para los subconjuntos de números enteros (en los que hay números negativos arbitrariamente pequeños) o los números reales positivos (en los que hay elementos arbitrariamente cercanos a cero).

Un enunciado equivalente al principio de buen orden es el siguiente:

El conjunto de enteros positivos no contiene ninguna secuencia infinita estrictamente decreciente.

La prueba de que este principio es equivalente al principio de inducción matemática se encuentra a continuación.


Cuando preguntaste sobre la inducción fuerte el otro día, me pregunté si el principio del buen orden estaba en camino y aquí estamos.

¿No estamos probando realmente que la inducción débil implica la existencia de un ordenamiento parcial particular ≤ en N tal que es un ordenamiento bien con $ x leq y Rightarrow x leq S (y) $?

Eso sería algo sensato, pero probablemente no sea lo que está sucediendo aquí.

Supongo que te estás estudiando por tu cuenta, ya que dijiste antes que estabas trabajando dentro de tu propio marco para los números naturales y que estás trabajando con un texto que demuestra que la inducción débil, la inducción fuerte y el buen orden son equivalentes.

Un texto que haga eso podría comenzar con un conjunto relativamente grande de axiomas de números naturales, los axiomas de Peano, excluyendo la inducción, digamos algunas leyes de orden y algunas leyes de adición. O podría derivar el orden de la adición, como parece que lo hacen las notas de la conferencia de Mauro Allegranza. Puede que ni siquiera establezca un conjunto de axiomas, sino que simplemente proceda del conocimiento informal preexistente: "Ya sabes mucho sobre los números naturales, pero ahora te contaremos tres cosas nuevas, aunque resultará que son realmente solo una cosa nueva. & quot

De todos modos, esto está en un nivel teórico más bajo que comenzar con los axiomas de Peano, construyendo las relaciones de orden y las operaciones aritméticas, y demostrando una fuerte inducción y un buen ordenamiento. Quizás por eso decidió desarrollar su propio marco.

En pocas palabras: lo más probable es que la pregunta que formule no sea la misma pregunta que hace su texto, sino una pregunta mejor.


Álgebra abstracta: MUESTRA XML PRETEXTUAL SOLAMENTE

para cualquier número natural (n text <.> ) Esta fórmula se verifica fácilmente para números pequeños como (n = 1 text <,> ) 2, 3 o 4, pero es imposible verificar todos los números naturales según el caso. Para probar que la fórmula es cierta en general, se requiere un método más genérico.

Suponga que hemos verificado la ecuación para los primeros (n ) casos. Intentaremos mostrar que podemos generar la fórmula para el ((n + 1) ) ésimo caso a partir de este conocimiento. La fórmula es verdadera para (n = 1 ) ya que

Si hemos verificado los primeros (n ) casos, entonces

Ésta es exactamente la fórmula para el caso ((n + 1) ) th.

Este método de prueba se conoce como. En lugar de intentar verificar una declaración sobre algún subconjunto (S ) de los enteros positivos (< mathbb N> ) caso por caso, una tarea imposible si (S ) es un conjunto infinito , damos una prueba específica para el número entero más pequeño que se está considerando, seguido de un argumento genérico que muestra que si la declaración es válida para un caso dado, entonces también debe ser válida para el siguiente caso en la secuencia. Resumimos la inducción matemática en el siguiente axioma.

Principio 2.1.1. Primer principio de inducción matemática.

Sea (S (n) ) un enunciado sobre enteros para (n in < mathbb N> ) y suponga que (S (n_0) ) es verdadero para algún entero (n_0 text <.> ) Si para todos los enteros (k ) con (k geq n_0 text <,> ) (S (k) ) implica que (S (k + 1) ) es verdadero, entonces (S (n) ) es cierto para todos los enteros (n ) mayores o iguales que (n_0 text <.> )

Ejemplo 2.1.2. Una desigualdad de potencias de (2 ).

Para todos los enteros (n geq 3 text <,> ) (2 ^ n gt n + 4 text <.> ) Dado

la afirmación es verdadera para (n_0 = 3 text <.> ) Suponga que (2 ^ k gt k + 4 ) para (k geq 3 text <.> ) Entonces (2 ^ = 2 cdot 2 ^ gt 2 (k + 4) text <.> ) Pero

ya que (k ) es positivo. Por lo tanto, por inducción, la declaración es válida para todos los enteros (n geq 3 text <.> )

Ejemplo 2.1.3. Algunos enteros divisibles por (9 ).

Cada entero (10 ​​^ + 3 cdot 10 ^ n + 5 ) es divisible por 9 para (n in < mathbb N> text <.> ) Para (n = 1 text <,> )

es divisible por 9. Suponga que (10 ​​^ + 3 cdot 10 ^ k + 5 ) es divisible por 9 para (k geq 1 text <.> ) Entonces

Ejemplo 2.1.4. El teorema del binomio.

Demostraremos el teorema del binomio usando inducción matemática, es decir,

donde (a ) y (b ) son números reales, (n in mathbb text <,> ) y

es el coeficiente binomial. Primero mostramos que

Si (n = 1 text <,> ) el teorema del binomio es fácil de verificar. Ahora suponga que el resultado es verdadero para (n ) mayor o igual que 1. Entonces

Tenemos una declaración equivalente del principio de inducción matemática que a menudo es muy útil.

Principio 2.1.5. Segundo principio de inducción matemática.

Sea (S (n) ) un enunciado sobre enteros para (n in < mathbb N> ) y suponga que (S (n_0) ) es verdadero para algún entero (n_0 text <.> ) Si (S (n_0), S (n_0 + 1), ldots, S (k) ) implican que (S (k + 1) ) para (k geq n_0 text <,> ) entonces la declaración (S (n) ) es verdadera para todos los enteros (n geq n_0 text <.> )

Un subconjunto no vacío (S ) de (< mathbb Z> ) es si (S ) contiene un elemento mínimo. Observe que el conjunto (< mathbb Z> ) no está bien ordenado ya que no contiene un elemento más pequeño. Sin embargo, los números naturales están bien ordenados.

Principio 2.1.6. Principio de buen orden.

Cada subconjunto no vacío de los números naturales está bien ordenado.

El principio de buen orden es equivalente al principio de inducción matemática.

Lema 2.1.7.

El principio de inducción matemática implica que (1 ) es el número natural menos positivo.

Prueba .

Deje (S = : n geq 1 > text <.> ) Entonces (1 in S text <.> ) Ahora suponga que (n en S text <> ) es decir, (n geq 1 text <.> ) Dado que (n + 1 geq 1 text <,> ) (n + 1 en S text < > ) por tanto, por inducción, todo número natural es mayor o igual que 1.

Teorema 2.1.8.

El principio de inducción matemática implica el principio de buen orden. Es decir, cada subconjunto no vacío de ( mathbb N ) contiene un elemento mínimo.

Prueba .

Debemos mostrar que si (S ) es un subconjunto no vacío de los números naturales, entonces (S ) contiene un elemento mínimo. Si (S ) contiene 1, entonces el teorema es verdadero según el Lema 2.1.7. Suponga que si (S ) contiene un número entero (k ) tal que (1 leq k leq n text <,> ) entonces (S ) contiene un elemento mínimo. Demostraremos que si un conjunto (S ) contiene un número entero menor o igual que (n + 1 text <,> ) entonces (S ) tiene un elemento mínimo. Si (S ) no contiene un número entero menor que (n + 1 text <,> ) entonces (n + 1 ) es el número entero más pequeño en (S text <.> ) De lo contrario, dado que (S ) no está vacío, (S ) debe contener un número entero menor o igual que (n text <.> ) En este caso, por inducción, (S ) contiene un elemento mínimo.

La inducción también puede ser muy útil para formular definiciones. Por ejemplo, hay dos formas de definir (n! Text <,> ) el factorial de un entero positivo (n text <.> )

La explícito definición: (n! = 1 cdot 2 cdot 3 cdots (n - 1) cdot n text <.> )

La inductivo o recursivo definición: (1! = 1 ) y (n! = n (n - 1)! ) para (n gt 1 text <.> )

Todo buen matemático o informático sabe que mirar los problemas de forma recursiva, en lugar de hacerlo explícitamente, a menudo da como resultado una mejor comprensión de cuestiones complejas.


1.3 Principio de ordenación adecuada

Este es uno de los más de 2.400 cursos de OCW. Explore los materiales de este curso en las páginas vinculadas a la izquierda.

MIT OpenCourseWare es una publicación abierta y gratuita de material de miles de cursos del MIT, que cubre todo el plan de estudios del MIT.

Sin inscripción ni registro. Navegue libremente y utilice los materiales de OCW a su propio ritmo. No hay registro, ni fechas de inicio ni de finalización.

El conocimiento es tu recompensa. Utilice OCW para guiar su propio aprendizaje de por vida o para enseñar a otros. No ofrecemos crédito ni certificación por usar OCW.

Hecho para compartir. Descarga archivos para más tarde. Envíe a amigos y colegas. Modificar, mezclar y reutilizar (solo recuerde citar OCW como fuente).

Acerca de MIT OpenCourseWare

MIT OpenCourseWare es una publicación en línea de materiales de más de 2500 cursos del MIT, que comparte conocimientos libremente con estudiantes y educadores de todo el mundo. Más información & raquo

& copiar 2001 y ndash2018
Instituto de Tecnología de Massachusetts

Su uso del sitio y los materiales de MIT OpenCourseWare está sujeto a nuestra Licencia Creative Commons y otros términos de uso.


2. Inducción estructural & # x7ED3 & # x6784 & # x5F52 & # x7EB3 & # x6CD5

Para probar resultados sobre conjuntos definidos recursivamente, podemos usar Inducción estructural

  • Paso básico: demuestre que el resultado es válido para todos los elementos especificados en el paso básico de la definición recursiva para que estén en el conjunto.
  • Paso recursivo: demuestre que si el enunciado es verdadero para cada uno de los elementos utilizados para construir nuevos elementos en el paso recursivo de la definición, el resultado es válido para estos nuevos elementos.

Sección 6 Inducción matemática

para cualquier número natural (n text <.> ) Esta fórmula se verifica fácilmente para números pequeños como (n = 1 text <,> ) (2 text <,> ) (3 text <,> ) o (4 text <,> ) pero es imposible verificar todos los números naturales caso por caso. Para probar que la fórmula es cierta en general, se requiere un método más genérico.

Suponga que hemos verificado la ecuación para los primeros (n ) casos. Intentaremos mostrar que podemos generar la fórmula para el ((n + 1) ) ésimo caso a partir de este conocimiento. La fórmula es verdadera para (n = 1 ) ya que

Si hemos verificado los primeros (n ) casos, entonces

Ésta es exactamente la fórmula para el caso ((n + 1) ) th.

Este método de prueba se conoce como inducción matemática. En lugar de intentar verificar una declaración sobre algún subconjunto (S ) de los enteros positivos (< mathbb N> ) caso por caso, una tarea imposible si (S ) es un conjunto infinito , damos una prueba específica para el número entero más pequeño que se está considerando, seguido de un argumento genérico que muestra que si la declaración es válida para un caso dado, entonces también debe ser válida para el siguiente caso en la secuencia. Resumimos la inducción matemática en el siguiente axioma.

Principio 6.31 Primer principio de inducción matemática

Sea (S (n) ) un enunciado sobre enteros para (n in < mathbb N> ) y suponga que (S (n_0) ) es verdadero para algún entero (n_0 text <.> ) Si para todos los enteros (k ) con (k geq n_0 text <,> ) (S (k) ) implica que (S (k + 1) ) es verdadero, entonces (S (n) ) es cierto para todos los enteros (n ) mayores o iguales que (n_0 text <.> )

Ejemplo 6.32

Para todos los enteros (n geq 3 text <,> ) (2 ^ n gt n + 4 text <.> ) Dado

empezar 8 = 2 ^ 3 gt 3 + 4 = 7, end

la afirmación es verdadera para (n_0 = 3 text <.> ) Suponga que (2 ^ k gt k + 4 ) para (k geq 3 text <.> ) Entonces (2 ^ = 2 cdot 2 ^ gt 2 (k + 4) text <.> ) Pero

empezar 2 (k + 4) = 2k + 8 gt k + 5 = (k + 1) + 4 end

ya que (k ) es positivo. Por lo tanto, por inducción, la declaración es válida para todos los enteros (n geq 3 text <.> )

Ejemplo 6.33

Cada entero (10 ​​^ + 3 cdot 10 ^ n + 5 ) es divisible por (9 ) para (n in < mathbb N> text <.> ) Para (n = 1 text <,> )

empezar 10 ^ <1 + 1> + 3 cdot 10 + 5 = 135 = 9 cdot 15 end

es divisible por (9 text <.> ) Suponga que (10 ​​^ + 3 cdot 10 ^ k + 5 ) es divisible por (9 ) para (k geq 1 text <.> ) Entonces

empezar 10 ^ <(k + 1) + 1> + 3 cdot 10 ^ + 5 & amp = 10 ^ + 3 cdot 10 ^ + 50 - 45 & amp = 10 (10 ^ + 3 cdot 10 ^ + 5) - 45 end

Ejemplo 6.34

Demostraremos el teorema del binomio usando inducción matemática, es decir,

donde (a ) y (b ) son números reales, (n in mathbb text <,> ) y

es el coeficiente binomial. Primero mostramos que

Si (n = 1 text <,> ) el teorema del binomio es fácil de verificar. Ahora suponga que el resultado es verdadero para (n ) mayor o igual que (1 text <.> ) Entonces

Tenemos una declaración equivalente del principio de inducción matemática que a menudo es muy útil.

Principio 6.35 Segundo principio de inducción matemática

Sea (S (n) ) un enunciado sobre enteros para (n in < mathbb N> ) y suponga que (S (n_0) ) es verdadero para algún entero (n_0 text <.> ) Si (S (n_0), S (n_0 + 1), ldots, S (k) ) implican que (S (k + 1) ) para (k geq n_0 text <,> ) entonces la declaración (S (n) ) es verdadera para todos los enteros (n geq n_0 text <.> )

Un subconjunto no vacío (S ) de (< mathbb Z> ) es bien ordenado si (S ) contiene un elemento mínimo. Observe que el conjunto (< mathbb Z> ) no está bien ordenado ya que no contiene el elemento más pequeño. Sin embargo, los números naturales están bien ordenados.

Principio 6.36 Principio de buen orden

Cada subconjunto no vacío de los números naturales está bien ordenado.

El principio de buen orden es equivalente al principio de inducción matemática.

Lema 6.37

El principio de inducción matemática implica que (1 ) es el número natural menos positivo.

Prueba

Sea (S = : n geq 1 > text <.> ) Entonces (1 in S text <.> ) Suponga que (n in S text <.> ) Dado que (0 lt 1 text <,> ) debe darse el caso de que (n = n + 0 lt n + 1 text <.> ) Por lo tanto, (1 leq n lt n + 1 text <.> ) En consecuencia, si (n in S text <,> ) entonces (n + 1 ) también debe estar en (S text <,> ) y por el principio de inducción matemática, y (S = mathbb N text <.> )

Teorema 6.38

El principio de inducción matemática implica el principio de buen orden. Es decir, cada subconjunto no vacío de ( mathbb N ) contiene un elemento mínimo.

Prueba

Debemos mostrar que si (S ) es un subconjunto no vacío de los números naturales, entonces (S ) contiene un elemento mínimo. Si (S ) contiene 1, entonces el teorema es verdadero según el Lema 6.37. Suponga que si (S ) contiene un número entero (k ) tal que (1 leq k leq n text <,> ) entonces (S ) contiene un elemento mínimo. Demostraremos que si un conjunto (S ) contiene un número entero menor o igual que (n + 1 text <,> ) entonces (S ) tiene un elemento mínimo. Si (S ) no contiene un número entero menor que (n + 1 text <,> ) entonces (n + 1 ) es el número entero más pequeño en (S text <.> ) De lo contrario, dado que (S ) no está vacío, (S ) debe contener un número entero menor o igual que (n text <.> ) En este caso, por inducción, (S ) contiene un elemento mínimo.

La inducción también puede ser muy útil para formular definiciones. Por ejemplo, hay dos formas de definir (n! Text <,> ) el factorial de un entero positivo (n text <.> )

La explícito definición: (n! = 1 cdot 2 cdot 3 cdots (n - 1) cdot n text <.> )

La inductivo o recursivo definición: (1! = 1 ) y (n! = n (n - 1)! ) para (n gt 1 text <.> )

Todo buen matemático o informático sabe que mirar los problemas de forma recursiva, en lugar de hacerlo explícitamente, a menudo da como resultado una mejor comprensión de cuestiones complejas.


SOLUCIÓN: MATH 109 Preguntas sobre problemas de matemáticas de la Universidad de California en San Diego

Matemáticas 109 SS1 2020
Tarea 3
Lec A Prof. Chow
Fecha límite el martes 25 de agosto a las 11:59 pm (nueva fecha de vencimiento) mediante envío en línea a
Gradoscopio.
Todos los ejercicios, problemas y números de página se refieren al libro de Eccles.
# 1. Realice el ejercicio 11.1 de la pág. 143 de Eccles: Supongamos que Nn → X es una sobreyección. Probar,
por inducción en n, que X es un conjunto finito y que | X | ≤ n.
# 2. Haga el n. ° 9 en los problemas III de la pág. 184: Demuestre la Proposición 11.1.4: si X → Nn es una
inyección, entonces X es finito y | X | ≤ n.
# 3. Realice el ejercicio 11.4 de la pág. 143 de Eccles: Demuestre que, si ayb son enteros distintos de cero
con mcd (a, b) = d, entonces los enteros a / d y b / d son coprimos.
# 4. Demuestre: si A es un conjunto finito no vacío de números reales, entonces A tiene un mínimo
elemento. (Este es el n. ° 5 en los problemas III de la p. 183, que es la "mitad" de la Proposición 11.2.3).
# 5. Dados números enteros distintos de cero a1,. . . , un, deja
D (a1,..., An) = .
Demuestre por inducción que max D (a1,..., An) ≤ min <| a1 |,. . . , | an |>.
# 6. Realice el ejercicio 11.6 de la pág. 143: Demuestre por inducción sobre n que si A es un conjunto de
enteros sin un elemento mínimo, entonces Nn ⊆ Z + - A para cada n, de modo que A es el conjunto vacío.
Deduzca el principio de ordenamiento correcto: cada conjunto no vacío de enteros positivos tiene un mínimo
elemento.
# 7. Haga el n. ° 11 en los problemas III de la pág. 184. Utilice el principio del casillero y pruebe
contradicción para demostrar Teorema 11.1.7: Dados conjuntos finitos no vacíos X e Y con | X | = | Y |,
una función f: X → Y es una inyección si y solo si f es una sobreyección.
# 8. Haga el n. ° 12 en los problemas III de la p. 184: Suponga que hay una inyección f: Z + → X.
Demuestre por contradicción que X es un conjunto infinito.
# 9. Haga el n. ° 15 en los problemas III de la pág. 184: Demuestre el principio de inducción a partir del principio de buen orden (consulte el Ejemplo 11.2.2 (c)).
[Demuestre el principio de inducción en la forma de Axioma 7.5.1 por contradicción.]
Sugerencia: Axiom 5.4.1 es equivalente a Axiom 5.1.1. Suponiendo que el principio de buen orden
es falso, existe un subconjunto B & # 8230 considerar el complemento de B y aplicar el fuerte
principio de inducción.
Matemáticas 109 SS1 2020
Tarea 3
Lec A Prof. Chow
# 10. Sea X1,. . . , Xk ser conjuntos finitos, donde k es un número entero positivo. Dado un conjunto de j distintos
índices I = ⊆ Nk = <1, 2,. . . , k>, donde 1 ≤ j ≤ k, defina
XI =

Xi = Xi1 ∩ Xi2 ∩ · · · ∩ Xij.
yo
(a) Para cada subconjunto no vacío I ⊆ N3 escriba el conjunto XI. Por ejemplo, si I = <1, 3>,
entonces XI = X1 ∩ X3.
(b) Escriba la suma
X
(−1) | I | −1 | XI |.
∅6 = I⊆N3
Haga esto para que la primera línea tenga los términos con | I | = 1, la segunda línea tiene los términos con
| Yo | = 2, y la tercera línea tiene los términos con | I | = 3. Por ejemplo, si está enumerando el
términos en "orden lexigráfico", entonces el primer término de la primera línea sería | X1 |, ya que este
es igual a (−1) | <1> | −1 | X <1> |.
(c) Hecho: La suma del inciso (b) es igual a | X1 ∪ X2 ∪ X3 |. Es decir,
X
| X1 ∪ X2 ∪ X3 | =
(−1) | I | −1 | XI |.
∅6 = I⊆N3
Compruebe que efectivamente esta es la afirmación (no pruebe) de la Proposición 10.3.2.
# 11. Suponga que k es un número entero positivo que conocemos para cualquier conjunto finito Y1,. . . , Yk,
que (principio de inclusión-exclusión para k conjuntos)
| Y1 ∪ · · · ∪ Yk | =
X
(−1) | I | −1 | YI |.
∅6 = I⊆Nk
Sea X1,. . . , Xk + 1 sean conjuntos finitos. Por supuesto,
X1 ∪ · · · ∪ Xk + 1 = (X1 ∪ · · · ∪ Xk) ∪ Xk + 1.
(a) Demuestre por inducción que para cualquier n + 1 conjuntos A0, A1,. . . , Un
(A1 ∪ · · · ∪ An) ∩ A0 = (A1 ∩ A0) ∪ · · · ∪ (An ∩ A0).
(1)
(b) Demuestre que (recuerde la suposición sobre k)
| X1 ∪ · · · ∪ Xk + 1 | =
X
∅6 = I⊆Nk
(−1) | I | −1 | XI | + | Xk + 1 | - | (X1 ∩ Xk + 1) ∪ · · · ∪ (Xk ∩ Xk + 1) | .
Matemáticas 109 SS1 2020
Tarea 3
Lec A Prof. Chow
# 12. Continuación del problema anterior.
(a) Para 0 ≤ i ≤ k, sea Zi = Xi ∩ Xk + 1. Explique por qué si J ⊆ Nk, entonces
ZJ = XJ ∩ Xk + 1 = XJ∪ .
(b) Demuestre que si ∅ =
6 I ⊆ Nk + 1, luego exactamente uno de los siguientes valores:
(i) ∅ =
6 I ⊆ Nk,
(ii) I = ,
(iii) I = J ∪ , donde ∅ =
6 J ⊆ Nk.
(c) Explique por qué
X
(−1) | I | −1 | XI | =
∅6 = I⊆Nk + 1
X
X
(−1) | I | −1 | XI | + | Xk + 1 | +
∅6 = I⊆Nk
(−1) | J | | XJ∪ |.
∅6 = J⊆Nk
(d) Demuestre que la suma del inciso (b) del problema anterior es igual a la suma del inciso
(c) de este problema, es decir,
X
| X1 ∪ · · · ∪ Xk + 1 | =
(−1) | I | −1 | XI |.
∅6 = I⊆Nk + 1
# 13. Haga el n. ° 4 en los problemas III de las págs. 182-183. Este es el principio de inclusión-exclusión.
Esto no debería ser mucho trabajo dado todo el trabajo que ha realizado en los problemas anteriores # 8
y # 9.
# 14. Demuestre, por inducción sobre n, que para cualquier conjunto X1,. . . , Xn, la siguiente igualdad para
funciones características:
χX1 ∪ ··· ∪Xn =
X
(−1) | I | −1 χXI.
∅6 = I⊆Nn
[La prueba de este problema está relacionada con los problemas # 11– # 13. Pero es mucho más corto.]

Compra respuesta para ver completa
adjunto archivo


1.1: El principio del buen orden y la inducción matemática - Matemáticas

La suposición básica que uno hace sobre el orden de los números enteros es la siguiente:

Principio de buen orden. Cada conjunto no vacío de enteros positivos tiene un elemento mínimo.

A partir de esta suposición, es fácil probar el siguiente teorema, que subyace al método de demostración por inducción:

Teorema 1: Principio de inducción matemática Sea A un conjunto de números enteros positivos. Considere las siguientes dos condiciones:

(ii)Para cualquier entero positivo k, si k está en A, entonces k + 1 está en un.

Si A es cualquier conjunto de enteros positivos que satisfacen estas dos condiciones, entonces A consta de todos los enteros positivos.

PRUEBA: Si A no contiene todos los enteros positivos, entonces por el principio de ordenamiento correcto (arriba), el conjunto de todos los enteros positivos que son no en A tiene un elemento mínimo llámalo B. De la condición (i), B & ne 1 por lo tanto B > 1.

Por lo tanto, B & menos 1> 0, y B & mdash 1 & isin A porque B es el menos entero positivo no en A. Pero luego, de la Condición (ii), B &es en A, lo cual es imposible. ■

Aquí hay un ejemplo de cómo se usa el principio de inducción matemática: Demostraremos la identidad

es decir, la suma del primero norte enteros positivos es igual a norte(norte + 1)/2.

Dejar A constan de todos los enteros positivos norte para cual Ecuación (1) es verdad. Entonces 1 está en A porque

A continuación, suponga que k es cualquier entero positivo en A debemos demostrar que, en ese caso, k + 1 también está en A. Para decir eso k es en A significa que

Añadiendo k + 1 a ambos lados de esta ecuación, obtenemos

De esta última ecuación, k + 1 & isin A.

Hemos demostrado que 1 & isin A, y además, que si k &es en A, luego k + 1 & isin A. Entonces, por el principio de inducción matemática, todos los enteros positivos están en A. Esto significa que Ecuación (1) es cierto para cada entero positivo, como se afirma.

Utilice la inducción matemática para demostrar lo siguiente:

1 1 + 3 + 5 + ⋯ + (2norte & menos 1) = norte 2

(Es decir, la suma de la primera norte números enteros impares es igual a norte 2 .)

2 1 3 + 2 3 + ⋯ + norte 3 = (1 + 2 + ⋯ + norte) 2

3 1 2 + 2 2 + ⋯ + norte 2 = norte(norte + 1)(2norte + 1)

4 1 3 + 2 3 + ⋯ + norte 3 = norte(norte + 1) 2

5

6 1 2 + 2 2 + ⋯ + (norte & menos 1) 2 2 + 2 2 + ⋯ + norte 2

Si usted es el propietario de los derechos de autor de cualquier material contenido en nuestro sitio y tiene la intención de eliminarlo, comuníquese con el administrador de nuestro sitio para su aprobación.


Teoría de números: en contexto e interactiva

Antes de continuar, necesitamos un poco de revisión. Los siguientes tres temas pueden considerarse requisitos previos para el curso.

Subsección 1.2.1 Buen orden

El primer principio es simple y profundo. Es una propiedad profunda de los enteros positivos, pero le damos su nombre habitual.

Axioma 1.2.1. Principio de buen orden.

Cualquier conjunto no vacío de enteros positivos tiene un elemento mínimo / mínimo.

Este principio en realidad se cumple con cualquier subconjunto de ( mathbb) que está delimitado por debajo, como ( mathbb) (recuerde la Definición 1.0.1).

Usémoslo como ejemplo para probar el siguiente hecho que probablemente no sabía que requería prueba.

Hecho 1.2.2. Enteros consecutivos.

No hay números enteros entre 0 y 1.

Prueba .

Esta prueba procede por contradicción. Suponga que hay algunos enteros de este tipo y deje

Este conjunto debe tener un elemento mínimo (a text <,> ) y (0 & lta & lt1 text <.> ) Si multiplicamos por (a ) (que es positivo), obtenemos (0 & lta ^ 2 & lta text <.> )

Por lo tanto, (a ^ 2 ) es otro número entero tal que (0 & lta ^ 2 & lt1 text <,> ) entonces (a in S text <,> ) pero también sabemos que (a ^ 2 & lta text <.> ) Entonces (a ^ 2 ) es un elemento de (S ) que es menor que el elemento menor de (S text <.> ) Eso es una contradicción, entonces nuestra suposición original estaba mal y no hay tales enteros (es decir, (S ) está vacío).

Observación 1.2.3.

Para revisar, las pruebas de y ambas comienzan asumiendo la negación de la conclusión. Una prueba por contraposición utiliza ese supuesto para probar la negación del supuesto original. Una prueba por contradicción, por otro lado, conduce a algo de absurdo, pero no necesariamente solo niega los supuestos originales. En la demostración anterior del Hecho 1.2.2, la contradicción es que no puedes tener dos elementos más pequeños diferentes de un conjunto.

Subsección 1.2.2 Inducción

A veces necesitamos una forma de probar una declaración para todos los enteros (n ) después de un cierto punto, por ejemplo, enteros mayores o iguales que (n = 1 text <.> ). Esto se suele llamar. Por lo general, hay dos pasos en una inducción "simple" típica.

Primero probamos el "caso base" (a menudo (n = 1 ) o (n = 0 )).

Luego probamos el "paso de inducción", que el caso (n = k ) implica el caso (n = k + 1 text <.> )

Estos se combinan para probar un hecho para todas casos (n geq 1 text <.> )

Ejemplo 1.2.4. Arquetipo de inducción.

El caso base es verificar que (1 = frac <1 (1 + 1)> <2> text <,> ) lo cual es fácil.

El paso de inducción comienza con el supuesto de que

y luego procede mostrando que la fórmula sigue siendo verdadera cuando (k ) se reemplaza con (k + 1 text <.> ) Para esta prueba, para agregar solo un entero más (k + 1 ) a la suma significa

(que podemos ver reescribiendo la suma). Entonces podemos simplemente conectar la inducción suposición para obtener

que es exactamente lo que se requiere para terminar el paso de inducción, a saber

En relación con algunos otros axiomas básicos, uno puede realmente tomar la legitimidad de la inducción como un axioma final y usarlo para demostrar que el buen orden (Axioma 1.2.1) es verdadero. Los instructores desearán tener en cuenta que lo contrario es falso 4. No incluiremos ninguna de estas pruebas (o una colección de axiomas relevantes, como el de Peano) aquí, pero tenga en cuenta la útil exposición en [E.7.33].

Subsección 1.2.3 Divisibilidad

Definición 1.2.5.

Si un entero (n ) se puede escribir como un producto (kd = n ) de dos enteros (k ) y (d text <,> ) entonces decimos que (d ) (n text <,> ) o que (n ) es por (d text <,> ) o que (d ) es una de (n text <.> ) Escribimos (d mid n ) para denotar que (d ) divide (n text <.> )

Ejemplo 1.2.6.

Por ejemplo, el concepto de que (n ) es par es lo mismo que (2 mid n text <.> )

La divisores de (n = 8 ) son… ( pm 1, pm 2, pm 4, pm 8 text <.> ) (No olvide los divisores negativos).

Muy a menudo podemos escribir esto de forma genérica, por lo que, por ejemplo, (n mid x + 1 ) significa que (x + 1 ) se puede escribir como el producto de (n ) y algún otro número entero (m texto <.> )

Ocasionalmente usamos el término para denotar un divisor positivo de (n ) que no es (n text <> ) en el ejemplo con (n = 8 text <,> ) (1 text < ,> ) (2 text <,> ) y (4 ) son todos divisores propios.

Hay muchas cosas interesantes que decir sobre la divisibilidad. Let's prove a somewhat unexpected statement using induction and just what we already know.

Example 1.2.7 .

Show that (4mid 5^n-1) for (ngeq 0 ext<.>)

This proof will proceed by induction. This time the base case will be (n=0 ext<.>) We'll try to make the steps clear with separate bullets.

Base step: If (n=0) the formula says that 4 divides (5^0-1=1-1=0 ext<,>) which is definitely true.

Suppose (4mid 5^k-1 ext<.>) Then, by Definition 1.2.5, (5^k-1=4x) for some integer (x ext<.>)

Hence (5^k=1+4x) is a fact we could use later.

Our goal in this step is to show (4mid 5^-1 ext<.>)

Since we need something true about (5^-1 ext<,>) let's consider (5^) first. The key observation will be that (5^=5^kcdot 5 ext<.>)

Using the fact we obtained from the induction assumption we can write this as (5^kcdot 5=(1+4x)cdot 5 ext<>) this means that

Certainly (20x+4) is divisible by 4.

Thus we have shown that (4mid 5^-1 ext<,>) so we have finished the induction step, and our proof by induction is complete.

There are lots of other propositions about divisibility you are probably familiar with from previous courses. Here is a sampler.

Proposition 1.2.8 . Divisibility Facts.

If (amid b) and (bmid c) then (amid c ext<.>)

If (amid b) then (camid cb ext<.>)

If (cmid a) and (cmid b) then (cmid au+bv) for any integers (u,v ext<.>)

If (n>0) then all divisors of (n) are less than or equal to (n ext<.>)

These are not hard to prove (see Exercise 1.4.1). For instance, the second one can be proved by simply noting (b=ka) for some (kinmathbb ext<,>) so that (cb=c(ka)=c(ak)=(ca)k ext<.>) The others are similar, and are good practice with using basic algebraic manipulation in proofs.


Ver el vídeo: Inducción Matemática (Septiembre 2021).