Artículos

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


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 ), probamos 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 ).

Utilice 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 había compartido 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 .↩

5 Inducción matemática

En esta sección, discutiremos una técnica poderosa para probar resultados sobre números naturales llamada inducción matemática. Recuerda que el conjunto de números naturales es ( NN = <0, 1, 2, 3, dots > ). En particular, hay infinitos números naturales, por lo que no podemos resolver cada caso individualmente. La idea principal detrás de la inducción es que se puede llegar a cada número natural desde (0 ) agregando (1 ) repetidamente. Por lo tanto, si podemos mostrar que una declaración es válida para (n = 0 ), y podemos mostrar que si la declaración es válida para (n ), entonces también es válida para (n + 1 ), entonces esto será probar el enunciado para todo (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 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 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.


Comentarios

Que sean equivalentes significa que si asume que se cumple el principio de buen orden, entonces puede probar que la inducción es un método válido de prueba y viceversa. De hecho, uno de ellos se toma como axioma, la mayoría de los autores toman la inducción como el axioma que eligen.

Sí, equivalente solo significa que las declaraciones se implican entre sí.

Dado que las declaraciones son equivalentes, realmente no importa cuál elija como axioma. La inducción se usa a menudo como axioma principalmente porque es el [editar: método de prueba] que se usa con más frecuencia. Si tomara el principio de buen ordenamiento, en una demostración que se reduce a los axiomas, aún tendría que demostrar que el principio de buen ordenamiento implica inducción matemática.


Algunos ejercicios de inducción

1. Sea D n la cantidad de formas de cubrir los cuadrados de un tablero de 2xn usando dominós simples. Entonces es fácil ver que D 1 = 1, D 2 = 2 y D 3 = 3. Calcule algunos valores más de D n y adivine una expresión para el valor de D n y use la inducción para demostrar que tiene razón.

2. La desigualdad del triángulo dice que para dos números reales cualesquiera xey,.
Muestre eso para cualquier n números reales & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp

& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp

3. ¿De cuántas formas hay de cubrir los cuadrados de un tablero de ajedrez de 2xn con dominó?

Sea D n el número de tales formas. Por ejemplo, D 1 = 1, D 2 = 2 y D 3 = 3 como

& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp

Calcula el valor de D 4 y tal vez D 5, y adivina una expresión para D n. Para verificar su conjetura, deberá utilizar la forma fuerte de inducción. Eso significa que en lugar de simplemente asumir que el resultado es verdadero para algunos k, asume que es cierto para todos los valores menores que algunos k, y luego demuestra que debe ser cierto para k.

(B). ¿La serie converge o diverge?

5. Sea a n el número de subconjuntos de <1, 2, 3,. n> (incluido el conjunto vacío
y el propio set.)
& nbsp & nbsp & nbsp (a). Muestre a n = 2a n-1. (Esto es bastante simple, no necesita inducción aquí).
& nbsp & nbsp & nbsp (b). Adivina una fórmula para el valor de una ny usa la inducción para demostrar que tienes razón.

6. Demuestre que para cualquier n> = 1, 4 | 3 (2n-1) +1

7. Demuestre por inducción: Para cualquier n> = 1, 1 3 + 2 3 + 3 3 +. + n 3 = (1 + 2 + 3 +. + n) 2.

& nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp & nbsp Ejemplos de pruebas de inducción

1. Demuestre que para todo n> = 1,

Argumentamos por inducción. Para n = 1, la expresión tiene el valor. Entonces, la afirmación es verdadera para n = 1.

Ahora suponga que para algún entero k,. Entonces debe existir un número entero t tal que. Ahora debemos mostrar que la aserción debe ser verdadera para k + 1, es decir, eso '.

Así que tenemos, y el resultado sigue por inducción.

2. Demuestre por inducción que la suma 1 + 3 + 5 + 7 +. + 2n-1 es un cuadrado perfecto.

Es casi imposible probar esta afirmación sin probar mucho más.

Por conveniencia, sea S n = 1 + 3 + 5 + 7 +. + 2n-1. Entonces S n + 1 = S n + (2n + 1).

Ahora se ve fácilmente que el resultado es cierto en el caso k = 1, ya que 1 es un cuadrado perfecto.

Ahora suponga que S k es un cuadrado perfecto, digamos S k = t 2 para algún t. Entonces debemos demostrar que S k + 1 también es un cuadrado perfecto. Bueno, S k + 1 = S k + (2k + 1) = t 2 + 2k +1.

¿¿Ahora que?? Bueno, parece que estamos estancados. La prueba no va a ninguna parte.

Pero mire lo que sucede si tratamos de probar el resultado más fuerte de que S n = n 2.

Nuestro argumento sería casi el mismo que antes, excepto que al final

& nbsp & nbsp & nbsp S k + 1 = S k + (2k + 1) = k 2 + 2k +1 = (k + 1) 2.

¡Y ahora la prueba de inducción funciona!

Esta es la paradoja del inventor: a menudo es más fácil demostrar un resultado más sólido que el que necesita. Aquí demostramos no solo que S n es un cuadrado perfecto, sino que es un cuadrado perfecto particular, a saber, n 2.

3. Sea f n el n-ésimo número de Fibonacci,
Demuestre por inducción: Para todo n> = 1, 2 | f 3n (es decir, f 3n es par)


Prueba .
Argumentamos por inducción. Para n = 1, esto dice que f 3 = 2 es par, lo cual es.

Ahora suponga que para algunos k, f 3k es par. Entonces f 3k = 2m para algún entero m.
Ahora debemos demostrar que f 3 (k + 1) es par.

Entonces, f 3 (k + 1) = f 3k + 3 = f 3k + 2 + f 3k + 1 = f 3k + 1 + f 3k + f 3k + 1 = 2f 3k + 1 + f 3k = 2 (f 3k +1 + m).

4. Demuestre por inducción: para todos los números enteros n> = 1,

Prueba: Para n = 1, esto afirma eso, lo cual es ciertamente cierto. Ahora suponga que para algún entero k> = 1,. Por tanto, hay un entero m tal que.

Nosotros lo reclamamos. Pero esto equivale a mostrar eso.
Sin embargo, y entonces es un múltiplo de 4 y el resultado sigue por inducción.

5. Demuestre por inducción: Para cualquier n> = 1, 7 | 8 n - 1.
Argumentamos por inducción. Para n = 1, esto solo dice que 7 | 7 que es cierto.
Ahora suponga que para algunos k> = 1, 7 | 8 k - 1. De modo que 8 k - 1 = 7t para algún número entero t.
Debemos demostrar que 7 | 8 k + 1 - 1. Pero, 8 k + 1 - 1 = 8 (8 k - 1) + 7 = 8 (7t) + 7 = 7 (8t +1).
Entonces tenemos 8 k + 1 - 1 es un múltiplo de 7 y entonces, 7 | 8 k + 1 - 1.

Un problema de la serie de Fibonacci

Recuerde que los números de Fibonacci están definidos por la relación de recurrencia,

f norte = f norte-1 + f norte-2 norte> 2, f 1 = 1, f 2 = 1.

Entonces, f 1 = 1, f 2 = 1, f 3 = 2, f 4 = 3, f 5 = 5, f 6 = 8, f 7 = 13, f 8 = 21, f 9 = 34,.

En este ejercicio determinaremos algunas propiedades muy interesantes de los números de Fibonacci.

A. Muestre por inducción que para todo n> 2.

C. Muestre (mediante una simple manipulación algebraica) eso.

D. Recuerde que toda secuencia acotada y monótona converge. Usando este hecho, demuestre:

Lema. Si una n es una secuencia acotada en la que

E. Demuestre que satisface las condiciones del lema en (D). En consecuencia, sabemos que la secuencia debe converger hasta algún límite t.

Problema: Encuentre el valor exacto de t. Tenga en cuenta que por (A) su respuesta debe ser un número entre 1 y 2.

F. Usando el resultado de (E), determine si la serie de potencias converge o diverge.


1.3 Principio de ordenación adecuada

Este es uno de los más de 2.400 cursos de OCW. Explore los materiales para 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.


Contenido

Cada conjunto bien ordenado tiene un orden único isomorfo a un número ordinal único, llamado tipo de orden del conjunto bien ordenado. La posición de cada elemento dentro del conjunto ordenado también viene dada por un número ordinal. En el caso de un conjunto finito, la operación básica de contar, encontrar el número ordinal de un objeto particular, o encontrar el objeto con un número ordinal particular, corresponde a asignar números ordinales uno por uno a los objetos. El tamaño (número de elementos, número cardinal) de un conjunto finito es igual al tipo de orden. El conteo en el sentido cotidiano generalmente comienza desde uno, por lo que asigna a cada objeto el tamaño del segmento inicial con ese objeto como último elemento. Tenga en cuenta que estos números son uno más que los números ordinales formales según el orden isomorfo, porque son iguales al número de objetos anteriores (que corresponde a contar desde cero). Así para finito norte, la expresion "norte-th elemento "de un conjunto bien ordenado requiere contexto para saber si esto cuenta desde cero o uno. En una notación" β-th elemento "donde β también puede ser un ordinal infinito, normalmente contará desde cero.

Para un conjunto infinito, el tipo de orden determina la cardinalidad, pero no a la inversa: los conjuntos bien ordenados de una cardinalidad particular pueden tener muchos tipos de orden diferentes, consulte la Sección #Números naturales para un ejemplo simple. Para un conjunto infinito contable, el conjunto de posibles tipos de orden es incluso incontable.

Números naturales Editar

El orden estándar ≤ de los números naturales es un buen orden y tiene la propiedad adicional de que cada número natural distinto de cero tiene un predecesor único.

Otro buen orden de los números naturales se da al definir que todos los números pares son menores que todos los números impares, y el orden habitual se aplica dentro de los pares y las probabilidades:

Este es un conjunto bien ordenado del tipo de orden ω + ω. Cada elemento tiene un sucesor (no hay ningún elemento más grande). Dos elementos carecen de predecesor: 0 y 1.

Enteros Editar

A diferencia de la ordenación estándar ≤ de los números naturales, la ordenación estándar ≤ de los enteros no es una ordenación correcta, ya que, por ejemplo, el conjunto de enteros negativos no contiene un elemento mínimo.

La siguiente relación R es un ejemplo de ordenación correcta de los números enteros: x R y si y solo si se cumple una de las siguientes condiciones:

  1. X = 0
  2. X es positivo, y y es negativo
  3. X y y son positivos y Xy
  4. X y y son negativos y |X| ≤ |y|

Esta relacion R se puede visualizar de la siguiente manera:

R es isomorfo al número ordinal ω + ω.

Otra relación para ordenar bien los enteros es la siguiente definición: Xz y si y solo si (|X| & lt |y| o (|X| = |y| y Xy)). Este orden de pozo se puede visualizar de la siguiente manera:

Reales Editar

La ordenación estándar ≤ de cualquier intervalo real no es una ordenación bien, ya que, por ejemplo, el intervalo abierto (0, 1) ⊆ [0,1] no contiene un elemento mínimo. A partir de los axiomas ZFC de la teoría de conjuntos (incluido el axioma de elección) se puede demostrar que existe un buen orden de los reales. También Wacław Sierpiński demostró que ZF + GCH (la hipótesis del continuo generalizado) implica el axioma de elección y, por lo tanto, un buen orden de los reales. No obstante, es posible demostrar que los axiomas ZFC + GCH por sí solos no son suficientes para probar la existencia de un orden definible (mediante una fórmula) de los reales. [1] Sin embargo, es consistente con ZFC que existe un buen orden definible de los reales; por ejemplo, es consistente con ZFC que V = L, y de ZFC + V = L se sigue que una fórmula particular ordena bien los reales, o de hecho cualquier conjunto.

Un subconjunto incontable de los números reales con el orden estándar ≤ no puede ser un orden correcto: Supongamos X es un subconjunto de R bien ordenado por ≤. Para cada X en X, dejar s(X) ser el sucesor de X en ≤ pedido en X (a no ser que X es el último elemento de X). Dejar A = < (X, s(X)) | XX > cuyos elementos son intervalos no vacíos y disjuntos. Cada uno de estos intervalos contiene al menos un número racional, por lo que hay una función inyectiva de A para Q. Hay una inyección de X para A (excepto posiblemente por un último elemento de X que podría asignarse a cero más tarde). Y es bien sabido que hay una inyección de Q a los números naturales (que podrían elegirse para evitar llegar a cero). Por lo tanto, hay una inyección de X a los números naturales lo que significa que X es contable. Por otro lado, un subconjunto numerablemente infinito de los reales puede o no ser un buen orden con el estándar "≤". Por ejemplo,

  • Los números naturales están bien ordenados bajo el orden estándar ≤.
  • El conjunto <1 / n: n = 1,2,3. > no tiene ningún elemento menor y, por lo tanto, no es un buen pedido según el pedido estándar ≤.
  • El conjunto de números <- 2 -norte | 0 ≤ norte & lt ω> tiene el tipo de orden ω.
  • El conjunto de números <- 2 -norte − 2 −metronorte | 0 ≤ metro,norte & lt ω> tiene el tipo de orden ω 2. El conjunto anterior es el conjunto de puntos límite dentro del conjunto. Dentro del conjunto de números reales, ya sea con la topología ordinaria o con la topología de orden, 0 también es un punto límite del conjunto. También es un punto límite del conjunto de puntos límite.
  • El conjunto de números <- 2 -norte | 0 ≤ norte & lt ω> ∪ <1> tiene el tipo de orden ω + 1. Con la topología de orden de este conjunto, 1 es un punto límite del conjunto. Con la topología ordinaria (o equivalentemente, la topología de orden) de los números reales no lo es.

Si un conjunto está totalmente ordenado, los siguientes son equivalentes entre sí:

  1. El conjunto está bien ordenado. Es decir, cada subconjunto no vacío tiene un elemento mínimo. funciona para todo el conjunto ordenado.
  2. Cada secuencia estrictamente decreciente de elementos del conjunto debe terminar después de un número finito de pasos (asumiendo el axioma de elección dependiente).
  3. Cada suborden es isomorfo a un segmento inicial.

Cada conjunto bien ordenado se puede convertir en un espacio topológico dotándolo de la topología de orden.

Con respecto a esta topología, puede haber dos tipos de elementos:

    - estos son los mínimos y los elementos con un predecesor. - este tipo no ocurre en conjuntos finitos, y puede ocurrir o no en un conjunto infinito los conjuntos infinitos sin punto límite son los conjuntos de tipo de orden ω, por ejemplo norte.

Para subconjuntos podemos distinguir:

  • Subconjuntos con un máximo (es decir, subconjuntos que están delimitados por sí mismos) este puede ser un punto aislado o un punto límite de todo el conjunto, en el último caso puede o no ser también un punto límite del subconjunto.
  • Los subconjuntos que son ilimitados por sí mismos pero están delimitados en el conjunto completo, no tienen un máximo, pero un supremo fuera del subconjunto si el subconjunto no está vacío, este supremo es un punto límite del subconjunto y, por lo tanto, también del conjunto completo si el subconjunto es vacío este supremum es el mínimo de todo el conjunto.
  • Subconjuntos que no están delimitados en todo el conjunto.

Un subconjunto es cofinal en todo el conjunto si y solo si no está acotado en todo el conjunto o tiene un máximo que también es el máximo de todo el conjunto.

Un conjunto bien ordenado como espacio topológico es un primer espacio contable si y solo si tiene un tipo de orden menor o igual a ω1 (omega-uno), es decir, si y solo si el conjunto es contable o tiene el tipo de orden incontable más pequeño.


El principio del buen orden

Principio de buen orden. Cada colección no vacía de números naturales tiene un elemento mínimo.

Observe, antes de probar esto, que un enunciado similar no es cierto para muchos conjuntos de números. El intervalo , por ejemplo, no tiene ningún elemento menor. El conjunto de enteros pares no tiene ningún elemento mínimo. El conjunto de números naturales no tiene el elemento más grande.

Prueba. Demostraremos lo contrapositivo, es decir, que si una colección de números naturales no tiene ningún elemento mínimo, entonces debe estar vacía.

Dejar ser una colección no vacía de números naturales. Considerar , los números naturales que no están en (en notación de conjuntos, ). Ya que no está vacío, no es todo . Lo mostraremos, para todos , es en .

caso base : Si , luego es lo mínimo. Entonces , es decir. .

paso inductivo: Suponga . Si alguno de los números es menor que estaban en , entonces uno de ellos sería el menor (ya que solo hay un número finito de tales números y probamos que cada conjunto finito tiene un elemento mínimo). Entonces ninguno de los números es en . Si , luego sería lo mínimo. Entonces , es decir. . Esto completa el paso inductivo.

Así que hemos demostrado que cada número natural está en , Lo que significa que debe estar vacío. Esto establece el contrapositivo del teorema.

El principio de buen orden se puede utilizar para probar todo tipo de teoremas sobre números naturales, generalmente asumiendo algún conjunto no está vacío, encontrando un elemento mínimo de , y "inducir hacia atrás" para encontrar un elemento de menos que - dando así una contradicción y demostrando que esta vacio. En este sentido, el principio de buen ordenamiento y el principio de inducción matemática son solo dos formas de ver una misma cosa.

De hecho, se puede probar que WOP, PCI y PMI son todos lógicamente equivalentes, por lo que podríamos haber tomado cualquiera de ellos como nuestro quinto axioma para los números naturales.

Teorema fundamental de la aritmética. Cualquier número natural mayor que 1 puede escribirse como producto de números primos.

Prueba. Dejar ser el conjunto de números naturales mayores que 1 que no se pueden escribir como producto de números primos. Por WOP, tiene un elemento mínimo .

Claramente no puede ser primo, entonces es compuesto. Entonces podemos escribir , donde ninguno de los y es 1. Entonces y . Si ambos y tenía factorizaciones primos, entonces también lo haría . Por lo tanto, al menos uno de y no tiene una factorización prima (al volver a etiquetar, podemos asumir que es ). Pero y , asi que no fue menos importante en .

Esta contradicción establece que no tiene ningún elemento mínimo, por lo tanto, WOP debe estar vacío. Entonces, todo número natural mayor que 1 se puede escribir como el producto de números primos.

Observe que esta prueba tiene más o menos los mismos "jugosos bits" que la prueba de PCI.

El algoritmo de división. Dejar ser números naturales. Entonces hay enteros no negativos así que eso y . Es más, y son únicos. Nosotros llamamos la cociente y la recordatorio.

Este teorema se llama algoritmo de división porque afirma que cualquier número natural se puede dividir, con el resto, por cualquier otro número natural.

Prueba. Dado y , Si , luego establece y . Luego , y según sea necesario.

Si , colocar y .

Nos quedamos con el caso . Considere el conjunto . Ya que , para todos . En particular, , o equivalente . Entonces , por eso .

Ya que no está vacío, por WOP, tiene un elemento mínimo, que llamaremos . Colocar y . Por elección de , tenemos , pero tenemos que demostrar que .

Ya que es el menos en , no puede ser un elemento de . Entonces .

Tenemos que demostrar que . Supongamos, por el contrario, que . Luego

así que eso . Pero , que es un elemento de . Esta contradicción establece que según sea necesario.

Ahora que hemos establecido la existencia de y , demostremos su singularidad. Considere dos pares , así que eso

Sin pérdida de generalidad, asuma . Tenemos

Ya que , esto significa que garantías , y eso si . Te mostraremos que , por eso , es decir, el par cociente-resto es único.

Considere el conjunto como arriba, con el mínimo elemento . Si , luego , asi que . Pero entonces no puede ser un cociente. Entonces . Por otro lado, si , luego

y restando de ambos lados tenemos . Pero es menos, entonces . Esta contradicción establece que .

Entonces vemos eso . Pero el mismo argumento se aplica a , por eso .

Corolario. Cualquier número entero es par o impar.

Prueba. Dado un número entero , Si incluso hemos terminado. Así que suponga ni siquiera, es decir, sabemos que no poder escribir para cualquier .

El algoritmo de división dice que debemos poder escribir para algunos . Desde que descartamos , Debemos tener , es decir. es impar.

Tenga en cuenta que establecimos previamente que ningún número entero puede ser tanto par como impar. Ahora sabemos que "impar" y "ni siquiera" son, de hecho, sinónimos.

Pruebas de inducción "disfrazadas"

Podemos usar el WOP para dar una especie de prueba de inducción disfrazada. Considerar:

Afirmar. La suma del primero los números naturales son .

Normalmente, demostraríamos esto por inducción.

Ejercicio. Escriba una prueba de esta afirmación por inducción ordinaria.

Pero podemos configurar una prueba que utilice el principio de buen orden, como este:

Prueba. Supongamos que no. Entonces hay un número natural (llámalo ) de modo que la suma de la primera los números naturales no lo son . Considere el conjunto de todos esos números:

Nuestra suposición es que en particular no está vacío. (Creemos en nuestro corazón que no existen tales números, es decir, que esta vacio. Pero esta es una prueba de reductio ad absurdum, así que tendremos que seguir adelante).

Según el principio del buen orden, tiene un elemento mínimo, que llamaremos .

Quizás ? No porque . Entonces . Pero entonces tiene un predecesor, .

Ya que , sabemos (, después de todo, fue menos entre los elementos de ).

Eso es, .

Ahora, considere :

lo que muestra que en realidad, . ¡Pero esto es una contradicción! Entonces, nuestra suposición inicial era incorrecta y, por lo tanto, la afirmación es verdadera. .

Ahora, he resaltado algunas partes de la prueba en verde y naranja. ¿Por qué? La parte verde es lo que sería el caso base si escribiéramos una prueba de inducción ordinaria. La parte naranja es el paso inductivo (desde para ) .

De hecho, cualquier prueba por inducción ordinaria puede elaborarse de esta manera, si lo desea.


MATH 4383 - Teoría de números y criptografía

Prerrequisitos: & # 160MATH 3330 o MATH 3336.

Descripción del curso del catálogo: & # 160Teoría de la divisibilidad, primos y su distribución, teoría de congruencias y aplicación en seguridad, representaciones enteras, pequeño teorema de Fermat y teorema de Euler, raíces primitivas, reciprocidad cuadrática e introducción a la criptografía

Libro de texto: Notas de la clase del instructor

Contenido del curso:

La teoría de números, una vez considerada la materia más pura, se ha convertido en una herramienta esencial para proporcionar seguridad informática e Internet. Este curso cubrirá los temas de la introducción estándar de un semestre a la teoría de números, así como sus aplicaciones en informática y criptografía. Incluye: & # 160Teoría de la divisibilidad, primos y su distribución, teoría de congruencias y su aplicación en seguridad, representaciones de enteros (expansiones binarias y de base, algoritmo de conversión de base), pequeño teorema de Fermat y teorema de Euler, raíces primitivas, reciprocidad cuadrática e introducción. a la criptografía (criptografía clásica, criptografía de clave pública, criptosistema RSA, protocolos criptográficos).

Capítulo 1: Preliminares

1.1 El sistema numérico y el principio del buen orden
1.2 Inducción matemática

Capítulo 2: & # 160 Divisibilidad y factorización

2.1 Divisibilidad, máximos divisores comunes, algoritmo euclidiano
2.2 Mínimo común múltiplo
2.3 Representaciones de enteros (Representación decimal y Representación binaria de enteros)

Capítulo 3: Resolución de ecuaciones diofánticas lineales

Capítulo 4: Primes

4.1 Números primos
4.2 Factorización prima única
4.3 Prueba de primordialidad por división de prueba

Capítulo 5: La teoría de las congruencias

5.1 El concepto de congruencias
5.2 Clases de congruencia
5.3 Aplicaciones de congruencias: dígitos de control

Capítulo 6: Resolución de congruencias lineales

6.1 Resolución de congruencia lineal (simple)
6.2 Sistema de resolución de congruencias lineales, el teorema del residuo chino

Capítulo 7: Teorema de Fermat y generalización de Euler

7.1 El pequeño teorema de Fermat
7.2 El caso general: el teorema de Euler

Capítulo & # 1608: Raíces primitivas

8.1 El orden multiplicativo
8.2 Raíces promitivas (mod n)
8.3 El módulo n que no tiene raíces primitivas
8.4 Los teoremas de la existencia
8.5 Aplicaciones: el uso de raíces primitivas

Capítulo 9: Congruencias cuadráticas

9.1 Criterio de Euler
9.2 El símbolo de Legendre y sus propiedades
9.3 Ejemplos de cálculo del símbolo de Legendre
9.4 Símbolo de Jacobi
9.5 Residuos cuadráticos y raíces primitivas

Capítulo 10: Criptografía

10.1 Introducción
10.2 Criptografía de clave simétrica
10.3 Criptografía de clave asimétrica o clave pública

Adaptaciones de CSD:

Ajustes académicos / ayudas auxiliares: El Sistema de la Universidad de Houston cumple con la Sección 504 de la Ley de Rehabilitación de 1973 y la Ley de Estadounidenses con Discapacidades de 1990, relacionada con la provisión de ajustes académicos razonables / ayudas auxiliares para estudiantes que tienen una discapacidad. De acuerdo con la Sección 504 y las pautas de la ADA, la Universidad de Houston se esfuerza por proporcionar ajustes académicos razonables / ayudas auxiliares a los estudiantes que las soliciten y requieran. Si cree que tiene una discapacidad que requiere ajustes académicos / ayuda auxiliar, visite el sitio web & # 160 The Center for Students with DisABILITIES (CSD) & # 160 en & # 160 http://www.uh.edu/csd/ & # 160 para obtener más información.

Formularios de alojamiento: Los estudiantes que buscan ajustes académicos / ayudas auxiliares deben, de manera oportuna (generalmente al comienzo del semestre), proporcionar a su instructor un Formulario de adaptación del estudiante (SAF) actual (copia impresa o & # 160 en línea & # 160, como apropiado) de la oficina del CSD antes de que se pueda implementar una adaptación aprobada.

Los detalles de esta política y las responsabilidades correspondientes del estudiante se describen en & # 160 La Política de Ajustes Académicos para Estudiantes / Ayudas Auxiliares (01.D.09) & # 160 documento bajo [PASO 4: Presentación del Estudiante (5.4.1 & amp 5.4 .2), página 6]. Para obtener más información, visite la página & # 160 Center for Students with Disabilities Student Resources & # 160.

Además, si un estudiante solicita una adaptación para la prueba (aprobada por el CSD), el estudiante también completará un formulario en papel de Solicitud de adaptaciones para las pruebas individualizadas (RITA) para organizar la administración de las pruebas en la oficina del CSD. CSD sugiere que el estudiante se reúna con su instructor durante el horario de oficina y / o haga una cita para completar el formulario RITA para garantizar la confidencialidad.

* Nota: Los formularios RITA deben completarse al menos 48 horas antes de la fecha original del examen. Consulte con su & # 160 consejero & # 160 con anticipación para asegurarse de que sus pruebas se programen de manera oportuna. Please keep in mind that if you run over the agreed upon time limit for your exam, you will be penalized in proportion to the amount of extra time taken.

Counseling and Psychological Services (CAPS) can help students who are having difficulties managing stress, adjusting to college, or feeling sad and hopeless. You can reach   (CAPS) by calling 713-743-5454 during and after business hours for routine appointments or if you or someone you know is in crisis. No appointment is necessary for the   "Let's Talk"   program, a drop-in consultation service at convenient locations and hours around campus.


Andrew Cooper

Well-Ordering Principle. Every nonempty collection of natural numbers has a least element.

Observe, before we prove this, that a similar statement is not true of many sets of numbers. The interval $(0,1)$, for example, has no least element. The set of even integers has no least element. The set of natural numbers has no greatest element.

Prueba. We’ll prove the contrapositive, namely, that if a collection of natural numbers has no least element, then it must be empty.

Let $T$ be a nonempty collection of natural numbers. Consider $S$, the natural numbers that aren’t in $T$ (in set notation, $S=mathbbsetminus T$). Since $T$ isn’t empty, $S$ isn’t all of $mathbb$. We’ll show that, for all $ninmathbb$, $n$ is in $S$.

base case $n=1$: If $1in T$, then $1$ is least. So $1 otin T$, i.e. $1in S$.

inductive step: Suppose $nin S$. If any of the numbers less than $n$ were in $T$, then one of them would be least (since there are only finitely many such numbers and we proved every finite set has a least element). So none of the numbers $1,ldots,n$ is in $T$. If $n+1in T$, then $n+1$ would be least. So $n+1 otin T$, i.e. $n+1in S$. This completes the inductive step.

So we’ve shown that every natural number is in $S$, which means that $T$ must be empty. This establishes the contrapositive of the theorem.$Box$

The Well-Ordering Principle can be used to prove all sort of theorems about natural numbers, usually by assuming some set $T$ is nonempty, finding a least element $n$ of $T$, and “inducting backwards” to find an element of $T$ less than $n#8211thus yielding a contradiction and proving that $T$ is empty. In this sense, the Well-Ordering Principle and the Principle of Mathematical Induction are just two ways of looking at the same thing.

Indeed, one can prove that WOP, PCI, and PMI are all logically equivalent, so we could have taken any one of them as our fifth axiom for the natural numbers.

Fundamental Theorem of Arithmetic. Any natural number greater than 1 can be written as the product of primes.

Prueba. Let $S$ be the set of natural numbers greater than 1 which cannot be written as the product of primes. By WOP, $S$ has a least element $n$.

Clearly $n$ cannot be prime, so $n$ is composite. Then we can write $n=ab$, where neither of $a$ and $b$ is 1. So $a<n$ and $b<n$. If both of $a$ and $b$ had prime factorizations, then so would $n$. Therefore at least one of $a$ and $b$ does not have a prime factorization (by relabeling, we can assume it’s $a$). But $a<n$ and $ain S$, so $n$ was not least in $S$.

This contradiction establishes that $S$ has no least element, hence by WOP must be empty. So every natural number greater than 1 can be written as the product of primes.$Box$

Observe that this proof has more or less the same “juicy bits” as the proof by PCI.

The Division Algorithm. Let $a,b$ be natural numbers. Then there are nonnegative integers $q,r$ so that leq r<b$ and $a=bq+r$. Moreover, $q$ and $r$ are unique. We call $q$ the quotient and $r$ the remainder.

This theorem is called the Division Algorithm because it asserts that any natural number can be divided, with remainder, by any other natural number.

Prueba. Given $a$ and $b$, if $a<b$, then set $q=0$ and $r=a$. Then leq r<b$, and $a=qb+r$ as required.

We are left with the case $a>b$. Consider the set $S=left<>middle| a-nb< 0 ight>$. Since $bgeq 1$, $kbgeq k$ for all $kinmathbb$. In particular, $abgeq a$, or equivalently $a-ableq 0$. So $a-(a+1)b<0$, hence $a+1in S$.

Since $S$ is nonempty, by WOP, $S$ has a least element, which we’ll call $s$. Set $q=s-1$ and $r=a-qb$. By choice of $r$, we have $a=qb+r$, but we need to show that leq r<b$.

Since $s$ is least in $S$, $q=s-1$ cannot be an element of $S$. So $r=a-qbgeq 0$.

We need to show that $r<b$. Suppose, to the contrary, that $rgeq b$. Thenegin
r&geq b
a-qb&geq b
a-qb-b&geq 0
a-(q+1)b&geq 0
fin

so that $q+1 otin S$. But $q+1=s$, which is an element of $S$. This contradiction establishes that $r< b$ as required.

Now that we have established the existence of $q$ and $r$, let us prove their uniqueness. Consider two pairs $(q,r)$, $(q’,r’)$ so thategin
a&=qb+r
a&=q’b+r’
fin

Since $bgeq 1$, this means that $rgeq r’$ guarantees $qleq q’$, and that $q=q’$ iff $r=r’$. We will show that $q=q’$, hence $r=r’$, i.e. the quotient-remainder pair is unique.

Consider the set $S$ as above, with least element $s$. If $q’>s-1$, then $q’geq s$, so $q’in S$. But then $q’$ cannot be a quotient. So $q’leq s-1$. On the other hand, if $q'<s-1$, thenegin
b> r’&=a-q’b
&> a-(s-1)b
fin

and subtracting $b$ from both sides we have >a-(s-1)b$. But $s$ is least, so $s-1 otin S$. This contradiction establishes that $q’geq s-1$.

So we see that $q’=s-1$. But the same argument applies to $q$, hence $q=q’$.$Box$

Corollary. Any integer is either even or odd.

Prueba. Given an integer $n$, if $n$ is even we’re done. So suppose $n$ is not even, i.e. we know that we no poder write $n=2k$ for any $k$.

The division algorithm says we must be able to write $n=2k+r$ for some leq r<2$. Since we ruled out $r=0$, we must have $r=1$, i.e. $n=2r+1$ is odd. $Box$

Note that we established previously that no integer could be both even and odd. Now we know that “odd” and “not even” are, in fact, synonyms.

“Disguised” Induction Proofs

We can use the WOP to give a kind of induction proof in disguise. Considerar:

Claim. The sum of the first $n$ natural numbers is $frac<2>$.

Ordinarily, we’d prove this by induction.

Exercise. Write a proof of this claim by ordinary induction.

But we can set up a proof that uses the Well-Ordering Principle, like this:

Prueba. Suppose not. Then there is some natural number (call it $p$) so that the sum of the first $p$ natural numbers isn’t $frac<2>$. Consider the set of all such numbers:

Our assumption is that $pin A$ in particular $A$ is not empty. (We believe in our hearts that there are no such numbers, i.e. that $A$ is empty. But this is a reductio ad absurdum proof, so we’ll have to roll with it.)

By the Well-Ordering Principle, $A$ has a least element, which we’ll call $N$.

Maybe $N=1$? No, because $1=frac<1cdot (1+1)><2>$. So $N>1$. But then $N$ has a predecessor, $n=N-1$.

Since $n<N$, we know $n otin A$ ($N$, after all, was least among the elements of $A$).

which shows that actually, $N otin A$. But this is a contradiction! So our initial supposition was incorrect, and thus the claim is true. $Box$.

Now, I’ve highlighted some parts of the proof in green and orange . ¿Por qué? The green part is what would be the base case if we wrote an ordinary induction proof. The orange part is the inductive step (from $n=N-1$ to $n+1=N$) .

In fact any proof by ordinary induction can be gussied up this way, if you desire.


6. Set Theory for the Natural Numbers -Order

A Set, is said to be partially ordered o un poset if there is a binary relation " " defined on satisfying the following three properties

For all

For all y

For all y It is (totally)ordered if it also satifies

For all o

Given a partially ordered set , we call a chain de if it is totally ordered.

Dejar . It is a simple matter to check that any a partial/total order on , restricts to a partial/total order on .

Proof: Verify for yourself.

Given partially ordered sets y , a one to one onto map is called an order isomorphism if

para todos

6.4.1 Lemma: Let be ordered and be a poset. Suppose we are given a one to one onto map tal que para todos then:

1. is ordered

2. is an order isomorphism.

3. If is Well Ordered so is

1. Let y be such that y

Ya que is ordered o and thus o

2. We need only show that for all . Ya que is ordered o

Pero and by hypothesis asi que and, since is one to one,

Thus we have

3. Let . Ya que is Well Ordered let be the least element of

Check that is the least element of

y are all ordered by the usual binary relations.

Dejar . Dejar m,n r,s iff metro r y norte s. This is partial ordering but not a total ordering. Compare 1,2 y 2,1

Dejar be the subset 1,n todos norte. is a chain.

Dejar y 2,4,6. 2n. then norte 2n is an order isomorphism.

Dejar be Ordered. Dejar Define, , called the segment defined by como sigue.

Si is finite it will be convenient to use the notation for the number of member in .

Example: In with the usual ordering norte y norte n-1.

Well Ordered Sets

6.6 Definition: A Set, is said to be Well Ordered (WO) if it is Ordered and every subset has a least member. That is there exists an such that for all . Note that by 6.1.2. above, we know that is unique.

It is enough to assume that is partially ordered and every subset has a least element?

Any subset of a Well Ordered Set is Well Ordered, using the same order. ¿Por qué?

Any Ordering of a finite set is a Well Ordering.

Assignment: Due Feb. 9: Show that any two orderings of a given finite set are order isomorphic.

is Well Ordered by the usual binary relation. Absent any qualifications, when we use the symbol this is the order that is implied.

Dejar 0,1,2,3,4,5. norte. with the usual order. Then defined by the
fórmula x

x 1 is an order isomorphism.This is what we "mean" when we say the Natural Numbers can be defined either as o .

y are not Well Ordered by the usual binary relation.

Suppose that we have a proposition norte .

Suppose 1 is true

para todos norte , norte norte 1 is true .

para todos norte norte is true .

Dejar be the set of all norte for which norte is not true. Suppose were not empty. Then it has a least element, l . Ya que 1 is true, l 1. We know that l 1 is true. Pero l 1 l Therefore l is true. Hence is empty.

un. Given , for any , is finite.

B. either is finite or for any integer norte 0 we can find a unique con norte.

C. There exists an order isomorphism

un. Is immediate from the observation that since , is a subset of the segment of en , which is finite.

B. Is a simple induction argument. Dejar to be the least element of

Ya que tenemos 0 . Moreover uniqueness follows from the fact that for any y

Hence 1.

Assume that for 0 I norte we can find a unique con I.

Since by assumption is not finite, let be the least element of

We need to verify that

,

hence n+1.

First note that , since if then

So

On the other hand if

y then . thus

Again uniqueness follow from the fact that since for any

y concluimos que

we can now apply the principal of mathematical induction.

First define by the formula norte

Clearly is one to one. If it were not onto let y

Suppose metro. Then contradicting the uniqueness of

Finally, let donde is defined by the formula norte n-1

Dejar be an order isomorphism. . Then

1. para todos

2. if (or ) is Well Ordered

so is (or )

Assignment: Due Feb. 9: Prove this

Dejar donde .Define an ordering on the as follows: ,the usual ordering, on and for all norte tenemos norte .

Assignment: Due Feb. 9: Show that

1. There exist a one to one onto set map

2. is a Well Ordering

3. is not order isomorphic to with the usual ordering.

Solución: We give the details for 3.

Dejar be an order isomorphism. Suppose norte Por 6.9.3 norte ,which is not possible since norte contains a finite number of elements and does not.

Finally, we gather results above to state the following theorem, which characterizes Set Theory for the Natural Numbers.

For any

1. There exists an norte and an order isomorphism

2. There exists an order isomorphism

While the set of fractions greater than 0, is not well ordered by the usual ordering, it is not hard to put a non-standard well ordering on .

Referring back to Page 0 , consider the function 2 3 Check that this is 1 to 1, hence inherits a well ordering from . This is certainly not the usual ordering since 12 y 108. hence 2 ( ). Note as well that inherits a form of mathematical induction from this well ordering albeit not a particularly useful one.


Ver el vídeo: Principio de Buen Orden - Teoría y ejemplos (Noviembre 2021).